3 ms·
You can get the best of piece tables and ropes using a B-tree-based rope- at small sizes, you get a single node that works like a sorted piece table, but you ca
by Rusky 3y ago
You can get the best of piece tables and ropes using a B-tree-based rope- at small sizes, you get a single node that works like a sorted piece table, but you can also scale up to larger documents without the high constant factors of a binary tree.
- josephg 3y agoYou can also get the best of btrees and gap buffers by putting a gap buffer in each leaf node in the tree. That allows the leaves to be much bigger (400 bytes seems to work well in practice) - and that helps keep the tree itself small and thus in the cpu cache. As the article says, it’s quite a complex data structure though.