索引
先来看一个世界上由 Bash 实现的最简单的数据库实现：
#!/bin/bash
db_set() {
echo "$1,$2" >> database
}
db_get() {
grep "^$1," database | sed -e "s/^$1,//" | tail -n 1
}
这种数据库通过追加文件尾部的方式高效写入，许多数据库内部都是用日志，日志是一个仅支持追加更新的数据文件。但是 db_get 的性能会随着数据量的变大而下降，为了解决这个问题就需要引入新的数据结构： 索引 。
索引是基于原始数据而派生而来的额外数据结构：适当的索引可以加速读取查询，但是回减慢写速度。
key-value 索引通常使用 hash map 来实现，最简单的索引策略：保存内存中的 hash map，把每个键一一映射到数据文件中特定的字节偏移量。
优化磁盘占用
- 将日志分解成一定大小的段，当文件达到一定大小时就关闭它，并将后续写入到新的段文件中。
- 然后可以在这些段上执行压缩：丢弃重复的键，并且只保留每个键最近的更新。
- 同时将变小后的多个段在后台合并在一起（段在写入后不再会进行修改所以不会出现竞争）。
- 合并完成后将读取请求切换到新的合并段上，然后可以安全的删除旧的段文件。
实现中面临的问题
- 文件格式：二进制。
- 删除记录：通过特殊的墓碑标记。
- 崩溃恢复：Bitcask 通过将 hash map 快照存储到磁盘。
- 部分写入：文件校验丢弃损坏的部分。
- 并发控制：只有一个写线程。
追加的好处
- 顺序写性能高。
- 并发控制和崩溃恢复简单。
- 段合并避免文件碎片化。
局限性
- 大量的键存储在内存可能导致内存耗尽，同时需要处理哈希冲突
- 区间查询效率不高。