实验 03：B+ 树索引 —— 从一次分裂看懂数据库为什么"矮而胖"

> 手工实现一棵 B+ 树，亲眼看到节点分裂、叶链形成，然后测出它比全表扫描快多少，最后用它做一次等深分区。

一、实验目标

完成本实验后，你应当能够：

1. 说清楚 B+ 树的三个组成部分：根（root）、内部节点（inner node）、叶子节点（leaf node），以及它们的分工。
2. 手工模拟一次插入导致节点分裂（split）的完整过程，并能画出分裂前后的结构。
3. 解释叶链（leaf chain，叶子之间的横向指针）存在的理由，以及它如何让范围查询只需一次树下降。
4. 用代码统计树高、节点数、叶节点数，解释为什么数据量从 1 万涨到 20 万，树高只从 3 变成 4。
5. 对比点查（point query）在三种方案下的代价：B+ 树、有序数组二分查找、全表顺序扫描。
6. 利用 B+ 树内部结构的分界点做等深分区（equi-depth partitioning），理解它和并行查询的关系。

二、预备知识

2.1 为什么数据库不用二叉搜索树

数据库的数据住在磁盘上，读数据的最小单位是页（page，通常 4 KiB 或 8 KiB）。一次页 I/O 大约能买来上百个键值，但寻道开销不会因为只用一个键而变小。

二叉搜索树一个节点放一个键，查找一个键要下降 log₂N 层，也就是 log₂N 次页访问。N = 20 万时，log₂N ≈ 17.6，要读 18 次页。

把每个节点塞满一个页能放得下的所有键，就是多路平衡树（multi-way balanced tree）。这种树"矮而胖"，一次下降能排除掉成百上千个键。B+ 树（B-plus tree）是其中的主流结构，原始方案出自 Bayer 与 McCreight 1972 年的工作。PostgreSQL 官方文档把它的 B-tree 索引描述为一种可以处理可排序数据的多路平衡树结构，叶页里的条目指向表中的行。

2.2 术语表

| 术语 | 英文 | 含义 |
| --- | --- | --- |
| 扇出 | fan-out | 一个节点最多能有多少个孩子。等于分隔键个数 + 1 |
| 容量 | capacity | 一个节点最多存放的键个数。本实验用小容量便于观察 |
| 占用率 / 填充率 | fill factor | 实际存放的键数 ÷ 容量 |
| 分隔键 | separator / pivot key | 内部节点中用于划分子树范围的键，它本身不携带数据行 |
| 分裂 | split | 节点装满后再插入，把节点一分为二、并把分隔键上提到父节点 |
| 叶链 | leaf chain / sibling pointer | 叶子之间沿 `next` 指针串成的横向链（本实现是单向链表；真实数据库常用双向） |
| 范围扫描 | range scan | 找出区间 [lo, hi] 内所有键：下降到起始叶，再沿叶链向右走 |
| 等深分区 | equi-depth partitioning | 把数据切成若干份，使每份记录数尽量相等 |

2.3 B+ 树长什么样

```
┌───────────────────────┐
│ root（内部节点） │
│ 分隔键: [ 32 ] │ ← 只放分隔键 + 孩子指针
└───────┬───────┬───────┘
┌───────────┘ └───────────┐
▼ ▼
┌────────────────┐ ┌────────────────┐
│ inner [13,21] │ │ inner [38,43] │
└──┬────┬────┬───┘ └──┬────┬────┬───┘
┌───┘ │ └───┐ ┌───┘ │ └───┐
▼ ▼ ▼ ▼ ▼ ▼
┌──────┐ ┌──────┐ ┌──────┐ ┌──────┐ ┌──────┐ ┌──────┐
│ leaf │→│ leaf │→│ leaf │→ │ leaf │→│ leaf │→│ leaf │→ ∅
│3 8 9 │ │14 18 │ │21 22 │ │31 34 │ │39 41 │ │44 46 │
│ 11 │ │20 │ │25 31 │ │36 │ │ │ │49 │
└──────┘ └──────┘ └──────┘ └──────┘ └──────┘ └──────┘
└──────────── 横向指针（next）贯穿整个叶层 ────────────┘
```

图 1：典型 B+ 树。所有真正的数据（键值到行号的映射）都在叶层，内部节点只是路标。

2.4 一次分裂的全过程

设叶容量 = 4。当前叶子装了 `[3, 8, 9, 11]`，再插 `7`：

```
步骤 1：先按序插入，允许暂时溢出 步骤 2：从中点切开（mid = 5//2 = 2）
┌───────────────┐ ┌──────────┐ ┌──────────┐
│ 3 7 8 9 11 │ ← 5 个 > 4 │ 3 7 │ │ 8 9 11 │
└───────────────┘ └──────────┘ └──────────┘
左半 右半
步骤 3：把中间的键 8 作为分隔键上提给父节点
┌──────────────┐
│ parent │
│ keys [ 8 ] │
└──┬────────┬──┘
▼ ▼
┌───────┐ ┌────────┐
│ 3 7 │ │ 8 9 11 │ ← 新右节点的首个键 = 上提的分隔键
└───────┘ └────────┘
步骤 4：重接叶链，让两个新叶子和左右邻居连起来（这一步不能漏，否则 range scan 会断）

left.prev ──► left ──► right ──► right.next
```

