1. 核心区别概述

跳表（Skip List） 和 B+ 树（B+ Tree） 都是用于实现高效查找的有序数据结构，支持 O(logN) 复杂度的增删改查及范围检索。

核心区别在于 适用场景 和 底层结构：

  • B+ 树 是 磁盘文件系统和关系型数据库（如 MySQL InnoDB）的首选，因为它对磁盘 I/O 友好（矮胖结构，减少 I/O 次数）。
  • 跳表 是 内存数据库（如 Redis ZSet）的首选，因为它实现简单、内存占用相对灵活，且在并发场景下更容易实现无锁或细粒度锁。

2. 深度对比分析

2.1 结构与原理

| 特性 | B+ 树 (B+ Tree) | 跳表 (Skip List) | | :— | :— | :— | | 逻辑结构 | 多路平衡查找树。 | 多层级的有序链表（概率平衡）。 | | 平衡机制 | 严格平衡。通过分裂（Split）和合并（Merge）节点来维持高度平衡。 | 概率平衡。通过随机函数决定新节点晋升的层数。 | | 叶子节点 | 所有数据存储在叶子节点，叶子节点间有双向指针连接，适合范围查询。 | 最底层链表包含所有元素，各层通过指针向下索引。 | | 高度 | 极低（通常 3-4 层），树形“矮胖”。 | 较高（通常 logN 层），结构“瘦高”。 |

2.2 读写性能与开销

  1. 查找性能：
    • 两者理论时间复杂度均为 O(logN)。
    • B+ 树由于高度更低，在数据量极大时，索引层级更少，但在内存中跳表的指针跳转可能比解析 B+ 树页结构略快（取决于实现）。
  2. 写入性能（核心差异）：
    • B+ 树：写入可能触发节点分裂，且分裂可能向上传播，导致整棵树结构的调整（Rebalance），代价较高，且并发实现复杂（需要复杂的锁机制）。
    • 跳表：写入只需维护局部指针，新节点的层数是随机生成的，不需要全局重平衡。这使得跳表在并发写入时，锁的粒度可以做得更小，甚至更容易实现无锁并发（CAS）。
  3. 空间利用率：
    • B+ 树：节点通常按页（Page）对齐，存在一定的填充率浪费（如 MySQL 默认页 16KB），但在磁盘存储上这是优势。
    • 跳表：每个节点包含的指针数量随机（平均 1.33 个指针），相比 B+ 树的固定开销，跳表在内存中的指针开销通常更低（Redis 考量点之一）。

2.3 为什么 Redis 选跳表，MySQL 选 B+ 树？

MySQL (InnoDB) 选择 B+ 树的原因：

  • 磁盘 I/O 是瓶颈：数据库数据量大，必须存磁盘。访问磁盘非常慢，必须最小化 I/O 次数。
  • 页对齐：B+ 树节点大小设计为磁盘页大小（如 16KB），一次 I/O 读取一个节点，利用局部性原理，效率极高。
  • 矮胖结构：B+ 树高度低（3 层可存 2000w+ 数据），意味着只需 3 次磁盘 I/O。而跳表高度较高，随机 I/O 次数多，对磁盘极不友好。

Redis (ZSet) 选择跳表的原因：

  • 纯内存操作：没有磁盘 I/O 瓶颈，B+ 树的“页对齐”优势不存在。
  • 实现简单：跳表代码不到 B+ 树的 1/5，易于维护和调试。
  • 并发优势：Redis 虽然主要是单线程，但部分场景或未来扩展中，跳表更容易进行并发优化（如更新节点时不涉及树的旋转分裂）。
  • 内存效率：跳表更加灵活，不需要像 B+ 树那样预留页空间。

3. 面试总结

在面试中回答此题，建议按以下逻辑复述：

  1. 本质定位：B+ 树是为磁盘优化的，跳表是为内存优化的。
  2. 操作代价：B+ 树写入需要复杂的重平衡（分裂/合并）；跳表基于概率平衡，写入操作局部化，简单且高效。
  3. 典型应用：
    • 需要减少磁盘 I/O、数据量巨大 -> B+ 树 (MySQL)。
    • 纯内存、追求实现简单、范围查询高效 -> 跳表 (Redis)。