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

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

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

B ⁺ -дерево , удовлетворяющее таким требованиям, называется .

Примечания

Ссылки

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