图 2：叶分裂四步。注意本实现中"上提的键在右半保留"（B+ 树的常见做法之一），所以右半的第一个键恰好等于父节点的分隔键。

内部节点的分裂同理，差别在于：被上提的键本身会从两个子树中移除（`mid` 位置那个键只留着当分隔键，不再出现在下一层）。代码里 `Inner.split` 用的是 `self.keys[mid+1:]`，就是这个原因。

2.5 树高公式

设：

• `N` = 索引中的键总数

• `L` = 一个叶节点最多能放的键数（叶容量）

• `F` = 内部节点的平均扇出

• `P` = 叶节点个数

则：

```
P ≈ N / L （按满载估算）
h ≈ 1 + ⌈log_F P⌉ （h 为层数：含内部节点层和叶层）
```

常见的写法 `h ≈ log_F(N)` 忽略了两件事：叶容量 `L` 的存在（不是每个键一层），以及实际装填率往往不满 100%。本实验后面会用实测数据验证这一点。

真实数据库里还有装填因子的概念：PostgreSQL 的 B-tree 索引默认 `fillfactor = 90`（可调范围 10–100），意思是建索引时每个页只填到 90%，剩余空间留给后续插入，从而减少分裂；代价是页数会多约 11%。本实验的实现采用"溢出后再分裂"的做法，装填率会落在 50% 附近，后面实测会看到这个数字。

三、实验原理

3.1 为什么是 B+ 而不是 B

B 树的每一个节点都能装数据：查到内部节点上的键就命中，不必走到叶层。听起来更快，但在数据库里有几个坏处：

| 对比项 | B 树 | B+ 树 |
| --- | --- | --- |
| 内部节点是否存数据 | 存 | 只存分隔键和指针 |
| 单个内部节点的扇出 | 小（键 + 数据挤占空间） | 大（只放键和指针，更省空间） |
| 树高 | 相对高 | 相对矮 |
| 范围查询 | 需要中序遍历来回上下走，随机 I/O | 一次下降到起点，之后沿叶链顺序扫 |
| 全索引扫描 | 中序遍历 | 直接从头走叶链 |

数据库大量场景是范围扫描 (`BETWEEN`、排序、`GROUP BY` 走索引)，因此 B+ 树的叶链优势决定了它是主流。

3.2 点查代价

一次点查的代价由两部分组成：

```
cost(point query) ≈ h 次节点访问（页 I/O）
+ 每个节点内部的二分查找 log₂(slot) 次比较
```

`h` 是几百几千字节级别的内存比较所换来的页访问次数，因此树的高度直接决定了慢的那部分开销有多大。这也是为什么"树高一律很小"这件事如此关键。

3.3 用 B+ 树做等深分区

等深分区的要求是：把值域切成若干段，每段装到的记录数接近相等。做法并不复杂：

1. 用一小部分样本数据建一棵"矮而胖"的树（内部节点少、叶子大）；
2. 把整批数据流过这棵树，落到叶子上，但叶子不存数据，只记数（这就是下面代码里的 `CountingLeaf`）；
3. 每个叶子的计数值就是一段桶的记录数，叶子之间的边界自然就是分区边界。

由于样本是从同一分布里采的，用 batch 数据计数后，各桶的记录数会比较均匀。这个性质对并行查询、直方图统计、数据倾斜检测都很有用。


图 3：依次插入 1…20 后的真实结果（叶容量 4，内节点容量 3）。底部绿色曲线是叶链。


图 4：N 从 100 增长到 200,000，树高只从 2 变到 4；节点数近似线性增长，且绝大多数是叶节点。


图 5：同一次点查，三种方案的检查单元数分布（N = 200,000，随机 2000 次查询）。

四、实验环境与准备

4.1 软件要求

• Python 3.10 及以上（本指导书的实测在 CPython 3.13 与 3.12 + Windows 上完成）

• 必装：`numpy`、`matplotlib`

• 选装：`graphviz`（Python 包 + 系统 Graphviz 可执行文件），用于把树渲染成图；不装也能完成全部实验，`show()` 那一步会跳过

```bash
python -c "import numpy, matplotlib; print('基础环境 OK')"
pip install numpy matplotlib # 缺哪个装哪个
pip install graphviz # 可选：渲染树形图
```

4.2 目录约定

本指导书位于：

```
…/教学产出/03-实验指导书/实验03-B+树.md
```

图件位于：

```
…/教学产出/figures/
```

文中用相对路径 `../figures/fig_btree_structure.png` 引用图件。

4.3 两种学法的分工

本实验的代码分两类：

• **A 类（必做，自包含）**：只用标准库 `bisect`，任何装了 Python 的机器都能跑。用来观察结构、数节点、量代价。

• **B 类（选做，调用 ExplainDB 教学库）**：直接调用课程自带的 `system.indexes.btree.BPlusTree`，验证同一套行为的工业写法，并用 graphviz 渲染。

B 类代码需要在仓库根目录下运行，并先把仓库根加入 `sys.path`：

```python
import sys, pathlib

for _p in (pathlib.Path.cwd(), *pathlib.Path.cwd().parents):
if (_p / "system").is_dir():
if str(_p) not in sys.path:
sys.path.insert(0, str(_p))
break
```

