前阵子参加一个技术选型评审，讨论新业务的存储方案。

有人提议：「用 TiKV 吧，底层 RocksDB，写入吞吐是 MySQL 的十倍。」

另一个人反问：「那为什么不直接上 Redis？哈希 O(1)，比什么树都快。」

第三个说：「跳表不是更简单吗，Redis 的 ZSet 就是跳表，几十万 QPS。」

会开到一半我发现，大家在比「谁快」，但没人说清「快在哪个动作上」。

哈希快在等值查询，跳表快在内存里的有序遍历，LSM 快在写入，B+ 树快在「用最少的磁盘 IO 完成一次范围查找」。这四句话说的根本不是同一件事。

所以这篇文章不打算给结论，而是想把这件事摊开：五种结构，各自在优化什么，代价是什么，InnoDB 为什么只能选它选的那个。

一、先算清「贵」这个字

所有存储结构的争论，本质都是在跟一个物理事实做斗争：内存和磁盘的速度差了三到五个数量级。

这张表最容易被低估的是最后一行。10 毫秒听起来很短，但它等于 CPU 做 3000 万次比较。也就是说，如果你的索引结构需要 20 次随机寻道，那算法再聪明也救不回来——这个查询注定要花 200 毫秒。

所以衡量索引结构的标准，其实只有一条：

从根找到目标，需要几次磁盘 IO。

这句话有两个推论，后面所有的分析都建立在它们上面：

1. IO 次数 ≈ 树的层数。层数少一层，就少一次随机读。
2. 层数由扇出（fanout）决定。每个节点能挂多少个子节点，决定了树有多矮。

有了这两条，五种结构就可以在同一把尺子上量了。

二、二叉搜索树：树高就是 IO 次数

先从最熟悉的说起。

二叉搜索树（包括它的平衡版本 AVL、红黑树）每个节点最多两个分支。100 万行数据，树高约log2(1000000) ≈ 20。

如果每个节点都存在磁盘上、每次访问节点都是一次随机读，那查一行要20 次 IO。

按 SSD 算，20 × 100 微秒 = 2 毫秒。按机械盘算，20 × 10 毫秒 = 200 毫秒。

这就是为什么红黑树在数据库里当不了主索引，却在 Java 的TreeMap、Linux 的 CFS 调度器、Nginx 的定时器里用得风生水起——那些场景的数据都在内存里，一次「节点访问」是 100 纳秒，不是 10 毫秒。

红黑树还有第二个问题：为了保持平衡，插入时要旋转。旋转在内存里是改几个指针，在磁盘上就是「重写一段页」——写放大。数据库不敢这么玩。

三、B 树：把「一个节点」变成「一页」

B 树的想法很直接：既然一次 IO 只能读一个块，那就让一个节点刚好等于一个块（16KB），并且让这个节点装尽可能多的分支。

一个 16KB 的节点，如果每条索引项是「8 字节 key + 6 字节指针」，理论上能装 1170 个分支。但 B 树的节点里同时存 key 和数据——这是它和 B+ 树最根本的区别。

假设每行 1KB，一个 16KB 的节点里只能放 16 条记录。所以 B 树的扇出是 16，树高log16(1000000) ≈ 5。

从 20 层降到 5 层，这是数量级的进步。B 树的价值不在于「树」，而在于「把节点大小对齐到磁盘页」这个洞察。

但 B 树还是不够好，问题出在「节点里同时存数据」这件事上。因为：

• 数据占地方，扇出就小（16 而不是 1170）
• 数据分布在各层，意味着「查任意一行，可能在第 1 层就返回，也可能要走到第 5 层」，性能不稳定
• 范围查询要在各层之间上下爬，没法顺序扫

四、B+ 树：把数据全部赶出内部节点

B+ 树做了一个看起来很小的改动：内部节点不存数据，只存 key 和页指针；所有数据都放在叶子节点。

这个小改动带来了三个连锁反应。

第一，扇出暴涨。

内部节点现在只装「key + 指针」= 14 字节，一个 16KB 页能装 1170 个。扇出从 16 变成 1170，树高从 5 层降到 3 层。同样的数据量，少读两次盘。

第二，查询路径变稳定。

