索引

先来看一个世界上由 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 快照存储到磁盘。
  • 部分写入:文件校验丢弃损坏的部分。
  • 并发控制:只有一个写线程。

追加的好处

  1. 顺序写性能高。
  2. 并发控制和崩溃恢复简单。
  3. 段合并避免文件碎片化。

局限性

  • 大量的键存储在内存可能导致内存耗尽,同时需要处理哈希冲突
  • 区间查询效率不高。