实验 06：基数树与圣诞树——前缀共享与"描述符"的递归细分

为什么做这个实验

• **要验证的现象**：前面几个实验的索引都按"一个完整的键"组织（B+ 树按键排序，位图按取值建位）。本实验看另一类结构 **Trie（前缀树）**：把键拆成一段一段，从根往下每一层消费一段。**查找代价是 $O(\text{键长})$，与表里有几行无关**——这是它相对 B+ 树（$O(\log n)$）的本质差别。

• **反直觉之处一**：Trie 省了比较次数，却很费空间。每个字符一个节点，长键会拉出很长的链，其中大量"只有一个孩子的链"是纯粹的浪费。**Radix Trie（基数树）**用路径压缩把这些链并成一条边、边上记完整片段。本仓库实测：插入 `CAR`、`CAT`、`CATS`、`DOG`、`DOGS`、`DOT` 这 6 个共享前缀的键，标准 Trie **11** 个节点，压缩后 **9** 个。

• **反直觉之处二**：本仓库把"逐字符比较"抽象成了"**把一个描述符（descriptor）递归细分**"。换掉描述符，同一套 Trie 代码就从字符串索引变成了二维空间索引——这就是标题里的**圣诞树**。

• **一处需要你自己动手查的地方**：本机实测 `Triangle.split_into_sub_descriptors()` 的细分结果**不符合**"取三边中点分成 4 个全等小三角形"的预期（详见后文"值得探究的问题"）。不要因为它是仓库自带的代码就默认它是对的。

• **学完能回答**：给定扇出 $c$ 与层数 $L$，这棵树有多少内部节点、多少叶子？为什么真实的空间索引（R-tree）不预先细分到固定深度？

运行前准备

本实验依赖仓库自带的 `system/` 模块，需要额外安装四个包：

```bash
python -m pip install ipycanvas graphviz deprecation faker
```

| 包 | 被谁需要 | 说明 |
|---|---|---|
| `ipycanvas` | `system/utils.py` | 在 notebook 里画三角形与树（顶层导入，**必须安装**） |
| `graphviz` | `system/indexes/btree.py` | B+ 树可视化，测试模块会间接导入 |
| `deprecation` | `system/interfaces/stores.py` | 弃用标记 |
| `faker` | `system/tests/test_indexing.py` | 生成测试数据 |

另外全局需要 `pandas` `numpy` `matplotlib` `seaborn`。验证：

```python
from system.utils import Vector, Triangle
from system.indexes.radix_trie import RadixTrie
from system.indexes.christmas_tree import ChristmasTree
print("环境就绪")
```

> **注意**：绘图部分（`ipycanvas` 的 `Canvas`）只能在 Jupyter 前端里显示，在纯 `.py` 脚本中不会有输出；逻辑部分（构建、`show()`、`contains()`）在脚本里照常可用。
> 如果 `import system` 失败，先运行下一个代码格——它会自动把仓库根目录（含 `system/` 的那一层）加入 `sys.path`。

**A Christmas Trie**

本笔记本演示一棵"圣诞树"（christmas trie）的主要特性。在往下走之前，先把三个概念理清楚。

标准 Trie：按前缀走，不比较整个键

Trie 把键拆成一段一段，从根往下每一层消费一段。以 `CAR`、`CAT`、`CATS` 为例：

```text
(root)
/ \
C D...
/ \
A O
/ \ / \
R T G T
/ \
S (end)
```

**Trie 的查找代价是 $O(\text{键长})$，与表里有几行无关。** 代价在**空间**：每个字符一个节点，长键会拉出很长的链，而且很多链上只有一个孩子——这些"单孩子链"是纯粹的浪费。

Radix Trie：把单孩子链压成一条边

**路径压缩（path compression）**：如果一条边上只有一个孩子，就把这条边和它的孩子合并，边上记下完整的字符串片段。压缩后边上的标签不再是一个字符，而可以是任意长度的串。这就是 **Radix Trie（基数树）**，也叫压缩 Trie。

本仓库的实测（插入 `CAR`、`CAT`、`CATS`、`DOG`、`DOGS`、`DOT` 六个共享前缀的键）：

| | 节点数 |
|---|---|
| 标准 Trie | **11** |
| Radix Trie（路径压缩后） | **9** |

