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

> 前面几个实验的索引都按**一个键**组织：B+ 树按键排序，位图索引按取值建位。本实验看另一类结构：**Trie（前缀树）**——它按键的"前缀"逐段向下走。本仓库把 Trie 的思想再往前推了一步：把"逐字符比较"换成"把一个描述符（descriptor）递归细分"，于是同一套代码既能索引字符串，也能索引二维空间里的点——后者就是本实验标题里的**圣诞树（Christmas Tree）**。

---

## 一、实验目标

做完本实验，你应当能够：

1. 说明标准 Trie 与 Radix Trie（基数树）的差别，并用实测数字说明路径压缩省了多少节点（本实验：11 → 9）。
2. 读懂 `children_per_inner_node` 与 `number_of_inner_node_levels` 两个参数的含义，并算出给定参数下的节点规模。
3. 说明"描述符（descriptor）"在圣诞树里扮演什么角色，以及为什么换成三角形描述符后，同一棵 Trie 就变成了空间索引。
4. 运行本仓库的 `RadixTrie` 与 `ChristmasTree`，复现它们的节点结构输出。
5. 解释节点工厂的三种配置（`inner` / `buffered` / `crystalball`）各自解决什么问题。

---

## 二、预备知识

### 2.1 Trie：按前缀走，不比较整个键

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

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

**Trie 的查找代价是 $O(\text{键长})$，与表里有几行无关。** 这是它相对 B+ 树（$O(\log n)$）的一个本质差别：Trie 的代价不随数据量增长。

**代价是空间。** 每个字符一个节点，长键会拉出很长的链，而且很多链上只有一个孩子——这些"单孩子链"是纯粹的浪费。

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

**路径压缩（path compression）**：如果一条边上只有一个孩子，就把这条边和它的孩子合并，边上记下完整的字符串片段。

压缩后，边上的标签不再是一个字符，而可以是任意长度的串。这就是 **Radix Trie（基数树）**，也叫压缩 Trie。

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

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

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

![标准 Trie 与 Radix Trie](../figures/fig_trie.png)

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

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

- 用 `PrefixDigitMapping`，键 `110` 在第 1 层取第 1 个字符 `'1'` → 走 1 号孩子；第 2 层取 `'1'` → 走 1 号孩子；第 3 层取 `'0'` → 走 0 号孩子。这就是普通的二进制 Trie。
- **换成别的映射，同一棵树就能索引别的东西。**

圣诞树就是把映射换成了**几何描述符的递归细分**：根节点持有一个三角形，把它细分成 4 个子三角形，每个孩子持有一个；再各自细分……于是"从根走到叶"等价于"不断判断一个点落在哪个子三角形里"，最终定位到这个点所属的叶。

**这就是空间索引**：把二维平面递归划分成嵌套的区域，区域编号就是索引键。

### 2.4 节点缓冲：为什么要 `buffered` / `crystalball`

逐层细分时，越深的层持有的描述符越多（c=4、L=3 时：第 1 层 1 个、第 2 层 4 个、第 3 层 16 个内部节点，第 4 层是 64 个叶子）。如果每次访问都要重新计算子描述符，代价很高。

`InnerNodeFactory` 的三种配置对应三种策略：

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

这是一种典型的工程取舍：**没有"最好"的配置，只有"匹配访问模式"的配置**。

---

## 三、实验原理

### 3.1 固定扇出 Trie 的规模

本仓库的 `RadixTrie` 按**固定扇出**构造：给定 `children_per_inner_node = c` 与 `number_of_inner_node_levels = L`，则

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

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

**注意**：这是"满树"的规模，与实际存了多少个键无关。存入 5 个键时，8 个叶子里有 3 个是空的——这正是固定扇出 Trie 的空间代价，也是路径压缩要解决的问题。

### 3.2 圣诞树的规模

同样的公式，取 $c = 4$、$L = 3$：

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

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

### 3.3 三角形描述符与"包含"判定

描述符要提供两件事：

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

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

本机实测（`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）在三角形外——判定正确。

---

## 四、实验环境与准备

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

```bash
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` | 生成测试数据 |

验证：

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

> 若只做逻辑部分、不画图，`ipycanvas` 仍会被 `system/utils.py` 顶层导入，所以**必须安装**。

---

## 五、实验步骤

### 步骤 1：构建一棵二进制 Radix Trie

```python
from system.indexes.radix_trie import RadixTrie
from system.tests.test_indexing import PrefixDigitMapping

