You would probably enjoy reading about an alternative implementation for STL's std::deque, called a tier vector[1][2].
It supports O(1) push_front/pop_front/push_back/pop_back/operator[]/at (like you would expect from a deque) but also O(sqrt(N)) insert and remove from middle!!!
The paper was from 1999 and 2001 but I only learned about it from a recent HN post[3] where some guy rediscovered it (20 years too late). I still wonder why this design lost to the std::deque we have in STL today.
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/