省下 2 个节点。键越长、共享前缀越多，省得越多。

描述符：把"逐字符"换成"递归细分"

本仓库的 `RadixTrie` 有一个关键抽象：**键映射（key mapping）**，它决定"一个键在第 $i$ 层被切成哪一段、这一段映射到第几个孩子"。

• 用 `PrefixDigitMapping`，键 `110` 在第 1 层取第 1 个字符 `'1'` → 走 1 号孩子；第 2 层取 `'1'` → 走 1 号孩子；第 3 层取 `'0'` → 走 0 号孩子。这就是普通的二进制 Trie。

• **换成别的映射，同一棵树就能索引别的东西。**

圣诞树把映射换成了**几何描述符的递归细分**：根节点持有一个三角形，把它细分成 4 个子三角形，每个孩子持有一个；再各自细分……于是"从根走到叶"等价于"不断判断一个点落在哪个子三角形里"。**这就是空间索引**：把二维平面递归划分成嵌套的区域，区域的编号就是索引键。

步骤 1：三角形描述符与"包含"判定

描述符（descriptor）要提供两件事：

1. `contains(point)` —— 判断一个点是否落在自己内部；
2. `split_into_sub_descriptors()` —— 把自己细分成 $c$ 个更小的描述符。

有了这两个方法，Trie 的"往下走一层"就等价于"判断点落在哪个子描述符里"。本仓库的 `Triangle.contains()` 用重心坐标实现。

下面这段代码做两件事：

• 构造一个三角形 `t = Triangle((0,0), (120,0), (60,120))`，并定义 `recursive_draw()`：`rec_depth` 控制递归到第几层，每层先把当前三角形画出来，再对它的 4 个子三角形递归；

• 画一排图（`rec_depth` 从 1 到 7），直观展示"递归细分"长什么样。

**预期看到什么**：一排越来越密的三角形。第 1 层是 1 个大三角形，第 2 层是它细分后的 4 个小三角形……

紧接着的下一格用 `contains()` 打点验证：在 $0 \le x, y < 300$ 的网格上逐点判断，落在三角形内的点画成白色，落在外的画成品红色。**预期看到**：一个三角形的轮廓被清晰地"点"出来——这说明 `contains()` 在边界附近也判得对。

> 浮点边界要留心：`(0,0)`、`(300,0)`、`(150,300)` 是三个顶点，`(150,0)` 在底边上。不同实现对边界的归属可能不同，这是空间索引里一个真实的坑。

步骤 2：一棵简单的 Radix Trie

下面构造一棵**固定扇出**的二进制 Radix Trie：

```python
trie = RadixTrie[str, str](
key_mapping=prefix_mapping, # 决定"键的第 i 位映射到第几个孩子"
children_per_inner_node=2, # 扇出 c = 2
number_of_inner_node_levels=3, # 层数 L = 3
)
```

两个参数的含义：

• `children_per_inner_node = c`：每个内部节点有几个孩子；

• `number_of_inner_node_levels = L`：内部节点有几层（叶子在第 $L+1$ 层）。

**固定扇出 Trie 的规模公式**（这是本实验要背下来的公式）：

$$\text{内部节点数} = \sum_{i=0}^{L-1} c^{i}, \qquad \text{叶子数} = c^{L}$$

代入 $c = 2$、$L = 3$：内部节点 $1 + 2 + 4 = 7$，叶子 $2^3 = 8$。

**注意**：这是"满树"的规模，与实际存了多少个键无关。下面存入 5 个键（`110`→a、`101`→b、`010`→c、`011`→d、`111`→e），8 个叶子里就会有 **3 个是空的**。这正是固定扇出 Trie 的空间代价，也是路径压缩要解决的问题。

**预期看到什么**：`trie.show()` 打印出的结构应当满足——

• **7 个内部节点 + 8 个叶子**，与公式 $1+2+4=7$、$2^3=8$ 完全一致；

• 8 个叶子里只有 **5 个非空**（前缀 `000`、`001`、`100` 对应的 3 个叶子是空的）；

• 非空叶子的分布：`010`→c、`011`→d 在"首位 0"一侧；`101`→b、`110`→a、`111`→e 在"首位 1"一侧。

请对照输出**亲手数一遍**节点，这是验证你真的读懂了公式的唯一办法。

