| Hmmm. This comment made me think. If you would do a radix tree that degrades to a b+tree, you would get a couple of things. The b+tree concat and subsequently insertions and removal, is faster than the rrb tree one, but yields more relaxed nodes. If you have a relaxed root, you know the size of every subtree. If the the subtree is dense you can easily calculate the shift, meaning you get dense radix tree subnodes with fast lookup. This gets you the benefits of a relaxed b tree, but no issues with accidentally having too deep shifts since they are relative to where the dense subtree starts. This could be done to a rrb tree as well, which would mitigate the issues you are seeing, but would still lead to an arbitrarily deep tree if the concatenation isn't done properly. The only tradeoff would be slower indexing on relaxed trees because more nodes would end up unbalanced, but at the same time concatenations, insertions and removals would probably be faster. I will try to implement this. Edit: no, seriously. This is a splendid idea. The b tree concat is faster than the rrb tree "full" merge. And simpler. And storing the tree subtree height in a byte somewhere means we can go from relaxed to dense and then do a proper radix tree search. (I have one of those rrb tree implementations that probably fails, btw. It has a proper concat, but the improper one is so much faster. I know. I am ashamed.) |