Разреженные и плотные индексы. Индексация по нескольким полям

Разреженный индекс (англ. sparse index) в базах данных — это файл с последовательностью пар ключей и указателей. Каждый ключ в разреженном индексе, в отличие от плотного индекса, ассоциируется с определённым указателем на блок в сортированном файле данных. Идея использования индексов пришла от того, что современные базы данных слишком массивны и не помещаются в основную память. Мы обычно делим данные на блоки и размещаем данные в памяти поблочно. Однако поиск записи в БД может занять много времени. С другой стороны, файл индексов или блок индексов намного меньше блока данных и может поместиться в буфере основной памяти что увеличивает скорость поиска записи. Поскольку ключи отсортированы, можно воспользоваться бинарным поиском. В кластерных индексах с дублированными ключами разреженный индекс указывает на наименьший ключ в каждом блоке.

Чтобы облегчить процедуру поиска, можно создать второй файл, называемый разреженным индексом, который состоит из пар (x, b), где x - значение ключа, а b - физический адрес блока, в котором значение ключа первой записи равняется х. Разреженный индекс должен быть отсортирован по значениям ключей.

Плотный индекс (dense index) — индекс в базах данных, файл с последовательностью пар ключей и указателей на запись в файле данных. Каждый ключ в плотном индексе, в отличие от разреженного индекса, ассоциируется с определённым указателем на запись в сортированном файле данных. Идея использования индексов пришла от того, что современные базы данных слишком массивны и не помещаются в основную память. Мы обычно делим данные на блоки и размещаем данные в памяти поблочно. Однако поиск записи в БД может занять много времени. С другой стороны, файл индексов или блок индексов намного меньше блока данных и может поместиться в буфере основной памяти что увеличивает скорость поиска записи. Поскольку, ключи отсортированы можно воспользоваться бинарным поиском. В кластерных индексах с дублированными ключами плотный индекс указывает на первую запись с указанным ключом.