Part 3: B+ -Tree Indexing — The Backbone of Fast Database Searches

What Is a B+ -Tree?

A B+ -Tree is a self-balancing, multilevel index structure optimized for read-heavy operations. Unlike basic index-sequential files, it avoids performance degradation as the file grows by maintaining balance and uniform depth.

Each path from root to leaf in a B+-Tree is the same length, making it a balanced tree, and thus predictable in performance even with insertions and deletions

Structure of a B+-Tree

Leaf Nodes

Example: Leaf Node (n = 4)

Suppose we’re indexing student IDs:

Leaf: [101 | 105 | 109] → [next leaf]

• The leaf node stores 3 keys: 101, 105, 109
• Each key points to the actual record in the table (not shown here)
• The → [next leaf] pointer connects to the next leaf node for range scanning

So if we run:

SELECT * FROM students WHERE student_id BETWEEN 101 AND 109;

→ The B+-Tree will find the leaf starting with 101 and follow the keys and next-leaf pointer if needed.

Nonleaf (Internal) Nodes

• Serve as a sparse index on leaf nodes
• Contain only keys and pointers to child nodes (not actual data)
• It helps you navigate the tree, like a signpost: “If your key is less than X, go left; if between X and Y, go middle; if greater than Y, go right.”

Example: Internal Node With n = 4

Assume:

• Max 3 keys per internal node (because n = 4)
• The internal node stores:

[20 | 50 | 80]

This node has 4 pointers:

P1    P2    P3    P4
 |     |     |     |
 ↓     ↓     ↓     ↓

Routing rules:

P1 → keys < 20

P2 → keys ≥ 20 and < 50

P3 → keys ≥ 50 and < 80

P4 → keys ≥ 80

Search Example

Suppose you’re searching for key 45:

1. Start at the root node:

[20 | 50 | 80]

2. Since 45 is ≥ 20 and < 50, you follow P2

3. That takes you to a leaf node where 45 might exist

Now if you’re searching for 81, you’ll go to P4, because it's ≥ 80.

B+ -Tree Construction Example (n = 4)

Let’s build a B+-Tree by inserting these keys in order:

[2, 3, 5, 7, 11, 17, 19, 23, 29, 31]

We assume n = 4, so each node can hold up to 3 keys and 4 pointers.

Step-by-Step Breakdown:

1. Insert 2, 3,5

[2 | 3 | 5]

Just one leaf node. Still under the limit.

2. Insert 7

• Leaf now has 4 keys → needs to split
• Split into two nodes:

[2 | 3]      [5 | 7]

• A new root node is created to point to both leaves:

Root: [5]

3. Insert 11, 17

• Goes into the right leaf:

[2 | 3]     [5 | 7 | 11 | 17]

• Right leaf overflows → split:

[5 | 7]     [11 | 17]

• Root gets updated:

Root: [5 | 11]

4. Insert 19, 23

• Goes to rightmost leaf:

[11 | 17 | 19 | 23]

• Overflows → split into:

[11 | 17]     [19 | 23]

• Root becomes:

Root: [5 | 11 | 19]

5. Insert 29, 31

• Goes to rightmost leaf. No split needed yet.

Final B+ -Tree Structure:

Root:

[5 | 11 | 19]

Leaf Level (Linked Left to Right):

[2 | 3] → [5 | 7] → [11 | 17] → [19 | 23 | 29 | 31]

Key Takeaways from B+ -Tree Construction

• Nodes split automatically when they exceed capacity
• The tree remains balanced, ensuring consistent performance
• Leaf nodes are linked in order — perfect for efficient range queries
• The root grows upward, increasing the tree’s height only when necessary
• Lookup, insertion, and deletion all happen in logarithmic time

Bulk Loading Optimization

Instead of inserting one-by-one, bulk loading:

1. Sorts entries
2. Constructs the leaf level first
3. Builds internal nodes above

This saves time and disk I/O, especially when building an index for millions of records

Why Use B+ -Trees?

• Handles growing data without full reorganization
• Excellent for range-based queries
• Efficient disk I/O due to high fanout (shallow depth)
• Well-suited for both indexing and file organization

Real-World Use Case: Instructor Name Lookup

Suppose your database of instructors has a B+-Tree index on the name field.

Now, you run this query:

SELECT * FROM instructor WHERE name BETWEEN 'Amit' AND 'Avinash';

What the B+ -Tree Does:

1. It navigates directly to the first leaf node where name ≥ 'Amit'
2. Then, it scans forward through the linked leaf nodes in order
3. It stops at ‘Avinash’, retrieving all matching records in that range

Much faster than scanning the whole table — especially when names are indexed alphabetically.

The B+-Tree is one of the most widely used index structures in modern databases. Its balanced and multi-level structure enables efficient searching, insertion, and deletion — all in logarithmic time. Leaf nodes are linked sequentially, making B+-Trees especially effective for range-based queries. They scale well with large datasets, support bulk loading, and are a critical part of how databases keep queries fast and storage efficient