Search tools and guides ⌘K
V · Strings & sequences

Piece table

Edit a file without copying it.

1971 · Implicit; popularised by Microsoft Word
The story

A 1971 paper by Charles Crowley described representing a document as a sequence of references into immutable buffers — the original file, plus an "add" buffer of new edits. Microsoft Word built its document model on this; Visual Studio Code's editor still uses it (with some clever buffer-list compression).

How it works

Two buffers: the original file (read-only) and an append-only edit buffer. The document is a linked list (or tree) of pieces (start, length, which-buffer). Insert: append to edit buffer, splice a new piece into the list. Delete: split or trim pieces. Undo: pop from a stack of operations.

Where it lives

Microsoft Word. AbiWord. The text buffer in Visual Studio Code (since 2018, after a famous performance overhaul).

The key insight

Piece tables make undo nearly free — the original is never modified, so undoing is just reverting the piece list. Other text buffers must replay forward to reconstruct old states.

More in Strings & sequences
Suffix array All suffixes, sorted. Suffix tree Every substring, in linear space. Rope A tree of small strings. Gap buffer A buffer with a hole at the cursor.
Across the cabinet
VI LSM-tree Append-only, merged in the background. VI DAG · directed acyclic graph Order without cycles. VII KD-tree Binary search, in higher dimensions. VII R-tree A tree of bounding boxes. VII Quad-tree / Octree Recursive 4-way / 8-way subdivision. VII BVH · bounding volume hierarchy A tree of boxes for ray tracing. VII Z-order / Hilbert curve Linearise space, preserve locality. I Array A row of equal-sized boxes.
← All data structures