prefix_mapping = PrefixDigitMapping()
trie = RadixTrie[str, str](
    key_mapping=prefix_mapping,
    children_per_inner_node=2,
    number_of_inner_node_levels=3,
)
for k, v in [("110", "a"), ("101", "b"), ("010", "c"), ("011", "d"), ("111", "e")]:
    trie.put(k, v)
trie.show()
```

本机实测输出（已整理缩进）：

```text
RadixTrie:
  InnerNode {
    InnerNode {                        # 首位 = 0
      InnerNode {                      # 前缀 00
        LeafNode { values: [] },
        LeafNode { values: [] },
      }
      InnerNode {                      # 前缀 01
        LeafNode { values: [('010', 'c')] },
        LeafNode { values: [('011', 'd')] },
      }
    }
    InnerNode {                        # 首位 = 1
      InnerNode {                      # 前缀 10
        LeafNode { values: [] },
        LeafNode { values: [('101', 'b')] },
      }
      InnerNode {                      # 前缀 11
        LeafNode { values: [('110', 'a')] },
        LeafNode { values: [('111', 'e')] },
      }
    }
  }
```

**数一数**：7 个内部节点 + 8 个叶子，与 3.1 节的公式 $1+2+4=7$、$2^3=8$ 完全一致。8 个叶子里只有 5 个非空——3 个空叶子就是固定扇出的代价。

### 步骤 2：验证节点规模公式

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

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}")
```

期望输出：

```text
c=2 L=3: 内部节点    7  叶子     8  合计    15
c=2 L=4: 内部节点   15  叶子    16  合计    31
c=4 L=3: 内部节点   21  叶子    64  合计    85
c=4 L=4: 内部节点   85  叶子   256  合计   341
c=8 L=3: 内部节点   73  叶子   512  合计   585
```

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

### 步骤 3：构建圣诞树

```python
from system.utils import Vector, Triangle
from system.indexes.christmas_tree import ChristmasTree

triangle = Triangle(Vector(0, 0), Vector(300, 0), Vector(150, 300))
christmas_trie = ChristmasTree[Vector, str](
    children_per_inner_node=4,
    descriptor=triangle,
    number_of_inner_node_levels=3,
)
christmas_trie.show()
```

**注意这里换了什么、没换什么**：

- 换了描述符：`key_mapping=PrefixDigitMapping` → `descriptor=triangle`；
- 换了扇出：2 → 4（三角形细分成 4 个子三角形）；
- **没换结构**：仍然是"每层把描述符细分，每个孩子持有一份"。

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

### 步骤 4：验证"包含"判定

```python
for p in [(150, 100), (10, 10), (150, 290), (299, 1), (1, 299)]:
    print(p, triangle.contains(Vector(*p)))
```

期望输出：

```text
(150, 100) True
(10, 10) True
(150, 290) True
(299, 1) True
(1, 299) False
```

**自己再验几个边界点**：`(0,0)`、`(300,0)`、`(150,300)` 是三个顶点，`(150,0)` 在底边上。观察实现如何处理边界（不同实现对边界的归属可能不同，这是空间索引里一个真实的坑）。

### 步骤 5：观察描述符的细分

```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 个全等子三角形，正确做法应当取三条边的中点，得到 4 个边长为原来一半的小三角形，全部在原三角形内部。上面这份输出不符合这个预期。

**这是本实验最值得做的一件事**：不要因为它是"仓库自带的代码"就默认它是对的。请打开 `system/utils.py` 里 `Triangle.split_into_sub_descriptors()` 的源码，画出它的取点逻辑，判断问题出在哪，并尝试改成取三边中点的版本。改完重跑步骤 5，检查 4 个子三角形是否都非退化且落在原三角形内。

> 教学提示：这类"实现与原理不符"的情况在真实工程里很常见。发现它、定位它、修好它，比按部就班跑通一遍笔记本有价值得多。

### 步骤 6：比较三种节点工厂配置

```python
for config in ("inner", "buffered", "crystalball"):
    tree = ChristmasTree[Vector, str](
        children_per_inner_node=4,
        descriptor=triangle,
        number_of_inner_node_levels=3,
        inner_node_factory=ChristmasTree.InnerNodeFactory[Vector, str](config=config),
    )
    print(f"{config:12s} 构建完成")
```

三种配置都能构建成功（否则会抛异常）。要看出它们的差别，需要测构建耗时与后续访问耗时——见扩展任务 2。

### 步骤 7：（需要 Jupyter）画出树

下面这段依赖 `ipycanvas` 的画布，**只能在 Jupyter 里跑**，在纯 Python 脚本中会因为没有前端而无法显示：

```python
from ipycanvas import Canvas, hold_canvas

