почему добавление индекса для сортируемой информации уменьшает объем работы по сортировке?

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, вы можете узнать о индексах покрытия , что расширяет эту концепцию.

Answer 2

Выполнение поиска одной строки в индексе, вероятно, является операцией O (log n) или около того.

Однако при чтении индекса в «порядке сортировки» обычно выполняетсяобход дерева или даже списка, и это будет O (n).Если индекс содержит всю информацию, необходимую для удовлетворения результатов запроса, это будет значительно быстрее, чем чтение и сортировка данных.

Это общая вещь SQL, не относящаяся к MySQL.