B-Tree vs LSMTree

Posted on In

B-tree 和 LSM-tree 是数据密集型应用中用于组织和存储数据最广泛的两种数据结构。然而，两者各有优劣。本文旨在通过定量分析的方法对这两种数据结构进行对比。

衡量指标

通常情况下，衡量数据结构性能有三个关键指标：写放大（Write Amplification）、读放大（Read Amplification）和空间放大（Space Amplification）。本节旨在对这些指标进行描述。

对于机械硬盘（HDD）而言，磁盘寻道成本极高，导致随机读写的性能远不如顺序读写。本文假设使用的是闪存存储（如 SSD），因此我们可以忽略磁盘寻道的成本。

写放大（Write Amplification）

写放大（Write Amplification）是指写入存储设备的实际数据量与写入数据库的数据量之比。

例如，如果你向数据库写入了 10 MB 数据，但观察到磁盘实际产生了 30 MB 的写入量（或观测到磁盘写入带宽是数据库写入带宽的 3 倍），那么写放大就是 3

读放大（Read Amplification）

读放大（Read Amplification）是指每次查询所需的磁盘读取次数。

例如，如果为了响应一个查询需要读取 5 个页面，那么读放大就是 5。

请注意，写放大与读放大的单位是不同的。写放大衡量的是实际写入数据量与应用程序预期写入量之间的倍数关系；而读放大计算的是执行一次查询所需的磁盘读取次数。

读放大针对点查询（Point Query）和范围查询（Range Query）有不同的定义。对于范围查询，范围的长度（即需要获取的行数）是一个重要因素。

缓存是影响读放大的关键因素。例如，对于冷缓存（Cold-cache）情况下的 B 树，一次点查询需要 O(log_B N)次磁盘读取；而在热缓存（Warm-cache）情况下，B 树的内部节点已被缓存，因此每次查询最多只需要一次磁盘读取。

N：数据库中 记录（keys / tuples）的总数量
B：一个磁盘页（page / block）能容纳的 key 数量

空间放大（Space Amplification）

空间放大（Space Amplification）是指存储设备上占用的实际数据量与数据库中存储的逻辑数据量之比。

例如，如果您向数据库存入 10 MB 的数据，而该数据库在磁盘上占用了 100 MB，那么空间放大倍数就是 10。

通常来说，一种数据结构最多只能在读、写和空间放大这三个指标中优化其中的两个。这意味着一种数据结构很难在所有三个指标上都优于另一种。例如，B 树的读放大比 LSM 树小，而 LSM 树的写放大则比 B 树小

分析

B 树是二叉搜索树（Binary Search Tree）的一种推广，其节点可以拥有两个以上的子节点。B 树中有两类节点：内部节点（Internal nodes）和叶子节点（Leaf nodes）。叶子节点包含实际的数据记录且没有子节点；而内部节点可以在预定义的范围内拥有不同数量的子节点。内部节点可以进行合并或分裂。图 1 展示了一个 B 树的示例。

图 1。根节点位于树的顶部，在本例中恰好包含一个枢轴键（Pivot keys）（20），这表示键值为 k 且满足 k <= 20 的记录存储在第一个子节点中，而键值满足 k > 20 的记录存储在第二个子节点中。第一个子节点包含两个枢轴键（11 和 15），这表示键值满足 k <= 11 的记录存储在第一个（孙子）节点中，满足 11 < k <= 15 的记录存储在第二个节点中，而满足 k > 15 的记录则存储在第三个节点中。最左侧的叶子节点包含三个数值（3、5 和 7）。

“B 树”一词可以指代一种特定的设计，也可以指代一类通用的设计。从狭义上讲，B 树在其内部节点中存储键（Keys），但并不一定在叶子节点的记录中重复存储这些键。B+ 树（B+ tree）是 B 树最著名的变体之一。B+ 树的核心理念是：内部节点仅包含键，且在底部增加了一个包含实际数值的额外层级，该层级的叶子节点相互连接。

与其他搜索树一样，LSM 树（LSM-tree）也包含键值对（Key-value pairs）。它将数据维护在两个或多个独立的组件中（有时被称为 SSTables），每个组件都针对其对应的底层存储介质进行了优化。低层组件中的数据会以批处理的方式高效地与高层组件中的数据进行合并。图 2 展示了一个 LSM 树的示例。

图 2。LSM 树包含 $k$ 个组件。数据首先进入 $C_0$ 层，随后被合并到 $C_1$ 层。最终，$C_1$ 层的数据会被合并到 $C_2$ 层，以此类推。

