GATE CS 2015 Set 3 Q.56 (CS Q.46): File Organization, B-Trees and B+ Trees Indexing

Consider a B+ tree in which the search key is 12 bytes long, block size is 1024 bytes, record pointer is 10 bytes long and block pointer is 8 bytes long. The maximum number of keys that can be accommodated in each non-leaf node of the tree is _____.

Your answer

Official answer and solution

Official answer: 50
From: Official GATE 2015 answer key

Solution

Formulate the node size inequality for non-leaf B+ tree nodes and solve for the maximum number of keys.

In a B+ tree, a non-leaf (internal) node of order $p$ contains:

$p$ block pointers (each pointing to a child node)
$p - 1$ search key values (record pointers are stored only in leaf nodes)

Given sizes:

Block size $= 1024\text{ bytes}$
Search key size $= 12\text{ bytes}$
Block pointer size $= 8\text{ bytes}$

The total size of a non-leaf node must not exceed the block size:

p \times (\text{block pointer}) + (p - 1) \times (\text{search key}) \le \text{block size}

p \times 8 + (p - 1) \times 12 \le 1024

8p + 12p - 12 \le 1024

20p \le 1036 \implies p \le \frac{1036}{20} = 51.8

Since the order $p$ must be an integer, the maximum order is $p = 51$ .
The maximum number of search keys accommodated in each non-leaf node is:

\text{Maximum keys} = p - 1 = 51 - 1 = 50

Final answer

Common trap

Including record pointers in non-leaf nodes, which are only present in leaf nodes in a B+ tree.

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2015 Computer Science and Information Technology (CS) Session 3
Question: 56 of 65, printed as CS Q.46
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source