封面《魔法少女ノ魔女裁判》

前言

因为公司里使用的是 OceanBase 数据库，其 DB 结构是 LSM 树，因此来记录一下 B + 树和 LSM 树的相关知识

B + 树

在 MySQL 这种数据库以及文件系统中，大多使用 B + 树做为索引结构，B + 树是 B 树的变种，B 树是一种平衡多路查找树，B + 树在 B 树的基础上做了改进。因在介绍 B + 树之前先简单的介绍一下 B 树

B 树

B - 树是一种多路平衡查找树，属于自平衡树结构。它与二叉搜索树（BST）类似，但每个节点可以拥有多个子节点和多个键值，从而降低树的高度，提升查找效率。因为在文件和数据库中，每次从磁盘读取数据的开销较大，而 B 树通过减少树的高度，降低了磁盘 I/O 操作的次数，从而提高了数据访问速度。

一颗 B 树需要满足以下性质：

  • 每个节点最多有 N 个子节点（N 为阶数）
  • 每个节点最多包含 N - 1 个键
  • 每个节点（除根节点）至少包含 ⌈N/2⌉ - 1 个键
  • 所有叶子节点位于同一层
  • 根节点至少有两个子节点（除非它是叶子节点）

B-Tree

一个 B 树的查询如下所示，图来自深入解析：B - 树与 B + 树

B-Tree Search

在读取磁盘内容时，通常会以块（block）为单位进行读取，而 B 树的设计使得每个节点可以存储多个键和子节点，从而减少了树的高度。这意味着在查找过程中，所需的磁盘 I/O 操作次数减少，从而提高了数据访问速度。在查询 28 的时候会有以下三次 I/O 查询

  • 第一次 IO，首先加载磁盘块 1， 28>16 ，28<34 ，找到磁盘块 1 → p2
  • 第二次 IO，加载磁盘块 3，28>25 ，28<31 ，找到磁盘块 2 → p2
  • 第三次 IO，加载磁盘块 8， 28=28

B + 树

B 树虽然已经很适合做为数据库索引结构，但还是有着以下缺点

  • 非叶子节点存储数据：非叶子节点存储数据，每个磁盘页能存储的数据量减少，导致树的高度增加，查询效率降低
  • 范围查询效率低：由于叶子节点之间没有指针连接，范围查询需要多次从根节点重新查询
  • 查询不稳定： 由于数据分布不均匀，部分数据可能在根节点只需要查询一次，部分数据在叶子节点需要最长查询链路。查询路径长度不一致，查询耗时差异大

因此 B + 树对 B 树做了以下改进，以提升磁盘 I/O 效率

  • 非叶子节点只存索引数据，所有数据都存储在叶子节点： 这样操作可以使得非叶子节点可以存储更多索引，起到降低树高度的作用，提高磁盘利用率。同时由于数据都在叶子节点，查询路径长度一致，查询效率更稳定
  • 叶子节点组成双向链表： 这样可以提高范围查询的效率，避免多次从根节点重新查询

一个 B + 树的结构如下所示
B+ Tree

LSM 树

在大量写入的场景下，B + 树的性能会受到影响，因为每次写入都需要进行随机 I/O 操作以保持树的平衡性，导致写入性能下降。为了解决这个问题，LSM 树 (Log-Structured Merge Tree) 被提出，用于优化写入密集型工作负载。

OceanBase的LSM树结构

LSM 树由两个主要组件组成：内存中的动态增量数据 (MemTable) 和磁盘上的静态基线数据 (Sorted String Table,SSTable)。写入操作首先在内存中进行，数据写入到 MemTable 中，当内存中的数据达到一定阈值时，会将数据批量写入磁盘，形成新的 SSTable 文件。为了保持查询效率，LSM 树会定期将多个 SSTable 文件合并（称为压缩），以减少文件数量并优化查询性能。

MemTable

MemTable 是 LSM 树中的内存组件，通常实现为跳表或红黑树。它负责接收和存储写入操作的数据，对其的写入和更新都在内存中进行。当 MemTable 达到预设的大小限制时，整个 MemTable 会被刷新到磁盘，形成一个新的 SSTable

OB的MemTable结构 B+树和HashTable实现

SSTable

当 MemTable 达到预设的大小限制时，MemTable 的数据会转储为 SSTable 写入到磁盘当中。写入 SSTable 的数据变不会再变更。

转储和合并

随着时间的推移，磁盘上会积累多个 SSTable 文件。为了优化查询性能，LSM 树会定期将多个 SSTable 文件合并为一个更大的 SSTable 文件，这个过程称为压缩（Compaction）。压缩过程中，会删除重复的数据和过期的数据，从而减少存储空间的使用，并提高查询效率。以 OceanBase 为例，其采用了 Tiered & Leveled 的 Compaction 策略

MiniCompaction

当 MemTable 大小超过限制后，会触发 MiniCompaction。MiniCompaction 会将 MemTable 转入 Mini SSTable，并释放内存

MinorCompaction

随着数据的写入，Mini SSTable 的数量会逐渐增多，在查询时需要访问的 Mini SSTable 数量就会增多，会影响查询的性能。Minor Compaction 就是将多个 Mini SSTable 合成一个 SSTable，其主要目的是减少 SSTable 的数量

  • L0 -> L0 Tiered 类型的 Compaction，系统将若干个 Mini SSTable 合成一个 Mini SSTable，放置于 L0 层
  • L0 -> L1: Leveld 类型的 Compaction，系统将若干个 Mini SSTable 与 Minor SSTable 合成一个新的 Minor SSTable，放置于 L1 层。

MajorCompaction

当增量数据累积到一定程度的时候，就会将多个转储的数据进行合并，与前面的 Minor Compaction 不同，Major Compaction 会将多个层级的数据进行合并产生全量数据，通常是将较高层级的数据与较低层级的数据进行合并，从而减少数据的冗余，提高查询效率。

查询

LSM 树的查询过程相对复杂，因为数据分布在内存中的 MemTable 和多个磁盘上的 SSTable 文件中。查询操作首先会在 MemTable 中查找数据，如果未找到，则依次在 SSTable 文件中进行查找，最后将查询结果合并返回。为了提高查询效率，LSM 树通常会维护一个布隆过滤器 (Bloom Filter) 来快速判断某个键是否存在于某个 SSTable 中，从而减少不必要的磁盘操作

总结

  • LSM 树：
    • 内存中数据读写极快
    • 追加写入特性使得写入性能优异，适合写入密集型场景。如日志、流水型数据
    • 追加写入数据使得顺序读写能力优秀，但是随机读写性能较差
    • 转储合并的过程看可能会影响数据操作，需要合理配置合并触发时间
    • 写放大问题，因为转储合并机制原因。写入的数据量可能远大于实际写入的数据量
  • B + 树：
    • 适合读多写少的场景，读性能优异
    • 单次写入开销稳定可预测
    • 随机 I/O，写入性能受限于磁盘寻道时间

参考资料