Б-деревья часто используются для хранения больших записей. Типичное Б-де-
рево может содержать записи о сотрудниках, каждая из которых занимает несколь-
ко килобайт памяти. Записи упорядочиваются по некоторому ключевому полю,
например по имени служащего или идентификационному номеру. В этом случае
переупорядочивание элементов будет происходить медленно. Чтобы объединить
два сегмента, программа должна переместить много записей, каждая из которых
довольно большая. Аналогично, для разбиения блока придется обработать не мень-
шее число записей большого объема.
Чтобы избежать перемещения больших блоков данных, программа записыва-
ет во внутренних узлах Б-дерева только ключи записей. Узлы также содержат ука-
затели на фактические записи данных, сохраненные в другом месте. Теперь, если
программе требуется переупорядочить блоки, нужно будет переместить только
ключи и указатели, а не сами записи. Данный тип Б-дерева называется Б+деревом
(B+tree).
Поскольку элементы Б+дерева довольно малы, программа сохраняет большее
количество ключей в каждом узле. При том же размере узла программа может уве-
личить порядок дерева и сделать его короче.
Например, имеется Б-дерево 2-го порядка, так что каждый узел имеет от трех
до пяти дочерних. Чтобы хранить миллион записей, дерево должно иметь глубину
от Iog5(1 000 000) до Iog3(1 000 000), или от 9 до 13. Чтобы разместить элемент в этом
дереве, программа должна выполнить 13 обращений к диску.
Предположим, что вы сохраняете тот же самый миллион записей в Б+дереве,
используя для узлов приблизительно тот же размер в байтах. Поскольку Б+дере-
во сохраняет только ключи в узлах, это дерево может содержать ключи для 20 за-
писей в каждом узле. В этом случае каждый узел будет иметь от 11 до 21 дочерних
узлов, поэтому глубина дерева будет от Iog21(1000 000) до log11(1000 000), или от 5
до 6. Чтобы разместить элемент, программе потребуется только шесть обращений
к диску для нахождения ключа элемента и одно дополнительное обращение, что-
бы восстановить сам элемент.
Сохранение одних указателей, на данные в узлах Б+дерева также облегчает со-
поставление ключей с наборами записей. В системе, оперирующей записями о слу-
жащих, одно Б+дерево может использовать в качестве ключей фамилию, а другое —
номер социального страхования. Оба дерева содержат указатели на фактические за-
писи, сохраненные где-то за пределами деревьев.
Б-деревья
Производительность Б-дерева
Добавление элементов в Б-дерево
Удаление элементов из Б-дерева
Разновидности Б-дерева
Нисходящие Б-деревья
Усовершенствование Б-деревьев
Добавление свободного пространства