Плотный индекс

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

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

Примечания

[править | править код]
  1. Database Systems: The Complete Book. Hector Garcia-Molina, Jeffrey D. Ullman, Jennifer D. Wisdom

Литература

[править | править код]
  • Hector Garcia-Molina, Jeffrey D. Ullman, Jennifer D. Widom. 13.1.2 Dense Indexes // Database Systems: The Complete Book. — Prentice Hall, 202. — С. 607-609. — 1119 с. — ISBN 0-13-031995-3.