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.

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.

What You'll Learn

Our Sample Table: employees

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.

1. B-Tree Indexes — The Workhorse

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:

• Equality ( = 75000 ): walk down the tree to one leaf.
• Range ( BETWEEN 50000 AND 80000 ): find the first matching leaf, then follow the leaf chain until you pass the upper bound.
• Sorting ( ORDER BY salary ): the leaves are already sorted, so no separate sort step is needed.

2. Reading the EXPLAIN Plan

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:

• Seq Scan — a full table scan; every row read. The index was not used.
• Index Scan — it jumped through the index. That's what you want.

Your Turn: pick the index type

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.

3. Hash Indexes — Equality Only

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.

4. Bitmap Indexes — Low Cardinality

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.

5. Clustered vs Non-Clustered

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.

6. Covering Indexes — Skip the Table

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).

7. Composite Indexes & the Leftmost-Prefix Rule

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 .

Your Turn: which queries does it serve?

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

Common Errors (and the fix)

• Hash index for a range query: you build USING hash (price) then run WHERE price > 100 and the plan shows a Seq Scan . Hashing has no order — use a B-tree for anything but exact equality.
• Wrong composite column order: an index on (hire_date, department_id) won't help WHERE department_id = 5 because department_id isn't the leftmost column. Reorder to put the most-filtered (usually the = ) column first.
• Over-indexing a write-heavy table: every INSERT / UPDATE / DELETE must update every index, so piling indexes onto an OLTP table makes writes crawl. Index the queries that matter, then drop unused ones (check idx_scan = 0 in pg_stat_user_indexes ).
• Low-selectivity B-tree index: indexing is_active (only true/false) rarely helps — when a value matches ~half the rows the planner ignores the index because a scan is cheaper. Index high-selectivity columns; consider a bitmap for low-cardinality reporting.
• Function on the indexed column: WHERE LOWER(email) = 'a@b.com' can't use a plain index on email — the function hides the raw value. Index the expression ( CREATE INDEX ... (LOWER(email)) ) or store it normalized.

📘 Quick Reference

Index type

Best for

Limitation

Frequently Asked Questions

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.

Mini-Challenge: Design the Optimal Index

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.

🎉 Lesson Complete

• ✅ A B-tree/B+tree keeps values sorted for O(log n) lookups, range scans, and free ordering
• ✅ Hash indexes are equality-only; bitmap indexes suit low-cardinality, read-heavy columns
• ✅ Clustered = physical row order (one per table); non-clustered = a sorted structure of pointers
• ✅ A covering index answers a query from the index alone (index-only scan)
• ✅ The leftmost-prefix rule decides which queries a composite index serves — column order is everything
• ✅ Read the EXPLAIN plan: Index Scan good, Seq Scan means your index was skipped
• ✅ Next: Query Optimization — turn these plans into faster queries

Practice quiz

Continue this course

• Previous: Advanced Normalization
• Next: Query Optimization