This idea of B-trees does generalize to other branching factors, of course, and it even allows for guaranteed logarithmic time of slice and concat operations, with no need to do O(n) work to rebalance a tree, ever. I was looking at how to do efficient concat, guarnateed, after trying to find an RRB-tree implementation without bugs that guarantees that run time, but haven’t found one yet (I begin to suspect whether that is possible – the research papers are not very explicit on some parts of the implementation). Here is an article on how to do the slice and concat operations in O(log n) time on B-trees that represent vectors: https://github.com/jafingerhut/core.btree-vector/blob/master/doc/intro.md
1 Like