从零写一个数据库

00数据库到底是什么

一句话：一个会自己保证「数据不丢、不错、不慢」的文件。

先把它拆掉神秘感。你写一段代码往文件里写 4096 字节，再读回来比对——那就是数据库的第一章。所有后面的东西（页、缓冲池、B 树、事务）都是在回答同一个问题的不同侧面：

• 怎么把数据放进文件？ → 固定大小的页。
• 怎么找得快？ → 页内用槽位、页间用 B+ 树。
• 怎么不丢？ → 先写日志再改数据，崩了重放。
• 怎么不慢？ → 内存里缓存一堆页，攒够了再落盘。

01文件 = 页的数组

数据库文件不是「一串字节」，而是「第 0 页、第 1 页、第 2 页……」。页大小固定 4096。

页大小选 4096 有两个原因：它等于一个磁盘扇区（操作系统本来就这么搬数据），而且够塞几十行小记录。固定的好处是——任何一页都能被同一个公式算出来，不需要索引文件本身。

// 打开/新建库的判据（顺序很重要）
if (size % 4096 != 0) 拒绝;      // 被截断过
if (memcmp(h.magic,"MINIDB01",8) != 0) 拒绝;  // 不是我的文件
if (h.page_size != 4096) 拒绝;

为什么页号从 0 开始、不跳号

因为「第 N 页」必须能直接算成字节偏移。一旦允许跳号，你就得额外存一张「页号 → 位置」的表，而那张表本身又得存在文件里——循环回来了。不跳号，公式就成立，公式成立，寻址就是 O(1)。

02页号 → 偏移

偏移 = 页号 × 4096。就这一条，没有例外。

size_t offset = (size_t)page_no * 4096;
file.seekg(offset);
file.read(buf, 4096);

看起来太简单，但它是整个系统能跑起来的地基：缓冲池靠它换页，B+ 树靠它定位子页，WAL 重放靠它找到该改哪一页。

03文件头：让程序认出自己人

页 0 不存数据，存的是「这个文件是谁、多大、怎么解释」。

八个字节的魔数是最便宜的身份证明：随便一个 txt 丢进来，前 8 字节对不上就立刻拒绝，而且不许修改文件。这条「拒绝时不动文件」比校验本身更重要——很多事故是校验失败后还硬写，把好数据写坏了。

04一页里怎么放记录

页不是随便塞的：前面长出一张「槽位表」，后面长出一条「记录区」，中间是空闲。

• 头部（前 16 字节）：nslots 有几个槽、low 槽位表长到哪、high 记录区长到哪、free = high − low。
• 槽位表从 low 往后长，每槽 2 字节，存「这条记录在第几字节」。
• 记录从第 4095 字节往前长，一条紧挨一条。

为什么要分成两头长？因为记录长度不一样。固定长度的话删一条就得整体挪，而两头长只需要改两个偏移量，删除是 O(1)。

删除为什么不能 nslots -= 1

槽位号是记录的身份。删掉第 2 条，如果把后面的槽整体前移，第 3 条就变成了第 2 条——所有指向「槽 3」的索引全部指错。正确做法是把这个槽标记作废（偏移写成 0xFFFF），记录区回收或标记死区。

05逐字节读写：PutU16 / GetU16

所有多字节整数一律小端：低字节在前。x86 天生小端，但你仍然要逐字节写。

void PutU16(unsigned char* p, uint16_t v) {
  p[0] = (unsigned char)(v & 0xFF);         // 低字节
  p[1] = (unsigned char)((v >> 8) & 0xFF);  // 高字节
}
uint16_t GetU16(const unsigned char* p) {
  return (uint16_t)(p[0] | (p[1] << 8));
}

为什么不用 memcpy 或指针强转？因为那样得到的是「这台机器上的字节序」。数据是要存到磁盘、给未来的程序读的，磁盘上必须有一个和机器无关的约定。

06插入、读取、删除

三个函数，把「手摆位置」变成可复用的一页操作。

// 插入：记录先放到 high 前面，槽位再指向它
low  += 2;
high -= len;
PutU16(page + low - 2, high);
memcpy(page + high, rec, len);

// 按槽号读
uint16_t off = GetU16(page + 16 + slot * 2);

// 删除：只作废槽位，不移动别人
PutU16(page + 16 + slot * 2, 0xFFFF);

顺序有讲究：一定要先把记录放好，再让槽位指向它。反过来写，万一中途断电，槽位会指向一块垃圾数据；按这个顺序，最坏情况是「有一条记录没人指向」，那是干净的泄漏，可以回收。

07缓冲池：磁盘太慢

一次磁盘读是微秒到毫秒级，一次内存读是纳秒级。中间差 1000 倍以上，所以必须缓存页。

做法很朴素：内存里开固定数量的槽（比如 64 个），每个槽放一页。要读页 5：先在槽里找，找到就叫命中；没找到就叫缺失，挑一个槽把它的页写回去，再把页 5 读进来。

挑哪个槽淘汰：LRU

「最久没用过的先走」。实现只需要给每页记一个最后访问时间（或维护一个链表）。看起来简单，坑在脏页：被改过的页必须先写回磁盘才能换出，否则改的东西就丢了。

08B+ 树：不再翻整页

一页能放几十条记录，扫一遍还行；放到一百万条，就是两万五千页，全扫一遍要读两万五千次磁盘。

B+ 树把「页」组织成三层：根页存「键 → 子页号」的分隔键，叶子页存真正的记录，叶子之间用链表串起来（方便范围查询）。找一条记录最多读三层，也就是三次磁盘。

为什么分裂发生在「满了再插一条」

一个叶子页最多放 N 条。插第 N+1 条时，把这一页对半分成两页，中间的键提上去给父页。父页满了就继续往上分裂，一路裂到根——根裂了就新建一层，树长高一层。整棵树永远平衡，这就是它比二叉搜索树适合磁盘的原因：高度低，读盘次数少。

09WAL：崩溃前的那一刻

写一半断电，是数据库唯一真正难对付的敌人。

办法是把「改哪里、改成什么」先顺序追加写进一个日志文件（WAL），写成功了才去改真正的数据页。日志是顺序写，比到处改页快得多，而且顺序写更不容易写坏。

崩溃恢复的三步

1. 扫描日志，找出崩溃那一刻还没提交的事务。
2. 重放（redo）已提交但没写进数据页的修改。
3. 撤销（undo）没提交的修改，把半截事务擦掉。

这就是为什么数据库敢在崩溃后说「已提交的一定还在」：提交的判据不是数据页写没写，而是日志有没有落盘。

10剩下的二十章

前面十章只是把「页」修好。真正让它成为数据库的，是后面这些。