Comment by colanderman

9 years ago

I've been doing the same thing (implementing a text editor for fun) and settled on a data structure which is a hybrid rope+2-3 tree+B+tree+gap buffer. I don't know what to call it but maybe someone here has seen it before.

Basically the idea is, the inner nodes are a 2-3 tree which track the size of each child like a rope does. The leaves are gap buffers of a fixed size (a few cache lines), which, when full, split into two like leaves of a B+tree. So you get the dense-ish packing of a gap buffer with the O(log n) performance guarantee of a 2-3 tree, while avoiding the potential linear copies associated with ropes and gap buffers.

(I know this is overkill for a toy text editor but it wouldn't be a side project if it weren't!)

I did something like this recently too. A b+tree w/ linked leaves containing piecetables in the leaf nodes. To avoid the memmove() costs it uses the right-edge of the leaf to keep a sorting queue so the operations are still O(1) inside the leaf.

I still need to finish up deletions, but early performance numbers are showing similar/better than the RBTree approach while being much more cacheline/allocation friendly.

Ultimately, I want to use this in a replacement for GtkTextBuffer/GtkTextView in gtk 4.x.

https://github.com/chergert/pieceplustree