实验 03 · Notebook

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

为什么做这个实验

数据库为什么用"矮而胖"的多路平衡树，而不是教科书里那个优雅的二叉搜索树？本实验手工搭一棵 B+ 树，逐个键插入，亲眼看到**节点分裂、分隔键上提、叶链重接**这三件事是怎么发生的；再用同一棵树做一次等深分区，理解为什么"B+ 树的内部节点就是数据分布的一个模型"。

反直觉的地方有两处。第一，**数据量涨 2000 倍，树高只加 2**：实测 N 从 100 涨到 200 000，树高从 2 变成 4（叶容量 64、内节点容量 63）。因为树高是关于叶子数的对数，不是关于键数的对数：

$$h \approx 1 + \lceil \log_F P \rceil, \qquad P \approx \frac{N}{L}$$

（$N$ = 键总数，$L$ = 叶容量，$F$ = 内部节点扇出，$P$ = 叶子个数，$h$ = 层数，含内部节点层与叶层。）

第二，**这套"溢出后从正中切开"的分裂策略，长期平均装填率只有约 50%**——一半的空间是空着的。真实数据库主动控制这个取舍：PostgreSQL 的 B-tree 索引默认 `fillfactor = 90`，建索引时每页只填到 90%，留出的空间用于吸收后续插入，代价是页数多约 11%（$1/0.9 \approx 1.111$）。

做完这个实验，你应该能回答：一次插入为什么会引发连锁分裂？叶链为什么是 B+ 树压过 B 树、成为数据库主流的关键？以及等深分区为什么可以"抽样建树 + 全量计数"两步完成，而不必先把全量数据排序。

运行前准备

1. Python 3.10 及以上。
2. 安装依赖（在仓库根目录执行）：

```bash
pip install numpy matplotlib jupyter
pip install graphviz # 可选：把树渲染成图
```

注意 `graphviz` 这个 pip 包只是 Python 绑定，**真正画图需要系统里另装 Graphviz 可执行程序**（Windows 可从 graphviz.org 下载安装包，或 `winget install Graphviz`；装完把 `bin` 目录加进 `PATH`）。没装也不影响本实验：`show()` 会自动退化成逐层文本打印。

验证方式：

```python
import numpy, matplotlib, graphviz
print("环境 OK")
```

3. 在 **`notebooks/` 目录下**打开本笔记本（`jupyter notebook notebooks/B-tree.ipynb`）。数据文件 `latitude_longitude.bin` 是用相对路径读取的，工作目录必须能直接看到它。
4. 若报 `ModuleNotFoundError: No module named 'system'`，说明仓库根目录没进 `sys.path`，重跑第一个代码单元格即可。

import sys, pathlib

# Put the repo root (the directory containing `system/`) on sys.path so
# `from system...` works whether this notebook is opened from its own
# folder or from the repo root.
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

一、B+ 树的结构：三层各司其职

| 组成部分 | 装什么 | 作用 |
| --- | --- | --- |
| 根 root | 分隔键 + 孩子指针 | 树的入口；根分裂是唯一让树长高的事件 |
| 内部节点 inner node | 只装分隔键 + 孩子指针，**不装数据** | 路标，负责把查找路由到正确的子树 |
| 叶子节点 leaf node | 键 + 值（这里值是行号/载荷） | 真正承载数据的地方，并且横向串成链表 |

四个必须分清的术语

| 术语 | 英文 | 含义 |
| --- | --- | --- |
| 扇出 | fan-out | 一个节点最多有多少个孩子，等于"分隔键个数 + 1" |
| 容量 | capacity | 一个节点最多放多少个键。本实验故意用小容量，方便肉眼观察 |
| 装填率 / 填充因子 | fill factor | 实际键数 ÷ 容量 |
| 分隔键 | separator / pivot key | 内部节点里划分子树范围的键，本身不携带数据行 |

分裂与叶链

**分裂（split）**：节点装满后再插入，就把节点一分为二，并把中间那个键**上提**到父节点当分隔键。若父节点也因此溢出，就继续向上——一次插入可能引发连锁分裂，一直到根。