五、实验步骤

步骤 1：实现一个可观察的 B+ 树（A 类）

把下面这段代码保存为 `btree_lab.py`。它比真实的数据库代码简化很多（不支持删除、不支持重复键合并），但完整保留了 B+ 树的核心行为：溢出后分裂、分隔键上提、叶链维护、范围扫描。

```python
import bisect

class BPNode:
"""一个节点。leaf=True 时是叶子，否则是内部节点。"""

__slots__ = ("leaf", "keys", "vals", "children", "next")

def __init__(self, leaf=True):
self.leaf = leaf
self.keys = [] # 叶子：键；内部：分隔键
self.vals = [] # 叶子：值（这里放行号）
self.children = [] # 内部：子节点
self.next = None # 叶子：叶链的下一个

class BPlusTree:
"""教学用 B+ 树。leaf_cap = 叶子最大键数，inner_cap = 内部节点最大分隔键数。"""

def __init__(self, leaf_cap=4, inner_cap=3):
self.leaf_cap = leaf_cap
self.inner_cap = inner_cap
self.root = BPNode(leaf=True)
self.split_count = 0

# ---------- 插入 ----------
def insert(self, key, val):
res = self._insert(self.root, key, val)
if res is not None: # 根也分裂了 → 树长高一层
pivot, right = res
new_root = BPNode(leaf=False)
new_root.keys = [pivot]
new_root.children = [self.root, right]
self.root = new_root
# 注意：这里不增加 split_count。根被替换是"多了一层"，
# 真正发生分裂的是下面那个叶子，已在 _split_leaf 里计过。

def _insert(self, node, key, val):
if node.leaf:
i = bisect.bisect_left(node.keys, key)
node.keys.insert(i, key)
node.vals.insert(i, val)
if len(node.keys) > self.leaf_cap:
return self._split_leaf(node)
return None
i = bisect.bisect_right(node.keys, key)
res = self._insert(node.children[i], key, val)
if res is None:
return None
pivot, right = res
node.keys.insert(i, pivot)
node.children.insert(i + 1, right)
if len(node.keys) > self.inner_cap:
return self._split_inner(node)
return None

def _split_leaf(self, node):
mid = len(node.keys) // 2
right = BPNode(leaf=True)
right.keys, right.vals = node.keys[mid:], node.vals[mid:]
node.keys, node.vals = node.keys[:mid], node.vals[:mid]
right.next = node.next # 重接叶链
node.next = right
self.split_count += 1
return right.keys[0], right # 上提新右节点的最小键作为分隔键

def _split_inner(self, node):
mid = len(node.keys) // 2
up = node.keys[mid] # 这个键上提，本身从下层消失
right = BPNode(leaf=False)
right.keys = node.keys[mid + 1:]
right.children = node.children[mid + 1:]
node.keys = node.keys[:mid]
node.children = node.children[:mid + 1]
self.split_count += 1
return up, right

# ---------- 查询 ----------
def search(self, key):
"""点查：自顶向下降到叶，再在叶内二分。"""
node = self.root
while not node.leaf:
i = bisect.bisect_right(node.keys, key)
node = node.children[i]
i = bisect.bisect_left(node.keys, key)
out = []
while i < len(node.keys) and node.keys[i] == key:
out.append(node.vals[i])
i += 1
return out

def range_search(self, lo, hi):
"""范围查：下降到起点叶，之后只沿叶链向右，不再回到树上。"""
node = self.root
while not node.leaf:
i = bisect.bisect_right(node.keys, lo)
node = node.children[i]
out = []
while node is not None:
for k, v in zip(node.keys, node.vals):
if k > hi:
return out
if k >= lo:
out.append(v)
node = node.next
return out

# ---------- 统计与检查 ----------
def height(self):
h, node = 1, self.root
while not node.leaf:
h += 1
node = node.children[0]
return h

def node_count(self):
cnt, stack = 0, [self.root]
while stack:
n = stack.pop()
cnt += 1
stack.extend(n.children)
return cnt

def leaf_count(self):
node, cnt = self.root, 0
while not node.leaf:
node = node.children[0]
while node is not None:
cnt += 1
node = node.next
return cnt

def check(self):
"""一致性检查：沿叶链走一遍，键必须全局有序，总数必须等于插入数。"""
node = self.root
while not node.leaf:
node = node.children[0]
prev, total = None, 0
while node is not None:
assert node.keys == sorted(node.keys), "叶内键未排序"
if prev is not None:
assert prev <= node.keys[0], "叶链顺序错误"
prev = node.keys[-1]
total += len(node.keys)
node = node.next
return total

def levels(self):
"""层序返回每一层的节点列表，levels[0] 是根，levels[-1] 是叶层。"""
levels, cur = [], [self.root]
while cur:
levels.append(cur)
nxt = []
for n in cur:
nxt.extend(n.children)
cur = nxt
return levels

def dump(self):
"""把树按层打印出来，同时用缩进标出叶子键与内部节点分隔键。"""
for depth, level in enumerate(self.levels()):
kind = "leaf " if level[0].leaf else "inner "
cells = ["[" + " ".join(map(str, n.keys)) + "]" for n in level]
print(f" level {depth} ({kind}, {len(level)} 个): " + " ".join(cells))
```