如果想直接验证公式，可以另起一格跑：

```python
def sizes(c, L):
return sum(c ** i for i in range(L)), c ** L

for c, L in [(2, 3), (2, 4), (4, 3), (4, 4), (8, 3)]:
inner, leaves = sizes(c, L)
print(f"c={c} L={L}: 内部节点 {inner:4d} 叶子 {leaves:5d} 合计 {inner+leaves:5d}")
```

期望输出：`c=2 L=3: 7/8`、`c=2 L=4: 15/16`、`c=4 L=3: 21/64`、`c=4 L=4: 85/256`、`c=8 L=3: 73/512`。

**读这张表**：层数每 +1，叶子数乘 $c$。空间索引要覆盖一个大区域，代价增长得非常快——这解释了为什么真实的空间索引（R-tree）**不预先细分到固定深度**，而是按需分裂。

步骤 3：圣诞树——只换描述符，不换结构

```python
triangle = Triangle(Vector(0, 0), Vector(300, 0), Vector(150, 300))
christmas_trie = ChristmasTree[Vector, str](
children_per_inner_node=4, # 三角形细分成 4 个子三角形
descriptor=triangle, # ← 这里是关键：换成几何描述符
number_of_inner_node_levels=3,
)
```

请盯住这里**换了什么、没换什么**：

• **换了描述符**：`key_mapping=PrefixDigitMapping` → `descriptor=triangle`；

• **换了扇出**：2 → 4（一个三角形细分成 4 个子三角形）；

• **没换结构**：仍然是"每层把描述符细分，每个孩子持有一份"。

同一套 Trie 代码，换一个描述符就从字符串索引变成了空间索引——这是本实验最值得体会的一点。

下一格用 `ipycanvas` 把这棵树画出来（只在 Jupyter 里可见）。

**预期看到什么**：同样的公式，取 $c = 4$、$L = 3$：

$$\text{内部节点} = 1 + 4 + 16 = 21, \qquad \text{叶子} = 4^3 = 64$$

64 个叶子就是把大三角形递归细分 3 层后得到的 64 个子区域。

验证"包含"判定

本机实测（`Triangle((0,0), (300,0), (150,300))`）：

| 点 | `contains` |
|---|---|
| (150, 100) | True |
| (10, 10) | True |
| (150, 290) | True |
| (299, 1) | True |
| (1, 299) | False |

（150, 290）靠近顶点仍在内部，（1, 299）明显在三角形外——判定正确。

值得探究的问题：细分结果不符合预期

下面这段值得你自己跑一遍：

```python
subs = list(triangle.split_into_sub_descriptors())
print("子描述符个数:", len(subs))
for i, s in enumerate(subs):
print(f" {i}: {s}")
```

**本机实测输出**：

```text
子描述符个数: 4
0: ∆((0, 0), (150.0, 0.0), (75.0, 150.0))
1: ∆((75.0, 150.0), (150.0, 0.0), (75.0, 150.0))
2: ∆((150.0, 0.0), (150.0, 0.0), (75.0, 150.0))
3: ∆((225.0, 150.0), (-150.0, -0.0), (-75.0, -150.0))
```

**本机实测结果与预期不符，请查看源码并判断。** 两处值得追问：

1. 第 1、2 个子三角形出现**重复顶点**（第 1 个的第 1、3 个顶点都是 `(75,150)`；第 2 个的前两个顶点都是 `(150,0)`），即它们是**退化三角形**（面积为 0）；
2. 第 3 个子三角形出现**负坐标** `(-150, 0)`、`(-75, -150)`，落在大三角形之外。

**正确的做法**应当是取三条边的中点，把三角形分成 4 个全等的小三角形，全部落在原三角形内部。设顶点 $A(0,0)$、$B(300,0)$、$C(150,300)$，三边中点为：

• $M_{AB}(150, 0)$

• $M_{AC}(75, 150)$

• $M_{BC}(225, 150)$

4 个子三角形应为：

1. $\triangle(A,\ M_{AB},\ M_{AC})$ = `((0,0), (150,0), (75,150))`
2. $\triangle(M_{AB},\ B,\ M_{BC})$ = `((150,0), (300,0), (225,150))`
3. $\triangle(M_{AC},\ M_{BC},\ C)$ = `((75,150), (225,150), (150,300))`
4. $\triangle(M_{AB},\ M_{BC},\ M_{AC})$ = `((150,0), (225,150), (75,150))` —— 中间那个**倒置**的三角形

