Gap Buffer vs Piece Table: Text Editor Data Structures
A gap buffer keeps free space at the cursor; a piece table never edits the original text. How editors store documents, compared side by side.
A gap buffer and a piece table are two classic data structures for storing the text inside an editor. A gap buffer is a single array with a block of unused space parked at the cursor, so typing fills the gap instead of shifting the whole document. A piece table never modifies the original file at all; it keeps an append-only buffer of new text and a list of “pieces” describing how to stitch the two together. Both exist to solve the same problem: a plain string is a terrible container for a document that changes one keystroke at a time.
Why a plain string doesn’t work
Store a document as one contiguous array of characters and every insertion in the middle forces you to shift every character after it. For a large file, typing a single letter near the top means moving almost the entire buffer. In Big O notation that is O(n) per keystroke, and editors perform a lot of keystrokes.
The opposite extreme, a linked list of characters, makes insertion O(1) at a known position but wastes memory on pointers, destroys cache locality, and makes jumping to a given offset slow. Real editors use structures that sit between those extremes.
How a gap buffer works
A gap buffer is an array that is larger than the text it holds. The unused slots form a contiguous gap that sits at the cursor position:
H e l l o [ _ _ _ _ _ ] w o r l d
^ gap start ^ gap end
- Typing writes the character into the first slot of the gap and moves the gap start forward by one. That is O(1).
- Backspace moves the gap start back by one. Also O(1); the character is not erased, just absorbed into the gap.
- Moving the cursor means moving the gap. To shift it left by k characters, you copy k characters from before the gap to the end of the gap. The cost is proportional to the distance moved, not the document size.
- Running out of gap triggers a reallocation: allocate a bigger array, copy everything over, and open a fresh gap. With geometric growth this is cheap when spread across many inserts, the same argument as in amortized analysis.
The gap buffer’s strength is locality. People tend to type in bursts at one spot, so most edits happen right at the gap and cost almost nothing. The text is also nearly contiguous: two array slices, before and after the gap, which makes searching and rendering simple.
Its weaknesses show up with non-local edits. Multiple cursors spread across a file, a search-and-replace touching hundreds of locations, or jumping between distant points forces the gap to move repeatedly, and each move copies text. Undo also isn’t built in; you track edits separately.
How a piece table works
A piece table keeps two buffers and a list:
- Original buffer — the file as loaded from disk. It is read-only and never changes.
- Add buffer — an append-only buffer. Every character the user types is appended here.
- Piece list — an ordered sequence of descriptors, each saying “take
lengthcharacters from buffer X starting atoffset.”
The document is whatever you get by walking the piece list and concatenating the referenced spans. Suppose the original text is Hello world and the user inserts , big after Hello:
Original: "Hello world"
Add: ", big"
Pieces:
1. original, offset 0, length 5 -> "Hello"
2. add, offset 0, length 5 -> ", big"
3. original, offset 5, length 6 -> " world"
An insertion splits at most one existing piece and adds a new one. A deletion trims or splits pieces. No text is ever copied or moved; only the small descriptors change. Because neither buffer is ever overwritten, undo becomes cheap: keep old versions of the piece list, or record each change to it, and reverting is a matter of restoring descriptors. That immutability is the same idea behind copy-on-write storage.
The cost is indirection. Finding the character at offset 50,000 means walking pieces until the running length reaches that point. With a plain array of pieces that is linear in the number of pieces, which grows with every edit. Production implementations store the pieces in a balanced tree where each node caches the total length of its subtree, turning lookups into O(log n) in the number of pieces. Some also cache line-break counts per node so “go to line 10,000” is fast.
Gap buffer vs piece table compared
| Gap buffer | Piece table | |
|---|---|---|
| Core idea | Array with movable free space at the cursor | Immutable original + append-only add buffer + list of spans |
| Insert at cursor | O(1) amortized | O(1) with a list, O(log n) with a tree |
| Edits far apart | Expensive; the gap must move | Cheap; only descriptors change |
| Memory overhead | The gap itself | Piece descriptors, plus deleted text kept in buffers |
| Loading a large file | Copy the file into the array | Point one piece at the original buffer |
| Undo and redo | Implemented separately | Natural fit; old piece lists stay valid |
| Reading contiguous text | Easy; two slices | Requires walking pieces |
| Implementation complexity | Low | Moderate, higher with a balanced tree |
Where ropes fit in
A third option is the rope, a balanced binary tree whose leaves hold short strings. Ropes make insertion, deletion, and concatenation O(log n) anywhere in the document and are easy to share between versions, which suits very large files and concurrent edits. A piece table backed by a balanced tree ends up looking similar to a rope; the main difference is that a piece table’s leaves point into shared buffers instead of owning their own text.
Collaborative editors add yet another layer. When several people edit the same document at once, the storage structure is usually paired with a merge model such as a CRDT, which decides how concurrent edits combine. The gap buffer or piece table still holds the text; the CRDT decides what the text should be.
Which one should you choose?
If you are building a small editor, a text field, or a REPL where edits cluster at one cursor, a gap buffer is hard to beat. It is a few dozen lines of code and its performance profile matches how people type.
If you need fast loading of large files, cheap undo history, many cursors, or frequent edits scattered across a document, a piece table — ideally with a balanced tree of pieces — scales better. The upfront complexity buys you an editor that never copies the user’s file and never loses the ability to revert.
The takeaway
Both structures avoid the O(n)-per-keystroke trap of a plain string. A gap buffer does it by keeping free space where the user is typing, which is simple and fast as long as edits stay local. A piece table does it by never touching existing text and describing the document as spans over two buffers, which makes large files, scattered edits, and undo cheap at the cost of extra indirection.
Keep reading
The Lycoris Team · · 6 min read Huffman Coding Explained: How Lossless Compression Works
Huffman coding gives frequent symbols short bit codes and rare symbols long ones, producing an optimal prefix code. How the tree is built and decoded.
The Lycoris Team · · 5 min read Kadane's Algorithm Explained: Maximum Subarray in O(n)
Kadane's algorithm finds the maximum-sum contiguous subarray in one O(n) pass. How it works, why it's correct, code, edge cases, and common variations.
The Lycoris Team · · 4 min read The Rope Data Structure: Editing Huge Strings Efficiently
A rope is a binary tree of string chunks that makes inserting, deleting, and slicing huge strings fast, which is why text editors use it over plain arrays.