Indexing Internals

By the end of this lesson you'll know what actually happens inside an index — how a B-tree turns a million-row scan into a handful of hops, when a hash or bitmap index wins, the difference between clustered and non-clustered storage, why a covering index can skip the table entirely, and the leftmost-prefix rule that decides whether your composite index gets used at all.

Learn Python, JavaScript, Java and more with free interactive lessons, real projects and AI-powered help. Beginner-friendly.

Part of the free SQL course at LearnCodingFast — hands-on lessons with examples you run in your browser, plus practice exercises and a quick quiz.

Picture this employees table with 1,000,000 rows . Without an index, finding one salary means reading all million rows. The examples below build indexes on it and watch the plan change.

An index is a separate data structure the database keeps next to your table to find rows quickly — like the index at the back of a book. The default everywhere (PostgreSQL, MySQL, SQLite, SQL Server) is the B-tree (technically a B+tree : only the leaf level holds the data, and the leaves are chained together).

A B-tree is a sorted phone book . The values are kept in order, so you never read it cover to cover. You open near the middle, see you've gone too far, jump back — a few hops and you're there. Each hop roughly halves what's left, which is why lookups are logarithmic : 1,000,000 rows take only about 20 comparisons (log₂ 1,000,000 ≈ 20), not a million.

How it works under the hood: internal nodes are signposts ("salaries from 50k–60k are down this branch"); the bottom leaf nodes hold the actual entries in sorted order and are linked left-to-right in a chain. That structure gives you three wins for free:

How do you prove the index is being used? Ask the planner with EXPLAIN . It prints the plan — the steps the database will take, as text. The two lines you care about most:

Choose B-tree vs hash vs bitmap for the described column and justify it. The expected answer is in the comments so you can check yourself.

A hash index runs each value through a hash function and stores it in a bucket. Looking up an exact value is O(1) on average — jump straight to the bucket. The catch: hashing scrambles order, so there is no "next" value. That means equality only — no ranges, no ORDER BY , no prefix LIKE .

Think of a hash index as a coat check : hand over your ticket number and you get the exact coat instantly — but you can't ask for "all coats with tickets between 40 and 80", because the rack isn't in number order.

Cardinality means "how many distinct values a column has". email is high-cardinality (nearly unique); status with four values is low-cardinality . A bitmap index stores one bit-string per distinct value — a row of 1s and 0s where bit position N means "row N has this value". To find "shipped AND west", the database just bitwise- AND s two bit-strings, which is blazingly fast.

Imagine a wall of light switches, one per row. The "shipped" bitmap flips on every shipped order; the "west" bitmap flips on every western order. Overlay the two and the switches still on are exactly the rows you want.

Oracle creates bitmap indexes explicitly; PostgreSQL builds equivalent bitmap scans on the fly to combine several B-tree indexes. The downside is writes: every insert or update must flip bits across whole bit-strings, so bitmaps belong on read-heavy tables (reporting, data warehouses), not busy transactional tables.

A clustered index decides the physical order of the rows on disk — the table is the index, with full rows living in the leaves. Because rows can only be stored one way, a table can have exactly one clustered index (usually the primary key). A non-clustered index is a separate sorted structure whose leaves hold the indexed value plus a pointer back to the row; you can have many of these, but each lookup pays for a pointer hop to fetch the rest of the row.

A clustered index is a dictionary: the words and their definitions are physically printed in sorted order. A non-clustered index is the index at the back of a textbook: it lists terms with page numbers you must flip to.

A covering index includes every column a query touches, so the database answers it from the index alone and never visits the table — an index-only scan . You keep the filter/sort columns as the index keys and tack on the columns you only need to return as the payload (via INCLUDE in PostgreSQL/SQL Server, or just by listing them in MySQL).

A composite (multi-column) index on (A, B, C) is sorted by A first, ties broken by B , then C — exactly like a phone book sorted by (last name, then first name) . The leftmost-prefix rule follows directly: the index can seek only on a prefix of its columns with no gaps. It serves filters on A , on A+B , or on A+B+C — but not on B alone or C alone, because without the leading column the entries are scattered all over the index.

💡 Rule of thumb — column order is everything

Put the columns you filter with = first, the column you range/sort on next, and payload-only columns last. Get the order wrong and the index sits unused while your query falls back to a Seq Scan .

Given the composite index below, mark each query ✅ (index helps) or ❌ (it can't) using the leftmost-prefix rule.

Q: If indexes make reads so fast, why not index every column?

Because every index must be kept up to date on every write, and each one eats storage and memory. More indexes mean slower INSERT / UPDATE / DELETE and a bigger database. Index for the queries you actually run, then drop the ones the stats show are unused.

Q: What's the difference between a B-tree and a B+tree?

In a B+tree only the leaf level stores data, and the leaves are linked in a chain — which is what makes range scans and ordered reads fast. Databases say "B-tree" but almost all of them actually implement B+trees.

Q: My index exists but the query still does a Seq Scan — why?

Common causes: the filter doesn't match the leftmost prefix of a composite index; a function wraps the column ( LOWER(col) ); the column has low selectivity so a scan is genuinely cheaper; or table statistics are stale (run ANALYZE ). Read the EXPLAIN plan to see which.

Q: Does the order of columns in a composite index matter?

Hugely. (A, B) and (B, A) are different indexes that serve different queries. Lead with the column(s) you filter by equality, then the range/sort column. The leftmost-prefix rule means only the leading columns can be seeked.

Put it all together — equality first, sort column next, payload via INCLUDE . Write the CREATE INDEX , then check it against the expected idea in the comments.

Practice quiz

• Browse all free courses
• Cheat sheets & quizzes
• Coding dictionary