Joe Celko's SQL for Smarties, 3rd Edition

33.11. Learn to Use Indexes Carefully

By way of review, most indexes are tree structures. They consist of a page or node that has values from the columns of the table from which the index is built, and pointers. The pointers point to other nodes of the tree and eventually point to rows in the table that has been indexed. The idea is that searching the index is much faster than searching the table itself in a sequential fashion (called a table scan).

The index is also ordered on the columns used to construct it; the rows of the table may or may not be in that order. When the index and the table are sorted on the same columns, the index is called a clustered index. The best example of this in the physical world is a large dictionary with a thumb-notch ...