Piece Table: The Text Editor's Secret Edit Buffer

Two buffers, never modified in place

The original buffer is loaded once when a file is opened and is treated as strictly read-only for the entire editing session; nothing is ever inserted into it or deleted from it. The add buffer starts empty and grows purely by appending, every character the user types anywhere in the document gets tacked onto the end of this buffer, regardless of where in the logical document it is meant to appear. This append-only discipline is what makes the piece table efficient: since neither buffer is ever mutated in the middle, there is no need for expensive memory shifting when handling an edit, and both buffers can be implemented as simple, contiguous, growable arrays that are extremely cache-friendly and fast to append to. The actual visual position of a character in the document is entirely determined by where its describing piece sits in the sequence of pieces, not by its physical offset in either buffer, which is the conceptual leap that decouples logical document order from physical storage order.

The piece sequence: an ordered list of small descriptors

The document itself is represented as an ordered sequence of piece descriptors, commonly implemented as a doubly linked list or occasionally a more advanced structure like a balanced tree for very large documents, where each piece is a small tuple recording which buffer it points into, the starting offset within that buffer, and the length of the run of text it covers. Reading the whole document in order simply means walking this sequence from start to end and concatenating each piece's referenced text; a freshly opened, unedited file starts as a single piece spanning the entire original buffer. Because pieces are small fixed-size records rather than copies of actual text, the piece sequence stays compact even for a heavily edited document, growing only in proportion to the number of edit operations performed, not the size of the document or the amount of text inserted, which is a crucial distinction from approaches that would need to duplicate text spans on every change.

Inserting text: split and splice

To insert new text at some position in the document, the editor first appends the newly typed characters to the end of the add buffer, then locates which existing piece in the sequence currently covers that insertion position. If the insertion point falls exactly at a piece boundary, a brand-new piece describing the freshly appended add-buffer text can simply be spliced into the linked list at that point with no further work. If the insertion point falls in the middle of an existing piece, that piece must be split into two pieces, one covering the text before the insertion point and one covering the text after it, both still pointing into whichever original buffer the split piece referenced, and the new piece for the typed text is inserted between them. Either way, this operation touches only a small constant number of piece descriptors, splitting at most one existing piece and inserting one new piece, regardless of how large the document is, which is why typing into a piece-table-backed editor stays fast even in documents with millions of characters.

Deleting text: split and trim, no data destroyed

Deletion works by the same split-and-splice logic in reverse. If the deleted range exactly covers one or more whole pieces, those pieces are simply removed from the sequence. If the deleted range starts or ends in the middle of a piece, that piece is split at the boundary of the deletion, and only the portion outside the deleted range is kept in the sequence; the portion falling inside the deleted range is simply excluded from the piece list going forward, even though its underlying bytes still physically exist untouched in the original or add buffer. This is one of the most elegant properties of the piece table: because the underlying buffers are never actually modified or shrunk, deleted text is never truly destroyed, it is merely no longer referenced by any piece in the current sequence, meaning the data structure is naturally forgiving of a design that wants to keep old text around for other purposes.

Fast, cheap undo and redo for free

Because every edit operation is expressed purely as a small, local change to the piece sequence, an editor can implement full undo and redo simply by recording, for every edit, which pieces were removed and which were added, essentially a tiny diff of the linked list rather than a diff or snapshot of the entire document text. Undoing an insertion means removing the piece or pieces that were added and restoring whichever piece or pieces were split, all without touching either buffer, and redoing simply replays the same small change again. This is dramatically cheaper than naive undo implementations that snapshot the whole document string on every keystroke, and it is a major reason piece tables remain popular in modern editor implementations: they give you not just fast typing but essentially free, memory-efficient undo history as a natural side effect of how edits are already represented internally, which is exactly the kind of design where getting the core data structure right pays dividends throughout the rest of the system.

Frequently asked questions

Try it live

Everything above runs in your browser — open Piece Table: The Text Editor's Secret Edit Buffer and change the parameters while it is running. Nothing is installed, nothing is uploaded, the whole model lives in one tab.