B⁺-дерево — структура данных на основе B-дерева, сбалансированное -арное дерево поиска с переменным, но зачастую большим количеством потомков в узле. B⁺-дерево состоит из корня, внутренних узлов и листьев, корень может быть либо листом, либо узлом с двумя и более потомками.
Изначально структура предназначалась для хранения данных в целях эффективного поиска в блочно-ориентированной среде хранения — в частности, для файловых систем; применение связано с тем, что в отличие от бинарных деревьев поиска, B⁺-деревья имеют очень высокий коэффициент ветвления (число указателей из родительского узла на дочерние, обычно порядка 100 или более), что снижает количество операций ввода-вывода, требующих поиска элемента в дереве.
Вариант B-дерева, в котором все значения сохранялись в листовых узлах, систематически рассмотрен в 1979 году[1], притом отмечено, что такие структуры использовались IBM в технологии файлового доступа для мейнфреймов VSAM[en] по крайней мере с 1973 года.
Структура широко применяется в файловых системах — NTFS, ReiserFS, NSS, XFS, JFS, ReFS и BFS используют этот тип дерева для индексирования метаданных; BeFS также использует B⁺-деревья для хранения каталогов. Реляционные системы управления базами данных, такие как DB2, Informix, Microsoft SQL Server, Oracle Database (начиная с версии 8), Adaptive Server Enterprise и SQLite поддерживают этот тип деревьев для табличных индексов. Среди NoSQL-СУБД, работающих с моделью «ключ—значение», структура данных реализована для доступа к данным в CouchDB, MongoDB (при использовании подсистемы хранения WiredTiger[en]) и Tokyo Cabinet[en].
B⁺-деревом называется сбалансированное -арное дерево поиска порядка , удовлетворяющее следующим свойствам:
Построение B⁺-дерева может требовать перестройки промежуточной структуры, это связано с тем, что количество ключей в каждом узле (кроме корня) должно быть от до , где — степень (или порядок) дерева. При попытке вставить в узел ( )-й ключ возникает необходимость разделить этот узел, в качестве ключа-разделителя сформированных ветвей выступает ( )-й ключ, который помещается на соседний ярус дерева. Особым же случаем является разделение корня, так как в этом случае увеличивается число ярусов дерева. Особенностью разделения листа B⁺-дерева является то, что он делится на неравные части. При разделении внутреннего узла или корня возникают узлы с равным числом ключей . Разделение листа может вызвать «цепную реакцию» деления узлов, заканчивающуюся в корне.
Корень B⁺-дерева является отправной точкой для всего спектра значений, в котором каждый внутренний узел представляет собой подинтервал.
Например, пусть необходимо найти значение ключа в B⁺-дереве. Для этого ищется листовой узел, содержащий значение . В каждом внутреннем узле нужно выяснить, на какой последующий дочерний узел необходимо следовать, внутренний узел B⁺-дерева имеет не более потомков, где каждый из них представляет собой отдельный подынтервал. Выбирается соответствующий узел с помощью поиска в ключевых значениях узла:
Function: search (k)
return tree_search (k, root);
Function: tree_search (k, node)
if node is a leaf then
return node;
switch k do
case k < k[0]
return tree_search(k, p[0]);
case k[i] ≤ k < k[i + 1]
return tree_search(k, p[i + 1]);
case k[d] ≤ k
return tree_search(k, p[d + 1]);
(Данный псевдокод рассчитан на то, что дубликаты игнорируются.)
Для добавления нового ключа или новой записи в первую очередь необходимо найти узел, в который их необходимо добавить. В этом случае алгоритм таков:
B-деревья, в отличие от B⁺-деревьев, расширяются со стороны корня, а не листьев.
Для удаления ключа или записи в первую очередь необходимо найти листовой узел, в котором они находятся. Алгоритм удаления от листового узла:
Объединение может распространяться на корень, тогда происходит уменьшение высоты дерева.
Вычислительная сложность каждой операции в худшем случае:
, где
— порядок дерева или коэффициент ветвления;
— количество элементов в дереве ветвей в узлах дерева.
Для улучшения этой статьи желательно: |
Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".
Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.
Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .