«Индекс ускоряет выполнение запроса» — это самое простое объяснение индекса, которое я когда-либо видел. Хотя оно очень хорошо описывает наиболее важный аспект индекса, для этой книги оно, к сожалению, недостаточно.
Индекс — это отдельная структура в базе данных, которая создается с помощью оператора create index. Он требует собственного дискового пространства и содержит копию данных индексируемой таблицы. Это означает, что индекс — это чистая избыточность. Создание индекса не изменяет данные таблицы; оно просто создает новую структуру данных, которая ссылается на таблицу. В конце концов, индекс базы данных очень похож на указатель в конце книги: он занимает собственное пространство, является сильно избыточным и ссылается на фактическую информацию, хранящуюся в другом месте.
Поиск в индексе базы данных подобен поиску в печатном телефонном справочнике. Ключевая концепция заключается в том, что все записи расположены в четко определенном порядке. Поиск данных в упорядоченном наборе данных выполняется быстро и легко, потому что порядок сортировки определяет положение каждой записи.
Однако индекс базы данных сложнее бумажного справочника, поскольку он постоянно меняется. Обновлять справочник при каждом изменении невозможно по простой причине: между существующими записями нет места для добавления новых. Данная проблема обходится только при следующей печати. SQL-база данных не может ждать так долго. Она должна немедленно обрабатывать операции вставки, удаления и обновления, сохраняя порядок индекса без перемещения больших объемов данных.
Для решения этой задачи база данных сочетает две структуры данных: двусвязный список и дерево поиска. Эти две структуры объясняют большинство характеристик производительности базы данных.
Больше про индексы найдете здесь https://dzen.ru/a/ZnR6UpVdxyL1PkV2