Database Indexes: What's Actually Happening Under the Hood

Every backend developer has typed ->index() in a migration at some point. Fewer have stopped to ask: what does the database engine actually do with that?
This article walks through indexes from first principles — B+Trees, how MySQL decides whether to use an index at all, why column order in a composite index matters, and how to read an EXPLAIN output like an engineer instead of guessing. Examples use MySQL/InnoDB and Laravel, but the concepts carry over to Postgres too.
Why indexes exist in the first place
A table without an index is just rows sitting on disk in pages. To find one row, the engine has no choice but to read pages one after another and check each row against your WHERE clause — a full table scan.
SELECT * FROM users WHERE email = '[e-mail]';

Row 1 → [e-mail] ✗
Row 2 → [e-mail] ✗
Row 3 → [e-mail] ✓ (found after checking 3 rows)
...
Row 1,000,000 → ...
That's O(n). Fine for a few thousand rows, brutal for millions. An index is simply a separate, ordered data structure that lets the engine skip straight to the answer instead of checking every row — at the cost of extra storage and slower writes. That trade-off is the entire story of indexing.
How the search actually changes
With an index built as a B+Tree, the same lookup becomes a walk down a balanced tree instead of a linear scan:
[ g ]
/ \
[ c ] [ n ]
/ \ / \
[a,b] [d,e,f] [k,l,m] [o,p...]

Looking for "ali":

1. root [g] → a < g → go left
2. node [c] → a < c → go left
3. leaf [a,b] → found 'ali' → pointer to the real row Instead of scanning a million rows, you're doing roughly log2(1,000,000) ≈ 20 comparisons. That gap — O(n) vs O(log n) — is the entire reason indexes exist, and it only gets more dramatic as tables grow. B+Tree, not just "a tree" Almost every relational database (InnoDB, Postgres) stores its indexes as a B+Tree, specifically:

Internal nodes hold only keys, used purely for navigation.
Actual data (or pointers to it) lives only in the leaf nodes.
Leaves are linked together, so range scans (BETWEEN, ORDER BY) can walk sideways instead of jumping back up the tree.

This is why B+Trees, not hash tables, are the default almost everywhere: a hash index gives you O(1) equality lookups but is completely useless for ranges, sorting, or prefix matching (LIKE 'abc%'). B+Trees give up a little raw speed on exact matches in exchange for handling nearly everything else.
Clustered vs. secondary indexes
This distinction trips people up constantly. In InnoDB, the table itself is the primary key's B+Tree — the leaves store the full row. That's the clustered index, and a table can only have one, because data can only be physically sorted one way at a time.
Every other index (a "secondary" or "non-clustered" index) stores the indexed column plus a pointer back to the primary key. Looking something up by a secondary index therefore takes two hops:

1. Search secondary index on email → get id = 458
2. Search clustered index on id = 458 → get the full row That second hop is called a bookmark lookup, and it's the reason a covering index (below) can be such a big win. Selectivity: the number that decides everything Cardinality is the count of distinct values in a column. Selectivity is that count divided by total rows. email on a million-row table has selectivity close to 1.0 — nearly every value is unique, making it a great index candidate. A status enum with 3 values has selectivity near 0.000003. Indexing it alone barely helps, because any single value still matches a huge chunk of the table — often cheap enough for MySQL's optimizer to just do a full scan instead. This is also why the optimizer sometimes ignores an index that exists: if a query is going to return 30%+ of the table anyway, hopping between index pages and table pages is slower than just scanning the table directly. Composite indexes and the leftmost prefix rule A multi-column index like (status, user_id, created_at) can only be used efficiently if your WHERE clause matches it starting from the left: ✅ WHERE status = 'pending' ✅ WHERE status = 'pending' AND user_id = 10 ✅ WHERE status = 'pending' AND user_id = 10 AND created_at > '2026-01-01'

❌ WHERE user_id = 10 -- skips the leftmost column
❌ WHERE created_at > '2026-01-01' -- doesn't touch status at all
Column order isn't cosmetic — it determines whether the index gets used at all. A practical rule of thumb: equality columns first, range/sort columns last. Anything compared with >, <, or BETWEEN stops the leftmost matching for everything after it, so put those columns at the end.
Covering indexes: skipping the table entirely
If an index contains every column your query needs — in WHERE and SELECT — the engine never has to touch the actual table row at all:
sqlCREATE INDEX idx_covering ON orders(status, created_at, total);

SELECT status, created_at, total
FROM orders
WHERE status = 'pending';
You'll see Using index in EXPLAIN's Extra column when this happens — no bookmark lookups, just the index leaves.
A real slow-query fix
Here's the pattern in practice. Say orders has 3 million rows:
sqlEXPLAIN SELECT * FROM orders
WHERE status = 'pending' AND user_id = 458
ORDER BY created_at DESC LIMIT 20;

-- type = ALL
-- rows = 2,987,410
-- Extra = Using where; Using filesort
type = ALL means a full scan, and Using filesort means MySQL is sorting 3 million rows by hand. That's the smoking gun.
sqlCREATE INDEX idx_orders_user_status_created
ON orders(user_id, status, created_at);
user_id and status are equality filters, created_at drives the ORDER BY, so it goes last. Re-running the query:
sql-- type = ref
-- key = idx_orders_user_status_created
-- rows = 34
-- Extra = Using index condition
From scanning ~3 million rows to 34, and the sort is now free because the index is already ordered by created_at. In Laravel you can check the same thing with DB::enableQueryLog() or Laravel Debugbar while iterating.
Reading EXPLAIN without guessing
The columns that actually matter, in order of how often you'll look at them:

type — access method. ALL (full scan, bad) → index → range → ref → eq_ref/const (best).
key — the index MySQL actually picked (not just what's available).
rows — estimated rows scanned. Lower is better.
Extra — Using index (covering, great), Using filesort (expensive manual sort), Using temporary (temp table, expensive).

If you only remember one thing: type = ALL plus a high rows count means you're looking at a full table scan, and that's usually your cue to add an index.
When an index quietly gets ignored
A few common reasons MySQL won't use an index even when one exists:

Wrapping the column in a function — WHERE YEAR(created_at) = 2026 can't use an index on created_at, because the engine would have to compute YEAR() on every row first. Rewriting as a range (created_at BETWEEN '2026-01-01' AND '2026-12-31') fixes it.
Leading wildcard — LIKE '%something' can't use a B+Tree, since the tree is ordered from the first character.
Type mismatches — comparing a string column to an implicit numeric conversion silently disables the index.
Stale statistics — the optimizer's cost estimates come from ANALYZE TABLE; if it hasn't run recently, its decisions can be wrong.

Practical rules for when (not) to index
Index columns that show up in WHERE, JOIN, or frequent ORDER BY/GROUP BY — especially ones with high selectivity. Skip indexing tiny tables, low-selectivity columns on their own (booleans, 2-3 value enums), or columns that get written far more than they're read. Every index you add makes every INSERT/UPDATE/DELETE on that table slightly slower, since the engine has to update every affected index's B+Tree, sometimes triggering a page split. More indexes isn't automatically better — it's a trade-off you should be able to justify with an actual query pattern, not a guess.
Closing thought
The engineering mindset here isn't "does this column deserve an index" in isolation — it's "what queries actually hit this table, and what's the right trade-off between read speed, write cost, and storage, based on real data." Measure with EXPLAIN and your slow query log first, index second, and re-measure after.

If you're building anything transaction-heavy — payments, reconciliation, ledgers — this trade-off matters even more, since those tables tend to be both write-heavy and query-heavy at the same time. Happy to go deeper into that in a follow-up if there's interest.