问题标签 [b-plus-tree]

我有关于我的作业的问题：

1）首先，假设4个指针可能适合一个内部节点，每个叶子节点可以存储4个键值，B+树应该用以下值构造：

2、3、5、7、11、17、19、23、29、31。

通过该站点，我收到了下面的树。我不确定它是否正确，因为在叶子节点中，可能有三个键值：

问题从插入和删除开始。因此插入 9、10、8，我收到了下面的树：

但是当我删除 23 时，我描述如下。问题是，19 不能独自一人，因为叶子必须是半满的：

之后删除 19 会出现同样的问题：

问题是：

1）初始树是否正确？

2）我对删除的假设是否正确？

3) 删除后的树必须如何相似？

带着敬意。

在 Database System Concepts，第 6^版，第 11 章，“图 11.11 查询 B+-树”中，有一个procedure printAll(value V). 它用于打印搜索键值为V的所有记录（可以有重复）。它调用，它返回具有键Vfind(V)的第一个叶节点，以及该叶中具有该键的第一个索引i。

为什么代码不包含Set i = 1when i > number of keys in L？

procedure printAll( value V )
    /* 打印搜索键值为V的所有记录*/
    Set done = false;
    设置 ( L,i ) = 查找( V );
    if (( L,i ) 为空) return
    repeat
        repeat打印LP _i
            指向的记录             Set i = i + 1 until ( i > L中的键数或L.K _i > V ) if ( i > 中的键数

       
        L )
            then L = LP _n // 不需要将i设置为 1？
            否则设置完成=真；
    直到（完成或L为空）

我查看了GitHub 上 JavaScript 中B+树的每个示例，并尝试将其中的一个简化为半可读的代码。但是我仍然不明白keys每个内部节点的数组结构是什么。钥匙长什么样？您如何在 get/insert/remove 算法中使用它们？特别是对于这个问题，我想将 B+tree 视为外部数组或排序列表。所以我希望“键”是一个整数（数组中项目的索引）。我该怎么做呢？什么是示例 JSON 演示，显示在这种情况下简单的 B+树会是什么样子？

钥匙还能做什么？我知道它们以某种方式用于查找，但是如何？

假设基地有 32 个内部节点，每个内部节点都有 32 个内部节点，每个内部节点都有一堆叶子。内部节点中的键是什么？

我想在 JavaScript 中实现一个健壮的 B+树，现在很难理解 B+树的基础知识。

我正在尝试遍历 B+ 树并将叶子中的元素添加到 ArrayList 中，代码如下：

它的作用是检查节点是内部节点还是叶节点的实例。如果它是一个内部节点，它会递归地调用它的每个子节点的函数。如果它是叶节点，那么它会将值添加到 ArrayList 中。然而，在运行这个功能时，我最终得到了一个java.lang.OutOfMemoryError.

有没有办法让我的代码更有效率，或者我应该采取不同的方法来处理这种方法？

我有一个包含 10M 叶子的 B+ 树索引。我知道内存中的一个块大小是 4KB，而 RAM 也是 4KB。如何计算最大和最小内存使用量是多少？

另外，我怎么知道分配给索引的实际存储空间是多少？

谢谢

在我的 B+Tree 中，我在叶级排序了键，数据指针指向一个单独的数据文件。这个问题是指这个数据文件中的数据顺序。

如我所见，订购时：

• 读取块时更容易加载块中的所有数据，因为数据的存储顺序与其键相同，因此您只需检查相邻的数据指针是否在同一块中。

• 访问大量相邻数据或执行范围时读取次数较少，因为数据更有可能包含在同一块中。

• 删除/拆分/插入时增加的碎片和写入

未订购时：

• 插入时减少写入，因为数据只是附加到与节点关联的最后一个块的末尾。

• 执行范围时增加读取，因为数据不太可能在多个块之间拆分。

• 在同一块中查找其他数据所属的条目要慢得多，因为您必须遍历节点中的所有条目来检查它们的数据指针。

或者，当我需要从该节点内的条目访问数据时，是否应该将整个节点加载到内存中？

寻找关于我应该存储数据（有序/无序）的最佳方式的第二种选择，以及在对一个值执行简单的“获取”时应该加载多少个数据指针？

谢谢！