Comment by cschmidt

Here's a paper reviewing the various choices, that is often mentioned in discussions around data structures for text editors:

https://www.cs.unm.edu/~crowley/papers/sds.pdf