Skip to content
THE CS NOTES

B+ Tree in DBMS

B+ Tree – Question Oriented Notes (Improved & Corrected)

What is B+ Tree? B+ Tree is a height-balanced multi-level indexing data structure used in DBMS for efficient disk-based storage and retrieval. It is a variant of B-Tree where all actual data pointers (record pointers) are stored only at the leaf level, while internal nodes store only keys for navigation.

Why B+ Tree is used in DBMS? Databases reside on secondary storage where disk I/O is costly. B+ Tree reduces disk I/O by:

  • Very high fanout (many children per node)
  • Very small height
  • Efficient equality and range queries due to sorted leaves

Basic Properties (Very Important) All keys are stored in sorted order All leaf nodes are at the same level (height-balanced) Internal nodes contain only keys and child pointers Leaf nodes contain keys and record pointers Leaf nodes are linked sequentially High fanout results in low tree height

Structure of B+ Tree (Frequently Asked)

Root Node Topmost node of the tree Contains keys and child pointers Can act as a leaf if the tree has only one node Minimum children: 2 (unless it is a leaf)

Internal Nodes Contain search keys and child pointers Do not contain record pointers Used only for guiding the search Keys act as separator values

Leaf Nodes Contain search keys and record pointers (or data block pointers) All actual data references are stored only at leaf level Leaf nodes are connected using next pointers Support sequential access and range queries

Diagram (Logical Structure)

       [ 20 | 40 ]
      /     |      \
 [5|10]  [20|30]  [40|50|60]

All leaf nodes are linked: [5|10] → [20|30] → [40|50|60]

Order of B+ Tree Order (m) = maximum number of children of an internal node Maximum children = m Maximum keys in internal node = m − 1 Minimum children (except root) = ceil(m / 2) Minimum keys = ceil(m / 2) − 1

Node Size and Capacity (Numerical Questions) Each node fits in exactly one disk block Block size = B bytes Key size = K bytes Pointer size = P bytes

Internal Node Entry Contains key + child pointer

Internal Node Size Constraint p pointers, each = P bytes (p − 1) keys, each = K bytes

Size condition: p·P + (p − 1)·K ≤ B

Maximum pointers (fanout) = maximum p satisfying constraint Maximum keys = p − 1

Leaf Node Entry Key + record pointer (Pr)

Leaf Node Capacity Maximum entries = floor(B / (K + Pr))

Fanout (Very Important for Numericals) Fanout = number of children of an internal node Determines height of the tree Higher fanout ⇒ smaller height ⇒ fewer disk accesses Depends on block size, key size, pointer size

Height of B+ Tree (Numerical + Theory) Height = number of index levels from root to leaf

If R = number of records Leaf capacity = L

Number of leaf nodes ≈ ceil(R / L)

If fanout = f Height ≈ ⌈log_f (number of leaf nodes)⌉

Search Operation (Common Question) Start from root At each internal node, compare keys Follow the appropriate child pointer Reach leaf node Access record using record pointer

Search Example Search key = 35 Root [20|40] → middle child Leaf [20|30] → key not found

Disk Access Cost (Very Important) Each index level requires one disk access Accessing data block requires one disk access

Total Disk Accesses = Height + 1

Example Height = 3 Total disk accesses = 3 (index) + 1 (data) = 4

Insertion in B+ Tree Find appropriate leaf node Insert key in sorted order If no overflow, stop If overflow occurs:

  • Split the leaf node
  • Copy first key of new right leaf to parent
  • Maintain leaf-level linked list Splitting may propagate upward If root splits, create a new root

Insertion Example Leaf capacity = 3 Insert: 10, 20, 30, 40 Overflow after 40 Split into [10|20] and [30|40] Promoted key = 30

Deletion in B+ Tree Delete key from leaf If node has minimum required keys, stop If underflow occurs:

  • Try redistribution from sibling
  • Else merge with sibling Update parent separator keys May propagate upward Tree remains height-balanced

Ordered Index vs Clustered Index (Conceptual Trap)

Ordered Index Keys are stored in sorted order Supports range queries Can be primary or secondary All B+ Trees are ordered indexes

Clustered Index Data records stored in same order as index keys Leaf nodes store actual data records Only one clustered index per table

Primary Index vs Secondary Index

Primary Index Index on primary key Usually implemented as clustered B+ Tree Leaf nodes contain actual data records

Secondary Index Index on non-primary key Implemented as non-clustered B+ Tree Leaf nodes contain key–record pointer pairs Multiple secondary indexes allowed

Important Clarification (Very Important) B+ Tree does not imply clustered index B+ Tree only ensures sorted keys Clustered or non-clustered depends on leaf node contents

Advantages of B+ Tree Always balanced Low height due to high fanout Minimizes disk I/O Efficient point and range queries Fast sequential access Standard indexing structure in DBMS

Disadvantages of B+ Tree Insertion and deletion are complex Extra space overhead due to pointers Frequent updates are costly compared to static indexes

Exam Tips Numericals mostly depend on fanout and height Always compute node capacity first Height questions use log base fanout Disk access questions usually = height + 1 Ordered index ≠ clustered index

Ques Consider a database implemented using B+ tree for file indexing and installed on a disk drive with block size of 4KB . The size of search key is 12 bytes and the size of tree/disk pointer is 8 bytes . Assume that the database has one million records. Also assume that no node of the B+ tree and no records are present initially in main memory. Consider that each record fits into one disk block. The minimum number of disk accesses required to retrieve any record in the database is __________

Solution:

  • Block size = 4096 bytes
  • One index entry = 12 (key) + 8 (pointer) = 20 bytes
  • Entries per node ≈ 4096 / 20 ≈ 204 → fanout ≈ 204
  • Leaf entries = 1,000,000 → leaf nodes ≈ 1,000,000 / 204 ≈ 4902
  • 204² = 41616 > 4902 → tree height = 3 (root + internal + leaf)
  • Disk accesses: root (1) + internal (1) + leaf (1) + data block (1)
  • Minimum disk accesses = 4

Explanation Think of a B+ tree as a multilevel index kept on disk. To find a record, the database starts from the root node, then goes down level by level until it reaches a leaf node, and finally accesses the data block that contains the actual record. Each of these steps needs one disk access, because initially nothing is in main memory.

Each node of the B+ tree must fit inside one disk block of size 4096 bytes. Every entry in an index node consists of a search key (12 bytes) and a pointer (8 bytes), so one entry takes 20 bytes. This means one B+ tree node can store about 4096 / 20 ≈ 204 entries. Hence, from any node, the tree can branch to roughly 204 child nodes. This is called the fanout of the tree.

The database has 1,000,000 records, and each leaf entry can point to only one record. Since each leaf node can hold about 204 entries, the total number of leaf nodes required is 1,000,000 / 204 ≈ 4902 leaf blocks. Now, starting from the root, one level of pointers can reach 204 nodes, and two levels can reach 204 × 204 = 41616 nodes, which is already more than the required 4902 leaf nodes. So the B+ tree needs three levels in total: the root, one internal level, and the leaf level.

To retrieve a record, the database performs one disk access for the root, one for the internal node, and one for the leaf node. After reaching the leaf, one more disk access is needed to fetch the actual data block, because the record itself is stored separately. Therefore, the minimum number of disk accesses required is 4.