How do MySQL indexes work?

I am really interested in how MySQL indexes work, more specifically, how can they return the data requested without scanning the entire table?

It's off-topic, I know, but if there is someone who could explain this to me in detail, I would be very, very thankful.

 Answers

Basically an index on a table works like an index in a book (that's where the name came from):

Let's say you have a book about databases and you want to find some information about, say, storage. Without an index (assuming no other aid, such as a table of contents) you'd have to go through the pages one by one, until you found the topic (that's a full table scan). On the other hand, an index has a list of keywords, so you'd consult the index and see that storage is mentioned on pages 113-120,231 and 354. Then you could flip to those pages directly, without searching (that's a search with an index, somewhat faster).

Of course, how useful the index will be, depends on many things - a few examples, using the simile above:

• if you had a book on databases and indexed the word "database", you'd see that it's mentioned on pages 1-59,61-290, and 292 to 400. In such case, the index is not much help and it might be faster to go through the pages one by one (in a database, this is "poor selectivity").
• For a 10-page book, it makes no sense to make an index, as you may end up with a 10-page book prefixed by a 5-page index, which is just silly - just scan the 10 pages and be done with it.
• The index also needs to be useful - there's generally no point to index e.g. the frequency of the letter "L" per page.

---

Basically an index is a map of all your keys that is sorted in order. With a list in order, then instead of checking every key, it can do something like this:

1: Go to middle of list - is higher or lower than what I'm looking for?

2: If higher, go to halfway point between middle and bottom, if lower, middle and top

3: Is higher or lower? Jump to middle point again, etc.

Using that logic, you can find an element in a sorted list in about 7 steps, instead of checking every item.

Obviously there are complexities, but that gives you the basic idea.

---

Take a look at this link: http://dev.mysql.com/doc/refman/5.0/en/mysql-indexes.html

How they work is too broad of a subject to cover in one SO post.

Here is one of the best explanations of indexes I have seen. Unfortunately it is for SQL Server and not MySQL. I'm not sure how similar the two are...