步骤 2：观察分裂（核心步骤）

用小容量（叶容量 4、内部容量 3）依次插入 1…20，每插若干个就打印一次结构。这是本实验最关键的一步，请对着输出图手动验证每一步。

```python
from btree_lab import BPlusTree

t = BPlusTree(leaf_cap=4, inner_cap=3)
watch = {1, 2, 3, 4, 5, 6, 8, 10, 12, 16, 20}
for k in range(1, 21):
t.insert(k, f"row{k}")
if k in watch:
print(f"--- 插入 {k} 之后：树高={t.height()}，"
f"节点={t.node_count()}，叶={t.leaf_count()}，累计分裂={t.split_count}")
t.dump()
print(f" 叶链全局有序检查：check()={t.check()}")
```

运行后你会看到的关键转折点：

• 插到第 4 个时，树还是孤零零一个叶节点；

• 插到第 5 个时，根叶子装不下 5 个键，发生第一次分裂，树从 1 层变成 2 层；

• 再往后，每当某个内部节点的分隔键数超过 3，它自己也会分裂，树继续长高。

把这一轮跑完，记录最后一行数据。参考实测（升序插入 1…20，叶容量 4，内节点容量 3）：

| 指标 | 实测值 |
| --- | --- |
| 树高 | 3 |
| 节点总数 | 13 |
| 叶节点数 | 9 |
| 内部节点数 | 4 |

步骤 3：插入顺序会影响什么

顺序插入会让节点分裂后只装一半，装填率偏低。换成降序或随机顺序再试一次：

```python
import random
from btree_lab import BPlusTree

keys = list(range(1, 21))

for name, order in [
("升序 ", keys),
("降序 ", list(reversed(keys))),
("随机 ", random.Random(1).sample(keys, len(keys))),
]:
t = BPlusTree(leaf_cap=4, inner_cap=3)
for k in order:
t.insert(k, f"row{k}")
print(f"{name} 树高={t.height()} 节点={t.node_count():2d} 叶={t.leaf_count():2d} "
f"分裂={t.split_count:2d} 装填率={20 / t.leaf_count() / 4 * 100:5.1f}%")
```

三种顺序都能通过 `check()`，说明结构依然正确。差别体现在节点数和装填率上——这正是真实数据库关心"插入顺序 / 建索引顺序"的原因。把结果填到第六节的表中。

步骤 4：树高几乎不随数据量增长

换成接近真实页容量的配置：叶容量 64、内部容量 63，跑 5 种数据量。

```python
import time
from btree_lab import BPlusTree

for n in (100, 2_000, 10_000, 50_000, 200_000):
t = BPlusTree(leaf_cap=64, inner_cap=63)
t0 = time.perf_counter()
for k in range(n):
t.insert(k, k)
el = (time.perf_counter() - t0) * 1000
leaves, nodes = t.leaf_count(), t.node_count()
print(f"N={n:>7d} 树高={t.height()} 节点={nodes:>5d} 叶={leaves:>5d} "
f"内部={nodes - leaves:>4d} 叶装填率={n / leaves / 64 * 100:5.1f}% "
f"构建={el:7.1f} ms")
```

参考实测（同一份代码，CPython + Windows）：

| N | 树高 | 节点总数 | 叶节点数 | 叶平均装填率 |
| --- | --- | --- | --- | --- |
| 100 | 2 | 4 | 3 | 52.1% |
| 2,000 | 2 | 63 | 62 | 50.4% |
| 10,000 | 3 | 322 | 312 | 50.1% |
| 50,000 | 3 | 1,610 | 1,562 | 50.0% |
| 200,000 | 4 | 6,444 | 6,249 | 50.0% |

注意最后一列：数据量越大，装填率越稳定地落在 50.0% 附近。这是因为"溢出后从正中切开"这种策略，长期看每个叶子平均装一半。真实数据库不走这条路——PostgreSQL 的做法是建索引时按 fillfactor 90% 装填，更新时优先复用页内空闲空间，把分裂尽量往后推。

步骤 5：点查代价的三种口径

现在把 B+ 树点查和另外两种方案放在一起量化。这一步要明确口径，否则数字没法比较：

• **B+ 树**：访问的节点数（含叶）+ 叶内二分查找的上界 ⌈log₂(len(keys)+1)⌉

• **有序数组二分**：⌈log₂ N⌉（最坏情况上界），以及随机点查的实际平均步数

• **全表顺序扫描**：从头找到为止，平均 N/2 行

