磁盘IO系列（四）：B树和RUM猜想

在前几篇文章中，我们讨论了不同类型的IO以及一种称为LSM树的不可变磁盘数据结构。继续这一系列，我们将讨论一种读取优化的可变存储，这种存储也有很多变体（这里只会简要提及，可能在以后深入探讨），并以RUM猜想总结我们对磁盘数据结构的探索。

可变存储

可变存储通常使用堆表文件实现，结合某种索引。在本文中，我们将仔细看看B树。

B树

B树是一种流行的索引数据结构，有许多变体，并在许多数据库中使用，包括MySQL InnoDB和PostgreSQL。B树是二叉搜索树的推广，其中每个节点允许多个指针。B树是自平衡的，因此在插入和删除期间不需要旋转步骤，只有合并和分裂。使用B树作为索引的原因是其对查找时间的重要性，具有对数时间查找保证。

除非另有说明，我们将主要讨论B+树，这是一种现代的B树变体，常用于数据库。B+树与原始B树论文不同，增加了一个链接的叶节点层，这些叶节点存储值。

结构

B树有几种节点类型：根节点、内部节点和叶节点。根节点是没有“父节点”的节点（例如，不是任何其他节点的子节点）。叶节点是没有子节点并携带数据的节点。内部节点是既有父节点又有子节点的节点，它们连接根节点和叶节点。一些B树变体允许在内部节点上存储数据。B树的一个特点是它的分支因子：指向子节点的指针数量（N）。根节点和内部节点最多包含N-1个键。

树中的每个非叶子节点包含N个键（索引条目），将树分隔成子树，并有N+1个指向子节点的指针。条目Ki的指针i指向一个子树，其中所有索引条目的键满足Ki <= K < Ki+1（其中K是一组键）。第一个和最后一个指针是特殊情况，分别指向所有条目小于（或等于）和大于K的子树。从逻辑上讲，内部节点保存键，代表它们指向的子节点的最小键。内部节点和叶节点还保存指向同一级别上前后节点的指针，形成一个双向链接的兄弟节点链表。

通常，保持B树节点的大小为一到两个页面大小（4-8K）是个好主意。考虑到这一点并知道你的键大小，你可以近似估算分支因子和树的高度（层数）。高度不应太大，因为跳过一个完整的层需要随机访问，执行太多的随机访问可能会导致性能下降。分支因子通常在数百左右；但是，当键很大时，它可能会更低。设置分支因子过高也可能导致性能问题。B树调整和选择分支因子的一个经验法则是，叶节点应该占据树空间的绝大多数。

查找

B树的根节点和内部节点通常可以缓存在RAM中，以促进更快的查找。由于在每一层中，子节点的数量按分支因子增长，叶节点占用的空间将大得多。在叶节点中进行搜索将在内存中进行，从叶节点中搜索和检索最终值将在磁盘上进行。

执行查找时，搜索从根节点开始，一直到达叶节点。在每一层，算法找到两个键，其中一个比搜索项小，另一个比搜索项大（搜索项在它们之间），然后沿着键之间的子指针进行查找。

在节点内的搜索通常使用二分搜索进行。对于固定大小的键，进行二分搜索的方式很明确：知道排序数组中的项的数量，跳到中间位置，进行比较，决定是向左遍历还是向右遍历，并重复此过程直到找到该项。

对于变长数据，可以在数据前面添加一个间接向量，保存实际记录的偏移量。间接向量中的指针必须按照搜索键排序（实际的变长数据不必按排序）。二分搜索通过选择间接向量的中间指针进行比较，以确定遍历方向，并重复此操作直到找到搜索键。

对于点查询，找到节点后搜索就完成了。当执行范围扫描时，遍历当前节点和其兄弟叶节点的键和值，直到到达范围的末尾。

修改

