Edit: Sorry for repeating myself. Still thinking out loud.
I have already started. Not only is the concat faster (which means the derived operations in the rrb tree will be faster), but the derived operations can be done directly since the relaxation is going to be between 16 and 32 elements. A remove will just be a copy 16 out of 17 times.
This will mean that indexing might be slower in the b tree (it will be higher since the fill ratio is lower) part of the tree, and there might be slightly more of the relaxed nodes, but sweet jeebus this is a simplification.
A simplification that makes correctness easier and speeds up all other operations.setting the minimal amount of elements to 24 will still make concat faster, and will make memory waste almost the same (I can use c# inline arrays without feeling too bad).
I have both a fast b+tree and am
Rrb tree. Why didn't I think of this before?!
I have already started. Not only is the concat faster (which means the derived operations in the rrb tree will be faster), but the derived operations can be done directly since the relaxation is going to be between 16 and 32 elements. A remove will just be a copy 16 out of 17 times.
This will mean that indexing might be slower in the b tree (it will be higher since the fill ratio is lower) part of the tree, and there might be slightly more of the relaxed nodes, but sweet jeebus this is a simplification.
A simplification that makes correctness easier and speeds up all other operations.setting the minimal amount of elements to 24 will still make concat faster, and will make memory waste almost the same (I can use c# inline arrays without feeling too bad).
I have both a fast b+tree and am Rrb tree. Why didn't I think of this before?!