B+树与LSM-tree：存储引擎的读优化与写优化之道

一、存储引擎的核心权衡

1.1 读写放大的困境

存储引擎设计面临一个根本性矛盾：读性能与写性能不可兼得。

读放大（Read Amplification）：

为读取一个逻辑数据项，实际需要读取的物理数据量。

写放大（Write Amplification）：

为写入一个逻辑数据项，实际需要写入的物理数据量。

示例对比：

操作	简单日志	B+树	LSM-tree
随机读	O(N)	O(log N)	O(log N) ~ O(N)
随机写	O(1)	O(log N)	O(1)（摊还）
写放大	1x	~10-100x	~10-30x
读放大	1x	~1-3x	~1-10x

1.2 硬件特性的影响

存储介质的演进深刻影响了存储引擎设计：

HDD 时代（机械硬盘）：

随机 IO 性能极差（寻道时间 10ms）
顺序 IO 性能良好（100MB/s）
设计目标：将随机 IO 转化为顺序 IO

SSD 时代（固态硬盘）：

随机读性能大幅提升（100μs）
写入有擦除块（Erase Block）限制
设计目标：减少写入次数，避免原地更新

NVMe 时代：

并行 IO 能力极强
延迟极低（10μs）
设计目标：充分利用并行性

二、B+树：读优化的经典

2.1 从二叉树到B树

二叉搜索树的问题：

树高 = O(log N)，但底数为 2
每个节点一次磁盘 IO（假设节点不在内存）
1000万数据 → 约 24 次磁盘 IO

B树的核心洞察：

将多个键打包到一个节点，减少树高和磁盘 IO。

B树定义：

每个节点包含 $[m/2, m]$ 个键（ $m$ 为阶数）
所有叶子节点在同一层
树高 = O(log_m N)

对比：

二叉树：1000万数据，树高 24
B树（m=200）：1000万数据，树高 3-4

2.2 B+树的优化

B+树是 B树的变种，针对磁盘存储优化：

            B+树结构：

内部节点（非叶子）：
┌─────────────────────────────────────────┐
│  Key1 │  Key2 │  Key3 │ ... │  KeyN    │
├───────┴───────┴───────┴─────┴───────────┤
│ Ptr0  │ Ptr1  │ Ptr2  │ ... │ PtrN     │
└─────────────────────────────────────────┘

叶子节点：
┌─────────────────────────────────────────┐
│  Key1 │  Key2 │  Key3 │ ... │  KeyN    │
├───────┴───────┴───────┴─────┴───────────┤
│ Val1  │ Val2  │ Val3  │ ... │ ValN     │
├─────────────────────────────────────────┤
│              Next Leaf Ptr              │  ← 链表连接
└─────────────────────────────────────────┘
          

B+树 vs B树：

特性	B树	B+树
数据存储	内部节点和叶子	仅叶子节点
叶子节点连接	无	双向链表
范围查询	中序遍历	顺序扫描
空间利用率	较低	较高

2.3 B+树操作详解

查找：

python

            class BPlusTree:
    """
    B+树实现（简化版）
    """
    
    def __init__(self, order: int = 4):
        self.order = order  # 阶数
        self.root = LeafNode(order)
    
    def search(self, key) -> any:
        """查找键对应的值"""
        node = self.root
        
        # 遍历内部节点
        while isinstance(node, InternalNode):
            node = node.get_child(key)
        
        # 在叶子节点中查找
        return node.get(key)
    
    def range_search(self, start_key, end_key) -> list:
        """范围查询"""
        results = []
        
        # 找到起始叶子节点
        node = self._find_leaf(start_key)
        
        # 顺序扫描
        while node:
            for key, value in node.items:
                if key > end_key:
                    return results
                if key >= start_key:
                    results.append((key, value))
            
            node = node.next
        
        return results
          

插入：

