B*-дерево

Материал из Seo Wiki - Поисковая Оптимизация и Программирование

Перейти к: навигация, поиск

B-дерево — разновидность B-дерева, в которой каждый узел дерева заполнен не менее чем на 2/3 (в отличие от B-дерева, где этот показатель составляет 1/2). B+ дерево, удовлетворяющее таким требованиям называется B+* деревом.

B*-деревья предложили Р. Бэйер и Е. МакКрейт, изучавшие проблему компактности B-деревьев. B*-дерево относительно компактнее, так как каждый узел используется полнее. В остальном же этот вид деревьев не отличается от простого B-дерева.

Для выполнения требования (заполненность узла не менее 2/3), приходится отказываться от простой процедуры разделения переполненного узла. Вместо этого происходит «переливание» в соседний узел. Если же и соседний узел заполнен, то ключи приблизительно поровну разделяются на 3 новых узла.

Ссылки

cs:B* strom

en:B*-tree de:B*-Baum es:Árbol-B* ja:B*木

Личные инструменты

Served in 0.079 secs.