B+ Tree Indexing

Why databases need indexes

A table with 10 million rows stored on disk. To find roll_no = 2023117, scanning every row could take seconds. An index lets the database jump almost straight to it — like the index at the back of a book.

Most relational databases (MySQL InnoDB, PostgreSQL, SQL Server, Oracle, SQLite) build their indexes as B+ trees.

The structure

A B+ tree of order m is a balanced search tree where:

• every node holds up to m − 1 sorted keys (in the 3D model, m = 4 → up to 3 keys),
• inner nodes hold only keys that guide the search, plus child pointers,
• leaves hold all the keys (and pointers to the actual table rows),
• all leaves are at the same depth, and
• leaves are linked left-to-right.

Why “wide” nodes? Reading one block from disk takes about as long as reading many keys. So each node is sized to fill a disk block (e.g. 4–16 KB → hundreds of keys). With 200 keys per node, a tree of height 3 can index 200³ = 8 million rows in just 3 disk reads.

Search

Start at the root. In each node, find the child whose key range contains the search key and follow it. At the leaf, look for the key. Cost: the tree height — O(log n).

Insertion and splits

1. Search for the correct leaf and insert the key in sorted order.
2. If the leaf now has too many keys (overflow), split it into two halves and copy the first key of the right half up into the parent.
3. If the parent overflows, split it too — but this time the middle key moves up (it isn’t kept in either half).
4. If the root splits, create a new root. The tree grows upward, so all leaves always stay at the same depth — the tree is always balanced.

Insert 80, 90 and 100 in the model to see a leaf split, then a root split.

Range queries

“Find all students with marks between 60 and 80”: search for 60 to reach the first leaf, then follow the leaf links to the right, collecting keys until one is greater than 80. No need to go back up the tree — O(log n + k).

B tree vs B+ tree

Code (search in Python)

class Node:
    def __init__(self, keys, children=None, next_leaf=None):
        self.keys = keys                # sorted
        self.children = children or []  # empty for leaves
        self.next = next_leaf           # leaf chain

def search(node, key):
    reads = 1
    while node.children:                # inner node
        i = 0
        while i < len(node.keys) and key >= node.keys[i]:
            i += 1
        node = node.children[i]
        reads += 1
    return key in node.keys, reads

def range_query(root, lo, hi):
    node = root
    while node.children:
        i = sum(1 for k in node.keys if lo >= k)
        node = node.children[i]
    out = []
    while node:
        for k in node.keys:
            if k > hi:
                return out
            if k >= lo:
                out.append(k)
        node = node.next                # follow the leaf link
    return out

In SQL you never build the tree yourself — you ask for it:

CREATE INDEX idx_marks ON students(marks);
SELECT * FROM students WHERE marks BETWEEN 60 AND 80;   -- uses the B+ tree

Common mistakes

• Confusing B trees (data in every node) with B+ trees (data only in leaves).
• Forgetting that leaf splits copy the separator up but inner splits move it.
• Thinking more indexes are always better — every index must be updated on every insert, slowing writes.