文章摘要
这篇文章介绍了如何从零开始构建一个键值数据库。作者以文件存储为基础，探讨了如何实现数据的持久化存储和高效查询，包括基本的增删改查操作。虽然最初的方法看似简单，但实际应用中会遇到可变更新等挑战。文章旨在引导读者理解数据库的基本工作原理。
文章总结
从零构建键值数据库：分步指南
本文详细介绍了如何从零开始构建一个键值数据库，并探讨了数据库设计中的核心概念和优化策略。
基础设计
键值数据库的工作原理类似于JavaScript中的对象——通过键存储值，并通过相同的键检索值：
$ db set 'hello' 'world'
$ db get 'hello'
world
持久化存储的核心问题
数据库需要解决两个核心问题： 1. 如何持久化存储数据 2. 如何高效查询数据
最简单的解决方案是使用文件存储键值对： - 插入：追加到文件末尾 - 查询：遍历文件查找匹配键 - 更新：找到键并原地替换值 - 删除：从文件中删除记录
性能优化挑战
原地更新的问题
原地更新和删除效率低下，因为修改记录可能需要移动后续所有数据。例如更新一个记录可能需要移动其后所有记录的位置。
只追加文件方案
解决方案是使记录不可变，只允许在文件末尾追加新记录： - 更新：追加新记录（会产生重复键） - 删除：添加特殊"墓碑"标记 - 查询：查找键的最后一次出现
这种方案带来两个新问题： 1. 文件会无限增长 2. 查询需要遍历所有记录，效率低下
优化策略
分段与压缩
解决方案： - 当文件达到一定大小时关闭它，创建新文件 - 旧文件进行压缩（删除无效数据） - 压缩后可以合并小文件
这样数据库由多个分段(segment)组成，通过定期压缩控制文件大小。
索引加速查询
使用内存中的哈希表作为索引： - 存储每个键在文件中的偏移量 - 查询时先查索引，直接定位记录位置 - 每个分段需要自己的索引
权衡： - 大幅提高查询速度 - 但写入变慢（需要维护索引） - 所有键必须能放入内存 - 范围查询效率仍然低下
高级优化：排序与LSM树
排序字符串表(SST)
通过保持数据按键排序： - 使范围查询更高效 - 允许使用稀疏索引（不必存储所有键的偏移量）
实现方式： 1. 在内存中维护排序的数据结构（如跳表） 2. 内存数据达到阈值时写入磁盘（已排序） 3. 查询时先查内存再查磁盘
为防止崩溃丢失数据，同时将写入追加到日志文件。
LSM树架构
最终我们实现了一个LSM(Log-Structured Merge Tree)树结构： - 内存中的排序结构(memtable) - 磁盘上的排序文件(SSTable) - 写入时先到内存，再定期刷盘 - 通过压缩控制文件大小
这种结构被LevelDB、DynamoDB等知名数据库采用，能够支持极高的吞吐量（如DynamoDB在Prime Day达到8000万QPS）。
总结
本文逐步展示了如何： 1. 从简单文件存储开始 2. 解决原地更新问题 3. 通过分段和压缩控制文件大小 4. 使用索引加速查询 5. 最终实现LSM树结构
虽然LSM树不是唯一方案（如关系数据库常用B树），但它为键值存储提供了高性能的解决方案。
[注：原文中具体的命令行示例和字节计算等细节已简化，保留了核心概念和设计思路]
评论总结
以下是评论内容的总结：
关于数据库本质的讨论
- 有评论认为数据库的核心是"持久化存储和高效查询"（评论1："How do we store data persistently and then efficiently look it up later?"）
- 反对观点认为没有事务处理就不算完整数据库（评论5："without transactions it is not a database yet"）
对文章设计的赞赏
- 多位用户称赞文章设计和动画效果（评论2："the design and animations are extremely pretty"；评论4："I love the design and examples in this post"）
技术实践相关
- 有用户分享简易键值存储代码示例（评论3展示bash脚本）
- 推荐数据库构建的免费在线书籍（评论6推荐build-your-own.org资源）
读者反馈
- 部分读者表示内容引发焦虑（评论8："my mind gets ahead of me...I get a bit weary"）
- 有用户请求增加RSS订阅功能（评论9："can you add an rss feed to your site?"）
- 赞赏"第一性原理"的讲解方式（评论10："love this 'first principles' approach"）
技术问题
- 网站可能因流量过大无法访问（评论7："it got hugged to death already"）