- B+ деревья
-
B+ деревья
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.