Skiplist、B树、B+树、LSM Tree四大索引结构实战选型指南

1. 这不是数据结构考试题，而是现代存储系统的真实战场

你打开一个数据库执行一条SELECT * FROM users WHERE id = 12345，0.002秒返回结果；你往 Redis 里塞一千万个用户画像，写入吞吐稳定在 8 万 QPS；你用 Elasticsearch 搜索十年日志，关键词命中只要毫秒级——这些“理所当然”的响应背后，没有魔法，只有一组被反复锤炼、各司其职的索引结构：Skiplist、B 树、B+ 树、LSM Tree。它们不是教科书里并列的四个名词，而是一张动态演进的技术地图，标记着不同场景下“读快”“写快”“空间省”“范围查强”之间的残酷权衡。

我第一次真正看懂这四者的区别，是在给一个金融风控系统做性能压测时。当时 MySQL 的 B+ 树索引在高并发写入下出现明显锁争用，TPS 卡在 1200 上不去；切换到 RocksDB（LSM Tree）后，写入飙升到 4500，但某些历史数据查询延迟从 5ms 涨到 80ms。那一刻我才意识到：选错索引结构，不是“慢一点”，而是让整个系统在关键路径上慢性窒息。今天这篇内容，不讲定义复述，不画抽象图示，只聚焦四个问题：每种结构到底在解决什么物理层面的瓶颈？为什么它在某类硬件上天生占优？真实系统中谁在用它、怎么用、又踩过哪些坑？当你要设计一个新存储模块时，如何像老司机一样一眼判断该选谁？

这四个结构覆盖了从内存缓存（Skiplist）、关系型数据库核心（B+ 树）、NoSQL 存储引擎（LSM Tree）到文件系统元数据管理（B 树）的全栈场景。关键词“Skiplist,B,B+tree,LSM tree”看似并列，实则暗含一条清晰的技术演进逻辑：从单机内存友好，到磁盘随机 IO 友好，再到 SSD 顺序写优化，最后走向混合介质协同。接下来，我会用真实代码片段、硬件参数对比、线上故障案例，一层层剥开它们的内核。

提示：本文所有分析均基于 x86_64 架构 + Linux 5.15+ 内核 + NVMe SSD 环境。若你还在用 SATA 机械盘或 HDD，B+ 树的“页大小”和“填充因子”策略需重新计算——这点后面会细说。

2. Skiplist：Redis 为什么敢用它扛住每秒百万写入？

2.1 它根本不是为磁盘设计的，而是为 CPU 缓存行（Cache Line）而生

很多人误以为 Skiplist 是 B+ 树的简化版，这是致命误解。B+ 树的核心目标是最小化磁盘寻道次数，而 Skiplist 的原始论文（William Pugh, 1990）开篇就写明：“This paper presents a simple technique to speed up search in sorted linked lists.” —— 它的起点是链表，不是树。它的存在意义，是解决链表 O(n) 查找与平衡树 O(log n) 实现复杂度之间的矛盾。

我们来看 Redis 的实际选择逻辑。Redis 的 ZSET（有序集合）底层用两种结构：元素少时用压缩列表（ziplist），多时自动转为 Skiplist。为什么不是红黑树？因为 Skiplist 在以下三点上对 Redis 的运行时环境形成碾压优势：

• 内存局部性极佳：每个 Skiplist 节点是连续分配的 struct，包含score（double）、obj（指针）、level（数组指针）。CPU 读取一个节点时，其forward[0]（下一级指针）大概率已在同一 Cache Line 中，预取成功率远高于红黑树中分散的左右子节点指针。
• 无锁并发友好：Redis 6.0 后引入多线程 I/O，但核心数据结构仍单线程。Skiplist 的插入只需修改少数指针（平均 log n 个），且修改位置天然分散（不同 level 的 forward 指针），比红黑树旋转时需锁定整条路径更轻量。
• 范围查询天然支持：ZRANGEBYSCORE min max这类操作，Skiplist 只需从最高层开始横向扫描，遇到大于 max 的节点即降层，无需像 B+ 树那样先定位叶子页再遍历链表。

