Redis里跳表和B树到底怎么用，性能差别啥情况分析探讨

关于Redis里跳表和B树的使用与性能差别，我们得先明白Redis这个数据库的设计初衷，Redis的核心目标是快，追求极致的读写速度，尤其是在内存中进行操作，为了实现这个目标，Redis在选择数据结构时，非常看重简单性和在内存中的高效性，理解了这一点,我们就能明白为什么Redis选择了跳表而不是B树。

Redis在哪里用了跳表？

根据《Redis设计与实现》这本书里的说明，Redis主要在两个地方使用了跳表（Skip List）：

1. 有序集合（Sorted Set）：这是跳表在Redis中最经典的应用，当有序集合的元素数量比较多（默认超过128个），或者元素的字符串长度比较长（默认超过64字节）时，Redis就会使用跳表（通常会结合字典一起使用）来实现，有序集合需要支持根据成员（member）快速查找分值（score），也需要支持根据分值范围进行快速遍历,比如ZRANGE这样的命令。
2. 集群节点：在Redis的集群模式中，节点之间需要维护和传播集群的配置信息，根据Redis的官方文档，这些节点信息在某些内部数据结构中也使用了跳表来管理,以便进行高效的查找和更新。

那Redis为什么不用B树呢？

这并不是说B树不好，而是因为B树和跳表是为不同场景设计的，B树是磁盘友好型的数据结构，它在数据库系统（如MySQL的InnoDB引擎）中是绝对的主力，它的设计目标是减少磁盘I/O次数，磁盘读写速度远远慢于内存，所以B树通过让一个节点存储多个键值对（即节点很“胖”），来降低树的高度，从而使得在查询数据时，需要访问的磁盘块（节点）尽可能少。

Redis的数据主要放在内存里，内存的访问速度极快，而且访问不同内存地址的速度是均匀的，没有磁盘那种“寻道”的巨大开销，在这种情况下，B树的优势就变得不明显了，反而,B树的结构比跳表复杂得多：

• 实现复杂度：B树需要处理节点分裂、合并、键的重新分配等复杂的逻辑，而跳表的实现非常直观，代码量少，容易调试和维护，对于Redis这样一个追求简洁高效的系统来说,简单的代码意味着更少的Bug和更高的可维护性。
• 范围查询：虽然B树也支持范围查询，但跳表在实现范围查询时更加优雅，跳表底层是一个有序链表，一旦定位到范围的起点，只需要沿着最底层的链表向后遍历即可，非常高效，B树的范围查询则需要通过中序遍历来实现,实现起来相对繁琐。
• 并发控制：在需要考虑并发读写的场景下（虽然Redis是单线程的，但一些衍生版本或类似系统会考虑多线程），跳表比B树更容易实现高效的锁机制,比如可以使用CAS操作等。

性能差别具体分析

在内存这个主战场上，跳表的性能表现通常优于B树,或者至少不逊色。

• 查询性能：对于单点查询，跳表和B树的时间复杂度都是O(log n)，效率都很高，但由于跳表的结构更简单，常数时间可能更小,在实际内存访问中可能略有优势。
• 插入和删除性能：这是跳表的一大亮点，B树的插入和删除可能引起复杂的节点分裂与合并操作，这些操作涉及大量数据的移动，而跳表的插入和删除，在确定位置后，只需要调整相邻节点的指针即可，操作非常轻量，虽然跳表插入时也有一个“随机层数”的过程,但整体开销通常小于B树的节点重整。
• 内存占用：B树由于节点存储多个键值对，内部可能有一些空间浪费（节点未填满），跳表每个节点除了存储数据，还需要存储多个层次的指针，这些指针会带来额外的内存开销，在内存使用率上，B树可能会更紧凑一些，但Redis为了速度,通常愿意牺牲一部分内存空间。

总结一下

可以这样理解：

• B树是给磁盘准备的：它的核心使命是“减少磁盘磕头次数”，是外部存储（比如数据库文件）的霸主。
• 跳表是给内存准备的：它的核心优势是“实现简单，操作快速”,是内存数据结构的优秀选择。

Redis选择跳表而不是B树，是一个非常符合其自身定位的决策，它牺牲了微不足道的一点内存空间，换来了数据结构的极致简单、代码的易于维护、以及非常高效（尤其是写入和范围查询）的性能表现，这正体现了Redis“一切为了速度”的设计哲学。

（主要参考来源：《Redis设计与实现》，Redis官方文档关于有序集合和集群的说明，以及计算机数据结构通用知识。）