python

            def insert(self, key, value):
        """插入键值对"""
        result = self._insert_recursive(self.root, key, value)
        
        if result:
            # 根节点分裂
            new_root = InternalNode(self.order)
            new_root.keys = [result['key']]
            new_root.children = [self.root, result['node']]
            self.root = new_root
    
    def _insert_recursive(self, node, key, value):
        """递归插入，返回分裂结果（如果有）"""
        if isinstance(node, LeafNode):
            # 叶子节点插入
            node.insert(key, value)
            
            if node.is_full():
                return self._split_leaf(node)
            return None
        
        else:
            # 内部节点：找到合适的子节点
            child = node.get_child(key)
            result = self._insert_recursive(child, key, value)
            
            if result:
                # 子节点分裂，插入新键
                node.insert_key(result['key'], result['node'])
                
                if node.is_full():
                    return self._split_internal(node)
            
            return None
    
    def _split_leaf(self, node):
        """分裂叶子节点"""
        mid = len(node.keys) // 2
        
        new_node = LeafNode(self.order)
        new_node.keys = node.keys[mid:]
        new_node.values = node.values[mid:]
        new_node.next = node.next
        
        node.keys = node.keys[:mid]
        node.values = node.values[:mid]
        node.next = new_node
        
        return {'key': new_node.keys[0], 'node': new_node}
          

删除：

python

            def delete(self, key):
        """删除键"""
        self._delete_recursive(self.root, key)
        
        # 如果根节点只剩一个子节点，降低树高
        if isinstance(self.root, InternalNode) and len(self.root.keys) == 0:
            self.root = self.root.children[0]
    
    def _delete_recursive(self, node, key):
        """递归删除"""
        if isinstance(node, LeafNode):
            node.delete(key)
            return len(node.keys) < self.order // 2  # 是否下溢
        
        else:
            child = node.get_child(key)
            underflow = self._delete_recursive(child, key)
            
            if underflow:
                # 处理下溢：借用或合并
                return self._handle_underflow(node, child)
            
            return False
          

2.4 节点布局与缓存优化

磁盘页对齐：

            典型 B+树节点大小 = 4KB（一个磁盘页）

节点结构：
┌─────────────────────────────────────────┐
│  Header (16 bytes)                      │
│  - node_type: 1 byte                    │
│  - key_count: 2 bytes                   │
│  - level: 1 byte                        │
│  - page_id: 4 bytes                     │
│  - checksum: 4 bytes                    │
├─────────────────────────────────────────┤
│  Key Offsets (2 bytes × N)              │
├─────────────────────────────────────────┤
│  Keys and Values                        │
│  (紧凑排列，从后向前增长)                  │
├─────────────────────────────────────────┤
│  Padding to 4KB                         │
└─────────────────────────────────────────┘
          

前缀压缩：

            键：["apple", "application", "apply", "apt"]

前缀压缩后：
- "apple"
- "5ication"  (共享 "appl" 前缀)
- "5y"        (共享 "appl" 前缀)
- "2t"        (共享 "ap" 前缀)
          

2.5 并发控制

B-link树：

python

            class BLinkTree:
    """
    B-link树：支持高并发读写
    特点：允许在分裂期间继续搜索
    """
    
    def __init__(self, order: int = 4):
        self.order = order
        self.root = LeafNode(order)
        self.lock = threading.RLock()
    
    def search_concurrent(self, key):
        """无锁搜索"""
        node = self.root
        
        while isinstance(node, InternalNode):
            next_node = node.get_child(key)
            
            # 检查是否需要向右兄弟移动（分裂期间）
            if key >= node.high_key and node.right_sibling:
                node = node.right_sibling
            else:
                node = next_node
        
        return node.get(key)
    
    def insert_concurrent(self, key, value):
        """乐观并发插入"""
        with self.lock:
            # 获取从根到叶子的路径
            path = self._get_path(key)
            
            # 锁定叶子节点
            leaf = path[-1]
            leaf.lock()
            
            try:
                # 检查路径是否仍然有效
                if not self._validate_path(path, key):
                    leaf.unlock()
                    return self.insert_concurrent(key, value)  # 重试
                
                # 执行插入
                self._insert_with_path(path, key, value)
            finally:
                leaf.unlock()
          

