为什么在排序的东西上添加索引会减少排序中的工作量？

Question

从这里: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.

我认为索引有助于检索特定的数据片段(比如数组中的索引),在索引时会给你一个O(1)而不是O(n).但是在排序时,我假设它们使用基于排序列的任何O(nlogn)或某种算法,但是显然索引排序的列可以减少涉及的工作量.

这是如何运作的？(我不确定这是一般的SQL还是MySQL的事情)

Answer 1

一个简单的答案:通常,索引本身按排序顺序存储(否则,使用索引快速查找记录将非常困难!)因此,"在某些情况下"(当ORDER BY与索引的排序顺序匹配时) ,数据可以通过其索引顺序返回,"无需进行任何额外的排序".

进一步:正如@Will A的答案提醒我的那样,您可能希望了解覆盖索引,从而扩展这一概念.