7.2 MdrDB：存储、页面与索引
当我们在 mdrdb 交互终端中执行一条插入语句 insert 1 alice alice@example.com 时，磁盘上的二进制数据库文件会精准增加 30 个有效字节。这一段载荷的物理落点位于文件偏移 8162 处；由于根节点位于第 1 页（基准偏移 4096），换算下来，它正好坐落在第 1 页的页内偏移 4066 位置：
$ xxd -s 8162 -l 30 fmt.db
00001fe2: 0000 0001 0018 0561 6c69 6365 1161 6c69 .......alice.ali
00001ff2: 6365 4065 7861 6d70 6c65 2e63 6f6d ce@example.com2
3
在十六进制转储中，开头的 0000 0001 对应 32 位无符号整型主键 1，紧随其后的 0018 指示变长数据负载长度为 24 字节，之后依次是以 1 字节长度前缀 5 引导的用户名 alice，以及以 1 字节长度前缀 0x11（十进制 17）引导的邮箱字符串。与此同时，该页物理头部的元数据同步发生更新：标注此页为叶子节点、当前容纳两个单元格、自底向上生长的内容区起始指针推进至 4036；而位于物理第 0 页的文件全局头部，则持久化记录着整页规格 4096 字节与全库总页数 2。命令行元命令 .page 与外部的 xxd 观察的是同一块物理事实，区别仅在于前者把原本紧凑咬合的原始二进制字节解析成了易于辨识的结构化字段。
我们将循着这条物理脉络，自底向上逐步剖析存储引擎的核心构件：从最底层的标准系统 IO 封装与无缓冲写盘，到跨平台二进制大端序编码；从内存 Pager 缓存池的 LRU 置换算法、页面钉住机制与空闲页分配，到单个物理页内部精巧的槽式（Slotted-page）重排布局；最后推进至变长记录协议的序列化，以及整棵 B+ 树的二分检索、节点级联分裂、惰性删除与一致性巡检。通过理清这些构件之间的层层协作，我们可以自然推导出 .page 诊断输出中的每一个物理字节偏移，看清从一串十六进制字节如何重构出一整页的拓扑全貌，并能够准确预判持续写入后整棵索引树的生长轨迹。
本节涉及的核心实现均源自仓库中的 code/项目/MdrDB/src 目录。工程的基础架构与构建环境已在 7.1 项目概述 中确立，关于上层查询路由、崩溃故障注入机制与事务回滚恢复的完整实现，则将在 7.3 查询路径、恢复与测试 深度剖析。
1. 文件层：按偏移读写整页
在 MdrDB 的抽象模型中，数据库文件在逻辑上被视作一组连续排列的、固定为 4096 字节的物理页面切片。页号为 n 的页面，其物理读取起点严格对齐于文件偏移 n × 4096 处。在整个架构设计中，唯一被允许直接接触底层磁盘数据库文件句柄的模块仅有 src/file.c，其余各层若接触到标准库的 FILE * 指针，也仅限于向终端控制台输出日志与诊断信息，坚决不越界触碰原始数据文件：
db_status file_read_at(db_file *f, long offset, void *buf, size_t size,
size_t *nread) {
*nread = 0;
if (fseek(f->fp, offset, SEEK_SET) != 0) {
return DB_IO_ERROR;
}
size_t n = fread(buf, 1, size, f->fp);
if (n < size && ferror(f->fp)) {
clearerr(f->fp);
return DB_IO_ERROR;
}
*nread = n;
return DB_OK;
}2
3
4
5
6
7
8
9
10
11
12
13
14
读取流程非常简练：首先调用 fseek 定位到指定的绝对物理偏移，随后通过 fread 将一整页的字节载入调用方提供的内存缓冲区。倘若实际读出的字节数 *nread 小于预期的页面规格，表明物理文件在磁盘上的实际尺寸小于文件头中记录的声明页数，Pager 层的 read_page 会立即向上传递 DB_CORRUPT 格式损坏错误，彻底杜绝上层业务拿着半截截断数据继续错误解析的隐患。在 IO 发生异常时显式调用 clearerr 至关重要：标准流在遭遇 EOF 或读取故障后，其内部错误标志位会一直处于挂起状态，若不及时清空，后续对该文件句柄的所有读写请求都将直接遭遇连锁失败。
底层的打开模式严格界定了生命周期语义：file_open 采用 "rb+" 模式，以读写权限打开一个预先存在的物理数据库；而 file_create 则使用 "wb+" 创建新文件或覆盖清空旧文件。所有文件交互必须严格声明为二进制模式：特别是在 Windows 宿主环境下，若误用文本模式，标准库的运行时会自动在换行符 \n 与 \r\n 之间进行隐式转换，从而导致物理偏移计算全盘错位。辅助函数 file_exists 则以只读二进制模式 "rb" 尝试打开目标路径，通过探测是否成功来返回布尔状态，并在返回前立即释放句柄。
file_write_at 多了一件事，故障注入：
db_status file_write_at(db_file *f, long offset, const void *buf, size_t size) {
if (fault.crashed) {
return DB_IO_ERROR;
}
bool crash_here = at_crash_point();
/* 崩溃点上的写只写进前一半，模拟断电时只写进一部分的撕裂写。 */
size_t n = crash_here ? size / 2 : size;
if (fseek(f->fp, offset, SEEK_SET) != 0 || fwrite(buf, 1, n, f->fp) != n) {
clearerr(f->fp);
return DB_IO_ERROR;
}
if (crash_here) {
crash();
return DB_IO_ERROR;
}
return DB_OK;
}2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
关于故障注入的具体模拟算法将在 7.3 全面剖析，在此处我们更需要关注的是它对文件层读写行为所施加的工程铁律：每一次上层下达的 fwrite 指令必须即刻越过应用层到达操作系统，绝不允许滞留在标准库内部的用户态缓冲区中。
在文件句柄初始化的包装函数 wrap 中，最优先执行的操作便是彻底关闭用户态缓冲：
/*
* 关掉 stdio 的缓冲，每次 fwrite 都立即交给操作系统。页本来就是
* 整块读写，缓冲省不了几次系统调用；更重要的是，数据到达操作系统
* 的顺序从此与代码中写的顺序一致，"在第 n 次写入时崩溃"才名副其实。
*/
if (setvbuf(fp, NULL, _IONBF, 0) != 0) {
fclose(fp);
return DB_IO_ERROR;
}2
3
4
5
6
7
8
9
由于 MdrDB 的磁盘交互本身就严格按 4096 字节的整页为单位推进，标准库自带的小缓冲池无法合并出更大批量的写入，因此开启缓冲对于减少系统调用次数并没有实际收益。更为核心的考量在于写入时序的绝对因果性：若保留缓冲机制，代码逻辑上虽然已经完成了写调用，但物理字节可能依然滞留在用户空间内存之中，自动化测试中设定的“在第 n 次物理写盘时瞬间模拟进程崩溃”就会因时序错乱而名不副实，使得崩溃一致性测试失去效力。
fseek 的偏移类型与寻址天花板
在基础实现中，page_offset 函数与标准库 fseek 的入参类型均为标准 long。在 64 位 Windows 平台上（LLP64 数据模型），long 类型的位宽仅有 32 位，其最大正整数表达能力为 DB_MAX_PAGES 审慎定为 524288，此时 fseeko 或 Windows 平台的 _fseeki64）。
文件层为什么用 setvbuf(fp, NULL, _IONBF, 0) 关掉 stdio 的缓冲？
2. 大端序：跨平台的二进制整型编码
为了保证数据库文件在异构软硬件体系间无缝流转，MdrDB 规定磁盘文件中存储的所有多字节整数一律严格采用网络字节序——即大端序（big-endian，高位字节优先存放在低地址）。负责整型编解码的核心逻辑被浓缩在 src/format.h 的内联辅助函数中：
/* 先转成 uint32_t 再移位：uint8_t 会提升为 int，左移 24 位可能溢出。 */
static inline uint32_t get_u32(const uint8_t *p) {
return ((uint32_t)p[0] << 24) | ((uint32_t)p[1] << 16) |
((uint32_t)p[2] << 8) | (uint32_t)p[3];
}
static inline void put_u32(uint8_t *p, uint32_t v) {
p[0] = (uint8_t)(v >> 24);
p[1] = (uint8_t)(v >> 16);
p[2] = (uint8_t)(v >> 8);
p[3] = (uint8_t)v;
}2
3
4
5
6
7
8
9
10
11
12
以页面尺寸 4096 为例，其十六进制表示为 0x00001000。经过 put_u32 的字节拆解后，在物理磁盘上将严格呈现为连续的 00 00 10 00 四个字节。无论宿主机是 x86 架构的小端机还是某种大端处理器，写出的字节序列均完全相同，确保了跨平台二进制兼容性。
内联实现中对 (uint32_t)p[0] 的显式强制类型转换蕴含着细致的 C 标准考量。由于 p[0] 的类型为 uint8_t，在参与左移位运算 << 时，C 语言标准整型提升规则会自动将其提升为有符号的 int 类型。如果最高位字节恰好为 0xFF，那么执行 0xFF << 24 时就会导致最高有效位溢入有符号整型的符号位甚至发生值溢出，在 ISO C 标准中直接构成未定义行为（Undefined Behavior）。先显式将其转换为无符号的 uint32_t，移位运算便会在定义明确的模算术无符号域内安全展开。
typedef struct header {
char magic[14];
uint32_t page_size;
uint32_t page_count;
} header;
header h = {"MdrDB format 1", 4096, 2};
fwrite(&h, sizeof h, 1, fp);2
3
4
5
6
7
8
static void fresh_header(uint8_t *data) {
memset(data, 0, DB_PAGE_SIZE);
memcpy(data, header_magic, HEADER_MAGIC_SIZE);
put_u32(data + HEADER_PAGE_SIZE_OFFSET, DB_PAGE_SIZE);
put_u32(data + HEADER_PAGE_COUNT_OFFSET, 1);
}2
3
4
5
6
左边这段在本机写出的文件是这样的：
$ ./struct_write
sizeof(header) = 24
$ xxd -l 24 struct.db
00000000: 4d64 7244 4220 666f 726d 6174 2031 0000 MdrDB format 1..
00000010: 0010 0000 0200 0000 ........2
3
4
5
在常见的 x86-64 小端平台上，结构体直接写盘暴露出两个严重的工程陷阱：其一，由于结构体成员的自然对齐要求，14 字节的 char 数组后方被编译器隐式插入了 2 字节的未初始化填充空隙（padding bytes）；其二，uint32_t 整型按宿主机小端序被倒序存储为 00 10 00 00。一旦将该文件拷贝至对齐策略不同或字节序相反的平台上运行，或者更换了编译器的对齐参数，结构体成员的物理映射就会瞬间错乱。相比之下，右侧 fresh_header 采纳的显式序列化实践完全消除了这一隐患：整页首先显式填充为零，随后紧扣预定义的常量偏移，由编解码函数统一按大端序注入字段。无论运行在何种编译器或芯片平台之下，写出的二进制排布都与格式规范保持 100% 绝对一致。
磁盘格式由代码显式确立
数据文件中的物理字段排布——每一个属性所处的绝对字节偏移、物理宽度以及字节编码顺序，完全由工程源代码与协议常量显式锁定，绝不依赖编译器的内存结构体对齐规则或宿主机的硬件字节序。在反序列化读取磁盘页时，同样必须严格按偏移逐字段反解，坚决避免将磁盘页面通过 memcpy 强转为 C 结构体对象读取成员。
3. pager：页框池、页面钉住与置换策略
在存储引擎的层次中，Pager 构筑了一道至关重要的抽象屏障：它将线性展开的文件字节流转化为离散的、具有整数编号的页面集合。上层的 B+ 树与行接口在读写数据时，只需向 Pager 声明逻辑页号（如第 1 页根节点、第 2 页叶子等），根本无需关心页面在磁盘上的实际物理偏移。围绕着页面对象，Pager 统一承担了三大核心职责：内存页面的按需缓存调度、新页面的物理追加分配，以及保障 ACID 的事务边界管理。
3.1 页框
缓存由固定数量的页框（frame）组成，每个页框是一页的空间加上几个字段：
typedef struct page {
uint32_t pgno;
int pins; /* 钉住计数，大于 0 时不能换出 */
bool in_use; /* 页框里是否装着一页 */
bool dirty; /* 内容改过，还没写回文件 */
uint64_t last_used; /* 最近一次被取用的时刻，用于 LRU */
uint8_t data[DB_PAGE_SIZE];
} page;2
3
4
5
6
7
8
pager 控制块的具体结构体定义被私有化封装在 src/pager.c 内部，对外仅暴露不透明指针（Opaque Pointer）。在内部实现中，它维护着一块连续分配的页框对象数组 page *frames、总页框配额 frame_count、用于逻辑时钟计数的自增计数器 clock，以及反映当前文件规模的总页数 page_count。在默认配置下，引擎分配 64 个页框供缓存使用，但在极度受限的环境下，系统容许的物理下限是 4 个页框：
#define PAGER_DEFAULT_FRAMES 64
/*
* B+ 树同时钉住的页不超过 2 个，分配新页时还要临时钉住文件头。
* 再留一个可以换出的页框，最少需要 4 个。
*/
#define PAGER_MIN_FRAMES 42
3
4
5
6
7
3.2 三条使用规则
取页的入口是 pager_get：
db_status pager_get(pager *p, uint32_t pgno, page **out) {
*out = NULL;
if (p->state == PAGER_ERROR) {
return DB_IO_ERROR;
}
if (pgno >= p->page_count) {
return DB_CORRUPT; /* 指向文件末尾之外，只能来自损坏的数据 */
}
page *pg = find_frame(p, pgno);
if (pg != NULL) {
p->stats.hits++;
} else {
db_status rc = take_frame(p, &pg);
if (rc != DB_OK) {
return rc;
}
rc = read_page(p, pgno, pg->data);
if (rc != DB_OK) {
return rc;
}
p->stats.misses++;
pg->pgno = pgno;
pg->in_use = true;
pg->dirty = false;
pg->pins = 0;
}
pg->pins++;
pg->last_used = ++p->clock;
*out = pg;
return DB_OK;
}2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
值得注意的是，pager_get 传出的内存指针直接指向驻留在页框内的 data 缓冲区，实现了零拷贝直读。为了防止该页面在当前函数处理期间被其他并发或内部操作的置换逻辑突然驱逐出内存，函数在返回前强制将引用计数 pins 递增 1——这一机制被称为“页面钉住”（Pinning）。上层代码在结束对该内存区域的访问之后，必须严格调用 pager_unpin 将其引用计数归还：
void pager_unpin(page *pg) {
if (pg != NULL && pg->pins > 0) {
pg->pins--;
}
}2
3
4
5
修改内容之前则要先声明：
db_status pager_write(pager *p, page *pg) {
if (p->state == PAGER_ERROR) {
return DB_IO_ERROR;
}
if (p->state != PAGER_WRITING) {
return DB_MISUSE;
}
/*
* 事务开始后才分配的页（页号不小于 orig_page_count）没有需要保存
* 的原始内容：回滚后页数恢复原值，这些页落在页数之外，自然作废。
* 位图保证每页只记一次：同一页第二次修改时，日志里已经是它的原貌。
*/
if (pg->pgno < p->orig_page_count && !test_bit(p->journaled, pg->pgno)) {
db_status rc = journal_append(&p->journal, pg->pgno, pg->data);
if (rc != DB_OK) {
return fail(p, rc);
}
set_bit(p->journaled, pg->pgno);
p->stats.journaled++;
}
pg->dirty = true;
return DB_OK;
}2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
pager_write 承担了事务完整性的前置守门职责：首先将当前页面在未被修改前的原始物理镜像追加写入回滚日志文件（借助位图保证同一个页面在单笔事务生命周期中只归档首个原始快照），随后将页框的 dirty 脏页标志位置为真。只有被打上脏标记的页框，在后续事务提交或内存不足发生驱逐时，才会被真正写回磁盘文件。
pager 的三条契约规则
- 借出必归还：由
pager_get获取的页面天然处于钉住状态（Pin），使用完毕后必须配对调用pager_unpin解钉。处于钉住状态的页框绝不允许被置换驱逐；若因遗漏解钉导致所有页框被长期占满，后续的取页操作将直接返回DB_CACHE_FULL。 - 写前必声明：在真正着手修改
pg->data内存字节之前，必须无条件调用pager_write。这一调用负责在写入前捕获磁盘原貌并锁定脏页状态；一旦漏调，改动既无法进入回滚日志保护，在事务提交时也会被静默丢弃。 - 改动必有事务：任何对存储状态产生修改的接口（包括
pager_write与pager_allocate），都必须运行在显式或隐式的事务上下文（即pager_begin之后）。在无事务状态下擅自调用将立即遭遇DB_MISUSE拦截。
必须先调用 pager_write，随后再修改内存字节
pager_get 的职责仅限于将物理页面载入内存缓存，并不提供写跟踪保证。若在拿到页面指针后未调用 pager_write 便径直改写 pg->data 中的字节，该页面便不会被置为脏页，回滚日志中也不会沉淀任何还原镜像。在单次运行的进程生命周期内，因为所有后续读取都直接命中这块被污染的内存缓存，表面上看起来读写一切正常；但一旦事务提交退出并重新打开数据库文件，未落盘的修改将彻底蒸发。
3.3 页面驱逐：LRU 淘汰与预写回（Spill）机制
当上层请求访问某个尚未载入内存的物理页、且当前缓冲池内所有页框均已被占满时，Pager 必须执行页面置换。调度算法首先在已有缓存池中遍历，探查目标页是否已在内存驻留：
/* 页框不多，顺序查找足够快。页框多起来时应当改用散列表。 */
static page *find_frame(pager *p, uint32_t pgno) {
for (size_t i = 0; i < p->frame_count; i++) {
page *pg = &p->frames[i];
if (pg->in_use && pg->pgno == pgno) {
return pg;
}
}
return NULL;
}2
3
4
5
6
7
8
9
10
若发生缓存未命中，算法便会在候选池中选拔一个牺牲者（Victim Frame）腾出位置：
/*
* 找一个页框装新页：有空闲的就用空闲的，否则换出最久没用、也没被
* 钉住的那一页。被换出的页若是脏的，要先写回文件。事务还没提交，
* 修改就进了数据库文件，这是允许的：原始内容在日志里，随时能撤销。
*/
static db_status take_frame(pager *p, page **out) {
page *victim = NULL;
for (size_t i = 0; i < p->frame_count; i++) {
page *pg = &p->frames[i];
if (!pg->in_use) {
victim = pg;
break;
}
if (pg->pins == 0 &&
(victim == NULL || pg->last_used < victim->last_used)) {
victim = pg;
}
}
if (victim == NULL) {
return DB_CACHE_FULL;
}
if (victim->in_use && victim->dirty) {
db_status rc = write_back(p, victim);
if (rc != DB_OK) {
return rc;
}
p->stats.spills++;
}
victim->in_use = false;
*out = victim;
return DB_OK;
}2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
驱逐淘汰的判决标准十分清晰：在所有未被钉住（pins == 0）的空闲或可用页框中，挑选逻辑时钟 last_used 数值最小的那一页作为置换对象，这便是经典的最近最少使用（LRU）策略。工程实现中没有采用系统墙上时钟（Wall-clock time），而是引入了全局单调自增的逻辑计数器 p->clock，每次发生页面访问便递增并打上时间戳。这种设计不仅规避了高频调用系统时间 API 的性能损耗，也彻底免疫了因宿主机夏令时调整或 NTP 授时回拨造成的时序混乱。
take_frame 的分支逻辑极为平实：如果缓冲池中尚存闲置页框，优先直接使用；若所有页框都已载入数据，则对挑出的牺牲者实施驱逐。如果该牺牲页处于已改动的脏页状态（dirty == true），Pager 会在其被覆盖前强制调用 write_back 将脏数据刷写回磁盘数据文件，并将本次提前写盘计入 spills（脏页外溢）统计指标。在一笔事务尚未真正执行 commit 之前，允许未决的修改数据提前落盘是否会破坏事务原子性？在经典回滚日志（Rollback Journal）体系下，这种提前下刷是被完全允许的，其前提是受影响页面的原始镜像已预先安全落盘至回滚日志中；write_back 在真正向数据文件落笔前，一定会强制调用 journal_sync 确保日志先于数据落盘（WAL/Write-Ahead 日志先写原则），关于此机制的完整状态机在 7.3 中展开。
3.4 分配新页与文件头
文件只增不减，新页总是追加在末尾，页数记在第 0 页的文件头里：
db_status pager_allocate(pager *p, page **out) {
*out = NULL;
if (p->state == PAGER_ERROR) {
return DB_IO_ERROR;
}
if (p->state != PAGER_WRITING) {
return DB_MISUSE;
}
if (p->page_count >= DB_MAX_PAGES) {
return DB_FULL;
}
/* 页数记在文件头里，改它和改别的页一样：先 pager_write，后修改。 */
page *header;
db_status rc = pager_get(p, 0, &header);
if (rc != DB_OK) {
return rc;
}
rc = pager_write(p, header);
if (rc != DB_OK) {
pager_unpin(header);
return rc;
}
uint32_t pgno = p->page_count;
put_u32(header->data + HEADER_PAGE_COUNT_OFFSET, pgno + 1);
pager_unpin(header);
p->page_count = pgno + 1;
/* 新页不用从文件读：它的内容从全零开始。 */
page *pg;
rc = take_frame(p, &pg);
if (rc != DB_OK) {
return rc;
}
memset(pg->data, 0, DB_PAGE_SIZE);
pg->pgno = pgno;
pg->in_use = true;
pg->dirty = true;
pg->pins = 1;
pg->last_used = ++p->clock;
*out = pg;
return DB_OK;
}2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
更新全局文件头的物理流程与普通数据页没有任何区别，同样必须遵循“先声明写、后修改字节”的铁律。倘若跳过了 pager_write 直接修改内存中的页数字段，总页数的扩增既无法登记到回滚日志，也不会被系统视作脏页下刷；一旦中途发生事务回滚，文件头便无法回退，而在事务提交后磁盘上的记录也可能沦为错误的旧值。新分配的页面无需发起物理磁盘读，系统直接在内存中将其字节全量置零清空；分配返回时该页面已被默认钉住，调用方在初始化完成其数据结构后同样必须调用 pager_unpin 予以解钉。
在初始化新数据库时，btree_create 正是通过 pager_allocate 首次申请得到物理第 1 页，确认其页号精准匹配宏定义的 BTREE_ROOT 后，调用 node_init(root->data, NODE_LEAF) 将其格式化为空叶子节点，随后执行 pager_unpin 归还。因此，新建的空数据库物理上恒定占据两页：物理第 0 页固化为文件全局头部，物理第 1 页则永久锚定为 B+ 树的根节点。
3.5 观察：页框多少影响什么
在一个已经有 300 行（7 页）的库上，用一个事务再插入 300 行：more.txt 里是 begin、300 行 insert、commit 和 .info。分别用默认的 64 个页框和 4 个页框跑一遍：
$ ./mdrdb --echo --cache 64 a.db < more.txt
mdrdb> .info
file: a.db
page size: 4096, page count: 12
cache: 64 frames, hits 1217, misses 3, spills 0
journal: pages saved 3, pages restored at open 0
transaction: none2
3
4
5
6
7
$ ./mdrdb --echo --cache 4 b.db < more.txt
mdrdb> .info
file: b.db
page size: 4096, page count: 12
cache: 4 frames, hits 1217, misses 3, spills 4
journal: pages saved 3, pages restored at open 0
transaction: none2
3
4
5
6
7
比对两组运行诊断可以发现：两者的缓存命中数、未命中数、最终物理总页数完全相同，运行 .tree 得到的拓扑树形也完全吻合，唯一产生分歧的指标正是 spills。在 4 个页框的极限配置下，可用内存无法完全容纳单笔庞大事务运行期间涉及的活动工作集（Working Set），因此先后发生了 4 次未提交脏页被提前淘汰并写回主数据文件的事件。这组对比雄辩地证明：页缓存池的容量配额不会左右事务的逻辑执行结果，它仅在物理层面影响脏页外溢的发生频率。
对照一下每条插入各自成事务的情形（rows_info.txt 是 300 条 insert 加一行 .info）：
$ ./mdrdb --echo --cache 4 c.db < rows_info.txt
mdrdb> .info
file: c.db
page size: 4096, page count: 7
cache: 4 frames, hits 1098, misses 1, spills 0
journal: pages saved 308, pages restored at open 0
transaction: none2
3
4
5
6
7
在自动提交场景下，spills 保持为 0。这是因为每一条独立插入语句自成一笔极短命的事务，在其短暂的生命周期内仅仅触及目标叶子节点与全局文件头等两三页，4 个页框的配额足以平整承载其瞬时工作集。然而，两者的开销代价在日志维度呈现了显著的剪刀差：300 笔微型事务各自独立落盘，导致叶子节点的物理旧镜像被反复写向回滚日志，加上多次扩展页面时的文件头快照，日志写入总量高达 308 页；而在单一事务中批量提交 300 条写入时，单笔事务内同一物理页仅记录一次旧快照，累计仅耗费 3 个日志页。工程实践中是选择更平稳的内存峰值还是更高效的磁盘 IO 吞吐，其权衡便直观投射在这组数据指标之中。
3.6 漏掉 pager_unpin 会怎样
页框是有限的，钉住不放的页无法换出。test_pager 里的 test_pins_and_cache_full 先建一个 5 页的库，用 4 个页框把第 1～4 页全部取出来钉住，再取第 5 页。省略了开头几行之后，函数的下半段是这样：
page *again;
CHECK_OK(pager_get(p, 1, &again)); /* 已在缓存中：同一个页框 */
CHECK(again == held[0] && again->pins == 2);
pager_unpin(again);
page *extra;
CHECK_STATUS(pager_get(p, 5, &extra), DB_CACHE_FULL);
for (int i = 0; i < PAGER_MIN_FRAMES; i++) {
pager_unpin(held[i]);
}
CHECK_OK(pager_get(p, 5, &extra));
pager_unpin(extra);
CHECK(pager_pinned(p) == 0);2
3
4
5
6
7
8
9
10
11
12
已经常驻内存的页面若被再次请求，并不会开辟新的页框，而是直接递增其原位 pins 计数至 2 并计入一次命中。当缓冲池中所有页框均处于钉住状态时，任何需要置换新页的 pager_get 请求都会因无页可换而抛出 DB_CACHE_FULL 错误；只要释放归还其中哪怕任意一个页框，后续的读取即可顺畅恢复。这一机制深刻揭示了为何在 test_btree 集成测试中，每次巡检整棵树后都会严密断言 pager_pinned(p) == 0：在代码中遗漏 pager_unpin 解钉并不会在当时当地立即崩溃，而是如同隐蔽的内存泄漏一般持续蚕食可用页框，直到未来某一刻在完全无关的业务分支上暴发缓存枯竭灾难，因此在测试断言中尽早拦截钉住泄露是至关重要的防御性实践。
take_frame 为什么跳过 pins 大于 0 的页框？
4. 节点页面：槽式（Slotted-page）重排布局
在 B+ 树的物理实现中，树中的每一个逻辑节点均独占一整个 4096 字节的物理页。无论是叶子节点还是负责路由的内部节点，两者在底层均共享同一套页面拓扑格局，仅在单元格承载的载荷语义以及头部 link 字段的指向属性上有所差异。工业级存储引擎普遍将这种将“间接槽位指针”与“自底向上生长的数据区”相分离的物理设计称为槽式页面（Slotted Page）。
4.1 页头元数据
src/node.h 的文件头注释以紧凑的形式给出了前 12 字节的固定排布：
* 偏移 0，1 字节：节点类型，1 = 叶子，2 = 内部节点
* 偏移 1，1 字节：保留，写 0
* 偏移 2，2 字节：单元格数量
* 偏移 4，2 字节：单元格内容区的起点
* 偏移 6，2 字节：保留，写 0
* 偏移 8，4 字节：叶子：右边相邻叶子的页号（0 表示没有）；
* 内部节点：最右孩子的页号
* 偏移 12 起：单元格指针数组，每项 2 字节，按键升序排列2
3
4
5
6
7
8
在这段 12 字节的头部结构中，有两处工程细节格外值得品味： 首先是两处显式标注为“保留，写 0”的留白填充：由于节点类型标识只需 1 字节，随后紧接着留出 1 字节空洞，从而使 2 字节的单元格计数能够自然对齐在偶数偏移 2 上；同理，在内容区起点之后再次留出 2 字节，使得占用 4 字节的 link 目标页号能够精准对齐在 4 的倍数偏移 8 处。这种兼顾自然内存对齐的排布不仅提高了不同架构下的寻址效率，也为未来扩展页头保留了弹性空间。
其次，偏移 4 处的 content_start 仅分配了 16 位（2 字节）无符号整型来记录内容区起始偏移。在 src/node.c 中，作者使用 C11 标准的编译期断言 _Static_assert 明确锁死了这一假设：
/* C11：内容区起点用 16 位存放，页不能大于 65535 字节。 */
_Static_assert(DB_PAGE_SIZE <= 65535, "page offsets are stored in 16 bits");2
对于当前固定的 4096 字节页面，最大页内偏移为 4095，16 位无符号整数（最大可表达 65535）足以轻松覆盖全页。倘若未来有人尝试将单页尺寸强行调增至 65536 字节或更大，该断言便会在编译阶段果断报错阻断，防止因偏移量整型截断而产生灾难性的静默溢出。
节点页面的四大物理分区
在逻辑内存地址上，单个物理页由低地址向高地址依次划分成四个连续互锁的区域：
- 定长页头（Fixed Header）：占据页首 0～11 字节，固定 12 字节，持久化存储节点种类、单元格计数、内容区下界指针与右侧链接。
- 槽位指针数组（Cell Pointer Array）：紧贴页头自低地址向高地址线性生长。每个单元格占用 2 字节槽位，存放其对应实体在页内的绝对偏移。该数组的元素物理顺序始终严格锚定主键的升序。
- 连续空闲缓冲区（Free Space Gap）：夹在指针数组末端与内容区起始边界之间的纯空闲内存缝隙。
- 单元格内容区（Cell Content Area）：从页面物理末端（偏移 4095）自顶向下、逆向朝低地址推进，
content_start始终精确对准该区域当前占用的最低字节位置。
空闲区域的实时可用字节数由 node_free_space 函数直接算出，其值即为内容区起始偏移减去指针数组当前占用的右边界：
size_t node_free_space(const uint8_t *node) {
size_t pointers_end =
NODE_HEADER_SIZE + CELL_POINTER_SIZE * (size_t)node_cell_count(node);
return content_start(node) - pointers_end;
}2
3
4
5
4.2 两种单元格的拓扑
叶子节点中的单元格由三部分复合而成：4 字节整型主键、2 字节负载长度标记，以及紧随其后的变长行数据载荷。而内部节点的单元格则极为规整，仅由 4 字节主键与 4 字节子节点物理页号构成，恒定为 8 字节。
由于两种单元格在起始位置均无一例外地将 4 字节主键作为前导字段，提取键值的通用函数 node_key 可以完全忽略当前节点的具体类型，直接以统一路径解出键值：
uint32_t node_key(const uint8_t *node, int i) {
return get_u32(node_cell(node, i));
}2
3
在内部节点中，前 n 个单元格各自记录着对应左侧子树的物理页号；而对于整页中最右侧的那个子节点，则不再单独开辟单元格存储，而是直接寄居在页头的 4 字节 link 字段中：
uint32_t internal_child(const uint8_t *node, int i) {
if (i == node_cell_count(node)) {
return node_link(node);
}
return get_u32(node_cell(node, i) + 4);
}2
3
4
5
6
B+ 树经典定义中“n 个键将子树划分为 n + 1 个分支区间”的数学特性，正是通过“n 个单元格对应前 n 个子树、外加 1 个头部 link 指向最右子树”的物理结构精准实现的。
4.3 走读 .page 1
插入三行，页里有三个单元格：
mdrdb> insert 1 alice alice@example.com
ok
mdrdb> insert 2 bob bob@example.com
ok
mdrdb> insert 3 carol carol@example.com
ok
mdrdb> .page 1
page 1: leaf
cells 3, free bytes 3992, content start 4010, next leaf 0
cell 0: offset 4066, size 30, key 1
cell 1: offset 4040, size 26, key 2
cell 2: offset 4010, size 30, key 32
3
4
5
6
7
8
9
10
11
12
同一页的字节是这样的：
$ xxd -s 4096 -l 20 f1.db
00001000: 0100 0003 0faa 0000 0000 0000 0fe2 0fc8 ................
00001010: 0faa 0000 ....2
3
页头的 12 个字节画成位图是这样（.page 不打印的保留字节也标出来了）：
| 位偏移 | 字段 | 长度 | 取值 | 说明 |
|---|---|---|---|---|
| 0–7 | 类型 | 1 字节 | 01 | 1 = 叶子，2 = 内部节点 |
| 16–31 | 单元格数量 | 2 字节 | 0003 | 大端序，本例为 3 |
| 32–47 | 内容区起点 | 2 字节 | 0faa | 本例为 4010 |
| 64–95 | link | 4 字节 | 00000000 | 叶子：右邻页号；内部节点：最右孩子 |
一页的四个区域按地址从低到高是这样：
逐项对照：
| 偏移 | 字节 | 含义 |
|---|---|---|
| 0 | 01 | 节点类型 1，叶子 |
| 1 | 00 | 保留 |
| 2 | 0003 | 3 个单元格 |
| 4 | 0faa | 内容区起点 4010 |
| 6 | 0000 | 保留 |
| 8 | 00000000 | 右邻叶子页号 0，没有 |
| 12 | 0fe2 | 第 0 个指针，指向 4066 |
| 14 | 0fc8 | 第 1 个指针，指向 4040 |
| 16 | 0faa | 第 2 个指针，指向 4010 |
回顾这三个单元格在页面中的布局，数据实体是自页尾向页首倒序紧密堆叠的：最早入库的 alice 独占了地址最高的 30 个字节区间（4066 至 4095）；随后写入的 bob 占据 26 个字节（4040 至 4065）；最后写入的 carol 则占领了 4010 至 4039 的 30 字节空间。与之形成鲜明对比的是，前端槽位指针数组的逻辑索引（第 0 项、第 1 项、第 2 项）完全按照主键的升序排列，与实体数据在页内的物理前后毫无绑定：数组第 0 项指向物理地址最高的 alice，而数组第 2 项则反向指向地址最低的 carol。
每个单元格的内容也能直接读出来。alice 的 30 个字节：
$ xxd -s $((4096 + 4066)) -l 30 f1.db
00001fe2: 0000 0001 0018 0561 6c69 6365 1161 6c69 .......alice.ali
00001ff2: 6365 4065 7861 6d70 6c65 2e63 6f6d ce@example.com2
3
转储中的 00000001 对应主键 1，0018 标明载荷总长为 24 字节，前缀 05 引导 5 字节字符串 alice，前缀 11（十六进制 17）引导 17 字节邮箱。整项单元格的物理长度为 4 + 2 + 24 = 30 字节，与 .page 诊断输出中的 size 30 严丝合缝。
对于 bob 的单元格，由于名字 bob（3 字节）比 alice（5 字节）少 2 字节，邮箱 bob@example.com（15 字节）比 alice@example.com（17 字节）同样少 2 字节，因此其载荷长度缩减为 20 字节（十六进制 0x14），整项单元格尺寸相应缩至 6 + 1 + 3 + 1 + 15 = 26 字节。页面内的各项参数均可精确推演：单个叶子单元格尺寸为 6 + 记录长度，其中记录长度为 1 + 名字长度 + 1 + 邮箱长度；而此时页内连续空闲容量公式为 content_start − 12 − 2 × n，代入数值即为 4010 − 12 − 6 = 3992 字节。
单元格的物理位置是任意的
页里决定逻辑顺序的只有指针数组。按 3、1、2 的顺序插入三行，指针数组仍是 1、2、3，内容区里单元格的先后却是 3、1、2。任何按单元格的逻辑下标读写的函数都必须经过 pointer_at，不能按地址推算「下一个单元格」。
按 3、1、2 的顺序插入，输出如下。注意 cell 0 的偏移是 4036，比 cell 2 的 4066 小，因为 alice 是第二个插入的，放在当时内容区的最前面：
mdrdb> insert 3 carol carol@example.com
ok
mdrdb> insert 1 alice alice@example.com
ok
mdrdb> insert 2 bob bob@example.com
ok
mdrdb> .page 1
page 1: leaf
cells 3, free bytes 3992, content start 4010, next leaf 0
cell 0: offset 4036, size 30, key 1
cell 1: offset 4010, size 26, key 2
cell 2: offset 4066, size 30, key 32
3
4
5
6
7
8
9
10
11
12
指针数组那一行也跟着变：0fc4 0faa 0fe2，依次指向 4036、4010、4066。物理顺序 3、1、2 与逻辑顺序 1、2、3 完全是两回事。
4.4 插入单元格
插入分两步：字节放到内容区前面，指针数组腾出位置。
void node_insert_cell(uint8_t *node, int i, const uint8_t *cell, size_t size) {
int count = node_cell_count(node);
size_t start = content_start(node) - size;
memcpy(node + start, cell, size);
/* 指针数组里第 i 项及之后的项后移一格，空出第 i 项。 */
memmove(pointer_slot(node, i + 1), pointer_slot(node, i),
CELL_POINTER_SIZE * (size_t)(count - i));
put_u16(pointer_slot(node, i), (uint16_t)start);
put_u16(node + COUNT_OFFSET, (uint16_t)(count + 1));
put_u16(node + CONTENT_OFFSET, (uint16_t)start);
}2
3
4
5
6
7
8
9
10
11
单元格的物理插入遵循清晰的几何递推：新的数据块紧挨着现有内容区下界向下拓扑，content_start 相应削减 size 字节并作为新实体的写入起点；在低地址端，指针数组从索引 i 开始的所有旧槽位整体向后挪动一格，腾出的第 i 个槽位随即填入新实体的物理偏移地址。这里对内存拷贝函数的选用严格遵从 C 标准：拷贝新单元格使用 memcpy，因为源缓冲区位于调用栈上，两者地址完全互斥；而移动指针数组内部各槽位时必须严格使用 memmove，因为移动前后的源区间与目的区间在同一段内存中高度重叠，误用 memcpy 将构成未定义行为。在完成数据搬移后，页头的单元格计数器与内容区起点偏移被同步原子写回。
调用之前必须用 node_has_room 确认放得下，node_insert_cell 自己不做检查：
bool node_has_room(const uint8_t *node, size_t cell_size) {
return node_free_space(node) >= cell_size + CELL_POINTER_SIZE;
}2
3
在真正调用插入前，外层逻辑必须借助 node_has_room 进行容量断言：除了核算单元格载荷自身的 cell_size 之外，还必须预留出指针数组新增项所消耗的 2 字节槽位开销（CELL_POINTER_SIZE）。
4.5 删除与紧凑
删除的做法与插入相反，但多了一步搬动：
void node_remove_cell(uint8_t *node, int i) {
int count = node_cell_count(node);
size_t start = content_start(node);
size_t offset = pointer_at(node, i);
size_t size = node_cell_size(node, i);
/*
* 让内容区保持连续：把地址低于被删单元格的内容整体后移 size 字节，
* 再给指向这些内容的指针加上 size。空闲空间因此总是一整块，插入时
* 不用整理碎片。代价是每次删除都要搬动数据，一页之内，搬得起。
*/
memmove(node + start + size, node + start, offset - start);
memset(node + start, 0, size);
memmove(pointer_slot(node, i), pointer_slot(node, i + 1),
CELL_POINTER_SIZE * (size_t)(count - i - 1));
memset(pointer_slot(node, count - 1), 0, CELL_POINTER_SIZE);
for (int k = 0; k < count - 1; k++) {
size_t p = pointer_at(node, k);
if (p < offset) {
put_u16(pointer_slot(node, k), (uint16_t)(p + size));
}
}
put_u16(node + COUNT_OFFSET, (uint16_t)(count - 1));
put_u16(node + CONTENT_OFFSET, (uint16_t)(start + size));
}2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
当在叶子节点中执行物理删除时，MdrDB 采取了一种极度规整紧凑的维护策略：算法定位到被删记录的物理偏移，将其低地址侧（即在此之后追加写入的内容）整体向高地址平移 size 字节，瞬间抹平删除留下的空洞，并将这些被移动实体的槽位指针统一增加 size。这一设计确保了内容区自始至终高度紧密相连，content_start 顺理成章地向高地址回缩，页内所有的剩余容量永远凝聚为单一连续的整块空闲区间，彻底根除了内存外部碎片。删掉 bob 之后：
mdrdb> delete 2
ok
mdrdb> .page 1
page 1: leaf
cells 2, free bytes 4020, content start 4036, next leaf 0
cell 0: offset 4066, size 30, key 1
cell 1: offset 4036, size 30, key 32
3
4
5
6
7
在删除前，carol 的物理落点在 4010，处于内容区的最前沿；当处于其中间的 bob 被抹除后，carol 整体向后滑动 26 字节来到 4036，内容区起点随之更新为 4036。此时连续空闲空间从原本的 3992 激增至 4020 字节，净增的 28 字节恰好是 bob 单元格实体（26 字节）与对应槽位指针（2 字节）之和。
在数据库工程史上，关于页内删除存在另一种经典方案——维护页内空闲链表（Free List）。SQLite 的底层页面正是采用此法：删除时不移动既有数据，仅将废弃槽位串入空闲链表；后续插入时再按最佳适配（Best Fit）寻找碎片槽位，当碎片过多时再触发页内紧缩（Defragmentation）。空闲链表虽然规避了删除时的内存搬移，但大幅增加了页内寻址分配与合并碎片的算法复杂度。MdrDB 毅然选择了紧凑单块模型：在 4096 字节的微观页面内，单次 memmove 最多仅需复制两三千字节，现代 CPU 的 L1 缓存几微秒内便能瞬时完成，却换来了极为精简优雅的状态机；不仅免去了复杂的碎片清理逻辑，也让页内数据完整性校验 node_validate 能够借助一条平整的数学恒等式 used == DB_PAGE_SIZE - start 瞬间完成。
4.6 节点防御性校验：面向非可信输入的完整性卫导
在任何涉及外存持久化的工业系统中，从磁盘读取到的二进制页面均属于不可信数据（Untrusted Input）。一旦因异常掉电产生撕裂写、磁盘扇区坏道或恶意构造引起元数据错乱，上层未经校验的代码极易发生数组越界与非法内存访问。node_validate 构成了抵御数据污染的第一道防线：
bool node_validate(const uint8_t *node) {
if (node[KIND_OFFSET] != NODE_LEAF && node[KIND_OFFSET] != NODE_INTERNAL) {
return false;
}
int count = node_cell_count(node);
size_t start = content_start(node);
size_t pointers_end = NODE_HEADER_SIZE + CELL_POINTER_SIZE * (size_t)count;
if (pointers_end > start || start > DB_PAGE_SIZE) {
return false;
}
size_t header =
node_is_leaf(node) ? LEAF_CELL_HEADER_SIZE : INTERNAL_CELL_SIZE;
size_t used = 0;
for (int i = 0; i < count; i++) {
size_t offset = pointer_at(node, i);
if (offset < start || offset + header > DB_PAGE_SIZE) {
return false;
}
size_t size = cell_size_at(node, offset);
if (offset + size > DB_PAGE_SIZE) {
return false;
}
used += size;
}
/* 内容区紧凑：所有单元格加起来正好填满 [start, 页尾)。 */
return used == DB_PAGE_SIZE - start;
}2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
校验函数对页面的几何形态实施了严密的四维闭环校验：
- 校验首字节节点类型是否严格落在合法枚举（
NODE_LEAF或NODE_INTERNAL）之内； - 校验前端指针数组的末端物理边界是否越过了内容区的起始位置
start，杜绝前后两端发生碰撞挤压； - 逐个遍历所有槽位，断言其所指向的偏移与单元格尺寸均严格受限在物理单页内；
- 最为精妙的是末尾的等式断言：累计所有合法单元格的实际物理字节数，核对是否精准满足
used == DB_PAGE_SIZE - start。由于 MdrDB 保持了内容区的绝对紧缩，只要此等式成立，就从数学上同时证毕了“内容区内部无任何重叠交错”与“内容区内部无任何无主碎片空洞”。
在整棵 B+ 树的实现中，任何尝试接触页面内容的函数均统一由 load_node 进行收敛代理：
/* 取一页并确认它是格式正确的节点。文件可能损坏，先验证再解析。 */
static db_status load_node(pager *p, uint32_t pgno, page **out) {
if (pgno == 0) {
return DB_CORRUPT; /* 第 0 页是文件头，不会是树节点 */
}
db_status rc = pager_get(p, pgno, out);
if (rc != DB_OK) {
return rc;
}
if (!node_validate((*out)->data) || !payloads_fit((*out)->data)) {
pager_unpin(*out);
*out = NULL;
return DB_CORRUPT;
}
return DB_OK;
}2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
除了基础布局的结构合法性，随后的 payloads_fit 进一步对变长负载的尺寸上限实施了防御性过滤。这一补充检查至关重要：在 7.6 中我们将推导证明，一旦允许超过特定阈值的超大负载混入叶子页，将直接击穿 B+ 树分裂算法赖以成立的几何前提。
借助 .page 高效推导页面状态
在排查底层页内损坏或数据错位时，REPL 中的 .page n 点号元命令是最直接的诊断探针。它本质上就是 node_print 函数的交互式镜像，以格式化结构忠实反映当前物理页的每个槽位与偏移。当写入逻辑出现异常时，优先调用 .page 审视各项偏移是否满足数学自洽，往往能省去在调试器中逐字节转储内存的漫长时间。
5. 记录编码：紧凑的 varint 变长序列化
在 B+ 树的索引组织中，32 位无符号主键已被单独抽离并固化在单元格头部充当检索键，因而叶子节点单元格承载的负载内容只需全权负责存储业务字段 name 与 email。为了尽可能压缩磁盘占用，字符串字段的长度并未采用定长 2 字节或 4 字节存储，而是引入了与 Protocol Buffers 及 SQLite 同款的变长无符号整型（Variable-length Integer，简称 varint）编码：
/*
* varint：每字节低 7 位存数据，最高位为 1 表示后面还有字节，低位组
* 在前（与 Protocol Buffers 相同）。小于 128 的数只占 1 字节，名字和
* 邮箱的长度大多在这个范围内，比固定用 2 字节省空间。
*/
size_t varint_encode(uint32_t value, uint8_t *out) {
size_t n = 0;
while (value >= 0x80) {
out[n++] = (uint8_t)(value | 0x80);
value >>= 7;
}
out[n++] = (uint8_t)value;
return n;
}2
3
4
5
6
7
8
9
10
11
12
13
14
varint 编码的数学机制十分精巧：每个编码字节仅使用低 7 位承载数值的有效位，最高有效位（MSB）充当“连续标记位”（Continuation Bit）。若最高位为 1，表明后续字节仍属于该数值的高位片段；若最高位为 0，则表明当前字节为该数值的终结字节。数值的低位分组优先存放（Little-Endian Base-128）。终端下的转储直观展示了不同数值区间的物理压缩形态：
$ ./varint_demo
5: 05
127: 7F
128: 80 01
300: AC 022
3
4
5
以数值 300 为例：其二进制原码为 0000 0001 0010 1100。提取最低 7 位 010 1100（十六进制 0x2C），因高位仍有有效数据，将最高位打上 1 形成首字节 1010 1100（即十六进制 0xAC）；右移 7 位后剩下数值 10（即十进制 2），此时已小于 128，最高位置 0 直接输出 0000 0010（即 0x02）。由此，300 被紧凑压缩为两个字节 AC 02。
在这一规则下，凡是不超过 127 的非负整数均仅占 1 个物理字节。引入变长编码的工程动机与表模式的长度分布息息相关：在当前场景中，name 限制为 32 字节，email 最长 255 字节，在现实业务的大多数典型数据中，字符串长度几乎都落在 127 以内。若机械采用定长 2 字节存储长度，每个字段都会浪费近半的元数据开销。为此，单元测试套件 test_record 专门选取了 0、1、127、128、300、16383、16384 等跨越阈值边界的关键值进行往返编解码断言，验证其在极端边界下的保真性。
单条行记录的物理载荷仅包含 name 与 email 两个连续段落：record_encode 首先求得两个字段的实际字节数，随后依次借助内部辅助函数 put_text 完成打包。每个字段均被编码为标准的“长度前缀 + 原始文本字节”序列，且文本结尾的空字符 '\0' 均被隐式剥离不存入磁盘。在测定字符串长度时，text_length 的实现中隐藏着关键的安全边界考量：
static db_status text_length(const char *text, size_t capacity, size_t *len) {
const char *end = memchr(text, '\0', capacity);
if (end == NULL) {
return DB_TOO_LONG;
}
*len = (size_t)(end - text);
return DB_OK;
}2
3
4
5
6
7
8
在长度检测算法上，工程放弃了常规的 strlen，转而使用 memchr 在严格限定的容量边界内主动探测空字符 '\0'。在 db_row 结构体中，name 字段被声明为 char name[DB_NAME_MAX + 1]。倘若上层调用者由于缓冲区填充失误，将数组的全部 33 个字节塞满有效字符而未保留合法的空字符终止符，传统的 strlen 会发生无节制的内存逃逸，一路向后越界读取导致段错误；而 memchr 最多扫描 capacity 字节，一旦在界限内未命中 '\0'，便立即返回业务错误 DB_TOO_LONG，彻底消除隐匿的越界隐患。自动化测试 test_record 中的 test_record_rejects_unterminated_field 用例正是针对这一安全防线所作的专项验证。
解码一侧把文件里的每个数字都当成不可信的输入：
/* 读一个文本字段。长度是否超限、是否越过记录末尾、内容里有没有 '\0'，
* 逐项核对：文件里的任何数字都不可信。 */
static db_status get_text(const uint8_t *in, size_t size, size_t *pos,
char *out, size_t max) {
uint32_t len;
size_t n = varint_decode(in + *pos, size - *pos, &len);
if (n == 0 || len > max || len > size - *pos - n) {
return DB_CORRUPT;
}
const uint8_t *text = in + *pos + n;
if (memchr(text, '\0', len) != NULL) {
return DB_CORRUPT; /* 文本里有 '\0'，读出来会被截断 */
}
memcpy(out, text, len);
out[len] = '\0';
*pos += n + len;
return DB_OK;
}2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
这里的连续四个条件判断分别精确拦截了四类潜在的物理损坏：
n == 0：varint 自身结构非法（例如到达记录尾端仍未遇见标记位为 0 的终结字节，或位宽溢出 32 位）；len > max：反解出的字符串长度超越了内存目标接收缓冲区的物理上限，防止发生缓冲区溢出；len > size - *pos - n：声明的字符串长度向后延伸越过了当前记录主体的物理末尾；memchr探测：在有效文本段落内部竟发现了内嵌的空字符'\0'，表明文本内容本身遭遇了截断污染。
最后，外层总控函数 record_decode 还追加了一条刚性守门规则：在顺序反解完全部字段之后，遍历指针 pos 必须与该记录传入的物理总长度 size 精准重合，任何尾部附带的垃圾游离字节均被断定为 DB_CORRUPT 数据损坏：
db_status record_decode(const uint8_t *in, size_t size, db_row *row) {
size_t pos = 0;
db_status rc = get_text(in, size, &pos, row->name, DB_NAME_MAX);
if (rc == DB_OK) {
rc = get_text(in, size, &pos, row->email, DB_EMAIL_MAX);
}
if (rc == DB_OK && pos != size) {
rc = DB_CORRUPT; /* 记录末尾多出了字节 */
}
return rc;
}2
3
4
5
6
7
8
9
10
11
测试用例 test_record 对此设计了极其严苛的故障样本注入矩阵：包括 {10, 'a', 'b'}（长度声明恶意溢出记录边界）、{1, 'a', 1, 'b', 0xEE}（记录尾端恶意携带多余游离字节）、{1, 'a'}（字段残缺不全）、{2, 'a', 0, 0}（文本内部注入空字符），以及长度超过 32 字节的名字越界样本。
针对 varint 本身的解码，varint_decode 同样对超出 32 位整型表示范围的恶意载荷构筑了理论闭环：
size_t varint_decode(const uint8_t *in, size_t size, uint32_t *value) {
uint32_t result = 0;
for (size_t i = 0; i < size && i < VARINT_MAX_SIZE; i++) {
uint32_t bits = in[i] & 0x7Fu;
if (i == VARINT_MAX_SIZE - 1 && bits > 0x0Fu) {
return 0; /* 第 5 个字节只剩 4 位可用，再多就超出 32 位 */
}
result |= bits << (7 * i);
if ((in[i] & 0x80u) == 0) {
*value = result;
return i + 1;
}
}
return 0;
}2
3
4
5
6
7
8
9
10
11
12
13
14
15
在 Base-128 编码体系下，一个 32 位无符号整数最多只需 5 个字节即可完整表达。在第 5 个字节中，由于前面 4 个字节已经消费了 bits > 0x0Fu，说明该数值在数学上已经无可挽回地溢出了 32 位范围，解码器直接返回 0 宣告失败。这种纯粹的防御性设计将整型溢出引发的隐式截断提前化解为可预测的错误状态。
varint_encode(300, buf) 写出几个字节，内容是什么？
6. B+ 树的二分检索与路径探查
在 MdrDB 的 B+ 树体系中，各层节点遵循清晰明确的区间划分哲学：内部路由节点中的每个单元格均保存着一个分隔键（Separator Key）与其对应的左子树页号；凡是物理上位于键 i 之前的子树，其中所包含的所有键均严格小于键 i；而当待查键与某个分隔键恰好相等时，根据 B+ 树叶子节点复制上提的性质，目标实体必然归属于该分隔键右侧的子树。
6.1 内部节点的路由契约与叶子链表
在遍历检索过程中，系统使用 tree_path 栈对象记录自顶向下寻径所经过的全部节点足迹：
typedef struct tree_path {
int depth; /* 层数，pgno[depth - 1] 是叶子 */
uint32_t pgno[BTREE_MAX_DEPTH]; /* 每一层经过的页 */
int slot[BTREE_MAX_DEPTH]; /* 每一层走的是第几个孩子 */
} tree_path;2
3
4
5
/*
* 在内部节点里为 key 选孩子。第 i 个孩子里的键都小于第 i 个分隔键，
* 且不小于第 i - 1 个分隔键；等于分隔键的 key 属于它右边的孩子。
*/
static int child_slot(const uint8_t *node, uint32_t key) {
bool found;
int i = node_search(node, key, &found);
return found ? i + 1 : i;
}2
3
4
5
6
7
8
9
二分查找辅助函数 node_search 始终返回第一个大于或等于 key 的槽位下标。若页面中未命中完全相等的键，该下标对应的值便是首个严格大于目标键的分隔键，算法依循左闭右开区间顺理成章地选取左侧子节点（即槽位 i）；若页面中命中了完全相等的分隔键，根据分裂契约，该键的物理数据行已被保留在右侧叶子节点中，因此算法必须精准向右偏移一格选取下标为 i + 1 的右侧子树。
在底层的叶子节点之间，水平贯通的双向链表同样在这套契约下紧密编织：新分裂出的右叶顺理成章地继承左叶原先的后继邻居，而左叶的后继链接则刷新指向新诞生右叶的物理页号：
node_set_link(right->data, link); /* 右叶接替原来的右邻 */
node_set_link(left->data, right->pgno); /* 左叶的右邻是新叶 */2
内部节点里的分隔键是 62，查找键 62 时走哪个孩子？
6.2 自顶向下寻径：下潜至叶子节点
自根节点向下穿梭的核心逻辑封装在 find_leaf 函数中：
static db_status find_leaf(pager *p, uint32_t key, tree_path *path) {
uint32_t pgno = BTREE_ROOT;
for (int level = 0; level < BTREE_MAX_DEPTH; level++) {
page *pg;
db_status rc = load_node(p, pgno, &pg);
if (rc != DB_OK) {
return rc;
}
path->pgno[level] = pgno;
if (node_is_leaf(pg->data)) {
path->depth = level + 1;
pager_unpin(pg);
return DB_OK;
}
path->slot[level] = child_slot(pg->data, key);
pgno = internal_child(pg->data, path->slot[level]);
pager_unpin(pg);
}
return DB_CORRUPT; /* 树不可能这么深，多半是页之间形成了环 */
}2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
寻径的算法推进方式体现了系统在内存受限环境下的精细权衡：在每一层循环中，当前页面的逻辑页号与所选取的下游分支槽位被实时压入调用栈上的 tree_path 结构中；更关键的是，在通过 internal_child 获得下游子节点的页号后，系统立即主动调用 pager_unpin(pg) 释放当前父页面的钉住锁定，随后再调用 load_node 载入下一层节点。这种“走一步释放一步”的单步钉住策略，使得树无论深入到何种层级，在单次遍历期间对 Pager 缓冲池的额外页框占用始终恒定为 1，确保了系统即便在极限的 4 页框配置下也能游刃有余地完成深层检索。
此外，MdrDB 在节点物理元数据中刻意省略了反向的“父节点页号指针”（Parent Pointer），这一决策与后续的树形分裂算法高度绑定：
借助调用栈 tree_path 避免反向父指针
如果在磁盘页面中显式持久化父节点的物理页号，虽然省去了外部栈，但在节点分裂与整树增高时会引爆灾难性的连锁修改写放大。尤其是当根节点被填满触发分裂增高时，原本根节点的内容会被全量克隆至新页，这意味着其下属的所有一级子节点内部持久化的“父节点指向”全部都需要逐一读出、打脏并刷新修改为新页号。改用外部栈对象 tree_path 之后，自顶向下的一次探查便顺带在调用栈上捕获了从根至叶的整条访问路径，后续若触发自底向上的级联分裂，算法只需逆序回溯栈帧即可精确定位父节点，磁盘页面无需维护任何脆弱的反向依赖。为此付出的代价仅仅是在调用栈上分配一个容纳最大深度 BTREE_MAX_DEPTH（定义为 16）的极小数组对象，总内存占用仅百余字节。
实现中的 BTREE_MAX_DEPTH 深度阈值还扮演着抵御恶意文件环路攻击的熔断哨兵：在正常的百万级数据规模下，B+ 树的高度通常仅为 2 到 3 层；若下潜深度触及 16 这一理论天花板，唯一的合理解释是磁盘损坏导致页面间的子节点链接形成了死循环环路，函数此时果断返回 DB_CORRUPT。
6.3 页内二分定位与点查闭环
当算法成功下潜至目标叶子节点后，页内所有单元格的有序定位便交由经典的二分查找算法 node_search 完成：
int node_search(const uint8_t *node, uint32_t key, bool *found) {
int count = node_cell_count(node);
int lo = 0;
int hi = count;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (node_key(node, mid) < key) {
lo = mid + 1;
} else {
hi = mid;
}
}
*found = lo < count && node_key(node, lo) == key;
return lo;
}2
3
4
5
6
7
8
9
10
11
12
13
14
15
该二分查找的核心契约是：在由槽位指针构成的有序序列中，寻找首个键值大于或等于 key 的槽位索引，并通过输出参数 *found 告知是否精准命中。这一返回值设计精妙地兼顾了三类完全不同的业务上下文：在按键点查 btree_find 中，调用端依据 *found 裁定是否存在目标；在写操作 btree_insert 中，返回值直接标明了新单元格理应插入的物理槽位位置；而在内部路由 child_slot 中，该索引则充当下游子树的分支选择标尺。
在计算中点时，代码采用了 mid = lo + (hi - lo) / 2 这一标准工业实践，避免了传统表达式 (lo + hi) / 2 在高位数值相加时发生整型有符号溢出的风险。
完整的按键点查入口 btree_find 将上述的自顶向下下潜与页内二分检索自然地缝合在一起：
db_status btree_find(pager *p, uint32_t key, uint8_t *payload, size_t *size) {
tree_path path;
db_status rc = find_leaf(p, key, &path);
if (rc != DB_OK) {
return rc;
}
page *leaf;
rc = load_node(p, leaf_of(&path), &leaf);
if (rc != DB_OK) {
return rc;
}
bool found;
int i = node_search(leaf->data, key, &found);
if (!found) {
rc = DB_NOT_FOUND;
} else {
const uint8_t *src = leaf_payload(leaf->data, i, size);
if (*size > BTREE_MAX_PAYLOAD) {
rc = DB_CORRUPT;
} else {
memcpy(payload, src, *size);
}
}
pager_unpin(leaf);
return rc;
}2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
值得留意的是，虽然 find_leaf 在下潜终点已经把叶子节点的页号锁存进了 path.pgno[path.depth - 1]，但由于它在返回前已遵循契约对该页执行了 pager_unpin，外层的 btree_find 必须重新发起一次 load_node 以建立对该叶子页的新引用。由于该页面刚刚被访问过，在 LRU 机制的保护下必然精确命中内存页框，无需触发任何实际磁盘物理 IO。
7. 动态维护：节点插入、级联分裂与整树增高
向 B+ 树写入一条新记录是存储引擎中状态转移最复杂的物理流程。依据当前目标页面的几何剩余空间，插入逻辑会在以下三种物理分支间平滑切换：
- 就地容纳：目标叶子节点尚有充裕空闲空间，直接在页内腾挪槽位完成单元格插入；
- 节点对半切分（Split）：目标节点空间耗尽，系统申请新页，将原有数据与新数据按字节容量均分至两页，并向父节点上提分隔键；
- 根节点垂直分裂增高（Grow Root）：分裂一路向上级联波及至根节点，物理第 1 页克隆新生，整棵树在高度上垂直长高一层。
7.1 放得下就插入
/* 节点放得下就把 cell 插到第 index 个位置，*done 置为 true。 */
static db_status insert_if_room(pager *p, uint32_t pgno, int index,
const uint8_t *cell, size_t size, bool *done) {
*done = false;
page *pg;
db_status rc = load_node(p, pgno, &pg);
if (rc != DB_OK) {
return rc;
}
if (node_has_room(pg->data, size)) {
rc = pager_write(p, pg);
if (rc == DB_OK) {
node_insert_cell(pg->data, index, cell, size);
*done = true;
}
}
pager_unpin(pg);
return rc;
}2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
在执行任何页内物理字节修改之前，代码严格前置调用了 pager_write。这一调用顺序构成了事务原子性的红线：pager_write 的使命是在当前页面发生变动前将其最原始的镜像抓取并追加落入回滚日志；若颠倒次序先调用 node_insert_cell 改写了内存，再调用 pager_write，写入日志的将是被污染后的新快照，导致后续异常回滚时无法还原历史现场。
7.2 叶子分裂
放不下时，把原单元格和新单元格一起取出来，排好序，按字节数一分为二：
/*
* 分裂用的临时区：节点原有的单元格加上新单元格，按键的顺序排好。
* 合计可能超过一页，所以不能在页面里原地操作。
*/
typedef struct cell_list {
int count;
size_t used;
uint16_t offset[NODE_MAX_CELLS + 1];
uint16_t size[NODE_MAX_CELLS + 1];
uint8_t bytes[2 * DB_PAGE_SIZE];
} cell_list;2
3
4
5
6
7
8
9
10
11
由于节点分裂涉及原有单元格与待插入新单元格的重排重组，其总字节量可能在短时间内突破单页 4096 字节的硬界限，因而无法在原页面内存中原地完成交换。临时结构体中的 bytes[2 * DB_PAGE_SIZE] 开辟了整整双倍页面规格的连续暂存区，足以从容容纳原页数据与新单元格的合并载荷；而 offset 偏移数组的大小特意声明为 NODE_MAX_CELLS + 1，确保在既有槽位配额上额外追加一项时绝不发生越界溢出。
collect_cells 把原单元格和新单元格按顺序排好：
static void collect_cells(const uint8_t *node, int index, const uint8_t *cell,
size_t size, cell_list *list) {
int count = node_cell_count(node);
list->count = 0;
list->used = 0;
for (int i = 0; i <= count; i++) {
if (i == index) {
cell_list_add(list, cell, size);
}
if (i < count) {
cell_list_add(list, node_cell(node, i), node_cell_size(node, i));
}
}
}2
3
4
5
6
7
8
9
10
11
12
13
14
循环写成 i <= count，因为新单元格可能插在最后（index == count）。每一轮先把新单元格放在第 index 个位置，再放原有的第 i 个，下标正好对齐。
split_point 选分裂位置：
static int split_point(const cell_list *list) {
size_t total = 0;
for (int i = 0; i < list->count; i++) {
total += list->size[i] + CELL_POINTER_SIZE;
}
size_t left = 0;
int m = 0;
while (2 * left < total) {
left += list->size[m] + CELL_POINTER_SIZE;
m++;
}
return m;
}2
3
4
5
6
7
8
9
10
11
12
13
与某些教材中“按单元格个数机械五五开”的简化思路不同，MdrDB 的切分点选取算法 split_point 严格以实际字节物理占用为考量基准。在支持变长字段的数据库中，不同单元格的尺寸悬殊极大（例如一条短记录仅 30 字节，而一条长记录可能达近 300 字节）；若粗暴按个数对半切分，极易导致某一侧分得过多长记录而在回填新页时再次撑爆页面。算法中的判定表达式 2 * left < total 是对“左半侧累计容量尚未触及总容量一半”的精妙整型无除法表达；当累加循环首次使得左半侧容量达到或跨越全页总负载中点时循环终止，此时输出的 m 便是归属于左侧页面的单元格绝对计数。
static void fill_node(uint8_t *node, node_kind kind, const cell_list *list,
int from, int to) {
node_init(node, kind);
for (int i = from; i < to; i++) {
/* split_point 保证放得下；断言把这条推理写进代码。 */
assert(node_has_room(node, list->size[i]));
node_insert_cell(node, i - from, list->bytes + list->offset[i],
list->size[i]);
}
}2
3
4
5
6
7
8
9
10
那句断言把「两半都装得下」这条推理写进了代码。7.6 会讲它成立的条件。
叶子分裂的结果：
if (node_is_leaf(left->data)) {
/* 叶子：右半的第一个键复制一份上去当分隔键，这一行仍留在右叶。 */
fill_node(left->data, NODE_LEAF, &list, 0, m);
fill_node(right->data, NODE_LEAF, &list, m, list.count);
node_set_link(right->data, link); /* 右叶接替原来的右邻 */
node_set_link(left->data, right->pgno); /* 左叶的右邻是新叶 */
} else {2
3
4
5
6
7
左半留在原页，右半放进新页；右叶接替原来的右邻，左叶指向新叶。分隔键是 list_key(&list, m)，也就是右半的第一个键，复制一份上去，那一行本身还留在右叶：
*separator = list_key(&list, m);
*right_pgno = right->pgno;2
7.3 内部节点分裂
内部节点放不下时，做法与叶子不同：第 m 个单元格整个移进父节点，它的孩子归左半：
} else {
/* 内部节点：第 m 个单元格整个移进父节点，它的孩子归左半。 */
fill_node(left->data, NODE_INTERNAL, &list, 0, m);
node_set_link(left->data, list_child(&list, m));
fill_node(right->data, NODE_INTERNAL, &list, m + 1, list.count);
node_set_link(right->data, link);
}2
3
4
5
6
7
在内部节点的重组中，左侧节点继承前 m 个单元格（槽位 0 至 m−1），右侧节点承接从 m+1 开始的后续单元格。处于正中分界线的第 m 个单元格被全权抽调提拔至父节点，其所携带的原子节点指针（由 list_child(&list, m) 获取）则顺位晋升为左侧节点的最右侧子树，被写入左页头的 link 字段中；而右侧节点的最右子树则继承原节点先前的旧 link 指针。
为什么叶子分裂采取“复制上推（Copy-up）”而内部节点分裂采取“移动抽离（Push-up）”？这一深刻差异源于数据在 B+ 树各层的驻留语义： 在叶子层中，由于数据库的所有实际数据行记录均必须完好存放在叶子节点内，右叶的首个键即便被选为父节点的分隔键，其实体行记录依然必须完整留在右叶内供业务检索，因此只能对其键值做一份副本上推；而在内部路由层中，第 m 个键的作用仅在于充当左右两半区间的逻辑分水岭，当它被提拔至父节点后，其下方左子树的所有键值均严格小于它，右子树的所有键值均严格大于它，原节点内部无需再为该键保留槽位，将其整项抽离上移正好两全其美。
7.4 根长高
根装不下时，根页号不能变，否则整个数据库都要改「根在哪一页」。做法是把根的内容搬到新页，根变成只有一个孩子的内部节点：
static db_status grow_root(pager *p, uint32_t *child_pgno) {
page *root;
page *child;
db_status rc = load_node(p, BTREE_ROOT, &root);
if (rc != DB_OK) {
return rc;
}
rc = pager_write(p, root);
if (rc == DB_OK) {
rc = pager_allocate(p, &child);
}
if (rc == DB_OK) {
memcpy(child->data, root->data, DB_PAGE_SIZE);
node_init(root->data, NODE_INTERNAL);
node_set_link(root->data, child->pgno);
*child_pgno = child->pgno;
pager_unpin(child);
}
pager_unpin(root);
return rc;
}2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
grow_root 的操作一气呵成： 首先将根节点的原始数据整页深拷贝至新分配的子页中，随后将物理第 1 页就地重新格式化为一个崭新的内部节点，并将其最右子树指针 link 精准锁定在刚才分配的子页页号上。在此瞬间，物理第 1 页作为新根暂时没有任何单元格，仅存在一个唯一的子节点分支——这也是整棵 B+ 树在生命周期中唯一允许“内部节点单元格数量为 0”的合法瞬态；随着后续对该子节点执行切分，提拔上来的首个分隔键便会立即填入根节点的第 0 个槽位中。
在经典数据库架构中，SQLite 的 B 树实现 balance_deeper 函数所贯彻的正是这一精巧的就地升格逻辑，只是额外附带了多连接共享缓存下的并发状态同步开销。
下面用小记录走一遍分裂。用 293 字节的长记录，一页正好放 13 个单元格（13 × 295 = 3835，剩 249 字节不够第 14 个），第 14 行触发分裂。14 个单元格共 14 × 295 = 4130 字节，一半是 2065：
mdrdb> .tree
internal 1: 1 key
leaf 2: 7 keys (1..7)
key 8
leaf 3: 7 keys (8..14)
mdrdb> .check
ok: rows 14, leaf pages 2, internal pages 1, height 2
mdrdb> .page 1
page 1: internal
cells 1, free bytes 4074, content start 4088, right child 3
cell 0: offset 4088, size 8, key 8, child 22
3
4
5
6
7
8
9
10
11
左半累计到第 7 个是 7 × 295 = 2065，正好达到一半，m 停在第 7 个之后，左半拿 7 个（键 1～7），右半拿 7 个（键 8～14）。第 8 个单元格的键 8 被复制上推成分隔键，它自己还在右叶里。.page 1 里的 cell 0: offset 4088, size 8, key 8, child 2 就是这条内部单元格，right child 3 是右叶的页号。
这次分裂发生在根上：原来的 13 行都在根这个叶子里。所以引出了 grow_root：根的内容先搬到新的第 2 页，根变成内部节点，然后再分裂第 2 页。.info 里页数从 2 变成 4，多出来的就是新的根内容页和右叶。
7.5 沿路径向上递归
/* 把 cell 插入路径第 level 层节点的第 index 个位置，必要时向上分裂。 */
static db_status insert_cell(pager *p, const tree_path *path, int level,
int index, const uint8_t *cell, size_t size) {
bool done;
db_status rc =
insert_if_room(p, path->pgno[level], index, cell, size, &done);
if (rc != DB_OK || done) {
return rc;
}
uint32_t node = path->pgno[level];
uint32_t parent = BTREE_ROOT;
int slot = 0;
if (level == 0) {
rc = grow_root(p, &node); /* 之后根就是 node 的父节点 */
} else {
parent = path->pgno[level - 1];
slot = path->slot[level - 1];
}
uint32_t right = 0;
uint32_t separator = 0;
if (rc == DB_OK) {
rc = split_node(p, node, index, cell, size, &right, &separator);
}
/*
* 父节点里原来指向 node 的位置改指右半，再在它前面插入
* (separator, node)：
* ... [slot] -> node ...
* => ... (separator, node) [slot + 1] -> right ...
* 先改指针再插入：插入若引起父节点分裂，这个指针会随单元格一起搬走。
*/
if (rc == DB_OK) {
rc = set_child(p, parent, slot, right);
}
if (rc != DB_OK) {
return rc;
}
uint8_t parent_cell[INTERNAL_CELL_SIZE];
internal_cell_build(parent_cell, separator, node);
/* level 为 0 时，父节点是刚长高的根，里面是空的，一定插得进去。 */
int parent_level = level > 0 ? level - 1 : 0;
return insert_cell(p, path, parent_level, slot, parent_cell,
sizeof parent_cell);
}2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
父节点接收分裂成果的动作被巧妙解耦为两步原子变换：原先父节点在第 slot 个位置上的指针指向分裂前的 node；算法首先通过 set_child 将该槽位的下游指向修正为分裂出的右侧新页 right；紧接着在相同的 slot 位置前置插入全新的内部单元格 (separator, node)。这次插入动作会平滑地将原先位于 slot 上的槽位及其关联的 right 指针整体向右挤压至 slot + 1 位置，最终呈现为标准的路由拓扑：第 slot 个单元格指引小于分隔键的数据流向左节点 node，而其后继槽位（或页头 link）则顺理成章地将大于等于分隔键的流量导入右节点 right。若父节点自身也随之装满，该函数将顺着 path 栈自底向上递归触发更上层内部节点的分裂，直至根节点增高。
这两步的推进次序蕴含着严谨的物理时序约束：必须先执行 set_child 修正指针，后调用 insert_cell 插入单元格。若颠倒执行，一旦父节点此时恰好已处于饱和临界态，新单元格的插入将瞬间引爆父节点的二次分裂，原先预备修改的目标槽位连同其关联的子树指针会被整体重排迁入新页；此时若再以旧页号调用 set_child，便会在物理上击中错误的位置甚至改写已迁走的原有槽位。而先就地刷新指针指向，指针便稳妥地驻留在预定槽位中，即便随后的插入触发分裂，该指针也会伴随整个单元格的平移迁移至合法的宿主页中。
向上递归的基底终止条件是 insert_if_room 成功落位。每递归一层，level 向上递减 1；当推演至树根（level == 0）时，父节点由刚才被垂直抬升的新根充当，其内部除了一条 link 指针外空空如也，拥有近乎完整的 4096 字节可用空间，因而新单元格必然能够稳稳入驻，整条递归链在根节点处绝对收敛闭环。
7.6 为什么单记录负载上限被严格限制在页内可用空间的四分之一
分裂算法能够平稳运转的充要数学前提，是切分后的左右两半必须能够无条件各自装入一个 4096 字节的物理新页。split_point 的策略仅能保证左半侧首次累加至总负载的二分之一；倘若允许系统中混入某个超大单元格，在极端边界下极易产生“左半侧刚超半页、而右半侧剩余的一个单体巨型单元格自身就突破半页甚至挤爆整页”的灾难，从而导致 fill_node 内部的容量断言 assert(node_has_room(...)) 当场崩溃。
为了在编译期从理论上根除这种空间假死，MdrDB 定义了严格的容量常数 BTREE_MAX_PAYLOAD：
/*
* 负载上限：一个单元格（连同指针）不超过页内可用空间的 1/4。这样
* 一个叶子至少放得下 4 个单元格，分裂后的两半也一定都装得下。
*/
#define BTREE_MAX_PAYLOAD \
((DB_PAGE_SIZE - NODE_HEADER_SIZE) / 4 - CELL_POINTER_SIZE - \
LEAF_CELL_HEADER_SIZE)2
3
4
5
6
7
将单页 4096 字节与页头 12 字节代入公式计算：
「两半都装得下」的推导
可用的空间是 4084 字节（4096 − 12）。设所有单元格连同指针总共 S 字节，第 i 个记为 s_i。
split_point 选出的 m 满足：左半 L = s_0 + … + s_{m−1} 是第一个达到或超过 S/2 的前缀。去掉最后一个单元格之后不足一半，所以 L < S/2 + s_{m−1}；右半 R = S − L，于是 R ≤ S/2。
S 的上界是原页可用的 4084 加上新单元格。新单元格也受 BTREE_MAX_PAYLOAD 限制，s_{m−1} ≤ 1013 + 2 = 1015，所以 S ≤ 5099，R ≤ 2549.5，远小于 4084。
L < S/2 + s_{m−1} 的两项分别不超过 2549.5 和 1015，加起来不超过 3564.5，也小于 4084。两半都装得下。
test_node 里有一条测试验证一页能放多少个。用 100 字节的负载填满一页，每个单元格 106 字节，加指针 108 字节：
/* 每个单元格 106 字节，加指针 108 字节：(4096 - 12) / 108 = 37。 */
CHECK(node_cell_count(node) == 37);2
37 是 4084 / 108 的整数部分，与 node_has_room 每次都要留 2 字节指针的算法一致。
这条推导依赖「页里的每个单元格都不超过 BTREE_MAX_PAYLOAD」。插入时 btree_insert 检查了这一条：
if (size > BTREE_MAX_PAYLOAD) {
return DB_TOO_LONG;
}2
3
但磁盘上的页可能已经损坏，load_node 因此除了 node_validate，还要调用 payloads_fit：
/*
* 叶子单元格的负载不超过 BTREE_MAX_PAYLOAD。插入时检查过的数据一定
* 满足这一条，损坏的文件却未必；分裂算法要靠它保证两半都装得下（见
* split_point），所以取页时要与页内布局一起检查。
*/
static bool payloads_fit(const uint8_t *node) {
if (!node_is_leaf(node)) {
return true; /* 内部单元格是定长的 */
}
for (int i = 0; i < node_cell_count(node); i++) {
size_t size;
(void)leaf_payload(node, i, &size);
if (size > BTREE_MAX_PAYLOAD) {
return false;
}
}
return true;
}2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
payloads_fit 是必需的一道检查：10.4 节有一个真实的例子说明少了它会写到页外。
7.7 观察：顺序插入后左边的叶子都半满
300 行顺序插入之后，树长到两层：
mdrdb> .tree
internal 1: 4 keys
leaf 2: 61 keys (1..61)
key 62
leaf 3: 60 keys (62..121)
key 122
leaf 4: 57 keys (122..178)
key 179
leaf 5: 57 keys (179..235)
key 236
leaf 6: 65 keys (236..300)
mdrdb> .check
ok: rows 300, leaf pages 5, internal pages 1, height 22
3
4
5
6
7
8
9
10
11
12
13
当这 300 条记录全部就位后，根节点容纳 4 个分隔键，向下管辖 5 个叶子节点。细看各叶子的单元格分布可以发现一种有趣的物理现象：各个页面的利用率并不均等，第 2 页存有 61 个键，而最右侧的第 6 页则累积了 65 个键。这一分布完全是由对半切分算法决定的： 在顺序递增写入场景下，user1 到 user9 的单项单元格占用 30 字节，user10 到 user99 占用 32 字节，user100 及以后则扩展至 34 字节；连同每项 2 字节的槽位指针，前 119 个单元格累计占据 4068 字节，当第 120 条记录涌入时，所需总空间突破了单页可用上限 4084 字节，瞬间触发叶子分裂。此时 120 项单元格合计 4104 字节，经由 split_point 按物理字节精准对半切分，左半侧 61 个单元格被保留在原物理页，右半侧 59 个单元格迁移至新分配的第 3 页，分隔键取自右半侧首个键值 62。在此之后，由于后续主键呈单调递增，所有新数据流均无一例外地涌入最右侧的活跃叶子页，留在左侧的历史页（如第 2 页）从此封板，其单元格计数便永久定格在半满的 61 项上。
第 120 行触发分裂时的树是这样的：
mdrdb> .tree
internal 1: 1 key
leaf 2: 61 keys (1..61)
key 62
leaf 3: 59 keys (62..120)2
3
4
5
此后最右边的叶子继续接收新键，满了（连同新键约 120 个单元格）就再分裂一次，左半留在原页从此不动。分出来的右半页一次装 57～60 个键：第 3 页 60 个、第 4 页 57 个、第 5 页 57 个。最终就是 61、60、57、57、65 这个分布。
最后那个叶子 6 有 65 个键，因为插入到 300 就停了，还没满。如果再插入，它会继续增长到满才分裂。
xxd 看内部节点的第 1 页：
$ xxd -s 4096 -l 20 big.db
00001000: 0200 0004 0fe0 0000 0000 0006 0ff8 0ff0 ................
00001010: 0fe8 0fe0 ....2
3
02 是内部节点，0004 是 4 个单元格，0fe0 是内容区起点 4064，00000006 是最右孩子（第 6 页），后面四个指针 0ff8、0ff0、0fe8、0fe0 依次指向 4088、4080、4072、4064，四个内部单元格各占 8 字节，从页尾往前排。与 .page 1 的输出逐项吻合：
mdrdb> .page 1
page 1: internal
cells 4, free bytes 4044, content start 4064, right child 6
cell 0: offset 4088, size 8, key 62, child 2
cell 1: offset 4080, size 8, key 122, child 3
cell 2: offset 4072, size 8, key 179, child 4
cell 3: offset 4064, size 8, key 236, child 52
3
4
5
6
7
四个孩子页号 2、3、4、5 分别是左叶、第三叶、第四叶、第五叶，最右孩子 6 存在 link 里。.tree 里 internal 1: 4 keys 下面那 5 个叶子正好对应这 5 个孩子。
7.8 顺序写入下的填充率权衡与快速分裂优化
split_point 始终恪守五五均分，这一策略对于数据分布均匀的随机插入是极其优良的，能使树的全局形态保持平衡；然而在主键自增的顺序追加场景中，它却暴露出明显的存储利用率代价：除了最右侧始终在接收新数据的叶子节点外，左侧所有已经沉淀的历史叶子节点几乎都恒定停留在 50% 左右的半满状态。集成测试 test_btree 中的 test_ascending_and_descending 专门针对单调递增与单调递减序列实施了全路径覆盖。
在成熟的工业实现中，诸如 SQLite 等系统在此处设计了一套专属的快速追加优化——balance_quick：当检测到写入溢出发生在最右侧边缘叶子、且新写入的键值严格大于当前页所有已有键时，存储引擎不再费力执行五五对半分裂，而是直接开辟一个全新的右侧兄弟页，仅将溢出的那一条孤立记录单独迁入新页。这样一来，左侧的历史叶子节点便能以 100% 的极高饱和度封箱保存，大幅压低全库的物理总页数与磁盘膨胀率。README 扩展任务第 4 条就是这个，比较 300 行顺序插入后的 .tree 与页数，能看到明显差别。
8. 删除与游标
8.1 删除不合并
db_status btree_delete(pager *p, uint32_t key) {
tree_path path;
db_status rc = find_leaf(p, key, &path);
if (rc != DB_OK) {
return rc;
}
page *leaf;
rc = load_node(p, leaf_of(&path), &leaf);
if (rc != DB_OK) {
return rc;
}
bool found;
int index = node_search(leaf->data, key, &found);
if (!found) {
rc = DB_NOT_FOUND;
} else {
rc = pager_write(p, leaf);
if (rc == DB_OK) {
node_remove_cell(leaf->data, index);
}
}
pager_unpin(leaf);
return rc;
}2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
在删除实现上，MdrDB 展现了极强的工程极简主义：算法从根下潜定位到目标叶子页后，仅仅调用 node_remove_cell 在页内抹除该单元格并紧凑剩余数据。它不向相邻兄弟节点借位（Borrowing），不触发空闲阈值下的节点合并（Coalescing），也不向文件系统回收空页。
这就引出了一个教科书式的经典理论疑虑：如果被删除的数据行恰好是父节点中记录的分隔键，父节点中的分隔索引并未被同步抹去，整棵树的检索语义是否会产生偏差？
惰性删除下分隔键的数学有效性
在 B+ 树的路由模型中，分隔键本质上是作为子树键值空间的绝对边界（Partition Boundary）而存在的。假设父节点中的分隔键为 62，其左侧子树的所有数据均满足 btree_check 中对键值区间闭包的验证也不会出现任何断言异常。
这种设计的工程红利十分显著：删除操作完全被拘禁在当前单一叶子页内，绝不引发任何自底向上的跨层递归修改，极大地精简了写路径的状态机复杂度。当然，其代价是放弃了磁盘空间的就地回收收缩：数据库文件在物理上只增不减。即便在业务层将 300 条记录全量清空，底层已分配的 5 个叶子页面依然驻留在文件中，根节点也依然保持为内部路由节点。删完 300 行的 .tree：
mdrdb> .tree
internal 1: 4 keys
leaf 2: 0 keys
key 62
leaf 3: 0 keys
key 122
leaf 4: 0 keys
key 179
leaf 5: 0 keys
key 236
leaf 6: 0 keys
mdrdb> .check
ok: rows 0, leaf pages 5, internal pages 1, height 2
mdrdb> select
(0 rows)2
3
4
5
6
7
8
9
10
11
12
13
14
15
select 仍然工作，因为游标跳过空叶子。README 扩展任务第 3 条是把删除时的借位与合并补上，并且把释放的页挂到一个空闲页链表里复用，btree_check 也要相应增加最小填充率与空闲页链表的检查。
8.2 游标机制与安全范围扫描
为了支撑顺序扫描与区间查询，系统提供了轻量级的游标对象 btree_cursor。它在逻辑上维护当前定位的叶子页号 leaf、页内槽位索引 index 以及当前单元格的主键缓存 key：
typedef struct btree_cursor {
pager *pager;
uint32_t leaf;
int index;
uint32_t key; /* 当前单元格的键，用来确认每走一步键都变大 */
bool valid; /* false 表示已经走过最后一个键 */
} btree_cursor;2
3
4
5
6
7
在游标的推进模型中，MdrDB 做出了一个极为务实的设计抉择：游标步进时绝不长期钉住内存页面。在游标完成某一项数据的读取之后，其所在的物理页立即被释放（Unpin）。这一机制解除了游标存活期与事务缓冲池之间的紧耦合：上层业务完全可以在两次推进调用 btree_next 的间隙自由发起其他查询或独立的内存操作，无需担忧有限的物理页框被遍历游标长期强占而引发缓存饥饿。但这一灵活性带来的契约约束同样非常刚性：在范围遍历的回调函数内部严禁夹带写操作。因为一旦在遍历期间触发增删引起页内单元格重排或节点分裂，未被钉住的页面结构随时会发生空间位移，游标原先持有的 index 槽位索引将瞬间失去对应关系，甚至导致游标漂移错位。
游标状态机的稳定落脚由 settle 函数全权把控：
static db_status settle(btree_cursor *c) {
uint32_t steps = 0;
for (;;) {
page *pg;
db_status rc = load_node(c->pager, c->leaf, &pg);
if (rc != DB_OK) {
return rc;
}
bool leaf = node_is_leaf(pg->data);
int count = node_cell_count(pg->data);
uint32_t next = node_link(pg->data);
uint32_t key = c->index < count ? node_key(pg->data, c->index) : 0;
pager_unpin(pg);
if (!leaf) {
return DB_CORRUPT;
}
if (c->index < count) {
if (c->valid && key <= c->key) {
return DB_CORRUPT; /* 键没有变大：叶子链接错了或成了环 */
}
c->key = key;
c->valid = true;
return DB_OK;
}
if (next == 0) {
c->valid = false;
return DB_OK;
}
if (++steps >= pager_page_count(c->pager)) {
return DB_CORRUPT; /* 走过的叶子比总页数还多：链表成了环 */
}
c->leaf = next;
c->index = 0;
}
}2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
settle 的核心使命在于将可能悬空的游标（例如刚进入新页、或当前槽位越界）平顺牵引至下一个真正包含有效记录的单元格上。如果当前叶子节点已被读尽，算法顺着页头的 link 跃迁至相邻的右侧叶子节点；由于系统支持惰性删除，磁盘上可能并列存在着多个被完全掏空的零数据叶子页，因而该寻径过程必须在一个安全受控的循环中推进。
在此处，算法构筑了两道极为强悍的防御性屏障，确保在面对损坏的磁盘输入时绝不陷入无限死循环：
- 步数熔断：单次牵引累计横跨的空叶子页总数绝不允许超过当前数据库的总页数配额
pager_page_count；一旦超标，表明叶子链表在物理上形成了环状拓扑死锁，立即返回DB_CORRUPT； - 键值单调递增断言：每次游标成功定格在某一有效记录上时，其主键
key必须严格大于上一落脚点锁存的主键（key <= c->key即判定损坏）。这道防线是作者在排查极端故障时特意补齐的：倘若仅有前一条步数限制，一旦链表中出现一个包含有效数据的环路，每次推进都会因读到实体数据而重置连续空页计数，导致select全表扫描陷入狂乱的无限打印循环中。在早期的鲁棒性回归测试中，曾因单字节磁盘翻转导致第 13 页的叶子指针错误指回前驱，未加单调性断言的旧版程序在 5 秒内疯狂输出了超过 1400 万行重复数据。
看一个具体的范围查询。删掉 1、61、62 之后，第 2 页从键 2 开始，第 3 页从 63 开始：
mdrdb> select 60 63
(60, user60, user60@example.com)
(63, user63, user63@example.com)
(2 rows)2
3
4
btree_seek(p, 60, &c) 下降到第 2 页，node_search 找到键 60 的位置；btree_read 读出一行；btree_next 把 index 加 1，超出这一页的单元格数，settle 沿 link 走到第 3 页，index 归零，停在键 63 上。db_scan 再读一行，键 64 大于 last（63），循环结束。
8.3 空叶子节点的两套遍历适应
惰性删除所残留的空叶子节点，在存储引擎的两套遍历路径上表现出截然不同的行为特征： 其一是区间扫描路径（btree_seek 配合 btree_next），该路径沿着水平的叶子链表向右推进，内部由 settle 负责平滑掠过空叶子；其二是整树巡检路径（btree_check），该路径以经典的中序深度优先遍历（先递归左子树、后核验自身节点）顺次巡查所有物理页面。这两套路径均必须对“单元格计数为 0 的叶子节点”保持完全兼容与容错。集成测试 test_btree 中的 test_random_insert_and_delete 专门设立了极限用例：在经历剧烈随机写入后将整库数据全量逐条删除，随后再度追加写入 100 个新主键，整棵树的结构完整性与检索功能依然毫发无损。
在树形可视化诊断函数 print_node 中，针对空叶子节点做了特殊适配输出：
fprintf(out, "%*s%s %" PRIu32 ": %d key%s", level * 2, "",
leaf ? "leaf" : "internal", pgno, count, count == 1 ? "" : "s");
if (leaf && count > 0) {
fprintf(out, " (%" PRIu32 "..%" PRIu32 ")", node_key(pg->data, 0),
node_key(pg->data, count - 1));
}2
3
4
5
6
当节点为叶子且有效键数量大于 0 时，终端才会追加打印主键区间 (min..max)；若是空叶子节点，则仅输出 leaf 2: 0 keys，既直观反映了物理存在，又避免了解码空区间的逻辑冲突。
9. 存储层一致性自检状态机
为了在软件运行期与故障恢复后能够确凿判定整棵索引树的结构健康度，系统实现了深度的树形不变式校验算法 btree_check。该算法从根节点出发递归遍历全树，不仅是单元测试与集成测试的基础守门员，也是交互式终端元命令 .check 以及每次崩溃恢复协议执行后的第一道健康核验屏障。
B+ 树全局健康的不变式准则
- 合法寻址界限：所有访问到的物理页号严格处于
[1, page_count)区间内（第 0 页保留给文件头，绝不可能作为树节点被引用）； - 拓扑单亲无环：除根节点外，全树中每一个节点有且仅有一个父节点引用，绝不存在多重引用或拓扑环路；
- 页内几何紧凑：各个物理节点内部排布完整通过
node_validate校验，且各单元格之间绝对无交叠重合； - 载荷上限规约：叶子单元格承载的变长数据严格受限于
BTREE_MAX_PAYLOAD阈值之内； - 键值单调递增与区间闭包：所有单元格的主键严格落在父节点界定的数值区间
[low, high)内，且同页内部的主键严格呈单调递增； - 非空路由保证：除尚未完成二次切分的刚升格新根外，所有内部路由节点至少包含 1 个有效键；
- 严格全局平衡：所有叶子节点在整棵树中所处的逻辑深度（Level）完全相等；
- 逻辑双链一致性：中序深度优先遍历所触及的叶子节点时序，与叶子节点头部 link 指针串接的水平链表物理时序 100% 绝对契合；
- 孤儿页零容忍：除物理第 0 页文件头外，当前数据文件中分配的所有物理页面必须无一遗漏地全部被挂接在这棵树的拓扑骨架之中。
static const char *node_problem(const uint8_t *node, uint64_t low,
uint64_t high) {
if (!node_validate(node)) {
return "bad page layout";
}
if (!payloads_fit(node)) {
return "payload is too long";
}
if (cells_overlap(node)) {
return "cells overlap";
}
int count = node_cell_count(node);
if (!node_is_leaf(node) && count == 0) {
return "internal node has no keys";
}
for (int i = 0; i < count; i++) {
uint32_t key = node_key(node, i);
if (key < low || key >= high) {
return "key outside the range given by the parent";
}
if (i > 0 && key <= node_key(node, i - 1)) {
return "keys are not in ascending order";
}
}
return NULL;
}2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
上述九项准则在代码中被严谨地映射为一个个防御性分支。“内部节点至少包含 1 个键”在工程中存在唯一的临时例外：在 grow_root 刚将旧根克隆至子页、且尚未完成对该子页的分裂之前，新根物理上仅包含一个指向子页的最右孩子指针。但在对外暴露的任何事务边界上，分裂都是紧随其后原子完成的，因此持久化的静态检查中绝不允许出现键数量为 0 的内部节点。
递归遍历的主体逻辑 check_node 则将自顶向下的深度优先遍历与自左向右的水平链表核验融为一体：
static db_status check_node(check_state *s, uint32_t pgno, int level,
uint64_t low, uint64_t high) {
if (level >= BTREE_MAX_DEPTH) {
return corrupt(s, pgno, "tree is too deep");
}
if (pgno == 0 || pgno >= pager_page_count(s->pager)) {
return corrupt(s, pgno, "page number out of range");
}
if ((s->seen[pgno / 8] >> (pgno % 8)) & 1u) {
return corrupt(s, pgno, "page is referenced twice");
}
s->seen[pgno / 8] = (uint8_t)(s->seen[pgno / 8] | (1u << (pgno % 8)));
s->visited++;
page *pg;
db_status rc = pager_get(s->pager, pgno, &pg);
if (rc != DB_OK) {
return rc;
}
const char *problem = node_problem(pg->data, low, high);
bool leaf = node_is_leaf(pg->data);
int count = node_cell_count(pg->data);
uint32_t link = node_link(pg->data);
pager_unpin(pg);
if (problem != NULL) {
return corrupt(s, pgno, problem);
}
if (leaf) {
if (s->leaf_level < 0) {
s->leaf_level = level;
} else if (level != s->leaf_level) {
return corrupt(s, pgno, "leaves are at different depths");
}
/* 叶子是按键的顺序访问的，叶子链必须与这个顺序一致。 */
if (s->last_leaf != 0 && s->last_link != pgno) {
return corrupt(s, s->last_leaf, "leaf chain skips a leaf");
}
s->last_leaf = pgno;
s->last_link = link;
s->stats.leaves++;
s->stats.keys += (uint32_t)count;
return DB_OK;
}
s->stats.internals++;2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
在内部节点的分支递归中，函数通过 i <= count 的循环依次巡检各子树：第 i 个子树所覆盖的数值区间为 [child_low, child_high)，其下界取自前驱分隔键，上界取自当前分隔键；对于最左侧的第 0 个分支与最右侧的分支，其外边界则顺理成章地继承自父节点传递下来的全局上下界。在此处，low 与 high 采用 uint64_t 宽整型进行参数传递，这是因为整棵树根节点的理论搜索上界为
在巡检推进时，函数同样贯彻了“走一步释放一步”的单步钉住原则，不长期钉住当前父页面。虽然在遍历其多个子树时会反复调用 pager_get 重新获取父页，但这几次调用由于 LRU 缓存热度必然精确命中内存页框，带来的开销微乎其微；而带来的巨大工程优势在于：哪怕面对包含数万个键、深达三层、物理跨度上百页的大型数据库，一致性自检全过程消耗的页框配额仅仅只需极少数几个，使得即使在 4 页框的极限环境下也可以从容执行全局校验。
在整树递归完成归一后，算法追加了关键的收尾两项断言：
db_status rc = check_node(&s, BTREE_ROOT, 0, 0, (uint64_t)UINT32_MAX + 1);
if (rc == DB_OK && s.last_link != 0) {
rc = corrupt(&s, s.last_leaf, "last leaf points to another leaf");
}
if (rc == DB_OK && s.visited != pages - 1) {
/* 除文件头外每一页都属于这棵树：MdrDB 从不释放页。 */
snprintf(message, message_size,
"%" PRIu32 " pages are not part of the tree",
pages - 1 - s.visited);
rc = DB_CORRUPT;
}2
3
4
5
6
7
8
9
10
11
中序遍历访问到的最后一个叶子节点，其右邻指针 last_link 必须严格为 0，以此断言水平叶子链表在末尾正确封口；随后核对整场深度优先遍历实际探查到的节点总数 s.visited 是否精准等于 pages - 1。在 MdrDB 当前文件只增不减的极简模型中，任何未被挂在树上的游离页面都构成了不可饶恕的存储泄漏损坏。
在交互终端中执行 .check 元命令，反馈直观明了：
mdrdb> .check
ok: rows 300, leaf pages 5, internal pages 1, height 22
在核心行接口层中，db_check 在驱动 btree_check 完成全树几何拓扑断言之后，还会主动沿着水平链表从头至尾遍历整表，调用 record_decode 尝试逐行解码每条记录的文本载荷。即便遇到某些极罕见的外力单字节损坏——即页面结构与指针数组几何自洽、但内部存储的字符串变长长度被破坏的静默损坏，该机制同样能即刻捕获并输出形如 row 7: record cannot be decoded 的精准定位报告。
10. 故障推演：偏离设计约束会引发什么
深入理解一个存储引擎的最佳途径，莫过于亲手打破它的某项核心设计假设，并观察其在错误路径上的崩溃形态。以下四个推演实验均在独立的临时构建副本中进行，通过刻意诱发典型缺陷，展现底层防御机制的拦截全貌。
10.1 分隔键加 1
把 split_node 里的分隔键改成右半第一个键加 1：
*separator = list_key(&list, m) + 1;用这个版本插入 20 行长记录，执行 .check：
mdrdb> .tree
internal 1: 1 key
leaf 2: 7 keys (1..7)
key 9
leaf 3: 13 keys (8..20)
mdrdb> .check
error: page 3: key outside the range given by the parent2
3
4
5
6
7
分隔键 9 把右叶划成「大于等于 9」，但右叶里还有键 8。查找 8 时会走左叶，而 8 不在左叶，返回值是「不存在」。test_btree 跑起来有 1770 处检查失败：
btree_check: page 3: key outside the range given by the parent
btree_check: page 536: key outside the range given by the parent
...
FAIL test_root_grows
FAIL test_ascending_and_descending
FAIL test_random_insert_and_delete
ok test_duplicate_and_oversized
ok test_cursor_scan
FAIL test_tiny_cache
ok test_rejects_oversized_payload
ok test_scan_detects_leaf_cycle
34059 checks, 1770 failed2
3
4
5
6
7
8
9
10
11
12
中间省掉了九百多条 check failed，页号有 3、84、536、992 等等。
无需在调试器中断点单步跟踪，一致性检查器直接在日志第一行输出了受损页面的具体物理编号与越界动因，为外存排障提供了无可替代的现场定位能力。
10.2 删除时漏掉指针修正
去掉 node_remove_cell 里的那个修正循环：
for (int k = 0; k < count - 1; k++) {
size_t p = pointer_at(node, k);
if (p < offset) {
put_u16(pointer_slot(node, k), (uint16_t)(p + size));
}
}2
3
4
5
6
内容整体后移了，但指针还是旧值，指向已经挪走的位置。test_node 的 test_remove_compacts_content 立刻失败，随后程序崩溃：
tests/test_node.c:75: check failed: node_key(node, 0) == 10 && node_key(node, 1) == 30
tests/test_node.c:76: check failed: payload_is(node, 0, "aaaa") && payload_is(node, 1, "cccccc")
tests/test_node.c:79: check failed: node_validate(node)2
3
三次检查失败之后进程收到 SIGSEGV 终止，shell 在命令行上打出 Segmentation fault，退出码 139。
崩溃的根源在于：当抹除前驱单元格时，由于漏掉了指针槽位的地址修补，后续槽位指针依然固执地指向未搬移前的旧偏移；随后再次调用删除时，算法算出的重叠平移长度 offset - start 发生回绕或变成超大数值，引发越界内存踩踏。这一破坏性实验生动证明了软件架构的分工原则：node_validate 仅能在宏观上捍卫页面的静态几何约束，一旦槽位指针在语义上指向了错误的实体内部，故障便可能滞后至下一次写操作时才以段错误形式爆发。
10.3 漏掉 pager_write
在 insert_if_room 里把 pager_write 去掉，直接改页：
if (node_has_room(pg->data, size)) {
node_insert_cell(pg->data, index, cell, size);
*done = true;
}2
3
4
两次自动提交的插入，同一个进程里读得到，重新打开就没了：
mdrdb> insert 1 alice alice@example.com
ok
mdrdb> insert 2 bob bob@example.com
ok
mdrdb> select
(1, alice, alice@example.com)
(2, bob, bob@example.com)
(2 rows)
mdrdb>2
3
4
5
6
7
8
9
mdrdb> select
(0 rows)
mdrdb>2
3
在单个进程的活动期内，上层的读取之所以能查出刚插入的记录，仅仅是因为其直接访问了驻留在页框缓存池中的那块脏内存；但由于跳过了 pager_write，该页从未被打上 dirty 脏页标记，因而在事务提交退出时被持久化刷盘逻辑彻底忽略，当新进程重新挂载磁盘文件时，一切未落盘的虚幻修改均化作乌有。在对应的测试套件中，test_btree 出现了多达 6357 处严重断言失败。这一现象揭示了系统级编程中极其重要的一条真理：在带缓存的存储架构中，“内存读得到”绝不代表“物理已落盘”。
10.4 去掉 payloads_fit
复核时发现的那个真实缺陷：删掉 load_node 里的 payloads_fit 检查，构造一个布局自洽、但有一个 3074 字节负载的叶子，再插入一行触发分裂。fill_node 里的断言立刻中止：
Assertion failed: node_has_room(node, list->size[i]), file src/btree.c, line 228在 Debug 调试构建模式下，运行时断言以可控的方式提前阻断了进程，这正是防御性断言的价值所在。倘若在 Release 生产编译时定义了 NDEBUG（导致断言语句被预处理器全量抹除），node_insert_cell 在为右半侧巨型单元格分配空间时，算出的内容区起点 start 将发生无符号整型下溢，向低地址反向越界改写属于槽位指针乃至页头元数据的神圣区域。在未引入该防御前，UBSan 未定义行为探测器曾捕获到布尔值越界污染等奇异错误，而在表层业务上插入甚至还给客户端返回了虚假的 ok 成功状态。因此，payloads_fit 为外存验证补齐了最后一块至关重要的拼图：磁盘页面内部的几何自洽，绝不能等同于变长载荷长度的合法有效。
11. 习题
11.1 巩固
不运行程序，先手算。在空库里依次插入 (1, alice, alice@example.com)、(2, bob, bob@example.com)、(3, carol, carol@example.com)，然后 .page 1。
(1) 三个单元格各占多少字节？写出 cell = 6 + 记录长度 的每一步。
(2) 三个单元格的偏移各是多少？从 4096 往下减。
(3) free bytes 和 content start 各是多少？用 content start − 12 − 2n 验算。
(4) 再 delete 2，content start 变成多少？为什么不是别的值？
写完用 mdrdb 实际跑一遍，对照 .page 1 的输出。四项全部一致才算通过。
(1) [2.1] src/format.h 的 get_u32 注释说「先转成 uint32_t 再移位」。写一个程序，把 {0xFF, 0x00, 0x10, 0x00} 分别用两种写法解成 32 位整数：一种每个字节先转 uint32_t，一种不转。在本机编译运行，比较结果。
(2) [3.2] 把不转的写法用 -fsanitize=undefined 编译。本机 MinGW 的 gcc 13.2 没带 libubsan，可以改用 Zig 自带的 clang：python -m ziglang cc -fsanitize=undefined；实测这样编出来的程序在 0xFF << 24 处收到 SIGILL 终止（退出码 132），没有打印诊断文字。用一句话说明：为什么本机两种写法碰巧给出相同结果，而标准上其中一种是未定义行为。
(3) [2.2] 写一个函数 read_page_bytes(const char *path, long pgno, uint8_t *out)，只让 file.c 的 file_read_at 读一页，其他代码不碰 FILE *。用它读 big.db 的第 1 页，打印偏移 0、2、4、8 四个字段。再用 xxd -s 4096 -l 20 big.db 对照，两者必须一致。
11.2 编程
给 db_print_page 增加一个检查工具：对指定的一页，按 node_validate 的规则逐项报告，而不是只返回 DB_CORRUPT。
要求：
(1) 新增一个内部函数 node_diagnose(const uint8_t *node, FILE *out)，逐项检查类型、指针数组末尾、每个单元格的偏移与长度、内容区是否紧凑，输出形如 offset 4036 + 30 > 4096、used 4050, expected 4084 的说明。
(2) 在 mdrdb 里加一条元命令 .verify <n>，对第 n 页调用它；布局正确时输出 page n: ok。
(3) 用 10.1 节的分隔键变异版生成的库测试：.check 说 key outside the range given by the parent，.verify 对相关页应当输出 page n: ok，因为页内布局本身没错。
验收：对正版 big.db 的每一页跑 .verify，全部输出 ok；对变异版跑，.check 报错而 .verify 通过，说明两条检查管的是不同层面。
把 pager 的顺序查找换成以页号为键的开放寻址散列表。
要求：
(1) 在 src/pager.c 里加一个 uint32_t *slots 数组，长度为 2 的幂，空槽用 UINT32_MAX 表示；散列函数自选，线性探测即可。页框被换出、pager_allocate 新页、pager_close 释放时都要维护它。
(2) find_frame 改成先查散列表；take_frame 换出后要把旧页号从表里删掉。
(3) 写一个测试 test_frame_lookup：用 64 个页框，反复取 1000 个不同的页号各 3 次，命中次数应当等于 2000（第一次是未命中）。
验收：ctest 全部通过，test_btree 的 34077 次检查不变。在报告里说明页框数为 1024 时，一次查找的比较次数从平均多少降到多少（用循环里实际执行比较的次数，或者直接给理论值）。
写一个 .record <id> 元命令，把指定主键的记录按字段拆开打印出来，未知的字节用十六进制显示。
要求：
(1) 用 db_find 取到负载，自己用 varint_decode 逐段解析，输出形如：
key 1
name len 5 "alice"
email len 17 "alice@example.com"
payload 24 bytes, 0 trailing2
3
4
(2) 负载里内嵌 '\0'、末尾有多余字节、长度越界时，分别输出一行说明（不要直接返回 DB_CORRUPT 了事）。
(3) 造三个库验证：正常行、手工把某个单元格的负载长度字段改大、手工在负载末尾加一个字节。后两个照 test_btree 里 replace_root 的做法，用 pager_get、pager_write 和 memcpy 直接改写页面，不走 btree_insert。
验收：三个库的输出各自与 .page 1 里的 size 对得上；第三种情况能指出「末尾多出 1 字节」。
child_slot 让等于分隔键的键走右边。把它改成走左边，先预测会破坏哪条不变式、哪个测试会先失败，再在副本里改并运行 test_btree。
要求：
(1) 写清楚预测：btree_check 会报哪条消息？哪几个测试会失败？
(2) 贴出 test_btree 的真实输出，与预测对照。
(3) 解释为什么 test_duplicate_and_oversized 可能不受影响（提示：它只插入两个键，树没有分裂过）。
验收：改在临时副本里，仓库代码保持原样；预测与实际对照的那一段是这道题的重点。
实现顺序插入优化（README 扩展任务第 4 条）：新键大于叶子里的所有键、且叶子放不下时，左叶保留全部旧单元格，只把新键放进新页。
要求：
(1) 在 split_node 之前判断：index == node_cell_count(left->data) 且 node_is_leaf(left->data) 时走快速路径，fill_node 只填右半。
(2) 注意 split_point 不再适用，separator 取新键。
(3) 顺序插入 300 行，比较 .tree 和 .info 的 page count。原来的结果是 5 个叶子、共 7 页；优化后应当是多少页？先预测，再实测。
(4) 用 test_btree 确认不影响其他场景，特别是 test_random_insert_and_delete 和 test_tiny_cache。
验收：ctest 全部通过；引用的两份 .tree 与 page count 都是真实运行结果；预测与实测不符时说明原因。
实现删除时的借位与合并，只做叶子层。
要求：
(1) 删除后如果叶子为空且不是根，先尝试从相邻兄弟借一个单元格（连同一个分隔键一起调整）；借不到就合并，把空页挂到文件头里的空闲页链表上。
(2) 文件头里用一个新字段记空闲链表的头，每个空闲页的开头 4 字节指向下一个空页（0 表示结束）；pager_allocate 优先从空闲链表取页。
(3) 扩展 btree_check：每一页要么属于树，要么在空闲链表里；叶子填充率不低于某个下限，下限自己定并说明理由。
(4) 说明 btree_delete 不合并时为什么查找仍然正确，以及合并之后这个理由为什么不再需要。
验收：ctest 全部通过；删光 300 行再插入 300 行，文件的页数不增加；.check 报出的 rows、leaf pages 正确。内部节点的合并可以只写文字说明。
11.3 综合与挑战
把页大小改成创建数据库时可选，并记在文件头里。
要求：
(1) 命令行加 --page-size <n>，只允许 512 到 65536 之间的 2 的幂；db_open 在新建文件时使用它，打开已有文件时从文件头读。
(2) 列出所有需要改动的常量与数组：DB_PAGE_SIZE、node.c 的 _Static_assert、page.data、NODE_MAX_CELLS、BTREE_MAX_PAYLOAD、cell_list.bytes、cells_overlap 里的 bool used[DB_PAGE_SIZE] 等。
(3) 实现之后，512 字节的页能不能正常工作？65536 字节的页为什么不能？结合 content start 的 16 位存储解释。
(4) 用 1024 字节的页建一个 300 行的库，跑 .check，贴出输出。
验收：512、1024、4096 三种页大小都能建库、插入、查询、.check 通过；对 65536 给出编译期拒绝的证据（_Static_assert 触发）。
12. 参考资料
code/项目/MdrDB/src/file.c、format.h、pager.c、node.c、btree.c、record.c与tests/：本页所有代码片段的出处，输出均由当前版本实测。- Database File Format（SQLite）：B 树页的单元格指针数组、单元格内容区、空闲块与碎片、varint。第 4 节关于「单元格物理位置任意」与删除时紧凑的讨论参照了它对页内布局的说明。
- Let's Build a Simple Database（cstack）：B+ 树的叶子分裂、根长高的讲法参照了第 7、8 部分。
- Alex Petrov，Database Internals（O'Reilly，2019，ISBN 978-1-492-04034-7），第 2～4 章：B 树的平衡、槽式页面、页内指针数组。
- Encoding（Protocol Buffers）：varint 的「低 7 位数据、最高位续位、低位组在前」，与
record.c的注释一致。 - setvbuf、fseek（cppreference）：
_IONBF的含义与fseek的偏移类型。 - 本教程：7.1 MdrDB 项目概述、7.3 查询路径、恢复与测试、SQLite 6.3 B 树与存储引擎、数据结构 10 B 树与外存数据结构。