Предположим, мне нужно обрабатывать таблицу в том порядке, при котором значения из поля ClientName будут выстроены по алфавиту. При этом у меня есть индекс, в котором значения из этого поля выстроены именно по алфавиту. Тогда свою работу я смогу выполнять так же быстро, как если бы сами записи таблицы данных были выстроены в том же порядке. У меня есть возможность последовательно перемещаться по строкам индекса и при этом немедленно переходить, используя указатель индекса, на те строки таблицы данных, которые соответствуют строкам индекса.
При использовании индекса время обработки таблицы пропорционально N, где N — количество ее строк. А при выполнении той же операции, но без индекса, время обработки таблицы
пропорционально NlgN, где igN — логарифм N по основанию 2. Для небольших таблиц разница между этими значениями получается незначительная, но для больших — огромная. Некоторые операции с большими таблицами без помощи индексов требуют слишком много времени.
Например, у вас есть таблица с 1000000 записей (N = 1000000) и на обработку каждой записи уходит одна миллисекунда (одна тысячная секунды). Если у вас есть индекс, то на обработку всей таблицы уйдет только 1000 секунд, т.е. меньше 17 минут. Однако, чтобы получить тог же результат без индекса, таблицу придется обрабатывать 100000x20 раз. Таким образом, этот процесс должен занять 20000 секунд, т.е. больше пяти с половиной часов. Думаю, вы согласитесь, что разница между семнадцатью минутами и пятью с половиной часами довольно-таки существенная. Это и есть та разница, которая создается индексированием записей.