B-tree лежит в файле в виде россыпи блоков. Дерево оперирует блоками (хранит в одних блоках указатели на другие) в виде ID этих блоков (а не поинтеров в памяти), по которым (ID) код ходит в некий кеш блоков. Если в кеше нет, то кеш знает по какому смещению на диске блок лежит. Блок (страница) имеет фиксированный размер, допустим.
Блоки надо иногда выделять, и обычно сильно реже освобождать.
Выделять блоки можно тупо с конца файла, либо из каталога свободных блоков - данный пост как раз об этом. При освобождении блока, он, естественно, продолжает занимать на диске в файле место какое и занимал, не сдвигать же содержимое файла назад и не фиксить же все ID блоков после него.
Как нормальные люди управляют удалением и переиспользованием удалённых блоков в хранилках СУБД? Первое что приходит на ум:
1) Есть тупой односвязный список удалённых блоков. В заголовке файла лежит один ID, ссылающийся на голову этого списка. Если блок удаляется, мы ставим в качестве головы его, а предыдущую голову крепим к этому. Если надо выделить блок, смотрим не пуст ли этот список. Если да, то потребляем голову этого списка. Недостатки: лишние обращения к диску: чтобы выделить какой-то блок, надо его зачитать в память (чтобы взять из него указатель на следующий блок, дабы поставить теперь его на роль головы этого списка). То есть выделение нового блока - всегда какая-то возня с диском, забивание кеша блоков ненужными данными с диска. Хотелось бы так: мы знаем что по такому-то смещению лежит блок, его статус «свободен», но читать его не нужно, возможно только что мы его потом запишем уже с новыми данными.
2) Хранить специальные блоки, выделяя их на общих правах со всеми, в которых будет тупо лежать FILO очередь свободных блоков. Ну то есть, это такой массив, побитый на блоки, наращиваемый блоками, поддерживающий только push_back + pop_back, хранящий ID свободных блоков. Массив может расти, потребляя блоки, сокращаться, освобождая блоки. Тут рекурсивная проблема хранения уже этих свободных блоков... Плюсы: в памяти всегда есть страничка с кучей ID свободных блоков.
3) Хранить в начале файла специальный массив фиксированного размера на неск. мегабайт, куда можно добавить лимитированное число свободных блоков. Какая-то жопная идея... Про битмаску на все блоки я молчу...
4) Как-то запилить серию специальных ключей в само B-дерево, хранить их на равных правах со всеми остальными ключами и в них как-то держать инфу про свободные блоки. Будут прикольный эффекты: ты освобождаешь блок, пытаешься записать на эту тему новый ключ, а эта операция сразу же потребляет только что освободившийся блок и ключ уже не нужен и блок снова надо освободить )
Пока самым перспективным кажется направление (2). Некий линейный тупой массив INT-ов (ID-шников свободных блоков), без пределов роста, хранящийся как последовательность блоков и блоки эти формируют список. В памяти всегда закеширован хвост этого списка блоков, т.е. большой задний кусок этого массива ID-шников, в нём легко совершать частые манипуляции без похода на диск (возможно отражая оперции в WAL-логе), а новый такой блок нужен только если исчерпали последний. Может понадобиться освобождать и эти блоки и как-то хранить уже их ID. Возможно можно резервировать место под них в их самих...
