Если инсертить в дерево возрастающие ключи, что часто и бывает, то самый правый листовой блок будет всё время линейно расти. Потом он поделится, например пополам, пробросив разделитель наверх, и правая половинка снова начнет линейно расти вправо.
А «левые», наполовину заполненные блоки, так и будут лежать, вечно храня половину пустого пространства.
Вот что почитать на тему разных алгоритмов деления? Например в случае выше можно было для листового блока завести две статистики - «число вставок в левую половину» и "-//- в правую". Делить блок обратно пропорционально - т.е. в случае выше «левые» продукты деления бы получались жирные, а правый пустой (и средняя заполненность блока в дереве была бы под 99%, а не 50%), а деления случались бы реже в 2 раза.
Короче интересны такие статистическо-эвристические штуки и мировой опыт. Сырцы постгреса почитываю бывает, до сабжеыой части не дошел.
