In a B+ tree, the order of a node is the maximum number of entries (search…

2013

In a B+ tree, the order of a node is the maximum number of entries (search keys) it can hold within one disk block. Using the parameters below, calculate the order of a leaf node (pleaf) and of a non-leaf / internal node (p). A leaf node stores (search key + record pointer) entries; an internal node stores search keys with their separating block pointers.

  • Search key field = 12 bytes

  • Record pointer = 10 bytes

  • Block pointer = 8 bytes

  • Block size = 1 KB = 1024 bytes

  1. A.

    pleaf = 51 & p = 46

  2. B.

    pleaf = 47 & p = 52

  3. C.

    pleaf = 46 & p = 50

  4. D.

    pleaf = 52 & p = 47

Attempted by 134 students.

Show answer & explanation

Correct answer: C

Concept

In a B+ tree the order of a node is fixed by requiring one node to fit inside a single disk block. The two node types store different things: a leaf node holds data entries, each = (search key + record pointer), plus one trailing block pointer that chains to the next leaf; a non-leaf / internal node holds only search keys and block pointers (no record pointers, because data lives only in the leaves). So you size each node by adding up the bytes of what it actually stores and keeping the total within the block size.

Application

Given: search key = 12 B, record pointer = 10 B, block pointer = 8 B, block size = 1024 B.

Leaf node order (pleaf): each entry = key + record pointer = 12 + 10 = 22 B, and a leaf keeps one extra block pointer (8 B) to link to its sibling:

  1. pleaf x 22 + 8 ≤ 1024

  2. pleaf x 22 ≤ 1016

  3. pleaf ≤ 1016 / 22 = 46.18

  4. Take the floor: pleaf = 46.

Non-leaf (internal) node order (p): here p is the number of search keys; a node holding p keys needs (p + 1) block pointers to separate its children, and the official sizing keeps this within one block:

  1. 12 x p + 8 x (p + 1) ≤ 1024

  2. 12p + 8p + 8 ≤ 1024

  3. 20p ≤ 1016

  4. p ≤ 1016 / 20 = 50.8

  5. Take the floor: p = 50.

Cross-check / contrast

Confirm each count is the largest that still fits one 1024-byte block:

  • pleaf = 46: 46 x 22 = 1012 B (+8 B sibling link = 1020 B ≤ 1024); 47 entries would need 1034 B — overflow.

  • p = 50: with 50 search keys and 51 block pointers, 50 x 12 + 51 x 8 = 600 + 408 = 1008 B ≤ 1024; 51 keys (with 52 pointers) would need 1028 B — overflow.

  • Sanity check on the asymmetry: a leaf entry (22 B) is heavier than an internal-node key slot (12 B paired with an 8 B pointer), so the leaf holds fewer entries than the internal node — any answer that swaps the two values fails this check.

Result: pleaf = 46 and p = 50.

Explore the full course: Isro