Индексирование баз данных

Производительность базы данных может стать решающим фактором для современных приложений. Представьте, что нам нужно найти профиль пользователя по email в таблице с миллионами записей. Без какой-либо оптимизации базе пришлось бы проверять строку за строкой, последовательно просматривая всю таблицу, пока она не найдет нужную запись. Для таблицы с миллионами строк это будет мучительно медленно - как если бы мы искали конкретный роман, перебирая в библиотеке каждую книгу по одной.

Здесь и помогают индексы. Они поддерживают отдельные структуры данных, оптимизированные для поиска, и позволяют базе быстро находить нужные записи, не просматривая каждую строку. От поиска товаров в каталоге интернет-магазина до загрузки профиля пользователя в социальной сети, именно индексы делают возможным быстрый поиск.

Понимание того, когда добавлять индекс, на какие столбцы и какого типа, - важная часть System Design. Выбор правильных индексов часто становится одной из ключевых тем на собеседованиях. От Middle-инженеров обычно ждут знания базовых стратегий индексирования. От Staff-инженеров - уверенного понимания разных типов индексов и их компромиссов.

В этом подробном обзоре мы разберем, как индексы баз данных работают "под капотом" и какие типы индексов встречаются чаще всего. Сначала поговорим о том, как индексы хранятся и как к ним обращаются, а затем перейдем к конкретным типам, таким как B-Tree, хеш-индексы, геопространственные индексы и не только. Для каждого типа мы рассмотрим сильные стороны, ограничения и случаи, когда их стоит предлагать на интервью по System Design.

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

Как работают индексы баз данных

Когда мы сохраняем данные в базе, в итоге они записываются на диск как набор файлов. Основные данные таблицы обычно хранятся в виде heap-файла - по сути, это набор строк без определенного порядка. Представьте обычный блокнот, в который мы записываем новые заметки по мере поступления, одну за другой.

Физическое хранение и паттерны доступа

Современные базы данных решают интересную задачу: им нужно хранить огромные объемы данных на диске и при этом быстро к ним обращаться. Данные лежат на диске, сегодня чаще всего на SSD, но обрабатывать мы можем только то, что загружено в память. Значит, любой запрос требует чтения данных с диска в RAM.

Когда мы выполняем запрос без индекса, приходится последовательно читать каждую страницу данных, загружать ее в память и проверять, есть ли там то, что мы ищем. Если таких страниц миллионы, это означает миллионы относительно медленных чтений с диска ради одной записи. Это как если бы нам пришлось перелистать каждую страницу огромной книги, чтобы найти одно конкретное слово.

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

Цена индексов

Но индексы не достаются бесплатно - у них есть свои компромиссы. Каждый индекс занимает дополнительное место на диске, иногда почти столько же, сколько и сами данные.

Скорость записи тоже страдает. Когда мы вставляем новую строку или обновляем существующую, базе нужно обновить не только основную таблицу, но и каждый индекс на ней. Если индексов несколько, одна запись может привести к нескольким операциям записи на диск.

Когда индексы могут вредить больше, чем помогать? Классический пример - таблица, в которую часто пишут, но редко читают. Например, таблица логов, куда мы постоянно добавляем новые записи, но почти не запрашиваем старые. В этом случае накладные расходы на поддержку индексов могут не окупиться. То же самое касается совсем маленьких таблиц на несколько сотен строк: стоимость поддержки индекса и обход его структуры может быть выше, чем цена простого последовательного сканирования.

Типы индексов

Типов индексов очень много. Многие из них редко встречаются и нужны только для узкоспециализированных сценариев. Вместо того чтобы перечислять все возможные варианты, мы сосредоточимся на самых распространенных индексах, которые чаще всего всплывают на интервью по System Design.

B-Tree индексы

B-Tree индексы - самый распространенный тип индексов в базах данных. Они дают эффективный способ организовать данные так, чтобы быстро выполнять поиск и обновления. Достигается это за счет сбалансированной древовидной структуры, которая минимизирует количество чтений с диска, необходимых для поиска любой записи.

Устройство B-деревьев

B-дерево - это самобалансирующееся дерево, которое хранит отсортированные данные и поддерживает эффективные вставки, удаления и поиск. В отличие от бинарных деревьев, где у каждого узла максимум два потомка, узлы B-дерева могут иметь много потомков - на практике часто сотни. Каждый узел содержит упорядоченный массив ключей и указателей, организованный так, чтобы уменьшить число дисковых чтений.

Каждый узел в B-дереве подчиняется строгим правилам:

• Все листья должны находиться на одной глубине.
• Каждый узел может содержать от m/2 до m ключей, где m - порядок дерева.
• Узел с k ключами должен иметь ровно k+1 потомков.
• Ключи внутри узла всегда хранятся в отсортированном порядке.

Эта структура особенно хороша тем, что идеально ложится на то, как базы данных хранят информацию на диске. Размер каждого узла подбирается так, чтобы он помещался в одну страницу диска, обычно около 8 KB, и это делает ввод-вывод максимально эффективным. Когда PostgreSQL нужно найти запись с id=350, ей часто достаточно прочитать всего 2-3 страницы с диска: корневой узел, возможно один внутренний узел и, наконец, листовой узел.

Примеры из реальных систем

B-деревья встречаются почти везде. PostgreSQL использует их практически для всего - первичные ключи, уникальные ограничения и большинство обычных индексов там реализованы именно как B-Tree.

Когда мы создаем такую таблицу в PostgreSQL:

CREATE TABLE users (
  id SERIAL PRIMARY KEY,
  email VARCHAR(255) UNIQUE
);

PostgreSQL автоматически создает два B-Tree индекса: один для первичного ключа и один для уникального ограничения на email. Эти B-деревья поддерживают отсортированный порядок, а это важно и для проверки уникальности, и для запросов по диапазону.

DynamoDB хранит элементы внутри раздела в порядке ключа сортировки, что позволяет делать эффективные запросы по диапазону в пределах одного раздела. Детали ее внутренних структур хранения публично не раскрываются полностью, но обычно считается, что в основе лежит LSM-подобная архитектура, а не B-Tree.

Даже MongoDB, несмотря на свою документную модель, использует B-деревья, точнее их вариант B+ Tree, где все данные лежат в листьях, для построения индексов.

Когда мы создаем индекс в MongoDB так:

db.users.createIndex({ email: 1 });

мы создаем B-Tree, который сопоставляет значения email с расположением документов.

Почему B-деревья - выбор по умолчанию

B-деревья стали стандартным выбором для большинства индексов, потому что они хорошо справляются почти со всем, что нужно базам данных:

1. Они поддерживают отсортированный порядок, поэтому запросы по диапазону и ORDER BY работают эффективно.
2. Они самобалансируются, поэтому производительность остается предсказуемой даже по мере роста данных.
3. Они минимизируют дисковый ввод-вывод, потому что их структура совпадает с тем, как базы хранят данные на диске.
4. Они одинаково хорошо поддерживают и запросы на точное равенство, такие как email = 'x', и на диапазоны, такие как age > 25.
5. Они остаются сбалансированными даже при случайных вставках и удалениях, без резких падений производительности, которые бывают у более простых древовидных структур.

Если на собеседовании вы не уверены, какой индекс выбрать, B-Tree почти всегда будет безопасным вариантом.

LSM-деревья

B-деревья отлично подходят для смешанной нагрузки, но что делать, если нам нужно обрабатывать огромный поток записей? Представьте систему мониторинга, такую как DataDog: система принимает миллионы метрик в секунду от тысяч серверов, и каждое значение CPU, памяти или счетчика ошибок нужно сохранять немедленно.