Question:medium

In a relational database, a B+ Tree Index is to be constructed for a relation on a key field. In a B+ Tree, a Node Pointer points to a sub-tree and a Data Record Pointer points to a block of database records.

Let, Node size = 4096 bytes, Node Pointer size = 10 bytes, Search Key Field size = 11 bytes and Data Record Pointer size = 12 bytes.

The maximum number of Node Pointers that can be present in a non-leaf node of the B+ Tree is __________. (Answer in integer)

Show Hint

A non-leaf node with n pointers holds n-1 keys between them; set up the space inequality and solve for the largest integer n.
Updated On: Jul 22, 2026
Show Solution

Correct Answer: 195

Solution and Explanation

A B+ Tree non-leaf node is built like this: pointer, key, pointer, key, and so on, ending in a pointer. If there are $n$ pointers, there must be exactly $n - 1$ keys sitting between them to guide the search. The Data Record Pointer size given in the question is a distractor here, since that field only matters inside leaf nodes, not non-leaf nodes.

Let $n$ be the number of Node Pointers we are trying to find. The total bytes used by the node is

\[ \underbrace{10n}_{\text{pointers}} + \underbrace{11(n-1)}_{\text{keys}} \]

and this has to stay within the 4096-byte node size:

\[ 10n + 11(n - 1) \le 4096 \]

Expand and collect terms:

\[ 10n + 11n - 11 \le 4096 \] \[ 21n \le 4107 \] \[ n \le \frac{4107}{21} = 195.571\ldots \]

Since $n$ has to be a whole number of pointers, round down to $n = 195$.

Double check: with $195$ pointers there are $194$ keys, using $195(10) + 194(11) = 1950 + 2134 = 4084$ bytes, safely under the 4096 limit. Bumping up to $196$ pointers would need $196(10) + 195(11) = 1960 + 2145 = 4105$ bytes, which overshoots the node size by 9 bytes. So 195 is indeed the maximum.

\[ \boxed{n = 195} \]
Was this answer helpful?
0