今日面试题 ：为什么 Redis Zset 用跳表实现而不是红黑树？B+树？

大家好，我是鸭鸭。

刷题就上面试鸭，帮助大家更高效通过面试（支持网页端、小程序）：https://mianshiya.com/ 。

祝大家都能拿到心仪的 Offer！

回答重点

为什么不用红黑树？

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

跳表是一种基于多层链表的数据结构，通过概率算法动态生成索引层级，逻辑理解上更为简单。相比之下，红黑树需要复杂的平衡操作（旋转）来维护其结构，代码实现复杂度较高。

2）范围查询更高效

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

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

3）更灵活

跳表的层数和节点结构是动态的，可以基于概率分布调整层数，能够灵活适应不同的数据量，平衡操作效率和内存消耗。

红黑树无法调整。

为什么不用 B+ 树？

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

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

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

扩展知识

其他

• 638. Redis 中跳表的实现原理是什么？
• 455. 为什么 JDK 1.8 对 HashMap 进行了红黑树的改动？
• 6336. 说说平衡树的基本实现，与红黑树的区别是什么？