Database Indexes
How a Database Index Finds Rows
A database index is a separate data structure that lets the database locate rows matching a condition without reading the whole table. It works much like the index at the back of a book, which points you to the pages for a given topic.
Without an index, a query that searches for one customer's email address has to check every row in the table. This is called a full table scan, and it becomes slow as the table grows. With an index on the email column, the database keeps the values in sorted order inside a structure, most often a B-tree or a close variant, and follows a short path from the top of the structure down to the matching value.
A B-tree can be thought of as a phone book split into sections, with signposts that show which section to open next. Each step narrows the search, so finding one value among millions of rows usually takes only a few steps.
Clustered and Non-Clustered Indexes Compared
Indexes come in two broad forms, and the difference lies in how they relate to the stored rows.
- Clustered index decides the physical order in which the table's rows are stored. A table can have only one, because rows can be sorted in only one order on disk. In InnoDB, the storage engine that MySQL and MariaDB use by default, the primary key usually acts as the clustered index.
- Non-clustered index, also called a secondary index, is a separate structure. It stores the indexed values along with a reference back to the full row. A table can have many of these.
A lookup through a non-clustered index often needs one extra step, because the database must go back to the table to read the columns the index does not hold.
The Trade-Off Between Read and Write Speed
Indexes make reads faster, but they are not free. Each index takes up storage space, and the database must update it whenever rows are inserted, changed or deleted. A table with many indexes can therefore slow down writes, even while searches run quickly.
Consider an orders table where customers often look up their past orders. An index on the customer ID column makes those lookups quick. Every new order, however, also has to add an entry to that index. If the same table carries five more indexes that nobody uses, the store pays the cost of maintaining them on every write and gets nothing back.
A sensible approach is to index the columns that appear most often in filters, sorting and joins, and to review the indexes when query patterns change.
Frequently asked questions
Does adding an index always make a database faster?
No. An index helps queries that filter, sort or join on the indexed columns, but it does not speed up queries that ignore them. Indexes also need storage and slow down inserts, updates and deletes. To find out what is slow in the first place, read about common causes of slow queries.
What is the difference between a clustered and a non-clustered index?
A clustered index sets the physical order of a table's rows, and a table can have only one. A non-clustered index is a separate structure that points back to the rows, and a table can have several. Lookups that use the clustered key read the row directly, while non-clustered lookups often take an extra step.
Are primary keys indexed automatically?
In most relational databases, yes. Declaring a primary key creates a unique index on that column, which lets the database enforce uniqueness and find rows by key quickly. Other columns, such as email addresses used for login, are not indexed automatically and need an index of their own if they are searched often. See primary and foreign keys for how keys work.