B+-деревья | это... Что такое B+-деревья? (original) (raw)

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

Литература

Wikimedia Foundation.2010.