所有数据都在叶子层，查任何一行都要走完整的 3 层。听起来变慢了，实际上变快了——因为不再有「运气好 1 次 IO，运气差 5 次 IO」的抖动，P99 延迟可控。

第三，叶子之间有链表。

这是 B+ 树最被低估的设计。叶子节点之间用双向链表串起来，于是WHERE id BETWEEN 100 AND 200这样的范围查询，只要找到起点，顺着链表往后扫就行，不用回到根节点重新定位。

B 树做不到这一点，它每次都要从根开始重新走一遍。

所以 B+ 树真正赢的地方，不是「更快」，而是**「用同样的 IO 预算，同时满足点查、范围、排序三种需求」**。

顺带一提：叶子挂整行，才是聚簇索引

B+ 树的叶子节点挂什么，决定了这张表长什么样。

InnoDB 的做法是：主键索引的叶子节点上挂整行数据。这种结构叫聚簇索引（clustered index）。

它带来一个很实在的好处：WHERE id = 123这样的查询，走三层 B+ 树找到叶子，整行数据就在眼前，不需要再回表。一次查询，三次页访问，其中前两次大概率命中内存，真实读盘只有一次。

如果换成哈希，情况会变成：哈希桶里存的是「行地址」，找到地址还要再去读一次行——哈希省下的那两次树遍历，被多出来的一次行读取吃掉了。

这也是为什么「哈希 O(1) 比 B+ 树快」这句话在数据库语境下是错的：B+ 树的 3 次访问里有 2 次几乎必然命中 Buffer Pool（根页 1 页、第二层 18MB），实际磁盘成本接近 1 次；而哈希要做的地址跳转，每一次都是真实的随机 IO。

顺带说，二级索引的叶子挂的是主键值，不是行地址——这就有了「回表」（根据主键再查一次聚簇索引）。这是另一个话题，但它同样说明：B+ 树的价值在于「叶子上可以挂东西」，而哈希的桶里只能挂指针。

五、哈希：最快的等值，最废的范围

哈希表在等值查询上近乎完美：hash(key)算出桶位置，一次访问就够。

那为什么 MySQL 不用哈希做主索引？

因为哈希丢掉了顺序。

• WHERE age > 20：不知道哪些桶对应 age > 20，只能全表扫
• ORDER BY created_at：哈希表里没有顺序，必须把数据全取出来再排
• WHERE name LIKE 'abc%'：前缀匹配失效
• 联合索引的最左前缀：完全用不上

在 OLTP 系统里，这四类查询占了绝大多数。一个只支持WHERE id = ?的索引，业务根本没法用。

顺带澄清一个常见混淆：InnoDB 里有哈希索引，但不是主索引。

它叫自适应哈希索引（Adaptive Hash Index, AHI），是在 Buffer Pool 之上自动建的一层内存哈希，把频繁访问的索引页的 key 映射到页位置。它解决的是「同一个 key 被反复查」的场景，是 B+ 树之上的加速层，不是替代品。

-- 看看 AHI 有没有在工作 SHOW ENGINE INNODB STATUS\G -- 输出里找这一段： -- Hash table size 34679, node heap has 12 buffer(s) -- 0.00 hash searches/s, 0.00 non-hash searches/s

hash searches/s远小于non-hash searches/s，说明 AHI 基本没起作用。

六、跳表：内存里的有序表

跳表（Skip List）是平衡树的「民主版」：不搞旋转，靠多层索引实现期望 O(log n) 的查找。

它的优点是实现简单、并发友好——插入时只需要改局部指针，不需要像红黑树那样旋转整棵树，所以无锁实现很容易。

Redis 的 ZSet 用它，LevelDB / RocksDB 的 memtable 也用它。

那为什么数据库的主索引不用它？

三个原因：

第一，它是为内存设计的。跳表的一个节点就是一个对象，散落在堆内存里。指针跳来跳去，每一跳都是一次随机内存访问。在内存里 100 纳秒，没问题；要落盘，你没法把「一跳」变成一个 16KB 的页。

第二，指针开销大。一个 4 层的跳表节点，平均要带 2 个左右的指针。同样存 100 万个 key，跳表占的内存是数组的两三倍。