三、LSM-tree：写优化的革新

3.1 日志结构合并树

1996年，O'Neil 等人提出 LSM-tree（Log-Structured Merge-Tree），彻底改变了写密集型 workload 的存储设计。

核心思想：

将所有写操作转化为顺序追加，延迟合并和整理。

            LSM-tree 架构：

写入路径：
┌─────────┐    ┌─────────────┐    ┌─────────────┐
│  Client │───>│  MemTable   │───>│  WAL (日志)  │
└─────────┘    │  (内存)      │    └─────────────┘
               └──────┬──────┘
                      │ 达到阈值
                      ▼
               ┌─────────────┐
               │  Immutable  │
               │  MemTable   │
               └──────┬──────┘
                      │ Flush
                      ▼
┌─────────────────────────────────────────────────┐
│              Level 0 (SSTable)                   │
│  ┌─────────┐ ┌─────────┐ ┌─────────┐           │
│  │SSTable 1│ │SSTable 2│ │SSTable 3│ ...        │
│  └─────────┘ └─────────┘ └─────────┘           │
└─────────────────────────────────────────────────┘
                      │ Compaction
                      ▼
┌─────────────────────────────────────────────────┐
│              Level 1 (SSTable)                   │
│  ┌─────────────────────────────────────────┐    │
│  │         更大的 SSTable                  │    │
│  └─────────────────────────────────────────┘    │
└─────────────────────────────────────────────────┘
                      │
                      ▼
              Level 2, 3, ...
          

3.2 组件详解

MemTable：

python

            class MemTable:
    """
    内存中的有序数据结构
    通常使用跳表（Skip List）或红黑树
    """
    
    def __init__(self, size_limit: int = 4 * 1024 * 1024):
        self.size_limit = size_limit
        self.data = SkipList()  # 或 SortedDict
        self.size = 0
    
    def put(self, key: bytes, value: bytes):
        """插入键值对"""
        self.data[key] = value
        self.size += len(key) + len(value)
    
    def get(self, key: bytes) -> Optional[bytes]:
        """查找键"""
        return self.data.get(key)
    
    def is_full(self) -> bool:
        """检查是否达到大小限制"""
        return self.size >= self.size_limit
    
    def to_sstable(self, file_path: str):
        """转换为 SSTable 文件"""
        writer = SSTableWriter(file_path)
        
        for key, value in self.data.items():
            writer.add(key, value)
        
        writer.finish()
          

SSTable（Sorted String Table）：

python

            class SSTable:
    """
    不可变的有序键值对文件
    """
    
    def __init__(self, file_path: str):
        self.file_path = file_path
        self.index = {}  # 稀疏索引：key -> offset
        self.bloom_filter = BloomFilter()
        
        self._load_index()
    
    def _load_index(self):
        """加载稀疏索引"""
        with open(self.file_path, 'rb') as f:
            # 每 16KB 创建一个索引点
            offset = 0
            while True:
                block = self._read_block(f, offset)
                if not block:
                    break
                
                first_key = block[0][0]
                self.index[first_key] = offset
                offset += len(block)
    
    def get(self, key: bytes) -> Optional[bytes]:
        """查找键"""
        # 1. 布隆过滤器检查
        if not self.bloom_filter.may_contain(key):
            return None
        
        # 2. 二分查找定位数据块
        block_offset = self._find_block(key)
        
        # 3. 在数据块内二分查找
        block = self._read_block_at(block_offset)
        return self._binary_search(block, key)
          

SSTable 文件格式：

            SSTable 文件结构：