canvas = Canvas(width=300, height=300, sync_image_data=True)
display(canvas)
with hold_canvas(canvas):
    christmas_trie.draw(canvas, canvas_height=300)
```

---

## 六、观测记录表

| 观测项 | 公式 / 期望 | 你的实测 |
|---|---|---|
| 二进制 Trie（c=2, L=3）内部节点 | $1+2+4 = 7$ | |
| 二进制 Trie（c=2, L=3）叶子 | $2^3 = 8$ | |
| 存入 5 个键后非空叶子数 | 5 | |
| 空叶子数（固定扇出的代价） | 3 | |
| 圣诞树（c=4, L=3）内部节点 | $1+4+16 = 21$ | |
| 圣诞树（c=4, L=3）叶子 | $4^3 = 64$ | |
| `Triangle.contains((1, 299))` | False | |
| `split_into_sub_descriptors()` 返回个数 | 4 | |
| 其中退化（重复顶点）的子三角形个数 | 2（本机实测） | |
| 落在原三角形外的子三角形个数 | 1（本机实测） | |

| 标准 Trie vs Radix Trie（6 个键） | 节点数 |
|---|---|
| 标准 Trie | 11 |
| Radix Trie（路径压缩） | 9 |
| 省下 | 2 |

这两个数可以程序化复核——对同一组键分别数两棵树的节点：

```python
KEYS = ["CAR", "CAT", "CATS", "DOG", "DOGS", "DOT"]

# 标准 Trie：节点 = 出现过的所有前缀（含空串根）
prefixes = {k[:i] for k in KEYS for i in range(len(k) + 1)}
print("标准 Trie 节点数:", len(prefixes))     # 11

# Radix Trie：节点 = 根 + 键终点 + 分叉点（向下分出 ≥2 条边的位置）
def children(p):
    return {k[len(p)] for k in KEYS if k.startswith(p) and len(k) > len(p)}

radix = {p for p in prefixes if p == "" or p in KEYS or len(children(p)) >= 2}
print("Radix Trie 节点数:", len(radix))       # 9
```

---

## 七、思考题

1. 标准 Trie 的查找代价是 $O(\text{键长})$，B+ 树是 $O(\log n)$。当表里有 100 万行、键长固定为 10 时，哪个更快？请说明理由，并指出这个比较里隐含了什么假设。
2. 本实验的二进制 Trie 存 5 个键却用了 8 个叶子（3 个空）。若改用路径压缩，叶子数会变成多少？请画出来。
3. 圣诞树把扇出从 2 提到 4、层数保持 3，叶子数从 8 变成 64。如果目标是"把 300×300 的区域划分成边长约 10 的小格"，需要多少层、多少叶子？这个数字说明了什么？
4. 描述符（descriptor）这个抽象带来了什么好处？如果不用描述符、直接写死"按字符走"，圣诞树还能实现吗？代价是什么？
5. `buffered` 与 `crystalball` 都在"预计算"上做文章。请设想两种访问模式，分别说明哪种配置更合适；再设想一种两种都不合适的模式。
6. 步骤 5 发现细分结果可疑。请说明：如果把细分改成"取三边中点"，4 个子三角形的顶点坐标分别是什么？改完后，`contains` 判定还需要改吗？
7. 圣诞树递归细分得到的是**固定**的区域划分，而 R-tree 是**按需**分裂。请比较两者在"数据分布极不均匀"（比如 90% 的点挤在 5% 的面积里）时的表现。

---

## 八、思考题答案与解析

**第 1 题**

键长固定为 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 也踩过同一个坑——算法更优，但常数因子输给了语言内建实现。

**第 2 题**

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$ 成正比。

**第 3 题**

每次细分把边长减半（等边三角形分成 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、四叉树）从不预先细分到固定深度——它们按需分裂，数据稀疏的地方保持大区域，数据密集的地方才继续分。这也正是第 7 题要讨论的问题。

**第 4 题**

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

- 用 `PrefixDigitMapping`：按字符切，是字符串 Trie；
- 用 `Triangle`：按几何细分，是空间 Trie。

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

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

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

**第 5 题**

- **适合 `crystalball`**：构建一次、查询极多，且各层访问频率均匀（如长期服务的空间索引）。预先算好全部子描述符，查询时零计算。
- **适合 `buffered`**：查询分布不均匀，只有部分区域被频繁访问（如城市 POI 检索，市中心热、郊区冷）。按需缓存，冷区域永远不付计算代价。
- **适合 `inner`**：构建后只查询很少几次（如临时的一次性分析），或内存极度紧张。预计算的成本收不回来。

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

**第 6 题**

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

- $AB$ 中点 $M_{AB}(150, 0)$
- $AC$ 中点 $M_{AC}(75, 150)$
- $BC$ 中点 $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` 不需要改。** 重心坐标法对任意方向的三角形都成立，倒三角形也一样——关键是三个顶点不能共线（不能退化）。这也反证了步骤 5 里退化三角形的危害：`contains` 在退化三角形上会除零或给出无意义结果。

