Алгоритмы индексирования

Введение: Индекс – это алгоритм плюс структура данных

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

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

Алгоритм индексирования – это набор правил и структур данных, которые определяют, как индекс хранит данные, как выполняет поиск, как вставляет новые записи и как удаляет старые.

B-Tree и B+Tree: Короли реляционных баз данных

B-Tree (сбалансированное дерево) и его улучшенная версия B+Tree – это самые распространенные алгоритмы индексирования в реляционных СУБД. PostgreSQL, MySQL (InnoDB), Oracle, SQL Server, DB2 – все они используют B-Tree или B+Tree как основной тип индекса.

Базовая идея

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

Структура B-Tree

B-Tree состоит из двух типов узлов:

• Внутренние узлы (internal nodes): Содержат ключи и указатели на дочерние узлы. Они направляют поиск в нужную ветку.
• Листовые узлы (leaf nodes): Содержат ключи и либо сами данные (в классическом B-Tree), либо указатели на данные (в B+Tree).

Упрощенная структура B-Tree:

                      [50, 70]
                     /    |    \
                 [30]   [60]   [80, 90]
                /   \   / \    /    \
             [10,20] [40] [55] [75] [85,95]

Ключевая характеристика: B-Tree всегда сбалансирован. Все листья находятся на одном уровне. Это гарантирует, что время поиска любой записи одинаково и предсказуемо.

B-Tree vs B+Tree: В чем разница

B+Tree – это модификация B-Tree, которая используется в большинстве современных баз данных (InnoDB, PostgreSQL, SQL Server).

Почему B+Tree лучше для баз данных:

1. Диапазонный поиск: Благодаря связному списку листьев, чтобы найти все ключи в диапазоне [a, b], достаточно найти a в листьях, а затем пройти по ссылкам. В классическом B-Tree пришлось бы подниматься вверх по дереву.

2. Лучшее использование кеша: Внутренние узлы содержат только ключи (которые короткие) и указатели. В один узел помещается больше ключей, дерево становится ниже, операций ввода-вывода меньше.

3. Предсказуемая производительность: Все данные находятся на одном уровне (в листьях), что упрощает оптимизации.

Как работает поиск в B-Tree

Алгоритм поиска значения X:

1. Начать с корневого узла.
2. В текущем узле найти позицию, где должен находиться X (бинарный поиск внутри узла).
3. Если X найден в узле и это лист – вернуть данные.
4. Если X найден во внутреннем узле (в B-Tree) – можно вернуть данные или продолжить поиск.
5. Если X не найден, перейти к соответствующему дочернему узлу и повторить с шага 2.

Количество операций: O(log N) по количеству узлов. Для таблицы с миллиардом строк высота B-Tree обычно составляет 4-5 уровней. Это означает, что для поиска любой записи нужно прочитать с диска 4-5 страниц.

Как работает вставка в B-Tree

Вставка в B-Tree сложнее, чем поиск. Алгоритм должен сохранять баланс дерева.

1. Найти лист, в который должна быть вставлена новая запись.
2. Если в листе есть место, вставить запись в правильную позицию (сохраняя порядок).
3. Если лист заполнен, разделить его на два листа:
   • Создать новый лист.
   • Распределить записи между старым и новым листом (обычно пополам).
   • Поднять средний ключ в родительский узел.
4. Если родительский узел тоже заполнен, разделить и его, и так далее до корня.
5. Если разделился корень, высота дерева увеличивается на 1.

Важный нюанс: Вставка в B-Tree – это дорогая операция, особенно когда страницы заполнены и нужно их разделять. Именно поэтому случайные ключи (например, UUID v4) приводят к множеству разделений и фрагментации.

Удаление из B-Tree

Удаление симметрично вставке, но сложнее. Возможны сценарии:

1. Удаление из листа, после чего лист остается заполненным хотя бы наполовину.
2. Удаление из листа, после чего лист становится слишком пустым – тогда нужно перераспределить записи с соседними листьями или объединить листья.
3. Удаление из внутреннего узла – нужно найти замену из листьев (следующий или предыдущий ключ).

Фактор заполнения (Fill Factor)

При создании индекса можно задать параметр FILLFACTOR (фактор заполнения). Он определяет, насколько плотно будут заполнены страницы индекса при создании.

• FILLFACTOR = 100: Страницы заполняются полностью. Экономит место, но при вставках часты разделения.
• FILLFACTOR = 70: Страницы заполняются на 70%, остается 30% свободного места. Требует больше места, но вставки дольше не вызывают разделений.

Рекомендации:

