B-деревья: принципы построения, операция поиска

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

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

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

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

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

Поиск.

Пусть необходимо найти запись со значением ключа V. При этом нужно найти путь от корня дерева до конкретного листа, в котором должна находиться запись v, если она существует в файле. Поиск начинается с корня дерева и продолжается по иерархии индексов, выстраивая путь.