执行插入操作时，首先要定位目标叶节点。为此，使用前面提到的搜索算法。找到目标叶节点后，将键和值附加到该节点。如果叶节点没有足够的空闲空间，这种情况称为溢出，叶节点必须分裂成两个叶节点。通过分配一个新叶节点，将一半的元素移动到新节点，并将指向新分配叶节点的指针添加到父节点来完成分裂。如果父节点也没有足够的空间，则进行另一次分裂。这个操作会一直持续到达根节点。通常，当根节点被分裂时，其内容会被分配到新分配的节点之间，根节点本身会被重写以避免重新定位。这也意味着树的高度总是从根节点开始增长，通过分裂它。

更新和删除

更新操作类似于插入操作，除了现有记录通常会被覆盖或附加到写缓冲区以进行延迟写入。删除操作可以被视为反向操作：当叶节点的占用率下降到某个阈值以下时，情况被视为下溢，此时会发生负载平衡（将键从占用较多的节点转移到占用较少的节点）或者合并两个兄弟节点，触发从父节点中移除键和指针，这反过来可能触发向上的重新平衡和合并级联。

我们不会深入讨论B树分裂和合并的语义（它们在什么阈值下发生），因为这取决于具体的B树变体。这里重要的是要提到，满节点分裂时，其内容必须重新定位，指针也需要更新。节点分裂和合并可能会向上传播一到多个层次，因为在分裂和合并期间子指针会在父节点上更新；树的高度在分裂时增长，在合并时缩小。

在进行分裂和合并时，必须锁定树的一部分：更新所有将在单个操作中分裂的节点对于读写者应该看起来是原子的。B树并发控制领域有一些研究，其中一个这样的尝试是Blink树，承诺更少的锁定，是一种更适合高并发的算法。

树的分支度直接影响将进行多少IO操作：较小的节点不仅可能导致树的深度更高，还会更频繁地触发分裂。

堆文件是变长记录的无序列表。由于它们经常用于可变存储，文件被分成页面大小的块（4KB或其倍数）。块按顺序编号，并从索引文件中引用。

B树变体

人们使用B树的方式之一是ISAM（索引顺序访问方法），一种创建、维护和操作树的方法，可以摊销B树的一些成本。ISAM结构是完全静态和预分配的。就像B+树一样，数据只存在于叶子页面上，这有助于保持非叶子节点的静态。ISAM的一个特点是存在溢出页面：写入首先进入叶子节点。当叶子节点没有足够空间时，数据会进入溢出区域，因此在搜索时首先遍历叶子页面，然后是溢出页面。其背后的理念是，溢出页面数量很少，不会影响性能。

另一个例子是B+树。有许多实现它们的方法，但许多现代实现都具有可变动态B+树的特点。它们的特别之处在于数据仅存储在叶子上。这可能简化了对树结构的更新，因为键的大小较小，可以很好地适应内部节点页面。叶子页面可以在必要时增长甚至重新定位，这只需要更新内部节点上的一个指针。

还有许多其他例子，每一个都涵盖了特殊情况：优化内存管理的Cache-Oblivious B树，已经提到的改进并发性的Blink树，提高写性能的分区B树等。

B树维护

许多现代数据库使用B树索引：它们快速、高效，并且有许多广泛已知和使用的优化。大多数实现是可变的。这意味着数据结构是动态的并且在磁盘上变化：当分配新节点时，内部结构会改变。为了促进这一点，必须为表维护一定的开销，所谓的占用因子，允许一些新写入的操作空间。在后面的章节中，我们将详细讨论数据库如何应对这个问题：通过使用写缓冲区、使用溢出页面或通过重写对表进行碎片整理。

压缩和负载平衡有助于B树的空间管理。压缩期间（这个术语在B树上下文中与在LSM树中的含义不同），通过清除过时或删除的记录并连续重写节点来回收空间（当树存储变长记录时，这可能会产生更大的效果）。负载平衡将键从兄弟节点中取出，并将它们从持有更多记录的节点移动到持有更少记录的节点。保持节点平衡还有助于减少分裂的数量。不幸的是，这种技术似乎有些被忽视了。页面分裂也有一些潜在的性能优化：为了便于键范围扫描，节点可以在磁盘上彼此靠近放置。

