GATE CS 2017 Set 2 Q.49 (CS Q.49): File Organization, B-Trees and B+ Trees Indexing

In a B+ tree, if the search-key value is 8 bytes long, the block size is 512 bytes and the block pointer size is 2 bytes, then the maximum order of the B+ tree is

Your answer

Official answer and solution

Official answer: 52
From: Official GATE 2017 answer key

Solution

Set up the node capacity inequality for internal nodes of a B+ tree where order $p$ is the maximum number of block pointers.

In a B+ tree of order $p$ , an internal node contains:

At most $p$ block pointers (each of size $P = 2$ bytes).
At most $p - 1$ search-key values (each of size $K = 8$ bytes).

The total size of an internal node must fit within one disk block ( $B = 512$ bytes):

p \cdot P + (p - 1) \cdot K \le B

Substitute the given parameters:

p \times 2 + (p - 1) \times 8 \le 512

2p + 8p - 8 \le 512

10p \le 520

p \le 52

Therefore, the maximum order of the B+ tree is 52.

Final answer

Common trap

Using $p \cdot K + (p - 1) \cdot P \le 512$ by swapping the key and pointer counts.

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

Source

Paper: GATE 2017 Computer Science and Information Technology (CS) Session 2
Question: 49 of 65, printed as CS Q.49
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