Обычно цитируемым преимуществом B-деревьев является то, что степень ветвления может быть высокой, что полезно при ограничении количества обращений к диску, необходимых для достижения узла.
Однако предположим, что у нас есть ( k, 2k) B-дерево и наивно реализовывать узлы. Поиск на самом деле будет в
log (n) * k / log (k)
Вместо этого можно было бы выбрать представление значений внутри узлов во вложенных сбалансированных деревьях, так что вставка и удаление ключей в этих узлах останется в журнале (k), а поиск останется в журнале (n) даже для очень больших k.
Существуют ли документы, предлагающие этот подход, или реализации, следующие за ним, или ветвление фактор к вообще слишком низок, чтобы стоить хлопот?