B-дерево

Эта статья находится на начальном уровне проработки, в одной из её версий выборочно используется текст из источника, распространяемого под свободной лицензией
Материал из энциклопедии Руниверсалис
(перенаправлено с «B-Tree»)
Пример B-дерева со степенью 3

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. У листьев потомков нет. Любой другой узел, содержащий ключи [math]\displaystyle{ K_1 }[/math], …, [math]\displaystyle{ K_n }[/math], содержит [math]\displaystyle{ n+1 }[/math] потомков. При этом
    1. Первый потомок и все его потомки содержат ключи из интервала [math]\displaystyle{ (-\infty, K_1) }[/math]
    2. Для [math]\displaystyle{ 2\le i\le n }[/math], i-й потомок и все его потомки содержат ключи из интервала [math]\displaystyle{ (K_{i-1}, K_i) }[/math]
    3. [math]\displaystyle{ (n+1) }[/math]-й потомок и все его потомки содержат ключи из интервала [math]\displaystyle{ (K_n, \infty) }[/math]
  3. Глубина всех листьев одинакова.

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

Поиск

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

Добавление ключа

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

Вначале определим функцию, которая добавляет ключ K к дереву потомков узла x. После выполнения функции во всех пройденных узлах, кроме, может быть, самого узла x, будет меньше [math]\displaystyle{ 2t-1 }[/math], но не меньше [math]\displaystyle{ t-1 }[/math], ключей.

  1. Если х — не лист,
    1. Определяем интервал, где должен находиться K. Пусть y — соответствующий потомок.
    2. Рекурсивно добавляем K к дереву потомков y.
    3. Если узел y полон, то есть содержит [math]\displaystyle{ 2t-1 }[/math] ключей, расщепляем его на два. Узел [math]\displaystyle{ y_1 }[/math] получает первые [math]\displaystyle{ t-1 }[/math] из ключей y и первые [math]\displaystyle{ t }[/math] его потомков, а узел [math]\displaystyle{ y_2 }[/math] — последние [math]\displaystyle{ t-1 }[/math] из ключей y и последние [math]\displaystyle{ t }[/math] его потомков. Медианный из ключей узла y попадает в узел х, а указатель на y в узле x заменяется указателями на узлы [math]\displaystyle{ y_1 }[/math] и [math]\displaystyle{ y_2 }[/math].
  2. Если x — лист, просто добавляем туда ключ K.

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

  1. Добавим K к дереву потомков R.
  2. Если R содержит теперь [math]\displaystyle{ 2t-1 }[/math] ключей, расщепляем его на два. Узел [math]\displaystyle{ R_1 }[/math] получает первые [math]\displaystyle{ t-1 }[/math] из ключей R и первые [math]\displaystyle{ t }[/math] его потомков, а узел [math]\displaystyle{ R_2 }[/math] — последние [math]\displaystyle{ t-1 }[/math] из ключей R и последние [math]\displaystyle{ t }[/math] его потомков. Медианный из ключей узла R попадает во вновь созданный узел, который становится корневым. Узлы [math]\displaystyle{ R_1 }[/math] и [math]\displaystyle{ R_2 }[/math] становятся его потомками.

Удаление ключа

Если корень одновременно является листом, то есть в дереве всего один узел, мы просто удаляем ключ из этого узла. В противном случае сначала находим узел, содержащий ключ, запоминая путь к нему. Пусть этот узел — [math]\displaystyle{ x }[/math].

Если [math]\displaystyle{ x }[/math] — лист, удаляем оттуда ключ. Если в узле [math]\displaystyle{ x }[/math] осталось не меньше [math]\displaystyle{ t-1 }[/math] ключей, мы на этом останавливаемся. Иначе мы смотрим на количество ключей в двух соседних узлах-братьях. Если соседний правый узел есть, и в нём не менее [math]\displaystyle{ t }[/math] ключей, мы добавляем в [math]\displaystyle{ x }[/math] ключ-разделитель между ним и соседним правым узлом, а на место этого ключа ставим первый ключ соседнего правого узла, после чего останавливаемся. Если это не так, но есть соседний левый узел, и в нём не менее [math]\displaystyle{ t }[/math] ключей, мы добавляем в [math]\displaystyle{ x }[/math] ключ-разделитель между ним и соседним левым узлом, а на место этого ключа ставим последний ключ соседнего левого узла, после чего останавливаемся. Наконец, если и с левым ключом не получилось, мы объединяем узел [math]\displaystyle{ x }[/math] с соседним левым или правым узлом, и в объединённый узел перемещаем ключ, до этого разделявший эти два узла. При этом в родительском узле может остаться только [math]\displaystyle{ t-2 }[/math] ключей. Тогда, если это не корень, мы выполняем аналогичную процедуру с ним. Если мы в результате дошли до корня, и в нём осталось от 1 до [math]\displaystyle{ t-1 }[/math] ключей, делать ничего не надо, потому что корень может иметь и меньше [math]\displaystyle{ t-1 }[/math] ключей. Если же в корне не осталось ни одного ключа, исключаем корневой узел, а его единственный потомок делаем новым корнем дерева.

Если [math]\displaystyle{ x }[/math] — не лист, а K — его [math]\displaystyle{ i }[/math]-й ключ, удаляем самый правый ключ из поддерева потомков [math]\displaystyle{ i }[/math]-го потомка [math]\displaystyle{ x }[/math], или, наоборот, самый левый ключ из поддерева потомков [math]\displaystyle{ i+1 }[/math]-го потомка [math]\displaystyle{ x }[/math]. После этого заменяем ключ K удалённым ключом. Удаление ключа происходит так, как описано в предыдущем абзаце.

Основные достоинства

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

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

См. также

Примечания

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

Литература

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

Ссылки

Источник — https://xn--h1ajim.xn--p1ai/index.php?title=B-дерево&oldid=10405437