```python
import bisect
import math
import numpy as np
from btree_lab import BPlusTree

n = 200_000
t = BPlusTree(leaf_cap=64, inner_cap=63)
for k in range(n):
t.insert(k, k)

rng = np.random.default_rng(7)
probes = rng.integers(0, n, 2000)

def btree_units(key):
"""自顶向下：每下降一层记 1，最后补上叶内二分上界。"""
node, cnt = t.root, 0
while not node.leaf:
cnt += 1
i = bisect.bisect_right(node.keys, key)
node = node.children[i]
cnt += 1 # 叶节点本身
cnt += math.ceil(math.log2(len(node.keys) + 1)) # 叶内二分
return cnt

def real_binary(key):
"""真的做一次二分，数比较次数。"""
lo, hi, c = 0, n - 1, 0
while lo <= hi:
mid = (lo + hi) // 2
c += 1
if mid == key:
return c
if mid < key:
lo = mid + 1
else:
hi = mid - 1
return c

b_units = [btree_units(int(k)) for k in probes]
bin_units = [real_binary(int(k)) for k in probes]
lin_units = [int(k) + 1 for k in probes]

print(f"B+ 树点查 平均 {np.mean(b_units):>10.1f} 个单元")
print(f"有序数组二分 平均 {np.mean(bin_units):>10.1f} 次比较"
f"（最坏上界 ⌈log₂N⌉ = {math.ceil(math.log2(n))}）")
print(f"全表顺序扫描 平均 {np.mean(lin_units):>10.0f} 行（理论期望 N/2 = {n // 2}）")
print(f"相对全表扫描的加速比：{np.mean(lin_units) / np.mean(b_units):.0f}×")
```

参考实测（N = 200,000，随机 2000 次查询）：

| 方案 | 平均检查单元数 | 相对全表扫描 |
| --- | --- | --- |
| B+ 树点查 | 10.0 | 约 10,000× |
| 有序数组二分 | 约 17（实测 16.6，上界 18） | 约 6,000× |
| 全表顺序扫描 | 100,000 | 1× |

二分查找的比较次数比 B+ 树少不了多少（对数 vs 对数），但真正的差别在别处：数组二分要求数据连续且有序、插入一行是 O(N) 的移动成本；而 B+ 树点查时的 10 个单元里包含的是"页访问"，这是可以在缓冲池里摊销的。这里量出来的"10000×"、"6000×"说的是比较操作的规模差异，真实 I/O 差距还要结合缓冲池命中率来看。

步骤 6：范围扫描只下降一次

```python
import time
from btree_lab import BPlusTree

t = BPlusTree(leaf_cap=64, inner_cap=63)
for k in range(1, 20_001):
t.insert(k, f"row{k}")

t0 = time.perf_counter()
hits = t.range_search(5_000, 5_999) # 连续 1000 个键
t1 = time.perf_counter()
print(f"范围查[5000, 5999] 命中 {len(hits)} 条，耗时 {(t1 - t0) * 1000:.3f} ms")
print("前 5 条:", hits[:5])

t0 = time.perf_counter()
single = [t.search(k) for k in range(5_000, 6_000)] # 退化成 1000 次点查
t1 = time.perf_counter()
print(f"同样 1000 个键做 1000 次点查，耗时 {(t1 - t0) * 1000:.3f} ms")
```

范围扫描只做一次树下降，之后是纯顺序遍历；退化成一串点查则每次都要从根重新走一遍。两者的差距体现的就是叶链的价值。若你还想看叶链是否完好，调用 `t.check()` 即可——它会沿链走完整个索引并统计总数。

步骤 7（选做）：调用课程自带的 B+ 树实现

ExplainDB 教学库里有一份完整的实现，语义与步骤 1 的代码一致，多了 `get_all_in_range`、graphviz 渲染和一致性断言。

```python
import sys, pathlib

for _p in (pathlib.Path.cwd(), *pathlib.Path.cwd().parents):
if (_p / "system").is_dir():
if str(_p) not in sys.path:
sys.path.insert(0, str(_p))
break

from system.indexes.btree import BPlusTree as DBMSBPlusTree

tree = DBMSBPlusTree(inner_capacity=3, leaf_capacity=4)
for k in range(1, 21):
tree.put(k, f"row{k}")

print(tree) # 打印容量配置
print("size =", tree.size()) # 叶层键总数
print("get(7) =", list(tree.get(7))) # 点查
print("range [5,12] =", list(tree.get_all_in_range(5, 12))) # 范围查
tree.consistency_check() # 断言：键有序、叶链指针成对
print("一致性检查通过")

需要安装 graphviz 包与系统 Graphviz 可执行文件

try:
tree.show()
except Exception as e:
print("图形渲染跳过：", e)
```

步骤 8（选做）：等深分区

思路在 3.3 节说过。ExplainDB 里提供了 `CountingLeaf`来代替普通叶子：它不存数据，只统计 put 被调用的次数。

```python
import sys, pathlib
for _p in (pathlib.Path.cwd(), *pathlib.Path.cwd().parents):
if (_p / "system").is_dir():
sys.path.insert(0, str(_p))
break

import numpy as np
from system.indexes.btree import BPlusTree as DBMSBPlusTree

data = np.fromfile("notebooks/latitude_longitude.bin", dtype=np.float32).reshape(-1, 2)[:, 0]
data = np.array(sorted(set(data.tolist()))) # 本实现暂不支持重复键
rng = np.random.default_rng(0)
sample = rng.choice(data, size=10_000, replace=False)

tree = DBMSBPlusTree(inner_capacity=5, leaf_capacity=2000)
for v in sample:
tree.put(float(v), float(v))

tree.convert_to_counting_leaf_tree() # 叶层换成只计数的叶子
for v in data:
tree.put(float(v), float(v)) # 全量数据灌进去，叶子只在计数

tree.show() # 每个叶子里显示落进来的记录数
```

