{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# 实验 03：B+ 树索引 —— 从一次分裂看懂数据库为什么\"矮而胖\"\n",
"\n",
"## 为什么做这个实验\n",
"\n",
"数据库为什么用\"矮而胖\"的多路平衡树，而不是教科书里那个优雅的二叉搜索树？本实验手工搭一棵 B+ 树，逐个键插入，亲眼看到**节点分裂、分隔键上提、叶链重接**这三件事是怎么发生的；再用同一棵树做一次等深分区，理解为什么\"B+ 树的内部节点就是数据分布的一个模型\"。\n",
"\n",
"反直觉的地方有两处。第一，**数据量涨 2000 倍，树高只加 2**：实测 N 从 100 涨到 200 000，树高从 2 变成 4（叶容量 64、内节点容量 63）。因为树高是关于叶子数的对数，不是关于键数的对数：\n",
"\n",
"$$h \\approx 1 + \\lceil \\log_F P \\rceil, \\qquad P \\approx \\frac{N}{L}$$\n",
"\n",
"（$N$ = 键总数，$L$ = 叶容量，$F$ = 内部节点扇出，$P$ = 叶子个数，$h$ = 层数，含内部节点层与叶层。）\n",
"\n",
"第二，**这套\"溢出后从正中切开\"的分裂策略，长期平均装填率只有约 50%**——一半的空间是空着的。真实数据库主动控制这个取舍：PostgreSQL 的 B-tree 索引默认 `fillfactor = 90`，建索引时每页只填到 90%，留出的空间用于吸收后续插入，代价是页数多约 11%（$1/0.9 \\approx 1.111$）。\n",
"\n",
"做完这个实验，你应该能回答：一次插入为什么会引发连锁分裂？叶链为什么是 B+ 树压过 B 树、成为数据库主流的关键？以及等深分区为什么可以\"抽样建树 + 全量计数\"两步完成，而不必先把全量数据排序。\n",
"\n",
"## 运行前准备\n",
"\n",
"1. Python 3.10 及以上。\n",
"2. 安装依赖（在仓库根目录执行）：\n",
"\n",
" ```bash\n",
" pip install numpy matplotlib jupyter\n",
" pip install graphviz # 可选：把树渲染成图\n",
" ```\n",
"\n",
" 注意 `graphviz` 这个 pip 包只是 Python 绑定，**真正画图需要系统里另装 Graphviz 可执行程序**（Windows 可从 graphviz.org 下载安装包，或 `winget install Graphviz`；装完把 `bin` 目录加进 `PATH`）。没装也不影响本实验：`show()` 会自动退化成逐层文本打印。\n",
"\n",
" 验证方式：\n",
"\n",
" ```python\n",
" import numpy, matplotlib, graphviz\n",
" print(\"环境 OK\")\n",
" ```\n",
"\n",
"3. 在 **`notebooks/` 目录下**打开本笔记本（`jupyter notebook notebooks/B-tree.ipynb`）。数据文件 `latitude_longitude.bin` 是用相对路径读取的，工作目录必须能直接看到它。\n",
"4. 若报 `ModuleNotFoundError: No module named 'system'`，说明仓库根目录没进 `sys.path`，重跑第一个代码单元格即可。"
],
"id": "d5e42456"
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"import sys, pathlib\n",
"\n",
"# Put the repo root (the directory containing `system/`) on sys.path so\n",
"# `from system...` works whether this notebook is opened from its own\n",
"# folder or from the repo root.\n",
"for _p in (pathlib.Path.cwd(), *pathlib.Path.cwd().parents):\n",
" if (_p / \"system\").is_dir():\n",
" if str(_p) not in sys.path:\n",
" sys.path.insert(0, str(_p))\n",
" break"
],
"id": "f8576985-0c69-46bf-812a-788fb2d6e43e"
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## 一、B+ 树的结构：三层各司其职\n",
"\n",
"| 组成部分 | 装什么 | 作用 |\n",
"| --- | --- | --- |\n",
"| 根 root | 分隔键 + 孩子指针 | 树的入口；根分裂是唯一让树长高的事件 |\n",
"| 内部节点 inner node | 只装分隔键 + 孩子指针，**不装数据** | 路标，负责把查找路由到正确的子树 |\n",
"| 叶子节点 leaf node | 键 + 值（这里值是行号/载荷） | 真正承载数据的地方，并且横向串成链表 |\n",
"\n",
"### 四个必须分清的术语\n",
"\n",
"| 术语 | 英文 | 含义 |\n",
"| --- | --- | --- |\n",
"| 扇出 | fan-out | 一个节点最多有多少个孩子，等于\"分隔键个数 + 1\" |\n",
"| 容量 | capacity | 一个节点最多放多少个键。本实验故意用小容量，方便肉眼观察 |\n",
"| 装填率 / 填充因子 | fill factor | 实际键数 ÷ 容量 |\n",
"| 分隔键 | separator / pivot key | 内部节点里划分子树范围的键，本身不携带数据行 |\n",
"\n",
"### 分裂与叶链\n",
"\n",
"**分裂（split）**：节点装满后再插入，就把节点一分为二，并把中间那个键**上提**到父节点当分隔键。若父节点也因此溢出，就继续向上——一次插入可能引发连锁分裂，一直到根。\n",
"\n",
"**叶链（leaf chain）**：所有叶子用 `next` / `previous` 双向指针首尾相接。有了它，范围查询只需要**一次**从根下降：找到起始键所在的叶子，之后顺着 `next` 一路向右走，完全不用回到父节点。这是 B+ 树压过 B 树的关键——B 树要中序遍历，来回上下走，产生大量随机 I/O。\n",
"\n",
"### 为什么是 B+ 而不是 B\n",
"\n",
"| 对比项 | B 树 | B+ 树 |\n",
"| --- | --- | --- |\n",
"| 内部节点是否存数据 | 存 | 不存，只放分隔键和指针 |\n",
"| 内部节点扇出 | 小（键 + 数据挤占空间） | 大（只剩键和指针） |\n",
"| 树高 | 相对高 | 相对矮 |\n",
"| 范围查询 | 中序遍历，来回上下 | 一次下降 + 沿叶链顺序扫 |\n",
"| 全索引扫描 | 中序遍历 | 直接从头走叶链 |\n",
"\n",
"设节点总空间为 $S$ 字节，一个\"键 + 行指针\"占 $k + p$ 字节，一个\"纯分隔键 + 孩子指针\"占 $k + c$ 字节（通常 $p > c$，因为行指针要定位到堆表里的具体位置）。则 B 树内部节点扇出 $\\approx S/(k+p)$，B+ 树 $\\approx S/(k+c)$——分母更小，扇出更大，树更矮。\n",
"\n",
"### 点查代价的口径\n",
"\n",
"一次点查的代价是两部分之和：\n",
"\n",
"$$\\text{cost} \\approx \\underbrace{h}_{\\text{节点访问次数（页 I/O）}} + \\underbrace{\\lceil \\log_2(\\text{叶内键数} + 1) \\rceil}_{\\text{叶内二分查找}}$$\n",
"\n",
"实测（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$）。"
],
"id": "8d14240e"
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## 二、手工搭一棵 B+ 树，观察一次分裂\n",
"\n",
"下面这一格不调用任何\"插入算法\"，而是**手工**把节点拼出来：先造 6 个叶子（`BPlusTree.Leaf(容量, 键列表, 值列表)`），用 `next` / `previous` 把它们串成叶链，再造 2 个内部节点和 1 个根（`BPlusTree.Inner(容量, 键列表, 孩子列表)`），最后挂到 `BPlusTree(3, 4)` 上——括号里的 3 是内部节点容量，4 是叶子容量。\n",
"\n",
"为什么要手工搭？因为这样你能**先看清一个稳定状态长什么样**，再看插入如何把它打破。\n",
"\n",
"初始结构（本机实测：树高 3、节点 9、叶 6、共 19 个键）：\n",
"\n",
"```text\n",
" root [32]\n",
" / \\\n",
" inner [13, 21] inner [38, 43]\n",
" / | \\ / | \\\n",
"[3 8 9 11] [14 18 20] [21 22 25 31] [31 34 36] [39 41] [44 46 49]\n",
" └────────────── 叶链 next/previous 双向贯穿 ──────────────┘\n",
"```\n",
"\n",
"两个观察点：\n",
"\n",
"- 内部节点只放分隔键（13、21、38、43、32），**没有任何数据**；\n",
"- 叶子之间横向相连，这是范围扫描能\"一次下降、顺序右移\"的物理基础。\n",
"\n",
"> 手工数据有个小瑕疵：键 `31` 同时出现在两个叶子里，`21` 既是分隔键又出现在叶内。真实索引不会有重复键；`consistency_check()` 只检查单个叶子内部是否重复，所以这里能通过。看结果时不必纠结它。\n",
"\n",
"搭好之后，代码依次插入 `50、53、55、58`，每插一次就渲染一次树，用来观察分裂。"
],
"id": "a3e4fd61"
},
{
"cell_type": "code",
"execution_count": 1,
"id": "2a74aea052a9b0a8",
"metadata": {
"ExecuteTime": {
"end_time": "2024-11-18T09:38:46.735145Z",
"start_time": "2024-11-18T09:38:46.078615Z"
}
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Initial B-tree:\n"
]
},
{
"data": {
"image/svg+xml": [
"\n",
"\n",
"\n",
"\n",
"\n"
],
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
},
{
"name": "stdout",
"output_type": "stream",
"text": [
"After inserting 50:\n"
]
},
{
"data": {
"image/svg+xml": [
"\n",
"\n",
"\n",
"\n",
"\n"
],
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
},
{
"name": "stdout",
"output_type": "stream",
"text": [
"After inserting 53:\n"
]
},
{
"data": {
"image/svg+xml": [
"\n",
"\n",
"\n",
"\n",
"\n"
],
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
},
{
"name": "stdout",
"output_type": "stream",
"text": [
"After inserting 55:\n"
]
},
{
"data": {
"image/svg+xml": [
"\n",
"\n",
"\n",
"\n",
"\n"
],
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
},
{
"name": "stdout",
"output_type": "stream",
"text": [
"After inserting 58:\n"
]
},
{
"data": {
"image/svg+xml": [
"\n",
"\n",
"\n",
"\n",
"\n"
],
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"from system.indexes.btree import BPlusTree\n",
"\n",
"import shutil\n",
"\n",
"\n",
"def show(tree):\n",
" \"\"\"渲染一棵 B+ 树。\n",
"\n",
" 检测到系统 Graphviz 可执行文件（dot）时用 graphviz 出图；\n",
" 没有安装时退化成逐层文本打印，保证后面的实验照常进行。\n",
" \"\"\"\n",
" if shutil.which(\"dot\") is None:\n",
" print(\"(未检测到系统 Graphviz 可执行文件 dot，改用文本打印)\")\n",
"\n",
" def label(node):\n",
" if isinstance(node, BPlusTree.CountingLeaf):\n",
" return f\"[count={node.put_calls}]\"\n",
" return \"[\" + \" \".join(str(k) for k in node.keys) + \"]\"\n",
"\n",
" level = [tree.root]\n",
" depth = 0\n",
" while level:\n",
" print(f\" level {depth}: \" + \" \".join(label(n) for n in level))\n",
" level = [c for n in level for c in getattr(n, \"children\", [])]\n",
" depth += 1\n",
" return\n",
" tree.show()\n",
"\n",
"# create leaves\n",
"leaf_1 = BPlusTree.Leaf(4, [3, 8, 9, 11], [1, 2, 3, 4])\n",
"leaf_2 = BPlusTree.Leaf(4, [14, 18, 20], [5, 6, 7])\n",
"leaf_3 = BPlusTree.Leaf(4, [21, 22, 25, 31], [8, 9, 10, 11])\n",
"leaf_4 = BPlusTree.Leaf(4, [31, 34, 36], [12, 13, 14])\n",
"leaf_5 = BPlusTree.Leaf(4, [39, 41], [15, 16])\n",
"leaf_6 = BPlusTree.Leaf(4, [44, 46, 49], [17, 18, 19])\n",
"\n",
"# connect leaves\n",
"leaf_1.next = leaf_2\n",
"leaf_2.previous = leaf_1\n",
"leaf_2.next = leaf_3\n",
"leaf_3.previous = leaf_2\n",
"leaf_3.next = leaf_4\n",
"leaf_4.previous = leaf_3\n",
"leaf_4.next = leaf_5\n",
"leaf_5.previous = leaf_4\n",
"leaf_5.next = leaf_6\n",
"leaf_6.previous = leaf_5\n",
"\n",
"# create inner nodes\n",
"inner_1 = BPlusTree.Inner(3, [13, 21], [leaf_1, leaf_2, leaf_3])\n",
"inner_2 = BPlusTree.Inner(3, [38, 43], [leaf_4, leaf_5, leaf_6])\n",
"\n",
"# create root node\n",
"root = BPlusTree.Inner(3, [32], [inner_1, inner_2])\n",
"\n",
"# create B-tree\n",
"bplustree = BPlusTree[int, int](3, 4)\n",
"bplustree.root = root\n",
"print(\"Initial B-tree:\")\n",
"show(bplustree)\n",
"\n",
"# insert values\n",
"bplustree.put(50, 20)\n",
"print(\"After inserting 50:\")\n",
"show(bplustree)\n",
"bplustree.put(53, 21)\n",
"print(\"After inserting 53:\")\n",
"show(bplustree)\n",
"bplustree.put(55, 22)\n",
"print(\"After inserting 55:\")\n",
"show(bplustree)\n",
"bplustree.put(58, 23)\n",
"print(\"After inserting 58:\")\n",
"show(bplustree)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### 这四次插入分别发生了什么\n",
"\n",
"下面把实测到的每一步拆开。叶容量 4 意味着：叶子**装满 4 个不分裂，插入第 5 个才溢出**。\n",
"\n",
"**1. `put(50, 20)` —— 无分裂**\n",
"\n",
"50 走路由落到最右叶 `[44, 46, 49]`，它只有 3 个键（容量 4，未满），直接插入 → `[44, 46, 49, 50]`。树高、节点数都不变。\n",
"\n",
"**2. `put(53, 21)` —— 叶子分裂，分隔键上提**\n",
"\n",
"目标叶已满，插入后变成 5 个键 `[44, 46, 49, 50, 53]`。从中点切开（`mid = 5 // 2 = 2`）：\n",
"\n",
"```text\n",
"左半 [44, 46] 右半 [49, 50, 53] 上提的分隔键 = 原 keys[2] = 49\n",
"```\n",
"\n",
"父节点 `[38, 43]` 只有 2 个键（容量 3，未满），直接把 49 插进去 → `[38, 43, 49]`，孩子从 3 个变 4 个。注意右半的第一个键正好等于上提的分隔键——**叶分裂时上提的键在右半保留**，这是 B+ 树的常见做法之一。同时代码会重接叶链：左半接原来的前驱、右半接原来的后继，中间两个新叶子互指。\n",
"\n",
"这一轮后：节点 10、叶 7。\n",
"\n",
"**3. `put(55, 22)` —— 无分裂**\n",
"\n",
"落到 `[49, 50, 53]`（未满）→ `[49, 50, 53, 55]`。\n",
"\n",
"**4. `put(58, 23)` —— 叶子分裂，并引发父节点分裂**\n",
"\n",
"目标叶已满 → 溢出成 `[49, 50, 53, 55, 58]` → 切成 `[49, 50]` 和 `[53, 55, 58]`，分隔键 53 上提。\n",
"\n",
"但这一次父节点的键已经是 `[38, 43, 49]`，**3 个 = 容量 3，父节点也满了**。于是连锁发生：先把 53 插进去（键暂时变 4 个），再分裂父节点——左 `[38, 43]` 带 3 个孩子、右 `[53]` 带 2 个孩子，分隔键 49 上提到根。根的键从 `[32]` 变成 `[32, 49]`，孩子从 2 个变 3 个。\n",
"\n",
"这一轮后：节点 12、叶 8，**树高仍然是 3**。\n",
"\n",
"关键结论：**只有根分裂才会让树长高一层。** 父节点分裂只是让树变宽。真正让树长高的事件在别处——是\"根也满了\"的那一次；而根满的前提是下面每一层都满过一遍，这就是 B+ 树能长期保持矮胖的原因。\n",
"\n",
"（内部节点分裂与叶分裂有一处不同：`Inner.split` 用的是 `keys[mid+1:]`，即上提的那个键**从下层消失**，只留在父节点当分隔键。叶分裂则保留在右半。）\n",
"\n",
"想再看一遍叶链的作用，可以自己加一格跑 `list(bplustree.get_all_in_range(21, 36))`：它会返回 `[8, 9, 10, 11, 12, 13, 14]`，横跨三个叶子，但只做了一次从根下降。"
],
"id": "3abdc344"
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## 三、B+ 树的另一个用途：给数据做等深分区\n",
"\n",
"到这里换一个问题。**等深分区（equi-depth partitioning）**要求把值域切成若干段，使每段落到的记录数尽量相等。它是并行查询切分、直方图统计、数据倾斜检测的共同基础。\n",
"\n",
"最直接的做法是\"排全序再均分\"，但那要对 N 条记录做一次 $O(N \\log N)$ 的外排序。B+ 树给了两步走的办法，省掉这次排序：\n",
"\n",
"1. 抽 $m$ 条样本（$m \\ll N$）建一棵**内节点很小、叶子很大**的树，整棵树常驻内存；\n",
"2. 把全量数据流式灌进这棵树，落到叶子上——但叶子不存数据，只记数。\n",
"\n",
"每个叶子的计数值就是一个桶的深数，叶子之间的边界自然就是分区边界。**内节点的分隔键，就是对数据分位数的一次估计**——这就是\"内部节点是数据分布的一个模型\"这句话的具体含义。\n",
"\n",
"代价也要说清楚：切分点来自样本，样本偏差会让桶深不均；样本量越大，桶边界越接近真实分位数。"
],
"id": "a4eaf83c"
},
{
"cell_type": "code",
"execution_count": 2,
"id": "beeac6c4d93a08da",
"metadata": {
"ExecuteTime": {
"end_time": "2024-11-21T18:22:30.414995Z",
"start_time": "2024-11-21T18:22:29.856485Z"
}
},
"outputs": [
{
"data": {
"image/png": "iVBORw0KGgoAAAANSUhEUgAAA9YAAAEyCAYAAAAfo0gPAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjkuMiwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy8hTgPZAAAACXBIWXMAAA9hAAAPYQGoP6dpAABQLklEQVR4nO3de1gWdf7/8ReKgKmAWJwSjfKYx0Sj28w0STzUZplluUnF6q+CSt1Vo4N5qCgzzyZrB61vmh12tVZLQ01tE01QNrUibS0svXFbFUQTUOb3Rxf3esuNHO4z9/NxXXPtzsxnZt5DbwfeM5/PjJ9hGIYAAAAAAECdNHB3AAAAAAAAeDMKawAAAAAA7EBhDQAAAACAHSisAQAAAACwA4U1AAAAAAB2oLAGAAAAAMAOFNYAAAAAANiBwhoAAAAAADtQWAMAAAAAYAcK6xqaOnWq/Pz89Ouvv7o7FIB8hNuQe3AXcg/uQu7BXcg970Jh7QG++uorPfLII4qLi1OjRo3k5+d30fZvvPGGOnbsqKCgILVt21YLFixwUaTwBffff7/8/PwqTR06dKjUtry8XDNnzlRsbKyCgoLUtWtXvfvuu26IGvWBs66Fv/zyi+666y6FhoYqODhYt912m/7973874xTgpTwh9/jd7pu8Kfe4ltYv9TX33HotNVAjzz77rCHJ+M9//uOUfTdq1MiIi4sz2rVrZ1zsP0tGRoYhyRg+fLixZMkS47777jMkGS+++KLD44LncmY+JiUlGYGBgcb//d//WU0ff/xxpbZPPPGEIckYM2aMsWTJEmPo0KGGJOPdd991eFzwDN52LTx58qTRtm1bIzw83HjppZeM2bNnGzExMUbLli2NX3/91eHnAOepz7nH73bPRu5xLXUXcs+7rqUU1jXkzMQ2m83G6dOnDcMwjJSUlCoT+/Tp00aLFi2MoUOHWi0fNWqU0aRJE+PYsWMOjw2eydmFdZMmTapt9/PPPxuNGjUyUlJSLMvKy8uNG264wWjZsqVx9uxZh8cG9/O2a+FLL71kSDK++uory7Jvv/3WaNiwoZGWlubwc4Dz1Nfc43e75yP3uJa6C7nnXddSuoLb4aefflKbNm3UuXNnFRQU1Hk/ERERaty4cbXtPv/8c/33v//VI488YrU8JSVFp06d0tq1a+scA7yfo/Kxwrlz51RUVFTl+o8++khlZWVW+ejn56eHH35YP//8s7KysuyOAd7Bk6+FH374oXr16qVevXpZlnXo0EEDBgzQ+++/X+dY4RnqQ+7xu907+VrucS31HOSe515LKazr6IcfflDfvn3VrFkzbd68WRERETp9+rR+/fXXaqfjx4/X6Zi7d++WJPXs2dNqeVxcnBo0aGBZD9/j6Hw8ffq0goODFRISorCwMKWkpKi4uNiqze7du9WkSRN17NjRavm1115rWY/6z5OvheXl5fr6668rtZN+z9MffvhBJ0+erFMMcL/6knv8bvc+vpZ7XEs9B7ln/z6dyd/pR6iHvvvuOw0YMECXX3651q9fr+bNm0uSZs6cqWnTplW7fevWrfXjjz/W+rhHjhxRw4YNFR4ebrU8ICBALVq00OHDh2u9T3g/R+djVFSUJk2apB49eqi8vFzr1q3Tq6++qn/961/avHmz/P1/v2wcOXJEERERlV52ERUVJUnkow/w9GvhsWPHVFJSYsnJ852fp+3bt691DHCv+pR7/G73Lr6Ye1xLPQO555h9OhOFdS3t3btXd999t9q0aaNPP/1UwcHBlnWjR49Wnz59qt1HTbpd2PLbb78pICDA5rqgoCD99ttvddovvJcz8jE9Pd1qfuTIkWrXrp2eeuopffjhhxo5cqSk3/MxMDCw0v6CgoIs61F/ecO1sOJ/ydP6pb7lHr/bvYev5h7XUvcj97zjWkphXUu33nqrIiIitH79ejVt2tRq3ZVXXqkrr7zSacdu3LixSktLba47c+ZMnf/BwHu5Kh/Hjx+vZ555Rhs2bLAU1o0bN1ZJSUmltmfOnLGsR/3lDdfCiv8lT+uX+pZ7/G73Hr6ae1xL3Y/c845rKWOsa2n48OH64YcftHz58krriouLZTabq53+85//1OnYUVFROnfunI4ePWq1vLS0VP/9738VHR1dp/3Ce7kqHxs3bqwWLVro2LFjlmVRUVEym80yDMOq7ZEjRySJfKznvOFaGBYWpsDAQEtOno889V71Lff43e49fDX3uJa6H7nnHddSnljX0ssvvyx/f3898sgjatasme69917LulmzZjl1jEP37t0lSdnZ2RoyZIhleXZ2tsrLyy3r4TtclY8nT57Ur7/+qssuu8yyrHv37nr99df17bff6uqrr7Ys37Fjh2U96i9vuBY2aNBAXbp0UXZ2dqV97NixQ1deeaWaNWtW6+PDvepb7vG73Xv4au5xLXU/cs87rqUU1rXk5+enJUuW6OTJk0pKSlLTpk31hz/8QZLzxzjcdNNNCgsL0+LFi60SZvHixbrkkks0dOjQOu0X3svR+XjmzBmVlZVV+gU5Y8YMGYahQYMGWZbddtttGj9+vF599VUtXLhQkmQYhjIyMnT55Zerd+/ejjhFeChvuRbeeeedeuKJJ5SdnW15U2heXp42bdqkv/zlL3U6PtyrvuUev9u9hy/nHtdS9yL3vORa6vQvZdcTF36gvbS01BgyZIgRGBhobNy40a59//jjj8aMGTOMGTNmGPHx8YYky/zbb79t1XbRokWGJOPOO+80XnvtNWP06NGGJOP555+3KwZ4F2fl48GDB43Q0FDj4YcfNubNm2fMmzfPGDJkiCHJGDRokHHu3Dmr9hMnTjQkGWPHjjVee+01Y+jQoYYkY/ny5XadHzyXt10Li4qKjKuuusoIDw83Zs6cacyZM8eIiYkxoqOjjaNHj9oVL1yrPucev9s9G7nHtdRdyD3vupZSWNfQhYltGIZx+vRp48YbbzSaNm1qbN++vc77/vzzzw1JNqcbb7yxUvslS5YY7du3NwICAoyrrrrKmDNnjlFeXl7n48P7OCsfjx8/bvzxj3802rRpY1xyySVGYGCg0alTJ+OFF14wSktLK7U/d+6c8cILLxitW7c2AgICjE6dOhnvvPNOnc8Lns8br4WHDh0y7rzzTiM4ONho2rSpccsttxj79++vc5xwj/qee/xu91zkXu33Cccg95y3T2fwM4wL3jwEAAAAAABqjLeCAwAAAABgBwprAAAAAADsQGENAAAAAIAdKKwBAAAAALADhTUAAAAAAHagsAYAAAAAwA7+7g6gJsrLy3X48GE1a9ZMfn5+7g4HVTAMQydPnlR0dLQaNKi/92zIR+9APsKTkI/wNL6Qk+Sj9/CFfJTISW9R13z0isL68OHDiomJcXcYqKFDhw6pZcuW7g7DachH70I+wpOQj/A09TknyUfvU5/zUSInvU1t89ErCutmzZpJ+v3kgoOD3RwNqlJUVKSYmBjLf6/6inz0DuQjPAn5CE/jCzlJPnoPX8hHiZz0FnXNR68orCu6SgQHB5OEXqC+d20hH70L+QhPQj7C09TnnCQfvU99zkeJnPQ2tc3H+juIAQAAAAAAF6CwBgAAAADADhTWAAAAAADYgcIaAAAAAAA71KqwTk9PV69evdSsWTOFh4dr2LBhysvLq3a7Dz74QB06dFBQUJC6dOmiTz75pM4BA/a64oor5OfnV2lKSUlxd2gAAAAAvFCtCustW7YoJSVF27dvV2ZmpsrKyjRw4ECdOnWqym22bdume+65R8nJydq9e7eGDRumYcOGae/evXYHD9TFzp07deTIEcuUmZkpSRoxYoSbIwMAAADgjWr1ua1169ZZzS9btkzh4eHKyclR3759bW4zb948DRo0SBMnTpQkzZgxQ5mZmVq4cKEyMjLqGDZQd5dddpnV/IsvvqirrrpKN954o5siAgAAAODN7BpjXVhYKEkKCwursk1WVpYSEhKsliUmJiorK6vKbUpKSlRUVGQ1Ac5QWlqqd955Rw8++GCV36ojHwEAAABcTK2eWJ+vvLxc48aN0/XXX6/OnTtX2c5sNisiIsJqWUREhMxmc5XbpKena9q0aXUNrU7mZH5fo3bjb27n5Egqq0lsjo7LHcd0h9WrV+vEiRO6//77q2xT03zkvxPqK0++PqJ+4ZoGX8f1Fp6EfKydOj+xTklJ0d69e7Vy5UpHxiNJSktLU2FhoWU6dOiQw48BSNIbb7yhwYMHKzo6uso25CMAAACAi6nTE+vU1FStWbNGW7duVcuWLS/aNjIyUgUFBVbLCgoKFBkZWeU2gYGBCgwMrEtoQI399NNP2rBhg/7+979ftB35CAAAAOBiavXE2jAMpaamatWqVdq0aZNiY2Or3cZkMmnjxo1WyzIzM2UymWoXKeBgS5cuVXh4uIYOHeruUADAblu3btWtt96q6Oho+fn5afXq1VW2feihh+Tn56e5c+daLT927JhGjRql4OBghYaGKjk5WcXFxc4NHF7HVbn29ddf64YbblBQUJBiYmI0c+ZMJ5wNADhGrQrrlJQUvfPOO1qxYoWaNWsms9kss9ms3377zdJm9OjRSktLs8w//vjjWrdunV555RV99913mjp1qrKzs5Wamuq4swBqqby8XEuXLlVSUpL8/ev8qgEA8BinTp1St27dtGjRoou2W7VqlbZv325zCMyoUaO0b98+ZWZmWnqmjR071lkhw0u5IteKioo0cOBAtW7dWjk5OXr55Zc1depULVmyxOHnAwCOUKuKYvHixZKkfv36WS1funSp5eVP+fn5atDgf/V67969tWLFCj399NN68skn1bZtW61evfqiLzwDnG3Dhg3Kz8/Xgw8+6O5QAMAhBg8erMGDB1+0zS+//KJHH31U69evr9Rb59tvv9W6deu0c+dO9ezZU5K0YMECDRkyRLNmzbJZHJWUlKikpMQyz1cTfIMrcm358uUqLS3Vm2++qYCAAHXq1Em5ubmaPXt2lTd7HJ2PvLgJnoR89Hy17gpuazr/jcqbN2/WsmXLrLYbMWKE8vLyVFJSor1792rIkCGOiB2os4EDB8owDLVrx8UHgG8oLy/Xfffdp4kTJ6pTp06V1mdlZSk0NNRS6EhSQkKCGjRooB07dtjcZ3p6ukJCQixTTEyM0+KH93BErmVlZalv374KCAiwtElMTFReXp6OHz9u87jkY/3kSUMPPvjgA3Xo0EFBQUHq0qWLPvnkE0ecIuoJu75jDQAAvMNLL70kf39/PfbYYzbXm81mhYeHWy3z9/dXWFhYlZ/I5KsJsMURuVbV51or1tlCPtZPnjL0YNu2bbrnnnuUnJys3bt3a9iwYRo2bJj27t3ruJOFV2NwKQAA9VxOTo7mzZunXbt2yc/Pz2H75asJuJCzcq0myMf6yVOGHsybN0+DBg3SxIkTJUkzZsxQZmamFi5cqIyMDCecObwNT6wBAKjnvvjiCx09elStWrWSv7+//P399dNPP+nPf/6zrrjiCkm/fx7z6NGjVtudPXtWx44du+gnMoHzOSrXqvpca8U6oIKrhh5kZWUpISHBat+JiYnKysqqMraSkhIVFRVZTai/KKwBAKjn7rvvPn399dfKzc21TNHR0Zo4caLWr18v6ffPY544cUI5OTmW7TZt2qTy8nLFx8e7K3R4GUflmslk0tatW1VWVmZpk5mZqfbt26t58+auPSl4NFcNPaiqTVVDEyTG/fsauoIDAFAPFBcX68CBA5b5gwcPKjc3V2FhYWrVqpVatGhh1b5Ro0aKjIxU+/btJUkdO3bUoEGDNGbMGGVkZKisrEypqakaOXKkzTGL8F2uyLV7771X06ZNU3JysiZPnqy9e/dq3rx5mjNnjutOFB7PnUMPaiItLU0TJkywzBcVFVFc12M8sQYAJ3HEm0yBmsrOztY111yja665RpI0YcIEXXPNNZoyZUqN97F8+XJ16NBBAwYM0JAhQ9SnTx++G4xKXJFrISEh+uyzz3Tw4EHFxcXpz3/+s6ZMmcJ31WHFlUMPqmpzsaEJgYGBCg4OtppQf/HEGgCcpOJNpg8++KDuuOOOKttd7E2mQE3169dPhmHUuP2PP/5YaVlYWJhWrFjhwKhQH7kq17p27aovvviituHBh9x33302xz3fd999euCBByRZDz2Ii4uTZHvowVNPPaWysjI1atRIUuWhByaTSRs3btS4ceMsx8rMzJTJZHL2acJLUFgDgJPY+yZTW0pKSlRSUmKZ50UoAID6zFOGHjz++OO68cYb9corr2jo0KFauXKlsrOz6dUDC7qCA4CbVPcmU1t4EQoAwJd4ytCD3r17a8WKFVqyZIm6deumDz/8UKtXr1bnzp0dd7LwajyxBgA3qe5NprbwIhQAgC/xpKEHI0aM0IgRI2ocC3wLhTUAuEFd32QaGBiowMBAJ0YGeLY5md/XqN34m9s5ORIAAP6HruAA4AY1eZMpAAAAvANPrAHADWryJlMAAAB4BwprAHASe99kCgAAAO9AYQ0ATpKdna3+/ftb5iteOpaUlKRly5a5KSoAAAA4GoU1ADiJI95kCgAAAM/Hy8sAAAAAALADhTUAAAAAAHagKzgAAABQRzX5tjrfVQfqP55YAwAAAABgBwprAAAAAADsQGENAAAAAIAdKKzhc3755Rf98Y9/VIsWLdS4cWN16dJF2dnZ7g4LAAAAgJfi5WXwKcePH9f111+v/v3769NPP9Vll12m/fv3q3nz5u4ODQAAAICXorCGT3nppZcUExOjpUuXWpbFxsa6MSLAOWryllrJc99U6+3xAwAA30JhDZ/y8ccfKzExUSNGjNCWLVt0+eWX65FHHtGYMWOq3KakpEQlJSWW+aKiIleECgBwAT6VBABwBApr+JR///vfWrx4sSZMmKAnn3xSO3fu1GOPPaaAgAAlJSXZ3CY9PV3Tpk1zyPFr+hTOHXhCCAAAANQNhTV8Snl5uXr27KkXXnhBknTNNddo7969ysjIqLKwTktL04QJEyzzRUVFiomJcUm8AAAAQE3RC8d9eCs4fEpUVJSuvvpqq2UdO3ZUfn5+ldsEBgYqODjYagIAT7N161bdeuutio6Olp+fn1avXm1ZV1ZWpsmTJ6tLly5q0qSJoqOjNXr0aB0+fNhqH8eOHdOoUaMUHBys0NBQJScnq7i42MVnAk/nqlz7+uuvdcMNNygoKEgxMTGaOXOmK04PAOqEwho+5frrr1deXp7Vsu+//16tW7d2U0QA4BinTp1St27dtGjRokrrTp8+rV27dumZZ57Rrl279Pe//115eXn6wx/+YNVu1KhR2rdvnzIzM7VmzRpt3bpVY8eOddUpwEu4IteKioo0cOBAtW7dWjk5OXr55Zc1depULVmyxOnnBwB1QWENnzJ+/Hht375dL7zwgg4cOKAVK1ZoyZIlSklJcXdoAGCXwYMH67nnntPtt99eaV1ISIgyMzN11113qX379rruuuu0cOFC5eTkWHrsfPvtt1q3bp1ef/11xcfHq0+fPlqwYIFWrlxZ6WljhZKSEhUVFVlNqP9ckWvLly9XaWmp3nzzTXXq1EkjR47UY489ptmzZ1cZF/lYP3lSD4kPPvhAHTp0UFBQkLp06aJPPvnEKecM70RhDZ/Sq1cvrVq1Su+++646d+6sGTNmaO7cuRo1apS7QwMAlyosLJSfn59CQ0MlSVlZWQoNDVXPnj0tbRISEtSgQQPt2LHD5j7S09MVEhJimXj/BGypS65lZWWpb9++CggIsLRJTExUXl6ejh8/bvM45GP95Ck9JLZt26Z77rlHycnJ2r17t4YNG6Zhw4Zp7969zjt5eBVeXgafc8stt+iWW25xdxgA4DZnzpzR5MmTdc8991jeG2E2mxUeHm7Vzt/fX2FhYTKbzTb3w8sdUZ265prZbFZsbKxVm4iICMu65s2bVzoW+Vg/DR48WIMHD7a5rqKHxPkWLlyoa6+9Vvn5+WrVqpWlh8TOnTstN3MWLFigIUOGaNasWYqOjrbqIREQEKBOnTopNzdXs2fPthTg8+bN06BBgzRx4kRJ0owZM5SZmamFCxcqIyPDiT8BeAueWAMA4EPKysp01113yTAMLV682K598XJHXIwjc60myEdIzushkZWVpYSEBKtjJSYmKisrq8pYGJ7gW3hiDQCAj6godH766Sdt2rTJqvCIjIzU0aNHrdqfPXtWx44dU2RkpKtD9Sg1+XyNxCdszmdvrkVGRqqgoMCqTcW8r+cjqubMHhJms9my7Pw2VfXokX4fnjBt2jS7zwvegSfWAOAkjnjhCuAoFYXO/v37tWHDBrVo0cJqvclk0okTJ5STk2NZtmnTJpWXlys+Pt7V4cKLOSLXTCaTtm7dqrKyMkubzMxMtW/f3mY3cMDVPSRqIi0tTYWFhZbp0KFD7g4JTkRhDQBO4ogXrgA1VVxcrNzcXOXm5kqSDh48qNzcXOXn56usrEx33nmnsrOztXz5cp07d05ms1lms1mlpaWSpI4dO2rQoEEaM2aMvvrqK3355ZdKTU3VyJEjFR0d7cYzg6dxRa7de++9CggIUHJysvbt26f33ntP8+bNsxpDDVQ4v4dEZmamU3pIVNXmYj0oGJ7gW+gKDgBOYu8LV4DayM7OVv/+/S3zFQVIUlKSpk6dqo8//liS1L17d6vtPv/8c/Xr10/S7584Sk1N1YABA9SgQQMNHz5c8+fPd0n88B6uyLWQkBB99tlnSklJUVxcnC699FJNmTKF76qjkvN7SHz++ecX7SERFxcnyXYPiaeeekplZWVq1KiRpMo9JEwmkzZu3Khx48ZZ9p2ZmSmTyeSCs3Ssmg5vQe1QWAOAh7jwhSu2lJSUqKSkxDLPi1BQoV+/fjIMo8r1F1tXISwsTCtWrHBkWKiHXJVrXbt21RdffFHr+FC/FBcX68CBA5b5ih4SYWFhioqK0p133qldu3ZpzZo1lh4S0u85FhAQYNVDIiMjQ2VlZTZ7SEybNk3JycmaPHmy9u7dq3nz5mnOnDmW4z7++OO68cYb9corr2jo0KFauXKlsrOzrT7JBd9GYQ0AHsDWC1dscfSLULhrDQDwZJ7SQ6J3795asWKFnn76aT355JNq27atVq9erc6dOzvpzOFtKKwBwM1q88IVvtMKAPAlntRDYsSIERoxYkS1x4NvorAGADe62CdpbAkMDFRgYKCLogMAAEBNUFgDgJtU98IVAED9wLAboP6jsAYAJ7H3hSsAANhSk0J9/M3tXBAJgAoU1gDgJI544QqAuuEJIQC4Bjd6fkdhDQBO4ogXrgAAAMDzNXB3AAAAAAAAeLNaF9Zbt27VrbfequjoaPn5+Wn16tUXbb9582b5+flVmirGEgIAAAAA4M1qXVifOnVK3bp106JFi2q1XV5eno4cOWKZwsPDa3toAAAAAAA8Tq3HWA8ePFiDBw+u9YHCw8MVGhpao7YlJSUqKSmxzBcVFdX6eAAAAAAAuILLxlh3795dUVFRuvnmm/Xll19etG16erpCQkIsU0xMjIuiBAAAAACgdpxeWEdFRSkjI0N/+9vf9Le//U0xMTHq16+fdu3aVeU2aWlpKiwstEyHDh1ydpgAAAAAANSJ0z+31b59e7Vv394y37t3b/3www+aM2eO/u///s/mNoGBgQoMDHR2aAAAAAAA2M0tn9u69tprdeDAAXccGgAAAAAAh3L6E2tbcnNzFRUV5Y5DAwDcbE7m9+4OAQAAwKFq/cS6uLhYubm5ys3NlSQdPHhQubm5ys/Pl/T7+OjRo0db2s+dO1cfffSRDhw4oL1792rcuHHatGmTUlJSHHMGQC1MnTq10jfVO3To4O6wAAAAAHixWj+xzs7OVv/+/S3zEyZMkCQlJSVp2bJlOnLkiKXIlqTS0lL9+c9/1i+//KJLLrlEXbt21YYNG6z2AbhSp06dtGHDBsu8v79bOm4AAAAAqCdqXVH069dPhmFUuX7ZsmVW85MmTdKkSZNqHRjgLP7+/oqMjKxxe76rDgAAAOBieFQHn7N//35FR0crKChIJpNJ6enpatWqVZXt09PTNW3aNBdG6FiOHs9ak/2Nv7mdQ48JAAAAeDK3vBUccJf4+HgtW7ZM69at0+LFi3Xw4EHdcMMNOnnyZJXb8F11AN5g69atuvXWWxUdHS0/Pz+tXr3aar1hGJoyZYqioqLUuHFjJSQkaP/+/VZtjh07plGjRik4OFihoaFKTk5WcXGxC88C3sBVufb111/rhhtuUFBQkGJiYjRz5kxnnxoA1BmFNXzK4MGDNWLECHXt2lWJiYn65JNPdOLECb3//vtVbhMYGKjg4GCrCQA8zalTp9StWzctWrTI5vqZM2dq/vz5ysjI0I4dO9SkSRMlJibqzJkzljajRo3Svn37lJmZqTVr1mjr1q0aO3asq04BXsIVuVZUVKSBAweqdevWysnJ0csvv6ypU6dqyZIlTj8/AKgLuoLDp4WGhqpdu3Z8Vx2A1xs8eLAGDx5sc51hGJo7d66efvpp3XbbbZKkt99+WxEREVq9erVGjhypb7/9VuvWrdPOnTvVs2dPSdKCBQs0ZMgQzZo1S9HR0S47F3g2V+Ta8uXLVVpaqjfffFMBAQHq1KmTcnNzNXv2bG72APBIPLGGTysuLtYPP/zAd9UB1GsHDx6U2WxWQkKCZVlISIji4+OVlZUlScrKylJoaKil0JGkhIQENWjQQDt27LC535KSEhUVFVlN8G2OyrWsrCz17dtXAQEBljaJiYnKy8vT8ePHbR6bfKyfPGnowQcffKAOHTooKChIXbp00SeffOLw84X3orCGT/nLX/6iLVu26Mcff9S2bdt0++23q2HDhrrnnnvcHRoAOI3ZbJYkRUREWC2PiIiwrDObzQoPD7da7+/vr7CwMEubC6WnpyskJMQyxcTEOCF6eBNH5ZrZbLa5j/OPcSHysX7ylKEH27Zt0z333KPk5GTt3r1bw4YN07Bhw7R3717nnTy8Cl3B4VN+/vln3XPPPfrvf/+ryy67TH369NH27dt12WWXuTs0APA6aWlpmjBhgmW+qKiIYgZuU9N8dPTXMuBcnjL0YN68eRo0aJAmTpwoSZoxY4YyMzO1cOFCZWRk2IyPT7b6Fp5Yw6esXLlShw8fVklJiX7++WetXLlSV111lbvDAgCnioyMlCQVFBRYLS8oKLCsi4yM1NGjR63Wnz17VseOHbO0uRAvd8SFHJVrkZGRNvdx/jEuRD76HlcOPcjKyrI6TkWbiuPYQi8K30JhDQBO4ohxYYAjxMbGKjIyUhs3brQsKyoq0o4dO2QymSRJJpNJJ06cUE5OjqXNpk2bVF5ervj4eJfHDO/kqFwzmUzaunWrysrKLG0yMzPVvn17NW/e3EVnA0/nyqEHVbWpamiCxCdbfQ2FNQA4iSPGhQE1VVxcrNzcXOXm5kr6/UlObm6u8vPz5efnp3Hjxum5557Txx9/rD179mj06NGKjo7WsGHDJEkdO3bUoEGDNGbMGH311Vf68ssvlZqaqpEjR/JGcFhxRa7de++9CggIUHJysvbt26f33ntP8+bNs+rqDXg6elH4FsZYA4CT2DsuzBbGa6Eq2dnZ6t+/v2W+ogBJSkrSsmXLNGnSJJ06dUpjx47ViRMn1KdPH61bt05BQUGWbZYvX67U1FQNGDBADRo00PDhwzV//nyXnws8mytyLSQkRJ999plSUlIUFxenSy+9VFOmTOFTW7By/tCD87/wUlBQoO7du1vaOGLoQVVtqhqaAN9DYQ0AblDduLCqCuv09HRNmzbNVWHCi/Tr10+GYVS53s/PT9OnT9f06dOrbBMWFqYVK1Y4IzzUI67Kta5du+qLL76oc5yo/84felBRSFcMPXj44YclWQ89iIuLk2R76MFTTz2lsrIyNWrUSFLloQcmk0kbN27UuHHjLMfPzMy0DHGoK16mV3/QFRwA3KAm48JsYbwWAMCXeMrQg8cff1zr1q3TK6+8ou+++05Tp05Vdna2UlNTXf0jgYfiiTUAeJHAwEAFBga6OwygVngiA6CuPGXoQe/evbVixQo9/fTTevLJJ9W2bVutXr1anTt3dsFPAd6AwhoA3KAm48IAAPB1njT0YMSIERoxYsTFA4bPois4ALhBTT5JAwAAAO/AE2sAcJLi4mIdOHDAMl8xLiwsLEytWrWyjAtr27atYmNj9cwzz1iNCwMAoK5qOgRj/M3tnBwJ4BsorAHASRwxLgwAAMDb+cKNHgprAHASR4wLAwAAgOdjjDUAAAAAAHagsAYAAAAAwA50BQcAAHAAXxhDCACwjSfWAAAAAADYgcIaAAAAAAA7UFgDAAAAAGAHCmsAAAAAAOxAYQ0AAAAAgB14KzgAwCFq+kZkdxyzJm9h5o3OAACgrnhiDQAAAACAHSisAQAAAACwA4U1fNqLL74oPz8/jRs3zt2hAAAAAPBSjLGGz9q5c6f++te/qmvXru4OBQAAK4z5BwDvwhNr+KTi4mKNGjVKr732mpo3b37RtiUlJSoqKrKaAAAAAKAChTV8UkpKioYOHaqEhIRq26anpyskJMQyxcTEuCBCAHCsc+fO6ZlnnlFsbKwaN26sq666SjNmzJBhGJY2hmFoypQpioqKUuPGjZWQkKD9+/e7MWp4I0fl2rFjxzRq1CgFBwcrNDRUycnJKi4udvXpAECNUFjD56xcuVK7du1Senp6jdqnpaWpsLDQMh06dMjJEQKA47300ktavHixFi5cqG+//VYvvfSSZs6cqQULFljazJw5U/Pnz1dGRoZ27NihJk2aKDExUWfOnHFj5PA2jsq1UaNGad++fcrMzNSaNWu0detWjR071h2nBADVorCGTzl06JAef/xxLV++XEFBQTXaJjAwUMHBwVYTAHibbdu26bbbbtPQoUN1xRVX6M4779TAgQP11VdfSfr9CeLcuXP19NNP67bbblPXrl319ttv6/Dhw1q9erV7g4dXcUSuffvtt1q3bp1ef/11xcfHq0+fPlqwYIFWrlypw4cPu/Hs4Glc2UPi66+/1g033KCgoCDFxMRo5syZLjlHeAcKa/iUnJwcHT16VD169JC/v7/8/f21ZcsWzZ8/X/7+/jp37py7QwQAp+jdu7c2btyo77///aVY//rXv/TPf/5TgwcPliQdPHhQZrPZaohMSEiI4uPjlZWVZXOfvIMCtjgi17KyshQaGqqePXta2iQkJKhBgwbasWOHzeOSj77JVT0kioqKNHDgQLVu3Vo5OTl6+eWXNXXqVC1ZssSl5wvPxVvB4VMGDBigPXv2WC174IEH1KFDB02ePFkNGzZ0U2QA4FxPPPGEioqK1KFDBzVs2FDnzp3T888/r1GjRkmSzGazJCkiIsJqu4iICMu6C6Wnp2vatGnODRxexxG5ZjabFR4ebrXe399fYWFh5COsnN9DQpKuuOIKvfvuu1X2kJCkt99+WxEREVq9erVGjhxp6SGxc+dOy82cBQsWaMiQIZo1a5aio6O1fPlylZaW6s0331RAQIA6deqk3NxczZ49myEKkMQTa/iYZs2aqXPnzlZTkyZN1KJFC3Xu3Nnd4cHH1KT7GuAo77//vpYvX64VK1Zo165deuuttzRr1iy99dZbdd4n76CALc7ItZogH32Tq3pIZGVlqW/fvgoICLC0SUxMVF5eno4fP24zNnpR+BaeWAOAm1R0X3vrrbfUqVMnZWdn64EHHlBISIgee+wxd4eHembixIl64oknNHLkSElSly5d9NNPPyk9PV1JSUmKjIyUJBUUFCgqKsqyXUFBgbp3725zn4GBgQoMDHR67PAujsi1yMhIHT161Gq/Z8+e1bFjxyzbX4h89E2u6iFhNpsVGxtbaR8V62x9vpVeFL6FJ9bweZs3b9bcuXPdHQZ8UHUv+AEc6fTp02rQwPrXfsOGDVVeXi5Jio2NVWRkpDZu3GhZX1RUpB07dshkMrk0Vng3R+SayWTSiRMnlJOTY2mzadMmlZeXKz4+3gVnAW/hrh4SNUEvCt/CE2sAcJPevXtryZIl+v7779WuXTtL97XZs2dXuU1JSYlKSkos83QrQ03deuutev7559WqVSt16tRJu3fv1uzZs/Xggw9Kkvz8/DRu3Dg999xzatu2rWJjY/XMM88oOjpaw4YNc2/w8CqOyLWOHTtq0KBBGjNmjDIyMlRWVqbU1FSNHDlS0dHRbjw7eBpX9ZCIjIxUQUGBVZuKeXpRQKKwBgC3qa77mi10K0NdLViwQM8884weeeQRHT16VNHR0fp//+//acqUKZY2kyZN0qlTpzR27FidOHFCffr00bp162r8eUJAclyuLV++XKmpqRowYIAaNGig4cOHa/78+e44JXiw2vSQqCikK3pIPPzww5Kse0jExcVJqtxDwmQy6amnnlJZWZkaNWokScrMzFT79u1tdgOH76GwBgA3Ob/7WsXbRceNG6fo6GglJSXZ3CYtLU0TJkywzBcVFSkmJsZVIcOLNWvWTHPnzr3o0Bc/Pz9Nnz5d06dPd11gqHcclWthYWFasWKFEyJEfeKqHhL33nuvpk2bpuTkZE2ePFl79+7VvHnzNGfOHHedOjwMhTUAuEl13ddsoVsZAAD/46oeEiEhIfrss8+UkpKiuLg4XXrppZoyZQqf2oIFhTUAuEl13dcAAMDFubKHRNeuXfXFF1/UNVTUc7V+K/jWrVt16623Kjo6Wn5+flq9enW122zevFk9evRQYGCg2rRpo2XLltUhVACoXyq6r61du1Y//vijVq1apdmzZ+v22293d2gAAACohVoX1qdOnVK3bt20aNGiGrU/ePCghg4dqv79+1vGD/7pT3/S+vXrax0sANQnCxYs0J133qlHHnlEHTt21F/+8hf9v//3/zRjxgx3hwYAAIBaqHVX8MGDB2vw4ME1bp+RkaHY2Fi98sorkn5/OcA///lPzZkzR4mJibU9PADUGzXpvgYAAADP5/Qx1llZWUpISLBalpiYqHHjxlW5Dd9pBQAAAJxvTub3DtvX+JvbOWxf8E01zUdPzDWnF9Zms1kRERFWyyIiIlRUVKTffvtNjRs3rrRNTb/TWpMfvCf+0Cs48kLmyH0BAAAAAGqu1mOsXSEtLU2FhYWW6dChQ+4OCQAAAAAAm5z+xDoyMlIFBQVWywoKChQcHGzzabXEd1oBAAAAAN7D6U+sTSaTNm7caLUsMzNTJpPJ2YcGAAAAAMDpal1YFxcXKzc3V7m5uZJ+/5xWbm6u8vPzJf3ejXv06NGW9g899JD+/e9/a9KkSfruu+/06quv6v3339f48eMdcwYAAAAAALhRrbuCZ2dnq3///pb5CRMmSJKSkpK0bNkyHTlyxFJkS1JsbKzWrl2r8ePHa968eWrZsqVef/11PrUFAAAAAKg1T3yJda0L6379+skwjCrXL1u2zOY2u3fvru2hAAAAAADweB75VnAAAAAAALwFhTUAAAAAAHagsAYAAAAAwA4U1gAAAAAA2IHCGgAAAAAAO1BYw6csXrxYXbt2VXBwsIKDg2UymfTpp5+6OywAAAAAXozCGj6lZcuWevHFF5WTk6Ps7GzddNNNuu2227Rv3z53hwYAAADAS9X6O9aAN7v11lut5p9//nktXrxY27dvV6dOndwUFQAAAABvxhNr+Kxz585p5cqVOnXqlEwmU5XtSkpKVFRUZDUBgDf65Zdf9Mc//lEtWrRQ48aN1aVLF2VnZ1vWG4ahKVOmKCoqSo0bN1ZCQoL279/vxojhrRyRa8eOHdOoUaMUHBys0NBQJScnq7i42NWnAgA1whNr+Jw9e/bIZDLpzJkzatq0qVatWqWrr766yvbp6emaNm2aCyP0fnMyv3fo/sbf3M6h+wN80fHjx3X99derf//++vTTT3XZZZdp//79at68uaXNzJkzNX/+fL311luKjY3VM888o8TERH3zzTcKCgpyY/T1i6OvkZ7GUbk2atQoHTlyRJmZmSorK9MDDzygsWPHasWKFe46NXioX375RZMnT9ann36q06dPq02bNlq6dKl69uwp6fcbOc8++6xee+01nThxQtdff70WL16stm3bWvZx7NgxPfroo/rHP/6hBg0aaPjw4Zo3b56aNm1qafP1118rJSVFO3fu1GWXXaZHH31UkyZNcvn5wjNRWMPntG/fXrm5uSosLNSHH36opKQkbdmypcriOi0tTRMmTLDMFxUVKSYmxlXhAoBDvPTSS4qJidHSpUsty2JjYy3/3zAMzZ07V08//bRuu+02SdLbb7+tiIgIrV69WiNHjnR5zPBOjsi1b7/9VuvWrdPOnTstxdGCBQs0ZMgQzZo1S9HR0a49KXgsV93IKSoq0sCBA5WQkKCMjAzt2bNHDz74oEJDQzV27Fi3nDs8C13B4XMCAgLUpk0bxcXFKT09Xd26ddO8efOqbB8YGGh5i3jFBADe5uOPP1bPnj01YsQIhYeH65prrtFrr71mWX/w4EGZzWYlJCRYloWEhCg+Pl5ZWVk298lQGdjiiFzLyspSaGiopaiWpISEBDVo0EA7duyweVzy0TedfyPn2muvVWxsrAYOHKirrrpKUuUbOV27dtXbb7+tw4cPa/Xq1ZJkuZHz+uuvKz4+Xn369NGCBQu0cuVKHT58WJK0fPlylZaW6s0331SnTp00cuRIPfbYY5o9e7a7Th0ehsIaPq+8vFwlJSXuDgM+qrpxiICj/Pvf/7Z0fVy/fr0efvhhPfbYY3rrrbckSWazWZIUERFhtV1ERIRl3YXS09MVEhJimejNA8kxuWY2mxUeHm613t/fX2FhYeQjrLjqRk5WVpb69u2rgIAAS5vExETl5eXp+PHjNmPjZo9vobCGT0lLS9PWrVv1448/as+ePUpLS9PmzZs1atQod4cGH1TRfa1Ro0b69NNP9c033+iVV16x6r4GOEp5ebl69OihF154Qddcc43Gjh2rMWPGKCMjo877TEtLU2FhoWU6dOiQAyOGt3JGrtUE+eibXHUjx2w229zH+ce4EDd7fAtjrOFTjh49qtGjR+vIkSMKCQlR165dtX79et18883uDg0+qLpxiIAjRUVFVXqXRMeOHfW3v/1NkhQZGSlJKigoUFRUlKVNQUGBunfvbnOfgYGBCgwMdE7A8FqOyLXIyEgdPXrUah9nz57VsWPHLNtfiHz0TeXl5erZs6deeOEFSdI111yjvXv3KiMjQ0lJSW6Njff0+BaeWMOnvPHGG/rxxx9VUlKio0ePasOGDRTVcJvquq/ZQrcy1NX111+vvLw8q2Xff/+9WrduLen3mzqRkZHauHGjZX1RUZF27Nhx0U8SAhdyRK6ZTCadOHFCOTk5ljabNm1SeXm54uPjXXAW8BZV3cjJz8+XZH0j53wFBQWWdTW5kRMZGWlzH+cf40K8p8e38MQaANykovvahAkT9OSTT2rnzp167LHHFBAQUOVddj7/Vjf1/fNGNTF+/Hj17t1bL7zwgu666y599dVXWrJkiZYsWSJJ8vPz07hx4/Tcc8+pbdu2ljfnRkdHa9iwYe4NHl7FEbnWsWNHDRo0yNKFvKysTKmpqRo5ciRvBIeV2tzIqegRUXEj5+GHH5ZkfSMnLi5OUuUbOSaTSU899ZTKysrUqFEjSVJmZqbat2/PEC5I4ok1ALhNXcYhMoYQddWrVy+tWrVK7777rjp37qwZM2Zo7ty5Vu+YmDRpkh599FGNHTtWvXr1UnFxsdatW8c3rFErjsq15cuXq0OHDhowYICGDBmiPn36WIpzoML48eO1fft2vfDCCzpw4IBWrFihJUuWKCUlRZL1jZyPP/5Ye/bs0ejRo6u8kfPVV1/pyy+/rHQj595771VAQICSk5O1b98+vffee5o3b55VV2/4Np5YA4CbVDcO0RbGEMIet9xyi2655ZYq1/v5+Wn69OmaPn26C6NCfeSIXAsLC7N8QxioSsWNnLS0NE2fPl2xsbE2b+ScOnVKY8eO1YkTJ9SnTx+bN3JSU1M1YMAANWjQQMOHD9f8+fMt60NCQvTZZ58pJSVFcXFxuvTSSzVlyhS+YQ0LCmsAcJPquq8BAIDquepGTteuXfXFF1/UOU7Ub3QFBwA3qa77GgAAALwDhTUAuElNxiECAADA89EVHADcqLruawAAAPB8PLEGAAAAAMAOFNYAAAAAANiBwhoAAAAAADtQWAMAAAAAYAcKawAAAAAA7EBhDQAAAACAHSisAQAAAACwA4U1AAAAAAB2oLAGAAAAAMAOFNYAAAAAANiBwhoAAAAAADtQWAMAAAAAYAcKawAAAAAA7EBhDQAAAACAHSisAQAAAACwA4U1fEp6erp69eqlZs2aKTw8XMOGDVNeXp67wwIAAADgxSis4VO2bNmilJQUbd++XZmZmSorK9PAgQN16tQpd4cGAAAAwEtRWMOnrFu3Tvfff786deqkbt26admyZcrPz1dOTo67QwMAl3rxxRfl5+encePGWZadOXNGKSkpatGihZo2barhw4eroKDAfUGiXqhrruXn52vo0KG65JJLFB4erokTJ+rs2bMujh4AaobCGj6tsLBQkhQWFlZlm5KSEhUVFVlNAODNdu7cqb/+9a/q2rWr1fLx48frH//4hz744ANt2bJFhw8f1h133OGmKFEf1DXXzp07p6FDh6q0tFTbtm3TW2+9pWXLlmnKlCmuPgV4GWfeyNm8ebN69OihwMBAtWnTRsuWLXPBGcFbUFjDZ5WXl2vcuHG6/vrr1blz5yrbpaenKyQkxDLFxMS4MEpI0pzM76ud6gNbfwwAjlZcXKxRo0bptddeU/PmzS3LCwsL9cYbb2j27Nm66aabFBcXp6VLl2rbtm3avn27GyOGt7In1z777DN98803euedd9S9e3cNHjxYM2bM0KJFi1RaWuquU4KHc+aNnIMHD2ro0KHq37+/cnNzNW7cOP3pT3/S+vXrXXZ+8GwU1vBZKSkp2rt3r1auXHnRdmlpaSosLLRMhw4dclGE8CVV/TEAOFpKSoqGDh2qhIQEq+U5OTkqKyuzWt6hQwe1atVKWVlZNvdFjx5cjD25lpWVpS5duigiIsLSJjExUUVFRdq3b5/N45GPvs3ZN3IyMjIUGxurV155RR07dlRqaqruvPNOzZkzxy3nC89DYQ2flJqaqjVr1ujzzz9Xy5YtL9o2MDBQwcHBVhPgSFX9MQA42sqVK7Vr1y6lp6dXWmc2mxUQEKDQ0FCr5RERETKbzTb3R48eVMXeXDObzVZFdcX6inW2kI++zdk3crKysirtOzExscobjxI3e3wNhTV8imEYSk1N1apVq7Rp0ybFxsa6OySgyj8GbOGXNOrq0KFDevzxx7V8+XIFBQU5ZJ/06IEtzsi1miAffZcrbuRU1aaoqEi//fabzbi42eNb6lRYL1q0SFdccYWCgoIUHx+vr776qsq2y5Ytk5+fn9XkyosscL6UlBS98847WrFihZo1ayaz2Syz2VzlBRFwtov9MWALv6RRVzk5OTp69Kh69Oghf39/+fv7a8uWLZo/f778/f0VERGh0tJSnThxwmq7goICRUZG2twnPXpgiyNyLTIystLLpSrmyUecz103cmqCmz2+xb+2G7z33nuaMGGCMjIyFB8fr7lz5yoxMVF5eXkKDw+3uU1wcLDy8vIs835+fnWPGLDD4sWLJUn9+vWzWr506VLdf//9rg8IPq3ij4HMzMwa/zGQlpamCRMmWOaLiooorlEjAwYM0J49e6yWPfDAA+rQoYMmT56smJgYNWrUSBs3btTw4cMlSXl5ecrPz5fJZHJHyKiBmr68cfzN7Zwcyf84ItdMJpOef/55HT161PL3ZWZmpoKDg3X11Ve77Fzg+c6/kVPh3Llz2rp1qxYuXKj169dbbuSc/9T6whs5Fz4ovPBGTlU3e4KDg9W4cWObsQUGBiowMNDuc4R3qHVhPXv2bI0ZM0YPPPCApN8H8q9du1ZvvvmmnnjiCZvb+Pn5VXl3EXAlwzDcHQJgUd0fAyUlJWrYsKHVNvySRl01a9as0hcQmjRpohYtWliWJycna8KECQoLC1NwcLAeffRRmUwmXXfdde4IGV7KEbk2cOBAXX311brvvvs0c+ZMmc1mPf3000pJSeEaCCuuupFjMpn0ySefWB0nMzOTG4+wqFVhXVpaqpycHKWlpVmWNWjQQAkJCRcduF9cXKzWrVurvLxcPXr00AsvvKBOnTpV2b6kpEQlJSWWecYQAqiPqvtj4MKiGnC2OXPmqEGDBho+fLhKSkqUmJioV1991d1hoR6qLtcaNmyoNWvW6OGHH5bJZFKTJk2UlJSk6dOnuzFqeCJX3ch56KGHtHDhQk2aNEkPPvigNm3apPfff19r16517QnDY9WqsP7111917tw5mwP3v/vuO5vbtG/fXm+++aa6du2qwsJCzZo1S71799a+ffuqfBtzenq6pk2bVpvQAMDr1OSPAcCZNm/ebDUfFBSkRYsWadGiRe4JCPVWXXKtdevWlZ4QAnXhiBs5sbGxWrt2rcaPH6958+apZcuWev3115WYmOiOU4IHqnVX8NoymUxWXSR69+6tjh076q9//atmzJhhcxvGEAIAAACoC2fdyOnXr592797tiBBRD9WqsL700kvVsGFDmwP3azqGulGjRrrmmmt04MCBKtswhhCAr7rwjwEAAAB4vlp9bisgIEBxcXHauHGjZVl5ebk2btxY44H7586d0549exQVFVW7SAEAAAAA8EC17go+YcIEJSUlqWfPnrr22ms1d+5cnTp1yvKW8NGjR+vyyy+3fJN1+vTpuu6669SmTRudOHFCL7/8sn766Sf96U9/cuyZAAAAAADgBrUurO+++2795z//0ZQpU2Q2m9W9e3etW7fO8kKz/Px8NWjwvwfhx48f15gxY2Q2m9W8eXPFxcVp27ZtfIMQAAAAAFAv1OnlZampqUpNTbW57sLxgXPmzNGcOXPqchgAAAAAADxercZYAwAAAAAAaxTWAAAAAADYgcIaAAAAAAA7UFgDAAAAAGCHOr28DAAAXzUn8/satRt/czsnRwIAADwFT6wBAAAAALADhTUAAAAAAHagsAYAAAAAwA4U1gAAAAAA2IHCGgAAAAAAO1BYAwAAAABgBwprAAAAAADswHesAQAAANhtTub3NWo3/uZ2To4EcD2eWAMAAAAAYAcKa/icrVu36tZbb1V0dLT8/Py0evVqd4cEAAAAwItRWMPnnDp1St26ddOiRYvcHQoAuEx6erp69eqlZs2aKTw8XMOGDVNeXp5VmzNnziglJUUtWrRQ06ZNNXz4cBUUFLgpYngrR+Vafn6+hg4dqksuuUTh4eGaOHGizp4968pTgRdwZb5t3rxZPXr0UGBgoNq0aaNly5Y5+/TgRSis4XMGDx6s5557Trfffru7QwFq9AcB4AhbtmxRSkqKtm/frszMTJWVlWngwIE6deqUpc348eP1j3/8Qx988IG2bNmiw4cP64477nBj1PBGjsi1c+fOaejQoSotLdW2bdv01ltvadmyZZoyZYo7TgkezFX5dvDgQQ0dOlT9+/dXbm6uxo0bpz/96U9av369S88XnouXlwHVKCkpUUlJiWW+qKjIjdGgvqn4g6BXr146e/asnnzySQ0cOFDffPONmjRp4u7wUI+sW7fOan7ZsmUKDw9XTk6O+vbtq8LCQr3xxhtasWKFbrrpJknS0qVL1bFjR23fvl3XXXddpX1yfYQtjsi1zz77TN988402bNigiIgIde/eXTNmzNDkyZM1depUBQQEVDou+eibXJVvGRkZio2N1SuvvCJJ6tixo/75z39qzpw5SkxMdPl5w/PwxBqoRnp6ukJCQixTTEyMu0NCPbJu3Trdf//96tSpk7p166Zly5YpPz9fOTk57g4N9VxhYaEkKSwsTJKUk5OjsrIyJSQkWNp06NBBrVq1UlZWls19cH1ETdQl17KystSlSxdFRERY2iQmJqqoqEj79u2zeRzyEZLz8i0rK8tqHxVtqro+Sr/f7CkqKrKaUH/xxBqoRlpamiZMmGCZLyoq4pc1nObCPwguxBMZOEJ5ebnGjRun66+/Xp07d5Ykmc1mBQQEKDQ01KptRESEzGazzf1wfUR16pprZrPZqsipWF+xzhbyEc7Mt6raFBUV6bffflPjxo0rxZOenq5p06Y55NxQe67+/BuFNVCNwMBABQYGujsM+ABbfxBciF/ScISUlBTt3btX//znP+3aD9dHVMdRuVYT5CNcmW81wc0e30JXcADwEBV/EKxcubLKNmlpaSosLLRMhw4dcmGEqA9SU1O1Zs0aff7552rZsqVleWRkpEpLS3XixAmr9gUFBYqMjHRxlKgP7Mm1yMjISm9trpgnH2GLs/OtqjbBwcE2n1ZLv9/sCQ4OtppQf1FYw+cUFxcrNzdXubm5kn5/y2Nubq7y8/PdGxh8WlV/EFyIX9KoK8MwlJqaqlWrVmnTpk2KjY21Wh8XF6dGjRpp48aNlmV5eXnKz8+XyWRydbjwYo7INZPJpD179ujo0aOWNpmZmQoODtbVV1/tmhOBV3BVvplMJqt9VLTh+ogKdAWHz8nOzlb//v0t8xVddJKSkvgeIVzOMAw9+uijWrVqlTZv3lzpDwLAUVJSUrRixQp99NFHatasmWXcYEhIiBo3bqyQkBAlJydrwoQJCgsLU3BwsB599FGZTCabbwQHquKIXBs4cKCuvvpq3XfffZo5c6bMZrOefvpppaSk0N0bVlyVbw899JAWLlyoSZMm6cEHH9SmTZv0/vvva+3atW47d3gWCmv4nH79+skwDHeHAUiq/g8CwFEWL14s6fdr4PmWLl2q+++/X5I0Z84cNWjQQMOHD1dJSYkSExP16quvujhSeDtH5FrDhg21Zs0aPfzwwzKZTGrSpImSkpI0ffp0V50GvISr8i02NlZr167V+PHjNW/ePLVs2VKvv/46n9qCBYU1ALhRTf4gAByhJjcUg4KCtGjRIi1atMgFEaG+clSutW7dWp988okjQ0M95Mp869evn3bv3l3rGOEbKKwBwI3oPQEAAOD9eHkZAAAAAAB2oLAGAAAAAMAOFNYAAAAAANiBwhoAAAAAADtQWAMAAAAAYAcKawAAAAAA7EBhDQAAAACAHSisAQAAAACwA4U1AAAAAAB2oLAGAAAAAMAOFNYAAAAAANiBwhoAAAAAADtQWAMAAAAAYAcKawAAAAAA7EBhDQAAAACAHSisAQAAAACwA4U1AAAAAAB2oLAGAAAAAMAOFNYAAAAAANiBwhoAAAAAADvUqbBetGiRrrjiCgUFBSk+Pl5fffXVRdt/8MEH6tChg4KCgtSlSxd98skndQoWcJTa5jDgTOQjPA05CU9CPsKTkI+oSq0L6/fee08TJkzQs88+q127dqlbt25KTEzU0aNHbbbftm2b7rnnHiUnJ2v37t0aNmyYhg0bpr1799odPFAXtc1hwJnIR3gachKehHyEJyEfcTF+hmEYtdkgPj5evXr10sKFCyVJ5eXliomJ0aOPPqonnniiUvu7775bp06d0po1ayzLrrvuOnXv3l0ZGRk2j1FSUqKSkhLLfGFhoVq1aqVDhw4pODjYsnzRpgPVxptyU5sanVdN9lWb/TnymJ7qwp9FUVGRYmJidOLECYWEhLgpqurVNocdmY9wHvKRfPQ05+ekt+SjVLucJB+9hy9cI8lH7+EL+SjVLCfJR/dzWD4atVBSUmI0bNjQWLVqldXy0aNHG3/4wx9sbhMTE2PMmTPHatmUKVOMrl27VnmcZ5991pDE5KXToUOHapNWLlWXHCYfvXsiH5k8afLkfDSM2uck+ej9kyfnJPnoe1N9ykfDICe9faptPvqrFn799VedO3dOERERVssjIiL03Xff2dzGbDbbbG82m6s8TlpamiZMmGCZLy8v17Fjx9SiRQudPHlSMTExle4+eoqKOxy+GJ9hGDp58qSio6Mdul9HqksOe0s+elLueUIsvpiPfn5+To23LjwhF9yp4vzz8/Pl5+fn0fko1T4nyUfvcv75N2vWrN5dI70pH305F22dO7+z3ctX87Gq865rPtaqsHaVwMBABQYGWi0LDQ2VJEsSBgcHe/R/eF+Nz5O779SVt+UjsfyPr+WjJ3N3LrhbSEhIvTx/8tE7VZx/fbtGemM++nIuXnju9S0fJe/LSV/NR1vnXZd8rNXLyy699FI1bNhQBQUFVssLCgoUGRlpc5vIyMhatQecqS45DDgL+QhPQ07Ck5CP8CTkI6pTq8I6ICBAcXFx2rhxo2VZeXm5Nm7cKJPJZHMbk8lk1V6SMjMzq2wPOFNdchhwFvIRnoachCchH+FJyEdUp9ZdwSdMmKCkpCT17NlT1157rebOnatTp07pgQcekCSNHj1al19+udLT0yVJjz/+uG688Ua98sorGjp0qFauXKns7GwtWbKkTgEHBgbq2WefrdStwlMQn+erLodrw5N+nsTinRyZj57I13PBG8+/PuekN/73cCRvPP/6mo/e+N/CUbz53MnH+sXh512Xt+ItWLDAaNWqlREQEGBce+21xvbt2y3rbrzxRiMpKcmq/fvvv2+0a9fOCAgIMDp16mSsXbu2LocFHOZiOQy4GvkIT0NOwpOQj/Ak5COqUuvvWAMAAAAAgP+p1RhrAAAAAABgjcIaAAAAAAA7UFgDAAAAAGAHCmsAAAAAAOzgMYX1iy++KD8/P40bN06S9OOPP8rPz8/m9MEHH1S5n/vvv79S+0GDBtUppqlTp1baV4cOHSzrz5w5o5SUFLVo0UJNmzbV8OHDK300/kKGYWjKlCmKiopS48aNlZCQoP379zs8vmPHjunRRx9V+/bt1bhxY7Vq1UqPPfaYCgsLL7pPR/78vJ07c9KTco88Q3Wcka/epLrz79evX6X1Dz30kBsjrt98PR8lctJT+HIukoOeyVdz0lX5WOvvWDvDzp079de//lVdu3a1LIuJidGRI0es2i1ZskQvv/yyBg8efNH9DRo0SEuXLrXM2/Ntsk6dOmnDhg2WeX////3Ixo8fr7Vr1+qDDz5QSEiIUlNTdccdd+jLL7+scn8zZ87U/Pnz9dZbbyk2NlbPPPOMEhMT9c033ygoKMhh8R0+fFiHDx/WrFmzdPXVV+unn37SQw89pMOHD+vDDz+86D4d+fPzVp6Qk56Ue+QZquPofPU2Fzt/SRozZoymT59umb/kkktcFpsv8vV8lMhJT+HLuUgOeiZfzUlX5KPbC+vi4mKNGjVKr732mp577jnL8oYNGyoyMtKq7apVq3TXXXepadOmF91nYGBgpW3ryt/f3+a+CgsL9cYbb2jFihW66aabJElLly5Vx44dtX37dl133XWVtjEMQ3PnztXTTz+t2267TZL09ttvKyIiQqtXr9bIkSMdFl/nzp31t7/9zTJ/1VVX6fnnn9cf//hHnT17tlIync+RPz9v5Ck56Um5R56hOo7MV29U1flXuOSSS8h3F/L1fJTISU/hy7lIDnomX81JV+Sj27uCp6SkaOjQoUpISLhou5ycHOXm5io5ObnafW7evFnh4eFq3769Hn74Yf33v/+tc3z79+9XdHS0rrzySo0aNUr5+fmWeMrKyqzi7tChg1q1aqWsrCyb+zp48KDMZrPVNiEhIYqPj69ym7rGZ0thYaGCg4MvWuxIjv35eSNPyUlPyj3yDNVxZL56o+r+jSxfvlyXXnqpOnfurLS0NJ0+fdpNkfoGX89HiZz0FL6ci+SgZ/LVnHRFPrr1ifXKlSu1a9cu7dy5s9q2b7zxhjp27KjevXtftN2gQYN0xx13KDY2Vj/88IOefPJJDR48WFlZWWrYsGGt4ouPj9eyZcvUvn17HTlyRNOmTdMNN9ygvXv3ymw2KyAgQKGhoVbbREREyGw229xfxfKIiIgab1PX+Jo1a2bV9tdff9WMGTM0duzYi+7TkT8/b+QpOelJuUeeoTqOzldvU92/kXvvvVetW7dWdHS0vv76a02ePFl5eXn6+9//7u7Q6yVfz0eJnPQUvpyL5KBn8tWcdFk+Gm6Sn59vhIeHG//6178sy2688Ubj8ccfr9T29OnTRkhIiDFr1qxaH+eHH34wJBkbNmywJ1zDMAzj+PHjRnBwsPH6668by5cvNwICAiq16dWrlzFp0iSb23/55ZeGJOPw4cNWy0eMGGHcddddDo3vfIWFhca1115rDBo0yCgtLa3VPh358/N0npyTnpR75BmqY2++eruq/o1U2LhxoyHJOHDggIsj802+no+GQU56Cl/ORXLQM/lqTjorH93WFTwnJ0dHjx5Vjx495O/vL39/f23ZskXz58+Xv7+/zp07Z2n74Ycf6vTp0xo9enStj3PllVfq0ksv1YEDB+yOOTQ0VO3atdOBAwcUGRmp0tJSnThxwqpNQUFBlf3zK5Zf+Ha9i21T1/gqnDx5UoMGDVKzZs20atUqNWrUqFb7dOTPz9N5ck56Uu6RZ6iOvfnq7Wz9GzlffHy8JJHvLuLr+SiRk57Cl3ORHPRMvpqTzspHtxXWAwYM0J49e5Sbm2uZevbsqVGjRik3N9eqO+gbb7yhP/zhD7rssstqfZyff/5Z//3vfxUVFWV3zMXFxfrhhx8UFRWluLg4NWrUSBs3brSsz8vLU35+vkwmk83tY2NjFRkZabVNUVGRduzYUeU2dY2vYt8DBw5UQECAPv744zq9ddyRPz9P58k56Um5R56hOvbmq7e78N/IhXJzcyWJfHcRX89HiZz0FL6ci+SgZ/LVnHRaPjricbqj2Op2u3//fsPPz8/49NNPbW7Tvn174+9//7thGIZx8uRJ4y9/+YuRlZVlHDx40NiwYYPRo0cPo23btsaZM2dqHc+f//xnY/PmzcbBgweNL7/80khISDAuvfRS4+jRo4ZhGMZDDz1ktGrVyti0aZORnZ1tmEwmw2QyVRmfYRjGiy++aISGhhofffSR8fXXXxu33XabERsba/z2228Oja+wsNCIj483unTpYhw4cMA4cuSIZTp79qxLfn71gbty0pNyjzxDdRyRr97sYud/4MABY/r06UZ2drZx8OBB46OPPjKuvPJKo2/fvu4Ou97y9Xw0DHLSU/hyLpKDnslXc9JV+ejxhXVaWpoRExNjnDt3zuY2koylS5cahvH7uNeBAwcal112mdGoUSOjdevWxpgxYwyz2VyneO6++24jKirKCAgIMC6//HLj7rvvtupr/9tvvxmPPPKI0bx5c+OSSy4xbr/9duPIkSNVxmcYhlFeXm4888wzRkREhBEYGGgMGDDAyMvLc3h8n3/+uSHJ5nTw4EGb8Tn651cfuCsnPSn3yDNUxxH56s0udv75+flG3759jbCwMCMwMNBo06aNMXHiRKOwsNDNUddfvp6PhkFOegpfzkVy0DP5ak66Kh/9DMMwaveMGwAAAAAAVHD7d6wBAAAAAPBmFNYAAAAAANiBwhoAAAAAADtQWAMAAAAAYAcKawAAAAAA7EBhDQAAAACAHSisAQAAAACwA4U1AAAAAAB2oLAGAAAAAMAOFNYAAAAAANiBwhoAAAAAADv8f6X4+WbUwHJoAAAAAElFTkSuQmCC",
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"import matplotlib.pyplot as plt\n",
"import numpy as np\n",
"import random as rnd\n",
"\n",
"# Load latitude/longitude data from disk\n",
"loaded_data = np.fromfile(\"latitude_longitude.bin\", dtype=np.float32).reshape(-1, 2)\n",
"\n",
"# remove duplicates as our b-tree cannot handle duplicates so far:\n",
"# correct would be to keep duplicates for counting, but this is not necessary to prove the point here\n",
"data = set()\n",
"for latitude, longitude in loaded_data:\n",
" data.add(latitude)\n",
"\n",
"# We need a sample of the data, i.e. a subset that has similar statistical properties:\n",
"# (1.) let's shuffle the input:\n",
"data = list(data)\n",
"rnd.shuffle(data)\n",
"\n",
"# (2.) And show histograms of varying granularity\n",
"fig, axs = plt.subplots(1, 6, figsize=(10, 3))\n",
"fig.tight_layout()\n",
"\n",
"for idx, k in enumerate([10, 50, 100, 1000, 10000, 100000]):\n",
" # take the first k elements as a sample:\n",
" sample = data[:k]\n",
"\n",
" # plot the histogram:\n",
" axs[idx].title.set_text(f\"k={k}\")\n",
" axs[idx].hist(sample, bins=10, alpha=0.5)\n",
" axs[idx].plot()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### 先看抽样为什么管用\n",
"\n",
"上一格从 `latitude_longitude.bin` 读入了真实数据（197 229 个经纬度点，float32 小端、纬度经度交替），取出纬度并去重后，随机打乱，然后对 $k = 10, 50, 100, 1000, 10000, 100000$ 六种样本量各画一张 10 桶直方图。\n",
"\n",
"看图要看的是**形状什么时候稳定下来**：$k = 10$ 时直方图完全不成形，$k$ 增大后各桶的高度比例逐渐固定。样本量足够大之后，再加大 $k$ 只是让曲线更平滑，不再改变形状——这正是\"用样本估计分布\"的合法性来源，也是下一步敢于只拿 1 万条样本建树的理由。\n",
"\n",
"注意两点实现细节：\n",
"\n",
"- 去重是因为本实现的 B+ 树暂不支持重复键（真实系统会把重复键合并成计数）；\n",
"- 打乱用的是 `rnd.shuffle` 且**没有设随机种子**，所以每次运行抽到的样本不同，后面的桶计数会在一定范围内浮动，\"各桶大致相等\"这个结论不变。"
],
"id": "9913f25a"
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### 第一步：用样本建一棵\"矮而胖\"的树\n",
"\n",
"`BPlusTree(5, 2000)`：内部节点容量 5（很小），叶子容量 2000（很大）。\n",
"\n",
"为什么这么配？等深分区想要的是**桶的数量适中、桶深尽量均匀**。叶子大 → 桶少；内部节点小 → 内部那棵\"索引树\"极小，可以整个待在内存里。这也正好呼应第一节的结论：真正需要常驻内存的不是数据，而是那点路标。\n",
"\n",
"然后取 10 000 条样本逐条 `put` 进去。本机实测：树高 3、节点 11、叶 8，也就是说这 1 万条样本把值域切成了 8 段。\n",
"\n",
"> 下一格注释掉的 `bplustree.show()` 故意不开：1 万条样本铺在 8 个容量 2000 的叶子里，画出来是一张又宽又密的图，看不清结构，而且渲染很慢。想看结构请用前面那棵只有 19 个键的小树。"
],
"id": "1f69ef09"
},
{
"cell_type": "code",
"execution_count": 3,
"id": "a63be937-f161-4444-a243-d7edabb02b22",
"metadata": {},
"outputs": [],
"source": [
"# create a b-tree with a decent sample size:\n",
"# we use small inners and big leaves, the goal here is to obtain a small \"inner tree\" (all nodes except the leaves)\n",
"bplustree = BPlusTree[int, int](5, 2000)\n",
"sample = sample[:10000]\n",
"\n",
"# insert the sample data\n",
"for el in sample:\n",
" bplustree.put(el, el)"
]
},
{
"cell_type": "code",
"execution_count": 4,
"id": "aa90d5f6-070b-4311-8a08-dc158b84ac37",
"metadata": {},
"outputs": [],
"source": [
"# this can be slow:\n",
"# bplustree.show()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### 第二步：把叶子换成\"只计数\"的叶子\n",
"\n",
"`convert_to_counting_leaf_tree()` 做一件事：**保留全部内部节点，把叶层整个换成 `CountingLeaf`。**\n",
"\n",
"`CountingLeaf` 不存键也不存值，只有一个 `put_calls` 计数器；它的 `split()` 直接抛 `NotImplementedError`——也就是说，**结构在建好样本树的那一刻就冻结了**，之后再灌多少数据都不会改变树的形状，只会增加计数。\n",
"\n",
"这正是\"两步法\"能省掉排序的原因：全量数据不需要参与任何结构调整，只做一次 $O(N \\log P)$ 的路由下降（$P$ 是叶子个数），比一次外排序便宜得多。\n",
"\n",
"换完之后调用 `show()`，你会看到每个叶子的计数都是 0——因为还没有数据灌进来，边界已经就位、桶还是空的。"
],
"id": "25ef6394"
},
{
"cell_type": "code",
"execution_count": 5,
"id": "e5792d09-502f-49d3-a290-d46e3a5e3874",
"metadata": {},
"outputs": [],
"source": [
"# now we replace the leaf level by CountingLeaves\n",
"# those are leaves that do not store the data but simply count the number of put calls\n",
"bplustree.convert_to_counting_leaf_tree()"
]
},
{
"cell_type": "code",
"execution_count": 6,
"id": "4212cfe6-1c75-406f-89b3-87bc6db47081",
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n",
"\n",
"\n",
"\n"
],
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"show(bplustree)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### 第三步：把全量数据灌进去\n",
"\n",
"现在把去重后的全部纬度（本机实测 132 305 个不同取值）逐条 `put` 进这棵树。\n",
"\n",
"注意这时 `put` 的语义已经变了：路由照旧从根下降到某个叶子，但落到 `CountingLeaf` 上只是 `put_calls += 1`。**没有任何一条数据被存下来，只有计数在增长。**"
],
"id": "db2df33f"
},
{
"cell_type": "code",
"execution_count": 7,
"id": "40ecc1f6-e2c2-406a-9204-1b07708982bb",
"metadata": {},
"outputs": [],
"source": [
"# Now, let's insert all data into this counting tree:\n",
"for el in data:\n",
" bplustree.put(el, el)"
]
},
{
"cell_type": "code",
"execution_count": 8,
"id": "7809ba36-1627-441e-b79a-a621ec017fda",
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n",
"\n",
"\n",
"\n"
],
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"# Here is the result\n",
"show(bplustree)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### 结果：一份近似等深的分区\n",
"\n",
"`show()` 之后每个叶子显示的就是落在它这个区间里的记录数。本机两次实测（都是 8 个桶，总计 132 305，均值 16 538）：\n",
"\n",
"| 运行 | 桶 1 | 桶 2 | 桶 3 | 桶 4 | 桶 5 | 桶 6 | 桶 7 | 桶 8 | 最深/最浅 |\n",
"| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |\n",
"| 第 1 次 | 16 021 | 16 883 | 16 364 | 17 002 | 17 181 | 16 795 | 15 766 | 16 293 | 1.09 |\n",
"| 第 2 次 | 16 557 | 17 616 | 16 666 | 16 507 | 16 081 | 16 900 | 16 434 | 15 544 | 1.13 |\n",
"\n",
"**最深桶 / 最浅桶稳定在 1.1 上下，偏差约 10%**——这就是等深分区：8 个桶几乎一样深，桶边界就是叶层各段的分界键值。\n",
"\n",
"（`rnd.shuffle` 没有固定随机种子，所以每次运行抽到的样本不同，8 个数会变；但\"总计 132 305、每桶一万六千上下、最深最浅相差约 10%\"这三条应当每次都复现。）\n",
"\n",
"两点值得记下来：\n",
"\n",
"- **省掉的是排序。** 全量数据只做了一次流式分发，没有排序、没有归并、没有中间落盘。\n",
"- **换来的是近似。** 桶边界来自 1 万条样本，不是真实分位数。样本量越大边界越准；数据量极度倾斜或分布未知时，偏差会明显变大。\n",
"\n",
"把桶数调一调（改 `BPlusTree(5, 2000)` 的叶子容量，或改样本量）再跑一遍，观察\"最深/最浅\"这个比值怎么变——这是本实验最值得动手的一步。"
],
"id": "a8ea5519"
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## 四、思考题与详解\n",
"\n",
"\n",
"第 1 题：叶容量 4、内部容量 3，为什么插入第 5 个键才触发第一次分裂，而不是第 4 个之后的某一次？
\n",
"\n",
"因为代码判断的是\"**溢出**\"而不是\"装满\"：`if len(node.keys) > self.leaf_cap`。\n",
"\n",
"插到第 4 个键时 `len(keys) == 4`，等于容量，不算溢出，不分裂；插第 5 个键后 `len(keys) == 5 > 4`，才调用 `split()`。\n",
"\n",
"本笔记本里的写法是\"先插入允许暂时溢出，再从中点切开\"——这是教科书里常见的一种变体（另一种是先检查容量、满了就先分裂再插入）。两者的树形会略有不同，装填率也不同，选哪种要在代码里保持一致。\n",
"\n",
" \n",
"\n",
"\n",
"第 2 题：假如把\"溢出后从正中切开\"改成\"快满了就提前分裂\"（PostgreSQL 的 fillfactor 思路），节点数、树高、后续插入的分裂次数会怎么变？
\n",
"\n",
"| 指标 | 溢出后分裂（本实验） | 提前分裂（预留空间） |\n",
"| --- | --- | --- |\n",
"| 短期节点数 | 少 | 多 |\n",
"| 树高 | 相同数量级，可能矮一层 | 相同数量级 |\n",
"| 后续插入触发分裂的频率 | 高（一次都塞不进就裂） | 低（有空位可直接放） |\n",
"| 长期平均装填率 | 约 50%（实测 N = 200 000 时为 50.0%） | 接近设定值（如 90%） |\n",
"\n",
"PostgreSQL 的做法正是后者：B-tree 索引默认 `fillfactor = 90`，插入新键时可以复用页内预留的 10%，代价是叶子页数比满载多约 11%（$1/0.9 \\approx 1.111$）。\n",
"\n",
"**这是一次性多占空间换后续少做结构变动的取舍。** 写多读少的表不值得留空，读多写少的表值得。\n",
"\n",
" \n",
"\n",
"\n",
"第 3 题：实测里 N 从 10 000 涨到 50 000（5 倍）树高不变，从 50 000 涨到 200 000（4 倍）树高加 1。用公式解释这种\"跳变\"。
\n",
"\n",
"用\n",
"\n",
"$$h \\approx 1 + \\lceil \\log_F P \\rceil, \\qquad P \\approx \\frac{N}{L \\times \\text{装填率}}$$\n",
"\n",
"代入 $L = 64$、装填率 ≈ 50%，每叶平均装 32 个键：\n",
"\n",
"- $N = 10\\,000 \\Rightarrow P \\approx 312$，只要 $F \\ge \\sqrt{312} \\approx 17.7$ 就有 $h = 3$；\n",
"- $N = 50\\,000 \\Rightarrow P \\approx 1562$，只要 $F \\ge \\sqrt{1562} \\approx 39.5$，仍是 $h = 3$；\n",
"- $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$ 满足）。\n",
"\n",
"本实验内部容量 63，即扇出最多 $F = 64$：前两档的门槛（17.7、39.5）都够得着，第三档的 79.1 够不着——树高就是在这里跳的。\n",
"\n",
"**关键在于 $h$ 是关于 $P$ 的对数，还带向上取整**：数据在一个数量级内变化时 $\\lceil \\cdot \\rceil$ 常常不变，只有跨过 $F$ 的某个幂次才 +1。这就是\"跳变\"——树高对数据量极其不敏感。\n",
"\n",
" \n",
"\n",
"\n",
"第 4 题：为什么 B+ 树的范围查询不会因为叶子分散在不同分支而反复回到根节点？如果删掉叶链指针，代价变成什么？
\n",
"\n",
"叶链把整个叶层串成一条双向链表。范围查询的流程是：一次从根下降到起始键所在的叶子（$O(\\log_F P)$），之后 `node = node.next` 一路向右，期间**完全不需要回到父节点**。代价是 $h + k/L$（一次下降 + $k/L$ 个叶子的顺序扫）。\n",
"\n",
"删掉叶链之后：想找下一个叶子只能从根重新下降一次，代价从 $h + k/L$ 退化成 $k \\cdot h$（每个叶子都要走一遍树），随机 I/O 数量直线上升；全索引扫描也没法线性走，退化成中序遍历。\n",
"\n",
"**叶链是 B+ 树压过 B 树的决定性设计**，不是\"锦上添花\"。\n",
"\n",
" \n",
"\n",
"\n",
"第 5 题：内部节点为什么\"弃卒保帅\"地不存数据行？如果非要在内部节点也存数据（回到 B 树），扇出和树高会怎么变？
\n",
"\n",
"设节点总空间 $S$，一个\"键 + 行指针\"占 $k + p$ 字节，一个\"纯分隔键 + 孩子指针\"占 $k + c$ 字节，通常 $p > c$（行指针要定位到堆表里的具体位置，可能还带元组 ID；孩子指针只是个页号）。\n",
"\n",
"- B 树内部节点扇出 $\\approx S/(k+p)$\n",
"- B+ 树内部节点扇出 $\\approx S/(k+c)$\n",
"\n",
"因为 $k + c < k + p$，B+ 树的 $F$ 更大，由 $h \\approx 1 + \\lceil \\log_F P \\rceil$ 得树更矮。而树高直接决定一次点查要访问多少个页。\n",
"\n",
"代价是 B+ 树的点查必须走到叶层（B 树在内部节点命中就可以返回），但换来的是\"每一层能排除更多键 + 范围查询可以走叶链\"。数据库里范围扫描（`BETWEEN`、排序、`GROUP BY` 走索引）远比单点命中常见，所以这笔交易划算。\n",
"\n",
" \n",
"\n",
"\n",
"第 6 题：实测 N = 200 000 时点查平均检查 10.0 个单元，树高为 4。这 10.0 是怎么拆出来的？
\n",
"\n",
"按点查代价的口径：\n",
"\n",
"$$\\text{单元数} = \\underbrace{(h - 1)}_{\\text{下降经过的内部节点}} + \\underbrace{1}_{\\text{叶节点}} + \\underbrace{\\lceil \\log_2(\\text{叶内键数} + 1) \\rceil}_{\\text{叶内二分}}$$\n",
"\n",
"$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",
"\n",
"回头核对：$N = 200\\,000$、叶数 6 249，平均每叶 $200000 / 6249 \\approx 32.0$ 个键，正好落在区间里，$\\lceil \\log_2 33 \\rceil = 6$。**完全自洽。**\n",
"\n",
"顺带看清一件事：同样是对数级，B+ 树的 10.0 和数组二分的 16.6 差别不算大；真正的差距在于这 10 个单元里有 4 个是**页访问**（可在缓冲池里摊销），而全表扫描的 100 000 是实打实的行检查。\n",
"\n",
" \n",
"\n",
"\n",
"第 7 题：等深分区为什么可以用\"抽样建树 + 全量计数\"两步完成，而不是排完序再切成 k 段？它省掉了什么，代价是什么？
\n",
"\n",
"排全序再均分要先对 N 条记录做一次 $O(N \\log N)$ 的外排序（大表还要落盘做归并），才能得到 $k-1$ 个切分点。两步法换成：\n",
"\n",
"1. 抽 $m$ 条样本（$m \\ll N$）建树，内部节点很少，常驻内存；\n",
"2. 全量数据做一次 $O(N \\log P)$ 的流式分发，落到叶子上只计数。\n",
"\n",
"**省掉的是全排序的磁盘 I/O 与归并开销。**\n",
"\n",
"代价有两点：一是切分点来自样本，样本偏差导致桶深不均（数据极度倾斜或分布未知时尤其明显）；二是树结构要保持在内存里。若样本确实是同分布随机采样，误差可以用样本量控制：$m$ 越大，桶边界越接近真实分位数。本实验 8 个桶的最深/最浅比值约 1.09，就是 1 万条样本换来的精度。\n",
"\n",
" \n",
"\n",
"\n",
"第 8 题：一棵叶容量为 L、内部容量为 F−1 的 B+ 树，若要求树高不超过 3，最多能索引多少个键？分满载与实测 50% 装填两种情况给出表达式。
\n",
"\n",
"树高 3 = 层 0 根、层 1 内部、层 2 叶：\n",
"\n",
"```text\n",
"每个叶子最多容纳键数 = L × 装填率\n",
"根的孩子数（层 1 节点数） ≤ F\n",
"层 1 每个节点的孩子数 ≤ F → 它们就是叶子\n",
"⇒ 叶总数 P ≤ F²\n",
"⇒ 键总数 N ≤ F² · L · 装填率\n",
"```\n",
"\n",
"- **满载**（装填率 = 1）：$N_{\\max} = F^2 \\cdot L$\n",
"- **实测装填率 ≈ 50%**：$N_{\\max} \\approx 0.5 \\cdot F^2 \\cdot L$\n",
"\n",
"代入本实验的 $L = 64$、$F = 64$：$N_{\\max} = 64^2 \\times 64 = 262\\,144$（满载），实测装填率下约 $131\\,072$。\n",
"\n",
"这也解释了为什么 N = 200 000 时装填率只有 50% 就\"被迫\"长到第 4 层：$131\\,072 < 200\\,000 < 262\\,144$——按满载估算还能塞下，按实际装填率就塞不下了。\n",
"\n",
" "
],
"id": "f1b82891"
},
{
"cell_type": "code",
"execution_count": null,
"id": "a7f27a87-9017-4c9f-abab-239d8f37b1d1",
"metadata": {},
"outputs": [],
"source": []
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3 (ipykernel)",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.12.7"
}
},
"nbformat": 4,
"nbformat_minor": 5
}