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

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

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

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 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.

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 has larger fanout and therefore have a depth smaller than that of corresponding B-tree.

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).

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.

Properties of B+ trees:

• B+ tree is height balance tree.
• Non leaf node has pointer to a node (leaf or non-leaf) and not pointer to data record
• Key value in each node is in sorted order.
• Leaf node has pointer to next leaf node.

Structure of non-leaf(internal) node of B+ tree:

Structure of leaf of B+ tree:

Option b is not correct.

A clustered index is when a file is organized so that ordering of the data records is the same as or close to the ordering of data entries in the index.  Alternative 1 by definition is clustered.  An index that uses Alternative2 or3 can be a clustered index only if the data records are sorted on the search key field.
A clustered index offers much better range query performance, but essentially the same equality search performance (modulo duplicates) as an unclustered index. Further, a clustered index is typically more expensive to maintain than an unclus­tered index. Therefore, we should make an index be clustered only if range queries are important on its search key. At most one of the indexes on a relation can be clustered, and if range queries are anticipated on more than one combination of fields, we have to choose the combination that is most important and make that be the search key of the clustered index.