这 4 个都非退化、都落在原三角形内，面积各为原三角形的 1/4。

**为什么这件事重要**：`contains()` 用重心坐标实现，在退化三角形上会除零或给出无意义结果；落在原三角形外的子描述符则会让整棵树的区域划分出错。所以细分的正确性完全由描述符的实现者负责。

请打开 `system/utils.py` 里 `Triangle.split_into_sub_descriptors()` 的源码，画出它的取点逻辑，判断问题出在哪，并尝试改成取三边中点的版本，再重跑验证。

**Animated tree：动态地往树里插点**

上一格看到的是一棵**空树**的 64 个区域划分。这一格做一件更有意思的事：**随机往三角形里撒点，每撒一批就重画一次**，看这棵树被"填充"的过程。

```python
inner_node_factory=ChristmasTree.InnerNodeFactory[Vector, str](config="crystalball")
```

这一行是三种节点工厂配置之一，控制"子描述符什么时候被算出来"：

| 配置 | 做法 | 取舍 |
|---|---|---|
| `inner` | 按需计算，不缓存 | 内存最省，重复访问要重算 |
| `buffered` | 第一次算完缓存起来 | 空间换时间，适合反复访问 |
| `crystalball` | 预先算好并持有 | 访问最快，构建时一次性付出全部代价 |

逐层细分时越深的层持有的描述符越多（$c=4, L=3$ 时第 3 层有 16 个内部节点、叶子 64 个），如果每次访问都重新计算子描述符，代价很高——所以才有这三种策略。

**预期看到什么**：20 帧动画（每帧间隔 0.2 秒），点逐渐填满三角形，越填越密。`crystalball` 配置下构建会稍慢一点，但后续每帧绘制不需要重算。

**没有"最好"的配置，只有"匹配访问模式"的配置**——这是本实验要传达的一个工程判断。

**Each phase of the tree shown separately：把各个阶段并排画出来**

与上一格的区别是：这里**不清空画布**（`canvas.clear()` 被注释掉了），而是把每一批插入的结果画在画布的不同横向位置上（`x_offset = tree * size + space_in_between * tree`）。于是 5 个阶段从左到右并排显示，可以直接比较"点越来越多时，树长什么样"。

每批插入 1000 个点，随机采样的写法是"先随机取点，若不在三角形内就重取"（拒绝采样）：

```python
while True:
v = Vector(rnd.randint(0, size), rnd.randint(0, size))
if triangle.contains(v):
break
christmas_trie.put(v, str(i))
```

**预期看到什么**：5 幅并排的图，从左到右逐渐变密。注意观察：**无论撒多少个点，区域划分（64 个叶子）始终不变**——这正是"固定细分"的特征，也是它与 R-tree 最本质的差别（见思考题）。

最后两格分别做收尾：`flush_all_buffers()` 把缓冲的绘制指令刷出，再单独重画一次。

思考题与详解

> 建议先自己写一遍答案，再展开对照。

**1. 标准 Trie 的查找代价是 $O(\text{键长})$，B+ 树是 $O(\log n)$。当表里有 100 万行、键长固定为 10 时，哪个更快？请说明理由，并指出这个比较里隐含了什么假设。**

<details><summary>答案要点</summary>

键长固定为 10 时，Trie 的查找是 10 步指针跳转，与行数无关；B+ 树要 $\log_F n$ 次比较（$F$ 为扇出，取 $F \approx 100$、$n = 10^6$ 时约 3 次）。**单看比较次数，Trie 未必占优**；Trie 的真正优势是**代价不随数据量增长**——数据涨到 10 亿行时 B+ 树要 4~5 次，Trie 还是 10 步。

**隐含的假设**（必须点明）：

• 假设每次指针跳转代价相同。实际上 Trie 的 10 次跳转访问 10 个不同节点，**几乎每次都 cache miss**；B+ 树的前几层常驻 cache，实际可能更快。

• 假设键长真的固定且很短。键长可变且很长（如 URL）时，Trie 的层数被最长键拉高，代价迅速恶化。

