DBMS · Session 6 — Index Structures

1 Why indexes — the full-scan problem

Explain like I'm 5

Picture a giant book with no contents page. To find the one page that mentions dinosaurs, you'd have to flip through every single page from the start. Exhausting! Now imagine someone added an index at the back: "Dinosaurs … page 184." You jump straight there. A database index is exactly that back-of-the-book index — a sorted shortcut that tells the database where to look, so it doesn't have to read everything.

A database table is stored as rows packed into fixed-size blocks on disk called pages (recall the buffer pool from Session 5 — pages are the unit the database reads from disk into memory). When you ask a question like SELECT * FROM students WHERE id = 8472, the database has two options.

Option A — the full table scan

A full table scan means reading every page of the table, row by row, checking each one to see if it matches. If the table has a million rows spread across thousands of pages, that's thousands of disk reads — even though you only wanted one row. Disk reads are slow (orders of magnitude slower than memory), so this is the expensive thing we want to avoid.

Concrete example

A table of 1,000,000 students, 100 rows per page → 10,000 pages. To find one student by id with no index, the database reads up to all 10,000 pages. With a good index, it reads about 3–4 pages instead. That's the difference between a query that takes seconds and one that takes milliseconds.

Option B — use an index (the sorted shortcut)

An index is a separate, sorted data structure built on one or more columns (the search key). Because it's kept in sorted order, the database can use fast lookup techniques — like binary search, or walking down a tree — to zoom in on the matching rows without scanning the whole table.

The one big idea

An index trades a little extra storage and slightly slower writes for dramatically faster reads. Instead of "look at everything," the database can say "the sorted index tells me exactly where row 8472 lives — fetch just that page."

Index vs. the table itself

It's important to keep these two things separate in your head:

Aspect	The table (heap)	The index
What it stores	All the actual row data.	Just the search-key values, plus a pointer to where the full row lives.
Order	Usually unordered ("heap") — rows sit wherever there was room.	Always kept sorted by the search key.
Size	Big — holds everything.	Smaller — only key + pointer per row.
Purpose	Be the source of truth.	Be a fast lookup map into the table.

The pointer in an index is typically a record ID (often written RID): the page number plus the slot on that page where the full row sits. Find the key in the index, follow the pointer, fetch one page — done.