第三，没有页的概念。B+ 树的所有优化都建立在「一次 IO = 一页」这个前提上，跳表根本没有这个粒度，也就无法对齐磁盘。

所以跳表的定位很清楚：它是内存里的有序容器，不是磁盘索引。

七、LSM：用顺序写换随机写

LSM（Log-Structured Merge Tree）走的是完全相反的路。

B+ 树的写入是「原地更新」：找到那一页，改它，标记脏页。如果页不在内存里，要先读进来再改——这就是随机写。

LSM 不这么干。所有写入先追加到 WAL，再写进内存的 memtable（通常是个跳表）。memtable 写满了就冻结，顺序刷成一个不可变的 SSTable 文件。后台再把多个 SSTable 合并（compaction）。

结果就是：写入永远是顺序追加，吞吐极高。

代价有三个，而且都不小：

读放大。查一个 key，要先查 memtable，再查 L0 的若干个小文件（key 范围重叠），再查 L1、L2……层数越多，读越慢。所以 LSM 通常配布隆过滤器（Bloom Filter）来快速排除不存在的 key。

写放大。compaction 会把同一份数据反复重写。业界常见的写放大是 10 到 30 倍——你写 1MB，实际写到磁盘 10~30MB。

空间放大。多层文件同时存在，旧版本数据还没清理完，磁盘占用会比实际数据大。

所以 LSM 适合的是写密集、读相对少、能接受读放大的场景：时序数据、日志、消息队列、KV 存储。

TiKV、HBase、Cassandra、RocksDB 都是这条路。

八、五种结构放在一张表里

现在可以横向比了。

看这张表要注意一点：「树高 3 层」和「1 次访问」不是同一个维度的比较。

哈希的 1 次是「1 次内存访问」，B+ 树的 3 次是「3 次磁盘访问」。如果数据全在内存里，哈希当然赢；如果数据有 500G 而内存只有 16G，那哈希就要做磁盘哈希——那时候它的表现会非常糟糕，因为哈希的随机性会导致缓存命中率极低。

这就是为什么「谁更快」这个问题没有意义，必须先说清数据规模和内存比例。

九、InnoDB 的三条硬约束

回到正题。InnoDB 选 B+ 树，不是因为它「先进」，而是因为它要同时满足三个约束。

约束一：要支持范围查询和排序。

这一条直接排除哈希。业务里WHERE create_time > ?、ORDER BY id DESC LIMIT 20是常态，没有范围能力就没法用。

约束二：数据量远大于内存，必须落盘。

这一条排除跳表和所有纯内存结构。InnoDB 的表可能有几百 G，Buffer Pool 只能装下热数据，剩下的在磁盘上。索引结构必须能对齐磁盘页。

约束三：要支持事务和原地更新。

这一条让 LSM 变得尴尬。InnoDB 的事务模型（MVCC、行锁、两阶段提交）建立在「页可以被原地修改」的基础上。undo log 挂在页上，行锁挂在索引记录上。LSM 的追加写模型要支持这些，得再叠一层（TiKV 就是这么干的，用 Percolator 事务模型 + MVCC 版本链），复杂度高一个量级。

三条约束的交集，只剩 B+ 树。

顺带回答一个常见的追问：为什么不是 B 树？

因为 B 树的节点里混装数据，扇出只有 16 左右，树高 5 层，比 B+ 树多两次 IO。而且在 B 树上做范围查询，要在各层之间反复上下，效率远不如叶子链表。

还有一个更细的差别：B 树因为「数据可能在任何一层」，删除数据时可能导致树的结构大幅调整；B+ 树所有数据都在叶子，删除只影响叶子层，内部节点只在分裂/合并时变动，稳定性更好。

写放大：两种结构的真实账本

选型时经常被提起的一个词是「写放大」，但很多人只知道 LSM 的写放大，不知道 B+ 树也有。

B+ 树的写放大来自三个地方：

1. 页分裂：往一个满页插数据，要申请新页、搬走一半记录、改父页指针。一次插入变成「写两页 + 改一页」。
2. 刷脏页：一个 16KB 的页被改了一个字节，整页都要刷回磁盘。改 8 字节要写 16KB，放大 2000 倍。
3. doublewrite：为了防止页写坏（部分写），InnoDB 会先把页写到 doublewrite buffer，再写到数据文件。等于写两次。

