在实现更大规模的数据库系统时，是否有特定的原因首选 B+-树而不是斐波那契堆？从图像中的复杂性分析来看，斐波那契堆似乎更快。
问问题
215 次
1 回答
0
B+ 树是搜索树而不是堆。该图像不是将斐波那契堆与 B+ 树进行比较，而是与二叉堆进行比较。
比较堆和搜索树
堆是一种提供惰性顺序的数据结构，即要按排序顺序获取第i个值，您必须在从中弹出值时更改堆。这对于您共享的映像中的两个堆实现都是如此。
搜索树更注重顺序。您可以在O(n)时间内按顺序迭代其值，而无需对树进行任何更改。对于相当于O(nlogn)的堆，因为您需要n 个 extract-min操作，并且堆会丢失您从中提取的值。
你写了：
在实现更大规模的数据库系统时，是否有特定的原因首选 B+-tree
堆不是用于在数据库系统中索引数据的有用数据结构，因为不更改顺序是不知道的，并且当按有序顺序读取时，节点分散在不同的磁盘位置。
搜索树更适合此目的。在搜索树中，那些与较大块大小配合得很好的搜索树对于将数据存储在相对较慢的磁盘上的数据库来说是有趣的选择。B树就是这样一个例子。B+-trees 比 B-trees 的优势在于它们在链接的叶块中按顺序存储值，因此它们在有序迭代上进行优化，而 B-trees 比 B+-trees 占用更少的空间。
比较二叉堆和斐波那契堆
二元堆和斐波那契堆之间的时间复杂度差异可能是斐波那契堆的一个因素。但由于斐波那契堆具有更大的开销，增益只会出现在更大的数据集上。在维基百科上它说：
虽然 Fibonacci 堆看起来非常高效，但它们有以下两个缺点（如论文“The Pairing Heap: A new form of Self Adjusting Heap”中所述）：
“在对它们进行编码时，它们很复杂。与理论上效率较低的堆形式相比，它们在实践中的效率也不高，因为在最简单的版本中，与两个相比，它们需要每个节点存储和操作四个指针或其他结构所需的每个节点三个指针“。
这些其他结构称为二叉堆、二项堆、配对堆、布罗达尔堆和等级配对堆。
尽管以空结构开始的一系列操作的总运行时间受上面给出的界限的限制，但序列中的一些（很少）操作可能需要很长时间才能完成（特别是 delete 和 delete minimum 在最坏的情况）。由于这个原因，斐波那契堆和其他摊销数据结构可能不适合实时系统。
于 2020-11-02T10:52:15.570 回答