The trade-off (there's no free lunch)

Indexes make reads fast, but they cost you:

Slower writes. Every INSERT, UPDATE, or DELETE must also update every index on that column to keep it sorted. More indexes = more write work.
Extra space. Each index is a whole separate structure stored on disk.

So you index the columns you search and join on a lot — not every column. Choosing indexes wisely is a core database-tuning skill.

Many kinds of index exist

Hash indexes, bitmap indexes, and tree indexes are all options. By far the most common default in real databases (PostgreSQL, MySQL/InnoDB, SQLite, Oracle…) is the B+ tree — because it's great at both single-value lookups and range queries, and it stays fast even when it's huge. That's our whole focus from here on.

Recap Without an index, finding a row means a slow full table scan of every page. An index is a separate sorted structure of (key → pointer) that lets the database jump straight to the right page. The price is slower writes and extra disk space — so you index the columns you query most.

2 B+ tree structure & invariants

Explain like I'm 5

Think of a company org chart, but upside down. At the top is one boss (the root). The boss doesn't do the work — they just point you to the right manager. That manager points you to the right team lead, and finally you reach the workers (the leaves) who actually hold the answers. To find anything, you only ask a few people on the way down instead of bothering everyone. A B+ tree is that pointing-you-down structure, kept perfectly balanced so the trip is always short.

A B+ tree is a balanced, sorted tree designed specifically for disk. Each node is exactly one page, so reading a node = one disk read. There are two kinds of nodes.

Two node types: internal vs. leaf

Node type	What it holds	Job
Internal node (incl. the root)	Sorted separator keys and child pointers only — no data.	Act as a signpost: "keys below X go left, keys ≥ X go right."
Leaf node	The actual sorted keys, each with its data pointer (RID), plus a pointer to the next leaf.	Hold the real answers and chain together for range scans.

The defining feature of a B+ tree

In a B+ tree, all the real data lives only in the leaves. Internal nodes are pure signposts. (This is the key difference from a plain B-tree, where data can sit in internal nodes too.) Putting all data at the bottom keeps internal nodes tiny, so each one can point to many children — which makes the tree very shallow.

Order / fanout — why the tree is so shallow

The fanout (also called the order) is the maximum number of children an internal node can have. Because each node is one page (say 4 KB or 8 KB) and a key+pointer pair is small (maybe ~16 bytes), a single node can hold hundreds of pointers. A fanout of a few hundred is normal.

High fanout is the whole magic. A tree where each node has ~hundreds of children gets very tall capacity from very few levels:

Example: how few levels you need

With a fanout of 100:

1 level (just leaves) → ~100 keys
2 levels → ~100 × 100 = 10,000 keys
3 levels → ~100 × 100 × 100 = 1,000,000 keys
4 levels → ~100,000,000 keys

So a B+ tree holding 100 million rows is only 4 levels deep. Finding any row touches just 4 nodes = 4 disk reads (and the top levels are usually already cached in the buffer pool, so it's often fewer). That's why databases love B+ trees.

A picture of a small B+ tree

Here's a tiny B+ tree (fanout small, just for drawing). Notice the leaves are chained left to right with arrows — that's the linked list.

                          [ internal / root ]
                          +-------------------+
                          |   13   |   30   |
                          +--+-----+------+---+
                  <13       |     | 13..29|      |  >=30
            +---------------+     +---+   +------------------+
            v                         v                      v
      [ leaf ]                  [ leaf ]                [ leaf ]
   +----+----+----+         +----+----+----+        +----+----+----+
   |  5 |  9 | 11 |  -->   | 13 | 20 | 27 |  -->  | 30 | 41 | 55 |  --> (null)
   +----+----+----+         +----+----+----+        +----+----+----+
     each key also carries a pointer (RID) to its full row in the table

Read the root as a set of signposts: keys < 13 go to the first child, keys 13 to 29 go to the middle child, keys ≥ 30 go to the last child. Notice 13 appears both in the root (as a separator) and in a leaf (as real data) — that's normal in a B+ tree, because the root copy is just a signpost.

The invariants (rules the tree always keeps)

A B+ tree is always valid because it enforces these rules on every operation:

Sorted. Keys within every node are in ascending order, and leaves overall read left-to-right as one fully sorted sequence.
Balanced. Every leaf is at the exact same depth. The tree never gets lopsided, so every lookup costs the same number of steps. This is the balance invariant.
Half-full (the occupancy rule). Every node except the root must be at least half full (roughly between ⌈order/2⌉ and order entries). This guarantees the tree doesn't waste space or grow needlessly tall.
Leaf chain. Leaves form a linked list: each leaf points to the next leaf in sorted order. This is what makes range scans fast (Topic 3).
Height stays low. Because of balance + high fanout, height is O(log_fanout n) — a small number even for billions of rows.

Why "balanced" matters so much

An ordinary binary search tree can degenerate into a long thin chain (basically a linked list) if you insert sorted data, making lookups slow again. A B+ tree guarantees balance by splitting nodes as it grows (Topic 4), so it can never degenerate. Performance is predictable no matter what order you insert keys.

Recap A B+ tree has internal nodes (sorted separator keys + child pointers, pure signposts) and leaf nodes (the real sorted keys + data pointers, chained into a linked list). High fanout packs hundreds of pointers per page, so even a billion rows fit in ~4 levels. It always stays sorted, balanced, and at least half full, giving O(log n) lookups with very few disk reads.

3 Searching: point lookups & range scans

Explain like I'm 5

You're looking for a friend's apartment in a huge building. At the front door, a sign says "Rooms 1–50 take the left lift, 51–100 take the right." You pick a lift. On your floor, another sign narrows it further. A few signs later, you're at the door. You never wandered every hallway — each sign cut your search in a big chunk. Searching a B+ tree is following those signs from the root down to one leaf.

Point lookup — finding one exact key

A point lookup finds the row(s) for one exact value, like WHERE id = 27. You start at the root and walk down, at each internal node choosing the child whose key range contains your target, until you reach a leaf — then look inside the leaf for the key.

Below is the B+ tree node structure (one type with a leaf flag — internal nodes hold child pointers, leaves hold data pointers plus a next chain pointer) together with the downward point-lookup search, in three languages.

# B+ tree node + point-lookup search

class Node:
    def __init__(self, leaf):
        self.leaf = leaf
        self.keys = []          # sorted keys
        self.children = []      # child Nodes (internal only)
        self.rids = []          # data pointers, parallel to keys (leaf only)
        self.next = None       # next leaf in the chain (leaf only)


def search(node, target):
    # Descend internal nodes following the right child range.
    while not node.leaf:
        i = 0
        while i < len(node.keys) and target >= node.keys[i]:
            i += 1
        node = node.children[i]
    # node is now a leaf: look for the exact key.
    for i, k in enumerate(node.keys):
        if k == target:
            return node.rids[i]      # the RID -> fetch the row
    return None                    # NOT FOUND

// B+ tree node + point-lookup search
#include <vector>

struct Node {
    bool leaf;
    std::vector<int> keys;        // sorted keys
    std::vector<Node*> children;   // child nodes (internal only)
    std::vector<int> rids;        // data pointers, parallel to keys (leaf only)
    Node* next = nullptr;        // next leaf in the chain (leaf only)
    Node(bool isLeaf) : leaf(isLeaf) {}
};

// Returns the RID, or -1 if not found.
int search(Node* node, int target) {
    while (!node->leaf) {              // descend to a leaf
        size_t i = 0;
        while (i < node->keys.size() && target >= node->keys[i]) ++i;
        node = node->children[i];
    }
    for (size_t i = 0; i < node->keys.size(); ++i)
        if (node->keys[i] == target) return node->rids[i];
    return -1;                       // NOT FOUND
}

// B+ tree node + point-lookup search
import java.util.*;

class Node {
    boolean leaf;
    List<Integer> keys = new ArrayList<>();      // sorted keys
    List<Node> children = new ArrayList<>();      // internal only
    List<Integer> rids = new ArrayList<>();       // data pointers (leaf only)
    Node next = null;                            // next leaf in the chain
    Node(boolean leaf) { this.leaf = leaf; }
}

// Returns the RID, or -1 if not found.
static int search(Node node, int target) {
    while (!node.leaf) {                          // descend to a leaf
        int i = 0;
        while (i < node.keys.size() && target >= node.keys.get(i)) i++;
        node = node.children.get(i);
    }
    for (int i = 0; i < node.keys.size(); i++)
        if (node.keys.get(i) == target) return node.rids.get(i);
    return -1;                                   // NOT FOUND
}

Worked example: look up key 27

Using the tree from Topic 2 (root separators 13 and 30):

🌳

Root

27 is ≥13 and <30 → take the middle child

→

🍃

Leaf [13,20,27]

scan inside → find 27

→

📄

Follow RID

fetch the full row from the table page

The whole lookup touched the root, one leaf, then one table page. On a real tree that's a handful of nodes regardless of how big the table is.

Range scan — finding everything in an interval

A range scan answers queries like WHERE id BETWEEN 20 AND 50 or WHERE age > 30. This is where the leaf linked list shines. You search down to the leaf holding the start of the range, then simply walk along the leaf chain collecting keys until you pass the end of the range.

function rangeScan(low, high):
    leaf = search down to the leaf that would contain low
    results = []
    while leaf is not null:
        for key in leaf.keys (ascending):
            if key > high:
                return results        # passed the end → done
            if key >= low:
                results.add(leaf.pointer_for(key))
        leaf = leaf.next         # hop to next leaf via the linked list
    return results

Worked example: keys BETWEEN 20 AND 50

Search down to the leaf containing the start (20) → land in leaf [13, 20, 27].
Collect 20, 27 (both in range; 13 is below low, skip it).
Follow next to leaf [30, 41, 55]; collect 30, 41.
Hit 55 > 50 → stop. Result: {20, 27, 30, 41}.

No need to climb back up the tree between leaves — the chain pointers let us slide along the bottom row like reading a sorted list.

Complexity

Operation	Cost	Why
Point lookup	O(log_F n) disk reads, where F = fanout	One node read per level; height is log_F n (≈ 3–4 for huge tables).
Range scan	O(log_F n + k)	log to find the start, then k for the matching results streamed along the leaf chain (k = number of matches).

Key takeaway

Because fanout F is large, log_F n is tiny — a million rows is ~3 levels, a billion is ~4–5. The base of the logarithm being hundreds (not 2, like a binary tree) is exactly why B+ trees are so disk-friendly: fewer levels = fewer slow disk reads.

Recap A point lookup walks root → leaf following signpost keys, in O(log_F n) reads. A range scan finds the start leaf the same way, then glides along the leaf linked list collecting matches until it passes the upper bound, in O(log_F n + k). High fanout keeps the height — and the disk reads — tiny.

4 Insertion & page splits

Explain like I'm 5

Imagine a school bus with rows of seats. New kids keep getting on. When a row is full and one more kid needs to sit there, you split the row into two and tell the bus monitor (one level up) "there's a new row now, here's where it starts." If the monitor's clipboard is also full, they split too, and tell their boss. Occasionally even the head teacher's list overflows and a brand-new top boss is created — that's the bus (the tree) growing one level taller. B+ tree insertion is exactly this splitting-and-telling-upward.

Inserting a key must keep all the invariants true (sorted, balanced, half-full). The trick that preserves balance is the page split.

The algorithm in words

Find the leaf where the key belongs (same downward search as a lookup).
If the leaf has room, insert the key in sorted position. Done — easy case.
If the leaf is full, split it into two leaves, dividing the keys roughly in half. Then copy up the smallest key of the new right leaf into the parent as a new separator, and fix the leaf-chain pointers.
If the parent is now full too, split the parent the same way — but for an internal node you push up the middle key (it moves up, it isn't copied), since internal nodes only hold signposts.
If the split reaches the root and the root splits, a brand-new root is created above it. This is the only way a B+ tree grows taller — from the top, which is why all leaves always stay at the same depth.

"Copy up" vs "push up" — the one subtlety

When a leaf splits, the separator key still needs to physically remain in the leaf (it's real data), so a copy of it goes up. When an internal node splits, the middle key is only a signpost, so it moves up entirely (push up) — it should not be duplicated. Mixing these up is the classic B+ tree bug.

Here is a correct, self-contained insertion for a B+ tree of a given order (max keys per node). It descends recursively; when a child overflows it returns a separator key and a new right sibling, which the parent absorbs. Leaves copy up; internal nodes push up. Each tab ends with a tiny demo that inserts a few keys and searches one.

# B+ tree insertion with leaf split + key promotion.
# Reuses the Node class from the search example above.

ORDER = 3                       # max keys per node; split when a 4th arrives

class BPlusTree:
    def __init__(self):
        self.root = Node(leaf=True)

    def insert(self, key, rid):
        sep, right = self._insert(self.root, key, rid)
        if right is not None:        # root split -> grow a new root (+1 level)
            new_root = Node(leaf=False)
            new_root.keys = [sep]
            new_root.children = [self.root, right]
            self.root = new_root

    # Returns (separator, right_sibling) if node split, else (None, None).
    def _insert(self, node, key, rid):
        if node.leaf:
            i = 0
            while i < len(node.keys) and node.keys[i] < key:
                i += 1
            node.keys.insert(i, key)
            node.rids.insert(i, rid)
        else:
            i = 0
            while i < len(node.keys) and key >= node.keys[i]:
                i += 1
            sep, right = self._insert(node.children[i], key, rid)
            if right is None:
                return None, None
            node.keys.insert(i, sep)             # absorb child's separator
            node.children.insert(i + 1, right)

        if len(node.keys) <= ORDER:
            return None, None               # no overflow
        return self._split(node)

    def _split(self, node):
        mid = len(node.keys) // 2
        right = Node(leaf=node.leaf)
        if node.leaf:
            # COPY up: separator stays in the right leaf as real data.
            right.keys = node.keys[mid:]
            right.rids = node.rids[mid:]
            node.keys = node.keys[:mid]
            node.rids = node.rids[:mid]
            right.next = node.next               # fix leaf chain
            node.next = right
            sep = right.keys[0]
        else:
            # PUSH up: middle key moves up, leaving this node.
            sep = node.keys[mid]
            right.keys = node.keys[mid + 1:]
            right.children = node.children[mid + 1:]
            node.keys = node.keys[:mid]
            node.children = node.children[:mid + 1]
        return sep, right


# --- demo ---
t = BPlusTree()
for k in [10, 20, 30, 40, 50, 25]:
    t.insert(k, rid=k * 100)         # fake RID = key*100
print(search(t.root, 25))           # -> 2500
print(search(t.root, 99))           # -> None

// B+ tree insertion with leaf split + key promotion.
// Reuses the Node struct from the search example above.
#include <vector>
#include <iostream>

const int ORDER = 3;        // max keys per node

struct Split { int sep; Node* right; };   // right == nullptr means "no split"

struct BPlusTree {
    Node* root = new Node(true);

    void insert(int key, int rid) {
        Split s = insertRec(root, key, rid);
        if (s.right) {                       // root split -> grow a new root
            Node* nr = new Node(false);
            nr->keys.push_back(s.sep);
            nr->children = { root, s.right };
            root = nr;
        }
    }

    Split insertRec(Node* node, int key, int rid) {
        if (node->leaf) {
            size_t i = 0;
            while (i < node->keys.size() && node->keys[i] < key) ++i;
            node->keys.insert(node->keys.begin() + i, key);
            node->rids.insert(node->rids.begin() + i, rid);
        } else {
            size_t i = 0;
            while (i < node->keys.size() && key >= node->keys[i]) ++i;
            Split s = insertRec(node->children[i], key, rid);
            if (!s.right) return { 0, nullptr };
            node->keys.insert(node->keys.begin() + i, s.sep);
            node->children.insert(node->children.begin() + i + 1, s.right);
        }
        if ((int)node->keys.size() <= ORDER) return { 0, nullptr };
        return splitNode(node);
    }

    Split splitNode(Node* node) {
        size_t mid = node->keys.size() / 2;
        Node* right = new Node(node->leaf);
        int sep;
        if (node->leaf) {                     // COPY up: sep stays in right leaf
            right->keys.assign(node->keys.begin() + mid, node->keys.end());
            right->rids.assign(node->rids.begin() + mid, node->rids.end());
            node->keys.resize(mid);
            node->rids.resize(mid);
            right->next = node->next;         // fix leaf chain
            node->next = right;
            sep = right->keys[0];
        } else {                              // PUSH up: middle key moves up
            sep = node->keys[mid];
            right->keys.assign(node->keys.begin() + mid + 1, node->keys.end());
            right->children.assign(node->children.begin() + mid + 1, node->children.end());
            node->keys.resize(mid);
            node->children.resize(mid + 1);
        }
        return { sep, right };
    }
};

// --- demo ---
int main() {
    BPlusTree t;
    for (int k : { 10, 20, 30, 40, 50, 25 }) t.insert(k, k * 100);
    std::cout << search(t.root, 25) << "\n";   // 2500
    std::cout << search(t.root, 99) << "\n";   // -1 (not found)
}

// B+ tree insertion with leaf split + key promotion.
// Reuses the Node class from the search example above.
import java.util.*;

class BPlusTree {
    static final int ORDER = 3;          // max keys per node
    Node root = new Node(true);

    // right == null means "no split".
    static class Split { int sep; Node right; Split(int s, Node r){ sep=s; right=r; } }

    void insert(int key, int rid) {
        Split s = insertRec(root, key, rid);
        if (s.right != null) {              // root split -> grow a new root
            Node nr = new Node(false);
            nr.keys.add(s.sep);
            nr.children.add(root);
            nr.children.add(s.right);
            root = nr;
        }
    }

    Split insertRec(Node node, int key, int rid) {
        if (node.leaf) {
            int i = 0;
            while (i < node.keys.size() && node.keys.get(i) < key) i++;
            node.keys.add(i, key);
            node.rids.add(i, rid);
        } else {
            int i = 0;
            while (i < node.keys.size() && key >= node.keys.get(i)) i++;
            Split s = insertRec(node.children.get(i), key, rid);
            if (s.right == null) return s;
            node.keys.add(i, s.sep);
            node.children.add(i + 1, s.right);
        }
        if (node.keys.size() <= ORDER) return new Split(0, null);
        return splitNode(node);
    }

    Split splitNode(Node node) {
        int mid = node.keys.size() / 2;
        Node right = new Node(node.leaf);
        int sep;
        if (node.leaf) {                       // COPY up: sep stays in right leaf
            right.keys.addAll(node.keys.subList(mid, node.keys.size()));
            right.rids.addAll(node.rids.subList(mid, node.rids.size()));
            node.keys.subList(mid, node.keys.size()).clear();
            node.rids.subList(mid, node.rids.size()).clear();
            right.next = node.next;           // fix leaf chain
            node.next = right;
            sep = right.keys.get(0);
        } else {                               // PUSH up: middle key moves up
            sep = node.keys.get(mid);
            right.keys.addAll(node.keys.subList(mid + 1, node.keys.size()));
            right.children.addAll(node.children.subList(mid + 1, node.children.size()));
            node.keys.subList(mid, node.keys.size()).clear();
            node.children.subList(mid + 1, node.children.size()).clear();
        }
        return new Split(sep, right);
    }

    // --- demo ---
    public static void main(String[] a) {
        BPlusTree t = new BPlusTree();
        for (int k : new int[]{ 10, 20, 30, 40, 50, 25 }) t.insert(k, k * 100);
        System.out.println(search(t.root, 25));   // 2500
        System.out.println(search(t.root, 99));   // -1 (not found)
    }
}

Step-by-step worked example

Let's build a small tree where a node holds at most 3 keys (so it splits when a 4th would arrive). We insert: 10, 20, 30, 40, 50.

Insert 10, 20, 30 — the easy case

insert 10 → [ 10 ]
insert 20 → [ 10 | 20 ]
insert 30 → [ 10 | 20 | 30 ]      # leaf now full (3 keys), still a single leaf = the root

So far no split — there was always room.

Insert 40 — the first leaf split (tree grows to 2 levels)

The leaf [10|20|30] is full and 40 needs to go in. We'd have [10,20,30,40] → overflow → split into two leaves around the middle:

                 [ new root ]
                 +--------+
                 |   30   |          # 30 = smallest key of right leaf, COPIED up
                 +--+--+--+
            <30   |     |  >=30
            v           v
        +----+----+   +----+----+
        | 10 | 20 | -->| 30 | 40 |  --> (null)
        +----+----+   +----+----+

Note: 30 stays in the right leaf (it's real data) and a copy went up to the new root as a separator. A brand-new root was created → the tree is now 2 levels tall, and both leaves are at the same depth (balance preserved). The two leaves are chained left → right.

Insert 50 — back to the easy case

                 +--------+
                 |   30   |
                 +--+--+--+
            v           v
        +----+----+   +----+----+----+
        | 10 | 20 | -->| 30 | 40 | 50 |  --> (null)
        +----+----+   +----+----+----+

50 belongs in the right leaf, which has room (only 2 of 3 slots used). Insert in sorted order, no split needed. The next insert into that right leaf (say 60) would overflow it and trigger another leaf split, copying a separator up into the root.

When the root itself splits (height +1)

Keep inserting and eventually the root fills with separators. When it overflows, it splits and the middle separator is pushed up into a fresh root holding just that one key with two children. This is the only moment a B+ tree gets taller — and it happens at the top, which is precisely why every leaf always stays on the same level. Deletes do the mirror image: if a node drops below half-full it borrows from a sibling or merges, occasionally shrinking the tree — we'll cover deletion fully in Session 7.

Complexity

Operation	Cost	Why
Insert (no split)	O(log_F n)	Walk down to the leaf, insert in place.
Insert (with splits)	O(log_F n)	Splits propagate up at most one level per step, and the height is log_F n — so even cascading splits stay logarithmic.

Watch out — the write cost from Topic 1, in action

This is the "slower writes" trade-off made concrete. A single insert is usually cheap, but a split touches multiple pages (the leaf, its new sibling, the parent, sometimes more) and must be written back to disk. Every index on a table pays this on every insert. Useful indexes are worth it; needless ones just tax your writes.

Recap To insert, walk to the right leaf and add the key. If the node overflows, split it in half: leaves copy up a separator, internal nodes push up the middle key, and splits cascade upward. The tree only ever grows taller when the root splits — keeping it perfectly balanced. All of this stays O(log_F n).

★ Putting it all together

You just learned how databases find rows fast. Here's the one-paragraph story that ties the four topics together:

Reading a whole table to find one row is a slow full scan, so databases build an index — a sorted (key → pointer) shortcut. The workhorse index is the B+ tree: internal nodes are pure signposts and leaf nodes hold the real sorted keys, chained into a linked list. Thanks to high fanout, even a billion rows fit in ~4 levels, so a point lookup is just a few disk reads (O(log_F n)) and a range scan glides along the leaf chain (O(log_F n + k)). Inserts walk to a leaf and, when a node fills, split — copying up from leaves, pushing up from internal nodes — so the tree stays balanced and grows taller only by splitting the root. That balance is what makes reads, ranges, and writes all predictably fast.

Quick self-check

Why does an index make reads faster but writes slower?

Reads get faster because the sorted index lets you jump straight to the right page instead of scanning the whole table. Writes get slower because every insert/update/delete must also update the index (and may trigger splits) to keep it sorted and balanced.

In a B+ tree, where does the actual row data (or its pointer) live?

Only in the leaf nodes. Internal nodes hold separator keys and child pointers only — they're signposts. This keeps internal nodes small, raising fanout and lowering height.

Why is a B+ tree only ~4 levels deep even for 100 million rows?

High fanout: each node (one disk page) holds hundreds of child pointers, so capacity multiplies by ~hundreds per level. Height is O(log_F n) with a large base F, so few levels cover enormous tables — meaning very few disk reads per lookup.

What makes range scans (e.g. BETWEEN 20 AND 50) efficient?

The leaf-level linked list. You search down once to the start leaf, then follow next pointers along the bottom row, collecting matches until you pass the upper bound — no climbing back up the tree. Cost: O(log_F n + k).

When a leaf splits, why is the separator "copied up" but for an internal node it's "pushed up"?

Leaf keys are real data and must stay in the leaf, so a copy of the separator goes to the parent. Internal keys are only signposts, so the middle one moves up entirely (no duplication).

What is the only event that increases a B+ tree's height?

A root split. When the root overflows it splits and a new root is created above it. Because growth happens at the top, all leaves always remain at the same depth — the tree stays balanced.

📚 References & Further Reading

Class material

📄 Original course notes / handout (source sheet) — open the shared class material for this session.
📘 DBMS Session 6 — Index Structures (class handout for this session).

Papers, docs & deep dives

CMU 15-445 — Database Systems (Tree Indexes / B+Trees lecture) — the gold-standard university course; its B+ tree lecture and slides are the clearest free walkthrough of structure, search, and splits.
B+ Tree Visualizer (USF, David Galles) — interactively insert and delete keys and watch nodes split and merge in real time; the best way to build intuition.
Comer, "The Ubiquitous B-Tree" (ACM Computing Surveys, 1979) — the classic survey that explains B-trees and the B+ tree variant and why they dominate database indexing.
"Database System Concepts" (Silberschatz, Korth, Sudarshan) — Indexing chapter — the standard textbook treatment of B+ tree indexes, with full algorithms for search, insert, and delete.
Use The Index, Luke! (Markus Winand) — a friendly, practical guide to how B+ tree indexes behave in real SQL databases and how to use them well.

How databases find a row without reading the whole table

1 Why indexes — the full-scan problem

Option A — the full table scan

Option B — use an index (the sorted shortcut)

Index vs. the table itself

2 B+ tree structure & invariants

Two node types: internal vs. leaf

Order / fanout — why the tree is so shallow

A picture of a small B+ tree

The invariants (rules the tree always keeps)

3 Searching: point lookups & range scans

Point lookup — finding one exact key

Range scan — finding everything in an interval

Complexity

4 Insertion & page splits

The algorithm in words

Step-by-step worked example

Complexity

★ Putting it all together

Quick self-check

📚 References & Further Reading

Class material

Papers, docs & deep dives