Database Indexing - Will Cygan

An index helps a database find rows without checking every row. Indexes can reduce the work a query needs to do, but they use storage and add work to writes.

These examples use MySQL's InnoDB engine. The people table has an id, a name, and a city. Its primary key, id, uniquely identifies each row.

Table scans

A full table scan examines every row to find those that match a query. The people table is ordered by id. To find every person named Zoe, the database checks each row's name.

Table Scan

SELECT * FROM people WHERE name = 'Zoe'

0 of 9 rows checked

Index and page routing

InnoDB's indexes use a B-tree structure. The tree groups index entries into pages. Branch pages contain routing keys that direct a lookup to a child page. Leaf pages contain the entries.

For id = 9, a routing key directs the lookup to the last leaf page. The database skips the other leaf pages.

Tree Lookup

SELECT * FROM people WHERE id = 9

Leaf pages are linked in key order. A range query can find its first matching entry, then follow neighboring leaf pages until it reaches the end of the range.

Secondary indexes

InnoDB stores full rows in the leaves of its primary index, ordered by the primary key. A secondary index provides another order for finding those rows.

An index on name stores names alongside primary keys, such as Zoe → 9. To fetch Zoe's full row, the database looks up Zoe in the name index to get ID 9, then looks up that ID in the primary index.

Secondary Lookup

SELECT * FROM people WHERE name = 'Zoe'

Covering indexes

A covering index contains all the columns a particular query needs. The name index already contains name and the primary key, id, so a query for those two columns can read them from the name index alone. It avoids the second lookup shown above.

Covering Index

SELECT name, id FROM people WHERE name = 'Zoe'

Whether an index covers a query depends on the columns the query needs. Adding city to the result would require fetching the row, because the name index does not contain that value.

Composite indexes

A composite index is defined on more than one column. An index on (city, name) sorts entries by city first, then by name within each city.

All Austin entries sit together. Zoe can appear in several city groups, so a search by name alone does not identify one continuous range of entries.

Column Order

WHERE city = 'Austin'

This grouping resembles partitioning: specifying a city narrows the search to that city's names. Here, the groups are ranges within one ordered index. Table partitioning divides the table's rows into separate storage partitions.

Choose column order to support the filters and sorting your queries use.

Paying for faster reads

An insert adds an entry to the primary index and every secondary index. Updating an indexed value also changes its index entry. Each additional index uses storage and adds work to writes.

Write Cost

INSERT INTO people VALUES (9, 'Zoe', 'Boston')

The demo counts index entries, not physical disk writes. An index needs to skip enough work to help: fetching most rows through a secondary index can cost more than scanning the table.

Comparing real access paths

Different access paths can return the same rows while doing different amounts of work. Compare the rows each path examines and its execution time.

Use EXPLAIN to inspect the access path and estimated row counts for your application's queries. For a SELECT you can safely run, EXPLAIN ANALYZE executes the query and reports actual row counts and timing. Check these plans before adding another index.

Code examples

The conceptual-database crate contains three runnable Rust examples, an HTTP API, and a MySQL comparison script. All links below point to the same pinned revision.

The Rust examples store rows in an in-memory hash map and keep secondary indexes of row IDs. Their row and index counts represent logical work. They do not model InnoDB disk I/O or covering reads.

Indexing walkthrough demonstrates primary and secondary lookups, date ranges, latest orders, forced scans, and rollback of a failed batch.
- Secondary lookups read row IDs from an index, then fetch their rows from the primary map.
- Composite ordering groups entries by customer, then date, then order ID.
- Index maintenance updates the primary map and four secondary indexes for every new order.

Access-path comparison loads one million generated orders and compares five ways to answer the same query:

SELECT * FROM orders
WHERE product_id = 7
  AND state = 'cancelled';

Every access path returns the same 24 orders, but reads different numbers of index entries and rows:

Access path	Index entries read	Rows fetched
Full scan	0	1,000,000
State index, then filter by product	20,087	20,087
Product index, then filter by state	886	886
Intersect the product and state indexes	20,962	24
Composite product/state index	24	24

Index intersection walks two ordered ID lists and fetches rows whose IDs appear in both.
Work counters report index entries read and full rows fetched. These counts are from the Rust program, not MySQL measurements.

Run the pinned version with Rust installed:

git clone https://github.com/wcygan/examples.git
cd examples
git checkout --detach 3205ebd3742799518de1e3c616fe218d9c90d5dd
cargo run --release --locked -p conceptual-database --example index_strategies

Tree implementation comparison compares database workloads using Rust's standard B-tree and bbtree.
- Swapping trees rebuilds the indexes with the other tree and checks that query results stay the same.
HTTP API examples show requests for seeding rows, querying indexes, and comparing forced scans. The setup commands include starting the server.
MySQL 8.4 comparison creates an InnoDB orders table, generates data, and compares access paths with EXPLAIN ANALYZE. Run it in a disposable database: it drops and recreates orders. Its data generator differs from the Rust examples, so its row counts differ from the table above. Inspect the resulting plans to see which indexes MySQL actually uses.