Kyle's Notebook

关于 B-Trees 的更多细节(译)

Word count: 2.9kReading time: 10 min
2021/09/05

原文链接:https://benjamincongdon.me/blog/2021/08/17/B-Trees-More-Than-I-Thought-Id-Want-to-Know

建议参考《数据库系统内幕》

关于 B-Trees 的更多细节

磁盘引起的约束

当试图在磁盘上存储大量的键值对时,也希望以一种简单的方法实现读取,并且希望能轻松查询特定键或键范围。

而一旦需要考虑磁盘 I/O,就会遇到一些在内存结构中不常见的限制:

  • 无法将整个数据集放入内存:需要对数据进行布局,以便仅将结构的一个子集加载到内存中来遍历结构。

  • 与内存访问(通常是整个页面与单个字节)相比,(从驱动中读写数据的)最小存储单元很大:应尽量将可能被一起访问的数据放在同一位置。

  • 磁盘 I/O 比在内存中查找要慢得多:应尽可能减少磁盘访问次数。

Petrov 通过一个例子说明将键/值存储在二叉搜索树(BST)中、并将该 BST 存储在磁盘上的简单方法:

在磁盘上维护 BST 会面临几个问题。其一是 局部性:元素是按随机添加的,不能保证新创建的节点被写入靠近其父节点的位置,意味着节点子指针可能跨越多个磁盘页面。

由于二叉树只有两个扇出,其高度是树元素数量的二元对数,必须以 O(log2N) 的复杂度定位元素,再执行相同数量的磁盘传输。

由于没有内置的局部性概念,在磁盘上 BST 实现要求与比较操作一样多的搜索操作。

由于 键比较操作次数 大致等于 磁盘寻道次数,BST 作为磁盘结构表现不佳:定位条目所需的键比较次数与数据集大小成比例,因此没有多少办法可对此做文章。然而却可以考虑改变 每次磁盘搜索触发的键比较次数:在磁盘布局中,将键收集到一起。如果在磁盘上存储一批彼此相邻的键,以便通过一次查找就能执行大量的键比较操作。这就是采用 B-Trees 实现的效果。 换句话说,B-Trees 具有高扇出。

这就是有一些人将 B-Trees 描述为 3 元到 5 元树是误用的原因:实际上可为每个节点存储数百个键,能提高每次磁盘搜索的键比较扇出的效益。

以槽实现的页

在深入了解 B-Trees 的过程中,可了解到一些更实际的细节,即考虑键在磁盘上的布局,以发挥最大化局部性和键的压缩。关于持久化存储的基础知识:

硬盘驱动器(HDD)包含通过静态磁头读取和写入的旋转磁盘,这使得随机访问比顺序访问慢,因为要查看驱动器的不同部分时,都需要等待磁盘旋转,使访问的部分位于磁头下方。

固态驱动器(SSD)由一系列内存单元构成,并组成页面、块和窗格的层次结构。其没有移动部件,但每个单元在永久失效前只能执行有限数量的读/写操作。因此存在设备级和操作系统级软件来跨驱动器分配操作,以延长驱动器的使用寿命。此外 SSD 不仅是“大量速度较慢的 RAM”。而是:

可写入(编程)或读取的最小单位是页。 但是只能对空的存储单元(即在写入之前已擦除的存储单元)进行更改。最小的擦除实体不是页面,而是包含多个页面的块,因此它通常被称为擦除块。空块中的页面必须按顺序写入。

综上所述,HDD 和 SSD 对它们可读写的最小单位都有硬件限制。操作系统将其抽象为块设备接口。 由于任何磁盘结构都应知道其更改的块(页面)的数量。在 1000 个不同的块中更改 1000 个字节,将比在同一块中更改 1000 个字节慢得多(读取同理)。因此需要考虑数据结构的逻辑布局,以很好地适应块设备抽象。

B-Trees 天然地适合页面布局:每个逻辑节点都有一个磁盘页面。可以调整树的参数(主要是每个节点的键数),以便在磁盘页面内适应固定节点。然而 B-Trees 是动态的,树节点可能因插入或删除操作而更改,并且键必须在节点内保持顺序。要按顺序布局数据,而且无需在每次变更期间移动数据,就应该以槽实现实现页。

Slotted Page Layout

这种布局的好处是可存储大小可变的数据,单元格大小可变,而且无需移动该数据以对其进行逻辑重新排序。重新排序指针数组中指针的位置即可。 由于指针很小,并且位于页面开头的位置,移动指针操作成本很低。 因此只要偏移指针是按键的顺序排列,键在实际页面中存储的位置不重要,这意味着还可以在删除/插入数据时释放和重用单元格(例如 SQLite 使用 freelist 实现管理)

B-Trees 查询

B-Trees 查找算法非常简单:

  • 从根节点开始。

  • 检查当前节点中的分隔键,以找到逻辑上包含待查找的搜索键的子节点。

  • 基于上一步骤的逻辑递归遍历树。

  • 但找到一个包含正在搜索的键的叶节点即完成操作;如果发现搜索关键字的叶节点不存在(例如该范围没有叶节点),或者叶节点不包含关键字,则返回不存在。

