使用 B-tree 优化 AVLTree
Optimizing AVLTree with B-tree
前提
所以最近我一直在思考一个数据库普遍存在的问题：试图优化数据的插入、搜索、删除和更新。
通常我看到现在大多数数据库都使用 BTree 或 B+Tree 来解决这样的问题，但它们通常用于将数据存储在磁盘中，我想使用 in-memory 数据，所以我想关于使用 AVLTree（差异应该很小，因为 BTree 的目的与 AVLTree 有点相同，但实现不同，效果也不同）。
在继续这背后的推理之前，我想更深入地了解我要解决的问题。
因此，在现代数据库中，数据存储在 table 中，主键往往被索引（我在索引方面不是很有经验，所以我要说的是我对这个问题的基本推理），通常是主键从 1 开始越来越多（尽管现在这是一种不好的做法）。
通常使用 AVLTree 应该足以解决问题，因为这棵特定的树总是平衡的并提供 O(log2(n)) 操作，但我想在更深层次上达到这一点，试图比需要的更多地优化它。
理论
正如问题的标题所示，我正在尝试优化 AVLTree 并将其与 Btree 合并。
基本上，这个新树的每个节点都可以说是一个包含十个元素的数组，每个节点以及树中的相应高度，并且数组的每个元素都按升序排列。
插入
插入最初填充根节点的数组，当根节点已满时，它生成左右children，其中也包含10个元素的数组。
每当添加新节点时，Tree 都会根据左右向量的第一个键 child 使用它们的高度自动重新平衡节点（请注意，这实际上是 AVLTree 的行为方式，但 AVLTree 只有 2 个节点没有矢量只有值）。
搜索
搜索元素的方式是这样的：从根开始，我们将搜索的值 K 与当前节点数组的第一个和最后一个键进行比较，如果该值介于两者之间，我们知道它肯定会在当前节点的数组中，所以我们可以开始使用具有 O(log2(n)) 复杂度的二进制搜索到这个十个元素的数组中，否则如果我们正在搜索的键更小，那么我们会在左边第一个键，如果它更大，我们就往右走。
删除
与搜索相同，但我们删除了该值。
更新
与搜索相同，但我们更新了值。
结论
如果我没记错的话，这应该有一个 O(log10(log2(10))) 的复杂度，它总是对数的，所以我们不应该关心这个优化，但在我看来，这可能会使高度树小得多，同时也提供了快速的搜索时间。
B树和B+树确实是用来做磁盘存储的，因为是分块设计的。但是没有理由不能将它们也用作 in-memory 数据结构。
B 树的优点包括它在单个节点内使用数组。 Look-up 在可能只有 10 个条目的有限向量中可能非常快。
您在 B 树和 AVL 之间折衷的想法肯定可行，但请注意：
- 您需要像在 AVL 中一样执行树旋转以保持树平衡。在 B 树中，您使用重新分配、合并和拆分，但没有旋转。
- 与 AVL 一样，树不会总是完美平衡。
- 你需要描述当向量已满并需要向其添加值时将执行的操作：节点将不得不分裂，并且一半必须作为叶子重新注入。
- 您需要描述当向量变得非常低 fill-factor（由于删除）时将执行的操作。如果你这样，树可能会退化为 AVL 树，其中每个向量只有 1 个值，然后额外的向量开销将使其效率低于真正的 AVL 树。要使向量的 fill-factor 保持在最小值之上，您不能像在 B-trees 中那样轻松地对兄弟节点应用重新分配机制。它适用于叶节点，但不适用于内部节点。所以这需要澄清...
- 您需要描述更新向量中的值时将执行的操作。当然，你会把它插入到它的排序位置：但如果它成为该向量中的第一个或最后一个值，这可能会违反左右 children 的顺序，因此你可能还需要更精确地定义算法。
- 在 10 的向量中进行二进制搜索可能有点矫枉过正：简单的 left-to-right 扫描可能会更快，因为 CPU 已优化为读取连续内存。这不会影响时间复杂度，因为我们将向量大小设置为 10。所以我们正在谈论最多进行 4 次比较（平均 3-4 次，具体取决于二进制搜索实现）或最多 10 次比较（5平均）。
If I am not wrong this should have a complexity of O(log10(log2(n))) which is always logarithmic
实际上，如果这是真的，它将是 sub-logarithmic，即 O(loglogn)。但是这里有一个错误。向量中的二进制搜索与 n 无关，但与 10 相关。此外，这项工作还 addition 来查找具有该向量的节点.所以不是对数的对数，而是对数的和：
O(log10n + log210) = O(log n)
因此，时间复杂度与 AVL 或 B-tree 的时间复杂度没有区别——前提是该算法完成了缺失的细节，并保持在对数复杂度内。
您也许还应该考虑实现纯 B 树或 B+ 树：这样您还可以从 AVL 和 in-between 结构都没有的一些优势中获益：
- 树的叶子都在同一层
- 不需要旋转
- 树高只在一处发生变化：根。
- B+ 树提供了一种按顺序迭代所有值的非常快速的方法。
前提
所以最近我一直在思考一个数据库普遍存在的问题：试图优化数据的插入、搜索、删除和更新。 通常我看到现在大多数数据库都使用 BTree 或 B+Tree 来解决这样的问题，但它们通常用于将数据存储在磁盘中，我想使用 in-memory 数据，所以我想关于使用 AVLTree（差异应该很小，因为 BTree 的目的与 AVLTree 有点相同，但实现不同，效果也不同）。 在继续这背后的推理之前，我想更深入地了解我要解决的问题。 因此，在现代数据库中，数据存储在 table 中，主键往往被索引（我在索引方面不是很有经验，所以我要说的是我对这个问题的基本推理），通常是主键从 1 开始越来越多（尽管现在这是一种不好的做法）。 通常使用 AVLTree 应该足以解决问题，因为这棵特定的树总是平衡的并提供 O(log2(n)) 操作，但我想在更深层次上达到这一点，试图比需要的更多地优化它。
理论
正如问题的标题所示，我正在尝试优化 AVLTree 并将其与 Btree 合并。 基本上，这个新树的每个节点都可以说是一个包含十个元素的数组，每个节点以及树中的相应高度，并且数组的每个元素都按升序排列。
插入
插入最初填充根节点的数组，当根节点已满时，它生成左右children，其中也包含10个元素的数组。 每当添加新节点时，Tree 都会根据左右向量的第一个键 child 使用它们的高度自动重新平衡节点（请注意，这实际上是 AVLTree 的行为方式，但 AVLTree 只有 2 个节点没有矢量只有值）。
搜索
搜索元素的方式是这样的：从根开始，我们将搜索的值 K 与当前节点数组的第一个和最后一个键进行比较，如果该值介于两者之间，我们知道它肯定会在当前节点的数组中，所以我们可以开始使用具有 O(log2(n)) 复杂度的二进制搜索到这个十个元素的数组中，否则如果我们正在搜索的键更小，那么我们会在左边第一个键，如果它更大，我们就往右走。
删除
与搜索相同，但我们删除了该值。
更新
与搜索相同，但我们更新了值。
结论
如果我没记错的话，这应该有一个 O(log10(log2(10))) 的复杂度，它总是对数的，所以我们不应该关心这个优化，但在我看来，这可能会使高度树小得多，同时也提供了快速的搜索时间。
B树和B+树确实是用来做磁盘存储的，因为是分块设计的。但是没有理由不能将它们也用作 in-memory 数据结构。
B 树的优点包括它在单个节点内使用数组。 Look-up 在可能只有 10 个条目的有限向量中可能非常快。
您在 B 树和 AVL 之间折衷的想法肯定可行，但请注意：
- 您需要像在 AVL 中一样执行树旋转以保持树平衡。在 B 树中，您使用重新分配、合并和拆分，但没有旋转。
- 与 AVL 一样，树不会总是完美平衡。
- 你需要描述当向量已满并需要向其添加值时将执行的操作：节点将不得不分裂，并且一半必须作为叶子重新注入。
- 您需要描述当向量变得非常低 fill-factor（由于删除）时将执行的操作。如果你这样，树可能会退化为 AVL 树，其中每个向量只有 1 个值，然后额外的向量开销将使其效率低于真正的 AVL 树。要使向量的 fill-factor 保持在最小值之上，您不能像在 B-trees 中那样轻松地对兄弟节点应用重新分配机制。它适用于叶节点，但不适用于内部节点。所以这需要澄清...
- 您需要描述更新向量中的值时将执行的操作。当然，你会把它插入到它的排序位置：但如果它成为该向量中的第一个或最后一个值，这可能会违反左右 children 的顺序，因此你可能还需要更精确地定义算法。
- 在 10 的向量中进行二进制搜索可能有点矫枉过正：简单的 left-to-right 扫描可能会更快，因为 CPU 已优化为读取连续内存。这不会影响时间复杂度，因为我们将向量大小设置为 10。所以我们正在谈论最多进行 4 次比较（平均 3-4 次，具体取决于二进制搜索实现）或最多 10 次比较（5平均）。
If I am not wrong this should have a complexity of O(log10(log2(n))) which is always logarithmic
实际上，如果这是真的，它将是 sub-logarithmic，即 O(loglogn)。但是这里有一个错误。向量中的二进制搜索与 n 无关，但与 10 相关。此外，这项工作还 addition 来查找具有该向量的节点.所以不是对数的对数，而是对数的和：
O(log10n + log210) = O(log n)
因此，时间复杂度与 AVL 或 B-tree 的时间复杂度没有区别——前提是该算法完成了缺失的细节，并保持在对数复杂度内。
您也许还应该考虑实现纯 B 树或 B+ 树：这样您还可以从 AVL 和 in-between 结构都没有的一些优势中获益：
- 树的叶子都在同一层
- 不需要旋转
- 树高只在一处发生变化：根。
- B+ 树提供了一种按顺序迭代所有值的非常快速的方法。