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

Индекс — главный инструмент ускорения поиска. Разберём две основные структуры (B-дерево и хеш) и поймём, когда индекс помогает, а когда мешает.

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

Индекс — это компромисс, а не панацея

Прежде чем восхищаться индексами, зафиксируем главную мысль: индекс — это обмен, а не бесплатное ускорение. Вы платите за быстрое чтение тремя вещами: дополнительным местом на диске (индекс — отдельная структура), замедлением записи (каждое изменение данных надо отразить и в индексе) и усложнением (индексы нужно сопровождать). Этот обмен почти всегда выгоден для полей, по которым часто ищут, но почти всегда невыгоден для полей, по которым не ищут. Поэтому правильный вопрос не «нужен ли индекс?», а «окупит ли ускорение чтения замедление записи и расход места в этом конкретном случае?». Держа в голове, что индекс — это сделка, вы не скатитесь ни в одну из двух крайностей: ни в «никаких индексов» (медленные чтения), ни в «индекс на каждый столбец» (медленные записи и распухший диск). Дальше разберём, как именно индекс ускоряет чтение и когда сделка выгодна.

Зачем нужен индекс

Из прошлого урока мы знаем: поиск без индекса в большой таблице — это полное сканирование, то есть чтение всех страниц. Для таблицы из миллиона строк это тысячи дисковых чтений ради одной нужной строки. Индекс превращает эту задачу в несколько чтений. Аналогия с книгой точна: чтобы найти слово «транзакция», вы не читаете книгу подряд, а открываете предметный указатель, находите страницу и идёте сразу туда. Индекс — это и есть такой указатель «значение → расположение строки».

B-дерево: универсальный индекс

Самая распространённая структура индекса — B-дерево (точнее, его вариант B+-дерево). Это сбалансированное дерево поиска, в котором ключи отсортированы, а все листья находятся на одной глубине. Поиск идёт от корня вниз: на каждом узле выбираем ветвь по сравнению с ключами. Высота дерева растёт логарифмически от числа строк — поэтому даже в миллионах записей нужное значение находится за несколько шагов (несколько чтений страниц).

Ключевое достоинство B-дерева — оно поддерживает не только точный поиск (= 5), но и диапазоны (BETWEEN, >, <) и сортировку, потому что ключи в нём упорядочены. Листья B+-дерева связаны в список, и пройти по диапазону — значит найти начало и идти по листьям. Именно поэтому B-дерево — индекс по умолчанию почти во всех СУБД.

Хеш-индекс: только равенство

Хеш-индекс хранит значения по хеш-функции: от значения вычисляется хеш, указывающий, где искать строку. Точный поиск (= '[email protected]') выполняется в среднем за одно обращение — быстрее, чем спуск по дереву. Но за скорость точного поиска хеш платит полной непригодностью для диапазонов и сортировки: хеш-функция намеренно «перемешивает» значения, поэтому соседние ключи оказываются в разных местах. Хеш-индекс хорош только для условий равенства.

Почему логарифм — это так быстро

Стоит прочувствовать, насколько мощна логарифмическая зависимость B-дерева, потому что именно она делает индексы волшебными. Полное сканирование таблицы из миллиона строк — это миллион операций. Поиск по B-дереву — это примерно log от миллиона, то есть около двадцати шагов. Разница не в разы, а на порядки: двадцать против миллиона. Удвойте данные до двух миллионов — сканирование удвоится (два миллиона операций), а дерево добавит всего один шаг (21 вместо 20). Вот почему индексы остаются эффективными при росте данных: их стоимость растёт несравнимо медленнее объёма. Это та же логарифмическая магия, что в бинарном поиске по отсортированному массиву или в угадывании числа делением пополам. Каждый шаг по дереву отсекает огромную долю кандидатов — и потому даже в гигантских таблицах нужное значение находится за считаные обращения к диску. Запомните этот контраст «миллион против двадцати» — он объясняет, почему без индексов большие базы немыслимы.

Живой пример: эффект индекса

