InnoDB 为什么选 B+ 树：B 树、哈希、跳表、LSM 五种结构横向对比

前阵子参加一个技术选型评审讨论新业务的存储方案。有人提议「用 TiKV 吧底层 RocksDB写入吞吐是 MySQL 的十倍。」另一个人反问「那为什么不直接上 Redis哈希 O(1)比什么树都快。」第三个说「跳表不是更简单吗Redis 的 ZSet 就是跳表几十万 QPS。」会开到一半我发现大家在比「谁快」但没人说清「快在哪个动作上」。哈希快在等值查询跳表快在内存里的有序遍历LSM 快在写入B 树快在「用最少的磁盘 IO 完成一次范围查找」。这四句话说的根本不是同一件事。所以这篇文章不打算给结论而是想把这件事摊开五种结构各自在优化什么代价是什么InnoDB 为什么只能选它选的那个。一、先算清「贵」这个字所有存储结构的争论本质都是在跟一个物理事实做斗争内存和磁盘的速度差了三到五个数量级。动作耗时相当于 CPU 空转多少次读 L1 缓存0.3 纳秒1 次读内存随机100 纳秒300 次SSD 随机读 4KB100 微秒30 万次机械盘随机寻道10 毫秒3000 万次这张表最容易被低估的是最后一行。10 毫秒听起来很短但它等于 CPU 做 3000 万次比较。也就是说如果你的索引结构需要 20 次随机寻道那算法再聪明也救不回来——这个查询注定要花 200 毫秒。所以衡量索引结构的标准其实只有一条从根找到目标需要几次磁盘 IO。这句话有两个推论后面所有的分析都建立在它们上面IO 次数 ≈ 树的层数。层数少一层就少一次随机读。层数由扇出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/shash 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用顺序写换随机写LSMLog-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 都是这条路。八、五种结构放在一张表里现在可以横向比了。结构等值范围排序树高100万行写放大典型系统二叉搜索树✓✓✓20 层高旋转内存结构TreeMapB 树✓✓△5 层中MongoDB 索引B 树✓✓✓3 层中InnoDB、MyISAM哈希✓✗✗1 次小Memory 引擎、Redis Hash跳表✓✓✓O(log n)大Redis ZSet、MemTableLSM△△✗多层小RocksDB、HBase、TiKV看这张表要注意一点「树高 3 层」和「1 次访问」不是同一个维度的比较。哈希的 1 次是「1 次内存访问」B 树的 3 次是「3 次磁盘访问」。如果数据全在内存里哈希当然赢如果数据有 500G 而内存只有 16G那哈希就要做磁盘哈希——那时候它的表现会非常糟糕因为哈希的随机性会导致缓存命中率极低。这就是为什么「谁更快」这个问题没有意义必须先说清数据规模和内存比例。九、InnoDB 的三条硬约束回到正题。InnoDB 选 B 树不是因为它「先进」而是因为它要同时满足三个约束。约束一要支持范围查询和排序。这一条直接排除哈希。业务里WHERE create_time ?、ORDER BY id DESC LIMIT 20是常态没有范围能力就没法用。约束二数据量远大于内存必须落盘。这一条排除跳表和所有纯内存结构。InnoDB 的表可能有几百 GBuffer Pool 只能装下热数据剩下的在磁盘上。索引结构必须能对齐磁盘页。约束三要支持事务和原地更新。这一条让 LSM 变得尴尬。InnoDB 的事务模型MVCC、行锁、两阶段提交建立在「页可以被原地修改」的基础上。undo log 挂在页上行锁挂在索引记录上。LSM 的追加写模型要支持这些得再叠一层TiKV 就是这么干的用 Percolator 事务模型 MVCC 版本链复杂度高一个量级。三条约束的交集只剩 B 树。顺带回答一个常见的追问为什么不是 B 树因为 B 树的节点里混装数据扇出只有 16 左右树高 5 层比 B 树多两次 IO。而且在 B 树上做范围查询要在各层之间反复上下效率远不如叶子链表。还有一个更细的差别B 树因为「数据可能在任何一层」删除数据时可能导致树的结构大幅调整B 树所有数据都在叶子删除只影响叶子层内部节点只在分裂/合并时变动稳定性更好。写放大两种结构的真实账本选型时经常被提起的一个词是「写放大」但很多人只知道 LSM 的写放大不知道 B 树也有。B 树的写放大来自三个地方页分裂往一个满页插数据要申请新页、搬走一半记录、改父页指针。一次插入变成「写两页 改一页」。刷脏页一个 16KB 的页被改了一个字节整页都要刷回磁盘。改 8 字节要写 16KB放大 2000 倍。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 变得更有竞争力了。十一、一张决策图如果要在项目里选按这个顺序问自己。三个问题只做点查永远不要范围和排序是 → 哈希Memory 引擎、Redis Hash写吞吐是第一位能容忍读放大是 → LSMRocksDB、HBase、TiKV数据全在内存要有序且并发友好是 → 跳表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; -- 关注 typeconst/eq_ref/ref/range 是好的ALL 是全表扫 -- 关注 key实际用了哪个索引 -- 关注 rows估算扫描行数下面这段脚本可以粗略估出「你的表在第几层」思路是用数据文件总大小除以页大小得到叶子页数再按扇出反推层数import math def tree_height(data_bytes, row_bytes1024, key_bytes8, ptr_bytes6, page16384, overhead128): 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 的差额那个差额里藏着「为什么有人说两千万、有人说两千万」的秘密。