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

Основная статья: Индекс (базы данных)

Плотный индекс (англ. 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.

• Dense Index Архивная копия от 10 июня 2018 на Wayback Machine / Encyclopedia of Database Systems, Springer, 2009. ISBN 978-0-387-35544-3, doi:10.1007/978-0-387-39940-9_760, pp 788-789  (англ.)

Ссылки

• Лекция 9: Физические модели баз данных. Индексные файлы. Файлы с плотным индексом, или индексно-прямые файлы Архивная копия от 31 августа 2016 на Wayback Machine / Татьяна Карпова, Базы данных: модели, разработка, реализация. Интуит, 2008
• 7.2.1. Индексно-прямые файлы Архивная копия от 6 сентября 2016 на Wayback Machine / П.В. Бураков, В.Ю. Петров. ВВЕДЕНИЕ В СИСТЕМЫ БАЗ ДАННЫХ. Учебное пособие - Санкт-Петербург, 2010
• Dense and Sparse Indices Архивная копия от 13 сентября 2016 на Wayback Machine / Osmar Zaiane, Chapter 11: Indexing & Hashing // CMPT 354: Database Systems and Structures. Summer 1998  (англ.)
• Free University of Bolzano–Database 2. Lecture II, 2003/2004 – A.Artale Архивная копия от 28 декабря 2013 на Wayback Machine