每个叶子就是一个桶。把它们的计数读出来画直方图，你会得到一份近似等深的分区；相邻的边界键值就是分区的切分点。

六、观测记录表

把你自己机器上跑出来的数字填进去。"推定值"列是可以用公式从你填的数算出来的。

**表 6-1：小容量下的结构（叶容量 4，内节点容量 3）**

| 插入序列 | 键数 N | 树高 h | 节点总数 | 叶节点数 | 分裂次数 | 平均叶装填率 = N ÷ 叶数 ÷ 4 |
| --- | --- | --- | --- | --- | --- | --- |
| 升序 1…20 | 20 | | | | | |
| 降序 20…1 | 20 | | | | | |
| 随机排列 | 20 | | | | | |
| 升序 1…40 | 40 | | | | | |

**表 6-2：大容量下随数据量增长（叶容量 64，内节点容量 63）**

| N | 树高 h | 节点总数 | 叶节点数 | 内部节点数 = 总数 − 叶数 | 平均叶装填率 | 构建耗时 (ms) |
| --- | --- | --- | --- | --- | --- | --- |
| 100 | | | | | | |
| 2,000 | | | | | | |
| 10,000 | | | | | | |
| 50,000 | | | | | | |
| 200,000 | | | | | | |

**表 6-3：点查代价（建议 N = 200,000，随机 2000 次）**

| 方案 | 平均检查单元数（本机实测） | 相对全表扫描加速比 |
| --- | --- | --- |
| B+ 树点查 | | |
| 有序数组二分（实际平均） | | |
| 有序数组二分（⌈log₂N⌉ 上界） | | |
| 全表顺序扫描 | | 1× |

**参考实测（供核对，升序插入，CPython + Windows）**

| 表 | 条目 | 参考值 |
| --- | --- | --- |
| 6-1 | 升序 1…20 | 树高 3 / 节点 13 / 叶 9 / 分裂 10 次 |
| 6-1 | 降序 20…1 | 树高 3 / 节点 11 / 叶 7 / 分裂 8 次 |
| 6-1 | 随机排列（seed=1） | 树高 3 / 节点 10 / 叶 7 / 分裂 7 次 |
| 6-2 | N = 10,000 | 树高 3 / 节点 322 / 叶 312 / 内部 10 / 装填率 50.1% |
| 6-2 | N = 200,000 | 树高 4 / 节点 6,444 / 叶 6,249 / 内部 195 / 装填率 50.0% |
| 6-3 | B+ 树点查 | 10.0 |
| 6-3 | 全表顺序扫描 | 100,000 |

七、思考题

1. 叶容量 4、内部容量 3，升序插入 1…20 之后树高是多少？为什么第 5 个键是第一次分裂的触发点，而不是第 4 个之后的某一次？
2. B+ 树的分裂是"溢出后从正中切开"。假如换成"发现快满了就提前分裂"（类似 PostgreSQL 的 fillfactor 思路），节点数、树高、后续插入的分裂次数会怎么变？
3. 表 6-2 里 N 从 10,000 涨到 50,000（涨了 5 倍），树高没有变化；从 50,000 涨到 200,000（涨了 4 倍），树高加了 1。用第二节的公式解释这种"跳变"。
4. 为什么 B+ 树的范围查询不会因为叶子分布在树的不同分支而反复回到根节点？如果删除了叶链指针，范围查询要付出什么代价？
5. 内部节点为什么要"弃卒保帅"地不存数据行？如果非要在内部节点也存数据（回到 B 树），扇出会怎么变，树高会怎么变？
6. 参考实测里 N = 200,000 时点查平均检查 10.0 个单元，其中树高为 4。这 10.0 是怎么拆出来的？请用代码里的口径做一次拆分。
7. 等深分区为什么可以用"抽样建树 + 全量计数"两步完成，而不是排完整序再切成 k 段？它省掉了什么，代价又是什么？
8. 一棵叶容量为 `L`、内部容量为 `F−1` 的 B+ 树，若要求树高不超过 3，最多能索引多少个键？（分满载和实测 50% 装填两种情况分别给出表达式。）

八、思考题答案与解析

**1. 树高与首次分裂**

树高 = 3（层 0 根、层 1 内部、层 2 叶）。

第 5 个键触发分裂的原因很直接：叶容量是 4，插到第 4 个键时 `len(keys) == 4`，未超过容量，不分裂；插第 5 个键后 `len(keys) == 5 > 4`，判定溢出，`_split_leaf` 才被调用。代码里的判断条件是 `if len(node.keys) > self.leaf_cap`，所以"装满"本身不分裂，"溢出"才分裂。

**2. 提前分裂的后果**

把节点数、树高、分裂次数三件事分开看：

| 指标 | 溢出后分裂（本实验） | 提前分裂（预留空间） |
| --- | --- | --- |
| 短期节点数 | 少 | 多 |
| 树高 | 相同数量级，可能矮一层 | 相同数量级 |
| 后续插入触发分裂的频率 | 高（一次都塞不进就裂） | 低（有空位可直接放） |
| 长期平均装填率 | 约 50%（实测） | 接近设定值（如 90%） |

