Why is B+-tree preferred over fibonacci heap in database-system implementation?

Question

Is there a particular reason the B+-tree is preferred, when implementing a larger scale database-system, over the Fibonacci heap? From the complexity analysis in the image it would seem that Fibonacci heap is faster.

Answer 1

A B+ tree is a search tree and not a heap. The image is not comparing a Fibonacci heap with a B+ tree, but with a binary heap.

Comparing heap and search tree

A heap is a data structure that provides a lazy order, i.e. to get the i^th value in sorted order, you will have to alter the heap as you pop values from it. This is true for both heap implementations in the image you shared.

A search tree has a stronger focus on order. You can iterate its values in order in O(n) time without making any change to the tree. For a heap that would amount to O(nlogn), as you would need n extract-min operations, and the heap loses the values you extract from it.

You wrote:

Is there a particular reason the B+-tree is preferred, when implementing a larger scale database-system

A heap is not a useful data structure for indexing data in database systems, as the order is not known without alteration, and the nodes, when read in ordered sequence, are scattered at different disk locations.

A search tree is a better fit for this purpose. Among search trees, those that go well with larger block sizes are interesting choices for databases that have their data on relatively slower disks. A B-tree is such an example. B+-trees have as advantage over B-trees that they store values in order within linked leaf-blocks, so that they optimise on ordered iteration, while B-trees take a little bit less space than B+-trees.

Comparing binary heap and Fibonacci heap

The difference in time complexity between a binary heap and Fibonacci heap could be a factor to go with the Fibonacci heap. But as a Fibonacci heap has larger overhead, the gain would only appear for larger data sets. On Wikipedia it says:

Although Fibonacci heaps look very efficient, they have the following two drawbacks (as mentioned in the paper "The Pairing Heap: A new form of Self Adjusting Heap"):

"They are complicated when it comes to coding them. Also they are not as efficient in practice when compared with the theoretically less efficient forms of heaps, since in their simplest version they require storage and manipulation of four pointers per node, compared to the two or three pointers per node needed for other structures ".

These other structures are referred to Binary heap, Binomial heap, Pairing Heap, Brodal Heap and Rank Pairing Heap.

Although the total running time of a sequence of operations starting with an empty structure is bounded by the bounds given above, some (very few) operations in the sequence can take very long to complete (in particular delete and delete minimum have linear running time in the worst case). For this reason Fibonacci heaps and other amortized data structures may not be appropriate for real-time systems.