Вопрос проверяет понимание фундаментальной структуры данных, лежащей в основе индексов в базах данных, и принципа их работы для ускорения поиска.
Индекс в базе данных чаще всего реализуется с помощью структуры данных "B-дерево" (или его разновидности B+дерево). Это сбалансированное дерево поиска, которое позволяет быстро находить данные по значению ключа. Оно хранит ключи в отсортированном порядке, что также ускоряет операции поиска по диапазону и сортировку.
Индекс можно сравнить с алфавитным указателем в конце книги. Вместо того чтобы перелистывать всю книгу (таблицу) в поисках термина (строки), вы открываете указатель (индекс), находите термин и сразу видите номер страницы (указатель на строку).
B+дерево как основная структура индекса:
Сбалансированность: Все листья дерева находятся на одинаковой глубине. Это гарантирует, что время доступа к любой записи будет предсказуемым и быстрым (логарифмическая сложность O(log n)).
Многоуровневость: Дерево состоит из корневого узла, внутренних узлов и листовых узлов.
Листовые узлы:
Содержат ключи (значения индексируемых столбцов) и указатели на соответствующие строки данных в таблице.
Листовые узлы связаны друг с другом в виде двусвязного списка. Это делает очень эффективным поиск по диапазону значений (например, WHERE date BETWEEN '2020-01-01' AND '2020-01-31'), так как не нужно возвращаться к корню дерева.
Как работает поиск по индексу:
Поиск начинается с корневого узла.
В узле находится диапазон, в который попадает искомое значение.
По указателю осуществляется переход на следующий, более глубокий узел.
Процесс повторяется, пока поиск не дойдёт до листового узла, где и находится искомая запись (или указатель на неё).
Пример для ясности:
Представьте индекс по столбцу Username.
Корневой узел может содержать значения: [ "D", "M" ].
Если мы ищем пользователя "Alice", система перейдёт по указателю, соответствующему диапазону до "D".
Во внутреннем узле она может найти [ "A", "C" ] и перейти дальше.
В листовом узле она найдёт точное значение "Alice" и адрес строки в таблице Users.
Типы индексов (на основе структуры):
Кластеризованный индекс (Clustered): Сами данные таблицы физически упорядочены на диске в соответствии с индексом. У таблицы может быть только один такой индекс. Например, часто это первичный ключ.
Некластеризованный индекс (Non-Clustered): Это отдельная структура, которая содержит ключи и указатели на строки данных. Таблица может иметь множество таких индексов.
Вывод:
Индексы, построенные на B-деревьях, обеспечивают высокоэффективный поиск за счёт:
Минимального количества обращений к диску (сбалансированность).
Быстрого поиска как по точным значениям, так и по диапазонам (отсортированность и связные листовые узлы).