LSM 树会定期执行合并（Compaction）操作，将多个 SSTable 合并为一个仅包含“活跃数据”（Live data）的新 SSTable。合并操作有助于 LSM 树回收空间并降低读放大。合并策略主要有两种：大小分级合并策略（STCS）和层级合并策略（LBCS）。STCS 的核心思想是：当 LSM 树积累了足够的短小 SSTable 时，将其合并为中等大小的 SSTable；当中等 SSTable 足够多时，再将其合并为大型 SSTable。而 LBCS 的核心思想是将数据组织进不同的层级（Level），每个层级包含一个有序序列（Sorted run）。一旦某一层积累了足够的数据，该层级的部分数据就会被合并到更高层级中。

本文讨论 B+ 树和基于层级的（Level-Based）LSM 树的写放大与读放大。

B+ Tree

在 B+ 树中，键（Keys）的副本存储在内部节点中；键与记录（Records）存储在叶子节点中；此外，叶子节点可能还包含指向下一个叶子节点的指针，以提高顺序访问性能。

为了简化分析，假设树的块大小（Block size）为 $B$（以字节为单位），且键、指针和记录的大小都是固定的，因此每个内部节点包含 $O(B)$ 个子节点，每个叶子节点包含 $O(B)$ 条数据记录。（根节点是一个特例，在某些情况下可能几乎为空。）在上述所有假设下，B+ 树的深度为：$$O(\log_B \frac{N}{B})$$其中 $N$ 是数据库的总大小。

写放大 (Write Amplification)
在最坏情况的插入负载下，每次插入都需要重写包含该记录的整个叶子块，因此写放大为 $B$。

读放大 (Read Amplification)
每次查询的磁盘读取次数最多为 $O(\log_B \frac{N}{B})$，即树的深度

Level-Based LSM-tree

在基于层级的（Level-based）LSM 树中，数据按层组织。每一层包含一个有序序列。数据始于第 0 层（Level 0），随后被合并到第 1 层的序列中。最终，第 1 层的数据会被合并到第 2 层，以此类推。每一层的大小都受到限制。增长因子（Growth factor） $k$ 定义为每一层数据容量的放大倍数：

$$\text{level}i = \text{level}{i-1} \times k$$

我们可以对基于层级的 LSM 树进行如下分析：如果增长因子为 $k$，且最小的层级是一个大小为 $B$ 的单个文件，那么层级的数量为：

$$\Theta(\log_k N/B)$$

其中 $N$ 是数据库的大小。为了简化分析，我们假设数据库规模稳定且随时间增长缓慢，因此数据库的总大小几乎等同于最后一层的大小。

写放大 (Write Amplification)
数据必须从每一层移出一次，但给定层级的数据会与来自前一层的数据不断重复合并。平均而言，每个数据项在首次写入某一层后，会被重新合并回同一层约 $k/2$ 次。因此，总的写放大为：$$\Theta(k \times \log_k N/B)$$

读放大 (Read Amplification) 在冷缓存情况下执行短范围查询时，我们必须在每个层级上进行二分查找。

对于最高层级 $\text{level}_i$，数据大小为 $O(N)$，因此执行 $O(\log N/B)$ 次磁盘读取。

对于上一层级 $\text{level}_{i-1}$，数据大小为 $O(N/k)$，执行 $O(\log (N/kB))$ 次磁盘读取。

对于 $\text{level}_{i-2}$ 层，数据大小为 $O(N/k^2)$，执行 $O(\log (N/k^2B))$ 次磁盘读取。

……

以此类推。

因此，磁盘读取的总次数为：$$R = O(\log N/B) + O(\log (N/kB)) + O(\log (N/k^2B)) + \dots + 1 = O(\frac{\log^2 N/B}{\log k})$$

总结

下表总结了各种放大指标：

数据结构 写放大 (Write Amplification) 读放大 (Read Amplification)
B+ 树 Θ(B) O(logB​N/B)
层级 LSM 树 Θ(klogk​N/B) Θ(logklog2N/B​)

通过对比 B+ 树与基于层级的 LSM 树的各种放大指标，我们可以得出结论：基于层级的 LSM 树在写入性能上优于 B+ 树，但在读取性能上则逊于 B+ 树。TiKV 选用 LSM 树而非 B 树作为其底层存储引擎的主要原因在于：利用缓存技术来提升读取性能，要比提升写入性能容易得多。