Piece Table — The Data Structure Behind VS Code

Structure

Piece = (buffer, offset, length). Text = concatenation of pieces in order. Insert splits pieces.

Insert

void insert(int pos, String s) {
  int addOffset = addBuffer.length();
  addBuffer.append(s);
  // Find piece containing pos, split it, insert new piece pointing to add buffer
}

Delete

Split pieces at endpoints of deletion, remove pieces in between. O(log N) with balanced BST of pieces.

Space

Original buffer never modified. Add buffer grows monotonically. Compact + fast.