To understand what indexes allow MySQL to do, it’s best to think about how MySQL works to answer a query. Imagine that phone_book is a table containing an aggregate phone book for the state of California, with roughly 35 million entries. And keep in mind that records within tables aren’t inherently sorted. Consider a query like this one:
SELECT * FROM phone_book WHERE last_name = ‘Zawodny’
Without any sort of index to consult, MySQL must read all the records in the phone_book table and compare the last_name field with the string “Zawodny” to see whether they match. Clearly that’s not efficient. As the number of records increases, so does the effort necessary to find a given record. In computer science, we call that an O(n) problem.
But given a real phone book, we all know how to quickly locate anyone named Zawodny: flip to the Zs at the back of book and start there. Since the second letter is “a,” we know that any matches will be at or near the front of the list of all names starting with Z. The method used is based on knowledge of the data and how it is sorted.
That’s cheating, isn’t it? Not at all. The reason you can find the Zawodnys so quickly is that they’re sorted alphabetically by last name. So it’s easy to find them, provided you know your ABCs, of course.
Most technical books (like this one) provide an index at the back. It allows you to find the location of important terms and concepts quickly because they’re listed in sorted order along with the corresponding page numbers. Need to know where mysqlhotcopy is discussed? Just look up the page number in the index.
Database indexes are similar. Just as the book author or publisher may choose to create an index of the important concepts and terms in the book, you can choose to create an index on a particular column of a database table. Using the previous example, you might create an index on the last name to make looking up phone numbers faster:
ALTER TABLE phone_book ADD INDEX (last_name)
In doing so, you’re asking MySQL to create an ordered list of all the last names in the phone_book table. Along with each name, it notes the positions of the matching records—just as the index at the back of this book lists page numbers for each entry.[1]
[1] That’s a bit of a lie. MySQL doesn’t always store the position of the matching records. We’ll see why soon enough.
From the database server’s point of view, indexes exist so that the database can quickly eliminate possible rows from the result set when executing a query. Without any indexes, MySQL (like any database server) must examine every row in a table. Not only is that time consuming, it uses a lot of disk I/O and can effectively pollute the disk cache.
In the real world, it’s rare to find dynamic data that just happens to be sorted (and stays sorted). Books are a special case; they tend to remain static.
Because MySQL needs to maintain a separate list of indexes’ values and keep them updated as your data changes, you really don’t want to index every column in a table. Indexes are a trade-off between space and time. You’re sacrificing some extra disk space and a bit of CPU overhead on each INSERT, UPDATE, and DELETE query to make most (if not all) your queries much faster.
Much of the MySQL documentation uses the terms index and key interchangeably. Saying that last_name is a key in the phone_book table is the same as saying that the last_name field of the phone_book table is indexed.
