从文件开始造一个键值数据库

问题

数据库最小要解决两件事：数据在程序退出后仍存在，并且能按 key 尽快找回。最直接的方案是把 key:value 写入文件，但原地更新一条变长记录可能迫使后续字节整体移动；顺序扫描又会让读取随文件增长而变慢。

append.log

1. 001: alpha
2. 018: beta

segments

active.log写入中

内存索引

001

0

018

11

查询结果

等待操作

更新 001删除 018查询 001压缩重置

2 条有效记录；索引指向各 key 的最新偏移。

直觉

先放弃原地修改。set 永远在文件末尾追加新版本，delete 追加一个墓碑；读取时采用某个 key 最后出现的记录。写入因此保持顺序且简单，但陈旧版本会堆积，需要后台压缩只保留最新有效值。

为了避免每次从头扫描，在内存中维护 key → offset 的哈希索引。写入多做一次索引更新，读取却可直接跳到最新字节位置。文件达到阈值后封存为不可变 segment，新写入进入新 segment；压缩时可以合并旧段。

形式化

日志是记录序列 $L=(r_0,\ldots,r_n)$，索引保存每个 key 的最后位置：

$$I(k)=\max\{i\mid r_i.key=k\}.$$

若 $r_{I(k)}$ 是墓碑，则查询不存在；否则返回它的 value。压缩生成只包含每个 key 最新非墓碑记录的新序列，同时重新计算偏移。进一步要求磁盘段按 key 排序并让内存表定期刷盘，就得到 LSM tree 的基本轮廓。

结果

交互模型允许连续更新、删除、查询和压缩。日志长度会增长，索引始终移动到最新 offset；压缩后陈旧版本和墓碑消失。它把三个经常被分别解释的对象——磁盘字节、内存索引、查询结果——放在同一个操作循环里。

限制

真实数据库还需要记录编码、校验和、崩溃恢复、WAL 刷盘策略、并发控制、segment 合并调度、稀疏索引与范围查询。本模型的 offset 是记录序号而非真实字节位置，也没有宣称性能数据。

来源

• 结构参考：Build Your Own Database，NaN；其叙事主要基于 Martin Kleppmann 的《Designing Data-Intensive Applications》第三章。
• 本页压缩为一个可重复操作的教学模型，正文和实现均为本站重写。