B+ 树索引结构

磁盘上的有序数据需要一种在树高受限的前提下完成查找的结构。二叉树每个节点只做两路分支，树高随记录数增长较快，而每次下探通常意味着一次随机读。多路平衡查找树让单个节点容纳多个键，把树高压缩到较小范围，从而减少随机读次数。这一结构通常称为 B 树，其变体 B+ 树在数据库索引实现中被广泛采用。

B 树与 B+ 树的结构差异

两者的差别在键的存放位置与节点职责的划分上：

• B 树的内部节点同时保存键与数据记录（或指向记录的指针），查找可能在内部节点命中并提前结束。
• B+ 树的内部节点只保存键与子节点指针，全部数据记录位于叶子节点，查找都会落到某一层叶子。

内部节点不携带数据，使同一页能容纳更多分支，因此在键数相同时树高通常更低；代价是每次查找都要走到叶子。

节点容量与平衡维护

阶与填充因子

节点容量常用阶来描述，一个 m 阶节点的子指针数不超过 m。实际实现里约束落在页上：每个节点对应一个页，键与指针的总长度不能超过页大小，因此阶由键长度与页大小共同决定。

填充因子描述节点被填满的程度。顺序插入时页接近满值才分裂；写入随机的键时，页的平均占用率通常低于满值，因为分裂发生在页已满、无法再放下新键的时刻。分裂点的选取会影响长期占用率：多数实现把已满节点按中间位置拆成两个节点，并把中间键上移到父节点；也有实现让两侧留出不对称的空间，以减少顺序插入时的分裂次数。

分裂与合并

父节点同样可能已满，分裂会向上传播；若根节点分裂，树高加一。删除键后节点占用率下降，若低于某个阈值，实现可能从兄弟节点借键，或把两个节点合并，合并会把父节点的分隔键一并删除，进而继续向上传播。

由于借键与合并都需要访问兄弟节点并加锁，部分实现只做页内空间回收而暂不合并，把释放的空间留在页中供后续插入复用。

范围扫描与叶子链表

范围查询要求返回某个区间内的全部键。B+ 树先从根下降到区间起点所在的叶子，再沿叶子之间的链表顺序推进，直到越过区间终点。除起点定位以外，读取过程接近顺序读，随机读次数与树的层数相关，而与结果集大小关系不大（跨页读取的成本另计）。

SELECT id, created_at FROM orders
WHERE created_at BETWEEN '2026-01-01' AND '2026-02-01'
ORDER BY created_at;

若索引建立在 created_at 上，上述查询可沿叶子链表取数并天然满足排序要求；若缺少可用索引，则可能退化为整表扫描加排序。取回阶段通常分批进行，其组织方式可参见 结果集虚拟滚动与懒加载。

聚簇索引与二级索引

按叶子节点的内容可以区分两类索引：

• 聚簇索引：叶子存放完整行记录，因此表数据本身按索引键有序排列。一张表通常只能有一个，因为行的物理组织只有一种。
• 二级索引：叶子存放索引列的值与指向行的引用，引用形式可能是行标识，也可能是主键值。

通过二级索引查到引用后，再去聚簇索引取完整行的过程称为回表。回表的代价通常是一次额外的树查找，当二级索引命中行数较多时，回表次数与命中行数成正比。

复合索引的前缀匹配

复合索引按列顺序构成键的元组，键之间的比较逐列进行。因此建立在 (a, b, c) 上的索引可以支撑约束了 a，或 a 与 b，或 a、b、c 的查询；只约束 b 或 c 的查询通常无法借助该索引定位区间，只能退化为扫描。这一规则通常称为左前缀匹配。

它成立的条件是过滤条件在列上构成连续前缀，并且这些列上做的是等值或可用范围表示的比较。列的顺序不改变前缀规则本身，但会影响同一前缀之下的键数。

索引覆盖

如果查询所需的全部列都能从索引中获得，实现可以不再回表，这一情形通常称为索引覆盖。判断依据是投影列与过滤列是否都被索引键包含。对聚簇索引而言，叶子已包含整行，覆盖条件自然成立；对二级索引而言，多访问一列就可能破坏覆盖，从而引入回表。

选择性对索引收益的影响

索引是否被采用取决于命中行的比例。若某个条件命中表中大部分行，优化器可能选择扫描整表而不走索引，原因是按索引取数会产生大量随机读，叠加回表后，随机读次数与往返次数可能超过一次顺序扫描。

条件过滤掉的行越多，按索引取数需要访问的行越少，索引带来的随机读次数也就越少。优化器估计选择性时依赖统计信息，通常包括列的基数与值的分布直方图；统计信息过旧会让估计偏差放大，进而使计划偏离预期。

小结

B+ 树把键集中在叶子节点、让内部节点只保留分支，使树高受限；叶子链表让范围扫描以接近顺序的方式推进；分裂与合并维持平衡。是否走索引则是回表成本与命中行数之间的权衡，这一权衡建立在选择性估计之上。