0

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

如我所见,订购时:

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

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

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

未订购时:

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

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

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

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

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

谢谢!

4

1 回答 1

1

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

绝对地。这就是 B-tree 系列数据结构背后的理念。它不适用于从/向慢速存储读取/写入部分节点(块)。当需要一个节点时,会将其全部读入内存(如果尚未加载)、操作并完全写回以持久保存它。

由于节点本身对数据的操作发生在内存中,因此选择是否保持节点内容排序并不重要。对较慢(er)存储的读/写操作将更多地决定整体性能。

考虑任何一种选择的时间复杂度也无关紧要,因为节点中的键数量有一个预设的最大值。所以所有的单节点操作都可以被认为具有恒定的时间复杂度。

您可以对不同的实现进行计时,看看是否能做出明确的选择。这种选择将取决于 B 树的程度。

于 2021-11-13T17:06:54.987 回答