【LSM-Tree】SSTable + Bloom Filter：磁盘上的有序表
💡
原文中文，约26900字，阅读约需64分钟。
📝
内容提要
本文介绍了SSTable的构建与读取过程，重点在于数据块的前缀压缩和布隆过滤器的实现，强调其在减少无效I/O中的作用。SSTable通过分块存储数据，利用索引和布隆过滤器提高查找效率，避免不必要的磁盘读取。文章还提供了相关的C代码实现。
🎯
关键要点
- SSTable 是通过 MemTable 中的 key-value 数据按序写入磁盘生成的。
- SSTable 文件被切分为多个固定大小的块（Block），每个块独立压缩和校验，以提高读取效率。
- 数据块使用前缀压缩技术，减少存储空间，且相邻的 key 共享前缀。
- 使用 restart point 解决前缀压缩带来的随机访问成本问题，通过二分查找和线性扫描提高查找效率。
- Bloom Filter 在内存中使用固定大小的位数组，快速判断某个 key 是否存在，减少无效的磁盘 I/O。
- SSTable 文件格式包括数据块、元数据块、索引块和文件尾，确保高效的读取和存储。
- TableBuilder 负责构建 SSTable，管理数据块和索引块的写入，并生成 Bloom Filter。
- TableReader 负责读取 SSTable，首先加载文件尾，然后根据索引块和 Bloom Filter 定位数据块。
❓
延伸问答
SSTable 是如何构建的？
SSTable 通过 MemTable 中的 key-value 数据按序写入磁盘生成，数据被切分为多个固定大小的块，每个块独立压缩和校验。
前缀压缩在 SSTable 中有什么作用？
前缀压缩减少了存储空间，允许相邻的 key 共享前缀，从而提高读取效率。
Bloom Filter 是如何减少无效 I/O 的？
Bloom Filter 在内存中使用固定大小的位数组，快速判断某个 key 是否存在，从而避免不必要的磁盘读取。
SSTable 的文件格式包含哪些部分？
SSTable 文件格式包括数据块、元数据块、索引块和文件尾，确保高效的读取和存储。
TableBuilder 在 SSTable 中的作用是什么？
TableBuilder 负责将一系列有序 key-value 写入文件，管理数据块和索引块的写入，并生成 Bloom Filter。
SSTable 的读取过程是怎样的？
读取过程包括先加载文件尾，获取索引块和 Bloom Filter，然后根据索引定位数据块，最后在数据块中查找目标 key。
➡️
