先看一个只在数据库里才会出现的现象。同一张订单表,同样按主键范围查一段数据,建了 B 树索引的那张表,执行计划里的读页数会随着范围变大而多出一截;换成 B+ 树索引,读页数几乎和「结果占了多少页」成正比,范围越连续越划算。两条 SQL 的写法完全一样,差别只在索引的节点里放了什么、叶子之间有没有连起来。
这里的 SQL 行为按常见存储引擎描述,未在本机实测;树的结构、分裂过程和叶子扫描在本机用 Node.js 模拟,代码与输出都是实际跑出来的。
B 树(B-tree)是一种多叉平衡搜索树,每个节点可以存很多个 key,并且所有叶子都在同一层。B+ 树(B plus tree)是它的变体:内部节点只存 key 用来指路,真正的数据全部放在叶子节点,叶子之间再用链表串起来。这篇先讲清楚多叉树、节点容量和分裂,再把两种树的分工摊开,最后解释为什么范围查询在 B+ 树上更顺。
现场:同一条范围查询,走了两种路
假设要查主键从 100 到 200 的所有记录。B 树的做法是:从根节点开始,比较 key 决定往哪个孩子走,一路下到某个节点,找到下界 100。接下来它要按顺序把范围内的 key 全部取出来,而 B 树的数据分散在内部节点和叶子节点上,取完一个子树之后,必须回到父节点,读父节点里紧接着的那个 key,再进入右边的子树。
这个「回到上一层」的动作,就是跨层回溯。树的每一层通常对应磁盘的一页,回溯意味着同一页可能被反复访问,还要在内存里维护一个栈记住「下一个访问谁」。范围越大,回溯越多,读页顺序也越跳。
B+ 树的做法不一样。它同样从根一路走到叶子,找到第一个不小于 100 的 key 所在的叶子页。但从这一页开始,它不需要再回上层,因为每个叶子都存了一个指向右边相邻叶子的指针。顺着这个指针一页一页往右读,直到 key 超过 200 为止。整个过程只往一个方向走,读的页在逻辑上是连续的。
这两条路径的差别,不是「谁更聪明」,而是「数据放在哪」带来的必然结果。B 树把数据放在每一层,所以按 key 顺序遍历时必须回到上层;B+ 树把数据只放在叶子,并且把叶子连成一条链,所以范围扫描可以一直往前。要理解这个结论,得先回到多叉树本身。
多叉树:一个节点装下几百个 key
多叉树(multiway tree)是每个节点可以有多个孩子的树。二叉搜索树每个节点最多两个孩子、一个 key;多叉树一个节点能存几百个 key,孩子数量比 key 多一个。数据库选多叉,是为了配合磁盘的读写单位。
磁盘和内存之间搬运数据的最小单位通常是一页(page),常见大小是 16KB。一次读一页和读一个字节,付出的寻道与传输成本差不多,所以「一次多读一点」几乎是免费的。多叉树就是顺着这个特点设计的:让一个节点正好占一页,一次读页就把这一层的几百个 key 全部拿到内存里,在内存里做一次二分查找,再决定去哪个孩子。
节点容量指一个节点最多能放多少个 key。它由页大小和单个条目的大小决定。假设一页 16KB,页头等元数据占 32 字节,每个 key 占 8 字节,每个指向孩子的指针占 6 字节,那么一个 key 加一个指针是 14 字节。用本机 Node.js 按这个公式算,一页能放下的条目数是 1168,也就是扇出约为 1168。
扇出(fanout)就是一个节点平均有多少个孩子。扇出直接决定树高:同样一千万条记录,二叉树的叶子层大约需要二十多层,而扇出 1168 的多叉树只要三层左右。树高每少一层,一次查询就少读一页,这个差别在磁盘上会被放大成几毫秒到几十毫秒。
本机按同一公式算过:两层内部节点约覆盖 136 万条,三层约覆盖 15.9 亿条,一千万行只需要三层内部节点。扇出越大,树越矮,一次查询读的页越少。
分裂:节点满了以后怎么办
多叉树最难写的是插入。查找只是比 key、往下走,插入却可能把节点撑爆。节点有容量上限,往装满的节点里再塞一个 key 就放不下,这时要做的是分裂(split):从中间切开,分成左右两个节点,中间那个 key 提升到父节点,作为两个孩子的分界。
分裂的关键在于「中间 key 往上走」。它不再留在原来的节点里,而是变成父节点里的一个分隔值:比它小的都去左孩子,比它大的都去右孩子。父节点因此多了一个 key 和一个孩子指针。如果父节点也满了,就继续往上分裂;一直分到根节点,根节点也满了,就再往上长出一层新的根。树高就是这样增加的。
本机用 Node.js 跑了一个简化演示:每个节点最多放 4 个 key,依次插入 10 到 90。前四个 key 直接放进去,插入 50 时节点里已经有 5 个 key,触发分裂。中间位置的 30 被提升,左节点留下 10 和 20,右节点拿到 40 和 50。演示只保留提升后的 key 继续往下走,插入 90 时再次分裂,70 被提升。
const MAX = 4;
function splitIfNeeded(keys) {
if (keys.length <= MAX) return null;
const mid = Math.floor(keys.length / 2);
return { left: keys.slice(0, mid), up: keys[mid], right: keys.slice(mid + 1) };
}
let node = [];
for (const k of [10, 20, 30, 40, 50, 60, 70, 80, 90]) {
node.push(k);
const r = splitIfNeeded(node);
if (r) {
console.log(`插入 ${k} 后溢出:左 [${r.left}] 上升 ${r.up} 右 [${r.right}]`);
node = [r.up];
}
}
console.log('最后停在', JSON.stringify(node));
实际输出是两行分裂记录和一行最终状态:插入 50 后,左节点为 10、20,上升的 key 是 30,右节点为 40、50;插入 90 后,左节点为 30、60,上升的 key 是 70,右节点为 80、90;最后演示节点停在 70。真实实现里,左节点和右节点会继续接收后续插入,父节点也会保留全部 key,不会像演示这样只留一个提升值。
还有一个细节容易被忽略:分裂不只是改 key,还要改指针。父节点要新增一个孩子指针,叶子节点要和左右兄弟重新建立链接。B+ 树的叶子之间有一条链表,分裂时必须先把新节点接进这条链表,再调整父节点的分隔 key。顺序错了,就会出现「树能查到,但范围扫描漏数据」的半坏状态。
B 树与 B+ 树:数据到底放在哪一层
B 树的每个节点都存数据(或者存指向完整记录的引用),内部节点和叶子节点没有分工上的区别。好处是点查可能在半路就命中:要找的 key 正好在某个内部节点里,读到那一页就可以返回,不必下到叶子。坏处是内部节点被数据挤占了空间,一页能放的 key 变少,扇出变小,树容易变高。
B+ 树的内部节点只存 key 和孩子指针,不存数据。数据全部集中在叶子节点,而且叶子节点通常存的是指向完整记录的引用。内部节点因此能塞下更多 key,扇出更大,树更矮。点查必须走到叶子才能拿到数据,路径长度固定;范围查询则从第一个叶子开始,顺着链表扫。
B 树:每层都可能命中
内部节点也带数据,点查运气好时读得少;但一页能装的 key 少,扇出小、树偏高,范围查询要跨层回溯,全表扫描也不容易按顺序走。
B+ 树:数据只在叶子
内部节点只做索引,扇出大、树矮;点查固定走到叶子,代价稳定;叶子之间有链表,范围查询和全表扫描都能顺序读页。
同一页大小下比较更直观。B 树内部条目要多带一个数据引用,假设引用 6 字节,一个 key 加引用是 14 字节,再加孩子指针 6 字节,接近 20 字节,一页只能放八百多个。B+ 树内部一个 key 加一个孩子指针只要 14 字节,一页能放 1168 个,扇出因此差了一截。
还有一点常被说反:B+ 树并非所有查询都比 B 树快。单条等值查询,如果 key 正好在 B 树的内部节点,B 树可能少读一页;B+ 树一定要走到叶子。B+ 树赢在稳定和批量:点查路径固定,范围查询不回溯,全表扫描只扫叶子。
叶子链表:范围查询为什么顺
叶子链表(leaf linked list)是两种树最关键的结构差异。每个叶子除存 key 和数据,还存一个指向右邻叶子的指针,有些实现还有回指左邻的指针。所有叶子按 key 从小到大串成一条链,链上的顺序就是数据的排序顺序。
有了这条链,范围查询变成一个「定位加顺扫」的动作:先用内部节点找到下界所在的叶子,然后从这一页开始,按链表一直往右读,直到超过上界。中途不需要回到根,也不需要维护遍历栈。读页的顺序和 key 的顺序一致,操作系统和存储引擎都容易做预读,连续页的读取代价远低于随机页。
本机用一个缩小的例子验证了扫描路径:四个叶子页,每页三个 key,按 3 到 47 递增,叶子之间用 next 串起来。查 16 到 40,先跳过第一个叶子,从第二个叶子开始,依次访问第二、第三、第四个叶子,取出的结果是 19、23、27、31、35、39,到第四个叶子的 47 超过上界就停。
const leaves = [
{ keys: [3, 7, 11], next: 1 },
{ keys: [15, 19, 23], next: 2 },
{ keys: [27, 31, 35], next: 3 },
{ keys: [39, 43, 47], next: null }
];
function rangeScan(leaves, lo, hi) {
const visited = [], out = [];
let i = 0;
while (i !== null && leaves[i].keys[leaves[i].keys.length - 1] < lo) i = leaves[i].next;
while (i !== null) {
visited.push(i);
for (const k of leaves[i].keys) if (k >= lo && k <= hi) out.push(k);
if (leaves[i].keys[leaves[i].keys.length - 1] > hi) break;
i = leaves[i].next;
}
return { out, visited };
}
console.log(JSON.stringify(rangeScan(leaves, 16, 40)));
实际输出里,visited 是 1、2、3,表示只往前走了三个叶子页,没有回头;out 是 19、23、27、31、35、39。如果换成 B 树,同样要取这段范围,访问完一个子树后必须回到父节点,读出父节点里下一个分界 key,再进入右子树;访问的页序会在层级之间来回跳。数据量小的时候两者都快,页数一多,顺序和随机就分开了。
全表扫描也是同一个道理。B+ 树只需要找到最左边那个叶子,然后顺着链表把所有叶子读完,读的是连续的一整段页。B 树要按 key 顺序走遍整棵树,内部节点和叶子节点交替访问,页序不连续。所以数据库在做全表扫描时,如果走的是 B+ 树的聚簇索引,往往能利用顺序读把吞吐拉起来。
现象、原因与第一步排查
下面这些现象经常被归因成「索引没用」或者「数据库慢」,其实大多能落到节点结构、分裂和叶子链表上。遇到时先按表里的第一步定位,不要上来就加索引或者改 SQL。
| 现象 | 真实原因 | 第一步查什么 |
|---|---|---|
| 范围查询的数据量翻倍,读页数涨得更快 | B 树要在层级之间回溯,范围越大回溯越多 | 执行计划用的是 B 树索引还是 B+ 树索引 |
| 同样的数据量,一种索引树高多一层 | B 树节点存数据,一页装的 key 少,扇出小 | 节点里是否带数据引用,单页能放多少 key |
| 同一条点查忽快忽慢 | B 树可能在上层命中,B+ 树固定走到叶子,缓存命中不同 | 查询是否命中缓存,实际走了几层 |
| 插入一批数据后查询明显变慢 | 页分裂导致树高增加、页内空隙变多、填充率下降 | 插入顺序是否单调递增,页填充率是多少 |
| 范围查询少返回了记录 | 叶子链表没接好,分裂时漏改相邻叶子的指针 | 分裂后新旧叶子的 next 和 prev 是否都更新 |
| 走索引反而比全表扫描慢 | 范围太大,回表变成大量随机读,优化器放弃索引 | 扫描比例多大,能不能用覆盖索引 |
| 父节点也满了,插入报错或卡住 | 分裂没有向上级联,根节点拆分逻辑缺失 | 是否有递归分裂和根节点增高处理 |
| 按时间倒序查最近几条很慢 | 叶子链表只维护了向右指针,倒序要另想办法 | 是否在叶子之间维护了双向链接 |
表里最容易被误判的是第一行和第五行。第一行看起来像「范围大了自然慢」,实际是回溯带来的额外页访问;第五行看起来像「数据被删了」,实际是链表断了。判断 B+ 树的问题,先确认数据是不是只在叶子、叶子是不是连成了一条完整的链。
边界与代价:B+ 树不是免费的
B+ 树的第一个代价是写放大。一次插入可能触发叶子分裂,写新叶子、写旧叶子、写父节点,父节点满了还要继续往上。每次分裂都会让页里出现一半左右的空隙,随机插入时填充率大约在六成到七成,顺序插入时最右边的页会反复分裂。填充率低意味着同样的数据占更多页,缓存能装下的记录变少。
第二个代价是空间。每个 key 都要在内部节点里重复一份,叶子之间还要多存链接指针。B 树内部节点直接带数据,看起来更省,但数据分散到多层,范围查询和全表扫描的读页效率更差。
第三个代价是并发。分裂会同时修改多个页,还要修改叶子链表,必须加锁或者用更复杂的并发协议。高并发写入时,热点页的分裂会成为争用点;自增主键让所有插入都落在最右叶子,这个叶子就是热点页。很多数据库因此建议用随机分布的主键,或者对大表做分区,把写入摊开。
还有一个边界要说清楚:B+ 树适合「按 key 有序访问」的场景,不适合所有查询。如果查询条件里没有索引的最左前缀,或者对索引列做了函数运算,树再矮也用不上。如果单次查询要返回表里很大比例的行,回表的随机读可能比直接全表扫描还贵,优化器会主动放弃索引。结构好不等于每次都快,还要看查询形状。
最后是维护成本。每个索引都是一棵额外的 B+ 树,插入要维护多棵树,更新索引列等于删一条再插一条。索引越多,写入越慢,空间越大,选索引要从真实查询出发。
当天能做的练习
- 用纸画出扇出为 4 的多叉树,依次插入 1 到 20,标出每次分裂提升了哪个 key、树高在哪一步增加,再用本文代码对照。
- 按 16KB 页、32 字节页头、8 字节 key、6 字节指针,算出扇出、两层和三层容量,再算一千万行需要几层内部节点,与文中数字对照。
- 把分裂演示改成每个节点最多 6 个 key,重新插入 10 到 90,记录每次分裂的左右节点与提升 key,看分裂次数怎么变。
- 把叶子链表的例子扩到八个叶子页,查 5 到 60,打印访问过的叶子下标和结果;再把某个 next 改成 null,确认查询会提前停止并漏数据。
- 用文字描述 B 树范围查询的顺序:从根到下界、访问子树、回到父节点、再进右子树,数访问了几个节点,再和 B+ 树只走叶子链表对比。
小结与下一篇
三句话收一下:多叉树把一页当成一个节点,用大扇出换低树高;节点满了就分裂,中间 key 上升,父节点满了继续往上;B 树每层都存数据,B+ 树只在叶子存数据并把叶子串成链表,所以范围查询和全表扫描可以一直往前读。
下一篇把这些结构放进真实查询里算账:一次点查读几页,一千万行为什么树高 3,LIMIT 10 OFFSET 100000 为什么要先扫十万行,二级索引为什么回表,覆盖索引省掉了哪几次读页。