B+ дерево

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
Пример B+ дерева, связывающего ключи 1-7 с данными d1-d7. Связи (выделены красным) позволяют быстро обходить дерево в порядке возрастания ключей.

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

Построение[править | править исходный текст]

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

Свойства[править | править исходный текст]

  • В 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
  • Дональд Кнут 4. Генерация всех деревьев. История комбинаторной генерации // Искусство программирования = The Art of Computer Programming. — М.: «Вильямс», 2007. — Т. 4. — С. 160. — ISBN 0-321-33570-8