【LSM-Tree】SSTable + Bloom Filter：磁盘上的有序表
内容提要
本文介绍了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通过将数据分块存储和使用前缀压缩技术，显著提高了读取效率。每个数据块独立压缩，减少了内存占用，同时通过restart point解决了随机访问的性能问题。这种设计使得在处理大规模数据时，SSTable能够有效降低I/O操作的成本。
布隆过滤器的应用与优势
布隆过滤器在SSTable中用于快速判断某个key是否存在，从而避免不必要的磁盘I/O。其零假阴性特性确保了查询的准确性，而假阳性率的控制则通过合理的哈希函数数量和位数组大小来实现。这种设计在高并发场景下尤为重要，能够显著提升系统的响应速度。
SSTable的构建与读取流程
SSTable的构建过程包括数据块的写入、索引块的生成以及布隆过滤器的创建。读取时，首先通过布隆过滤器排除不存在的key，再通过索引块定位到相应的数据块。这一流程的高效性使得SSTable在大数据存储中成为一种理想的选择，尤其是在需要频繁读写的场景中。
延伸问答
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。