В песочнице данных немного, но покажем, как создаётся индекс и как им пользуется поиск по равенству. На больших данных именно такой индекс по email превращает полное сканирование в несколько чтений.

CREATE TABLE clients (id INTEGER PRIMARY KEY, email TEXT, city TEXT);
INSERT INTO clients VALUES
  (1,'[email protected]','Москва'),
  (2,'[email protected]','Казань'),
  (3,'[email protected]','Москва');

-- индекс по email ускоряет поиск по точному значению
CREATE INDEX idx_email ON clients(email);

SELECT id, city FROM clients WHERE email = '[email protected]';

Вывод: одна строка — клиент 2, город Казань. С индексом по email СУБД идёт прямо к нужной записи через дерево, а не перебирает все строки. Первичный ключ id, к слову, тоже индексируется автоматически — поэтому поиск по нему всегда быстрый.

Кластеризованный и некластеризованный индекс

Индексы делятся на два важных типа по их связи с физическим хранением. Кластеризованный индекс определяет сам порядок строк на диске: данные таблицы физически отсортированы по ключу индекса. Такой индекс может быть только один (нельзя одновременно отсортировать таблицу двумя способами), и поиск по нему особенно дёшев — найдя позицию, вы сразу у самих данных, без лишнего «прыжка». Некластеризованный (вторичный) индекс — это отдельная структура, которая хранит ключ и указатель на расположение строки; самих данных в нужном порядке нет. Таких индексов может быть много. Поиск по некластеризованному индексу требует двух шагов: найти в индексе указатель, затем по указателю прочитать страницу с данными. Разница объясняет, почему поиск по первичному ключу (обычно кластеризованному) часто быстрее поиска по вторичному индексу: меньше «прыжков» к данным. Понимание этого различия помогает решать, по какому полю кластеризовать таблицу — обычно по тому, по которому чаще всего ищут диапазоны.

Когда индекс вредит

Индекс — не бесплатное благо. У него есть цена:

• Замедление записи. При каждом INSERT, UPDATE, DELETE нужно обновлять не только таблицу, но и все индексы по затронутым столбцам. Чем больше индексов, тем дороже запись.
• Занимает место. Индекс — это отдельная структура на диске; на много индексов уходит память и диск.
• Бесполезен на малой выборке. Если запрос всё равно возвращает большую часть таблицы, полное сканирование дешевле прыжков по индексу — и оптимизатор индекс проигнорирует.
• Не работает при преобразовании столбца. Условие вроде WHERE LOWER(email) = ... или вычисление над индексированным столбцом обычно «отключает» обычный индекс.

Поэтому правило: индексируйте столбцы, по которым часто ищут и соединяют (внешние ключи, поля в WHERE и JOIN), но не создавайте индексы «на все столбцы» — это замедлит запись без пользы для чтения.

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

Индекс может покрывать несколько столбцов — составной индекс по (city, email). Важна очерёдность: такой индекс помогает запросам по city и по (city, email), но не запросу только по email — как телефонный справочник, отсортированный по фамилии, а внутри по имени: искать по одному имени без фамилии он не помогает. Это «правило левого префикса».

Типичные ошибки

• Индексируют всё подряд. Лишние индексы замедляют запись и съедают место без выгоды для чтения.
• Хеш-индекс на диапазон. Ждут от хеша ускорения BETWEEN — он работает только на равенство.
• Преобразование столбца в условии. WHERE LOWER(col)=... отключает обычный индекс по col.
• Игнорируют порядок в составном индексе. Индекс по (a, b) не помогает запросу только по b.

Итог

• Индекс находит строки по значению, не сканируя всю таблицу, — как предметный указатель в книге.
• B-дерево универсально: поддерживает равенство, диапазоны и сортировку; это индекс по умолчанию.
• Хеш-индекс отлично работает только на точное равенство и бесполезен для диапазонов.
• Индексы замедляют запись и занимают место — создавайте их под реальные запросы, а не на все столбцы.