Разрежённый индекс

Разрежённый индекс — это структура данных, предназначенная для ускорения поиска записей в отсортированных наборах данных, при которой индексируются не все элементы, а только некоторые, выбранные по определённому правилу (например, каждый n-й элемент или блок записей). В отличие от плотного индекса, который содержит ссылку на каждую запись, разрежённый индекс занимает меньше места в памяти, но требует дополнительного времени на последовательный просмотр (сканирование) внутри найденного блока. Разрежённые индексы широко применяются в системах управления базами данных (СУБД), файловых системах и поисковых движках, где объём данных велик, а скорость доступа к первичному носителю (например, к жёсткому диску) ограничена.

История и происхождение

Концепция разрежённого индекса возникла в контексте развития технологий хранения данных в 1960–1970-х годах, когда объёмы информации начали превышать возможности оперативной памяти. Первые базы данных, такие как IMS (IBM, 1966) и System R (IBM, 1974), использовали индексы для ускорения доступа, однако плотные индексы требовали значительных ресурсов. Разрежённый индекс стал компромиссным решением: он позволял сократить объём индекса за счёт увеличения времени поиска в пределах одного блока.

В 1980-х годах, с распространением реляционных СУБД (например, Oracle, DB2), разрежённые индексы стали стандартным элементом реализации B-деревьев и их разновидностей (B+-, B*-деревьев). В B+-деревьях, например, листовые узлы содержат все записи, а внутренние узлы — только разрежённые указатели, что делает структуру эффективной для операций вставки, удаления и поиска.

Принцип работы

Разрежённый индекс строится на основе отсортированного набора данных. Индекс содержит ключи и указатели на начало блоков (страниц) данных. Например, если данные хранятся в виде последовательных записей на диске, а размер блока составляет 100 записей, то индекс может содержать ключ первой записи каждого блока. При поиске конкретного значения система сначала находит в индексе блок, в котором это значение может находиться (поскольку индекс отсортирован), а затем последовательно сканирует записи внутри этого блока.

Отличие от плотного индекса

• Плотный индекс — содержит ссылку на каждую запись. Обеспечивает максимально быстрый поиск (O(log n) для дерева или O(1) для хеш-таблицы), но требует много памяти (пропорционально числу записей).
• Разрежённый индекс — содержит ссылки только на начало блоков. Занимает меньше памяти (пропорционально числу блоков), но поиск внутри блока требует последовательного просмотра (O(m), где m — размер блока). В среднем, при размере блока в 100 записей, время поиска увеличивается на 50 сравнений по сравнению с плотным индексом.

Пример

Пусть есть таблица с 1000 записей, отсортированных по ключу. Размер блока — 100 записей. Разрежённый индекс будет содержать 10 записей (по одной на блок). Для поиска записи с ключом 567:

1. Индекс находит блок, содержащий ключи от 501 до 600 (например, блок 5).
2. Система последовательно считывает записи блока, пока не найдёт ключ 567 (или не обнаружит его отсутствие).

Классификация

Разрежённые индексы можно классифицировать по нескольким признакам:

По типу данных

• Первичный индекс — строится на основе первичного ключа (уникального идентификатора записи). Обычно разрежённый, так как данные физически упорядочены по этому ключу.
• Вторичный индекс — строится на основе неключевых полей. Часто бывает плотным, но может быть разрежённым, если поле имеет низкую селективность (много повторяющихся значений).

По способу организации

• Одноуровневый — простой список указателей на блоки. Используется для небольших объёмов данных.
• Многоуровневый — иерархическая структура (например, B-дерево), где каждый уровень является разрежённым индексом для следующего. Это стандартный подход в современных СУБД.

По физическому расположению

• Кластеризованный — данные физически упорядочены в соответствии с индексом. Разрежённый индекс в этом случае наиболее эффективен.
• Некластеризованный — данные не упорядочены по индексу. Разрежённый индекс может быть менее эффективен, так как блоки могут быть разбросаны по диску.

Применение

Системы управления базами данных

В реляционных СУБД (например, PostgreSQL, MySQL, Oracle) разрежённые индексы используются в составе B+-деревьев. В таких структурах внутренние узлы содержат разрежённые указатели, а листовые — все записи или ссылки на них. Это позволяет эффективно выполнять операции поиска, вставки и удаления при минимальном объёме индекса.

Файловые системы

В файловых системах (например, ext4, NTFS) разрежённые индексы применяются для управления блоками данных. Например, в ext4 используется индексная структура (extent tree), где каждый узел содержит указатели на непрерывные блоки, а не на каждый блок отдельно. Это уменьшает размер метаданных и ускоряет доступ к большим файлам.

Поисковые системы

В поисковых системах (например, Яндекс, Google) разрежённые индексы используются для хранения инвертированных списков. Вместо того чтобы хранить ссылки на каждое вхождение слова, система может хранить указатели на блоки документов, а затем сканировать их в пределах блока.

Базы данных временных рядов

В системах хранения временных рядов (например, InfluxDB, TimescaleDB) разрежённые индексы применяются для ускорения запросов по временным меткам. Данные группируются в блоки по времени, и индекс хранит только начало каждого блока.

Преимущества и недостатки

Преимущества

• Экономия памяти — объём индекса пропорционален числу блоков, а не числу записей. При большом размере блока (например, 1000 записей) экономия может достигать 99,9 %.
• Ускорение операций вставки и удаления — при добавлении или удалении записей внутри блока не требуется обновлять весь индекс, только указатель на блок (если блок не меняет своё положение).
• Простота реализации — разрежённый индекс может быть реализован как простой отсортированный массив, что упрощает его поддержку.

Недостатки

• Увеличение времени поиска — для точного нахождения записи требуется последовательное сканирование внутри блока. При большом размере блока (например, 10 000 записей) это может стать узким местом.
• Зависимость от размера блока — выбор оптимального размера блока критичен. Слишком маленький блок приводит к росту индекса, слишком большой — к медленному сканированию.
• Неэффективность при частых обновлениях — если данные часто вставляются или удаляются, блоки могут переполняться или становиться пустыми, что требует перестройки индекса.

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

Интересные факты

• В некоторых СУБД (например, SQLite) разрежённый индекс используется в сочетании с плотным: для небольших таблиц применяется плотный индекс, а для больших — разрежённый, чтобы оптимизировать использование памяти.
• В файловой системе ext4 размер блока по умолчанию составляет 4096 байт, а разрежённый индекс (extent tree) может содержать до 4 уровней, что позволяет адресовать файлы размером до 16 терабайт.
• В поисковых системах разрежённые индексы часто комбинируются с кэшированием часто запрашиваемых блоков, что снижает влияние последовательного сканирования.

Источники

• Silberschatz, A., Korth, H. F., Sudarshan, S. (2010). Database System Concepts (6th ed.). McGraw-Hill.
• Elmasri, R., Navathe, S. B. (2015). Fundamentals of Database Systems (7th ed.). Pearson.
• Garcia-Molina, H., Ullman, J. D., Widom, J. (2009). Database Systems: The Complete Book (2nd ed.). Prentice Hall.
• Документация PostgreSQL: «Index Types» (B-tree, GiST, GIN).