**叶链（leaf chain）**：所有叶子用 `next` / `previous` 双向指针首尾相接。有了它，范围查询只需要**一次**从根下降：找到起始键所在的叶子，之后顺着 `next` 一路向右走，完全不用回到父节点。这是 B+ 树压过 B 树的关键——B 树要中序遍历，来回上下走，产生大量随机 I/O。

为什么是 B+ 而不是 B

| 对比项 | B 树 | B+ 树 |
| --- | --- | --- |
| 内部节点是否存数据 | 存 | 不存，只放分隔键和指针 |
| 内部节点扇出 | 小（键 + 数据挤占空间） | 大（只剩键和指针） |
| 树高 | 相对高 | 相对矮 |
| 范围查询 | 中序遍历，来回上下 | 一次下降 + 沿叶链顺序扫 |
| 全索引扫描 | 中序遍历 | 直接从头走叶链 |

设节点总空间为 $S$ 字节，一个"键 + 行指针"占 $k + p$ 字节，一个"纯分隔键 + 孩子指针"占 $k + c$ 字节（通常 $p > c$，因为行指针要定位到堆表里的具体位置）。则 B 树内部节点扇出 $\approx S/(k+p)$，B+ 树 $\approx S/(k+c)$——分母更小，扇出更大，树更矮。

点查代价的口径

一次点查的代价是两部分之和：

$$\text{cost} \approx \underbrace{h}_{\text{节点访问次数（页 I/O）}} + \underbrace{\lceil \log_2(\text{叶内键数} + 1) \rceil}_{\text{叶内二分查找}}$$

实测（N = 200 000，随机 2000 次查询，叶容量 64、内节点容量 63）：B+ 树平均 **10.0** 个检查单元；有序数组二分平均 **16.6** 次比较（最坏上界 $\lceil \log_2 200000 \rceil = 18$）；全表顺序扫描 **100 000** 行（$= N/2$）。这 10.0 的构成是：树高 4 中的 3 次内部节点下降 + 1 个叶子 + 叶内二分 6 次（每叶平均 32 个键，$\lceil \log_2 33 \rceil = 6$）。

二、手工搭一棵 B+ 树，观察一次分裂

下面这一格不调用任何"插入算法"，而是**手工**把节点拼出来：先造 6 个叶子（`BPlusTree.Leaf(容量, 键列表, 值列表)`），用 `next` / `previous` 把它们串成叶链，再造 2 个内部节点和 1 个根（`BPlusTree.Inner(容量, 键列表, 孩子列表)`），最后挂到 `BPlusTree(3, 4)` 上——括号里的 3 是内部节点容量，4 是叶子容量。

为什么要手工搭？因为这样你能**先看清一个稳定状态长什么样**，再看插入如何把它打破。

初始结构（本机实测：树高 3、节点 9、叶 6、共 19 个键）：

```text
root [32]
/ \
inner [13, 21] inner [38, 43]
/ | \ / | \
[3 8 9 11] [14 18 20] [21 22 25 31] [31 34 36] [39 41] [44 46 49]
└────────────── 叶链 next/previous 双向贯穿 ──────────────┘
```

两个观察点：

• 内部节点只放分隔键（13、21、38、43、32），**没有任何数据**；

• 叶子之间横向相连，这是范围扫描能"一次下降、顺序右移"的物理基础。

> 手工数据有个小瑕疵：键 `31` 同时出现在两个叶子里，`21` 既是分隔键又出现在叶内。真实索引不会有重复键；`consistency_check()` 只检查单个叶子内部是否重复，所以这里能通过。看结果时不必纠结它。

搭好之后，代码依次插入 `50、53、55、58`，每插一次就渲染一次树，用来观察分裂。

from system.indexes.btree import BPlusTree

import shutil


def show(tree):
    """渲染一棵 B+ 树。

    检测到系统 Graphviz 可执行文件（dot）时用 graphviz 出图；
    没有安装时退化成逐层文本打印，保证后面的实验照常进行。
    """
    if shutil.which("dot") is None:
        print("(未检测到系统 Graphviz 可执行文件 dot，改用文本打印)")

        def label(node):
            if isinstance(node, BPlusTree.CountingLeaf):
                return f"[count={node.put_calls}]"
            return "[" + " ".join(str(k) for k in node.keys) + "]"

        level = [tree.root]
        depth = 0
        while level:
            print(f"  level {depth}: " + " ".join(label(n) for n in level))
            level = [c for n in level for c in getattr(n, "children", [])]
            depth += 1
        return
    tree.show()

