为什么Redis用跳表不用B+树，而MySQL用B+树而不是跳表？

为什么Redis用跳表不用B+树，而MySQL用B+树而不是跳表？

引用

CSDN

1.

https://m.blog.csdn.net/weixin_45304503/article/details/143836275

在数据库领域，Redis和MySQL是两个非常重要的存储系统，但它们在数据结构的选择上却有着显著的差异。Redis的有序集合使用跳表（Skip List），而MySQL的InnoDB引擎则使用B+树。这种选择并非偶然，而是基于各自的设计目标和使用场景。本文将深入探讨为什么Redis选择跳表而不是B+树，而MySQL则相反。

B+树和跳表结构对比

我们分别从读操作和写操作两个场景来分析这两种数据结构。

B+树结构

• 读操作：B+树的结构中，每个节点都是一个16K的数据页，能存放较多的索引信息。通常三层左右就可以存储3000万左右的数据。查询一次数据，最多需要三次磁盘I/O。
• 写操作：随着数据的增加，B+树为了保持自身平衡，需要进行复杂的调整。这种平衡调整可能会导致树高变化，影响性能。

B+树这类数据结构适合大量数据的存储，而大量的数据通常不能全放内存里，必定需要存放在磁盘。由于磁盘的读写速度较慢，B+树的索引设计主要是为了加速磁盘I/O。

但是，Redis是一个内存数据库，索引在内存中的作用并不大。相反，B+树复杂的平衡逻辑会使得插入操作变慢。对于追求高速的单进程数据库来说，这种慢操作是不建议的。

跳表结构

• 读操作：跳表的每个节点存放一条数据。即使像MySQL那样存储3000万左右的数据，即使每次都能达到最优的二分查找，也需要查找2的25次方左右。当然，Redis通常不会出现这么大的key，因为这会被认为是大key，是不允许的。而且与磁盘I/O不同，内存访问速度非常快。
• 写操作：跳表的插入操作相对简单，一个节点直接插入一条数据，没有复杂的平衡过程。这种简单的逻辑使得插入操作非常快速。

总结

Redis使用跳表的原因：

• 内存数据库，查询、插入、删除的效率高，且实现简单，适合高并发、低延迟的内存操作。
• 内存管理灵活，不需要像B+树那样复杂的节点分裂和合并操作，这些操作也比较耗时。并且B+树最大的索引优势在内存中作用不大。

MySQL使用B+树的原因：

• 适合磁盘存储和大规模数据，能够高效进行范围查询和排序，支持复杂的事务管理。
• 适合持久化存储，在数据量很大的情况下，通过索引结构能够优化磁盘I/O，保持查询性能。

参考

[1] https://15721.courses.cs.cmu.edu/spring2018/papers/08-oltpindexes1/pugh-skiplists-cacm1990.pdf

[2] https://opensource.googleblog.com/2013/01/c-containers-that-save-memory-and-time.html