B+-деревья

B+-деревья

B+-деревья

A simple B+ tree example linking the keys 1-7 to data values d1-d7. Note the linked list (red) allowing rapid in-order traversal.

B+ дерево — структура данных, представляет собой дерево поиска. Является модификацией B-дерева, истинные значения ключей которого содержатся только в листьях, а во внутренних узлах — ключи разделители, содержащие диапазон изменения ключей для поддеревьев.

Содержание

Построение B+ дерева

При построени B+ дерева, его временами приходится перестраивать. Это связано с тем, что количество ключей в каждом узле (кроме корня) должно быть от k, до 2k, где k — степень дерева. При попытке вставить в узел (2k+1)-й ключ возникает необходимость разделить этот узел. В качестве ключа-разделителя сформированных ветвей выступает (k+1)-й ключ, который помещается на соседний ярус дерева. Особым же случаем является разделение корня, так как в этом случае увеличивается число ярусов дерева. Особенностью разделения листа B+ дерева является то, что он делится на неравные части. При разделении внутреннего узла или корня возникают узлы с равным числом ключей k. Разделение листа может вызвать «цепную реакцию» деления узлов, заканчивающуюся в корне.

Другие особенности B+ дерева

В B+ дереве легко реализуется независимость программы от структуры информационной записи.

Поиск обязательно заканчивается в листе.

Удаление ключа имеет преимущество — удаление всегда происходит из листа.

Другие операции выполняются аналогично B-деревьям.

B+ деревья требуют больше памяти чем B-деревья для представления.

B+ деревья имеют возможность последовательного доступа к ключам.

Поиск

 function search(record r)
   u := root
   while (u is not a leaf) do
     choose the correct pointer in the node
     move to the first node following the pointer
     u := current node
   scan u for r

Литература

  • Зубов В. С., Шевченко И. В. Глава 6. Поиск в недвоичных деревьях - B-деревьях // Структуры и методы обработки данных. Практикум в среде Delphi. — Филинъ, 2004. — С. 144-164. — ISBN 5-9216-0053-9

Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать реферат

Полезное


Смотреть что такое "B+-деревья" в других словарях:

  • Деревья (песня) — «Деревья» …   Википедия

  • Деревья (сингл) — «Деревья» …   Википедия

  • ДЕРЕВЬЯ-ПАМЯТНИКИ — деревья, взятые под охрану государства как ценные биология, и культурно исторические объекты. Деревья памятники. Охраняемый государством 600 летний дуб (с.Кобыльня. Шолданештский р н,МССР). Например, известный дуб в Ясной Поляне, чинара “Семь… …   Экологический словарь

  • деревья — Кельты считали священными как отдельные деревья, особенно дубы, так и целые леса, в частности, рощи и дубравы. По представлениям кельтов, деревья представляли собой связующее звено между верхним миром, или миром смертных, и нижним, подземным, то… …   Энциклопедия мифологии

  • Деревья — один из основных и самых распространенных растительных компонентов среды, участвующий во всех процессах живого вещества планеты. Производят необходимые вещества для питания, дыхания, существования других организмов. Морфологически отличаются от… …   Экологический словарь

  • ДЕРЕВЬЯ САБЛЕВИДНЫЕ — см. Лес пьяный и деревья саблевидные. Геологический словарь: в 2 х томах. М.: Недра. Под редакцией К. Н. Паффенгольца и др.. 1978 …   Геологическая энциклопедия

  • Деревья умирают стоя — Название пьесы (1949) испанского драматурга Алехандро Касоны (псевдоним Алехандро Родригеса Альвареса, 1903 1965). Иносказательно: о достойном поведении в трудных обстоятельствах. Энциклопедический словарь крылатых слов и выражений. М.: «Локид… …   Словарь крылатых слов и выражений

  • ДЕРЕВЬЯ НА АСФАЛЬТЕ — ДЕРЕВЬЯ НА АСФАЛЬТЕ, СССР, Беларусьфильм, 1984, цв., 80 мин. Семейная драма. В ролях: Галина Макарова (см. МАКАРОВА Галина Климентьевна), Леонид Кулагин (см. КУЛАГИН Леонид Николаевич), Светлана Кузьмина (см. КУЗЬМИНА Светлана), Виктор Мирный,… …   Энциклопедия кино

  • Деревья скоро садят, да не скоро с них плод едят. — Деревья скоро садят, да не скоро с них плод едят. См. ТЕРПЕНИЕ НАДЕЖДА …   В.И. Даль. Пословицы русского народа

  • деревья — мертвые (Горький); окоченелые (Арцыбашев); сумрачно странно безмолвные (Бальмонт); унылые (Чехов) Эпитеты литературной русской речи. М: Поставщик двора Его Величества товарищество Скоропечатни А. А. Левенсон . А. Л. Зеленецкий. 1913 …   Словарь эпитетов

  • деревья — сущ., кол во синонимов: 2 • деревье (2) • спёнки (2) Словарь синонимов ASIS. В.Н. Тришин. 2013 …   Словарь синонимов


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»