BlockBasedTable是RocksDB中SST文件的默认格式，本文是源码学习BlockBasedTable的第二篇，主要围绕数据块（Data Block）层面，进行介绍。

一、SST文件格式回顾

在第一篇里我们已经介绍过BlockBasedTable SST文件的格式，这里再回顾下：

一个 SST 文件从头到尾依次包含以下部分：

1. [Data Blocks]: 一系列连续的数据块。这是文件的主体，存储了实际的键值对。
2. [Meta Blocks]: 一系列元数据块，包括：
   • Filter Block: 用于快速判断某个 Key 是否 可能 不在文件中的过滤器（如布隆过滤器）。
   • Properties Block: 存储文件的元信息，如比较器名称、前缀提取器名称、创建时间、总条目数等。
   • Range Deletion Block: 存储范围删除的墓碑标记。
   • Compression Dictionary Block: 用于ZSTD压缩的字典，可以显著提高压缩率。
3. [Metaindex Block]: 元数据索引块。它的 “key” 是元数据块的名称（例如 "filter.rocksdb.BuiltinBloomFilter2"），”value” 是一个 BlockHandle，指向该元数据块在文件中的位置。
4. [Index Block]: 数据块的索引。它的 “key” 是某个数据块的 separator (通常是 >= 该数据块的最大key，且 < 下一个数据块的最小key)，”value” 是一个 BlockHandle，指向该数据块的位置。
5. [Footer]: 文件尾部。它是一个固定长度的结构，包含了指向 Metaindex Block 和 Index Block 的 BlockHandle，以及用于校验文件类型的 Magic Number。

Footer 是整个文件的入口点。任何读取操作都始于解析 Footer，然后按图索骥，找到索引，最终定位到数据。

---

二、BlockBasedTable的读写

2.1 写路径：BlockBasedTableBuilder 的构建之旅

BlockBasedTableBuilder 的核心职责就是接收用户传入的、已排序的键值对，将它们打包成数据块，并生成上述的所有元数据块和索引，最后将它们有序地写入文件。

2.1.1 Add(): 键值对的添加与数据块切分

Add() 是构建过程的起点。每当一个键值对被添加时，Builder 会将其交给内部的 data_block（一个 BlockBuilder 实例）。同时，它会通过一个 FlushBlockPolicy 来判断当前的数据块是否已经“满”了。

// table/block_based/block_based_table_builder.cc
void BlockBasedTableBuilder::Add(const Slice& ikey, const Slice& value) {
  Rep* r = rep_;
  // ...
  // 1. FlushBlockPolicy 决定是否应该切分（Flush）当前数据块
  auto should_flush = r->flush_block_policy->Update(ikey, value);
  if (should_flush) {
    // 2. 将当前key作为下一个数据块的第一个key，用于生成上一个块的索引分隔符
    r->first_key_in_next_block = &ikey;
    Flush(); // 切分并写入块

    // 3. 为刚刚写入的块，在索引中添加条目
    if (ok() && r->state == Rep::State::kUnbuffered) {
        // 使用上一个块的最后一个key (r->last_ikey) 和下一个块的第一个key (ikey)
        // 来生成一个短的 separator，并添加到 index_builder
        r->index_builder->AddIndexEntry(r->last_ikey, &ikey,
                                        r->pending_handle,
                                        &r->index_separator_scratch);
    }
  }

  // 4. 将键值对添加到当前的数据块中
  r->data_block.AddWithLastKey(ikey, value, r->last_ikey);
  r->last_ikey.assign(ikey.data(), ikey.size());
  // ...
}

Add() 的逻辑非常清晰：它使用 FlushBlockPolicy (默认基于块大小) 来决策何时一个数据块写满了。如果写满，就调用 Flush() 来持久化这个块，并为这个刚写完的块在 index_builder 中添加一个索引条目。最后，将新的键值对添加到当前（可能是新的）数据块中。

2.1.2 Flush() 与 WriteBlock(): 数据块的持久化

当 Add() 决定切分一个块时，Flush() 方法被调用。它负责压缩（如果配置了）、打包并写入这个块。

// table/block_based/block_based_table_builder.cc
void BlockBasedTableBuilder::Flush() {
  Rep* r = rep_;
  if (r->data_block.empty()) {
    return;
  }
  // 1. 从 BlockBuilder 获取序列化后的、未压缩的块内容
  Slice uncompressed_block_data = r->data_block.Finish();
  // ...
  // 2. 单线程模式下，直接调用 WriteBlock
  WriteBlock(uncompressed_block_data, &r->pending_handle, BlockType::kData);
  r->data_block.Reset(); // 重置 data_block 以便接收新的键值对
}

void BlockBasedTableBuilder::WriteMaybeCompressedBlock(
    const Slice& block_contents, CompressionType comp_type, BlockHandle* handle,
    BlockType block_type, const Slice* uncompressed_block_data) {
  // 文件格式包含一系列块，每个块都有:
  //    block_data: uint8[n]
  //    compression_type: uint8
  //    checksum: uint32
  Rep* r = rep_;
  const uint64_t offset = r->get_offset();
  handle->set_offset(offset); // 记录块的起始偏移
  handle->set_size(block_contents.size()); // 记录块的大小

  // 1. 写入块内容
  r->file->Append(io_options, block_contents);

  // 2. 写入块的 trailer (1字节压缩类型 + 4字节CRC32C校验和)
  std::array<char, kBlockTrailerSize> trailer;
  trailer[0] = comp_type;
  uint32_t checksum = ComputeBuiltinChecksumWithLastByte(...);
  EncodeFixed32(trailer.data() + 1, checksum);
  r->file->Append(io_options, Slice(trailer.data(), trailer.size()));

  // 3. 更新文件总偏移
  r->set_offset(r->get_offset() + block_contents.size() + kBlockTrailerSize);
}

Flush() 的流程很简单，它调用 data_block.Finish() 来获取当前块的完整内容，然后调用 WriteBlock。WriteBlock 负责压缩，并最终调用 WriteMaybeCompressedBlock。后者在写入块数据前，会先将当前的文件偏移量和块大小记录在 BlockHandle 中，这个 handle 就是未来索引块中指向这个数据块的“指针”。然后它写入块数据，并在块末尾追加5字节的 trailer（包含压缩类型和CRC校验和）。

2.1.3 Finish(): 元数据写入与文件封存

当所有键值对都添加完毕后，调用 Finish() 来完成整个SST文件的构建。

// table/block_based/block_based_table_builder.cc
Status BlockBasedTableBuilder::Finish() {
  Rep* r = rep_;
  // 1. Flush 最后一个未满的数据块
  Flush();

  BlockHandle filter_block_handle, meta_index_block_handle, index_block_handle;
  MetaIndexBuilder meta_index_builder;

  // 2. 写入各种元数据块 (Filter, Properties, etc.)
  if (ok()) { WriteFilterBlock(&meta_index_builder); }
  if (ok()) { WritePropertiesBlock(&meta_index_builder); }
  
  // 3. 写入索引块
  if (ok()) { WriteIndexBlock(&meta_index_builder, &index_block_handle); }

  // 4. 写入元数据索引块
  if (ok()) {
    WriteBlock(meta_index_builder.Finish(), &meta_index_block_handle,
               BlockType::kMetaIndex);
  }

  // 5. 写入文件尾部 Footer
  if (ok()) { WriteFooter(meta_index_block_handle, index_block_handle); }
  
  return r->GetStatus();
}

Finish() 的过程是收尾工作。它首先确保最后一个数据块被 Flush。然后，依次写入过滤器块、属性块等元数据块，每写完一个，就在 meta_index_builder 中添加一条记录。接着，它将 index_builder 中积累的所有数据块索引信息序列化，写入为主索引块。然后，写入 meta_index_builder 自身形成的元数据索引块。最后，也是最关键的一步，它将主索引块和元数据索引块的 BlockHandle 连同 magic number 一起写入文件的最末端，形成 Footer。

2.2 读路径：BlockBasedTableReader 的解析过程

BlockBasedTableReader 的工作流程与 Builder 的 Finish() 过程正好相反。它从 Footer 开始，反向解析出文件的结构。

2.2.1 Open(): 从 Footer 开始的探索

Open() 是一个静态方法，是创建 BlockBasedTableReader 实例的唯一入口。

// table/block_based/block_based_table_reader.cc
Status BlockBasedTable::Open(
    std::unique_ptr<TableReader>* table_reader, ...) {
  
  // 1. 从文件末尾读取并解析 Footer
  Footer footer;
  s = ReadFooterFromFile(..., &footer, ...);
  if (!s.ok()) { return s; }

  // 2. 创建 Rep 对象，存储 Table 的所有状态
  Rep* rep = new BlockBasedTable::Rep(...);
  rep->footer = footer;

  // 3. 读取 Metaindex Block
  std::unique_ptr<BlockBasedTable> new_table(new BlockBasedTable(rep, ...));
  std::unique_ptr<InternalIterator> metaindex_iter;
  s = new_table->ReadMetaIndexBlock(..., &metaindex_iter);
  if (!s.ok()) { return s; }

  // 4. 使用 Metaindex 查找并读取 Properties Block
  s = new_table->ReadPropertiesBlock(..., metaindex_iter.get(), ...);
  if (!s.ok()) { return s; }

  // 5. 根据 Properties 和 Footer 信息，预取或加载 Index 和 Filter 块
  s = new_table->PrefetchIndexAndFilterBlocks(...);

  if (s.ok()) { *table_reader = std::move(new_table); }
  return s;
}

Open() 的初始化过程严格遵循 SST 文件的布局：它首先从文件末尾读取 Footer，从中获得 metaindex_handle 和 index_handle。然后使用 metaindex_handle 读取元数据索引块，并通过它找到并读取属性块 (Properties Block)。最后，它使用 index_handle 和属性信息，创建对应类型的 IndexReader 和 FilterBlockReader。当 Open() 成功返回后，一个 BlockBasedTableReader 实例就准备就绪了，可以响应数据查找请求。

---

三、核心导航系统：索引 (Index) 的设计与实现

索引是快速定位数据块的关键。IndexReader 是 BlockBasedTableReader 内部用于解析和查询索引的抽象接口。RocksDB 提供了多种索引实现，在内存占用、点查找性能和范围扫描性能之间做出了不同的权衡。

3.1 IndexReader 接口

IndexReader 接口最核心的方法是 NewIterator()，它返回一个用于遍历索引条目的迭代器。这个迭代器的 value() 就是数据块的 BlockHandle。

3.2 二分查找索引 (kBinarySearch)

这是最基础、也是默认的索引类型。

• 结构: Index Block 本身就是一个标准的 Block，其中 Key 是数据块的 separator，Value 是 BlockHandle，所有条目有序存储。
• 查找过程: 在 Index Block 内部进行一次二分查找，快速定位到第一个 separator >= key 的条目，从而找到目标数据块的句柄。
• 优缺点: 结构简单，范围扫描友好，内存占用较低。但每次点查找都需要 O(log N) 的二分查找。

3.3 哈希索引 (kHashSearch)

为加速点查找而设计，需要用户提供前缀提取器 (prefix_extractor)。

• 结构: 在标准 Index Block 之外，额外存储一个元数据块 hash.index，包含一个从“键的前缀”到“重启点索引”的哈希表。
• 深度揭秘：“重启点 (Restart Point)” 与 “重启点索引”:
  • 重启点机制: 为解决前缀压缩带来的无法二分查找的问题，Block 被内部分为若干“重启区间”。每隔 N 个 key 就存储一个完整的“重启点”。块末尾有一个重启点偏移量数组，其下标就是“重启点索引”。
  • 哈希索引如何利用: hash.index 哈希表存储的 Value 正是这个“重启点索引”。当查找一个 key 时，通过其前缀在哈希表中直接查到它所在的重启区间，将一次对整个 Index Block 的搜索，降维成一次哈希计算和一次对一个极小数据范围的廉价扫描。
• 优缺点: 极大地加速了点查找性能，接近 O(1)。但依赖 prefix_extractor，增加了内存开销，对范围扫描无益。

3.4 两级分区索引 (kTwoLevelIndexSearch)

当 SST 文件非常大时，单一的索引块会变得巨大，消耗大量内存并增加打开文件的延迟。两级分区索引正是为解决此问题而设计的。

3.4.1 写路径：PartitionedIndexBuilder 的构建逻辑

当 index_type 为 kTwoLevelIndexSearch 时，BlockBasedTableBuilder 会采用 PartitionedIndexBuilder。它将一个巨大的索引切分成多个小的“二级索引分区”，并为这些分区建立一个“一级顶层索引”。

• 核心成员变量 (简化后):

  // table/block_based/partitioned_index_builder.h & .cc
  class PartitionedIndexBuilder : public IndexBuilder {
   private:
    BlockBuilder index_block_builder_; // 用于构建当前“二级索引分区”
    BlockBuilder top_level_index_builder_; // 用于构建“一级顶层索引”
    std::string last_key_in_partition_; // 当前分区中最后一个 key
    const BlockBasedTableOptions& table_options_;
  };

• AddIndexEntry() 的核心逻辑:
  每当一个数据块写完，AddIndexEntry() 会被调用，其逻辑如下：

  // table/block_based/partitioned_index_builder.cc (伪代码)
  void PartitionedIndexBuilder::AddIndexEntry(
      const Slice& last_key_in_block, ...,
      const BlockHandle& block_handle) {
  
    // 1. 将数据块的索引条目添加到当前的“二级索引分区”中
    index_block_builder_.Add(last_key_in_block, block_handle.Encode());
    last_key_in_partition_.assign(last_key_in_block.data(), ...);
  
    // 2. 检查当前的“二级索引分区”是否已经太大
    if (index_block_builder_.CurrentSizeEstimate() >= table_options_.metadata_block_size) {
      
      // 3. 如果太大，就“切分”出一个分区
      // a. 将当前二级索引分区的数据写入文件，获取其 BlockHandle (partition_handle)
      // b. 在“一级顶层索引”中，添加一个指向该分区的条目：
      //    Key: 刚完成分区的最后一个 key, Value: partition_handle
      top_level_index_builder_.Add(last_key_in_partition_, partition_handle.Encode());
  
      // c. 重置二级索引分区构造器，准备构建下一个分区
      index_block_builder_.Reset();
    }
  }

  这个过程像一条装配线：不断将索引条目装入“箱子”(index_block_builder_)，箱子满了（达到 metadata_block_size）就封箱并登记到总货运单（top_level_index_builder_）上，然后换新箱子继续。

3.4.2 读路径：PartitionedIndexReader 与 TwoLevelIterator

读取时，BlockBasedTableReader 会创建 PartitionedIndexReader。

• NewIterator() 的魔法:
  PartitionedIndexReader 的 NewIterator() 方法会返回一个精心构造的 TwoLevelIterator**。TwoLevelIterator 是 RocksDB 中一个通用的两级迭代辅助类，它接收一个一级迭代器和一个回调函数**。

  // table/block_based/partitioned_index_reader.cc
  InternalIteratorBase<IndexValue>* PartitionedIndexReader::NewIterator(...) {
    // 1. 创建一级迭代器：在内存中的“顶层索引块”上创建迭代器。
    auto top_level_iter = index_block_->NewIndexIterator(...);
  
    // 2. 创建回调函数状态对象：PartitionedIndexIteratorState
    auto two_level_iter_state =
        new BlockBasedTable::PartitionedIndexIteratorState(table_, &block_map_);
  
    // 3. 创建并返回 TwoLevelIterator
    return NewTwoLevelIterator(two_level_iter_state, top_level_iter);
  }

• 回调函数 NewSecondaryIterator 的实现:
  当一级迭代器（遍历顶层索引）定位到一个条目时，TwoLevelIterator 会调用此回调，并传入该条目的 Value（即二级索引分区的 BlockHandle）。

  // table/block_based/block_based_table_reader.cc
  InternalIteratorBase<IndexValue>*
  BlockBasedTable::PartitionedIndexIteratorState::NewSecondaryIterator(
      const BlockHandle& handle) { // handle 是二级索引分区的句柄
    
    // 1. 通过 table_ 指针和 handle，读取或从缓存获取二级索引分区（可能发生I/O）
    CachableEntry<Block> block_entry;
    table_->RetrieveBlock(..., handle, ..., &block_entry, ...);
    
    // 2. 为读取到的二级索引分区，创建一个标准的块迭代器并返回
    return block_entry.GetValue()->NewIndexIterator(...);
  }

3.4.3 读操作流程串讲

一个 Seek("some_key") 操作的内部流程如下：

1. TwoLevelIterator 在一级迭代器（顶层索引）上 Seek，找到包含 "some_key" 的二级分区的 BlockHandle。
2. TwoLevelIterator 调用回调函数 NewSecondaryIterator，传入该 BlockHandle。
3. 回调函数内部读取（可能从磁盘）并解析这个二级分区，然后返回一个二级迭代器。
4. TwoLevelIterator 在这个新的二级迭代器上 Seek("some_key")，最终找到指向数据块的 BlockHandle。
5. 上层的 BlockBasedTableIterator 获得这个最终的 BlockHandle，进而读取数据块。

• 优缺点: 显著降低超大 SST 文件的内存占用，极大提高缓存利用率。但点查找可能需要两次 I/O（虽然顶层索引通常在缓存中）。

3.5 三种索引的对比总结

索引类型	点查找速度	范围扫描速度	内存占用	适用场景
kBinarySearch	良好 (O(log N))	优秀	中等	默认选项，通用，性能均衡。
kHashSearch	优秀 (近 O(1))	一般	较高	点查找密集型负载，需配置前缀提取器。
kTwoLevelIndexSearch	很好	优秀	极低 (对大文件)	文件体积非常大的场景，用于优化内存和缓存。

---

四、 性能加速器之一：过滤器 (Filter)

过滤器是位于索引之前的“第一道防线”，专门用于“剪枝”，过滤掉大量对不存在的 key 的无效查询，避免昂贵的磁盘 I/O。

4.1 FilterPolicy 策略接口与主流实现

FilterPolicy 是用户在 Options 中配置的策略工厂。最核心的实现是布隆过滤器 (Bloom Filter)**，新兴的选择有 **Ribbon 过滤器。

4.2 布隆过滤器 (Bloom Filter) 深度解析

4.2.1 原理：位数组与哈希函数

布隆过滤器的核心思想是：用一个很长的位数组 (bit array) 和几个不同的**哈希函数 (hash function)**，来以极高的空间效率表示一个庞大的集合。

4.2.2 Add 与 MayMatch 操作

我们通过它的两个核心操作来理解其原理：

1. 添加元素 (Add)

当 BlockBasedTableBuilder 构建SST文件，并将一个 key 添加到布隆过滤器时，会发生以下事情：

1. 取一个长度为 m 的位数组，初始时所有位都为 0。
2. 准备 k 个独立的哈希函数（例如 h1, h2, ..., hk）。
3. 对于要添加的 key，分别计算 k 次哈希，得到 k 个哈希值。
4. 将这 k 个哈希值分别对位数组的长度 m 取模，得到 k 个在数组中的位置（下标）。
5. 将位数组在这 k 个位置上的 bit 全部置为 1。

图解 Add("hello") 操作:
假设我们有3个哈希函数 (k=3)，一个位数组。

• h1("hello") % m -> 得到下标 5
• h2("hello") % m -> 得到下标 12
• h3("hello") % m -> 得到下标 21

操作就是： bit_array[5] = 1, bit_array[12] = 1, bit_array[21] = 1。

2. 查询元素 (MayMatch)

当 BlockBasedTableReader 需要判断一个 key 是否“可能存在”时：