# create leaves
leaf_1 = BPlusTree.Leaf(4, [3, 8, 9, 11], [1, 2, 3, 4])
leaf_2 = BPlusTree.Leaf(4, [14, 18, 20], [5, 6, 7])
leaf_3 = BPlusTree.Leaf(4, [21, 22, 25, 31], [8, 9, 10, 11])
leaf_4 = BPlusTree.Leaf(4, [31, 34, 36], [12, 13, 14])
leaf_5 = BPlusTree.Leaf(4, [39, 41], [15, 16])
leaf_6 = BPlusTree.Leaf(4, [44, 46, 49], [17, 18, 19])

# connect leaves
leaf_1.next = leaf_2
leaf_2.previous = leaf_1
leaf_2.next = leaf_3
leaf_3.previous = leaf_2
leaf_3.next = leaf_4
leaf_4.previous = leaf_3
leaf_4.next = leaf_5
leaf_5.previous = leaf_4
leaf_5.next = leaf_6
leaf_6.previous = leaf_5

# create inner nodes
inner_1 = BPlusTree.Inner(3, [13, 21], [leaf_1, leaf_2, leaf_3])
inner_2 = BPlusTree.Inner(3, [38, 43], [leaf_4, leaf_5, leaf_6])

# create root node
root = BPlusTree.Inner(3, [32], [inner_1, inner_2])

# create B-tree
bplustree = BPlusTree[int, int](3, 4)
bplustree.root = root
print("Initial B-tree:")
show(bplustree)

# insert values
bplustree.put(50, 20)
print("After inserting 50:")
show(bplustree)
bplustree.put(53, 21)
print("After inserting 53:")
show(bplustree)
bplustree.put(55, 22)
print("After inserting 55:")
show(bplustree)
bplustree.put(58, 23)
print("After inserting 58:")
show(bplustree)
Initial B-tree:

<graphviz.sources.Source at 0x11405ad50>
After inserting 50:

<graphviz.sources.Source at 0x114021e20>
After inserting 53:

<graphviz.sources.Source at 0x111b8a8d0>
After inserting 55:

<graphviz.sources.Source at 0x111b88d70>
After inserting 58:

<graphviz.sources.Source at 0x111bbeb10>

这四次插入分别发生了什么

下面把实测到的每一步拆开。叶容量 4 意味着：叶子**装满 4 个不分裂，插入第 5 个才溢出**。

**1. `put(50, 20)` —— 无分裂**

50 走路由落到最右叶 `[44, 46, 49]`，它只有 3 个键（容量 4，未满），直接插入 → `[44, 46, 49, 50]`。树高、节点数都不变。

**2. `put(53, 21)` —— 叶子分裂，分隔键上提**

目标叶已满，插入后变成 5 个键 `[44, 46, 49, 50, 53]`。从中点切开（`mid = 5 // 2 = 2`）：

```text
左半 [44, 46] 右半 [49, 50, 53] 上提的分隔键 = 原 keys[2] = 49
```

父节点 `[38, 43]` 只有 2 个键（容量 3，未满），直接把 49 插进去 → `[38, 43, 49]`，孩子从 3 个变 4 个。注意右半的第一个键正好等于上提的分隔键——**叶分裂时上提的键在右半保留**，这是 B+ 树的常见做法之一。同时代码会重接叶链：左半接原来的前驱、右半接原来的后继，中间两个新叶子互指。

这一轮后：节点 10、叶 7。

**3. `put(55, 22)` —— 无分裂**

落到 `[49, 50, 53]`（未满）→ `[49, 50, 53, 55]`。

**4. `put(58, 23)` —— 叶子分裂，并引发父节点分裂**

目标叶已满 → 溢出成 `[49, 50, 53, 55, 58]` → 切成 `[49, 50]` 和 `[53, 55, 58]`，分隔键 53 上提。

