I used this data structure in my immutable database (see profile) but eventually switched to a B-tree because I believe RRB trees are inherently flawed. If you do a large number of slices and concats, it is possible for the tree to contain so many gaps it that the tree grows so deep it can't be modified anymore. At first I thought it was a bug in my own implementation but I eventually found the same bug in rrb-vector, the clojure implementation (see CRRBV-14). In fact, the maintainer of that library reached the same conclusion I did and switched to B-trees: https://github.com/jafingerhut/core.btree-vector
Still, I have huge respect for Phil Bagwell and I make heavy use of his hash array mapped trie. But this issue with RRB trees makes it impossible for me to use them, especially for an on-disk data structure whose long lifespan makes it way more likely that the problem will eventually happen.
that is because many implementations bypass strict rebalancing to squeeze out extra concat performance. And because the strict rebalancing algorithm is awful to implement.
I believe Vec is a straight array underneath, which is reallocated at a larger size when full. And Vector in the `im` crate you mentioned looks very interesting indeed.
Still, I have huge respect for Phil Bagwell and I make heavy use of his hash array mapped trie. But this issue with RRB trees makes it impossible for me to use them, especially for an on-disk data structure whose long lifespan makes it way more likely that the problem will eventually happen.
https://rikspucko.koketteriet.se/bjoli/PersistentMap/src/bra...
[0] https://github.com/lacuna/bifurcan