B+ 树是 InnoDB 存储引擎实现索引的底层数据结构。理解它的结构和查询方式，并不是为了让你去手写一棵树，而是为了让你在面对索引优化时，能真正理解“为什么联合索引要按这个顺序建”、“为什么范围查询后面的条件会失效”这类实际问题。
5.3.1 B+ 树的结构：从磁盘视角看索引
InnoDB 的所有数据都是以“页”为单位存储在磁盘上的，默认每个页的大小是 16KB。B+ 树的每个节点就恰好对应一个数据页，这种设计使得一次磁盘 I/O 读取一个节点变成一件非常自然的事。
B+ 树由三种节点组成：根节点（Root Node）、内部节点（Internal Node）和叶子节点（Leaf Node）。它的结构有几个关键特征：
- 所有数据都存放在叶子节点中：内部节点只存储索引键值和指向下一层节点的页指针，不存实际行数据。这使得每个内部节点可以容纳更多的键值，从而让整棵树变得更矮。
- 叶子节点之间用双向链表连接：这是 B+ 树区别于普通 B 树的一大亮点。每个叶子节点中存储了相邻叶子节点的指针，使得在叶子节点这一层，数据按索引键值从大到小形成一个有序的链表。
- 节点内部数据有序：不管内部节点还是叶子节点，它们内部的键值都是按照升序（或降序，取决于索引定义）严格排列的。这一点保证了查找时可以快速通过二分法定位。
如果以一张具体的表来观想，假设有一张用户表 users，主键 id 是 INT 类型，InnoDB 就会以 id 为键建立一棵主键 B+ 树。在这棵树中：
- 叶子节点存储的是完整的用户行数据（因为 InnoDB 的主键索引是聚簇索引，行数据直接挂在叶子节点里）。
- 内部节点只存主键值和对孩子页的引用，一个 16KB 的页能装上千个这样的条目。
- 每个叶子节点中，除了存放行数据，还包含指向前一个叶子节点和后一个叶子节点的指针。
这样一来，B+ 树形成了一种兼具“搜索树”和“有序链表”性质的结构：顺着根节点往下走，可以快速定位某一条数据；一旦找到叶子节点，顺着链表就能顺序遍历出一大片数据。
5.3.2 一个等值查询的完整过程
当执行一条最基础的查询 SELECT * FROM users WHERE id = 1000; 时，InnoDB 是如何利用这棵 B+ 树找到数据的？
- 从根节点开始：服务器先定位到这张表的聚簇索引根页，这个根页通常在表第一次创建时就确定，并且会被缓存在 Buffer Pool 里，很少需要真的读磁盘。
- 层序判断：根据根节点内部存储的键值范围，判断
id = 1000应该落在哪个区间。比如根节点里有键值[500, 2000, 4000]，1000落在500和2000之间，那么沿着对应的页指针跳转到下一层内部节点。 - 向下钻取：在下一层内部节点继续同样的二分查找，一直走到叶子节点所在的层。B+ 树的世界里，不管表有多少层，到叶子节点的搜索路径总是从根到某片叶子的一条直线。
- 命中数据：在叶子节点内部，通过页目录（Page Directory）二分查找，快速定位到
id = 1000所在的具体行记录，然后将这行数据返回。
整个过程，读到的节点数等于树的高度。对于一个 3 层的 B+ 树，只需要 3 次 I/O 就能完成查询。考虑到根节点常驻内存，实际需要读盘的通常只有 2 次甚至 1 次。
如果走的是二级索引（如 idx_name），流程会多一步“回表”：先在二级索引的 B+ 树叶子节点中找到对应记录的主键值，然后再到聚簇索引的 B+ 树中用主键值查找完整的行数据。这也是为什么推荐用覆盖索引来避免回表——如果查询的列全部包含在二级索引的叶子节点中，直接从二级索引就能返回结果，无需再去主键树上查一次。
5.3.3 范围查询为什么高效：链表遍历的本质
B+ 树的一大实战亮点是它的范围查询能力。比如 SELECT * FROM users WHERE id BETWEEN 1000 AND 2000;：
- 先像等值查询一样，通过根→内部→叶子的寻找路径，定位到第一个符合条件的叶子节点（即包含
id >= 1000的页）。 - 然后顺着叶子节点之间的双向链表向右扫描，逐页读取，直到超出
2000的范围为止。
这个过程的优势在于：除了最开始的一次搜索定位，后续的遍历全是沿着链接指针顺序读数据页。因为磁盘在对顺序 I/O 的处理上远优于随机 I/O，这种链表式的扫描在物理上体现为对相邻数据页的连续读取，效率很高。
排序查询能利用索引也是同样的道理。ORDER BY id 如果走聚簇索引，直接在叶子链表上扫描就能天然得到有序结果，不需要额外的文件排序。这也是为什么尽量让索引满足排序需求能极大减少临时磁盘空间的使用。
5.3.4 关于索引高度的直觉：为什么 B+ 树通常很矮
很多开发者第一次接触 B+ 树时的一个困惑是：“我的表有几千万行数据，这棵树会不会高得离谱？” 答案是：不会。这正是 B+ 树强于其他结构的地方。
不妨做一个粗算。假设一张表的主键是 8 字节的 BIGINT，每个页指针占 4 字节，那么内部节点每个键值+指针的组合约占 12 字节。一个 16KB 的页减去页头页尾的开销后，大约能存储 1200 个这样的组合条目。这意味着：
- 根节点（1 个页）可以指向 1200 个内部节点。
- 第二层 1200 个内部节点，每个又可以指向 1200 个叶子节点，此时叶子节点数 = 1200 × 1200 = 1,440,000 个。
- 第三层叶子节点中，每个页假设存 100 行记录（实际随行大小浮动），那么这棵树能轻松容纳 1.44 亿行数据，高度仅为 3 层。
也就是说，几千万行级别的表，B+ 树高度通常就是 2 到 3 层，上亿行也基本不会超过 4 层。在实际观测中，通过 SHOW TABLE STATUS 或者查看索引文件大小可以间接验证这一点——绝大部分业务表的 B+ 树高度都卡在 2 到 3 层，这就是 B+ 树为磁盘 I/O 而生带来的底气。
这一节内容如果能形成一种直觉——索引查询从根走到叶子节点，最多只需要屈指可数的几次磁盘读取——那么你在分析慢查询时就会更敏锐：一次 EXPLAIN 看到 rows 很大但 type 不是 ALL，可能就是在索引叶子链表上扫了大量页。此时我们优化的方向就不是“加索引”，而是“减少索引扫描的范围”，这就是下一节要讨论的索引代价与选择性的事了。