**第 7 题**

- **固定细分（圣诞树）**：无论数据怎么分布，都把区域划成同样大小的 $4^L$ 块。数据挤在 5% 面积里时，那 5% 里的块塞满了点（查找退化成在块内线性扫描），另外 95% 的块全是空的（白白占用节点）。$L$ 小则热点太挤，$L$ 大则空块太多——**永远两头不讨好**。
- **按需分裂（R-tree / 四叉树）**：数据密集的地方继续分裂，稀疏的地方保持大块。节点数与**数据量**成正比，而不是与"区域面积 / 最小粒度"成正比。热点区域自动获得更细的划分。

这正是 R-tree（Guttman, SIGMOD 1984）成为空间索引主流的原因，也是 PostgreSQL 的 GiST / SP-GiST 与 PostGIS 采用它的原因。

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

---

## 九、扩展任务（选做）

1. **修复细分逻辑。** 按第 6 题的坐标改 `Triangle.split_into_sub_descriptors()`，重跑步骤 5 验证 4 个子三角形都非退化且落在原三角形内，再递归画到第 3 层，看看是否得到 64 个整齐的小三角形。

2. **测量三种节点工厂的真实差别。** 分别用 `inner` / `buffered` / `crystalball` 构建 `c=4, L=4` 的圣诞树，测构建耗时；再随机查询 10,000 个点，测总耗时。把结果填成一张表，说明在什么访问模式下 `crystalball` 才值得。

3. **换成矩形描述符。** 实现一个 `Rectangle` 描述符（提供 `contains` 与"四分"细分），接入 `ChristmasTree`。这就是一棵四叉树（quadtree）。比较它与三角形版本在同样 $c$、$L$ 下的节点数与 `contains` 判定耗时。

4. **把圣诞树接到真实经纬度上。** 用实验 16 用到的 `notebooks/latitude_longitude.bin`（197,229 个点），用一个覆盖其经纬范围的大三角形作描述符，构建 `c=4, L=5` 的圣诞树，统计 1024 个叶子里的点数分布，验证"固定细分在数据不均匀时两头不讨好"。

---

## 十、常见错误与排查

| 现象 | 原因 | 解决办法 |
|---|---|---|
| `ModuleNotFoundError: No module named 'ipycanvas'` | `system/utils.py` 顶层导入 ipycanvas | `pip install ipycanvas` |
| `ModuleNotFoundError: No module named 'graphviz'` | `system/indexes/btree.py` 导入 graphviz，测试模块间接依赖 | `pip install graphviz`；若需真正渲染还要装 Graphviz 可执行文件 |
| `ModuleNotFoundError: No module named 'deprecation'` | `system/interfaces/stores.py` 依赖 | `pip install deprecation` |
| `ModuleNotFoundError: No module named 'faker'` | `system/tests/test_indexing.py` 依赖 | `pip install faker` |
| `Canvas` 相关代码在 .py 脚本里无输出 | ipycanvas 需要 Jupyter 前端 | 把绘图代码放到 notebook 里；逻辑部分（构建、`show()`、`contains`）在脚本里照常可用 |
| `trie.show()` 抛异常 | 底层用了 graphviz 渲染且缺少可执行文件 | 装 Graphviz 可执行文件并加入 PATH；或改用打印节点结构的方式（步骤 1 的缩进输出） |
| 叶子数与预期不符（如期待 5 个却得到 8 个） | 固定扇出 Trie 预先建满，与存了多少键无关 | 这是预期行为，正是路径压缩要解决的问题（见思考题 2） |
| 细分结果出现退化三角形或负坐标 | 仓库 `split_into_sub_descriptors()` 的实现问题（本机实测存在） | 见步骤 5 与扩展任务 1：改取三边中点 |
| 构建 `c=8, L=5` 时卡住 | 叶子数 $8^5 = 32768$，内部节点 4681，生成量大 | 降低 $c$ 或 $L$；或改用按需分裂的结构 |
| `ChristmasTree.InnerNodeFactory` 报类型错误 | 泛型参数未写全 | 写成 `ChristmasTree.InnerNodeFactory[Vector, str](config=...)` |