实际测下来，B+ 树的写放大通常在10 到 30 倍之间。

LSM 的写放大来自 compaction：每合并一层，数据重写一次。三层结构、每层 10 倍容量，写放大通常是 10 到 30 倍，极端情况能到 50 倍。

所以在这个维度上，两者其实是平手，不是「LSM 更省」。

真正的差别在写的方式：B+ 树是随机写（页散落在磁盘各处），LSM 是顺序写（追加到文件末尾）。机械盘上，顺序写比随机写快 100 倍；SSD 上，这个差距缩小到 3~5 倍，但依然存在。

这就是 LSM 的真正优势——它赢在随机写变顺序写，不是赢在写放大小。

反过来说，如果你的场景是「读多写少」，B+ 树的随机写根本不是瓶颈，LSM 的优势就用不上，反而要承担读放大的代价。这也是为什么大部分 OLTP 系统至今还留在 B+ 树上。

十、B+ 树什么时候不是最优

公平地说，B+ 树也有明显的短板，有三种场景它确实不是最佳选择。

写入极其密集、读很少。

比如埋点日志、时序数据。这类场景每秒写几十万条，B+ 树的随机写会成为瓶颈。这时候 LSM 明显更合适——这也是为什么 InfluxDB、ClickHouse、TDengine 都不约而同选了 LSM 或类 LSM 的结构。

纯内存 KV。

Redis 选跳表不选 B+ 树，是对的。内存里没有「页」的概念，跳表的并发友好性反而更重要。

只做点查的缓存层。

比如会话存储、配置中心。哈希 O(1) 完胜。MySQL 的 Memory 引擎就支持哈希索引，专门干这个。

但要注意：这三种场景的共同点是「放弃了通用性」。它们为某一个维度做到了极致，代价是牺牲其他维度。InnoDB 面对的是通用 OLTP 业务，它必须每一项都及格，而不是某一项满分。

这就是「通用数据库」和「专用存储」的根本区别。

SSD 时代，B+ 树还成立吗

有一个很尖锐的质疑，值得认真回答：

SSD 的随机读只要 100 微秒，比机械盘的 10 毫秒快了 100 倍。那「少读几次盘」还有那么重要吗？二叉树 20 次 IO 也就 2 毫秒，能接受吧？

这个说法在单条查询的尺度上是对的，但在系统吞吐的尺度上是错的。

原因有三个。

第一，IO 次数决定了并发上限。

一块 SSD 的 IOPS 是有限的，消费级 NVMe 大约 50 万 IOPS，企业级能到 100 万。如果每个查询要 20 次 IO，那理论上限就是 2.5 万 QPS；如果只要 1 次，上限就是 50 万 QPS。

IO 次数不是「快慢」问题，是「乘以 QPS 之后会不会打爆设备」的问题。

第二，每次 IO 都有固定的栈开销。

一次 SSD 读不只是「传输 16KB」，还要经过文件系统、块层、设备队列、中断。这些开销加起来，一次随机读的实际延迟往往是 100~200 微秒，而不是芯片标称的 20 微秒。20 次 IO 的真实成本可能接近 4 毫秒。

第三，页的大小没有变。

SSD 的物理页是 4KB 或 16KB，一次读还是一个页。B+ 树的核心优势「一页装 1170 个路标」，在 SSD 上完全成立，甚至更重要——因为 SSD 的顺序读带宽很高，一次读 16KB 比读 4 次 4KB 划算得多。

所以结论是：SSD 让「多读几次盘」的惩罚变小了，但没有消除它。在 QPS 上万的系统里，3 层和 20 层的差距依然是数量级的。

真正因为 SSD 而受益的其实是 LSM——随机写变顺序写的优势，在 SSD 上依然存在，而且更适合 SSD 的写入特性（SSD 的随机写会引发写放大和寿命损耗）。这也是为什么新一代分布式数据库（TiDB、CockroachDB）大多选了 LSM 作为存储层。

换句话说：SSD 没有让 B+ 树过时，但确实让 LSM 变得更有竞争力了。

十一、一张决策图

如果要在项目里选，按这个顺序问自己。

三个问题：

