Sparse index
Материал из Википедии — свободной энциклопедии
Редкий индекc (англ. sparse index) в базах данных – это файл с последовательностью пар ключей и указателей. Каждый ключ в редком индексе, о отличии от плотного индекса, ассоциируется с определённым указателем на блок в сортированном файле данных. Идея использования индексов пришла оттого что современные базы данных слишком массивны и не помещаются в основную память. Мы обычно делим данные на блоки и размещаем данные в памяти по-блочно. Однако поиск записи в БД может занять много времени. С другой стороны, файл индексов или блок индексов намного меньше блока данных и может поместиться в буфере основной памяти что увеличивает скорость поиска записи. Поскольку, ключи отсортированы можно воспользоваться бинарным поиском. В кластерных индексах с дублированными ключами редкий индекс указывает на наименьший ключ в каждом блоке.
Литература: Database Systems: The Complete Book. Hector Garcia-Molina, Jeffrey D. Ullman, Jennifer D. Widom