1. 对要查询的 key，使用完全相同的 k 个哈希函数，计算出 k 个对应的数组下标。
2. 检查位数组在这些下标上的值。
3. 判断逻辑:
   • 如果这 k 个位置中，只要有任何一个 bit 是 0，那么过滤器就断定这个 key 绝对不存在。因为如果它存在，当初 Add 操作时一定会把所有这些位都置为 1。这是布隆过滤器没有假阴性的根本原因。
   • 如果这 k 个位置的 bit 全部都是 1**，那么过滤器就认为这个 key **可能存在。

为什么是“可能”存在？—— 假阳性的来源
因为这些位上的 1 可能是由其他 key 的 Add 操作设置的。例如，Add("world") 可能把第 5 位置为 1，Add("rocksdb") 可能把第 12 和 21 位置为 1。这样一来，即使我们从未添加过 "hello"，在查询它时也会发现第 5, 12, 21 位全为 1，从而产生误判。这个误判概率就是**假阳性率 (False Positive Rate)**。

4.2.3 假阳性率与 bits_per_key

假阳性是布隆过滤器的固有特性。bits_per_key 参数用于权衡空间占用和假阳性率，值越高，假阳性率越低，但内存占用越大。推荐值为 10，假阳性率约 1%。

4.3 新兴选择：Ribbon 过滤器

Ribbon 过滤器基于更复杂的数学变换，目标是在达到相同假阳性率的前提下，比布隆过滤器使用更少的空间（可节省25-50%），但代价是更高的 CPU 开销。适用于对内存占用极度敏感的场景。

4.4 过滤器模式：完整 (Full) vs. 分区 (Partitioned)

与索引类似，为了解决单个巨型过滤器带来的内存压力问题，过滤器也支持分区。该功能由 BlockBasedTableOptions::partition_filters 控制。

BlockBasedTableBuilder 在创建时，会根据该选项决定使用哪种 FilterBlockBuilder。

// table/block_based/block_based_table_builder.cc
FilterBlockBuilder* CreateFilterBlockBuilder(...) {
  // ...
  if (table_opt.partition_filters) {
    // 创建分区过滤器 Builder
    return new PartitionedFilterBlockBuilder(...);
  } else {
    // 创建完整过滤器 Builder
    return new FullFilterBlockBuilder(...);
  }
}

4.4.1 完整过滤器 (Full Filter)

这是最直接的实现方式，由 FullFilterBlockBuilder 和 FullFilterBlockReader 实现。

• 结构: 对整个 SST 文件中的所有 key，只构建一个单一、巨大的过滤器。这个过滤器作为一个整体，存储在 SST 文件的一个元数据块中。
• 查找过程: BlockBasedTableReader::Open() 时，会找到并读取整个 Filter Block 到内存（或块缓存）中。当 Get(key) 请求到来时，FullFilterBlockReader 会在内存中的完整位图上进行一次哈希计算和检查。
• 优缺点: 结构简单，每次查询只需要在内存中进行一次判断，速度很快。但当 SST 文件非常大时，这个单一的过滤器也会变得非常大，消耗大量内存和块缓存。

4.4.2 分区过滤器 (Partitioned Filter)

这是更现代、更节省内存的实现，由 PartitionedFilterBlockBuilder 和 PartitionedFilterBlockReader 实现。

• 结构:
  1. 过滤器分区: 不再为整个文件创建一个大过滤器，而是将 key 集合进行切分，为每个数据块（或每组数据块）创建一个独立的、小型的过滤器。这些小过滤器一个接一个地拼接在一起，形成过滤器的数据主体。
  2. 过滤器的索引: 同时，会创建一个用于定位这些小型过滤器的索引。这个索引的 Key 是数据块的最后一个 key，Value 则是对应的小型过滤器在拼接数据中的偏移量。这个索引本身被存储在一个独立的元数据块中。实际上，分区过滤器的索引和两级分区索引可以共用同一个 PartitionedIndexBuilder，这使得它们的结构和行为高度一致。