1. 只做点查，永远不要范围和排序？是 → 哈希（Memory 引擎、Redis Hash）
2. 写吞吐是第一位，能容忍读放大？是 → LSM（RocksDB、HBase、TiKV）
3. 数据全在内存，要有序且并发友好？是 → 跳表（Redis ZSet）

三个都否 →B+ 树。

绝大多数业务会走到第四个分支。这不是因为它最好，而是因为它的短板最少。

十二、验证一下你的表

讲完理论，说说怎么在自己的库上验证。

看索引的层数估算：

SELECT table_name, table_rows, ROUND(data_length / 1024 / 1024, 1) AS data_mb, ROUND(index_length / 1024 / 1024, 1) AS index_mb FROM information_schema.tables WHERE table_schema = 'your_db' ORDER BY data_length DESC LIMIT 10;

看一次查询实际读了多少页：

FLUSH STATUS; SELECT * FROM orders WHERE id = 1234567; SHOW SESSION STATUS LIKE 'Innodb_buffer_pool_read_requests'; -- 走索引时这个数通常是 3~5：根页 + 中间层 + 叶子页

如果这个数是几十甚至上百，说明查询没走对索引——可能在做全表扫描，也可能在回表。

用 EXPLAIN 看有没有走索引：

EXPLAIN SELECT id, order_no FROM orders WHERE shop_id = 10241 AND status = 1; -- 关注 type：const/eq_ref/ref/range 是好的，ALL 是全表扫 -- 关注 key：实际用了哪个索引 -- 关注 rows：估算扫描行数

下面这段脚本可以粗略估出「你的表在第几层」，思路是用数据文件总大小除以页大小，得到叶子页数，再按扇出反推层数：

import math def tree_height(data_bytes, row_bytes=1024, key_bytes=8, ptr_bytes=6, page=16384, overhead=128): usable = page - overhead fanout = usable // (key_bytes + ptr_bytes) # 非叶扇出 rows_per_leaf = max(1, usable // row_bytes) # 每叶行数 leaves = math.ceil(data_bytes / page) # 实际叶子页数 h = 1 nodes = leaves while nodes > 1: nodes = math.ceil(nodes / fanout) h += 1 return fanout, rows_per_leaf, leaves, h for mb in (1024, 8 * 1024, 64 * 1024, 512 * 1024): fanout, rpl, leaves, h = tree_height(mb * 1024 * 1024) print(f"{mb:>6} MB 表 → 叶页 {leaves:>7,} → 扇出 {fanout} → 树高 {h} 层")

输出大致是这样：

1024 MB 表 → 叶页 65,536 → 扇出 1161 → 树高 3 层 8192 MB 表 → 叶页 524,288 → 扇出 1161 → 树高 3 层 65536 MB 表 → 叶页 4,194,304 → 扇出 1161 → 树高 4 层 524288 MB 表 → 叶页 33,554,432 → 扇出 1161 → 树高 4 层

注意 1GB 和 8GB 都是 3 层。因为三层能装 2000 万行，1GB 的表远没到上限。这就是为什么大部分业务表查一行只要 1~2 次真实 IO——根页和第二层几乎总在内存里。

十三、把这件事记住

最后压缩成几句话：

• 数据结构的选型不是「谁更先进」，而是「谁更贴合你的访问模式和硬件代价」
• B+ 树的三个关键设计：节点对齐磁盘页、内部节点只放路标、叶子之间有链表
• 哈希和跳表输在「不支持范围」，LSM 输在「读放大 + 事务复杂」，B 树输在「扇出太小」
• 100 万行的表，B+ 树 3 层，二叉搜索树 20 层，哈希 1 次但只支持等值
• 选型先问访问模式，再问写读比例，最后才问「谁更先进」

写到这里，下一个问题自然就出来了：三层到底能装多少行？

很多人能背出「2000 万」这个数字，但说不出它是怎么算出来的，也说不出「如果你的行是 4KB，这个数字会变成多少」。

下一篇把这件事一行一行算给你看：从 16KB 的页切开，算出一条目录项 14 字节，算出扇出 1170，再乘三层。中间会有一步 1170 和 1161 的差额，那个差额里藏着「为什么有人说两千万、有人说两千万」的秘密。