How database indexes work

A database index is a sorted structure, usually a B-tree, that lets a query jump to matching rows instead of reading the whole table.

1
Without an index, read everything
To find one email in an unsorted table, the database has to check every row. That's fine for 12 rows and slow for millions.
2
An index is a sorted tree
The index keeps the emails sorted in a tree. The root holds separator keys, and the leaves hold every key with a pointer to its row.
3
Search by following branches
To find kai, compare with the root's keys and go down the one branch that can contain it. A few reads replace a full scan.
4
Ranges are cheap too
Leaves are linked in order, so a range like kai to ned walks from leaf to leaf without going back to the root.
5
Writes pay the cost
Every insert must also go into each index. When a leaf is full it splits and the parent gains a key. More indexes, slower writes.

To find one email in an unsorted table, the database has to check every row. That's fine for 12 rows and slow for millions.

The index keeps the emails sorted in a tree. The root holds separator keys, and the leaves hold every key with a pointer to its row.

To find kai, compare with the root's keys and go down the one branch that can contain it. A few reads replace a full scan.

Leaves are linked in order, so a range like kai to ned walks from leaf to leaf without going back to the root.

Every insert must also go into each index. When a leaf is full it splits and the parent gains a key. More indexes, slower writes.

In short

Index the columns you filter, join and sort on, and check the query plan (EXPLAIN) to confirm the index is used.
Real B-tree nodes hold hundreds of keys, so a million rows needs only about 3 or 4 levels.
A composite index on (a, b) helps queries on a, or on a and b together, but not on b alone.