Если мы навтыкали в B-tree ключей, а потом несколько случайных из них удалили, то маловероятно, что дерево будет занимать памяти столько же, сколько бы оно занимало, если бы мы в пустое дерево добавили все оставшиеся ключи с начала.

То есть, когда мы удаляем узел в каком-нибудь std::map, деаллокатору говорят "верни память, выделенную под этот узел", память освобождается, в дереве крутятся узлы и всё. В B-Tree узлы хитрее, а удаление одного ключа далеко не всегда означает освобождение какой-либо памяти или удаление каких-либо узлов.

Насколько B-Tree подходит для приложений, в которых идёт оперативное добавление-удаление ключей?

Имеется приложение, хранящее 1 млрд ключей в b-tree. В это дерево активно добавляются ключи и при переходе их количества за предел, запускается процедура поиска и удаления старых. В дереве поддерживается одно и то же логическое количество записей.

При этом приложение медленно и верно растёт по памяти, а valgrind молчит. Возникают подозрения на описанный в первом абзаце эффект. Эмуляция проводилась на дереве меньшего размера, эффект проявляется, но потребление памяти постепенно стабилизируется и перестаёт расти.

MasterZivgbl37004Если мы навтыкали в B-tree ключей, а потом несколько случайных из них удалили, то маловероятно, что дерево будет занимать памяти столько же, сколько бы оно занимало, если бы мы в пустое дерево добавили все оставшиеся ключи с начала.

А с чего такие далеко идущие выводы?

Если valgring молчит, то каким образом ты узнаёшь, что память течёт?
1. Далеко идущие выводы из устройства b-tree.
2. Смотрю на количество занимаемой процессом памяти. Логически постоянно одно и то же количество объектов, а память всё жрёт и жрёт.