As a counterpoint, I’ve been working on collaborative text editing. I ended up implementing a custom b-tree because we needed a few features that I couldn’t find in any off the shelf library:

- My values represent runs of characters in the document.

- Inserts in the tree may split a run.

- Runs have a size - 0 if the run is marked as deleted or the number of characters otherwise. The size changes as we process edits

- Every inserted character has an ID. I need to be able to look up any run by its ID, and then edit it. (Including querying the run’s current position in the tree and editing the run’s size).

It’s an interesting data structure problem, and it took a few weeks to have a good solution (and a few weeks more later rewriting it in safe rust & improving performance in the process).

I love this stuff. I think it’s pretty rare to find a reason to code your own collection types these days, but it certainly comes up from time to time!