Question
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.
Answer
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.