PostgreSQL 文档里给出的做法正是后者：B-tree 索引默认 `fillfactor = 90`，插入新键时可以复用页内预留的 10%，从而减少分裂引发的整体重组；代价是叶子页数比满载多约 11%（1/0.9 ≈ 1.111）。所以这是一个"一次性多占空间"换"后续少做结构变动"的取舍。

**3. 树高的跳变**

用 2.5 节的公式：

```
h ≈ 1 + ⌈log_F P⌉ ， P ≈ N / (L · 装填率)
```

代入 L = 64、装填率 ≈ 50%，得每叶平均装 32 个键：

• N = 10,000 → P ≈ 312 → h = 1 + ⌈log_F 312⌉。只要 F ≥ √312 ≈ 17.7，就得到 h = 3。

• N = 50,000 → P ≈ 1,562 → 只要 F ≥ √1562 ≈ 39.5，仍是 h = 3。

• N = 200,000 → P ≈ 6,249 → 要维持 h = 3，需要 F ≥ √6249 ≈ 79.1，而本实验扇出只有 64，做不到；于是走到 h = 4（要求 F ≥ ³√6249 ≈ 18.4）。

关键在于 `h` 是关于 `P` 的对数，且带向上取整：数据在一个数量级内变化时 `⌈·⌉` 常常不变，跨过某个 F 的幂次才 +1。这就是"跳变"。用 F 的实际量级（内部容量 63，也就是最多 64 个孩子）代入，各档都吻合。

**4. 叶链的意义**

叶链把整个叶层接成一条单向链表——本实现只维护 `next`，真实数据库通常做成双向，以支持从右往左的范围扫描。范围查询的流程是：下降到起始键所在的那个叶（一次 log 级查找），之后 `node = node.next` 一路向右。这期间完全不需要回到父节点。

若删掉叶链指针：

• 想找下一个叶，只能从根重新下降一次。范围查询的代价从 `h + k/L`（一次下降 + k/L 个叶的顺序扫）变成 `k · h`（每个叶都要从根走一遍），随机 I/O 数量直线上升。

• 全索引扫描也没法线性走，退化成中序遍历。

• `convert_to_counting_leaf_tree` 之后仍能计数，是因为 put 走的是树下降路径，与叶链无关；但等深分区需要按边界顺序输出桶，那时叶链就又重要了。

**5. B 树 vs B+ 树的扇出**

设一个节点的总空间为 S 字节，一个键 + 行指针占 `k + p` 字节，一个纯分隔键 + 孩子指针占 `k + c` 字节。通常 `p > c`（行指针要定位到堆表里的具体位置，可能带元组 ID；孩子指针只是页号）。

• B 树内部节点扇出 ≈ `S / (k + p)`

• B+ 树内部节点扇出 ≈ `S / (k + c)`

因为 `k + c < k + p`，B+ 树的 F 更大，树高 `1 + ⌈log_F P⌉` 就更矮，且在做范围扫描时还能顺着叶链走顺序 I/O。

**6. 10.0 这个数字怎么来的**

按步骤 5 的口径：

```
每次点查单元数 = （下降经过的内部节点数 = h − 1） + 1（叶节点） + ⌈log₂(叶内键数 + 1)⌉
```

N = 200,000 时 h = 4，所以前两项 = 3 + 1 = 4。实测平均是 10.0，因此叶内二分那一项平均贡献 `10.0 − 4 = 6.0`，对应 `⌈log₂(len+1)⌉ = 6`，即叶内键数在 (31, 63] 这个区间。回头核对：N = 200,000，叶数 6,249，平均每叶 32.0 个键，正好落在区间里，`⌈log₂ 33⌉ = 6`。完全自洽。

可以用下面这段代码把拆分显式打印出来：

```python
import bisect, math
from btree_lab import BPlusTree

n = 200_000
t = BPlusTree(leaf_cap=64, inner_cap=63)
for k in range(n):
t.insert(k, k)

for key in (0, 100_000, 199_999):
node, inner_hops = t.root, 0
while not node.leaf:
inner_hops += 1
node = node.children[bisect.bisect_right(node.keys, key)]
leaf_bins = math.ceil(math.log2(len(node.keys) + 1))
print(f"key={key:>7d} 内部节点={inner_hops} 叶={1} 叶内二分={leaf_bins} "
f"合计={inner_hops + 1 + leaf_bins} 该叶实有键={len(node.keys)}")
```

**7. 两步法做等深分区**

排序后再均分的做法需要先对 N 条记录做一次 O(N log N) 的外排序，才能得到 k−1 个切分点。两步法的做法是：

1. 抽 m 条样本（m ≪ N）建树，树的内部节点很小，常驻内存；
2. 全量数据只做一次 O(N log P) 的流式分发（P 是叶子个数），落到叶 visited 上计数。

省掉的是：全排序的磁盘 I/O 与归并开销。

代价有两点：一是切分点来自样本，样本偏差会导致桶深不均（数据量极度倾斜或分布未知时尤其明显）；二是要将树结构保持在内存里。若样本确实是同分布的随机采样，这一步的误差可以用样本量控制：`m` 越大，桶边界越接近真实分位数。

**8. 树高不超过 3 的容量**

