DBMS

Storage And Indexing

B+ Tree Indexes

The DSA Notes presented the BST as the standard ordered structure. On disk it is close to useless, and the reason is Chapter 1's cost model.

JrCodex·8 min read

Jr Codex DBMS Notes

Level: Intermediate Prerequisites: Chapter 1: How a Database Stores Data; DSA Notes, Module 7, Chapter 3 Time to complete: ~25 minutes

Table of Contents

  1. Why Not a Binary Search Tree
  2. The B+ Tree Shape
  3. Why It Is So Shallow
  4. Searching
  5. Range Scans and the Leaf Chain
  6. Insertion and Splitting
  7. What This Costs You
  8. Summary & Next Steps

1. Why Not a Binary Search Tree

The DSA Notes presented the BST as the standard ordered structure. On disk it is close to useless, and the reason is Chapter 1's cost model.

The Arithmetic
─────────────────────────────────────────
  10,000,000 rows.

  BALANCED BST
    height = log₂(10,000,000) ≈ 24
    Each node is small and lives on its own page.
    A lookup = 24 RANDOM PAGE READS.
    24 × 100µs ≈ 2.4 ms

  B+ TREE with 400 keys per node
    height = log₄₀₀(10,000,000) ≈ 3
    A lookup = 3 page reads.
    3 × 100µs ≈ 0.3 ms

  Eight times fewer reads, from the same O(log n)
  — because the LOGARITHM BASE changed.
─────────────────────────────────────────

The Insight
─────────────────────────────────────────
  A page read costs the same whether you use 16
  bytes of it or 8,192.

  A binary node wastes almost the entire page. So
  make the node AS BIG AS A PAGE and give it
  hundreds of children.

  Height collapses. That is the whole idea.
─────────────────────────────────────────

2. The B+ Tree Shape

Structure
─────────────────────────────────────────
              ┌───────────────┐
   ROOT       │  30  |  60    │        internal:
              └───┬───┬───┬───┘        KEYS + child
                  │   │   │            pointers only
        ┌─────────┘   │   └─────────┐
        ▼             ▼             ▼
   ┌─────────┐   ┌─────────┐   ┌─────────┐
   │ 10 | 20 │   │ 40 | 50 │   │ 70 | 80 │   internal
   └──┬───┬──┘   └──┬───┬──┘   └──┬───┬──┘
      ▼   ▼         ▼   ▼         ▼   ▼
   ┌────┐┌────┐  ┌────┐┌────┐  ┌────┐┌────┐
   │10→ ││20→ │→ │40→ ││50→ │→ │70→ ││80→ │   LEAVES:
   │data││data│  │data││data│  │data││data│   keys + row
   └────┘└────┘  └────┘└────┘  └────┘└────┘   pointers
     └──────┴───────┴──────┴───────┴─────┘
        LINKED LIST across all leaves
─────────────────────────────────────────

The Three Defining Properties
─────────────────────────────────────────
  1. ALL DATA POINTERS ARE IN THE LEAVES.
     Internal nodes hold only keys for navigation.
     So internal nodes fit MORE keys, so the tree
     is shallower. (This is the "+" in B+ tree; a
     plain B-tree stores data in internal nodes
     too.)

  2. LEAVES ARE LINKED.
     A doubly-linked list in key order. This is
     what makes range scans fast (Section 5).

  3. PERFECTLY BALANCED.
     Every leaf is at the same depth, always. Every
     lookup costs exactly the height — no worst
     case, unlike an unbalanced BST.
─────────────────────────────────────────

3. Why It Is So Shallow

PAGE_SIZE   = 8192
KEY_BYTES   = 8          # a BIGINT key
PTR_BYTES   = 8          # a child pointer
HEADER      = 64
 
fanout = (PAGE_SIZE - HEADER) // (KEY_BYTES + PTR_BYTES)
print(f"fanout ≈ {fanout} children per node")        # ≈ 508
 
for height in range(1, 5):
    print(f"height {height}: up to {fanout ** height:,} keys")
# height 1:             508
# height 2:         258,064
# height 3:     131,096,512
# height 4:  66,597,028,096
Read That Table Again
─────────────────────────────────────────
  A three-level B+ tree indexes 131 MILLION rows.

  So almost any lookup in almost any real table is
  THREE page reads.

  And in practice fewer: the root is always cached,
  and the level below it usually is too (Chapter
  5). The typical cost is ONE actual disk read.
─────────────────────────────────────────

The Practical Corollary
─────────────────────────────────────────
  Index key SIZE matters, because it sets the
  fanout.

  8-byte integer key    ──► fanout ~508
  60-byte text key      ──► fanout ~120

  The text index is deeper and every node holds
  fewer keys, so the whole index is larger and
  colder. This is a concrete reason to prefer
  integer surrogate keys (Module 2, Chapter 2).
─────────────────────────────────────────

4. Searching

class Node:
    def __init__(self, leaf=False):
        self.keys, self.children, self.leaf, self.next = [], [], leaf, None
 
