B+ Tree Index

Why Not Just Use a Binary Search Tree?

• BST can become unbalanced → O(n) worst case
• Each node holds only 1 key → too many disk I/O operations
• Not optimized for disk storage

B Tree vs B+ Tree

• B Tree: Data stored in ALL nodes (internal + leaf). Range queries are slow.
• B+ Tree: Data stored ONLY in leaf nodes. Internal nodes store only KEYS for routing. Leaf nodes linked as a linked list. Range queries are fast. Used by MySQL, PostgreSQL, Oracle.

B+ Tree Structure

                [ 30 | 60 ]              <- Root (internal)
               /     |     \
        [ 10|20 ]  [40|50] [70|80]       <- Internal nodes
        /   |   \    |  \    |  \
  [5|8][10|15][20|25][35|38][40|55][65|70][75|80|90]   <- Leaf nodes

  Leaf nodes connected as a Linked List (for range queries)

Key Properties

• Internal nodes → store keys ONLY (for routing)
• Leaf nodes → store keys + actual data pointers
• Leaf nodes → connected as a LINKED LIST (critical for range queries)
• All leaves at same depth (always balanced)

Performance

• Point lookup: O(log n) — traverse from root to leaf
• Range query: O(log n + k) — find start point, then traverse linked list

Height Example

Order 500 B+ Tree (500 keys per node)

Level 1 (root) → 500 pointers
Level 2        → 500 × 500 = 250,000 pointers
Level 3 (leaves) → 250,000 × 500 = 125,000,000 rows

Just 3 levels for 125 MILLION rows!
→ Only 3 disk reads to find any record

Clustered vs Non-Clustered Index (Overview)

	Clustered Index	Non-Clustered Index
Data storage	Inside leaf nodes	Separate from index
Per table	Only ONE	Many allowed
Lookup speed	Faster (1 traversal)	Slower (2 traversals)
Range queries	Very fast (data sorted)	Slower (random I/O)
Insert cost	Higher (maintain sort order)	Lower

Indexes and Performance Tradeoffs

• More indexes → faster reads ✅
• More indexes → slower writes ❌ (must update all indexes)
• More indexes → more storage ❌
• Rule of thumb: Index columns used in WHERE, JOIN, ORDER BY. Don't over-index write-heavy tables.