为什么 Redis Zset 用跳表实现而不是红黑树？B+树？

回答重点

为什么不用红黑树？

1）相比红黑树而言实现简单

跳表基于多层链表实现，通过概率算法动态生成索引层级，没有左旋右旋等操作，逻辑理解上更为简单。而红黑树需要复杂的平衡操作（旋转）来维护结构，代码实现复杂度较高，理解门槛更高。

2）范围查询更高效

范围查询跳表可以通过 O(logn) 的时间复杂度定位起点，然后在原始的链表中往后遍历即可。

红黑树从结构上不支持范围查询。

3）结构更灵活

跳表的层数和节点结构是动态的，可以基于概率分布调整层数，灵活的适应不同的数据量（数据量大层级可以多一些，小的话层级少一些）。

红黑树则无法调整。

为什么不用 B+ 树？

B+ 树节点更新比较复杂，涉及页合并和分裂，会导致额外的计算。

B+ 树节点理论上占用内存也比跳表节点大。因为控制层级的情况下，大部分跳表节点仅需维护自身的值和一个指针（可能还有一个回退指针，redis的实现有回退指针），而 B+ 树是多叉树，一个节点需要多指针，且节点内部还有若干指针。每个元素在叶子节点有一份完整数据内容，在非叶子节点还需要存储键的数据，所以内存开销相比跳表大。

B+树其实更适合磁盘存储，特别是大规模存储数据。因为 B+树完整数据都存储在叶子节点中，而非叶子节点只起到索引作用，这样内存中就能存放更多的索引，便于海量数据的快速检索。

扩展知识

redis 作者对 zset 用跳表实现的原因解释

Is there any particular reason you chose skip list instead of btrees except for simplicity? Skip lists consume more memory in pointers and are generally slower than btrees because of poor memory locality so traversing them means lots of cache misses.

之前有人询问作者 antirez，不用 b 树而用跳表来实现 zset 除了简单之外还有什么特别原因吗？跳表在指针上比 b 树消耗的更多的内存，并且通常因为内存局部性差，可能有大量缓存未命中索引而访问起来比 b 树慢。

作者 antirez 回复如下：

There are a few reasons:

They are not very memory intensive. It’s up to you basically. Changing parameters about the probability of a node to have a given number of levels will make then less memory intensive than btrees.

A sorted set is often target of many ZRANGE or ZREVRANGE operations, that is, traversing the skip list as a linked list. With this operation the cache locality of skip lists is at least as good as with other kind of balanced trees.

They are simpler to implement, debug, and so forth. For instance thanks to the skip list simplicity I received a patch (already in Redis master) with augmented skip lists implementing ZRANK in O(log(N)). It required little changes to the code.

以下是翻译内容：

有以下几个原因：

1）它们对内存的占用不是很大。这基本上取决于你的设置。通过调整节点拥有特定层数的概率参数，可以使跳表比 B 树更少占用内存。

2）排序集合经常会被用于许多 ZRANGE 或 ZREVRANGE 操作，也就是以链表的方式遍历跳表。在这种操作中，跳表的缓存局部性至少与其他类型的平衡树一样好。

3）跳表实现起来更简单，调试等操作也更方便。例如，由于跳表的简单性，我收到了一个补丁（已经在 Redis 的主分支中实现），它使用增强的跳表在 (O(log(N))) 的时间复杂度内实现了 ZRANK。这只需要对代码进行很少的修改。