← Back to context

Comment by audidude

9 years ago

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