Type a character in the middle of a huge document and a naive editor would shift and re-copy everything after it — O(n) per keystroke. Real editors use smarter structures. A piece table keeps the loaded file as a read-only original buffer, appends every newly typed character to a separate append-only add buffer, and represents the current document as an ordered list of pieces, each just (which buffer, start, length). An insert never copies text — it appends to the add buffer and splits one piece into up to three. The document is whatever you get by reading the pieces in order. (Its cousin the rope stores text as a balanced tree of chunks for the same goal.) Insert some text and watch a piece split.
edits without copying the document · original + add buffers · pieces = (buffer, start, len)
original buffer
The loaded file, read-only and never modified.
add buffer
Append-only storage for everything newly typed.
piece
A span (buffer, start, length) into one of the two buffers.
document
The concatenation of the pieces, read in order — computed, not stored.
piecetable.js — split a piece, append the text
Ready
The document starts as one piece spanning the read-only original buffer. Each insert appends the new text to the add buffer and splits a piece — the original text is never touched or copied. Insert to edit.
1
pieces
0
add buffer chars
0
chars copied
How it works
The elegance is that the two buffers only ever grow at the end and are never rewritten. The original buffer is the file as loaded, fixed forever. The add buffer is append-only: new text goes on the end and stays put. All the editing lives in the cheap piece list. Inserting text at a position finds the piece covering that position and splits it: the part before the insertion stays a piece pointing into its original buffer, a new piece points at the just-appended text in the add buffer, and the part after becomes a third piece — again pointing into the original buffer, no bytes moved. Because nothing is copied, an insert is O(1) plus the small cost of splitting the piece list, and undo is trivial: just remember the previous piece list (the buffers already hold everything). The rope achieves the same goals with a balanced tree of text chunks, giving O(log n) split and concatenate.
1
Load into a read-only original buffer
The document text as loaded lives in an immutable original buffer. Start with one piece spanning all of it.
2
Append new text to the add buffer
When the user types, append those characters to the end of a separate, append-only add buffer. Nothing existing is moved.
3
Split a piece to insert
To insert at a position, split the piece there into a "before" part, a new piece pointing at the just-added text, and an "after" part. Only the small piece list changes.
✓
Read pieces in order; undo is free
The current document is the concatenation of the pieces in order — computed on demand. Undo/redo just swap piece-list versions, since both buffers already contain every character ever typed.
Insert
no doc copy
Buffers
append-only
Undo
trivial
Rope split/concat
O(log n)
The code
# piece table insert: append to add buffer, split a piecedef insert(self, pos, text):
start = len(self.add)
self.add += text # append-only, no copy
new_piece = Piece('add', start, len(text))
offset = 0; result = []
for p in self.pieces:
if offset <= pos <= offset + p.length:
left = pos - offset
if left: result.append(Piece(p.buf, p.start, left))
result.append(new_piece) # the inserted textif left < p.length: result.append(Piece(p.buf, p.start+left, p.length-left))
else: result.append(p)
offset += p.length
self.pieces = result # document = pieces in order
Quick check
1. Where does newly typed text go in a piece table?
All new text is appended to the add buffer, which only ever grows at the end. The original buffer is read-only. This is why editing never has to shift or re-copy existing text.
2. What happens to the piece list when you insert text in the middle of a piece?
Inserting inside a piece splits it: the part before the cursor, a new piece pointing at the just-appended text in the add buffer, and the part after. Only the small piece list changes — no character data is copied.
3. Why is undo trivial in a piece table?
Since the original and add buffers are append-only and never deleted from, every character ever typed still exists. Undo/redo just swaps to a previous version of the piece list — no text needs to be recovered.
FAQ
What is a piece table?
A text-editor data structure: the loaded file sits in a read-only original buffer, new text is appended to an append-only add buffer, and the document is an ordered list of pieces (buffer, start, length) into the two buffers. Edits split/rearrange pieces without copying text, making inserts, deletes, and undo cheap.
What is a rope, and how does it compare?
A rope stores a big string as a balanced tree of small text chunks with cached subtree lengths, giving O(log n) split/concatenate and efficient edits without copying the whole string. Piece tables are simpler and pair well with append-only buffers and undo; ropes give better asymptotics for very large strings and heavy structural edits.
Why not just use a plain string or array for a document?
A contiguous string/array makes a middle insert or delete O(n) because everything after shifts — too slow for large documents and frequent edits. Piece tables and ropes never store the document contiguously; they rearrange spans or chunks, so an edit touches only a little structure.
Which editors use these structures?
Piece tables have a long editor history (the Bravo editor, Microsoft Word, and VS Code’s piece-tree — a piece table backed by a balanced tree). Ropes and gap buffers appear elsewhere (Emacs classically uses a gap buffer). All aim to edit text without copying the whole document.