Открыть главное меню

B-дерево

Пример B-дерева степени 4

B-дерево (по-русски произносится как Би-дерево) — структура данных, дерево поиска. С точки зрения внешнего логического представления, сбалансированное, сильно ветвистое дерево. Часто используется для хранения данных во внешней памяти.

Использование B-деревьев впервые было предложено Р. Бэйером (англ. R. Bayer) и Э. МакКрейтом (англ. E. McCreight) в 1970 году.

Сбалансированность означает, что длина любых двух путей от корня до листьев различается не более, чем на единицу.

Ветвистость дерева — это свойство каждого узла дерева ссылаться на большое число узлов-потомков.

С точки зрения физической организации B-дерево представляется как мультисписочная структура страниц памяти, то есть каждому узлу дерева соответствует блок памяти (страница). Внутренние и листовые страницы обычно имеют разную структуру.

ПрименениеПравить

Структура B-дерева применяется для организации индексов во многих современных СУБД.

B-дерево может применяться для структурирования (индексирования) информации на жёстком диске (как правило, метаданных). Время доступа к произвольному блоку на жёстком диске очень велико (порядка миллисекунд), поскольку оно определяется скоростью вращения диска и перемещения головок. Поэтому важно уменьшить количество узлов, просматриваемых при каждой операции. Использование поиска по списку каждый раз для нахождения случайного блока могло бы привести к чрезмерному количеству обращений к диску вследствие необходимости последовательного прохода по всем его элементам, предшествующим заданному, тогда как поиск в B-дереве, благодаря свойствам сбалансированности и высокой ветвистости, позволяет значительно сократить количество таких операций.

Относительно простая реализация алгоритмов и существование готовых библиотек (в том числе для C) для работы со структурой B-дерева обеспечивают популярность применения такой организации памяти в самых разнообразных программах, работающих с большими объёмами данных.

Структура и принципы построенияПравить

B-деревом называется дерево, удовлетворяющее следующим свойствам:

  1. Ключи в каждом узле обычно упорядочены для быстрого доступа к ним. Корень содержит от 1 до 2t-1 ключей. Любой другой узел содержит от t-1 до 2t-1 ключей. Листья не являются исключением из этого правила. Здесь t — параметр дерева, не меньший 2 (и обычно принимающий значения от 50 до 2000[1]).
  2. У листьев потомков нет. Любой другой узел, содержащий ключи  , ...,  , содержит   потомков. При этом
    1. Первый потомок и все его потомки содержат ключи из интервала  
    2. Для  , i-й потомок и все его потомки содержат ключи из интервала  
    3.  -й потомок и все его потомки содержат ключи из интервала  
  3. Глубина всех листьев одинакова.

Свойство 2 можно сформулировать иначе: каждый узел B-дерева, кроме листьев, можно рассматривать как упорядоченный список, в котором чередуются ключи и указатели на потомков.

ПоискПравить

Если ключ содержится в корне, он найден. Иначе определяем интервал и идём к соответствующему потомку. Повторяем.

Добавление ключаПравить

Будем называть деревом потомков некоего узла поддерево, состоящее из этого узла и его потомков.

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

  1. Если х — не лист,
    1. Определяем интервал, где должен находиться K. Пусть y — соответствующий потомок.
    2. Рекурсивно добавляем K к дереву потомков y.
    3. Если узел y полон, то есть содержит   ключей, расщепляем его на два. Узел   получает первые   из ключей y и первые   его потомков, а узел   — последние   из ключей y и последние   его потомков. Медианный из ключей узла y попадает в узел х, а указатель на y в узле x заменяется указателями на узлы   и  .
  2. Если x — лист, просто добавляем туда ключ K.

Теперь определим добавление ключа K ко всему дереву. Буквой R обозначается корневой узел.

  1. Добавим K к дереву потомков R.
  2. Если R содержит теперь   ключей, расщепляем его на два. Узел   получает первые   из ключей R и первые   его потомков, а узел   — последние   из ключей R и последние   его потомков. Медианный из ключей узла R попадает вo вновь созданный узел, который становится корневым. Узлы   и   становятся его потомками.

Удаление ключаПравить

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

Если   — лист, удаляем оттуда ключ. Если в узле   осталось не меньше   ключей, мы на этом останавливаемся. Иначе мы смотрим на количество ключей в следующем, а потом в предыдущем узле. Если следующий узел есть, и в нём не менее   ключей, мы добавляем в   ключ-разделитель между ним и следующим узлом, а на его место ставим первый ключ следующего узла, после чего останавливаемся. Если это не так, но есть предыдущий узел, и в нём не менее   ключей, мы добавляем в   ключ-разделитель между ним и предыдущим узлом, а на его место ставим последний ключ предыдущего узла, после чего останавливаемся. Наконец, если и с предыдущим ключом не получилось, мы объединяем узел   со следующим или предыдущим узлом, и в объединённый узел перемещаем ключ, разделяющий два узла. При этом в родительском узле может остаться только   ключей. Тогда, если это не корень, мы выполняем аналогичную процедуру с ним. Если мы в результате дошли до корня, и в нём осталось от 1 до   ключей, делать ничего не надо, потому что корень может иметь и меньше   ключей. Если же в корне не осталось ни одного ключа, исключаем корневой узел, а его единственный потомок делаем новым корнем дерева.

Если   — не лист, а K — его  -й ключ, удаляем самый правый ключ из поддерева потомков  -го потомка  , или, наоборот, самый левый ключ из поддерева потомков  -го потомка  . После этого заменяем ключ K удалённым ключом. Удаление ключа происходит так, как описано в предыдущем абзаце.

Основные достоинстваПравить

  • Во всех случаях полезное использование пространства вторичной памяти составляет свыше 50 %. С ростом степени полезного использования памяти не происходит снижения качества обслуживания.
  • Произвольный доступ к записи реализуется посредством малого количества подопераций (обращения к физическим блокам).
  • В среднем достаточно эффективно реализуются операции включения и удаления записей; при этом сохраняется естественный порядок ключей с целью последовательной обработки, а также соответствующий баланс дерева для обеспечения быстрой произвольной выборки.
  • Неизменная упорядоченность по ключу обеспечивает возможность эффективной пакетной обработки.

Основной недостаток В-деревьев состоит в отсутствии для них эффективных средств выборки данных (т.е. метода обхода дерева), упорядоченных по отличному от выбранного ключа.

См. такжеПравить

ЛитератураПравить

СсылкиПравить

ПримечанияПравить

  1. Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн. Глава 18. B-деревья // Алгоритмы: построение и анализ = Introduction to Algorithms. — 2-е изд. — М.: Вильямс, 2006. — С. 515—536. — ISBN 0-07-013151-1.