Выжимаем максимум из B-Tree

Когда мы говорим о B+ Tree, важно понимать, что именно лежит в его листовых узлах. От этого зависит архитектура всей базы данных.

В этой концепции индекс — это и есть таблица (Index-Organized Table). Листовые узлы дерева хранят физически полную строку данных. Строки на диске упорядочены ровно так, как диктует этот индекс. Очевидно, что такой индекс может быть только один на таблицу.

• Плюсы: Феноменально быстрые Range-запросы (считываем данные прямо из листьев подряд).
• Минусы: Если ты обновляешь (UPDATE) кластеризующий ключ, базе приходится физически перемещать всю тяжелую строку данных в другое место на диске. Это очень дорого.
• Пример: MySQL (движок InnoDB) по умолчанию хранит все таблицы как кластерные индексы на базе Primary Key.

Листья такого дерева хранят только сам проиндексированный ключ и указатель (Pointer/ID) на место, где физически лежит полная строка.

Когда ты ищешь данные по некластерному индексу, происходит Bookmark Lookup (двойной прыжок). Сначала индекс за O(log N) находит нужный указатель, а затем делает дополнительное случайное чтение с диска, чтобы вытащить саму строку из таблицы. Таких индексов может быть сколько угодно.

Bookmark Lookup — это дорого. Если запрос требует вытащить 10 000 строк по вторичному индексу, база сделает 10 000 дополнительных прыжков на диск. Чтобы этого избежать, придумали механизм INCLUDE.

Это способ прикрепить к листьям индекса дополнительную (не ключевую) «полезную нагрузку».

-- Пример: мы часто ищем заказы клиента, и нам нужна только сумма (total_sum).
-- Мы добавляем total_sum прямо в листья индекса.
CREATE INDEX idx_orders_covering 
ON orders (customer_id)           -- ключ для поиска (B-Tree)
INCLUDE (total_sum);              -- просто данные в листьях

Теперь база найдет customer_id и сразу же отдаст total_sum прямо из индекса (Index-Only Scan), ни разу не обратившись к основной таблице!

В Computer Science есть концепция MVCC (Multi-Version Concurrency Control), которая позволяет транзакциям не блокировать друг друга. База хранит несколько версий одной и той же строки. И здесь кроется главный подвох покрывающих индексов.

В системах вроде PostgreSQL индекс не знает, какая версия строки сейчас активна (видима) для твоей транзакции. Если таблица часто обновляется (высокий DML), Index-Only Scan вырождается:

1. Индекс находит нужные данные в своих листьях.
2. Но он не уверен, не удалены ли они параллельной транзакцией.
3. Ему всё равно приходится делать дорогой прыжок в Visibility Map или саму таблицу, чтобы проверить статус строки.