Test: B+ Tree - Computer Science Engineering (CSE) MCQ

In a B+ -tree, only the leaves have keys, and these keys are replicated in non-leaf nodes for defining the path for locating individual records.

Maximum number of pointers in a node is 7, i.e. the order of the B+ -tree is 7. In a B+ tree of order n each leaf node contains at most n – 1 key and at least ⌈(n − 1)/2⌉ keys. Therefore, a minimum number of keys each leaf can have = ⌈(7 – 1)/2⌉ = 3.

In a B+ -tree of order 3 every non-root node has at most 2 keys.
After inserting 89 the tree formed will be, 

After inserting 9

After inserting 8, the node will get overflowed so we split the node and create a new root with key 9. So, the tree formed will be 

In a B+ -tree finding the next recored (successor) involves accessing an additional leaf at most. So, the efficiency of finding the next record is O(1).

A B+ -tree has larger fanout and therefore have a depth smaller than that of corresponding B-tree.

The B+ -tree being a variation of B-tree allows rapid random access. In a B+ -tree the leaves are linked together, so it also provides rapid sequential access.

A B+ -tree always grows upwards. And In a B+tree – i)The path from the root to every leaf node is of the same length, so the tree is balanced. ii) Leaves are linked, so allow sequential searching. iii) An index is built with a single key per block of data rather than with one key per data record, so it is shallower than B-tree.

During the split, the middle key is retained in the right half node and also promoted to parent node. When a key is deleted from the leaf, it is retained in non-leaves, because it can be still a valid separator between keys in nodes below.

 A B+ tree of order n and height h can have at most nh – 1 keys. Therefore maximum number of keys = 33 -1 = 27 -1 = 26.

The database-system implementations use B+ -tree data structure because they can be used for multilevel indexing.