How Database Indexing Works

What is Indexing?

📚Without Index — Full Table Scan

P1

→

P2

→

P3

→

...

→

P6

→

P7

Read every page sequentially until you find what you need — like flipping through an entire book page by page.

7 pages checkedO(n)

📖With Index — Direct Lookup

INDEX

→

P7

Look up the term in the index at the back of the book, then jump directly to the right page.

1 page checkedO(log n)

🎯

What is an Index?

A separate data structure that stores a sorted copy of selected columns alongside pointers to the actual rows.

⚡

Why use Indexes?

Without an index, the database must scan every row. With one, it traverses a tree — reducing reads from billions to ~5.

⚙️

How does it work?

A B-tree keeps data sorted. Each level narrows the search range by following the correct branch — like a decision tree.

Visualization

Watch both approaches side by side for the same query — see how many rows the full table scan checks vs how few nodes the B-tree visits:

0 / 13

Without Index — Full Table Scan

SELECT * FROM users WHERE email = 'alice@mail.com'

#	Name	Email
1	Emma	emma@mail.com
2	Liam	liam@mail.com
3	Sophia	sophia@mail.com
4	Noah	noah@mail.com
5	Olivia	olivia@mail.com
6	James	james@mail.com
7	Alice	alice@mail.com
8	Bob	bob@mail.com
9	Carol	carol@mail.com
10	Dave	dave@mail.com

With B-tree Index — Tree Traversal

SELECT * FROM users WHERE email = 'alice@mail.com'

[ dave | sophia ]

┌─────────────┼─────────────┐

[ bob ]

[ james ]

[ noah ]

┌────┼────┐

alice, bob

carol, dave

emma, james

Waiting for table scan to progress...

Types of Indexes

🌳

B-tree

Default in most databases. Sorted structure supports range queries.

WHERE, ORDER BY, JOIN

#️⃣

Hash

O(1) exact match lookup using a hash table.

Equality only (=)

📊

Bitmap

Bit arrays for low-cardinality columns.

Data warehousing

🔗

Composite

Index on multiple columns — column order matters.

Multi-column WHERE

📦

Covering

Includes all queried columns — avoids table lookups entirely.

Index-only scans

🔑

Unique

Enforces uniqueness on column values.

Primary keys

Index Scan Strategies

The query optimizer chooses between these strategies based on cost estimates:

Index SeekFastest

B-tree traversal to find specific rows directly.

Index ScanFast

Read the entire index in order. Faster than table scan when index covers the query.

Full Table ScanSlowest

Read every row sequentially. Sometimes faster than index when selecting most rows.

Key Takeaways

🐢

Without Index

Every row is checked sequentially — O(n) — painfully slow for large tables.

🚀

With B-tree Index

The tree narrows the search at each level — only a few nodes visited — O(log n).

⚖️

Trade-off

Indexes speed up reads but slow down writes — every INSERT/UPDATE/DELETE must update the index too.

💾

Storage Cost

Indexes consume additional disk space — typically 10-20% of table size.

🌲

B-tree Depth

For 1 billion rows with branching factor 100 → only ~4-5 levels needed.

When to Index vs When NOT to

✅ When to Index

✓🔍Columns frequently used in WHERE clauses

✓🔗Columns used in JOIN conditions

✓📊Columns used in ORDER BY or GROUP BY

✓📈High cardinality columns (many distinct values)

❌ When NOT to Index

✗📭Tables with few rows (scan is fast enough)

✗🔄Low cardinality (e.g. boolean — index won't help)

✗✍️Heavy write workloads (each write updates every index)

✗🔁Frequently updated columns (maintenance cost is high)

How B-tree Indexes Work (Deep Dive)

The most common index type is the B-tree (Balanced Tree). It keeps data sorted and allows searches, insertions, and deletions in O(log n) time:

1. The root node contains keys that divide the data into ranges
2. Each child node narrows the range further
3. Leaf nodes contain the actual values and row pointers
4. The tree stays balanced — all leaf nodes are at the same depth

For example, searching 1 billion rows with a branching factor of 100 requires only ~4-5 levels — that's 4-5 disk reads instead of 1 billion.

Learn More

Read the full theory in Database Design > Indexing.