┌─────────────────────────────────────────┐
│  Data Blocks                            │
│  ┌─────────┐ ┌─────────┐ ┌─────────┐   │
│  │ Block 1 │ │ Block 2 │ │ Block 3 │   │
│  │(16KB)   │ │(16KB)   │ │(16KB)   │   │
│  └─────────┘ └─────────┘ └─────────┘   │
├─────────────────────────────────────────┤
│  Index Block                            │
│  (每个数据块的第一个 key 和 offset)        │
├─────────────────────────────────────────┤
│  Bloom Filter Block                     │
├─────────────────────────────────────────┤
│  Meta Index Block                       │
├─────────────────────────────────────────┤
│  Footer (固定大小)                       │
│  - Index Block offset                   │
│  - Bloom Filter offset                  │
│  - Magic Number                         │
└─────────────────────────────────────────┘
          

3.3 合并策略（Compaction）

Size-Tiered Compaction：

python

            class SizeTieredCompaction:
    """
    大小分层合并策略（Cassandra 默认）
    
    特点：
    - 每层大小是上一层的倍数
    - 同层 SSTable 大小相近
    - 合并时同层全部合并到下一层
    """
    
    def __init__(self, min_threshold: int = 4, size_ratio: int = 4):
        self.min_threshold = min_threshold  # 触发合并的最小文件数
        self.size_ratio = size_ratio        # 层间大小比例
    
    def should_compact(self, level: int, sstables: list) -> bool:
        """检查是否需要合并"""
        if level == 0:
            # L0 特殊处理：文件数过多就合并
            return len(sstables) >= self.min_threshold
        else:
            # 其他层：总大小超过阈值
            total_size = sum(s.size for s in sstables)
            threshold = (4 * 1024 * 1024) * (self.size_ratio ** level)
            return total_size > threshold
    
    def compact(self, level: int, sstables: list) -> list:
        """执行合并"""
        # 合并所有 SSTable
        merged = self._merge_sstables(sstables)
        
        # 如果超过目标层大小，分裂成多个 SSTable
        target_size = 4 * 1024 * 1024  # 4MB
        return self._split_into_chunks(merged, target_size)
          

Leveled Compaction：

python

            class LeveledCompaction:
    """
    分层合并策略（LevelDB/RocksDB 默认）
    
    特点：
    - 每层大小固定上限
    - 每层内部 SSTable 不重叠
    - 合并时只涉及相邻层
    """
    
    def __init__(self):
        self.level_max_sizes = [
            10 * 1024 * 1024,      # L1: 10MB
            100 * 1024 * 1024,     # L2: 100MB
            1000 * 1024 * 1024,    # L3: 1GB
            10 * 1000 * 1024 * 1024  # L4: 10GB
        ]
    
    def compact(self, level: int, sstables: list) -> list:
        """执行分层合并"""
        if level == 0:
            # L0 -> L1：特殊处理，可能涉及 L1 的多个文件
            return self._compact_l0_to_l1(sstables)
        else:
            # Ln -> Ln+1：选择重叠的 Ln+1 文件合并
            return self._compact_level_to_next(level, sstables)
    
    def _compact_l0_to_l1(self, l0_sstables: list) -> list:
        """L0 合并到 L1"""
        # 找出 L0 文件覆盖的 key 范围
        min_key = min(s.first_key for s in l0_sstables)
        max_key = max(s.last_key for s in l0_sstables)
        
        # 找出 L1 中重叠的文件
        l1_overlapping = self._find_overlapping(1, min_key, max_key)
        
        # 合并所有文件
        to_merge = l0_sstables + l1_overlapping
        merged = self._merge_sstables(to_merge)
        
        # 确保 L1 文件不重叠
        return self._split_non_overlapping(merged)
          

3.4 读取路径优化

布隆过滤器：

