The Rope

A string held in one contiguous buffer answers s[i] with a single indexed read, which is the reason the representation is nearly universal. Every operation that changes the length pays for that layout. Concatenating two strings of lengths a and b allocates a + b bytes and copies both, and inserting one character at position i shifts every byte after it.

The cost is invisible until the buffer is large. A 200 MB source file or log opened in an editor that stores the text flat pays a 200 MB copy per edit near the front, and a program that builds a document by repeated concatenation performs Θ(n²) total copying to produce n bytes. A rope replaces the single buffer with a tree whose leaves hold short strings, so that concatenation stops copying and the cost of an edit becomes proportional to the depth of the tree instead of the length of the text.

A rope is a binary tree. Each leaf holds a short immutable string, and the sequence represented by the rope is the concatenation of its leaves in left-to-right order. Each internal node holds two children and one number: the total length of everything in its left subtree. That number is the node's weight, and it is the whole index.

No node stores a position, and no node stores the text of its descendants. The tree is therefore a sequence built out of pieces that never move: an edit changes which nodes exist and how they are connected, never the contents of a leaf. Boehm, Atkinson, and Plass introduced the structure under this name in 1995, with leaves as immutable flat strings for exactly that reason.

Take the rope for "Hello_world!" built from four leaves — "Hel", "lo_", "wor", "ld!" — and ask for character 7. Nothing in the tree records where character 7 lives, so the descent works it out from the weights. Start at the root, whose weight is 6: the left subtree holds the first 6 characters, "Hello_". Since 7 is not below 6, the character cannot be on the left, so the search goes right and subtracts the left weight, rewriting the request as "character 1 of whatever hangs on the right".

That right-hand node has weight 3, because its own left subtree is the leaf "wor". Now 1 is below 3, so the character is on the left and the index stays as it is — no subtraction happens when the search goes left. The left child is the leaf "wor" itself, and the request is character 1 of it. Leaves hold plain contiguous text, so that last step is an ordinary indexed read: "wor"[1] is o.

The whole descent is one comparison and at most one subtraction per level, which is why random access costs O(d) rather than the single load a flat buffer offers. The index is never searched for; it is transformed on the way down until it becomes an offset inside one leaf.

To read character i, start at the root and compare i with the node's weight. If i is smaller, descend left with i unchanged. Otherwise subtract the weight from i and descend right. On reaching a leaf, i is the offset within that leaf's string. Each step is one comparison and one subtraction, so a random access costs O(d) for tree depth d rather than the O(1) of a flat buffer.

That is the trade the whole structure rests on. Random indexing gets slower by a logarithmic factor when the tree is balanced, and sequential scanning stays fast because iterating the leaves in order walks contiguous runs of bytes. Editors read text far more often in runs than at isolated random offsets, which is why the exchange is acceptable there and not in, say, a numeric array.

Now insert "XY" at position 8 of the same rope. The first half of the work is the descent just described: weights carry the position down to the leaf that contains it, which is "wor", at offset 2. What happens next is the part that separates a rope from a buffer — the leaf is not modified, because leaves are immutable. It is replaced. The text "wor" splits at offset 2 into "wo" and "r", and the inserted text becomes a leaf of its own, giving three new leaves where one stood.

Those new leaves need a parent, and that parent needs a parent, so the nodes along the path from the leaf back to the root are rebuilt with new children — here the right-hand internal node and then the root. Every node rebuilt this way also recomputes its weight, since the sequence below it just grew by two characters. Nothing else is created: the subtrees hanging off the rebuilt path, holding "Hel", "lo_", and "ld!", are reattached to the new nodes by pointer.

The result is a new root describing "Hello_woXYrld!", built from a handful of fresh nodes, while the old root still describes the original text and remains perfectly valid. The cost is proportional to the depth of the tree, not to the length of the document, and no character outside the edited leaf was read, moved, or copied.

Concatenating two ropes allocates one internal node, points it at both roots, and sets its weight to the length of the left rope. No character is copied and no existing node is modified, so the operation is O(1) in the length of the text. This is the operation flat strings cannot do cheaply, and it is the one ropes were introduced for.

Splitting at position i descends to that offset and returns two ropes. The descent path is rebuilt — every node on it is replaced by a node with one side truncated — and the subtrees hanging off the path are reattached without being touched. One leaf is divided if the split lands mid-leaf. Both the work and the newly allocated nodes are proportional to the depth, giving O(d), and every other node is shared with the original rope rather than copied.

Every edit reduces to split and concatenate. Inserting a string at position i splits the rope at i into L and R, then concatenates L + new + R. Deleting the range [i, j) splits twice and concatenates the outer two pieces, discarding the middle. The bytes in the untouched parts of the document are never read, let alone moved.

Each edit therefore costs O(d) plus the length of the inserted text, against O(n) for the flat buffer. On a balanced rope over a 200 MB file that is a walk of roughly thirty nodes instead of a copy of two hundred million bytes. The cost that replaces it is allocation: an edit produces O(d) fresh internal nodes, so an editor doing this per keystroke needs allocation and reclamation to be cheap.

Concatenation is O(1) precisely because it does not look at the shape of the tree, and a program that appends repeatedly builds a right-leaning chain whose depth equals the number of appends. Depth is the cost of every other operation, so a rope that is never rebalanced degrades until indexing is linear.

