Плотное и неплотное индексирование
Основной целью использования индекса является ускорение процесса извлечения данных, точнее, уменьшение числа дисковых операций ввода-вывода, необходимых для извлечения требуемой записи. В основном это достигается благодаря использованию указателей. Хотя до сих пор предполагалось, что в этом качестве используются указатели записей, на самом деле для этого достаточно было бы указателей страниц (т.е. номеров страниц). Конечно, для последующего поиска записи внутри данной страницы придется осуществить еще одну операцию извлечения записи, однако теперь она будет выполняться в оперативной памяти и для этого не придется увеличивать число дисковых операций ввода-вывода.
Эту идею можно развить дальше, если вспомнить, что данные в каждом хранимом файле находятся в единой "физической" последовательности на основе комбинации последовательности хранимых записей внутри каждой страницы и последовательности страниц внутри каждого набора страниц. Предположим, что физическая последовательность файла студентов соответствует логической последовательности, заданной на основе некоторого поля, например номера студента. Иначе говоря, в этом файле выполнена кластеризация по данному полю. Допустим, что по этому же полю осуществляется индексирование; тогда нет необходимости в данном индексе хранить указатели для каждой записи индексируемого файла (в данном случае для файла студентов). Все, что требуется, – это указатель для каждой страницы, состоящий из максимального номера студента для данной страницы и соответствующего номера страницы. Схематически такая структура показана на
рис. 13.4, где для простоты предполагается, что на каждой странице может размещаться максимум две записи.
рис. 13.4 Рис. А. 12 Пример использования неплотного индекса.
В качестве примера рассмотрим процесс извлечения записи с номером 3 с помощью такого индекса. Сначала в СУБД проводится поиск индекса для записи с номером, большим или равным 3. При этом будет найдено поле с номером 4, которое содержит указатель на страницу p. Страница p извлекается, помещается в оперативную память и просматривается для поиска заданной хранимой записи (которая в данном примере будет найдена очень быстро).
Индекс с описанной структурой называется неплотным (или разряженным), поскольку в нем не содержатся указатели на все записи индексированного файла. Схематически пример такого индекса показан на
рис. 13.4. (Все описанные выше индексы, наоборот, называются плотными.) Одним из преимуществ неплотных индексов является их малый размер по сравнению с плотными индексами, так как они содержат меньшее число записей. Это часто позволяет просматривать содержимое базы данных с большей скоростью. Однако с помощью одного только неплотного индекса нельзя выполнить проверку наличия некоторого значения.
Следует отметить, что в данном хранимом файле может быть по крайней мере один неплотный индекс, который организуется на основе (уникальной) физической последовательности, заданной в файле. А все другие индексы обязательно должны быть плотными.