树高 3 意味着 层0 根、层1 内部、层2 叶：

```
叶最多容纳键数 = L × 装填率
根的孩子数（即层 1 节点数）≤ F（内部容量 F−1 ⇒ 扇出 F）
层 1 每个节点的孩子数 ≤ F，它们就是叶子
⇒ 叶总数 P ≤ F²
⇒ 键总数 N ≤ F² · L · 装填率
```

• 满载情况（装填率 = 1）：`N_max = F² · L`

• 实际情况（装填率 ≈ 0.5，本实验实测值）：`N_max ≈ 0.5 · F² · L`

代入本实验的参数 L = 64、F = 64：`N_max = 64² × 64 = 262,144`（满载），实测装填率下则为 `≈ 131,072`。这也解释了为什么 N = 200,000 时装填率只有 50% 反而"被迫"长到第 4 层：131,072 < 200,000 < 262,144，按满载估算还能塞下，按实际装填率就塞不下了。

九、扩展任务（选做）

1. **实现随机数据下的 breakdown 统计**：遍历树的每一层，统计该层的节点数、每个节点的孩子数，算出每一层的实测平均扇出，与第三节的 F 做对比。观察"内部→内部"和"内部→叶"两档扇出是否一样。
2. **给叶子加批量加载**：实现 `bulkload(sorted_items)`，让 b+ 树按序直接铺满叶子、只保留偶尔余量，然后量一遍装填率，与逐条插入对比，验证 PostgreSQL 讨论 fillfactor 的语境。
3. **测量拼接开销**：在 `_split_leaf` 里加计数器，统计不同插入顺序下"每插入一个键平均引发多少次分裂"，把结果画成图。
4. **做一次真正的等深分区直方图**：从步骤 8 的 `CountingLeaf` 里读出各桶计数，画直方图，并计算"最深桶 / 最浅桶"的比值；把扇出从 4 调到 16（改 `children_per_inner_node` 或内部容量）后再测一遍，讨论样本量该怎么取。
5. **对比 open-source 实现**：在 PostgreSQL 里建一个百万行的表，用 `EXPLAIN (ANALYZE, BUFFERS)` 观察一次索引扫描访问了多少个缓冲区块，与本实验的单元数口径对比，讨论两者的差别。

十、常见错误与排查

| 现象 | 原因 | 处理 |
| --- | --- | --- |
| `check()` 抛出 `叶链顺序错误` | 分裂时忘记维护 `next` 指针（或维护顺序不对），导致叶链在分裂点断开或错序 | 检查 `_split_leaf`：`right.next = node.next` 必须在 `node.next = right` 之前执行——顺序反了，`node` 原来的整段后继就丢了 |
| 树长不高，插入 200,000 个键后 `height()` 还是 2 | 叶容量或内节点容量设得过大，或循环里插入的键重复成了同一个值 | 打印 `check()` 的返回值，确认是不是等于期望的键数；键重复时本实现的处理是覆盖而不是新增 |
| `search()` 返回空列表但键明明亮存在 | 内部节点路由用的是 `bisect_right`而你写成了 `bisect_left`（或反之），在下 NL-page 有相等分隔键时走去错误的孩子 | 保持 `_insert` 的下降与 `search` 的下降用同一个判定方式；本实验两处都用 `bisect_right` 做路由 |
| 范围扫描结果比预期的少 | `range_search` 在中间退出条件写成了 `k >= hi` 就 return，而不是 `k > hi` | `hi` 是闭区间上界，条件必须是 `if k > hi: return out`，且 `if k >= lo` 才开始收集 |
| 分裂后 `node_count()` 比 `leaf_count()` 小 | 统计逻辑反了：`node_count` 应该遍历 `children`，不适用于叶子 | 用 `stack.extend(n.children)` 遍历时，叶子没有孩子，自然返回空，不会出错；若手写了自己的三层循环，多半是遍历方向搞反了 |
| `dump()` 少打印最后一层 | 层序遍历的循环条件写成 `while cur` 之外又多写了一层 | `levels()` 里每轮先 `levels.append(cur)` 再算 `nxt`，不要提前 pop 掉叶层 |
| 使用课程 `system` 包时 `ModuleNotFoundError: No module named 'system'` | 未把仓库根目录加入 `sys.path` | 按 4.3 节的代码片段先插路径，或把脚本放在仓库根目录下运行 |
| `tree.show()` 无输出或报 `ExecutableNotFound` | 只装了 Python 的 `graphviz` 包，没装系统 Graphviz 程序 | 安装系统 Graphviz 并把 `bin` 目录加入 `PATH`；或直接跳过 `show()`，用 `dump()` 打印结构 |
| `system` 的 B+ 树 `put` 报 `TypeError: '<' not supported` | 插入了不可比较类型（比如 numpy 的 float32 和 Python float 混合） | 统一类型：`put(float(v), float(v))`；NumPy 标量与 Python 数混合比较在部分版本上会出问题 |
| 大 N 实验跑得很慢（几十秒） | 把 print 放进了插入循环，或每个键都伴随一次对象分配 | 插入循环里不要打印；N 超过 100 万时改用 `bulkload` 思路，或降到 20 万量级观察趋势即可 |