def search(node, key):
    """Descend from root to leaf. One page read per level."""
    while not node.leaf:
        i = 0
        while i < len(node.keys) and key >= node.keys[i]:    # binary search in practice
            i += 1
        node = node.children[i]                              # ← ONE page read
 
    for k, ptr in zip(node.keys, node.children):             # now in the leaf
        if k == key:
            return ptr                                        # the row pointer
    return None
Cost, Precisely
─────────────────────────────────────────
  PAGE READS   the height. 3 or 4, always.
  COMPARISONS  log₂(fanout) per node via binary
               search within the page — pure CPU,
               essentially free.

  The whole design trades more in-memory
  comparisons for fewer disk reads, which is
  exactly the right trade under Chapter 1's cost
  model.
─────────────────────────────────────────

5. Range Scans and the Leaf Chain

The property that makes B+ trees right for databases specifically.

SELECT * FROM students WHERE marks BETWEEN 70 AND 90;
How It Runs
─────────────────────────────────────────
  1. Descend to the leaf containing 70.
       3 page reads.
  2. Read entries rightwards along the LEAF LINKED
     LIST until a key exceeds 90.
       SEQUENTIAL reads — cheap.

  A hash index cannot do this at all: it can find
  70 and 90, and has no idea what lies between
  (Chapter 3).
─────────────────────────────────────────

Everything a Sorted Structure Gives You
─────────────────────────────────────────
  WHERE x BETWEEN a AND b     range
  WHERE x > a                 open range
  ORDER BY x                  free — walk the
                              leaves; NO SORT STEP
  MIN(x) / MAX(x)             leftmost / rightmost
                              leaf. O(height).
  WHERE x LIKE 'abc%'         a prefix IS a range
  GROUP BY x                  pre-sorted input

  This is why B+ trees are the default index in
  every relational database: one structure serves
  equality, ranges, sorting and grouping.
─────────────────────────────────────────

6. Insertion and Splitting

The Algorithm
─────────────────────────────────────────
  1. Descend to the correct leaf.
  2. Room? Insert in key order. Done.
  3. Full? SPLIT:
       - divide entries between two leaves
       - push the middle key UP to the parent
       - if the parent is now full, split it too
       - if the ROOT splits, a new root is created
         and the tree grows one level

  The tree grows at the ROOT, never at the leaves.
  That is why it stays perfectly balanced with no
  rebalancing pass.
─────────────────────────────────────────

Sequential vs Random Insert Keys
─────────────────────────────────────────
  SEQUENTIAL (auto-increment id)
    Every insert lands in the RIGHTMOST leaf.
    Splits are cheap, pages fill ~100%, and the hot
    page stays cached.
    ── the good case

  RANDOM (UUID v4)
    Inserts scatter across the whole tree.
    Every insert may touch a cold page. Splits leave
    pages ~50% full, so the index is roughly TWICE
    the size.
    ── measurably worse, on both writes and reads

  Fix if you need UUIDs: use a time-ordered variant
  (UUIDv7, ULID) so inserts are sequential again.
  This is a real and common production problem.
─────────────────────────────────────────

7. What This Costs You

An index is not free, and the costs are the reason not to index everything.

The Four Costs
─────────────────────────────────────────
  WRITE AMPLIFICATION
    Every INSERT, UPDATE of an indexed column, and
    DELETE must update EVERY affected index.
    Five indexes ──► roughly six writes per insert.

  SPACE
    Often 10-30% of the table per index. Several
    indexes can exceed the table's own size.

  MEMORY PRESSURE
    Index pages compete with table pages for the
    buffer pool (Chapter 5). Unused indexes evict
    useful data.

  OPTIMISER COST
    More indexes means more candidate plans to
    consider on every query.
─────────────────────────────────────────

-- Find indexes nobody uses (PostgreSQL) — usually a surprising list.
SELECT relname AS table, indexrelname AS index, idx_scan AS times_used,
       pg_size_pretty(pg_relation_size(indexrelid)) AS size
FROM pg_stat_user_indexes
WHERE idx_scan = 0
ORDER BY pg_relation_size(indexrelid) DESC;
The Balance
─────────────────────────────────────────
  READ-HEAVY   index generously; reads dominate
  WRITE-HEAVY  index sparingly; every index taxes
               every write

  Chapter 4 turns this into a procedure.
─────────────────────────────────────────

8. Summary & Next Steps

Key Takeaways

  • A binary search tree wastes almost an entire page per node; a B+ tree makes the node page-sized, which changes the logarithm's base and collapses the height to three or four.
  • Data pointers live only in leaves, so internal nodes pack more keys and the tree stays shallow; leaves are linked, which is what makes range scans and free ordering possible.
  • Index key size sets the fanout, so a wide text key produces a deeper, larger, colder index than an integer one.
  • Random insert keys such as UUIDv4 scatter writes and leave pages half full, roughly doubling index size — time-ordered identifiers fix it.

Concept Check

  1. Both a BST and a B+ tree are O(log n). Why is one usable on disk and the other not?
  2. Which structural property makes ORDER BY indexed_column free, and which index type lacks it?
  3. Why does switching a primary key from auto-increment to UUIDv4 slow down both writes and reads?

Next Chapter

→ Chapter 3: Hash and Specialised Indexes

Jr Codex — 1-on-1 Personalized Coaching | Back to Module Index | Back to DBMS Index