数据库按主键查一行，为什么通常只读 3 个页？为什么主键建议短一点？为什么范围查询快，而 LIKE '%关键词' 快不起来？
这些问题的答案，都在 B+ 树的形状里。
本文不背结论，直接从一棵小树开始：先定规则，再走一遍查找、插入、删除、范围查询，最后写出完整实现。全文用 order=4（每个节点最多 4 个孩子、3 个 key），小到能在纸上画完；核心规则和真实数据库一致，真实实现另外还多了并发、锁、页头等工程细节。
一、为什么是 B+ 树：先把树压矮
磁盘按页读写，一次随机 I/O 约 100 µs（SSD）；内存里一次比较只要几十纳秒。点查一棵树要读多少页，基本等于树有多高。所以数据库索引优化的第一目标不是“比较次数最少”，而是树最矮。
二叉搜索树每个节点只有 2 个孩子。1000 万个 key，树高约 ceil(log2(10^7)) = 24 层，点查最坏要 24 次随机 I/O。
B+ 树把一个节点变成一个 16 KB 的页，页里塞几百上千个 key，树高立刻塌下来：
算一下就明白。key 8 B 加子页指针 6 B，约 14 B 一路，16 KB 的一页能放约 1170 路；叶子一行 key + 行指针约 14 B，加上行头按 16 B 估算，一页约 1024 行。于是：
- 2 层：
1170 × 1024 ≈ 120 万行 - 3 层：
1170² × 1024 ≈ 14 亿行
这就是“三层 B+ 树能装千万到十亿级数据”的算术来源。主键越短，一页装的路越多，树越矮——这条优化规则从第一性原理直接推出来。
B 树的内部节点也存数据，同样大小的页能放的指针更少；范围查询还要在树里来回走。B+ 树把数据全部赶到叶子，内部页只留 key 和指针，扇出更大；叶子再用链表串起来，范围扫描可以横着走。这是它成为数据库索引默认结构的直接原因。
二、五条规则，定义一棵 B+ 树
- 每个节点最多 m−1 个 key；内部节点最多 m 个孩子。 非根节点至少
ceil(m/2)−1个 key。order=4 时：最多 3 个 key，最少 1 个 key。 - 内部节点的
keys[i]是分界值：左孩子所有 key <keys[i]≤ 右孩子所有 key。它通常等于右子树的最小 key。 - 数据只存在叶子；内部节点只存导航用的 key 和子页指针。
- 所有叶子在同一层，所以每次点查经过的层数都一样。
- 叶子之间用
next指针按 key 顺序串成链表。
根节点是唯一的例外：树可以是空的；非空树的根可以只有 1 个 key，不受下限约束。其他节点低于下限就叫下溢，插入和删除的复杂逻辑，本质上都在修下溢。
一个实现细节：删除最小 key 后，
keys[i]可能不再正好等于右子树最小值，但“左 < 分界值 ≤ 右”始终成立，查找不受影响。本文不专门回填它。
三、节点长什么样
内部节点只有两个数组：keys 和 children。keys.length 永远比 children.length 少 1，key 之间的每个“缝”就是一个子页指针。
叶子节点多两个字段：values 和 next。真实数据库里，叶子存整行或“主键 + 行指针”；内部页只存 key，不存数据。
// B+ 树教学实现：order = 每个节点最多有多少个子节点
// 约定：内部节点的 keys[i] 是分界值：左孩子所有 key < keys[i] ≤ 右孩子所有 key
// 所有数据只存在叶子节点；叶子节点用 next 串成一条有序链表
export type Node = InternalNode | LeafNode;
export interface InternalNode {
leaf: false;
keys: number[];
children: Node[];
}
export interface LeafNode {
leaf: true;
keys: number[];
values: string[];
next: LeafNode | null;
}
export class BPlusTree {
root: Node | null = null;
size = 0;
readonly order: number;
readonly maxKeys: number;
readonly minKeys: number;
constructor(order = 4) {
if (order < 3) throw new Error('order 至少为 3');
this.order = order;
this.maxKeys = order - 1;
this.minKeys = Math.ceil(order / 2) - 1;
}
order=4 对应 maxKeys=3、minKeys=Math.ceil(4/2)-1=1。这两个数字后面会反复用到。下面按操作逐个补全这个类，所有片段按顺序拼起来就是完整文件。
四、查找：在每一层做一次路由
从根开始，在内部节点里找“第一个大于 key 的分界值”：比它小就走左边，否则（包括相等）走右边。走到叶子后，在叶子的 keys 里二分。
// ---------------------------------------------------------- 查找
/** 点查：沿树下降到叶子，再在叶子里二分。 */
search(key: number): string | undefined {
if (!this.root) return undefined;
const leaf = this.findLeaf(key, []);
const at = this.lowerBound(leaf.keys, key);
return leaf.keys[at] === key ? leaf.values[at] : undefined;
}
/** 记录下降过程中经过的内部节点，最后一个就是叶子的父节点。 */
private findLeaf(key: number, path: InternalNode[]): LeafNode {
let node: Node = this.root!;
while (!node.leaf) {
path.push(node);
let i = 0;
while (i < node.keys.length && key >= node.keys[i]) i++;
node = node.children[i];
}
return node;
}
private lowerBound(keys: number[], key: number): number {
let lo = 0;
let hi = keys.length;
while (lo < hi) {
const mid = (lo + hi) >>> 1;
if (keys[mid] < key) lo = mid + 1;
else hi = mid;
}
return lo;
}
三个细节：
key >= keys[i]的等号很重要：key 等于分界值时，只可能去右子树找。分界值不大于右子树的最小 key；左边所有 key 都小于它，所以不可能在左边。lowerBound返回第一个大于等于 key 的位置，查找和插入都用它定位。- 查找只读
height个页；页内比较是内存操作，可以忽略（真实数据库会在页内二分，把每层比较压到log m）。
五、插入：先放进去，满了就分裂
5.1 叶子有空位
插入永远发生在叶子：先按查找的路径走到叶子，把 key 插到有序位置。key 已存在就更新 value，不新增。
// ---------------------------------------------------------- 插入
/** 插入；key 已存在时更新 value。 */
insert(key: number, value: string): void {
if (!this.root) {
this.root = { leaf: true, keys: [key], values: [value], next: null };
this.size = 1;
return;
}
const path: InternalNode[] = []; // 从根到叶经过的内部节点
const leaf = this.findLeaf(key, path);
const at = this.lowerBound(leaf.keys, key);
if (leaf.keys[at] === key) {
leaf.values[at] = value; // 重复 key：只更新
return;
}
leaf.keys.splice(at, 0, key);
leaf.values.splice(at, 0, value);
this.size++;
if (leaf.keys.length > this.maxKeys) {
const [left, right, upKey] = this.splitLeaf(leaf);
this.fixAfterSplit(path, left, right, upKey);
}
}
注意 path：下降时把经过的内部节点记下来，后面分裂时才知道该把新 key 插到哪个父节点。
5.2 叶子分裂
叶子最多 3 个 key，插入第 4 个就溢出。做法是从中间劈开：
- 左叶留前
floor(m/2)个 key； - 右叶拿剩下的；
- 右叶的第一个 key（右子树的最小 key）复制一份，插到父节点做分界值。key 本身留在叶子里，因为数据不能丢。
private splitLeaf(leaf: LeafNode): [LeafNode, LeafNode, number] {
const mid = Math.floor(this.order / 2);
const right: LeafNode = {
leaf: true,
keys: leaf.keys.slice(mid),
values: leaf.values.slice(mid),
next: leaf.next,
};
leaf.keys = leaf.keys.slice(0, mid);
leaf.values = leaf.values.slice(0, mid);
leaf.next = right;
return [leaf, right, right.keys[0]]; // 右叶最小 key 复制一份给父节点
}
splitLeaf 里返回的 right.keys[0] 是复制，不是移动。父节点里的 7 只是目录，真正的数据 7 还在右叶。
5.3 内部节点也满了
父节点收到新的分界值后可能也超过 3 个，需要继续分裂。规则和叶子不同：
- 内部节点的中间 key 上移，成为父节点的分界值，原节点不再保留它；
- 左右两边各自保留一部分 key 和对应的子页指针。
为什么中间 key 可以“搬走”？因为内部 key 只是目录项，真正的 key 在叶子里都有一份。这是 B+ 树分裂时最容易和 B 树混淆的地方。
内部页的分裂点取 floor((m−1)/2)：order=4 时，把下标 1 的那个 key 搬上去，左边留 1 个 key，右边留 2 个。
private splitInternal(node: InternalNode): [InternalNode, InternalNode, number] {
const mid = Math.floor((this.order - 1) / 2);
const upKey = node.keys[mid];
const right: InternalNode = {
leaf: false,
keys: node.keys.slice(mid + 1),
children: node.children.slice(mid + 1),
};
node.keys = node.keys.slice(0, mid);
node.children = node.children.slice(0, mid + 1);
return [node, right, upKey]; // 中间 key 上移，不再留在本层
}
/** 叶子分裂后，把新节点和分隔 key 插进父节点；父节点可能继续分裂。 */
private fixAfterSplit(path: InternalNode[], left: Node, right: Node, upKey: number): void {
let node = left;
let sibling = right;
let key = upKey;
for (;;) {
const parent = path.pop();
if (!parent) {
this.root = { leaf: false, keys: [key], children: [node, sibling] };
return;
}
const at = parent.children.indexOf(node);
parent.children.splice(at + 1, 0, sibling);
parent.keys.splice(at, 0, key);
if (parent.keys.length <= this.maxKeys) return;
[node, sibling, key] = this.splitInternal(parent);
}
}
fixAfterSplit 是一个循环：叶子裂了插父页，父页裂了插祖父页，直到某层放得下。如果一路裂到根，就新建一个根，树高加 1。
六、删除：借一个，借不到就合并
删除先定位叶子并移除 key。如果删除后叶子仍然不少于 minKeys（order=4 时 1 个 key），直接结束；否则下溢，分三种情况：借位、合并、根收缩。如果根本身就是叶子，删空后直接把 root 置空，树变成空树。
删除主体和修复循环：
// ---------------------------------------------------------- 删除
/** 删除；key 不存在返回 false。 */
delete(key: number): boolean {
if (!this.root) return false;
const path: InternalNode[] = [];
const leaf = this.findLeaf(key, path);
const at = this.lowerBound(leaf.keys, key);
if (leaf.keys[at] !== key) return false;
leaf.keys.splice(at, 1);
leaf.values.splice(at, 1);
this.size--;
if (this.root === leaf) {
if (leaf.keys.length === 0) this.root = null;
return true;
}
if (leaf.keys.length < this.minKeys) this.fixUnderflow(path, leaf);
return true;
}
/** 从下往上修：能借就借，借不到就合并；父节点不够了继续往上。 */
private fixUnderflow(path: InternalNode[], leaf: Node): void {
let node = leaf;
for (;;) {
const parent = path.pop();
if (!parent) {
if (!node.leaf && node.keys.length === 0) this.root = node.children[0];
return;
}
const at = parent.children.indexOf(node);
const left = at > 0 ? parent.children[at - 1] : null;
const right = at < parent.children.length - 1 ? parent.children[at + 1] : null;
if (left && left.keys.length > this.minKeys) {
this.borrowFromLeft(parent, at);
return;
}
if (right && right.keys.length > this.minKeys) {
this.borrowFromRight(parent, at);
return;
}
if (left) this.merge(parent, at - 1);
else this.merge(parent, at); // 没有左兄弟，就把右兄弟并进来
if (parent === this.root) {
if (parent.keys.length === 0) this.root = parent.children[0]; // 根空了：树高 -1
return;
}
if (parent.keys.length >= this.minKeys) return;
node = parent; // 父节点也不够了，继续往上
}
}
6.1 借位
- 左兄弟有富余：把左兄弟最大的 key（和 value）移到当前叶子最前面；父页分界值改成当前叶子的新最小值。
- 右兄弟有富余：把右兄弟最小的 key 移到当前叶子最后面；父页分界值改成右兄弟的新最小值。
private borrowFromLeft(parent: InternalNode, at: number): void {
const node = parent.children[at];
const left = parent.children[at - 1];
if (node.leaf && left.leaf) {
node.keys.unshift(left.keys.pop()!);
node.values.unshift(left.values.pop()!);
parent.keys[at - 1] = node.keys[0];
} else if (!node.leaf && !left.leaf) {
node.keys.unshift(parent.keys[at - 1]);
node.children.unshift(left.children.pop()!);
parent.keys[at - 1] = left.keys.pop()!;
} else {
throw new Error('树结构损坏：兄弟节点类型不一致');
}
}
private borrowFromRight(parent: InternalNode, at: number): void {
const node = parent.children[at];
const right = parent.children[at + 1];
if (node.leaf && right.leaf) {
node.keys.push(right.keys.shift()!);
node.values.push(right.values.shift()!);
parent.keys[at] = right.keys[0];
} else if (!node.leaf && !right.leaf) {
node.keys.push(parent.keys[at]);
node.children.push(right.children.shift()!);
parent.keys[at] = right.keys.shift()!;
} else {
throw new Error('树结构损坏：兄弟节点类型不一致');
}
}
内部节点借用同理，只是移动的是“key + 子页指针”，父页分界值也要跟着换。
6.2 合并
两边兄弟都只有最少 key 时，借不到，只能合并：把右叶的 key/value 追加到左叶，左叶的 next 指向右叶的 next；父页里对应的分界值和子页指针一起删掉。
/** 合并 parent.keys[at] 左右两个孩子，并把分隔 key 摘掉。 */
private merge(parent: InternalNode, at: number): void {
const left = parent.children[at];
const right = parent.children[at + 1];
if (left.leaf && right.leaf) {
left.keys.push(...right.keys);
left.values.push(...right.values);
left.next = right.next;
} else if (!left.leaf && !right.leaf) {
left.keys.push(parent.keys[at], ...right.keys);
left.children.push(...right.children);
} else {
throw new Error('树结构损坏：兄弟节点类型不一致');
}
parent.keys.splice(at, 1);
parent.children.splice(at + 1, 1);
}
父页少了一个 key，可能也下溢，于是修复继续向上——这就是 fixUnderflow 的循环。内部节点合并还要把父页的分界值下沉到合并后的节点里。
6.3 根收缩
如果合并一路合并到根，根可能变成 0 个 key、1 个孩子。这时把唯一的孩子提上来当新根，树高减 1。这是 B+ 树变矮的唯一方式。
七、范围查询：叶子链表就是答案
先按 low 下降找到叶子，在叶子里二分到第一个大于等于 low 的位置；然后沿着 next 一路往后扫，直到 key 大于 high。
// ---------------------------------------------------------- 范围查询
/** 范围查询：先找到 low 所在的叶子，再沿 next 指针往后扫。 */
range(low: number, high: number): Array<[number, string]> {
const out: Array<[number, string]> = [];
if (!this.root) return out;
let leaf: LeafNode | null = this.findLeaf(low, []);
let at = this.lowerBound(leaf.keys, low);
while (leaf) {
for (; at < leaf.keys.length; at++) {
if (leaf.keys[at] > high) return out;
out.push([leaf.keys[at], leaf.values[at]]);
}
leaf = leaf.next;
at = 0;
}
return out;
}
代价是：height 次下降（第 height 次已经读到起点叶子），再加上后面扫过的叶子页数；如果一共命中 k 个叶子，页读是 height + k − 1。因为叶子是顺序链表，范围扫描是顺序 I/O。点查再快也替代不了这一点，所以 B+ 树能同时覆盖 OLTP 点查和范围扫描。
八、把它跑起来：不变量 + 随机对拍
只靠“看起来对”不够。B+ 树必须始终满足：
- 每个节点 key 有序，且不超过
maxKeys； - 非根节点不少于
minKeys； - 内部节点
children.length === keys.length + 1； - 所有叶子在同一层，叶子链表顺序正确且与 key 顺序一致；
- 叶子里的 key 总数等于
size。
两个调试辅助方法：
// ---------------------------------------------------------- 调试辅助
get height(): number {
let h = 0;
let node: Node | null = this.root;
while (node) {
h++;
node = node.leaf ? null : node.children[0];
}
return h;
}
/** 按顺序遍历所有叶子，方便测试与调试。 */
*leaves(): Generator<LeafNode> {
if (!this.root) return;
let node: Node = this.root;
while (!node.leaf) node = node.children[0];
let leaf: LeafNode | null = node as LeafNode; // 循环结束时 node 一定是叶子
while (leaf) {
yield leaf;
leaf = leaf.next;
}
}
}
测试用最笨但最可靠的办法：拿一个 Map 当标准答案，随机做 2 万次操作（插入、删除合计），定期检查全部不变量和全量查找；完整脚本还会对随机区间做范围查询对拍。
const t = new BPlusTree(4);
const model = new Map();
let seed = 20261018;
const rnd = () => ((seed = (seed * 1664525 + 1013904223) >>> 0) / 2 ** 32);
for (let step = 0; step < 20000; step++) {
const key = Math.floor(rnd() * 300);
if (rnd() < 0.62) {
t.insert(key, `v${step}`);
model.set(key, `v${step}`);
} else if (t.delete(key) !== model.delete(key)) {
throw new Error(`delete(${key}) 与标准答案不一致`);
}
if (step % 250 === 0) {
check(t); // 逐条检查上面的不变量，见 test.mjs
for (const [k, v] of model) {
if (t.search(k) !== v) throw new Error(`search(${k}) 不一致`);
}
}
}
console.log('2 万次随机操作对拍通过');
关键输出（节选）：
插入 1..10 后：
内部 [5]
c0: 内部 [3]
c0: 叶 [1,2]
c1: 叶 [3,4]
c1: 内部 [7,9]
c0: 叶 [5,6]
c1: 叶 [7,8]
c2: 叶 [9,10]
range(4,9) = [[4,"v4"],[5,"v5"],[6,"v6"],[7,"v7"],[8,"v8"],[9,"v9"]]
…（中间删除过程略）…
随机 20000 次插入/删除对拍通过，最终 size = 183 height = 6
这棵树和第二节的全景图、第六节的删除图是同一棵。你可以用文末的完整代码复现每一步。
九、代价：B+ 树不是免费的
| 结构 | 点查 | 范围查询 | 顺序写 | 典型场景 |
|---|---|---|---|---|
| 哈希表 | O(1) | 不支持 | 差 | 等值缓存 |
| 红黑树 | O(log n) 次内存访问 | 支持 | 一般 | 内存有序结构 |
| B+ 树 | 约 3 次页 I/O | 叶子链表顺序扫 | 好 | 磁盘索引 |
| LSM 树 | 内存 + 多层查找 | 支持 | 极好 | 写多读少 |
B+ 树的代价也很明确：
- 写放大：一次分裂要改父页，最坏一路改到根；随机插入还会造成页分裂和空间碎片。
- 空间开销：非根节点按孩子数至少半满；真实数据库的 order 很大，页内平均填充率通常约 2/3 到 3/4（order=4 这种教学树会更低）。
- 点查不如哈希：哈希一次定位；但哈希不支持范围、排序和最左前缀。
所以选不选 B+ 树，本质是问一句：你的查询需不需要顺序？ 需要范围、排序、前缀匹配，B+ 树几乎总是默认答案；只要单点 KV，哈希可能更合适。
十、速查：一张表记住所有操作
| 操作 | 路径 | 触发条件 | 修复动作 |
|---|---|---|---|
| 点查 | 根 → 叶 | — | — |
| 插入 | 根 → 叶 | 节点 key 数 > maxKeys |
分裂；叶子复制右叶最小 key，内部页搬中间 key；根裂则树高 +1 |
| 删除 | 根 → 叶 | 节点 key 数 < minKeys |
先借，借不到合并；根空则树高 −1 |
| 范围 | 根 → 叶 → next |
— | — |
最后三句话：
- 内部页是目录，叶子页是数据；目录只负责把路指对。
- 所有操作都从“找到叶子”开始：插入向上裂，删除向上修。
- 树高就是点查的页读次数。让节点变胖、让 key 变短，是数据库索引优化的第一性原理。
完整代码与测试脚本（打包下载）：
- bplus-tree-principles-code.zip：包含
bplus.ts（289 行）与test.mjs；解压后运行node --experimental-strip-types test.mjs。