Foundations — Composite indexes, covering indexes

This page assumes you have seen nothing. Before we talk about "composite" or "covering" anything, we must earn every word the parent note used: table, row, column, sorted, seek, scan, B-tree, pointer, page, I/O, lexicographic, and the symbols $N$, $O(N)$, $O(\log N)$, (a, b). We build them one at a time, each on top of the last.

1. Table, row, column — the grid

Picture a spreadsheet. That is literally all a table is at this level.

Look at the figure: the whole rectangle is the table orders. One highlighted horizontal band is a row. One highlighted vertical band is a column. The topic needs these words because an index is built on columns to help you find rows — so we must be able to name both.

2. $N$ — a name for "how many rows"

Before we can say anything is fast or slow, we need a name for the size of the table.

That is the whole meaning of $N$: a stand-in for a count. Every claim about speed below is really a claim about how the work changes as $N$ grows.

3. Scan vs seek — the whole reason indexes exist

Suppose you want every order where status = 'paid'.

We have a name for the table's size ($N$) and two behaviours (scan, seek). Next we need a way to measure how each behaviour's work grows with $N$.

4. $O(N)$ and $O(\log N)$ — measuring "how much work"

The parent note says a scan is $O(N)$ and an index lookup is $O(\log N)$. Let us earn that notation from zero.

Why the tool "logarithm"? Because it answers exactly one question: "How many times can I split this pile into a fixed number of parts and follow just one part, before one item is left?" That is precisely what a good lookup does — shrink the search space by a constant factor each step.

Look at the two curves. The straight blue line is $O(N)$: the scan. The nearly-flat pink line is $O(\log N)$: the seek. As you slide right (more rows), the gap explodes. This gap is the entire payoff of an index. We need this notation so "faster" has a precise meaning instead of a feeling.

5. "Balanced" — why the tree stays shallow

A tree can lead to a fast seek only if it is balanced. Let us define that word before we use it.

6. The B-tree — the shape that makes a seek possible

How does a seek actually shrink the search each step? Through a sorted, balanced, branching tree — a B-tree.

Trace the figure: to find 50, you stand at the root, compare against its split-points, and descend into the one child range that contains 50 — throwing away all the other branches at once. Because each node has a high fan-out (many children, not just two), each step discards a large fraction of the data — even more than half — so the tree is very shallow and a lookup takes only a handful of steps. The bottom yellow strip is the leaf level, where entries sit in sorted order, side by side.

For the deeper mechanics see B-tree indexes.

7. Sorted by ONE column vs sorted by (many) — lexicographic order & the leftmost-prefix rule

A single-column index sorts leaf entries by one value. A composite index sorts by a list of values, in order. That "sort a list of things by comparing item 1, then item 2 on ties" is called lexicographic (dictionary) order.

The figure shows the notation (a, b): a pair of columns treated as one sort key. The parentheses just mean "these two, in this order, form the key." Notice in the picture: to find a specific b value you'd have to hunt through every a group — because b is only sorted within each a. This picture forces one exact rule, which we now name:

We only name the rule here; the parent note shows how to apply it to real queries.

8. Pointer, page, I/O — why the "extra fetch" is expensive

The parent note warns that even after the index finds a match, the DB may take an "extra trip" to the table, costing "random I/O." Let us define those words.

Where the row physically lives (right next to the index or elsewhere) is the subject of Clustered vs non-clustered indexes.

9. Which column should go first? — selectivity, in one breath

The parent note says "equality columns first." Underneath sits one idea:

We only mention it here so the symbol/word exists; the full treatment is Index selectivity & cardinality. The tools that report what the database actually decided to do are covered by Query planner / EXPLAIN, and the cost of keeping all these indexes updated on every write is Write amplification. Keeping columns tidy in the first place is Database normalization.

How it all feeds the topic

Read top to bottom: the need for a seek demands $O(\log N)$, which demands a balanced B-tree with high fan-out, whose sorted leaves let us key on multiple columns lexicographically (the leftmost-prefix rule → composite) and store payload to skip the fetch (covering). Both arrows land on the parent topic.

Return now to Composite indexes, covering indexes (index 4.4.14) — every symbol it uses is now defined.

Equipment checklist

Answer each before moving on; if any stumps you, re-read that section.