The original paper defines balance against the Fibonacci numbers: a rope of depth d is balanced when its length is at least F(d + 2). Rebalancing collects the leaves in order into a sequence of slots, slot k accepting a rope whose length falls in [F(k), F(k + 1)), concatenating into a slot that is already occupied and carrying the result upward. The result has depth O(log n), and the bound is checked after concatenation rather than maintained continuously, so the work is amortized across many edits — the same accounting the scapegoat tree uses for subtree rebuilds. Implementations that maintain a stricter invariant on every operation, as an AVL tree does, pay per edit and never need a repair pass.

Nothing in the definition fixes how much text a leaf holds, and the choice sets the constants. Single-character leaves make the tree n leaves deep and spend tens of bytes of node overhead per character. Very large leaves push the structure back toward a flat buffer: an insertion inside a leaf copies that leaf, so a one-megabyte leaf reintroduces a one-megabyte copy.

Production ropes take leaves of a few hundred bytes to a few kilobytes, sized so that a leaf spans one or two cache lines' worth of useful work and a leaf-local edit is a short memcpy. Implementations also raise the branching factor above two, storing several children and their cumulative lengths per node, which shortens the tree and lets one node fill a cache line. Zed's rope is built on such a B-tree-shaped structure rather than a binary one.

Because leaves are immutable and an edit rebuilds only the path from the root to the edit point, the old root remains a valid rope describing the document before the edit. The two versions share every subtree that the edit did not touch, so retaining a snapshot costs O(d) nodes rather than a copy of the text.

That property is what editors use for undo history, for handing a consistent view of the buffer to a background thread while the user keeps typing, and for computing a diff against a previous state. Helix keeps document snapshots this way, describing its ropes as cheap to clone. The same mechanism underlies the zipper, which navigates an immutable tree by rebuilding one root-to-focus path, and a rope walked with a cursor is a zipper over a sequence.

The weight field generalises. Any quantity that is associative over concatenation can be stored per node as the aggregate for its subtree: byte count, character count, newline count, maximum line width, or the state of an incremental parser. The descent that finds a character offset then also answers "which line is offset 4,271 on" by comparing against newline counts instead of lengths, in the same O(d) walk.

Editors need this constantly, because a buffer is addressed by byte offset for I/O, by character index for cursor movement, and by line and column for display and diagnostics. Zed's rope stores chunks in a copy-on-write B-tree it calls a SumTree, where every node carries a summary of its subtree, and uses those summaries to convert between offsets and line-column points without scanning. Maintaining the aggregates costs one recomputation per node on the rebuilt path, which the edit was already paying for.

Two other representations solve the same problem differently. A gap buffer keeps the text flat but leaves an unused gap at the cursor, so insertion at the cursor is O(1) and moving the cursor by k characters costs O(k) to shift the gap. It is fast for the common case of typing in one place and slow for scattered edits; Emacs uses it. A piece table keeps the original buffer read-only, appends new text to a second buffer, and stores the document as a list of pieces referencing spans of the two, making edits cheap and indexing linear in the number of pieces until the list is itself indexed by a tree.

The three differ in what they make cheap. A gap buffer optimises locality of edits, a piece table optimises never rewriting original text and gives a compact undo log, and a rope optimises concatenation, split, and snapshotting at the cost of an indirection per access. Visual Studio Code moved its buffer from an array of lines to a piece table with a balanced-tree index, reporting large reductions in memory use and load time for big files; ropes and indexed piece tables converge on similar shapes.

A rope gives O(1) concatenation, O(log n) split, insert, and delete on a balanced tree, snapshots that share storage with the live document, and per-node summaries that answer line and column queries during the same descent. Nothing is copied at scale, so worst-case latency stops tracking document size — the property an interactive editor actually needs.

The costs are a logarithmic factor and a constant factor on every read, node overhead of tens of bytes per few hundred bytes of text, allocation traffic proportional to depth on every edit, and rebalancing logic that a flat buffer does not have. For strings that are built once and read many times, or that fit comfortably in cache, a flat buffer is faster on every operation and the rope is the wrong structure.

V8 does not represent the result of a + b as a new flat string. It allocates a ConsString holding pointers to the two operands, giving constant-time concatenation, and flattens the tree into a sequential string only when an operation needs contiguous bytes; a related SlicedString represents a substring as a parent pointer plus offset and length so that slicing copies nothing. The rope is the concatenation strategy of a production JavaScript engine, and flattening is where the deferred copy is finally paid.

Text editors are the other concentration. Zed stores every buffer as an immutable rope of fixed-size chunks over a copy-on-write B-tree whose nodes carry subtree summaries, which is what lets it convert offsets to line-column coordinates and hand snapshots to background threads. Helix represents all documents with the ropey rope and runs regular-expression search directly over the rope's chunks through regex-cursor, avoiding a copy of the buffer into a contiguous string for every search. The xi editor was built around the same choice, and the SGI C++ standard library shipped a rope container implementing the original paper.

A rope stores a sequence as a tree of immutable string leaves, with each internal node recording the length of its left subtree. Indexing descends on that number, concatenation allocates one node without copying, and split rebuilds one root-to-leaf path while sharing everything else. Insert and delete are a split followed by a concatenation, so an edit costs O(log n) on a balanced tree instead of O(n).

Random access loses its constant-time bound, each edit allocates nodes proportional to depth, and balance has to be restored explicitly because concatenation ignores shape. In return the structure gives cheap snapshots through shared subtrees and a place to hang associative summaries — newline counts, character counts — that turn coordinate conversion into the same descent as the lookup.