索引可以通过批量加载形成（类似于在LSM树中创建SSTable索引）。在批量加载时，数据可以预先排序，整个算法更简单：所有追加操作都将完成在最右边的子节点，以避免遍历。当最右边的索引页面满了时将进行分裂，这可能会在上层触发一系列分裂。使用不可变的B树变体进行批量加载可以保证完全占用，这既节省空间又提高读取性能，因为在占用因子较高时需要的节点更少。

RUM猜想

有很多方法可以读取和写入数据：数据结构、访问模式、优化措施：所有这些都对系统的最终性能有所贡献。但很难同时在所有方面都优化系统。在理想世界中，我们会有能够保证最佳读写性能并且没有存储开销的数据结构，但实际上这是不可能的。哈佛大学数据库实验室的研究人员总结了人们在设计数据库系统时试图优化的三个参数：读取开销、更新开销和内存开销。决定优化哪个开销将影响数据结构、访问方法的选择，甚至某些工作负载的适用性。RUM猜想指出，为其中两个开销设置上限也会为第三个开销设置下限。

树状数据结构通常针对读取性能进行优化，这需要付出空间开销和写入放大的代价，后者来自节点分裂/合并、重新定位以及与碎片/不平衡相关的维护工作。在读取放大方面，树状结构有助于最小化总访问数据与预期读取数据之间的比率。使用自适应数据结构可以在提高读取性能的同时，带来更高的维护成本。添加促进遍历的元数据（如分数级联）会影响写入时间并占用空间，但可以提高读取时间。

LSM树

正如我们已经讨论过的，LSM树优化了写入性能。更新和删除操作不需要在磁盘上搜索数据，并通过延迟和缓冲所有插入、更新和删除操作来保证顺序写入。这带来了更高的维护成本和压缩的需要（这只是缓解不断增长的读取成本的一种方式）以及更昂贵的读取（因为数据必须从多个文件中读取并合并在一起）。同时，LSM树通过避免保留空闲空间（这是某些读取优化数据结构中的开销来源）并允许块压缩来提高内存效率，因为最终文件的占用率更高且不可变。

内存效率优化

优化内存效率可能涉及使用压缩（例如，Gorilla压缩、delta编码等算法），这会增加一些读取和写入开销。有时你可以以效率为代价来换取功能。例如，堆文件和哈希索引由于文件格式简单，可以提供良好的性能保证和较小的空间开销，但代价是只能执行点查询。你还可以通过使用近似数据结构来换取效率，例如布隆过滤器、HyperLogLog、Count Min Sketch等。

读取、更新和内存开销

这三个可调节参数：读取开销、更新开销和内存开销，可以帮助你评估数据库并更深入地了解其适用的工作负载。所有这些参数都非常直观，通常很容易将存储系统分类到其中一个类别中，并猜测其性能表现。

结语

话虽如此，使用最佳的数据结构只是完成了一半的工作：数据库系统中还有许多部分的性能可能仍然是瓶颈。但我们假设数据库开发人员总是致力于消除问题，使他们的产品在其设计的工作负载下表现最佳，并在所有其他使用场景下表现良好。

下一次，我们将继续讨论不同的数据库方法。计划是仔细看看访问模式，并了解哪些类型的工作负载提供了某些保证。我们还将简要讨论不同类型的数据集如何影响数据库的选择。

我正在评估为架构师、数据库开发人员和所有可能对数据库存储感兴趣的人撰写一本深入书籍的兴趣。我会继续发布关于这个主题的简短文章，但如果你对更全面的指南感兴趣，请订阅邮件列表，你可以通过邮件列表获得最新更新，如果书籍真的被写出来，你将是第一个知道的人。我保证保持内容有趣且简短。