但这一次父节点的键已经是 `[38, 43, 49]`，**3 个 = 容量 3，父节点也满了**。于是连锁发生：先把 53 插进去（键暂时变 4 个），再分裂父节点——左 `[38, 43]` 带 3 个孩子、右 `[53]` 带 2 个孩子，分隔键 49 上提到根。根的键从 `[32]` 变成 `[32, 49]`，孩子从 2 个变 3 个。

这一轮后：节点 12、叶 8，**树高仍然是 3**。

关键结论：**只有根分裂才会让树长高一层。** 父节点分裂只是让树变宽。真正让树长高的事件在别处——是"根也满了"的那一次；而根满的前提是下面每一层都满过一遍，这就是 B+ 树能长期保持矮胖的原因。

（内部节点分裂与叶分裂有一处不同：`Inner.split` 用的是 `keys[mid+1:]`，即上提的那个键**从下层消失**，只留在父节点当分隔键。叶分裂则保留在右半。）

想再看一遍叶链的作用，可以自己加一格跑 `list(bplustree.get_all_in_range(21, 36))`：它会返回 `[8, 9, 10, 11, 12, 13, 14]`，横跨三个叶子，但只做了一次从根下降。

三、B+ 树的另一个用途：给数据做等深分区

到这里换一个问题。**等深分区（equi-depth partitioning）**要求把值域切成若干段，使每段落到的记录数尽量相等。它是并行查询切分、直方图统计、数据倾斜检测的共同基础。

最直接的做法是"排全序再均分"，但那要对 N 条记录做一次 $O(N \log N)$ 的外排序。B+ 树给了两步走的办法，省掉这次排序：

1. 抽 $m$ 条样本（$m \ll N$）建一棵**内节点很小、叶子很大**的树，整棵树常驻内存；
2. 把全量数据流式灌进这棵树，落到叶子上——但叶子不存数据，只记数。

每个叶子的计数值就是一个桶的深数，叶子之间的边界自然就是分区边界。**内节点的分隔键，就是对数据分位数的一次估计**——这就是"内部节点是数据分布的一个模型"这句话的具体含义。

代价也要说清楚：切分点来自样本，样本偏差会让桶深不均；样本量越大，桶边界越接近真实分位数。

import matplotlib.pyplot as plt
import numpy as np
import random as rnd

# Load latitude/longitude data from disk
loaded_data = np.fromfile("latitude_longitude.bin", dtype=np.float32).reshape(-1, 2)

# remove duplicates as our b-tree cannot handle duplicates so far:
# correct would be to keep duplicates for counting, but this is not necessary to prove the point here
data = set()
for latitude, longitude in loaded_data:
    data.add(latitude)

# We need a sample of the data, i.e. a subset that has similar statistical properties:
# (1.) let's shuffle the input:
data = list(data)
rnd.shuffle(data)

# (2.) And show histograms of varying granularity
fig, axs = plt.subplots(1, 6, figsize=(10, 3))
fig.tight_layout()

for idx, k in enumerate([10, 50, 100, 1000, 10000, 100000]):
    # take the first k elements as a sample:
    sample = data[:k]

    # plot the histogram:
    axs[idx].title.set_text(f"k={k}")
    axs[idx].hist(sample, bins=10, alpha=0.5)
    axs[idx].plot()
Notebook 已保存的运行结果

先看抽样为什么管用

上一格从 `latitude_longitude.bin` 读入了真实数据（197 229 个经纬度点，float32 小端、纬度经度交替），取出纬度并去重后，随机打乱，然后对 $k = 10, 50, 100, 1000, 10000, 100000$ 六种样本量各画一张 10 桶直方图。

看图要看的是**形状什么时候稳定下来**：$k = 10$ 时直方图完全不成形，$k$ 增大后各桶的高度比例逐渐固定。样本量足够大之后，再加大 $k$ 只是让曲线更平滑，不再改变形状——这正是"用样本估计分布"的合法性来源，也是下一步敢于只拿 1 万条样本建树的理由。

注意两点实现细节：

• 去重是因为本实现的 B+ 树暂不支持重复键（真实系统会把重复键合并成计数）；

