Piece Table

Used by VS Code, Notepad++, Word.

Idea:

• Two append-only buffers: original (immutable, the file content) and add (everything typed).
• A list of pieces: (which buffer, start, length).
• Edits update the piece list, never modify the buffers.

original = "The quick brown fox"
add      = ""
pieces   = [(original, 0, 19)]

Insert "lazy " at position 16:

original = "The quick brown fox"
add      = "lazy "
pieces   = [
    (original, 0, 16),    # "The quick brown "
    (add, 0, 5),          # "lazy "
    (original, 16, 3),    # "fox"
]

Logical text: "The quick brown lazy fox". Buffers UNCHANGED.

Delete:

• Find pieces overlapping the range.
• Split pieces at boundaries.
• Remove deleted pieces.

Pros:

• Original buffer never modified (memory mappable, can swap).
• Undo: just remove pieces from list (stack of operations).
• Multiple cursors: each cursor independent; no buffer conflicts.

Cons:

• Many edits → many pieces → slow walk for large position lookups.
• Memory: each piece has overhead.
• Need periodic compaction.

Optimization: balanced tree of pieces (red-black, B-tree) for O(log N) operations on huge files.

VS Code uses piece tables internally; performance is excellent for files up to ~hundreds of MB.