第 2 步掩盖了一些与存储大量数据的更高阶树有关的有趣的细节。

  • 在遍历树的大多数实现中,会对节点内的键执行二分搜索,因此键在节点内按顺序存储很重要。

  • 叶节点实际存储数据,分隔键只是充当节点之间的分区,其无需存放完整的值。只要分隔键准确地表示每个子节点负责的键范围之间的分区,就可以是包含该分区属性的任何值。使用实际的数据库键作为分区键只是一种便捷方法。

分隔键截断

利用以上描述的特性,可以决定更好的分区键来提高 B-Trees 存储效率:

不必存储整个键,而是存放缩写来节省页空间。尤其是在树内部的页中,键充当键范围之间的边界,只需要提供足够的信息。将更多的键打包到一个页面中,可使树具有更高的分支因子,从而减少层级。

为了说明这一点,假设正在尝试存储以下键:

1
2
3
4
5
6
0xAAAAAA
0xBBBBBB
0xCCCCCC
0xDDDDDD
0xEEEEEE
0xFFFFFF

插入算法决定将以上的键存储在 2 个树节点中:

1
2
3
4
5
6
7
8
9
# Node 1
0xAAAAAA
0xBBBBBB
0xCCCCCC

# Node 2
0xDDDDDD
0xEEEEEE
0xFFFFFF

考虑节点 1 和节点 2 的父节点应如何选择它们之间的分隔键。最简单是使用 0xDDDDDD,小于 0xDDDDDD 的所有内容都在节点 1 中,大于或等于 0xDDDDDD 的内容都在节点 2 中,但 0xCCCCCC 和 0xDDDDDD 之间间距会很大。可以使用更细粒度的分隔符,并保持正确的分区。例如以前缀键 0xD* 作为分隔符,可以提供同样多的信息,但存储的字节更少。

在真实的数据库系统中键可能非常大(SQLite 默认最大键为 1MB)。键前缀截断也是一种常见做法,可在后缀截断的节点中节省更多空间:

前缀压缩比后缀截断更重要,因为 db 中超过 99% 的节点都是叶子(> 100 的索引扇出在使用前缀编码 + 后缀截断时很常见)。前缀压缩可以节省更多空间。后缀截断对于索引节点密度仍然非常重要,缓存性能和其他。

溢出页

通过分隔键截断,可以将更多键打包到内部(非叶)节点中。 有时可能会在叶节点中遇到相反的问题:物理页面太小,无法容纳逻辑节点中的键的数量。

在这种情况下,一些 B-Trees 实现转向溢出页。存储引擎为溢出数据分配新页面,并更新第一页的 header 以标识溢出。可以简单认为只需在溢出的页中分配额外单元格,并视为有更多的单元格空间。而大多数数据库操作都在键范围内,快速访问键前缀可能比访问整个键更重要。

因此,实际拆分键会更有效:将前缀存储在原始页面中,并将其余部分添加到溢出页:

1
2
3
4
5
6
# Very long key:
AAABBBCCCDDDEEEFFFGGGHHH

| Stored in primary page | Stored in overflow page |
----------------------------------------------------
| AAABBBCC | CDDDEEEFFFGGGHHH |

在检查键是否存在或执行范围查询时,则更有可能无需查阅溢出页:在许多情况下,键前缀足以响应查询。

兄弟指针

最后一个有趣的优化是额外的记录:

在一些实现中,通过存储向前和向后链接,指向左右兄弟页面,有助于定位相邻节点,而无需上升回父节点。

这些同级指针能有效提高范围查询性能:

在范围扫描期间,从最接近的键值对开始迭代,跟随兄弟指针直到到达范围末尾或竭尽范围谓词。

第一,在每个级别的基础上,同级节点始终具有不重叠的、严格递增的键范围。这意味着遍历节点的右兄弟节点可保证(在该级别)包含键空间的逻辑(下一个)块。 再者,在层次更深的树中,拥有兄弟指意味着可避免反向遍历父节点。

在下图中(为简单起见使用二叉树)。每个节点中的第一行表示存储在节点中的键,第二行表示该节点中可以存在的键:

Visual proof for key range property of per-level siblings

从 K8 移动到 K9 是通过一个兄弟指针,而不是在树上向上和向下遍历六跳。因此当查询一系列值时,额外的兄弟指针记录可防止很多不必要的回溯。

B-Trees 变体

最后,除了主要讨论 B⁺-Trees 之外,还有其它 B-Trees 的变体和优化可在某些情况下发挥作用:

  • 像 WiredTiger 和 Lazy-Adaptive Tree 的 Lazy B-Trees 可通过缓冲写入来提高性能。

  • FD-Trees 是一种以对 SSD 物理特性更友好的方式构建 B-Trees 数据。

  • Bw-Trees 为高并发和内存中的树访问提供了进一步的优化。

总结

如果对以上内容感兴趣,再次强烈建议通读《数据库系统内幕》。作为抽象数学概念(B⁺-Tree)和具体实现(SQLite)的数据结构之间存在显着差异,对具体实现的优化不会改善数据结构的大 O 特性,但会对数据库性能和可用性产生重大的现实影响。

下图取自《数据密集型应用系统设计》,可更好地理解实践中的树结构。

img

CATALOG
  1. 1. 关于 B-Trees 的更多细节
    1. 1.1. 磁盘引起的约束
    2. 1.2. 以槽实现的页
    3. 1.3. B-Trees 查询
    4. 1.4. 分隔键截断
    5. 1.5. 溢出页
    6. 1.6. 兄弟指针
    7. 1.7. B-Trees 变体
    8. 1.8. 总结