why does adding an index on something you sort by decrease the amount of work in sorting?

Question

From here: http://dev.mysql.com/doc/refman/5.0/en/order-by-optimization.html

In some cases, MySQL can use an index to satisfy an ORDER BY clause without doing any extra sorting.

I thought indexes helped with retrieving specific pieces of data (like the indexes in array) giving you a O(1) instead of O(n) when indexed. But when sorting, I assumed they use whatever O(nlogn) or something algorithm based on the sorting column, however apparently indexing the columns you sort by can decrease the amount of work involve.

How does this work? ( I am not sure if this is a general SQL thing or a MySQL thing either )

Answer 1

Performing a lookup of a single row in an index is likely an O(log n) operation or thereabouts.

When reading through an index in 'sort order', however, you're typically performing a tree- or even list- traversal, and this'll be O(n). If the index contains all of the information needed to satisfy the output of the query, this'll be considerably faster than reading and sorting the data.

This is a general SQL thing, not specific to MySQL.

Answer 2

A simple answer: Generally, indexes are themselves stored in sorted order (otherwise, using an index to quickly find a record would be extremely difficult!) Hence, "in some cases" (when an ORDER BY matches the sort order of an index), the data can be returned via its index order, "without doing any extra sorting".

Further: As @Will A's answer reminded me, you may wish to learn about covering indexes, which extend this concept.