23-10-2023
B-дерево (по-русски произносится как Б-дерево) — структура данных, дерево поиска. С точки зрения внешнего логического представления, сбалансированное, сильно ветвистое дерево во внешней памяти.
Использование B-деревьев впервые было предложено Р. Бэйером (англ. R. Bayer) и Е. МакКрейтом (англ. E. McCreight) в 1970 году.
Сбалансированность означает, что длина любых двух путей от корня до листов различается не более, чем на единицу.
Ветвистость дерева — это свойство каждого узла дерева ссылаться на большое число узлов-потомков.
С точки зрения физической организации B-дерево представляется как мультисписочная структура страниц внешней памяти, то есть каждому узлу дерева соответствует блок внешней памяти (страница). Внутренние и листовые страницы обычно имеют разную структуру.
Содержание |
Структура B-дерева применяется для организации индексов во многих современных СУБД.
B-дерево может применяться для структурирования (индексирования) информации на жёстком диске (как правило, метаданных). Время доступа к произвольному блоку на жёстком диске очень велико (порядка миллисекунд), поскольку оно определяется скоростью вращения диска и перемещения головок. Поэтому важно уменьшить количество узлов, просматриваемых при каждой операции. Использование поиска по списку каждый раз для нахождения случайного блока могло бы привести к чрезмерному количеству обращений к диску, вследствие необходимости осуществления последовательного прохода по всем его элементам, предшествующим заданному; тогда как поиск в B-дереве, благодаря свойствам сбалансированности и высокой ветвистости, значительно позволяет сократить количество таких операций.
Относительно простая реализация алгоритмов и существование готовых библиотек (в том числе для C) для работы со структурой B-дерева обеспечивают популярность применения такой организации памяти в самых разнообразных программах, работающих с большими объёмами данных.
B-деревом называется дерево, удовлетворяющее следующим свойствам:
Свойство 2 можно сформулировать иначе: каждый узел B-дерева, кроме листьев, можно рассматривать как упорядоченный список, в котором чередуются ключи и указатели на сыновей.
Если ключ содержится в корне, он найден. Иначе определяем интервал и идём к соответствующему сыну. Повторяем, пока не дошли до листа.
Будем называть деревом потомков некоего узла поддерево, состоящее из этого узла и его потомков.
Вначале определим функцию, которая добавляет ключ K к дереву потомков узла x. После выполнения функции во всех пройденных узлах, кроме, может быть, самого узла x, будет меньше , но не меньше , ключей.
Теперь определим добавление ключа K ко всему дереву. Буквой R обозначается корневой узел.
Если корень одновременно является листом, то есть в дереве всего один узел, мы просто удаляем ключ из этого узла. В противном случае сначала находим узел, содержащий ключ, запоминая путь к нему. Пусть этот узел - .
Если - лист, удаляем оттуда ключ. Если в узле осталось не меньше ключей, мы на этом останавливаемся. Иначе мы смотрим на количество ключей в следующем, а потом в предыдущем узле. Если следующий узел есть, и в нём не менее ключей, мы добавляем в ключ-разделитель между ним и следующим узлом, а на его место ставим первый ключ следующего узла, после чего останавливаемся. Если это не так, но есть предыдущий узел, и в нём не менее ключей, мы добавляем в ключ-разделитель между ним и предыдущим узлом, а на его место ставим последний ключ предыдущего узла, после чего останавливаемся. Наконец, если и с предыдущим ключом не получилось, мы объединяем узел со следующим или предыдущим узлом, и в объединённый узел перемещаем ключ, разделяющий два узла. При этом в родительском узле может остаться только ключей. Тогда, если это не корень, мы выполняем аналогичную процедуру с ним. Если мы в результате дошли до корня, и в нём осталось от 1 до ключей, делать ничего не надо, потому что корень может иметь и меньше ключей. Если же в корне не осталось ни одного ключа, исключаем корневой узел, а его единственный потомок делаем новым корнем дерева.
Если - не лист, а K - его -й ключ, удаляем самый правый ключ из поддерева потомков -го сына , или, наоборот, самый левый ключ из поддерева потомков -го сына . После этого заменяем ключ K удалённым ключом. Удаление ключа происходит так, как описано в предыдущем абзаце.
Основной недостаток В-деревьев состоит в отсутствии для них эффективных средств выборки данных (т.е. метода обхода дерева), упорядоченных по отличному от выбранного ключу.
Это заготовка статьи о программировании. Вы можете помочь проекту, исправив и дополнив её. |
Дерево (структура данных) | |
---|---|
Двоичное дерево поиска · Дерево (теория графов) · Древовидная структура | |
Двоичные деревья | Двоичное дерево · T-дерево |
Самобалансирующиеся двоичные деревья | АА-дерево · АВЛ-дерево · Красно-чёрное дерево · Расширяющееся дерево · Дерево со штрафами · Декартово дерево · Дерево Фибоначчи |
B-деревья | B-дерево · 2-3-дерево · B+ дерево · B*-дерево · UB-дерево · 2-3-4 дерево · (a,b)-дерево · Танцующее дерево |
Префиксные деревья | Суффиксное дерево · Radix tree · Ternary search tree |
Двоичное разбиение пространства | k-мерное дерево · VP-дерево |
Недвоичные деревья | Дерево квадрантов · Октодерево · Sparse Voxel Octree · Экспоненциальное дерево · PQ-дерево |
Разбиение пространства | R-дерево · R+-дерево · R*-дерево · X-дерево · M-дерево · Дерево Фенвика · Дерево отрезков |
Другие деревья | Куча · TTH · Finger tree · Metric tree · Cover tree · BK-tree · Doubly-chained tree · iDistance · Link-cut tree |
Алгоритмы | Поиск в ширину · Поиск в глубину · DSW-алгоритм · Алгоритм связующего дерева |
Структуры данных (список) | |
---|---|
Типы | |
Массивы | |
Списки | |
Деревья |
B-дерево • Двоичное дерево поиска • Куча |
Графы |
B-дерево.