Tree 模块：在 SQLite 中将页面转化为行
Source: Dev.to
（请提供您希望翻译的正文内容，我将把它翻译成简体中文并保持原有的 Markdown 格式。）
从分页器到树
在前一章中，我们停在了 分页器。
分页器为 SQLite 提供了一件极其重要但也非常有限的东西：对字节流的 基于页的视图。
你可以请求第 17 页，对其进行修改、固定、解固定——但分页器根本不知道 行、列 或 记录 是什么。
正是这段空白让 树模块 介入。
树模块将这种扁平的、基于页的世界转换为 VM 能够理解的形式：基于元组、键序列的文件。
从此以后，VM 不再以页为单位思考，而是以 元组 为单位——有序、可搜索、可插入的数据单元。
Source: …
什么是 SQLite 中的元组？
在继续之前，值得放慢脚步并澄清一个非常常见的混淆。
- SQLite 中的元组不是一种数据类型。
- 它也不是 C 结构体、不是行对象，也不是树模块试图语义化解释的东西。
元组仅仅是：
- 由虚拟机（VM）看到的关系的逻辑行，在内部表示为可变长度的字节序列。
- 被树模块视为不透明数据。
换句话说，树模块不关心元组代表的是：
- 带有列的表行，或
- 带有 key + rowid 的索引条目。
sqlite_master 的元数据是单独存储的。对树模块而言，所有这些都只是带有关联键的字节串。意义是由树模块之上的层次（主要是 VM 和记录格式逻辑）强加的。
为什么元组需要组织
一个关系在概念上是 元组的集合，但仅靠集合不足以实现高效访问。虚拟机（VM）需要以下保证：
- 通过键查找元组
- 按顺序扫描元组
- 高效插入和删除元组
- 即使在同一文件中，也要将不同关系的元组分开
组织元组的经典方式包括：
- 条目序列（仅追加）
- 相对定位
- 基于哈希的组织
- 键序列组织（SQLite 的选择）
每种选择都会影响插入、查找和删除的行为。
SQLite的“一大”设计决策：一切皆树
SQLite 只使用 一种组织技术 来存储持久化数据：
| 结构 | 用途 |
|---|---|
| B⁺‑trees | 表 |
| B‑trees | 索引 |
没有哈希表，没有堆文件，没有聚簇的二级结构。每个关系——无论是表还是索引——都 拥有自己的树。
后果
- 每棵树对应 一个关系或索引。
- 所有树都位于 同一个数据库文件 中。
- 不同树的页面可以在磁盘上交错存放。
- 没有任何单页会同时包含来自多个树的元组。
最后一点至关重要。虽然页面在文件层面是共享的，但 所有权 在树层面是严格的。确保这一点是树模块的主要职责之一。
从页面导向到树导向
| 层 | 它公开的内容 |
|---|---|
| Pager | 编号页面的集合 |
| Tree Module | 支持有序访问以及元组级别插入、删除和查找的 面向树的文件 |
内部，树模块：
- 选择哪些页面属于哪个树
- 维护父/子关系
- 确保 B⁺ 树的平衡属性
- 决定何时对页面进行拆分或合并
对分页器而言，页面仅仅是页面。对树模块而言，页面是 节点。
树模块是有意被动的
一项细微但重要的设计选择：树模块是结构上活跃但语义上被动的。
| 它关注的内容 | 它不关注的内容 |
|---|---|
| 键、排序、页面布局、树的平衡、导航 | 列类型、SQL 模式、约束、元组中字段的含义 |
树元数据的存放位置
SQLite 仍然需要一种方式来回答以下问题：
- 哪棵树属于哪个表？
- 这棵树的根页在哪里？
- 这棵树是表还是索引？
这些映射信息存储在一个特殊且众所周知的关系中：
sqlite_master（临时对象使用sqlite_temp_master）
这个目录本身也存放在一个 预定的 B⁺‑树 中，和其他所有数据一样。SQLite 并没有通过将元数据存放在系统“外部”来投机取巧——它自己也使用自己的数据结构。
我们接下来要去的方向
到目前为止，我们已经建立了宏观概念：
- Pager → 页面
- Tree module → 元组
- VM → SQL 语义
在接下来的几天里，我们将进一步聚焦并具体化：
- 树接口函数 – VM 实际如何与树交互
- B⁺树结构 – 内部节点、叶子节点、分隔符
- 页面结构 – 元组在单个页面内如何打包、索引和导航
那时，图示开始变得有意义，SQLite 设计的真正优雅也随之显现。
需要持续记住的关键理念： SQLite 将字节文件转换为页面，页面转换为树，树转换为关系——一次一个干净的层次。
我的 SQLite 实验和动手执行示例位于此：
lovestaco/sqlite – sqlite‑examples
参考文献
- SQLite Database System: Design and Implementation – Sibsankar Haldar
(如有需要，请替换为实际的图片 URL)
[](https://hexmos.com/freedevtools/)
👉 **查看:** [FreeDevTools](https://hexmos.com/freedevtools/)
欢迎提供任何反馈或贡献！
它是在线的、开源的，随时可供任何人使用。
⭐ **在 GitHub 上给它加星:** [FreeDevTools 仓库](https://github.com/HexmosTech/FreeDevTools)