Redis Zset 底层设计：为什么选择跳表而非 B+ 树？

Corey2026/6/9大约 4 分钟面试题面试题

来源：Redis Zset 底层设计：为什么选择跳表而非 B+ 树？

在数据库领域，B+ 树几乎是索引的代名词。MySQL、Oracle 等主流关系型数据库都坚定地选择它作为底层数据结构。然而，作为内存数据库霸主的 Redis，在其核心数据类型 Zset（有序集合）中，却出人意料地选择了跳表（SkipList）。

这是为什么？是 Redis 作者 Antirez 另辟蹊径，还是由于内存场景下的特殊权衡？

如上图所示，跳表并非某种复杂的树形结构，而是一种多层链表。

文字不再赘述图中显而易见的“多层索引”形态，我们需要理解其背后的概率哲学：

O(log n) 的由来：不同于平衡树通过严格的旋转来维持平衡，跳表通过“抛硬币”的方式决定新节点的高度。这种随机性在数据量足够大时，数学上保证了查找效率趋近于 O(log n)。
无需重平衡：当你向图中插入一个新节点时，只需修改相邻节点的指针，而不需要像红黑树那样进行全局的颜色翻转或旋转。这种“局部性”是它轻量化的根源。

B+ 树之所以成为数据库的标准答案，核心在于磁盘 I/O。

页对齐（Page Aligned）：请注意图中 B+ 树的节点被设计得非常宽（矮胖）。这是为了让一个节点的大小（如 16KB）刚好填满一个磁盘页。
一次 I/O，海量索引：在磁盘场景下，读取一次磁盘的代价极其昂贵。B+ 树的设计目标是“让每一次 I/O 读取都尽可能包含更多的索引信息”，从而降低树的高度，减少磁盘寻道次数。

这是 Redis 放弃 B+ 树的最根本原因：场景变了，瓶颈也变了。

B+ 树优势失效：在纯内存场景下（Redis），所有数据都在 RAM 中，不存在磁盘 I/O 的高昂开销。此时，B+ 树为了“减少磁盘读取”而设计的复杂页管理机制，反而成了累赘。
CPU 缓存友好性：跳表的结构更简单，节点更紧凑。在内存中遍历时，跳表能更好地利用 CPU Cache，而 B+ 树复杂的节点结构可能会导致更多的 Cache Miss。
指针跳转 vs 复杂计算：在内存中，指针跳转（跳表）的开销远小于解析 B+ 树复杂节点结构的 CPU 开销。

除了性能，工程实现的复杂度往往被理论分析所忽视，但它对开源项目至关重要。

200行 vs 1000行：跳表的插入和删除操作仅涉及局部指针更新，逻辑极其简单。而 B+ 树在节点分裂（Split）和合并（Merge）时，可能引发连锁反应，甚至波及根节点。
并发控制：
跳表：由于更新只影响局部，实现无锁（Lock-free）或细粒度锁非常容易。
B+ 树：一旦触发节点分裂，需要锁定整条路径甚至全树，这在多核高并发时代是致命的性能杀手。

Redis 选择跳表，并不是因为跳表在算法理论上比 B+ 树更强，而是因为它在内存场景下做到了收益与成本的最佳平衡：