Б-деревья часто используются для хранения больших записей. Типичное Б-де-
рево может содержать записи о сотрудниках, каждая из которых занимает несколь-
ко килобайт памяти. Записи упорядочиваются по некоторому ключевому полю,
например по имени служащего или идентификационному номеру. В этом случае
переупорядочивание элементов будет происходить медленно. Чтобы объединить
два сегмента, программа должна переместить много записей, каждая из которых
довольно большая. Аналогично, для разбиения блока придется обработать не мень-
шее число записей большого объема.
Чтобы избежать перемещения больших блоков данных, программа записыва-
ет во внутренних узлах Б-дерева только ключи записей. Узлы также содержат ука-
затели на фактические записи данных, сохраненные в другом месте. Теперь, если
программе требуется переупорядочить блоки, нужно будет переместить только
ключи и указатели, а не сами записи. Данный тип Б-дерева называется Б+деревом
(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. Чтобы разместить элемент, программе потребуется только шесть обращений
к диску для нахождения ключа элемента и одно дополнительное обращение, что-
бы восстановить сам элемент.
Сохранение одних указателей, на данные в узлах Б+дерева также облегчает со-
поставление ключей с наборами записей. В системе, оперирующей записями о слу-
жащих, одно Б+дерево может использовать в качестве ключей фамилию, а другое -
номер социального страхования. Оба дерева содержат указатели на фактические за-
писи, сохраненные где-то за пределами деревьев.
Опубликовал Kest
October 30 2009 09:31:27 ·
0 Комментариев ·
8991 Прочтений ·
• Не нашли ответ на свой вопрос? Тогда задайте вопрос в комментариях или на форуме! •
Комментарии
Нет комментариев.
Добавить комментарий
Рейтинги
Рейтинг доступен только для пользователей.
Пожалуйста, залогиньтесь или зарегистрируйтесь для голосования.
Нет данных для оценки.
Гость
Вы не зарегистрированны? Нажмите здесь для регистрации.
Главная
Каталог файлов