• Для таблиц, где данные редко изменяются (справочники, исторические данные) – высокий FILLFACTOR (90-100).
• Для таблиц с частыми вставками (логи, транзакции) – более низкий FILLFACTOR (70-80).
• Для таблиц, где вставки идут в конец – высокий FILLFACTOR не страшен.

Когда B-Tree эффективен

Когда B-Tree неэффективен

Хеш-индекс (Hash Index)

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

Базовая идея

Хеш-функция преобразует значение ключа в число – хеш-код. Этот код используется как индекс в массиве (хеш-таблице). В каждой ячейке массива хранится указатель на строку (или на список строк, если коллизия).

Хеш-индекс:

Значение "Иван" → хеш-функция → 42 → ячейка 42 → указатель на строку
Значение "Петр" → хеш-функция → 17 → ячейка 17 → указатель на строку
Значение "Мария" → хеш-функция → 42 → ячейка 42 → указатель на строку (коллизия)

Как работает поиск

1. Вычислить хеш-код от искомого значения.
2. Перейти к ячейке массива по этому коду.
3. В ячейке находится указатель на строку (или на список строк).
4. Если есть коллизия, нужно проверить точное совпадение значения (хеш может совпадать для разных значений).

Сложность: O(1) в среднем (константное время). Теоретически это быстрее, чем O(log N) у B-Tree.

Как работает вставка

1. Вычислить хеш-код от вставляемого значения.
2. Перейти к ячейке массива.
3. Если ячейка пуста, поместить туда указатель.
4. Если ячейка занята, обработать коллизию.

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

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

Ключевые ограничения хеш-индекса

Где используется хеш-индекс

Хеш-индекс в памяти vs на диске

Хеш-индексы идеальны для данных, которые целиком помещаются в оперативной памяти. Для данных на диске хеш-индекс требует случайного доступа, что может быть медленнее, чем B-Tree.

Когда хеш-индекс хорош:

• Поиск в памяти (кеш, временные таблицы)
• Точечный поиск в распределенных системах
• Базы данных типа “ключ-значение” (Redis, RocksDB с хеш-движком)

Когда B-Tree лучше хеш-индекса:

• Нужны диапазонные запросы
• Нужна сортировка
• Данные на диске (B-Tree лучше использует последовательное чтение)

LSM-Tree (Log-Structured Merge-Tree)

LSM-Tree – это алгоритм индексирования, оптимизированный для очень частых вставок и обновлений. Он используется в современных базах данных с высокой нагрузкой на запись: Cassandra, HBase, RocksDB, LevelDB, MongoDB (с движком WiredTiger), ScyllaDB.

Базовая идея

Вместо того чтобы обновлять индекс на месте (как B-Tree), LSM-Tree накапливает изменения в памяти, а затем периодически записывает их на диск большими блоками. Это заменяет множество мелких случайных операций записи на несколько крупных последовательных.

Ключевая метафора: Представьте, что вы ведете дневник. Вместо того чтобы каждый раз вставлять новую запись в середину толстой тетради (что требует сдвига страниц), вы просто пишете новые записи в конец. А раз в день вы переписываете дневник заново, расставляя записи в правильном порядке.

Структура LSM-Tree

LSM-Tree состоит из нескольких уровней:

Запись → MemTable (в памяти, сортированная структура)
              ↓
         Immutable MemTable (ожидает сброса)
              ↓
         SSTable (Sorted String Table) на диске, уровень 0
              ↓
         Компакция (merge) → SSTable, уровень 1, более крупные файлы
              ↓
         Компакция → SSTable, уровень 2, еще крупнее
              ↓
         ... и так далее

Компоненты LSM-Tree:

1. MemTable: Структура в памяти (обычно сбалансированное дерево или пропускаемый список), которая хранит свежие записи. Все вставки и обновления сначала попадают сюда.

2. Write-Ahead Log (WAL): Журнал на диске, в который все операции записываются сразу. Нужен для восстановления после сбоя. Без WAL при падении сервера MemTable потеряется.

3. Immutable MemTable: Когда MemTable заполняется, она становится неизменяемой (immutable), и создается новая MemTable для новых записей.

4. SSTable (Sorted String Table): Файл на диске, содержащий отсортированные пары ключ-значение. Когда immutable MemTable сбрасывается на диск, она преобразуется в SSTable.

5. Уровни (Levels): На диске данные организованы в уровни. Уровень 0 содержит самые свежие SSTable (много маленьких файлов). Более высокие уровни содержат более крупные файлы.

Как работает запись (вставка/обновление)

Алгоритм записи в LSM-Tree:

1. Записать операцию в WAL (для надежности).
2. Вставить запись в MemTable (сортированную структуру в памяти).
3. Если ключ уже существует в MemTable, обновить его (последняя запись выигрывает).
4. Если MemTable превысила порог размера, превратить ее в immutable и создать новую MemTable.
5. Асинхронно сбросить immutable MemTable на диск как SSTable.

Что делает LSM-Tree быстрым для записи: Никаких обновлений на месте. Никаких разделений страниц. Никакого поиска правильной позиции в середине файла. Просто последовательная запись в конец лога и вставка в память.

Как работает чтение

Чтение в LSM-Tree сложнее, чем в B-Tree, потому что данные могут находиться в нескольких местах.

Алгоритм поиска ключа:

1. Проверить MemTable (самые свежие данные).
2. Проверить Immutable MemTable.
3. Проверить SSTable уровня 0 (все файлы, так как они могут пересекаться по ключам).
4. Проверить SSTable уровня 1, затем уровня 2 и так далее.

Для ускорения чтения используются вспомогательные структуры:

• Bloom-фильтр: Позволяет быстро определить, есть ли ключ в SSTable. Если фильтр говорит “нет” – SSTable можно пропустить.
• Индекс внутри SSTable: Позволяет найти позицию ключа внутри файла без полного сканирования.

Компакция (Compaction)

Компакция – это процесс, который поддерживает LSM-Tree в работоспособном состоянии. Он объединяет несколько SSTable в один, удаляя устаревшие версии ключей и удаленные записи (tombstones).

Типы компакции:

LSM-Tree vs B-Tree: Сравнение

Амплификация: Важное понятие для понимания LSM

Амплификация записи (Write Amplification): Во сколько раз больше данных записывается на диск, чем было передано приложением.

Пример: Вы вставили 1 КБ данных. Из-за компакции этот 1 КБ может быть переписан несколько раз, прежде чем окажется в финальном SSTable. Амплификация записи 10 означает, что для 1 КБ приложения физически записано 10 КБ.

Амплификация чтения (Read Amplification): Сколько операций чтения нужно выполнить, чтобы получить данные.

Пример: Поиск ключа может потребовать проверки MemTable и нескольких SSTable. Амплификация чтения 5 означает 5 операций ввода-вывода для одного запроса.

Когда LSM-Tree лучше B-Tree

Когда B-Tree лучше LSM-Tree

Инвертированный индекс (Inverted Index)

Инвертированный индекс – это алгоритм, лежащий в основе полнотекстового поиска. Он используется в поисковых системах (Elasticsearch, Solr, Lucene), в полнотекстовом поиске баз данных (PostgreSQL, MySQL, SQL Server), в системах анализа логов.

Базовая идея

В обычном индексе вы берете документ и спрашиваете: “Какие слова в нем есть?”. В инвертированном индексе вы делаете наоборот: берете слово и спрашиваете: “В каких документах оно встречается?”.

Инвертированный индекс – это словарь, где ключ – это слово (терм), а значение – список документов, содержащих это слово.

Инвертированный индекс:

"кот"    → [документ1, документ3, документ5]
"собака" → [документ2, документ3]
"мышь"   → [документ4]
"человек"→ [документ1, документ2, документ4, документ5]

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

Инвертированный индекс состоит из двух основных частей:

1. Словарь (Dictionary): Отсортированный список всех уникальных слов (термов). Обычно хранится в виде B-Tree или хеш-таблицы.

2. Постинг-листы (Posting Lists): Для каждого слова — список идентификаторов документов, где это слово встречается. Часто постинг-листы содержат дополнительную информацию: позицию слова в документе, частоту, вес.

Структура с дополнительной информацией:

"кот" → [(doc1, pos=3, freq=2), (doc3, pos=7, freq=1), (doc5, pos=1, freq=3)]

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

Процесс построения (индексация):

1. Токенизация: Разбить текст на отдельные токены (слова, числа).
2. Нормализация: Привести токены к единой форме (нижний регистр, удаление пунктуации).
3. Стемминг/лемматизация: Привести слова к основе (“бежал” → “бежать”, “книги” → “книга”).
4. Удаление стоп-слов: Убрать слишком частые слова (и, в, на, с, по).
5. Добавление в индекс: Для каждого токена добавить ссылку на документ.

Как выполняется поиск

Пример: поиск документов, содержащих “кот” И “собака”.

1. Найти постинг-лист для слова “кот” → список A.
2. Найти постинг-лист для слова “собака” → список B.
3. Выполнить пересечение списков (операция И) → документы, которые есть в обоих списках.
4. Если нужно “кот” ИЛИ “собака” – объединение списков.

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

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