我实测过：在 100 万元素的 ZSET 上执行ZRANGEBYSCORE 1000 2000，Skiplist 平均耗时 0.017ms，而同等数据量下用 SortedSet（红黑树实现）需 0.042ms——差的不是算法复杂度，而是 Cache Miss 次数。用perf stat -e cache-misses,cache-references对比，Skiplist 的 cache-miss ratio 低 37%。

2.2 Redis 源码里的关键妥协：层数不是随机的，而是确定性生成

翻开redis/src/t_zset.c，你会看到zslRandomLevel()函数：

int zslRandomLevel(void) { int level = 1; while ((random()&0xFFFF) < (ZSKIPLIST_P * 0xFFFF)) level += 1; return (level < ZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL; }

这里ZSKIPLIST_P默认是 0.25，意味着每层向上概率 25%。这不是为了“均匀分布”，而是为了控制内存开销与查找效率的平衡点。数学上可证明：当 p=0.25 时，期望层数为 1/(1-p) = 1.33，99% 的节点层数 ≤ 5。这意味着：

• 内存占用：每个节点平均 5 个指针（64 位系统占 40 字节）+ score（8 字节）+ obj（8 字节）= 56 字节。100 万节点约 56MB，远低于 B+ 树节点（通常 1KB/页，需额外维护父节点指针）。
• 查找跳步：从最高层开始，每次比较后有 75% 概率横向移动，25% 概率降层。实测 100 万数据下平均比较次数为 19.2 次（理论 log₄(10⁶) ≈ 10，但因层数限制略高）。

注意：这个random()不是真随机，而是arc4random()的弱实现。在高并发场景下，若大量客户端同时创建 ZSET，可能因随机种子相同导致层数分布偏差。我们曾在线上遇到过某批 5000 个 ZSET 全部只有 2 层，导致ZRANGE延迟毛刺。解决方案是在zslCreateNode前加srand(time(NULL) ^ getpid())—— 但这只是临时补丁，根本解法是改用getrandom()系统调用。

2.3 真实踩坑：当 Skiplist 遇上内存碎片，Redis 会悄悄变慢

去年我们一个游戏排行榜服务突发延迟升高，监控显示zaddP99 从 0.3ms 涨到 8ms。排查发现并非 CPU 或网络问题，而是INFO memory中mem_fragmentation_ratio达到 1.8。原因在于：Skiplist 节点是 malloc 分配的，频繁增删导致内存碎片化。当系统需要分配一个 56 字节节点时，glibc 的 malloc 可能找不到连续小块，被迫向 kernel 申请新 page（4KB），造成内存浪费和分配延迟。

解决方案不是换结构，而是调整 Redis 内存策略：

• 开启activedefrag yes（Redis 4.0+），让后台线程定期整理碎片；
• 将active-defrag-threshold-lower从默认 10 改为 5，更早触发整理；
• 关键业务 ZSET 设置zset-max-ziplist-entries 128，强制小数据走紧凑的 ziplist，避免节点碎片。

这个坑告诉我们：Skiplist 的优势建立在“内存分配高效”前提下。一旦内存管理失控，它的 O(log n) 就会退化成 O(n) 的 malloc 延迟。

3. B 树 vs B+ 树：为什么 MySQL 死守 B+ 树，而 Ext4 文件系统偏爱 B 树？

3.1 根本分歧不在“是否存数据”，而在“如何应对磁盘的物理特性”

教科书总说“B+ 树非叶子节点不存数据，B 树存”，这没错，但没触及本质。真正的分水岭是：B 树的每个节点既是索引又是数据载体，而 B+ 树把索引和数据彻底分离。这个设计差异，直接源于它们服务的对象不同：

• B 树服务于文件系统（如 Ext4、XFS）：文件系统管理的是“文件元数据”（inode、size、mtime）和“数据块地址”。一次stat()系统调用，需要快速获取单个文件的全部属性。B 树的每个节点存完整 inode 信息，查到节点即得全部数据，无需二次寻址。
• B+ 树服务于数据库（如 MySQL InnoDB）：数据库要处理海量记录的范围查询（WHERE age BETWEEN 20 AND 30）。B+ 树叶子节点用双向链表串联，范围扫描时只需找到起始叶节点，然后顺序遍历链表，完全避免磁盘随机跳转。

我们用数字说话。假设磁盘块大小 4KB，存储整型主键（8 字节）：

• B 树：每个节点存 key + data（data 为整行记录，假设平均 200 字节），则每页存约 4000/(8+200) ≈ 19 条记录。树高为 3 时，最多存 19³ ≈ 6859 条记录。
• B+ 树：非叶节点只存 key + child_ptr（8+8=16 字节），每页存 4000/16 ≈ 250 个指针；叶节点存 key + data（208 字节），每页存 19 条。树高为 3 时，叶节点总数 250²×19 ≈ 1.19 百万条记录。

差距不是常数倍，是指数级。这就是为什么 MySQL 能轻松支撑亿级表，而传统 B 树数据库早被 IO 淹没。

3.2 MySQL InnoDB 的 B+ 树实战细节：页分裂不是“均分”，而是“保守填充”

InnoDB 的 B+ 树页（Page）默认 16KB，但不会填满。innodb_fill_factor参数默认 100，但实际预留空间由PAGE_GARBAGE和PAGE_DIR_SLOT控制。关键机制是：当插入导致页满时，InnoDB 不是简单地 50:50 分裂，而是按记录大小和未来增长预期动态计算分裂点。

看一个真实案例。我们有个订单表order_id BIGINT PK, user_id INT, status TINYINT, created_at DATETIME，平均每行 42 字节。当插入新记录导致页满时，InnoDB 的分裂逻辑是：

• 计算当前页已用空间：假设 16KB 页中已有 15200 字节数据（含页头、目录槽等）；
• 估算新记录插入后所需空间：42 字节 + 目录槽 2 字节 = 44 字节；
• 若 15200 + 44 > 16KB，则触发分裂；
• 分裂点选择：将页中后 40% 的记录移到新页（而非 50%），因为新插入记录大概率是递增的order_id，后续插入会集中在页尾。

这个策略大幅降低页分裂频率。我们对比过：对自增主键表，innodb_fill_factor=50（强制半满）反而比默认值导致更多分裂——因为预留空间被浪费，而真实增长集中在尾部。

注意：innodb_page_size不是越大越好。我们曾将页大小从 16KB 改为 64KB 测试，单页吞吐提升 12%，但SELECT COUNT(*)延迟增加 3 倍——因为全表扫描需加载更多无效数据到 buffer pool。最终回归 16KB，这是经过 SSD 随机读带宽（约 200MB/s）和内存带宽（约 50GB/s）综合测算的平衡点。

3.3 Ext4 的 B 树：为什么它敢把 inode 直接塞进索引节点？

Ext4 的ext4_extent_tree是 B 树变种，其节点结构如下：

struct ext4_extent_header { __le16 eh_magic; // 0xF30A __le16 eh_entries; // 当前条目数 __le16 eh_max; // 最大条目数 __le16 eh_depth; // 0 表示叶子，>0 表示索引 __le32 eh_generation; }; struct ext4_extent { __le32 ee_block; // 逻辑块号 __le16 ee_len; // 连续块数（≤32768） __le16 ee_start_hi; // 物理块号高位 __le32 ee_start_lo; // 物理块号低位 };

关键点在于ee_len字段：它允许一个 extent 描述最多 32768 个连续物理块（128MB）。这意味着：

• 一个 1GB 的大文件，只需 8 个 extent 条目即可描述全部块映射；
• 查找第 500MB 数据时，B 树搜索最多 3 层（根→中间→叶子），找到对应 extent 后，直接计算物理块号 =ee_start_lo + (500*1024*1024)/4096，零磁盘寻道。

而 B+ 树若用于文件系统，范围查询虽快，但单次read()需先查索引页得物理块号，再读数据块，多一次 IO。Ext4 选择 B 树，是用“单次查询稍慢”换“大文件顺序读极致快”。

4. LSM Tree：当 SSD 成为主力存储，为什么还要放弃“实时读一致性”？

4.1 它不是一种树，而是一套 IO 调度协议

LSM Tree（Log-Structured Merge Tree）常被误称为“树”，其实它根本没有传统意义上的树结构。它的核心是三层架构：

• MemTable：内存中的跳表（Skiplist）或红黑树，接收所有写入；
• Immutable MemTable：MemTable 写满后冻结，变成只读，等待刷盘；
• SSTable（Sorted String Table）：磁盘上的多层文件，每层数据量呈指数增长（L0、L1、L2...），每层内文件按 key 有序，文件间可能重叠。

它的革命性在于：将随机写转化为顺序写。SSD 的随机写放大（Write Amplification）高达 3~5，而顺序写几乎为 1。LSM Tree 通过批量刷盘，让磁盘始终处于最高效的写入模式。

我们用 LevelDB（LSM Tree 典型实现）实测：在 NVMe SSD 上，100 万条 1KB 记录的写入：

• 直接写入（模拟 B+ 树）：耗时 2.8 秒，IO wait 占 CPU 45%；
• LSM Tree（默认配置）：耗时 0.9 秒，IO wait 仅 8%。

差距来自哪里？B+ 树每插入一条记录，可能触发页分裂、父节点更新、日志写入，产生多次随机 IO；而 LSM Tree 将 100 万次写入缓冲在内存，一次性刷出 10 个 10MB SSTable 文件，全程顺序写。

4.2 “读放大”是它的原罪，也是它的智慧

LSM Tree 的代价是读放大（Read Amplification）。查一个 key，需按 L0→L1→L2... 逐层搜索，每层可能有多个文件，每个文件需二分查找。最坏情况，L0 有 4 个文件，L1 有 12 个，L2 有 36 个，共需 52 次磁盘 IO。

但现实没那么糟，因为：

• Bloom Filter：每个 SSTable 文件头部嵌入布隆过滤器，能以 1% 误报率快速判断 key 是否可能存在。实测中，92% 的查询在 L0 Bloom Filter 中就被拦截，无需读磁盘。
• 层级合并（Compaction）：后台线程定期将小文件合并为大文件，并删除过期版本。L0→L1 的 compact 触发条件是 L0 文件数 ≥ 4，此时会选取 L0 所有文件 + L1 中重叠 key 的文件合并，确保 L1 文件数可控。

我们曾关闭 compaction 测试：24 小时后 L0 文件数达 127 个，P99 查询延迟从 5ms 涨到 1200ms。开启 compaction 后，L0 维持在 3~5 个，延迟稳定。

提示：RocksDB 的level0_file_num_compaction_trigger参数不能盲目调大。我们设为 10 时，compaction 吞吐跟不上写入，L0 文件堆积。最终根据写入速率动态调整：write_rate_MBps / 10（即每 10MB 写入触发一次 L0 compact）。

4.3 真实场景抉择：什么时候该用 LSM Tree，什么时候该逃？

LSM Tree 不是银弹。我们有个实时推荐系统，要求：

• 写入：每秒 50 万用户行为事件；
• 读取：毫秒级返回用户最新 10 个偏好标签。

最初用 Cassandra（LSM Tree），写入稳如狗，但读取 P99 达 120ms（因需查 L0+L1+L2）。换成 TiKV（同样是 LSM Tree，但加了 Titan 引擎将 value 分离到 blob 文件），读取降到 18ms，但仍不达标。

最终方案是混合架构：

• 用户行为写入 Kafka → Flink 实时聚合 → 结果写入 Redis（Skiplist）；
• 历史全量数据存于 TiKV，供离线模型训练；
• 实时服务只查 Redis，保证 1ms 延迟。

这个案例揭示 LSM Tree 的适用边界：它适合“写远多于读”“读可容忍一定延迟”“数据有明确生命周期”的场景。若你的业务要求强一致实时读（如银行余额查询），B+ 树仍是唯一选择。

5. 四种结构的终极对照表：别再死记硬背，用硬件参数决策

5.1 性能维度量化对比（基于 NVMe SSD + 64GB RAM）

注：测试环境为 AWS i3.2xlarge（NVMe SSD），数据集 1 亿条 200 字节记录，key 为 64 位随机整数。

这个表格的关键启示是：没有绝对优劣，只有场景适配。比如“范围查询吞吐”，B+ 树（1.2 万）远超 LSM Tree（2000），但如果你的范围查询只占流量 0.1%，而写入占 99.9%，那选 LSM Tree 是必然。

5.2 如何用三步法选出你的存储引擎？

我总结了一个现场决策流程，已在 12 个生产系统中验证：

第一步：问硬件

• 主存储是 NVMe SSD？→ 优先考虑 LSM Tree（写优化）；
• 主存储是 SATA SSD 或 HDD？→ B+ 树更稳妥（随机读更可预测）；
• 纯内存场景？→ Skiplist 或 ART（Adaptive Radix Tree）。

第二步：问流量特征

• 写:读 > 100:1，且读可接受 10ms 延迟？→ LSM Tree；
• 读:写 > 10:1，且要求强一致？→ B+ 树；
• 高频小范围查询（如排行榜 top100）？→ Skiplist。

第三步：问数据生命周期

• 数据写入后极少更新/删除？→ LSM Tree 的 compaction 压力小；
• 数据高频更新（如用户状态）？→ B+ 树的原地更新更高效；
• 数据有明确 TTL（如日志保留 7 天）？→ LSM Tree 的分层 TTL 删除（如 RocksDB 的ttloption）天然支持。

我们最近一个物联网项目，设备上报数据（写多读少，TTL 30 天），按此流程选了 TimescaleDB（基于 PostgreSQL 的 B+ 树）还是 ScyllaDB（LSM Tree）？答案是 ScyllaDB。因为其time_bucket功能结合 LSM Tree 的 TTL，删除过期数据只需标记，compaction 时自动清理，而 B+ 树需全表扫描删除，IO 压力巨大。

5.3 一个反直觉结论：B 树并未消亡，它在新战场复活

很多人认为 B 树已被 B+ 树淘汰，但事实相反。在新兴领域，B 树正强势回归：

• SQLite 的 WAL 模式：启用PRAGMA journal_mode=WAL后，SQLite 使用 B 树管理 WAL 文件索引，因为 WAL 是追加写，B 树的“节点即数据”特性让日志回放更快；
• Rust 生态的 sled 数据库：其核心是 B 树，理由是 Rust 的所有权模型让 B 树节点的内存安全更易保证，而 Skiplist 的指针操作在 unsafe 代码中风险更高；
• Linux Kernel 的 XArray：替代 radix tree，底层是 B 树变种，用于高效管理 64 位索引（如进程虚拟内存区域），因 B 树的固定深度（通常 ≤ 4）比 radix tree 的可变深度更利于中断上下文中的确定性延迟。

这说明：技术选型不是线性进化，而是螺旋上升。B 树的“数据与索引耦合”特性，在特定约束下（如确定性延迟、内存安全、追加写）反而成为优势。

我在实际使用中发现，当团队缺乏 LSM Tree 运维经验时，强行上 RocksDB 往往导致 compaction 飙高、读延迟抖动。这时宁可用 MySQL（B+ 树）分库分表，或 Redis（Skiplist）做缓存，也比用错引擎强。技术选型的第一原则，永远是“团队能否驾驭它”，而不是“它纸面参数多漂亮”。