Rope vs Gap Buffer Visualization | How Editors Store Text

The idea: a text that changes in the middle

A text editor keeps the file in memory while you type. A plain string is a bad fit: inserting one letter near the start of a 1 MB file shifts a million bytes. Editors use structures that make edits at the cursor cheap. This page runs the three classic ones side by side on the same text, hello world!, and counts the work each edit costs: bytes moved (existing characters copied or shifted) and nodes touched (tree nodes or pieces visited or created).

The text hello world! stored three ways. Gap buffer: an array with four empty gap cells at position 5. Rope: a root with weight 4, leaf hell on the left, and a node with weight 4 over leaves o wo and rld! on the right. Piece table: the original buffer, an empty add buffer and one piece orig 0, len 12. — The same 12 characters as a gap buffer, a rope and a piece table.

Gap buffer: a hole at the cursor

A gap buffer is one array with an empty stretch, the gap, where the cursor is. The text sits in [0, gapStart) and [gapEnd, capacity). Typing writes into the gap and moves gapStart right: no byte moves. Backspace moves gapStart left: the deleted character simply joins the gap.

The price is paid when the cursor moves. The gap must follow it, so every character between the old and the new cursor is copied across the gap. A jump from the end of a 1 MB file to its start copies 1 MB (Demo: cursor jumps: 37 bytes moved for the gap buffer, 7 for the rope). When the gap is used up, the array is reallocated bigger and the whole text is copied (Demo: gap fills up: 16 bytes in one edit). Emacs uses a gap buffer and moves the gap lazily, at the next edit rather than at every cursor move.

Rope: a tree of short strings

A rope is a binary tree whose leaves hold short strings; read left to right they give the text. Each inner node stores its weight: the number of characters in its left subtree. To find position p, start at the root: if p ≤ weight go left, else go right with p − weight. That is a walk of about log n nodes, like a search in a binary search tree, but keyed by position instead of by value.

Finding position 7 in the rope: at the root 7 is greater than 4, go right with 3; at the next node 3 is at most 4, go left; leaf o wo at offset 3. The path is drawn in red. — Finding a position reads one weight per level, not the characters before it.

An insert splits one leaf (here leaves hold at most 4 characters) and hangs the pieces under new inner nodes; only the characters after the cut inside that leaf are copied, and only the weights on the path change. Moving the cursor is free: it is just a number. The cost is tree upkeep. Repeated splits make the tree deep, so ropes rebalance: this page rebuilds the rope when it gets deeper than 4 or has more than 8 leaves, which copies every character once (Demo: scattered edits: 22 bytes and 30 nodes in that edit). Real ropes keep the tree balanced as they go, like the splay tree or other self-adjusting trees.

Piece table: never change what you have

A piece table keeps the original file in a read-only buffer and appends everything you type to an add buffer that only grows. The document is a list of pieces, each one (buffer, start, length). An insert appends the new text and splits the piece under the cursor into up to three; a delete shrinks a piece or splits it in two. No character is ever moved: the bytes-moved column stays 0 for the piece table in every demo.

Inserting ab at position 6: before, one piece orig 0 len 12. ab is appended to the add buffer. After, three pieces: orig 0 len 6 hello, add 0 len 2 ab, orig 6 len 6 world!. — An insert turns one piece into three and leaves both buffers' old bytes where they are.

Deleted text stays in its buffer, so undo only has to put the old pieces back (Demo: backspace). Typing in one place is cheap too: text right after the newest add piece just makes that piece longer. The weak spot is finding the piece: a plain list is walked from the start, and every edit adds pieces. VS Code's "piece tree" keeps the pieces in a balanced red-black tree to fix that; Microsoft Word and the old Bravo editor used piece tables.

What each edit costs

operation	gap buffer	rope	piece table (list)
type at the cursor	O(1), 0 bytes moved	O(log n) nodes, a few bytes in one leaf	walk to the piece; extend or split it
backspace	O(1)	O(log n) nodes	walk to the piece; shrink or split it
move the cursor by d	O(d) bytes copied	free	free
buffer full / tree too deep	copy all n bytes	rebuild: n bytes, all nodes	never (buffers only grow)
undo	needs a separate log	keep old roots (persistent tree)	restore old pieces
memory	text + the gap	text + a node per leaf	original + every char ever typed

So the pattern of editing decides. Typing a paragraph in one place favours the gap buffer (Demo: type in one place: 7 bytes in total, all from the first cursor move). Jumping around a big file, or many cursors at once, favours the rope and the piece table. See also a tiny editor with undo and CRDTs, which collaborative editors use on top of such a buffer.

What the page leaves out

Real buffers are far bigger: a gap of kilobytes, rope leaves of hundreds of bytes, and growth by doubling again and again. Emacs moves the gap lazily and also tracks line starts; ropes in Xi and Zed store line counts in every node so "go to line 5000" is a tree walk too, and use B-trees rather than binary trees. VS Code's piece tree caches line breaks per piece. The page also skips Unicode (a character can be several bytes), memory-mapped files and how undo history is stored.