Структура данных в БД

Реляционная модель описывает таблицы и связи, но физически СУБД работает страницами: читает и записывает блоки фиксированного размера. Структуры хранения и индексы уменьшают число страниц, которые нужно просмотреть.

Heap table

В heap-организации строки не обязаны лежать в порядке ключа. Полный поиск без подходящего индекса читает множество страниц — это sequential/table scan.

Индекс хранит ключи и указатели на строки либо на страницы. За быстрый поиск приходится платить:

• дополнительным местом;
• обновлением индекса при INSERT, UPDATE, DELETE;
• конкуренцией и обслуживанием структуры;
• случайным доступом к таблице при низкой селективности.

B-tree и B+tree

B-tree — сбалансированное многопутевое дерево. В одном узле помещается много ключей и ссылок на дочерние страницы, поэтому высота невелика.

Упрощённо:

                  [20 | 50]
             /        |        \
       [2..19]     [20..49]    [50..90]

Инварианты:

• ключи внутри узла отсортированы;
• диапазоны дочерних узлов не пересекаются;
• листья находятся на одной глубине;
• при переполнении узел делится, при удалении может объединяться или перераспределять ключи;
• коэффициент ветвления зависит от размера страницы и ключа.

Многие индексы фактически ближе к B+tree: данные/ссылки находятся в листьях, а листья связаны для последовательного диапазонного чтения. Конкретная реализация зависит от СУБД.

Поиск

Для условия:

SELECT *
FROM purchase
WHERE created_at >= TIMESTAMP '2026-01-01'
ORDER BY created_at;

индекс по created_at позволяет:

1. пройти от корня до первого подходящего leaf;
2. последовательно читать соседние leaf-страницы;
3. получать ссылки на строки таблицы.

Высота дерева растёт логарифмически, но стоимость запроса определяется не только Big O: важны попадание страниц в cache, число подходящих строк и случайные обращения к heap.

Составной индекс

Индекс (customer_id, created_at) отсортирован сначала по customer_id, затем по времени внутри одного клиента. Он хорошо подходит:

WHERE customer_id = ?
  AND created_at >= ?

Один только фильтр по created_at не всегда эффективно использует такой индекс: нарушен ведущий префикс. Порядок столбцов выбирают под реальные условия, сортировку и селективность.

Clustered и covering

В некоторых СУБД таблица физически организована по одному индексу; в других индекс хранит указатели на отдельно расположенные строки. Термин «clustered index» поэтому нельзя переносить между СУБД без уточнения.

Covering index содержит все данные, нужные запросу, и позволяет обойтись без чтения таблицы. Но широкий индекс дороже обновлять и хранить.

Почему индекс не используется

• запрос возвращает большую долю таблицы;
• статистика устарела или оценка кардинальности ошибочна;
• функция/преобразование над столбцом мешает обычному поиску;
• тип параметра не совпадает и появляется cast;
• не подходит порядок полей составного индекса;
• последовательное чтение дешевле множества random lookups.

Решение проверяют через execution plan, а не через правило «индекс всегда быстрее».

На собеседовании

Почему B-tree удобнее бинарного дерева на диске? Один узел содержит много ключей, поэтому дерево ниже и требует меньше чтений страниц.

Чем поиск по диапазону отличается от hash index? B-tree сохраняет порядок и поддерживает range scan; hash ориентирован на равенство.

Связанные заметки: Индексы SQL, Селективность SQL, SQL оценка производительности, Ключи БД.