索引的物理存储结构：数据页、索引页与B+树层高计算
上一章我们搭好了实验环境，相信你已经跑通了基础语句。这一章我想聊聊索引的物理存储——说白了就是索引在磁盘上到底长什么样，怎么算出B+树到底有几层。你可能会觉得层高计算是个理论问题，但我在调优时发现，很多慢SQL的根因就是层高没算好。
数据页：最小的I/O单元
MySQL（InnoDB）的数据页大小默认为16KB。什么意思呢？你读一行数据，InnoDB会把整页数据从磁盘拉到内存里。你写一行，也是写满一页才落盘。这很好理解——机械硬盘最怕随机I/O，一次I/O能多带点数据就多带点。
数据页的结构很清晰，我直接列个表给你看：
| 区域 | 大小 | 作用 |
|---|---|---|
| File Header | 38字节 | 页类型、上一页/下一页指针、校验和等 |
| Page Header | 56字节 | 槽数、页内记录数、空闲空间起始偏移 |
| Infimum + Supremum | 固定 | 页面内最小和最大虚拟行记录 |
| User Records | 动态 | 实际行数据（按主键顺序排列） |
| Free Space | 动态 | 剩余空间 |
| Page Directory | 动态 | 槽数组，加速页内二分查找 |
| File Trailer | 8字节 | 校验和，用于崩溃恢复 |
注意看，User Records 是物理上按主键顺序存储的。你插入一条新记录，InnoDB 不会直接追加到末尾，而是找到该页内合适的位置插入，必要时分裂页。这也是为什么主键顺序插入性能最高。
索引页：B+树的非叶子节点
索引页和数据页本质上是一样的——都是16KB的页。区别在于里面存的不是完整行数据，而是索引项。每个索引项包含两部分：
- 键值：索引列的值
- 页号：指向下一级页的指针（4字节）
举个例子，假设整型主键（INT，4字节）加上页号（4字节），一个索引项大概8字节。那么每个索引页能存（16KB - 固定开销）≈ 16380字节 / 8 ≈ 约2000个索引项。这个数字很关键，后面算层高时要用。
B+树层高计算：关键公式
现在我们来算核心问题：一个表有1亿行数据，B+树到底有几层？
先明确几个参数：
- 非叶子节点的出度（扇出）：每个索引页能存多少个索引项，记为 N
- 叶子节点容量：每个数据页能存多少行记录，记为 M
- 总行数：R
公式很简单，但你要理解它的推导过程：
- 第1层（根节点）：1个页，最多指向 N 个第2层页
- 第2层：最多 N 个页，每个指向 N 个第3层页，总数 N²
- 第k层：最多 N^(k-1) 个页
- 叶子页总量：第最后层（假设高度为h）有 N^(h-1) 个数据页
- 能承载记录数：N^(h-1) × M ≥ R
所以，B+树高度 h 满足：
h = ceil( log_N( R / M ) ) + 1
注意这里加1是因为根节点也算一层。
实战计算示例
我们填几个实际数字。
场景1：整型主键，每行200字节
- N（非叶子出度）：每个索引项 4B键 + 4B页号 = 8B；16384B / 8B ≈ 2048
- M（每页行数）：16384B / 200B ≈ 81 行
- R = 1亿 = 10^8
计算：R / M ≈ 10^8 / 81 ≈ 1.23×10^6；log₂₀₄₈(1.23×10^6) ≈ log₂(1.23×10^6) / log₂(2048) ≈ 20.23 / 11 ≈ 1.84；向上取整=2；再加1 -> h = 3
是的，你猜对了——一百行的表通常2～3层就够了，三亿行可能也就4层。这也是为什么B+树作为索引结构这么强大：层数极低，I/O次数极少。
场景2：varchar(255) 主键，每行500字节
- N：假设平均键值30字节+页号4B ≈ 34B；16384/34 ≈ 481
- M：16384/500 ≈ 32 行
- R = 1亿
计算：R/M ≈ 3.125×10^6；log₄₈₁(3.125×10^6) = ln(3.125×10^6)/ln(481) ≈ 14.96/6.17 ≈ 2.42；取整=3；加1 -> h = 4
看到没？同样1亿行，因为主键变长、行变长，层数从3变成了4。多一层就是多一次随机I/O。所以，选择短主键非常关键。
我也踩过的坑：索引页分裂导致的层高异常
有一次我排查一个线上查询，走唯一索引，理论上应该3层就能找到，但实际执行计划显示每次查询都需要读4个页。很奇怪，于是我抓了SHOW TABLE STATUS看索引大小，发现数据量明明只有5000万行，索引却占了1.2GB。算一下：如果只有3层，索引页数量应该在2万左右（N=2000，叶子页数≈2.5万），但实际索引页数量超3万——说明扇出远低于理论值。
原因呢？表中大量delete+insert操作导致了索引页分裂后没有合并，形成了很多只存了几十个索引项的半空页。于是扇出从2000降到400，层数自然上去了。
怎么解决？OPTIMIZE TABLE可以重新整理聚簇索引，或者干脆重建索引。从那以后，我养成了定期检查索引碎片率的习惯——SELECT * FROM information_schema.INNODB_SYS_INDEXES配合INNODB_SYS_TABLESPACES可以查出每个索引的实际页数量，跟理论值做对比。
B+树结构图
下面的SVG把完整的B+树结构画出来了。你可以对照着理解层高和图节点的关系。
层高计算的工程意义
知道了怎么算，能干嘛？我列几个直接的应用场景：
- 预估索引大小：用公式反推索引页数量，就能算出索引占多少磁盘空间。我一般上线前会粗略估算一下，避免索引膨胀导致buffer pool装不下。
- 判断是否需要分区：如果你算出层高已经接近4或5层（比如1亿行、索引列较长），可以考虑分区或使用子分区来降低层高。
- 选择索引列顺序：联合索引中把选择性高的列放前面，能减少索引项数量，间接降低层高。
SELECT b.name, a.page_no, a.index_id, a.num_leaf_pages, a.num_internal_pages FROM information_schema.INNODB_SYS_INDEXES a JOIN information_schema.INNODB_SYS_TABLES b ON a.table_id = b.table_id WHERE b.name = '你的库名/表名';。通过叶子页数和内部页数可以反推实际扇出，对比理论值，就知道索引碎片程度了。
内存模型与I/O关注点
最后再提一点：B+树层高直接决定了查询时访问磁盘的次数。一次随机I/O大约10ms（机械盘），3层就是30ms；如果层高变成5层，就是50ms，翻了一倍。但在SSD时代，随机I/O只有0.1ms左右，所以层高的影响没那么夸张。不过Buffer Pool命中率仍然很关键——如果层高导致的I/O次数让BP迅速淘汰热页，反而可能更严重。这个我们后面章节讲缓冲池管理时会展开。