Комментарии 3
Там ещё указатели между узлами одного уровня есть для навигации; это, конечно, технические детали, но при навигации по индексу они крайне полезны.
Статья хорошая.
"B", согласно вики, Кнуту и прочим, это bushy и broad - по новым идеям, а Bayer для Boeing - исходно.
Полезность B-деревьев в оперативной памяти замечается в случае, если для бинарных получается слишком много торможения от того, что данные разбросаны по памяти и плохо кэшируются. Для диска это было очевидно изначально, а вот для оперативы - только в последние десятилетия и не всегда. Но для диска с 2000 года есть LSM tree, и для SSD оно может быть полезнее (хоть и сильно толще в объёме).
Реализация ваша понятная и простая, это хорошо. Я для себя делал аналогичное для Python, для проверки понимания, основы подходов сходятся. "Взрослые" реализации ещё заботятся о возможности ключей и данных неравной длины. Например, в BerkeleyDB ещё в 1-й (до неприятных лицензий) использовались "overflow pages". Современные реализации типа как в Postgres ещё хитрее. Кстати, там ещё стараются поддерживать не максимальное заполнение страниц индекса - говорят, улучшает производительность. В общем, это отдельный сложный мир.
B-Tree — сбалансированный куст поиска