What Is an Index?

An index is a separate, sorted structure that lets MySQL find rows without reading the whole table.

The best comparison is the index at the back of a book. To find every page that mentions “transaction”, you do not read all 600 pages. You look up the word in the alphabetical index, which tells you “pages 212, 218, 340”, and you jump straight there.

Without an index, MySQL does the equivalent of reading every page: a full table scan. With an index, it does a quick lookup.

See the difference

Let us build a table with 50,000 rows.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

SET SESSION cte_max_recursion_depth = 100000;

CREATE TABLE customers (
    id INT AUTO_INCREMENT PRIMARY KEY,
    email VARCHAR(80) NOT NULL,
    city VARCHAR(30) NOT NULL,
    created_at DATE NOT NULL
);

INSERT INTO customers (email, city, created_at)
WITH RECURSIVE n AS (SELECT 1 AS i UNION ALL SELECT i + 1 FROM n WHERE i < 50000)
SELECT CONCAT('user', i, '@example.com'),
       ELT(1 + MOD(i, 5), 'Pune', 'Delhi', 'Kochi', 'Jaipur', 'Surat'),
       DATE_ADD('2024-01-01', INTERVAL MOD(i, 700) DAY)
FROM n;

ANALYZE TABLE customers;

Look up one customer by email. There is no index on email, yet:

1

EXPLAIN FORMAT=TRADITIONAL SELECT id, city FROM customers WHERE email = 'user31337@example.com';

1
2
3
4
5
6

+----+-------------+-----------+------------+------+---------------+------+---------+------+-------+----------+-------------+
| id | select_type | table     | partitions | type | possible_keys | key  | key_len | ref  | rows  | filtered | Extra       |
+----+-------------+-----------+------------+------+---------------+------+---------+------+-------+----------+-------------+
|  1 | SIMPLE      | customers | NULL       | ALL  | NULL          | NULL | NULL    | NULL | 50063 |    10.00 | Using where |
+----+-------------+-----------+------------+------+---------------+------+---------+------+-------+----------+-------------+
1 row in set

type: ALL means full table scan. rows is about 50,000: MySQL must look at every row to find the one you want. The key column is NULL because no index is used.

Now add an index on email and ask the same question:

1
2

CREATE INDEX idx_email ON customers (email);
EXPLAIN FORMAT=TRADITIONAL SELECT id, city FROM customers WHERE email = 'user31337@example.com';

1
2
3
4
5
6

+----+-------------+-----------+------------+------+---------------+-----------+---------+-------+------+----------+-------+
| id | select_type | table     | partitions | type | possible_keys | key       | key_len | ref   | rows | filtered | Extra |
+----+-------------+-----------+------------+------+---------------+-----------+---------+-------+------+----------+-------+
|  1 | SIMPLE      | customers | NULL       | ref  | idx_email     | idx_email | 322     | const |    1 |   100.00 | NULL  |
+----+-------------+-----------+------------+------+---------------+-----------+---------+-------+------+----------+-------+
1 row in set

type: ref, key: idx_email and rows: 1. MySQL reads about one entry instead of fifty thousand. On a table with fifty million rows, the difference is the difference between a millisecond and a minute.

How it works: the B-tree

MySQL (InnoDB) stores most indexes as a B-tree, a balanced tree of sorted values:

1
2
3
4
5

                [ M ]                      <- root: a few keys, pointers to children
              /       \
        [ D  H ]       [ R  V ]            <- branch pages
        /  |  \         /  |  \
     [A-C][E-G][I-L]  [N-Q][S-U][W-Z]      <- leaf pages: the sorted values, with row pointers

To find a value, MySQL starts at the root, follows one pointer per level and reaches the right leaf after 3 or 4 steps, even for hundreds of millions of rows. Each step is a page read. Because the leaf pages are sorted and linked, the index also answers:

• Ranges: WHERE created_at BETWEEN ... AND ... (read leaves in order).
• Sorting: ORDER BY email (the data is already in order).
• Min and max: first or last leaf.
• Prefix searches: WHERE email LIKE 'user31%'.

It does not help with LIKE '%example.com' (no known starting point) or with a function applied to the column.

What the index stores

• A secondary index (like idx_email) stores the indexed values plus the primary key of each row. To get other columns, MySQL looks up the primary key in the main table (the “clustered index”). That extra step is the cost of a normal index lookup.
• The primary key is special in InnoDB: the table itself is the primary key B-tree (PRIMARY KEY).

The price of an index

An index is not free:

1
2
3
4
5

ANALYZE TABLE customers;
SET SESSION information_schema_stats_expiry = 0;
SELECT table_name, ROUND(data_length / 1024) AS data_kb, ROUND(index_length / 1024) AS index_kb
FROM information_schema.tables
WHERE table_schema = 'learn' AND table_name = 'customers';

1
2
3
4
5
6

+------------+---------+----------+
| TABLE_NAME | data_kb | index_kb |
+------------+---------+----------+
| customers  |    3600 |        0 |
+------------+---------+----------+
1 row in set

(The sizes depend on the server, so this block is not compared.) (information_schema caches table statistics for 24 hours by default, so the query sets information_schema_stats_expiry = 0 to see current numbers.) The email index adds a noticeable amount to the table size. An index on a text column is large, an index on a small integer is small.

The rule of thumb

> Index the columns you search by, join on and sort by, on tables that are big enough to matter. Do not index everything.

On a table with 100 rows, a full scan is as fast as an index lookup. Indexes pay off on tables with thousands of rows and more, and for queries that run often.

Every table already has one

The primary key is an index. A UNIQUE constraint is an index. A foreign key creates an index on the child column if none exists. You get these without writing CREATE INDEX.

What comes next

The next lessons show how to create indexes, how to design multi-column indexes, and how to find out why a query is not using an index.