B+ Tree Indexing

The B+ Tree is the most widely used index structure in relational databases. PostgreSQL, MySQL (InnoDB), Oracle, SQL Server, and SQLite all use B+ Trees as their default index type.

Understanding B+ Trees is essential for optimizing query performance and for technical interviews.

---

Learning Objectives

After completing this chapter, you will be able to:

• Explain what a B+ Tree is and why databases use it.
• Understand search, insert, and delete operations.
• Differentiate B+ Tree from B-Tree and BST.
• Calculate fan-out and tree height.
• Explain clustered vs non-clustered indexes in terms of B+ Trees.
• Understand page splits and merge.
• Answer B+ Tree interview questions.

---

Why B+ Tree?

Databases store data on disk (not in memory). Disk access is about 100,000x slower than memory access.

A B+ Tree minimizes disk I/O by:

1. High fan-out: Each node can hold hundreds of keys, making the tree very shallow.
2. Nodes = disk pages: Each node fits in one disk page (4KB, 8KB, 16KB).
3. Sequential access: Leaf nodes are linked, enabling efficient range scans.

Fan-out Example

• A B+ Tree with order 100 (200 keys per node).
• With just 3 levels, it can index ~8 million records.
• Any lookup requires only 3-4 disk reads.

---

B+ Tree Structure

A B+ Tree has two types of nodes:

Internal Nodes (Index Nodes)

• Store keys and pointers to child nodes.
• Guide the search to the correct leaf.
• Do NOT store actual data records.

Leaf Nodes (Data Nodes)

• Store keys and pointers to data records (row locations or actual data).
• Leaf nodes at the same level are linked together (doubly linked list) — this enables efficient range scans.

                    Internal Node
               [50 | 100 | 150]
              /      |       |     \
             /       |       |      \
     [10|20|30]  [60|70|80] [110|120] [160|170|180]
        ↓           ↓          ↓          ↓
    (linked leaf nodes for efficient range scans)

---

B+ Tree Properties

Property	Description
Balanced	All leaf nodes are at the same depth
Order (m)	Maximum number of keys per node
Min keys	Internal: ⌈m/2⌉ - 1; Leaf: ⌈m/2⌉
Max keys	m - 1
Children	Internal node with k keys has k+1 children
Leaf link	Leaf nodes have pointers to next/previous leaf

---

Search Operation

Searching in a B+ Tree is similar to searching in a BST, but each node contains multiple keys.

Example: Search for key 110

1. Start at root: [50 | 100 | 150]
   110 > 100 → go to child 3

2. Internal node: [110 | 120]
   110 = first key → go to first child
    
3. Leaf node: [110 | data_pointer]
   Found! Return data.

Number of Disk Reads

Number of reads = height of the tree.

With a fan-out of 200 and 1 million records:

• Height = log200(1,000,000) ≈ 3
• Only 3 disk reads to find any record.

---

Insert Operation

Steps

1. Search: Find the correct leaf node.
2. Insert: Add the key to the leaf node in sorted order.
3. Check overflow: If the leaf has more than m-1 keys, split.

Split

When a node overflows:

1. Create a new node.
2. Distribute the keys evenly (first half stays, second half moves to new node).
3. Push the middle key up to the parent.
4. Insert the middle key into the parent.
5. Recursively check the parent for overflow.

Example: Insert into a B+ Tree with order 5 (max 4 keys)

Before:

Leaf: [10, 20, 30, 40]

Insert 35:

Leaf: [10, 20, 30, 35, 40]  -- Overflow!

Split:

Leaf 1: [10, 20, 30]    Leaf 2: [35, 40]
                          ↑
                    Push 30 to parent

---

Delete Operation

Steps

1. Search: Find the key in the leaf node.
2. Delete: Remove the key.
3. Check underflow: If the leaf has fewer than ⌈m/2⌉ keys:
   • Try to borrow from a sibling.
   • If borrowing is not possible, merge with a sibling.
4. Update parent: Adjust the parent’s key entry after merge.

Merge

When a node underflows and its sibling also has minimum keys:

1. Combine both nodes into one.
2. Remove the separator key from the parent.
3. Recursively check the parent for underflow.

---

B+ Tree vs B-Tree

Feature	B+ Tree	B-Tree
Data pointers	Only in leaf nodes	In all nodes
Leaf links	Yes (linked list)	No
Range scans	Very fast (follow leaf pointers)	Slow (traverse up and down)
Space utilization	Higher (internal nodes store only keys)	Lower (internal nodes store keys + data)
Internal node size	Smaller (no data) → higher fan-out	Larger (has data) → lower fan-out

Why databases prefer B+ Tree:

1. Higher fan-out → shorter tree → fewer disk reads.
2. Range scans are efficient (linked leaves).
3. More keys fit in memory from internal nodes → fewer cache misses.

---

B+ Tree vs BST (Binary Search Tree)

Feature	B+ Tree	BST
Balanced	Always	Only if AVL/Red-Black
Height	log(n) / log(fan-out)	log₂(n)
Node size	Matches disk page	Single key per node
Disk I/O	~3-4 reads for 1M keys	~20 reads for 1M keys
Range scan	Efficient (leaf pointers)	Inefficient (in-order traversal)

BST height: log₂(1,000,000) ≈ 20 disk reads vs B+ Tree: ~3 reads.

---

Clustered vs Non-Clustered B+ Tree

Clustered Index

• The leaf nodes contain the actual data rows.
• There can be only one clustered index per table.
• The table is physically ordered by the clustered key.
• InnoDB’s PRIMARY KEY is a clustered index.

Leaf: [101 | row_data_101] → [102 | row_data_102] → [103 | row_data_103]

Non-Clustered Index

• The leaf nodes contain pointers to data rows (or the clustered key).
• There can be multiple non-clustered indexes per table.
• The table is NOT physically ordered by the index key.

Leaf: [101 | page_pointer_101] → [102 | page_pointer_102]

---

Page Splits

When a B+ Tree node becomes full and a new key is inserted, the node splits.

Impact of Page Splits

• Write overhead: Splitting a page requires allocating a new page, moving 50% of keys, and updating the parent.
• Fragmentation: Pages become only 50% full after a split (until subsequent inserts fill them).
• Random insert issue: Inserting keys in random order causes many splits.

Sequential Inserts

Inserting keys in increasing order (like auto-increment IDs) is optimal:

• Splits happen only at the right edge.
• Most pages remain densely packed.
• Minimum page split overhead.

---

B+ Tree in Practice

Database	Default Index	Details
MySQL (InnoDB)	B+ Tree	Primary key is clustered; secondary indexes reference PK
PostgreSQL	B+ Tree (B-Tree implementation)	All indexes are non-clustered; heap-based storage
Oracle	B+ Tree	Uses B+ Tree for most index types
SQL Server	B+ Tree	Clustered and non-clustered both use B+ Tree
SQLite	B+ Tree	Default index structure

---

Interview Deep Dive

---

Key Takeaways

• B+ Tree is the standard index structure in relational databases.
• High fan-out (many keys per node) makes the tree shallow (~3-4 levels for millions of records).
• Internal nodes guide the search; leaf nodes store data pointers and are linked for range scans.
• Every B+ Tree is balanced — all leaves are at the same depth.
• B+ Tree is preferred over B-Tree for higher fan-out and efficient range scans.
• Clustered indexes store data in leaves; non-clustered indexes store pointers.
• Sequential inserts (auto-increment) minimize page splits and optimize space.
• A B+ Tree query typically requires 3-4 disk reads regardless of data size (for typical fan-out).