• 打乱用的是 `rnd.shuffle` 且**没有设随机种子**，所以每次运行抽到的样本不同，后面的桶计数会在一定范围内浮动，"各桶大致相等"这个结论不变。

第一步：用样本建一棵"矮而胖"的树

`BPlusTree(5, 2000)`：内部节点容量 5（很小），叶子容量 2000（很大）。

为什么这么配？等深分区想要的是**桶的数量适中、桶深尽量均匀**。叶子大 → 桶少；内部节点小 → 内部那棵"索引树"极小，可以整个待在内存里。这也正好呼应第一节的结论：真正需要常驻内存的不是数据，而是那点路标。

然后取 10 000 条样本逐条 `put` 进去。本机实测：树高 3、节点 11、叶 8，也就是说这 1 万条样本把值域切成了 8 段。

> 下一格注释掉的 `bplustree.show()` 故意不开：1 万条样本铺在 8 个容量 2000 的叶子里，画出来是一张又宽又密的图，看不清结构，而且渲染很慢。想看结构请用前面那棵只有 19 个键的小树。

# create a b-tree with a decent sample size:
# we use small inners and big leaves, the goal here is to obtain a small "inner tree" (all nodes except the leaves)
bplustree = BPlusTree[int, int](5, 2000)
sample = sample[:10000]

# insert the sample data
for el in sample:
    bplustree.put(el, el)
# this can be slow:
# bplustree.show()

第二步：把叶子换成"只计数"的叶子

`convert_to_counting_leaf_tree()` 做一件事：**保留全部内部节点，把叶层整个换成 `CountingLeaf`。**

`CountingLeaf` 不存键也不存值，只有一个 `put_calls` 计数器；它的 `split()` 直接抛 `NotImplementedError`——也就是说，**结构在建好样本树的那一刻就冻结了**，之后再灌多少数据都不会改变树的形状，只会增加计数。

这正是"两步法"能省掉排序的原因：全量数据不需要参与任何结构调整，只做一次 $O(N \log P)$ 的路由下降（$P$ 是叶子个数），比一次外排序便宜得多。

换完之后调用 `show()`，你会看到每个叶子的计数都是 0——因为还没有数据灌进来，边界已经就位、桶还是空的。

# now we replace the leaf level by CountingLeaves
# those are leaves that do not store the data but simply count the number of put calls
bplustree.convert_to_counting_leaf_tree()
show(bplustree)
<graphviz.sources.Source at 0x120fce240>

第三步：把全量数据灌进去

现在把去重后的全部纬度（本机实测 132 305 个不同取值）逐条 `put` 进这棵树。

注意这时 `put` 的语义已经变了：路由照旧从根下降到某个叶子，但落到 `CountingLeaf` 上只是 `put_calls += 1`。**没有任何一条数据被存下来，只有计数在增长。**

# Now, let's insert all data into this counting tree:
for el in data:
    bplustree.put(el, el)
# Here is the result
show(bplustree)
<graphviz.sources.Source at 0x120fea300>

结果：一份近似等深的分区

`show()` 之后每个叶子显示的就是落在它这个区间里的记录数。本机两次实测（都是 8 个桶，总计 132 305，均值 16 538）：

| 运行 | 桶 1 | 桶 2 | 桶 3 | 桶 4 | 桶 5 | 桶 6 | 桶 7 | 桶 8 | 最深/最浅 |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| 第 1 次 | 16 021 | 16 883 | 16 364 | 17 002 | 17 181 | 16 795 | 15 766 | 16 293 | 1.09 |
| 第 2 次 | 16 557 | 17 616 | 16 666 | 16 507 | 16 081 | 16 900 | 16 434 | 15 544 | 1.13 |

**最深桶 / 最浅桶稳定在 1.1 上下，偏差约 10%**——这就是等深分区：8 个桶几乎一样深，桶边界就是叶层各段的分界键值。

（`rnd.shuffle` 没有固定随机种子，所以每次运行抽到的样本不同，8 个数会变；但"总计 132 305、每桶一万六千上下、最深最浅相差约 10%"这三条应当每次都复现。）

两点值得记下来：

• **省掉的是排序。** 全量数据只做了一次流式分发，没有排序、没有归并、没有中间落盘。