python

            class BloomFilter:
    """
    布隆过滤器：快速判断键是否可能存在
    """
    
    def __init__(self, capacity: int, error_rate: float = 0.01):
        self.capacity = capacity
        self.error_rate = error_rate
        self.num_hashes = self._optimal_num_hashes()
        self.bit_array = BitArray(self._optimal_size())
    
    def add(self, key: bytes):
        """添加键"""
        for i in range(self.num_hashes):
            index = self._hash(key, i) % len(self.bit_array)
            self.bit_array.set(index)
    
    def may_contain(self, key: bytes) -> bool:
        """
        检查键可能存在
        返回 False：一定不存在
        返回 True：可能存在（有假阳性）
        """
        for i in range(self.num_hashes):
            index = self._hash(key, i) % len(self.bit_array)
            if not self.bit_array.get(index):
                return False
        return True
    
    def _optimal_size(self) -> int:
        """计算最优位数组大小"""
        import math
        n = self.capacity
        p = self.error_rate
        return int(-n * math.log(p) / (math.log(2) ** 2))
    
    def _optimal_num_hashes(self) -> int:
        """计算最优哈希函数数量"""
        import math
        m = self._optimal_size()
        n = self.capacity
        return max(1, int(m / n * math.log(2)))
          

读取流程：

python

            class LSMTree:
    """
    LSM-tree 完整实现
    """
    
    def __init__(self, db_path: str):
        self.db_path = db_path
        self.memtable = MemTable()
        self.immutable_memtable = None
        self.levels = [[] for _ in range(7)]  # L0-L6
        self.wal = WriteAheadLog(db_path + "/wal.log")
    
    def get(self, key: bytes) -> Optional[bytes]:
        """
        读取键值
        从最新数据到最旧数据依次查找
        """
        # 1. 检查 MemTable
        value = self.memtable.get(key)
        if value is not None:
            return value if value != b'__DELETED__' else None
        
        # 2. 检查 Immutable MemTable
        if self.immutable_memtable:
            value = self.immutable_memtable.get(key)
            if value is not None:
                return value if value != b'__DELETED__' else None
        
        # 3. 从 L0 到 Ln 依次检查 SSTable
        for level, sstables in enumerate(self.levels):
            # 根据 level 选择查找顺序
            if level == 0:
                # L0：从新到旧检查
                for sstable in reversed(sstables):
                    value = sstable.get(key)
                    if value is not None:
                        return value if value != b'__DELETED__' else None
            else:
                # L1+：二分查找定位 SSTable
                sstable = self._find_sstable_in_level(level, key)
                if sstable:
                    value = sstable.get(key)
                    if value is not None:
                        return value if value != b'__DELETED__' else None
        
        return None
          

四、B+树 vs LSM-tree 深度对比

4.1 性能特征对比

维度	B+树	LSM-tree
随机读	O(log N)，稳定	O(log N) ~ O(N)，取决于层数
随机写	O(log N)，随机 IO	O(1)，顺序 IO
范围读	顺序扫描，高效	多路归并，较复杂
空间放大	1.1x ~ 1.3x	1.1x ~ 1.5x
写放大	~10-100x	~10-30x
读放大	~1-3x	~1-10x
并发写入	需要锁，复杂	无锁，简单

4.2 适用场景

选择 B+树：

读密集型 workload
需要事务支持（ACID）
范围查询频繁
数据量适中（< 1TB）

选择 LSM-tree：

写密集型 workload
高并发写入
可以容忍读延迟波动
大数据量（> 1TB）

4.3 混合架构

现代存储引擎往往结合两者优点：

            混合架构（如 MyRocks）：

写入：
  Client -> MemTable (LSM) -> WAL
                         │
                         ▼
                    SSTable Files

读取：
  热点数据 -> Block Cache (B+树索引)
  冷数据 -> SSTable Files
          

五、工程实践与优化

5.1 实际系统实现

RocksDB 优化：

            RocksDB 关键优化：

1. Column Family
   - 多租户支持
   - 独立的 LSM-tree 实例

2. Prefix Bloom Filter
   - 前缀布隆过滤器
   - 优化范围查询

3. Block Cache
   - 分层的 LRU 缓存
   - 索引块和数据块分离

