B + деревья, выбирая порядок

Question

Я изучаю деревья B + впервые. Я просто хочу знать, на каком основании разработчик выбирает порядок дерева B +?

Кроме того, есть что-то вроде деревьев B + для учебника чайников? Я отчаянно нужно это.

Answer 1

Если вы имеете в виду «порядок» количество исходящих указателей в узле дерева B +, вы должны рассмотреть порядок k , чтобы узел на диске был кратным размеру сектора диска или размер блока файловой системы, например 4 КБ.

Если вы читаете узел с диска, то диск (я предполагаю, что здесь диски, а не твердотельные накопители) должен искать положение узла и читать узел. Время поиска намного больше, чем фактическое время передачи для узла на диске для узла размером в несколько килобайт. Так что выбор порядка, чтобы узел имел на диске размер 64 КБ, мог бы быть хорошим выбором.

Answer 2

В идеале вам нужно выбрать заказ, который имеет справочную местность , чтобы помочь с кэшированием. Также может быть полезен порядок, который поощряет последовательное сканирование ключей. В целом это будет зависеть от ваших данных.