**结论**：复杂度阶相同不代表实际性能相同，必须把"指针跳转 vs 顺序比较""cache 命中率"这些常数因子算进去。本案例库实验 07 的 RMI 也踩过同一个坑——算法更优，但常数因子输给了语言内建实现。

</details>

**2. 本实验的二进制 Trie（$c=2, L=3$）存 5 个键却用了 8 个叶子（3 个空）。若改用路径压缩，叶子数会变成多少？请画出来。**

<details><summary>答案要点</summary>

5 个键：`110`→a、`101`→b、`010`→c、`011`→d、`111`→e。

压缩后：

```text
(root)
├── "01" → { 0 → c, 1 → d } # 010, 011 共享前缀 01
└── "1" → { 01 → b, # 101
10 → a, # 110
11 → e } # 111
```

叶子数从 8 降到 **5**（正好等于键的个数，一个空叶子都不剩）；内部节点从 7 降到 3 个（根 + `"01"` + `"1"`）。

**这就是路径压缩的价值**：把"满树"变成"按需生长的树"，空间与**键的数量**成正比，而不是与 $c^L$ 成正比。

</details>

**3. 圣诞树把扇出从 2 提到 4、层数保持 3，叶子数从 8 变成 64。如果目标是"把 300×300 的区域划分成边长约 10 的小格"，需要多少层、多少叶子？这个数字说明什么？**

<details><summary>答案要点</summary>

每次细分把边长减半（三角形分成 4 个全等小三角形，边长为原来的一半）。要从 300 降到约 10：

$$300 / 2^{L} \approx 10 \ \Longrightarrow\ 2^{L} \approx 30 \ \Longrightarrow\ L \approx 5$$

5 层：叶子数 $4^5 = 1024$，内部节点 $\sum_{i=0}^{4} 4^i = 341$，**合计 1365 个节点**。

6 层（边长降到 4.7）：叶子 $4^6 = 4096$，合计 5461 个节点。

**这个数字说明**：靠固定细分去追求"精细"，代价是**指数级**的。真实的空间索引（R-tree、四叉树）从不预先细分到固定深度——它们按需分裂，数据稀疏的地方保持大区域，数据密集的地方才继续分。

</details>

**4. 描述符（descriptor）这个抽象带来了什么好处？如果不用描述符、直接写死"按字符走"，圣诞树还能实现吗？代价是什么？**

<details><summary>答案要点</summary>

描述符带来的是**"如何把一个键切成段、每段映射到哪个孩子"的策略与树结构解耦**：

• 用 `PrefixDigitMapping`：按字符切，是字符串 Trie；

• 用 `Triangle`：按几何细分，是空间 Trie。

树本身只关心"每个内部节点有 $c$ 个孩子，孩子各自持有一个子描述符"。

如果不用描述符、直接写死"按字符走"，要实现圣诞树就得**再写一套树**——两套代码各自维护、各自出 bug。用了描述符，只需要提供一个实现 `contains` 与 `split_into_sub_descriptors` 的类。

**代价是抽象成本**：描述符必须是不可变的（细分后原描述符不能被改），否则父节点持有的区域会与孩子的区域不一致；而且细分逻辑的正确性完全由描述符的实现者负责——本笔记本"值得探究的问题"一节发现的细分结果异常，问题就出在这里。

</details>

**5. `buffered` 与 `crystalball` 都在"预计算"上做文章。请设想两种访问模式，分别说明哪种配置更合适；再设想一种两种都不合适的模式。**

<details><summary>答案要点</summary>

• **适合 `crystalball`**：构建一次、查询极多，且各层访问频率均匀（如长期服务的空间索引）。预先算好全部子描述符，查询时零计算。

• **适合 `buffered`**：查询分布不均匀，只有部分区域被频繁访问（如城市 POI 检索，市中心热、郊区冷）。按需缓存，冷区域永远不付计算代价。

• **适合 `inner`**：构建后只查询很少几次（如临时的一次性分析），或内存极度紧张。预计算的成本收不回来。

**两种都不合适的模式**：构建后一次都不查（纯浪费），或查询模式完全随机且每个区域只查一次。后者用 `buffered` 会不断触发首次计算，缓存命中率为 0，白白付出缓存管理的开销——此时 `inner` 反而最好。

