Индексы: B-дерево и хеш

В прошлом уроке мы выяснили, что таблица это файл из страниц, и строку легко прочитать, если знаешь её адрес. Но запрос спрашивает по значению: «найди студента с почтой petya@example.com». Без помощи СУБД остаётся перебрать все страницы таблицы. Этот урок про индексы, которые превращают перебор в несколько шагов, и про два самых частых их вида: B-дерево и хеш.

Указатель в конце книги

Тебе нужно найти в учебнике по биологии всё про митохондрии. Можно листать все 600 страниц подряд. А можно открыть алфавитный указатель в конце: «митохондрии, с. 112, 340». Указатель отсортирован, поэтому слово находится за секунды, и он ведёт сразу на нужные страницы.

Индекс в базе данных устроен так же. Это отдельная структура рядом с таблицей. В ней лежат значения колонки, разложенные так, чтобы их было легко искать, и рядом с каждым значением адрес строки: номер страницы и слот.

CREATE INDEX students_email_idx ON students (email);

После этой команды поиск по email идёт через индекс: найти значение, взять адрес, прочитать одну страницу таблицы. Без индекса СУБД читает весь файл. Такой проход называют полным просмотром.

B-дерево

Самый частый индекс в реляционных СУБД это B-дерево. По умолчанию CREATE INDEX в PostgreSQL создаёт его.

Аналогия: картотека в библиотеке. На шкафу таблички «А-Г», «Д-К», «Л-П». Открыл нужный ящик, внутри разделители «Ла-Ле», «Ли-Ло». За разделителем карточки по алфавиту. Три шага, и ты у карточки, даже если их сто тысяч.

                    [ Л ]
                 /         \
         [ Г  |  Е ]        [ П  |  Т ]
        /    |     \       /    |     \
  [А Б В] [Г Д] [Е Ж К] [Л М Н] [П Р С] [Т У Я]   ← листья

Как идёт поиск значения «Р»:

1. В корне сравниваем с «Л»: «Р» больше, идём вправо.
2. В узле [П | Т] «Р» между ними, идём в средний лист.
3. В листе [П Р С] находим «Р» и берём адрес строки.

Свойства, которые делают B-дерево таким полезным:

• Узел это страница. В одном узле сотни ключей, поэтому дерево очень широкое и очень низкое. Таблице в миллионы строк хватает трёх-четырёх уровней, то есть трёх-четырёх чтений страниц.
• Дерево сбалансировано. Все листья на одной глубине, поиск любого значения стоит одинаково.
• Ключи отсортированы. Это главное. Отсортированный порядок позволяет искать не только точное значение, но и диапазон.

В базах обычно используют вариант B+-дерева: адреса строк лежат только в листьях, а листья связаны в цепочку слева направо. Чтобы прочитать диапазон «оценки от 4 до 5», СУБД спускается к первому подходящему листу и идёт по цепочке, пока значения не выйдут за границу.