• 查找过程: PartitionedFilterBlockReader 内部持有自己的 IndexReader，用于查找过滤器分区。

  // table/block_based/partitioned_filter_block.h
  class PartitionedFilterBlockReader : public FilterBlockReaderCommon {
   public:
    static std::unique_ptr<FilterBlockReader> Create(...);
    // ...
   private:
    std::unique_ptr<IndexReader> index_reader_; // 内部持有自己的索引读取器
    // ...
  };

  当一个 Get(key) 请求到来时，PartitionedFilterBlockReader 首先查询过滤器的索引，找到目标小型过滤器的位置，然后读取这个小型过滤器（如果不在缓存中），最后在加载到内存的小型过滤器上进行 KeyMayMatch() 判断。
• 优缺点: 极大地降低了内存占用。对于一次查询，不再需要加载整个文件的过滤器，而只需要加载一个很小的过滤器分区。但查询过程更复杂，可能需要一次额外的 I/O 来读取过滤器分区。

---

五、 性能加速器之二：块缓存 (Block Cache)

Block Cache 是 RocksDB 的核心性能引擎，通过在内存中缓存热点数据块，有效地将慢速的磁盘操作转换为了快速的内存操作。

5.1 默认实现：分片的 LRU 缓存 (Sharded LRUCache)

RocksDB 的默认 Block Cache 实现是基于 LRU (Least Recently Used, 最近最少使用) 算法。

• LRU 原理：哈希表 + 双向链表: 内部使用哈希表实现 O(1) 的快速查找，同时使用双向链表维护块的访问顺序。链表头部是最新访问的，尾部是最久未访问的。
• 命中、插入与淘汰逻辑:
  • 命中: 在哈希表中找到，将对应节点移到链表头部。
  • 插入: 当缓存未命中时，从磁盘读取新块，创建新节点插入到链表头部。
  • 淘汰: 如果缓存已满，则从链表尾部移除最久未使用的节点。
• 为并发而生：分片机制: 为避免多线程下的锁竞争，LRUCache 内部被分为多个小的、独立的 LRU 实例（分片），每个分片有自己的锁。一个 key 根据其哈希值被路由到特定分片，极大地提高了并发性能。

5.2 高级特性

• 缓存优先级: 允许为索引、过滤器等高价值块设置高优先级，使其在缓存中停留更长时间。
• 二级压缩块缓存: 当块从主缓存（存储解压后数据）淘汰时，可以将其压缩后存入二级缓存。这是一种用 CPU 解压开销换取“第二次缓存机会”的有效策略，能进一步降低磁盘 I/O。

---

6. 数据的流动：迭代器与压缩

6.1 遍历全表：BlockBasedTableIterator

• 两级迭代器模型: BlockBasedTableIterator 是一个典型的两级迭代器。它内部持有一个“一级迭代器”（遍历索引）和一个“二级迭代器”（遍历数据块）。当二级迭代器遍历完一个数据块后，它会自动驱动一级迭代器前进，加载并切换到下一个数据块，从而对上层呈现出无缝、连续的遍历视图。
• 一个 Seek 操作的生命周期: 一个 Seek 操作是所有组件协同工作的完美体现：它可能先经过过滤器的快速剪枝，然后通过两级索引迭代器定位到数据块句柄，接着在块缓存中查找数据块，如果未命中则从磁盘读取并解压，最后在数据块内部完成最终的查找。

6.2 空间与性能的艺术：块压缩 (Block Compression)

压缩是平衡存储成本和查询性能的关键手段。

6.2.1 主流压缩算法对比

压缩算法	压缩速度	解压速度	压缩率	CPU占用	核心特点
LZ4	极高	极高	低	极低	极限速度
Snappy	极高	极高	中-低	极低	速度快，非常均衡的旧默认选项
ZSTD	高	极高	高	低-中	全能，强烈推荐，支持字典压缩
ZLIB	低	中	中-高	中	压缩率较好，经典但偏慢
BZip2	极低	极低	极高	极高	极限压缩率，用于归档

6.2.2 ZSTD 的王牌：字典压缩

ZSTD 的字典压缩特性尤其强大。RocksDB 可以在构建 SST 文件时，自动从数据样本中训练出一个字典，并用它来压缩该文件内的所有块。对于包含大量相似结构的小记录，这能带来巨大的额外空间节省。对于新应用，ZSTD 是首选推荐。