B-деревья

Плотное индексирование

Эффективность индексированных файлов

Пусть блок главного файла максимально вмещает E записей. Тогда в худшем случае блок будет вмещать e равное (E+1)/2 записей. Эта ситуация складывается при делении блока при вставке новой записи. Аналогично если блок индекса максимально вмещает D, тогда в худшем случае он будет содержать d равное (D+1)/2 записей. Если в файле содержится n записей, то можно сделать следующие выводы об эффективности индексированных файлов.

При двоичном поиске в индексированном файле потребуется 2+Log₂(n/de) обращений к диску. Где n/de – максимальное количество блоков в индексе (логарифм из эффективности двоичного поиска). Еще два обращения для чтения и записи блока основного файла. При интерполирующем поиске потребуется 3+Log₂Log₂(n\de) обращений к диску.

Индексирование, рассмотренное выше, называется разреженным индексированием. Существует другой вид индексирования широко распространенный в реальных СУБД – плотное индексирование. В этом случае индексные файлы содержат пары вида (v,p), где первый элемент – значение ключа, а второй – адрес записи в основном файле с этим ключом. Такой подход не требует обязательного упорядочивания записей по индексируемому полю, а так же не обязательна уникальность ключа. Поэтому подход плотного индекса применим для ускорения поиска по любым полям, позволяя построить несколько независимых индексов.

При организации таких файлов скорость доступа будет 2+время поиска в файле индекса.

При увеличении числа блоков, занятых индексом в разреженных индексированных файлах, снижается эффективность работы. Структура, называемая В–деревом, позволяет избежать такого снижения путем построения индекса для индекса, и при необходимости далее, пока верхний индекс не будет помещаться в один блок. Таким образом, получается иерархическая структура индексов - рисунок 10.

Рисунок 10 – В-дерево степени 5

В В-дереве узел может иметь много сыновей (на практике до тысячи). Количество сыновей (максимальное) определяет степень В-дерева.

Узел х, хранящий n[x] ключей, имеет n[x]+1 сыновей. Хранящиеся в х ключи служат границами, разделяющими всех потомков узла на n[x]+1 групп. За каждую группу отвечает один из сыновей х.

При организации В–деревьев не должно быть узлов, заполненных меньше, чем наполовину. Структура В–дерева отличается от простой иерархии индексов следующим соглашением: в индексных блоках В–деревьев значения ключей в первой записи пропускаются. При поиске полагают, что все значения, меньшие второго значения в индексе, покрываются отсутствующим первым значением ключа.

Дата добавления: 2015-05-09