Explaining Indexes with a Library MetaphorJonathan Levin
My favorite metaphor for explaining indexes is comparing them to index cards in an old library. In an old library, you used to (or still do) have index cards at the front desk which have some brief description of the books in the library. They also used to be categorized alphabetically.
(image taken from http://www.flickr.com/photos/reedinglessons/2239767394/)
Let’s pretend that you are simulating an application that is trying to find a book with a certain title in the library.
Not using an index
If you are not using the index cards, you would have to go shelf by shelf and row by row, look at each book’s title and see if its the one you need. This is very time consuming and is similar to how a database looks at blocks on the hard disk when its not using an index.
Using an index
You are interested in a book by J.R. Hartley. You go to the index card, you look at section H (categorized by last name of author) and browse through the list till you find Hartley, J.R. You get back the description of the shelf and row in which these books can be found. You then walk over to the right shelf and the right row, go over the books in that row till you find the ones you want.I’m sure you can imagine that this step would be much faster.
Using an index with range scans
You would like to count how many books J.R. Hartley has ever written. You goto the index cards, look up section H, find Hartley and count all the index cards that have Hartley, J.R in the title. You then find that J.R. Hartley has written 4 books. You have your result and you have saved yourself from walking over to the shelves.
Using a covering index
You are interested to know how many pages a certain book by J.R. Hartley has. You go over to the index cards, open section H, go over the index cards till you find the right book. Now on these particular cards, the number of pages of the book is written on them. You get your result and saved yourself from walking over to the right shelf, finding the book and seeing how many pages it has.
If you imagine yourself doing these tasks, you can imagine how long they might take to complete. It is not entirely different from the tasks the database has to do.
I hope this metaphor has helped you understand indexes better (if you were not sure about them before) and I also hope that you will enjoy using it in the future.