Как устроены индексы с точки зрения структур данных?

Question

Индекс в базе данных чаще всего реализуется с помощью структуры данных "B-дерево" (или его разновидности B+дерево). Это сбалансированное дерево поиска, которое позволяет быстро находить данные по значению ключа. Оно хранит ключи в отсортированном порядке, что также ускоряет операции поиска по диапазону и сортировку.

YeaHub · Accepted Answer

Индекс можно сравнить с алфавитным указателем в конце книги. Вместо того чтобы перелистывать всю книгу (таблицу) в поисках термина (строки), вы открываете указатель (индекс), находите термин и сразу видите номер страницы (указатель на строку).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-деревьях, обеспечивают высокоэффективный поиск за счёт:Минимального количества обращений к диску (сбалансированность).Быстрого поиска как по точным значениям, так и по диапазонам (отсортированность и связные листовые узлы).