database - 用 B-tree 优化 AVLTree

Question

前提

所以最近我一直在思考一个数据库常见的问题：尝试优化数据的插入、搜索、删除和更新。通常我看到现在大多数数据库都使用 BTree 或 B+Tree 来解决这样的问题，但它们通常用于将数据存储在磁盘内，我想处理内存中的数据，所以我考虑使用AVLTree（差异应该很小，因为 BTrees 的目的与 AVLTree 相同，但实现不同，效果也不同）。在继续这背后的推理之前，我想更深入地了解我想要解决的问题。因此，在一个现代数据库中，数据存储在一个带有 PRIMARY KEY 的表中，该表往往被索引（我在索引方面不是很有经验，所以我要说的是我对这个问题的基本推理），

理论

因此，正如问题的标题所示，我正在尝试优化 AVLTree，将其与 Btree 合并。基本上，这个新树的每个节点都可以说是一个由十个元素组成的数组，每个节点也是树中的相应高度，并且数组的每个元素都是按升序排列的。

插入

当根节点已满时，插入最初会填充根节点的数组，它会生成左右子节点，其中也包含 10 个元素的数组。每当添加一个新节点时，树会根据左右子节点向量的第一个键使用它们的高度自动重新平衡节点（请注意，这实际上是 AVLTree 的行为方式，但 AVLTree 只有 2 个节点，没有向量而已价值）。

搜索

搜索一个元素是这样工作的：从根开始，我们将我们正在搜索的值K与当前节点数组的第一个和最后一个键进行比较，如果值介于两者之间，我们知道它肯定会在当前节点，因此我们可以开始使用复杂度为 O(log2(n)) 的 binarySearch 到这个包含十个元素的数组中，否则如果我们搜索的键小于第一个键，我们就往左边走，如果它更大。

删除

与搜索相同，但我们删除了该值。

更新

与搜索相同，但我们更新了值。

结论

如果我没记错的话，这应该具有 O(log10(log2(10))) 的复杂度，它始终是对数的，所以我们不应该关心这种优化，但在我看来，这可能会使树的高度小得多同时还提供快速搜索时间。

标签： databaseoptimizationtreetime-complexitybinary-search

Answer 1

B树和B+树确实是因为块的设计而用于磁盘存储。但是没有理由不能将它们也用作内存数据结构。

B 树的优点包括它在单个节点内使用数组。在可能有 10 个条目的有限向量中查找可能非常快。

您在 B 树和 AVL 之间折衷的想法肯定会奏效，但请注意：

• 您需要像在 AVL 中一样执行树旋转以保持树平衡。在 B 树中，您使用重新分配、合并和拆分，但没有旋转。
• 与 AVL 一样，树并不总是完美平衡的。
• 您需要描述当向量已满并且需要向其添加值时将执行的操作：节点必须拆分，一半必须作为叶子重新注入。
• 您需要描述当向量获得非常低的填充因子（由于删除）时将执行的操作。如果你这样离开它，树可能会退化成一个 AVL 树，其中每个向量只有 1 个值，然后额外的向量开销将使其效率低于真正的 AVL 树。要使向量的填充因子保持在最小值以上，您不能像在 B 树中那样轻松地对兄弟节点应用重新分配机制。它适用于叶节点，但不适用于内部节点。所以这个需要澄清...
• 您需要描述更新向量中的值时将执行的操作。当然，您可以将它插入到它的排序位置：但是如果它成为该向量中的第一个或最后一个值，这可能会违反左右孩子的顺序，因此您可能还需要更精确地定义算法。
• 在一个 10 的向量中进行二分搜索可能有点过头了：简单的从左到右的扫描可能会更快，因为 CPU 已针对读取连续内存进行了优化。这不会影响时间复杂度，因为我们将向量大小限制为 10。所以我们谈论的是最多进行 4 次比较（平均 3-4 次，具体取决于二进制搜索实现）或最多 10 次比较（5一般）。

如果我没记错的话，这应该具有O(log10(log2(n)))的复杂度，它总是对数的

实际上，如果这是真的，那将是次对数，即O(loglogn)。但是这里有一个错误。向量中的二分查找与n无关，而是与 10 相关。此外，这项工作还包括查找具有该向量的节点。所以它不是对数的对数，而是对数的和：

O(log ₁₀ n + log ₂ 10) = O(log n)

因此，时间复杂度与 AVL 或 B-tree 的时间复杂度没有什么不同——前提是算法在缺少细节的情况下完成，并保持在对数复杂度内。

您也许还应该考虑实现纯 B 树或 B+ 树：这样您还可以从 AVL 和中间结构都没有的一些优点中受益：

• 树的叶子都在同一水平线上
• 不需要旋转
• 树的高度只在一个地方发生变化：根。
• B+ 树为按顺序迭代所有值提供了一种非常快速的方法。