**这三类配置的实际耗时差别需自行实测确认**（可分别构建 $c=4, L=4$ 的圣诞树测构建耗时，再随机查询 10,000 个点测总耗时）。

</details>

**6. 本机实测 `split_into_sub_descriptors()` 的结果与预期不符。若改成"取三边中点"，4 个子三角形的顶点坐标分别是什么？改完之后 `contains()` 还需要改吗？**

<details><summary>答案要点</summary>

设三角形顶点 $A(0,0)$、$B(300,0)$、$C(150,300)$。三边中点：

• $M_{AB}(150, 0)$

• $M_{AC}(75, 150)$

• $M_{BC}(225, 150)$

4 个子三角形为：

1. $\triangle(A,\ M_{AB},\ M_{AC})$ = `((0,0), (150,0), (75,150))`
2. $\triangle(M_{AB},\ B,\ M_{BC})$ = `((150,0), (300,0), (225,150))`
3. $\triangle(M_{AC},\ M_{BC},\ C)$ = `((75,150), (225,150), (150,300))`
4. $\triangle(M_{AB},\ M_{BC},\ M_{AC})$ = `((150,0), (225,150), (75,150))` —— 中间那个**倒置**的三角形

4 个都非退化、都落在原三角形内，面积各为原三角形的 $1/4$。

**`contains()` 不需要改。** 重心坐标法对任意方向的三角形都成立，倒三角形也一样——关键是三个顶点不能共线（不能退化）。这也反证了退化三角形的危害：`contains()` 在退化三角形上会除零或给出无意义结果。

</details>

**7. 圣诞树递归细分得到的是**固定**的区域划分，而 R-tree 是**按需**分裂。请比较两者在"数据分布极不均匀"（例如 90% 的点挤在 5% 的面积里）时的表现。**

<details><summary>答案要点</summary>

• **固定细分（圣诞树）**：无论数据怎么分布，都把区域划成同样大小的 $4^L$ 块。数据挤在 5% 面积里时，那 5% 里的块塞满了点（查找退化成在块内线性扫描），另外 95% 的块全是空的（白白占用节点）。$L$ 小则热点太挤，$L$ 大则空块太多——**永远两头不讨好**。

• **按需分裂（R-tree / 四叉树）**：数据密集的地方继续分裂，稀疏的地方保持大块。节点数与**数据量**成正比，而不是与"区域面积 / 最小粒度"成正比。热点区域自动获得更细的划分。

这正是 R-tree（Guttman, SIGMOD 1984）成为空间索引主流的原因，也是 PostgreSQL 的 GiST / SP-GiST 与 PostGIS 采用它的原因（出处：Guttman, *R-trees: A Dynamic Index Structure for Spatial Searching*, SIGMOD 1984）。

**不过固定细分并非一无是处**：Geohash、H3、S2 这些"网格编码"本质上就是固定细分，它们的优势是**编码可以直接比较、可以用普通 B+ 树索引**，实现简单、分布式友好（见实验 16）。

</details>

**8. 本笔记本里"固定扇出"的规模公式是 $\sum c^i$ 与 $c^L$。请说明：为什么即使一个键都没存，这棵树也已经有这么多节点？这和"路径压缩"解决的正是同一个问题吗？**

<details><summary>答案要点</summary>

因为构造函数是按参数**预先把树建满**的：给定 $c$ 和 $L$，它就生成 $\sum_{i=0}^{L-1} c^i$ 个内部节点和 $c^L$ 个叶子，每个内部节点一开始就持有 $c$ 个子描述符。这与存了多少键无关——存 0 个键时，64 个叶子全是空的。

这与路径压缩解决的是**同一个问题的两个侧面**，但机制不同：

• 固定扇出的问题是"**预留了用不上的节点**"：空间与 $c^L$ 成正比，而不是与实际键数成正比。

• 路径压缩的做法是"**把单孩子链合并**"：它不预留空节点，而是让树随键一起生长，空间与键的数量成正比。

所以严格说，路径压缩解决的是"链太长"，而"预先建满"要靠"按需生长"（不为不存在的键创建分支）来解决。二者在真实实现里通常一起出现：**基数树既做路径压缩，也按需创建节点**。本仓库为了把"固定扇出的规模公式"讲清楚，选择了预先建满的写法——这正是你在输出里看到 3 个空叶子的原因。

</details>