21
правка
Изменения
м
→B и B+ деревья
** Сильно ветвящиеся деревья, так размер узла будет ~странице и высота будет минимальной
=== $B $ и $B+ $ деревья ===
* $B$ деревья степени $n$
** Указатели и ключи хранятся в узлах
* $B+$ деревья степени $n$
** От $\frac{n}{2}$ до $n $ детей
** Указатели хранятся в листьях
* $B+ $ меньше данных в узлах - сильнее ветвятся* $B+ $ на одну страницу глубже
Мы храним корень и несколько первых уровней в памяти для быстрого обращения, из-за этого время работы может резко возрастать, когда заканчивается закешированные уровни.
