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

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 https://github.com/chergert/pieceplustree