Mastodon Feed
dysfun@treehouse.systems ("gaytabase") wrote:
argh. i had a neat idea for using roaring bitmaps to store a free space map. then i remembered i need to store values with them.
...and that my nodes are somewhat smaller than page sized so a free space map won't necessarily lead to being able to reuse all the space.
one way around this is to rewrite the entire page contents, meaning the previous block can be freed up in its entirety when other transactions cease to be reading it. it seems you need either periodic compaction and the metadata to power it, or you need a continuous process.
lmdb solves this by having the (single) writer do maintenance as it writes stuff. so i'm going to just use that model because it will suffice for my purposes. but that means doing a page at a time. which is sorta fine, but then it makes me want to do continuous compaction (relocate nodes to be more favourably arranged for traversal) and i'm still not sure what the best algorithm for doing it in this context is.
leaf nodes are the problem - if you do a naive thing of say making a page able to store two levels of node (a subtree of height 2) then you can end up pushing leaves off into their own individual pages. given that leaf nodes are going to tend towards small, you're now multiplying the space required.
i have ideas about how to fix it, but i haven't sat down and worked it out yet.