This made me search around about unsorted B-tree-like collections. Turns out Clojure[1] and the im immutable-collections crates in Rust[2] use a structure called an RRB-tree, and searching 'blist' (because why not) turned up a Python module[3]. So, yes, a thing!
Tricky bit is trying to work well when used like a plain vector too. Clojure's RRB-tree special-cased repeated small appends to the end to help with this, and the Rust page mentions a clever chunking technique for append/prepend. And I imagine largeish leaf pages might help with average prepend/append/iteration overhead, at some cost when inserting in the middle?
Anyway, just neat that it's been taken further than I realized!
Tricky bit is trying to work well when used like a plain vector too. Clojure's RRB-tree special-cased repeated small appends to the end to help with this, and the Rust page mentions a clever chunking technique for append/prepend. And I imagine largeish leaf pages might help with average prepend/append/iteration overhead, at some cost when inserting in the middle?
Anyway, just neat that it's been taken further than I realized!
[1] https://infoscience.epfl.ch/record/213452/files/rrbvector.pd...
[2] https://docs.rs/im/15.0.0/im/struct.Vector.html
[3] https://pypi.org/project/blist/