Ранжирование в инвертированном индексе

Поисковые системы не просто находят документы, они еще сортируют их по релевантности. Для этого используются:

• TF (Term Frequency): Как часто слово встречается в документе. Чем чаще, тем важнее.
• IDF (Inverse Document Frequency): Насколько слово редкое во всей коллекции. Редкие слова важнее.
• BM25: Улучшенная формула, учитывающая длину документа.

Инвертированный индекс хранит достаточно информации (частоты, длины) для вычисления этих метрик на лету.

Где используется инвертированный индекс

Инвертированный индекс в реляционных базах

В PostgreSQL GIN-индекс (Generalized Inverted Index) реализует инвертированный индекс для типов данных, где один элемент может содержать много значений (массивы, JSON, полнотекстовый поиск).

Пример в PostgreSQL:

CREATE INDEX idx_documents ON documents USING GIN (to_tsvector('russian', content));

SELECT * FROM documents 
WHERE to_tsvector('russian', content) @@ to_tsquery('russian', 'кот & собака');

Bitmap-индекс (Битовый индекс)

Bitmap-индекс использует битовые строки (bitmaps) для представления множества значений. Он эффективен для столбцов с небольшим количеством уникальных значений (низкой кардинальностью).

Базовая идея

Для каждого уникального значения создается битовая строка длиной в количество строк таблицы. Если значение присутствует в строке i, то i-й бит устанавливается в 1.

Таблица "Сотрудники" (10 строк):

id  | пол | город
----|-----|-------
1   | М   | Москва
2   | Ж   | СПб
3   | М   | Москва
4   | Ж   | Казань
5   | М   | Москва
...

Bitmap для "пол = М":  [1, 0, 1, 0, 1, ...]
Bitmap для "пол = Ж":  [0, 1, 0, 1, 0, ...]
Bitmap для "город = Москва": [1, 0, 1, 0, 1, ...]
Bitmap для "город = СПб":   [0, 1, 0, 0, 0, ...]

Как работает поиск

Поиск с несколькими условиями выполняется через побитовые операции:

SELECT * FROM сотрудники WHERE пол = 'М' AND город = 'Москва'

1. Взять bitmap для пол = М: [1,0,1,0,1,...]
2. Взять bitmap для город = Москва: [1,0,1,0,1,...]
3. Выполнить побитовое AND: [1,0,1,0,1,...] & [1,0,1,0,1,...] = [1,0,1,0,1,...]
4. Получить номера строк с битом 1: строки 1, 3, 5, …

Сложность: Побитовые операции на CPU очень быстрые. Один такт процессора может обработать 64 или даже 512 бит (с использованием SIMD).

Когда bitmap-индекс эффективен

Когда bitmap-индекс неэффективен

Сжатие bitmap

Для столбцов с высокой кардинальностью или большим количеством нулей bitmap-индексы сжимаются. Самый популярный алгоритм – BBC (Byte-aligned Bitmap Compression), также используется Roaring Bitmap.

Сжатый bitmap может занимать значительно меньше места, но побитовые операции все равно могут выполняться над сжатыми данными (с некоторыми накладными расходами).

Сравнение с B-Tree для низкой кардинальности

Пространственные индексы (Spatial Index)

Пространственные индексы предназначены для работы с геометрическими данными: точки, линии, полигоны. Они используются в географических информационных системах (ГИС), сервисах карт, аналитике местоположений.

Базовая идея

Обычные индексы (B-Tree) не могут эффективно отвечать на вопросы типа “найти все точки в радиусе 10 км” или “найти все полигоны, пересекающиеся с заданным прямоугольником”. Пространственные индексы используют специальные структуры, которые разбивают пространство на области.

R-Tree (Rectangle Tree)

R-Tree – самая распространенная структура для пространственного индексирования. Используется в PostgreSQL (PostGIS), MySQL (InnoDB), SQL Server, SQLite (Spatialite), Oracle Spatial.

Идея R-Tree: Группировать близко расположенные объекты в минимальные ограничивающие прямоугольники (MBR – Minimum Bounding Rectangle). Каждый узел дерева содержит MBR, который покрывает все объекты в этом узле.

R-Tree (упрощенно):

                    [MBR: весь Европа]
                    /        |        \
        [MBR: Москва]  [MBR: СПб]  [MBR: Казань]
         /    |    \      /    \       /    \
    (точки) (точки) (точки) ... (точки) ... (точки)

Как работает поиск в R-Tree:

Алгоритм поиска всех точек в заданном прямоугольнике:

1. Начать с корня.
2. Для каждого дочернего узла проверить, пересекается ли его MBR с искомым прямоугольником.
3. Если пересекается, спуститься в этот узел.
4. В листьях проверить каждый объект (точную геометрию, а не только MBR).

Ключевой нюанс: MBR – это приближение. Объект может быть внутри MBR, но не внутри искомого прямоугольника. Поэтому на уровне листьев нужна точная проверка.

Quadtree (Квадродерево)

Quadtree – альтернативная пространственная структура. Она рекурсивно делит пространство на 4 квадранта (северо-запад, северо-восток, юго-запад, юго-восток).

Quadtree:

Уровень 0: [весь мир]
Уровень 1: [NW] [NE] [SW] [SE]
Уровень 2: каждый из них снова делится на 4

Когда Quadtree лучше R-Tree:

• Данные равномерно распределены по пространству.
• Нужны частые вставки и удаления (Quadtree проще обновлять).

Когда R-Tree лучше Quadtree:

• Данные распределены неравномерно (есть области с высокой плотностью).
• R-Tree адаптируется под данные, Quadtree — нет.

Grid Index (Сеточный индекс)

Сеточный индекс – самый простой пространственный индекс. Пространство разбивается на ячейки фиксированного размера (сетку). Каждый объект привязывается к ячейкам, которые он пересекает.

Grid Index (3×3 сетка):

    (0,0)  (1,0)  (2,0)
    (0,1)  (1,1)  (2,1)
    (0,2)  (1,2)  (2,2)

Объект попадает в ячейки: (1,1) и (1,2)

Плюсы: Очень простой, легко реализовать. Минусы: Размер ячейки сложно выбрать. Если ячейки крупные — много ложных срабатываний. Если мелкие – объект может попадать во много ячеек.

Когда нужны пространственные индексы

Пространственные индексы в реляционных базах

PostgreSQL (PostGIS): GIST-индекс (Generalized Search Tree), который может реализовывать R-Tree.

CREATE INDEX idx_locations ON points USING GIST (geom);

SELECT * FROM points 
WHERE ST_DWithin(geom, ST_MakePoint(37.617, 55.752), 500);

MySQL (InnoDB): SPATIAL INDEX (R-Tree).

CREATE SPATIAL INDEX idx_locations ON points (geom);

SELECT * FROM points 
WHERE MBRContains(geom, ST_GeomFromText('POLYGON(...)'));

SQL Server: SPATIAL INDEX.

Сравнительная таблица алгоритмов индексирования

Какой алгоритм выбрать. Общие рекомендации

Что нужно знать аналитику

1. Вы не выбираете алгоритм напрямую. В большинстве случаев СУБД сама выбирает алгоритм в зависимости от типа индекса (DEFAULT, HASH, GIST, GIN, SPATIAL).

2. Понимание алгоритмов помогает интерпретировать производительность.

   • Медленные вставки при UUID? B-Tree страдает от случайных ключей.
   • Полнотекстовый поиск медленный? Возможно, не хватает GIN-индекса.
   • Запросы с LIKE '%abc' медленные? Никакой индекс не поможет – нужен инвертированный индекс или другой подход.

3. Разные алгоритмы для разных задач. Не пытайтесь использовать B-Tree для полнотекстового поиска или Bitmap для уникальных идентификаторов.

4. LSM-Tree и B-Tree – два основных подхода к индексированию на диске. Понимание их различий помогает выбирать между базами данных (PostgreSQL vs Cassandra, ClickHouse vs MySQL).

Резюме для системного аналитика

1. B-Tree / B+Tree – основной алгоритм индексирования в реляционных базах данных. Он обеспечивает баланс между чтением и записью, поддерживает диапазонные запросы и сортировку. Но страдает от случайных ключей и высоких нагрузок на запись.

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

3. LSM-Tree оптимизирован для очень частых вставок. Превращает случайные записи в последовательные. Используется в Cassandra, HBase, RocksDB. Плата – сложность чтения и высокая амплификация записи.

4. Инвертированный индекс (Inverted Index) – основа полнотекстового поиска. Позволяет быстро находить документы по словам и фразам. Используется в Elasticsearch, а также в полнотекстовых индексах реляционных баз (GIN, FULLTEXT).

5. Bitmap-индекс эффективен для столбцов с низкой кардинальностью и сложными комбинированными условиями. Широко используется в аналитических базах данных и хранилищах (OLAP).

6. Пространственные индексы (R-Tree, Quadtree) работают с геоданными. Позволяют искать точки в радиусе, пересечения полигонов, ближайших соседей.