MySQL B树百万行查询只要几毫秒的秘密目录聚簇索引数据和索引长在一起没有聚簇索引会怎样为什么是 B 树淘汰赛其他数据结构为什么不行B 树长什么样B 树的两个关键特征为什么是 B 树三个维度收束回答开头的问题小结SELECT * FROM user WHERE id 1执行计划显示走了主键索引几毫秒就返回了。换成 SELECT * FROM user WHERE id 999999居然还是几毫秒。表里明明有 500 万行数据为什么查任意一行速度都差不多MySQL 到底是怎么做到几乎瞬间定位到目标数据的关键就在“聚簇索引”这四个字。不过在理解聚簇索引为什么快之前我们得先弄明白它背后用的到底是什么数据结构。聚簇索引数据和索引长在一起在 InnoDB 中表本身就是按主键组织的一棵 B 树。所谓聚簇就是数据行和主键索引绑在一起不分开存放。一本字典书的正文部分本身就是按拼音排序的。你想查张字翻到 Z 开头的位置直接就能看到张的释义不需要先查一个单独的拼音索引再去另一个地方找释义。正文和索引是同一份东西。聚簇索引就是这个思路。主键索引的叶子节点里直接存的就是完整的数据行。你通过主键查一行数据找到叶子节点就找到了全部字段不需要回表不需要二次查找。非叶子节点只存主键值用来做导航叶子节点存完整的行数据按主键顺序排列并且叶子节点之间用双向链表串起来。没有聚簇索引会怎样假设表没有主键数据就是一堆散落在磁盘上的行。要查id 500这一行数据库只能从头开始一行一行扫直到找到为止。五百万行数据最坏情况下要扫五百万次。这就是全表扫描。如果有一棵 B 树做索引呢同样是五百万行树的高度大概是 3 到 4 层。你只需要从根节点走到叶子节点经过 3-4 次磁盘 IO就能定位到目标行。全表扫描是 O(n)走索引是 O(log n)。当 n 是五百万的时候这个差距就是几毫秒和几十秒的差距。抛出问题为什么是 B 树到这里我们知道了聚簇索引的数据结构是 B 树。但为什么是 B 树MySQL 为什么不用别的数据结构这不是一个显而易见的问题。直觉上我们可能会想到很多方案有序数组、二叉搜索树、红黑树、Hash 表、B 树。每一种看起来都有道理但每一种都有致命缺陷。我们来打一场淘汰赛让他们切磋切磋。淘汰赛其他数据结构为什么不行选手一有序数组有序数组支持二分查找O(log n) 的查询效率很快。但它有一个致命问题插入和删除的成本太高。你在数组中间插入一个元素后面所有元素都得往后挪。五百万行数据插一次可能要挪几百万个元素。更新频繁的业务表根本扛不住。优点缺点查询 O(log n)插入/删除 O(n)支持范围查询不适合频繁写入的场景淘汰原因写入代价太高只适合读多写极少的场景比如历史归档表。选手二二叉搜索树 / 红黑树二叉搜索树查询也是 O(log n)红黑树还能保证树的平衡。看起来不错问题在于树太高了。二叉树每个节点只有两个子节点五百万行数据树的深度大概是 22-23 层。每一层就是一次磁盘 IO。23 次磁盘 IO在机械硬盘上意味着几十毫秒的延迟。数据库操作的瓶颈不在 CPU 计算而在磁盘 IO。我们真正要优化的不是比较次数而是 IO 次数。优点缺点查询 O(log n)树太高IO 次数多红黑树保证平衡每个节点只有 2 个子节点淘汰原因树深度太大磁盘 IO 次数太多。选手三Hash 表Hash 表的查询是 O(1)比任何树都快。MySQL 自己也支持 Hash 索引Memory 引擎。那为什么 InnoDB 不用 Hash 做主键索引因为 Hash 表不支持范围查询。你查WHERE id 500Hash 表确实很快。但你查WHERE id BETWEEN 100 AND 500Hash 表就傻了——它只能一个一个算 hash 值没法利用数据的有序性。而范围查询在业务中太常见了。查最近一周的订单、查某个价格区间的商品、查某个时间段的日志全是范围查询。优点缺点等值查询 O(1)不支持范围查询精确匹配极快不支持排序淘汰原因无法处理范围查询而这是数据库的高频操作。选手四B 树B 树和 B 树名字只差一个符号但差异很大。B 树的每个节点——包括非叶子节点——都存完整的数据行。这意味着每个节点能存的 key 数量变少了树会更高IO 次数更多。而且 B 树的叶子节点之间没有链表连接范围查询只能在树内部做中序遍历效率远不如 B 树沿着链表顺序扫。优点缺点查询 O(log n)非叶子节点存数据树更高支持范围查询叶子节点无链表范围查询效率低淘汰原因非叶子节点冗余存储数据范围查询效率不如 B 树。淘汰赛总结数据结构查询写入范围查询树高度结论有序数组O(log n)O(n)支持—写入太慢二叉树/红黑树O(log n)O(log n)支持太高IO 太多Hash 表O(1)O(1)不支持—无法范围查询B 树O(log n)O(log n)支持较高非叶子节点冗余B 树O(log n)O(log n)高效极低全部达标B 树是唯一一个全部过关的选手。B 树长什么样B 树是一种多路平衡搜索树不是二叉是多叉。每个节点可以有多个子节点具体数量由阶决定。比如一棵 3 阶 B 树每个节点最多有 3 个子节点。来看一棵简化版的 B 树假设每个非叶子节点最多存 3 个 key从根节点到任意叶子节点经过的层数是固定的。这就是 B 树的平衡性——不管数据怎么分布查询路径长度都一样。B 树的两个关键特征特征一非叶子节点只存 key不存数据这是 B 树和 B 树最核心的区别。B 树的每个节点都存完整数据行一个节点能放的 key 就少了。B 树的非叶子节点只存 key 值一个节点能塞进更多的 key扇出fan-out更大树就更矮。打个比方你去图书馆找书。B 树相当于每层楼的指示牌上都堆满了书指示牌很大一层楼放不了几个指示牌你要爬很多层。B 树相当于每层楼的指示牌只写分类编号很薄一层楼能放很多指示牌你两三层就到顶了书都在最顶层。树矮 IO 次数少 查询快。在实际的 InnoDB 中一个页page默认 16KB。假设一个 key 是 8 字节bigint指针 6 字节一个非叶子节点大约能存 16384 / 14 ≈ 1170 个 key。三层 B 树就能存 1170 × 1170 × 16 ≈ 2190 万行数据。两千多万行数据只需要 3 次磁盘 IO。特征二叶子节点形成有序双向链表B 树的所有叶子节点通过双向链表串起来按 key 顺序排列。这意味着什么范围查询。你要查WHERE id BETWEEN 100 AND 500先通过 B 树定位到 id 100 的叶子节点3 次 IO然后沿着链表往右扫一直扫到 id 500不需要回到父节点不需要中序遍历链表扫就行了。顺序 IO 比随机 IO 快得多尤其在机械硬盘上差距更大。这也是为什么 InnoDB 建议用自增主键——自增主键保证新数据永远插在链表尾部不会引起中间节点的分裂和数据挪动写入性能最好。为什么是 B 树三个维度收束把前面的分析收束起来B 树在三个维度上同时做到了最优1. 磁盘 IO 次数最少非叶子节点不存数据 → 每个节点能放更多 key → 树更矮 → IO 更少。三层树就能覆盖两千万行数据。2. 范围查询效率最高叶子节点链表 → 范围查询变成顺序扫描 → 利用磁盘顺序 IO 的优势。不用在树里来回跳。3. 查询性能稳定平衡树 → 任何查询都走相同层数 → 没有运气好两层就到、运气差要走十层的情况。每次查询都是确定性的 O(log n)。这三条加在一起就是 MySQL 选择 B 树的全部理由。不是因为它某一项特别突出而是因为它每一项都够好没有短板。回答开头的问题回到最开始的问题五百万行数据SELECT * FROM user WHERE id 999999为什么几毫秒就能返回表数据以聚簇索引的形式组织成一棵 B 树数据行就存在叶子节点里五百万行数据的 B 树高度大约 3-4 层MySQL 从根节点出发经过 3 次二分查找定位到叶子节点叶子节点里直接就是 id 999999 那一行的完整数据不需要回表不需要二次查找3 次 IO 搞定就这么简单。不是 MySQL 有多快是 B 树的结构决定了它只需要 3 次磁盘读取就能定位到任意一行。小结B 树不是 MySQL 的发明它是一种通用的数据结构。MySQL 选择它是因为它在磁盘 IO、范围查询、查询稳定性三个维度上同时做到了最优是一个没有明显短板的方案。B 树的设计哲学其实是取舍的艺术。它放弃了 Hash 表 O(1) 的极致点查速度换来了范围查询的能力它放弃了 B 树每个节点都存数据的直觉设计换来了更矮的树和更少的 IO。每一个放弃背后都是对数据库真实使用场景的深刻理解——数据库不只有点查还有范围扫描、排序、分组B 树是这些需求的最优交集。
