B*-дерево — разновидность B-дерева, в которой каждый узел дерева заполнен не менее чем на ⅔ (в отличие от B-дерева, где этот показатель составляет 1/2).
B*-деревья предложили Рудольф Байер и Эдвард МакКрейт, изучавшие проблему компактности B-деревьев. B*-дерево относительно компактнее, так как каждый узел используется полнее. В остальном же этот вид деревьев не отличается от простого B-дерева.
Для выполнения требования «заполненность узла не менее 2/3», приходится отказываться от простой процедуры разделения переполненного узла. Вместо этого происходит «переливание» в соседний узел. Если же и соседний узел заполнен, то ключи приблизительно поровну разделяются на 3 новых узла.
B+-дерево, удовлетворяющее таким требованиям, называется B<sup>*+</sup>-деревом[1].
Энциклопедичный YouTube
-
1/3Просмотров:47 5291 1465 663
-
B-дерево
-
АиСД 9. Декартово дерево, B-дерево.
-
b-дерево / b tree
Субтитры
Примечания
- ↑ 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.
| Двоичные деревья | |
|---|---|
| Самобалансирующиеся<br/> двоичные деревья |
|
| B-деревья |
|
| Префиксные деревья |
|
| Двоичное разбиение пространства | |
| Недвоичные деревья |
|
| Разбиение пространства |
|
| Другие деревья |
|
| Алгоритмы |
|
Эта страница в последний раз была отредактирована 4 мая 2022 в 12:42.
Обычно почти сразу, изредка в течении часа.