Rope vs Piece Table data structure

I'm building a text editor, and I'm currently deciding on the data structure behind it.

The text editor is designed to open multiple gigabytes worth of data, and support fast edits (insertions & deletions) anywhere in the text without having to move every character. The indexing (getting a character at say position 5) should also be fast.

There are two data structures in which I'm considering, which are the Rope and Piece Table.

The Rope's time complexity fits my needs, as it has O(log(n)) insertion, deletion, and indexing. However it appears an disadvantage is that it takes up a lot of memory when you have a bunch of edits.

The Piece Table seems like a good choice as the insertion, deletion are pretty quick. However, indexing seems to be its downside. In order to find the character at index i, you have to iterate through all the pieces in the table. That means if you have thousands of pieces (ie edits), then indexing is going to get a whole lot slower. However, it seems that a solution is to use a BST like VSCode.

Which one is the better option when you're going to have many edits on GB's large files?

https://stackoverflow.com/questions/66880254/rope-vs-piece-table-data-structure March 31, 2021 at 08:56AM