A refreshing break from Molt News. Now I want to check how vectors are implemented in my favorite languages.

If you like this kind of thing, Bifurcan [0] is a Java library with implementations of RBB-trees and related (fast) immutable data structures.

[0] https://github.com/lacuna/bifurcan

This is Rhombus’ native data type! Such a nice data structure.

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.