• **换来的是近似。** 桶边界来自 1 万条样本，不是真实分位数。样本量越大边界越准；数据量极度倾斜或分布未知时，偏差会明显变大。

把桶数调一调（改 `BPlusTree(5, 2000)` 的叶子容量，或改样本量）再跑一遍，观察"最深/最浅"这个比值怎么变——这是本实验最值得动手的一步。

四、思考题与详解

<details>
<summary><b>第 1 题</b>：叶容量 4、内部容量 3，为什么插入第 5 个键才触发第一次分裂，而不是第 4 个之后的某一次？</summary>

因为代码判断的是"**溢出**"而不是"装满"：`if len(node.keys) > self.leaf_cap`。

插到第 4 个键时 `len(keys) == 4`，等于容量，不算溢出，不分裂；插第 5 个键后 `len(keys) == 5 > 4`，才调用 `split()`。

本笔记本里的写法是"先插入允许暂时溢出，再从中点切开"——这是教科书里常见的一种变体（另一种是先检查容量、满了就先分裂再插入）。两者的树形会略有不同，装填率也不同，选哪种要在代码里保持一致。

</details>

<details>
<summary><b>第 2 题</b>：假如把"溢出后从正中切开"改成"快满了就提前分裂"（PostgreSQL 的 fillfactor 思路），节点数、树高、后续插入的分裂次数会怎么变？</summary>

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

PostgreSQL 的做法正是后者：B-tree 索引默认 `fillfactor = 90`，插入新键时可以复用页内预留的 10%，代价是叶子页数比满载多约 11%（$1/0.9 \approx 1.111$）。

**这是一次性多占空间换后续少做结构变动的取舍。** 写多读少的表不值得留空，读多写少的表值得。

</details>

<details>
<summary><b>第 3 题</b>：实测里 N 从 10 000 涨到 50 000（5 倍）树高不变，从 50 000 涨到 200 000（4 倍）树高加 1。用公式解释这种"跳变"。</summary>

用

$$h \approx 1 + \lceil \log_F P \rceil, \qquad P \approx \frac{N}{L \times \text{装填率}}$$

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

• $N = 10\,000 \Rightarrow P \approx 312$，只要 $F \ge \sqrt{312} \approx 17.7$ 就有 $h = 3$；

• $N = 50\,000 \Rightarrow P \approx 1562$，只要 $F \ge \sqrt{1562} \approx 39.5$，仍是 $h = 3$；

• $N = 200\,000 \Rightarrow P \approx 6249$，要维持 $h = 3$ 需要 $F \ge \sqrt{6249} \approx 79.1$，而本实验 $F = 64 < 79.1$，做不到；于是走到 $h = 4$（要求 $F \ge \sqrt[3]{6249} \approx 18.4$，$F = 64$ 满足）。

本实验内部容量 63，即扇出最多 $F = 64$：前两档的门槛（17.7、39.5）都够得着，第三档的 79.1 够不着——树高就是在这里跳的。

**关键在于 $h$ 是关于 $P$ 的对数，还带向上取整**：数据在一个数量级内变化时 $\lceil \cdot \rceil$ 常常不变，只有跨过 $F$ 的某个幂次才 +1。这就是"跳变"——树高对数据量极其不敏感。

</details>

<details>
<summary><b>第 4 题</b>：为什么 B+ 树的范围查询不会因为叶子分散在不同分支而反复回到根节点？如果删掉叶链指针，代价变成什么？</summary>

叶链把整个叶层串成一条双向链表。范围查询的流程是：一次从根下降到起始键所在的叶子（$O(\log_F P)$），之后 `node = node.next` 一路向右，期间**完全不需要回到父节点**。代价是 $h + k/L$（一次下降 + $k/L$ 个叶子的顺序扫）。

删掉叶链之后：想找下一个叶子只能从根重新下降一次，代价从 $h + k/L$ 退化成 $k \cdot h$（每个叶子都要走一遍树），随机 I/O 数量直线上升；全索引扫描也没法线性走，退化成中序遍历。

**叶链是 B+ 树压过 B 树的决定性设计**，不是"锦上添花"。

</details>