4. Direct IO
   - 绕过页缓存
   - 减少双份缓存

5. Rate Limiter
   - 限制后台合并速度
   - 避免影响前台读写
          

性能调优参数：

python

            # RocksDB 配置示例
options = {
    # 写缓冲
    'write_buffer_size': 64 * 1024 * 1024,  # 64MB
    'max_write_buffer_number': 3,
    
    # 合并策略
    'compaction_style': 'level',
    'target_file_size_base': 64 * 1024 * 1024,
    'max_bytes_for_level_base': 512 * 1024 * 1024,
    
    # 缓存
    'block_cache_size': 8 * 1024 * 1024 * 1024,  # 8GB
    'block_size': 16 * 1024,  # 16KB
    
    # 布隆过滤器
    'bloom_filter_bits': 10,
}
          

5.2 监控与诊断

关键指标：

python

            class StorageMetrics:
    """
    存储引擎监控指标
    """
    
    def __init__(self):
        # 延迟指标
        self.read_latency = Histogram()
        self.write_latency = Histogram()
        
        # 吞吐量
        self.read_throughput = Counter()
        self.write_throughput = Counter()
        
        # 放大指标
        self.write_amplification = Gauge()
        self.read_amplification = Gauge()
        self.space_amplification = Gauge()
        
        # 合并指标
        self.compaction_pending = Gauge()
        self.compaction_bytes_per_sec = Gauge()
        
        # 缓存指标
        self.block_cache_hit_rate = Gauge()
        self.bloom_filter_efficiency = Gauge()
          

5.3 故障处理

数据损坏检测：

python

            def verify_sstable(sstable_path: str) -> bool:
    """验证 SSTable 完整性"""
    with open(sstable_path, 'rb') as f:
        # 读取 Footer
        f.seek(-48, 2)  # 最后 48 字节
        footer = f.read(48)
        
        # 验证 Magic Number
        magic = footer[-8:]
        if magic != b'0x88e241b785f4cff7':
            return False
        
        # 验证 Checksum
        index_offset = int.from_bytes(footer[:8], 'little')
        f.seek(index_offset)
        index_block = f.read()
        
        stored_checksum = index_block[-4:]
        computed_checksum = crc32(index_block[:-4])
        
        return stored_checksum == computed_checksum.to_bytes(4, 'little')
          

结语

B+树与 LSM-tree 代表了存储引擎设计的两种哲学：

B+树：

"就地更新，保持有序"

读优化，延迟稳定

适合事务型 workload

LSM-tree：

"追加写入，延迟整理"

写优化，吞吐极高

适合分析型 workload

理解这两种数据结构，不仅是掌握存储引擎的基础，更是理解读写权衡这一分布式系统核心矛盾的窗口。

在现代数据库系统中，两者往往结合使用：B+树作为索引，LSM-tree 作为存储，各取所长，共同构建高性能、高可靠的存储引擎。

参考资源

经典论文：

Bayer, R., & McCreight, E. (1972). "Organization and Maintenance of Large Ordered Indexes". Acta Informatica.
O'Neil, P., Cheng, E., Gawlick, D., & O'Neil, E. (1996). "The Log-Structured Merge-Tree (LSM-Tree)". Acta Informatica.
Graefe, G. (2011). "Modern B-Tree Techniques". Foundations and Trends in Databases.

工程实践： 4. RocksDB Wiki: https://github.com/facebook/rocksdb/wiki 5. LevelDB Documentation: https://github.com/google/leveldb/blob/main/doc/index.md 6. MyRocks: http://myrocks.io/

性能研究： 7. Lomet, D., & Barga, R. (2019). "The Bw-Tree: A B-tree for New Hardware Platforms". ICDE. 8. Dong, S., Callaghan, M., Galanis, L., Borthakur, D., Savor, T., & Strum, M. (2017). "Optimizing Space Amplification in RocksDB". CIDR.

创建时间：2026年04月11日
更新时间：2026年04月11日