B*-дерево

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

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

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

B^+-дерево, удовлетворяющее таким требованиям, называется B^*+-деревом[1].

Примечания

1. Rigin A. M., Shershakov S. A. SQLite RDBMS Extension for Data Indexing Using B-tree Modifications (англ.). Proceedings of the Institute for System Programming of the RAS (Proceedings of ISP RAS). Institute for System Programming of the RAS (ISP RAS) (10 сентября 2019). doi:10.15514/ispras-2019-31(3)-16. Дата обращения: 29 августа 2021. Архивировано 29 августа 2021 года.

Ссылки

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