At a high level, a SQL index is very similar to the index at the back of a textbook.
Without an index, if you want to find every mention of "B-trees," you flip through every page until you find it. That's a full table scan.
With an index, you look up "B-trees" alphabetically, jump directly to the page numbers, and then go straight to those pages.
The same idea applies to databases—but the data structures are much more sophisticated.
Without an index
Imagine a table:
| id | name | age |
|---|
| 1 | Alice | 32 |
| 2 | Bob | 25 |
| 3 | Charlie | 41 |
| ... | ... | ... |
| 10,000,000 | Zoe | 29 |
Now run:
SELECT * FROM users
WHERE name = 'Charlie';
If there's no index on name, the database has only one option:
Alice? No.
Bob? No.
Charlie? Yes.
David? Keep going...
...
Worst case it examines every row.
Time complexity is roughly:
O(n)
where n is the number of rows.
With an index
Suppose we create one:
CREATE INDEX idx_users_name
ON users(name);
The database builds a separate structure that looks conceptually like:
Alice -> Row 5012
Bob -> Row 18
Charlie-> Row 7721
David -> Row 942
...
Notice:
- the table itself isn't rearranged
- the index is stored separately
- it points to where rows live
But how is the index stored?
Most SQL databases (PostgreSQL, MySQL InnoDB, SQL Server, Oracle) use a B-tree by default.
Not a binary tree.
A B-tree.
Why?
Because databases care far more about disk access than CPU instructions.
A binary search tree would be terrible
A binary tree might look like
M
/ \
G T
/ \ / \
C J P Z
To find "Charlie":
M
↓
G
↓
C
Nice.
But if there are 100 million rows, every node might require another disk read.
That would be incredibly slow.
B-trees are much wider
Instead of 2 children...
A B-tree node might have hundreds.
[A G M T Z]
/ | | \
Each node contains many keys.
For example:
[Aaron]
[Alice]
[Bob]
[Charlie]
[David]
...
When searching:
- Read one node.
- Decide which child contains your value.
- Read that child.
- Repeat.
Because each node is so large, the tree stays very shallow.
Even with millions of rows:
Root
↓
Intermediate
↓
Leaf
Only about 3–5 page reads may be needed.
Why is this so much faster?
Suppose:
100 million rows
Full scan:
100,000,000 comparisons
B-tree:
Root
↓
Child
↓
Leaf
≈ 3–5 page reads
The complexity becomes approximately:
O(log n)
instead of
O(n)
What do the leaves contain?
Typically something like
Alice
-> row #12
Bob
-> row #98
Charlie
-> row #771
David
-> row #542
The leaf stores:
- indexed value
- pointer (or row identifier)
- sometimes the row itself (depending on the database and index type)
Example search
Suppose you ask:
SELECT *
FROM users
WHERE name = 'Charlie';
The database:
Root
[A G M T]
Charlie < G?
No.
Charlie < M?
Yes.
Go left-middle.
Second node:
[H J L]
Charlie < H
Yes.
Third node:
[Alice]
[Bob]
[Charlie]
[David]
Found.
Jump directly to the row.
Done.
No need to inspect the other 9,999,999 rows.
Range queries are even better
Suppose:
SELECT *
FROM users
WHERE age BETWEEN 20 AND 30;
The leaves of a B-tree are linked together:
20
↓
21
↓
22
↓
23
↓
24
↓
...
↓
30
The database:
- Finds 20.
- Walks sequentially until 30.
No rescanning the whole table.
That's why B-trees are excellent for:
<
>
BETWEEN
ORDER BY
Why not use a hash table?
Hash indexes are great for exact matches.
Charlie
↓
Hash
↓
Bucket 42
↓
Found
This is often close to:
O(1)
But hash indexes can't efficiently answer:
age > 30
or
ORDER BY age
because hashing destroys the ordering.
That's why B-trees are the default in most relational databases: they support both equality and ordered lookups well.
What is the cost of indexes?
Indexes aren't free.
Every insert:
INSERT INTO users ...
must:
- insert into the table
- insert into every relevant index
Likewise, updates and deletes may require modifying the indexes.
So indexes make reads faster but usually make writes slower and consume additional storage.
Composite indexes
Suppose you frequently run:
SELECT *
FROM users
WHERE last_name = 'Smith'
AND first_name = 'John';
Instead of two separate indexes:
last_name
first_name
you might create:
CREATE INDEX idx_name
ON users(last_name, first_name);
The index is sorted like:
Adams, Amy
Adams, Bob
Brown, Alice
Brown, John
Smith, Adam
Smith, John
Smith, Mary
The database can quickly navigate to:
Smith
↓
John
This is usually much faster than combining two independent indexes.
Why indexes speed things up so dramatically
The biggest performance gain comes from avoiding unnecessary work. Reading data from storage (or even from memory) is much slower than comparing a few values in a small tree.
Instead of:
Scan every row
1
2
3
4
5
...
100,000,000
an index lets the database do something closer to:
Root
↓
Branch
↓
Leaf
↓
Target row
By reducing the search from a linear scan to a handful of tree traversals, the database touches far fewer data pages. That's why an indexed lookup on a large table can complete in milliseconds, while the same query without an index may take seconds or longer.