<details>
<summary><b>第 5 题</b>：内部节点为什么"弃卒保帅"地不存数据行？如果非要在内部节点也存数据（回到 B 树），扇出和树高会怎么变？</summary>

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

• B 树内部节点扇出 $\approx S/(k+p)$

• B+ 树内部节点扇出 $\approx S/(k+c)$

因为 $k + c < k + p$，B+ 树的 $F$ 更大，由 $h \approx 1 + \lceil \log_F P \rceil$ 得树更矮。而树高直接决定一次点查要访问多少个页。

代价是 B+ 树的点查必须走到叶层（B 树在内部节点命中就可以返回），但换来的是"每一层能排除更多键 + 范围查询可以走叶链"。数据库里范围扫描（`BETWEEN`、排序、`GROUP BY` 走索引）远比单点命中常见，所以这笔交易划算。

</details>

<details>
<summary><b>第 6 题</b>：实测 N = 200 000 时点查平均检查 10.0 个单元，树高为 4。这 10.0 是怎么拆出来的？</summary>

按点查代价的口径：

$$\text{单元数} = \underbrace{(h - 1)}_{\text{下降经过的内部节点}} + \underbrace{1}_{\text{叶节点}} + \underbrace{\lceil \log_2(\text{叶内键数} + 1) \rceil}_{\text{叶内二分}}$$

$N = 200\,000$ 时 $h = 4$，前两项 $= 3 + 1 = 4$。实测平均 10.0，所以叶内二分那一项平均贡献 $10.0 - 4 = 6.0$，即 $\lceil \log_2(\text{叶内键数}+1) \rceil = 6$，对应叶内键数落在 $(31, 63]$ 区间。

回头核对：$N = 200\,000$、叶数 6 249，平均每叶 $200000 / 6249 \approx 32.0$ 个键，正好落在区间里，$\lceil \log_2 33 \rceil = 6$。**完全自洽。**

顺带看清一件事：同样是对数级，B+ 树的 10.0 和数组二分的 16.6 差别不算大；真正的差距在于这 10 个单元里有 4 个是**页访问**（可在缓冲池里摊销），而全表扫描的 100 000 是实打实的行检查。

</details>

<details>
<summary><b>第 7 题</b>：等深分区为什么可以用"抽样建树 + 全量计数"两步完成，而不是排完序再切成 k 段？它省掉了什么，代价是什么？</summary>

排全序再均分要先对 N 条记录做一次 $O(N \log N)$ 的外排序（大表还要落盘做归并），才能得到 $k-1$ 个切分点。两步法换成：

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

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

代价有两点：一是切分点来自样本，样本偏差导致桶深不均（数据极度倾斜或分布未知时尤其明显）；二是树结构要保持在内存里。若样本确实是同分布随机采样，误差可以用样本量控制：$m$ 越大，桶边界越接近真实分位数。本实验 8 个桶的最深/最浅比值约 1.09，就是 1 万条样本换来的精度。

</details>

<details>
<summary><b>第 8 题</b>：一棵叶容量为 L、内部容量为 F−1 的 B+ 树，若要求树高不超过 3，最多能索引多少个键？分满载与实测 50% 装填两种情况给出表达式。</summary>

树高 3 = 层 0 根、层 1 内部、层 2 叶：

```text
每个叶子最多容纳键数 = L × 装填率
根的孩子数（层 1 节点数） ≤ F
层 1 每个节点的孩子数 ≤ F → 它们就是叶子
⇒ 叶总数 P ≤ F²
⇒ 键总数 N ≤ F² · L · 装填率
```

• **满载**（装填率 = 1）：$N_{\max} = F^2 \cdot L$

• **实测装填率 ≈ 50%**：$N_{\max} \approx 0.5 \cdot F^2 \cdot L$

代入本实验的 $L = 64$、$F = 64$：$N_{\max} = 64^2 \times 64 = 262\,144$（满载），实测装填率下约 $131\,072$。

这也解释了为什么 N = 200 000 时装填率只有 50% 就"被迫"长到第 4 层：$131\,072 < 200\,000 < 262\,144$——按满载估算还能塞下，按实际装填率就塞不下了。

</details>