Research / 2025 –

Trees as columns

Draft · the definitions and theorems on this page are machine-checked in Lean; independent review is in progress.

A JSON tree written as two pre-order pointer arrays plus typed value columns, packed at the bit level, and an update scheme in which each edit is a small payload addressed against the previous materialized state.

Tree encodingColumnar layoutDelta codingIncremental update
100 bits
for the object a:1, b:2, c:[3,4] (13 bytes with padding)
3 B
a counter update, against an 8 B full encoding
4.9×
smaller than storing all seven versions of a record in full

A row-oriented serializer writes a tree the way a printer would: open, key, value, close. A columnar encoder writes it as parallel homogeneous sequences that compress independently. This article works through one such encoding at the bit level: how the shape is represented, why that is cheap in pre-order, what grouping values by kind costs, and how edits become small payloads against a materialized table. Twelve columns and Delta packing cover parts of it.

Slots and two pointer arrays

Slots. Walk the document in pre-order. Every container (object or array) and every object key gets a slot. Slots are numbered 0,1,…,n−10, 1, \dots, n-1 in visiting order, and slot 0 is the root. Primitive values are leaves. They are not slots.

Key link. For each slot i≥1i \ge 1 with parent π(i)\pi(i), store ki=π(i)+1k_i = \pi(i) + 1. A key’s parent is its object. A container’s parent is the key that holds it, or the array it sits in.

Value link. For each leaf jj in pre-order, store vj=ω(j)+1v_j = \omega(j) + 1, where the owner ω(j)\omega(j) is the key slot (for an object member) or the array slot (for an array element).

The +1+1 keeps 0 free as an escape value. Array indices are never stored, because element order is the order of the value links. An empty container inside a structure gets a slot and one marker leaf, so every slot without child slots still owns at least one leaf.

Input
{ "a": 1, "b": 2,
  "c": [3, 4] }

One depth-first scan:
{} → a → 1 → b → 2 → c → [] → 3 → 4

Slots klink = parent + 1
slotnodeklinkktype
0{}—object · 01
1"a"1b64 key · 10
2"b"1b64 key · 10
3"c"1b64 key · 10
4[]4array · 00
Leaves vlink = owner + 1
valuevlinkΔ code
122
231
352
450

Links [2,3,5,5] become delta codes [2,1,2,0], 3 bits each.

Emitted bitstream: 12 columns in fixed order, then zero padding
  1. 1dc · mode + count
  2. 2vflags
  3. 3vlinks
  4. 4kflags
  5. 5klinks
  6. 6keys
  7. 7kvals
  8. 8types
  9. 9bools
  10. 10nums
  11. 11vals
  12. 12strdiffs
  13. ·pad
Fig. 1Slots and links for the object a:1, b:2, c:[3,4]. The key links are 1,1,1,4 and the value links 2,3,5,5. Both sequences change slowly, which is what the delta code exploits.

Both columns come out of one pre-order walk. A container takes a slot (with key link parent +1+1), an object member takes a slot for its key, and a primitive pushes a value link to its owner.

inductive Json where
  | null | bool (b : Bool) | num (n : Int) | str (s : String)
  | arr (xs : List Json) | obj (kvs : List (String × Json))

-- state: next free slot, key links, value links
abbrev Walk := StateM (Nat × Array Nat × Array Nat)

def alloc (parent : Option Nat) : Walk Nat :=
  modifyGet fun (n, ks, vs) => (n, (n + 1, parent.elim ks (ks.push <| · + 1), vs))
def leaf (owner : Nat) : Walk Unit :=
  modify fun (n, ks, vs) => (n, ks, vs.push (owner + 1))

mutual
  def visit (parent : Option Nat) : Json → Walk Unit   -- pre-order
    | .arr xs => do let s ← alloc parent; if xs.isEmpty then leaf s else elems s xs
    | .obj kvs => do let s ← alloc parent; if kvs.isEmpty then leaf s else members s kvs
    | _ => leaf (parent.getD 0)
  def elems (s : Nat) : List Json → Walk Unit
    | [] => pure ()
    | x :: xs => do visit (some s) x; elems s xs
  def members (s : Nat) : List (String × Json) → Walk Unit
    | [] => pure ()
    | (_, v) :: kvs => do let k ← alloc s; visit (some k) v; members s kvs
end

/-- (slot count n, key links k₁…, value links v₀…) -/
def links (j : Json) : Nat × List Nat × List Nat :=
  let (n, ks, vs) := ((visit none j).run (0, #[], #[])).2
  (n, ks.toList, vs.toList)

The encoder also keeps a 2-bit kind per slot, the key characters, a 3-bit type per leaf (seven value types, with 000 reserved as the run escape), and columns for booleans, numbers and strings: twelve columns, emitted in an order fixed by the format, so no directory or offsets are written.

Implicit counts. Only the number of leaves rr is written. Everything else follows from it.

Claim. If the root is a container, the number of slots is n=max⁡jvjn = \max_j v_j.

Proof. The root is slot 0, so n≥1n \ge 1. The last slot in pre-order has no child slot. So it is a key with a primitive value, an empty container with its marker leaf, or an array whose elements are all primitive. In each case some leaf has it as owner, so max⁡jω(j)=n−1\max_j \omega(j) = n-1. No owner exceeds n−1n-1, so max⁡jvj=n\max_j v_j = n. □\square

On the example both the links and the claim are checked:

-- continues the definitions above
def ex : Json := .obj [("a", .num 1), ("b", .num 2), ("c", .arr [.num 3, .num 4])]

#eval links ex   -- (5, [1, 1, 1, 4], [2, 3, 5, 5])
example : links ex = (5, [1, 1, 1, 4], [2, 3, 5, 5]) := by native_decide
-- the claim n = max vⱼ, on this example and on an empty container root
example : (links ex).2.2.foldl max 0 = (links ex).1 := by native_decide
example : links (.arr []) = (1, [], [1]) := by native_decide
-- a primitive root has no slot, so the claim needs a container root
example : links (.num 5) = (0, [], [1]) := by native_decide

Then there are n−1n-1 key links and nn slot kinds, and the type column gives the number of booleans, numbers and strings. Each column tells the decoder how much of the next ones to read.

Why pre-order parent pointers are cheap

Written naively, a parent array costs ⌈log⁡2n⌉\lceil \log_2 n \rceil bits per entry. In pre-order it is far more regular.

Stack property. For 1≤i≤n−21 \le i \le n-2, π(i+1)\pi(i+1) is an ancestor-or-self of ii. Hence π(i+1)≤i\pi(i+1) \le i. Let mm be the number of slots that have at least one child slot. Then π(i+1)≠π(i)\pi(i+1) \ne \pi(i) for at most 2m2m values of ii.

Proof. If ii has a child slot, i+1i+1 is its first child, so π(i+1)=i\pi(i+1) = i (a descent). Otherwise i+1i+1 is the next sibling of the nearest ancestor-or-self of ii that has one. If that node is ii, then π(i+1)=π(i)\pi(i+1) = \pi(i). If not, π(i+1)\pi(i+1) is a proper ancestor of π(i)\pi(i), and the subtree of π(i)\pi(i) has just been closed (an ascent). Each slot with children causes exactly one descent. Each ascent closes the subtree of a slot with children, and pre-order closes each subtree once. □\square

So the key-link sequence is constant except at O(m)O(m) positions. Value links are similar: owners strictly increase within an object, repeat along an array of primitives, and decrease only when an array resumes after a nested container. Both columns therefore use one delta code. With d=x−xprevd = x - x_{\text{prev}} and xprev=0x_{\text{prev}} = 0 before the first link of a column:

c(d)={d0≤d≤3∣d∣+3−3≤d≤−1literalotherwisec(d) = \begin{cases} d & 0 \le d \le 3 \\ |d| + 3 & -3 \le d \le -1 \\ \text{literal} & \text{otherwise} \end{cases}
/-- The 3-bit delta code `c(d)`; `none` means "write a literal". -/
def code (d : Int) : Option Nat :=
  if 0 ≤ d ∧ d ≤ 3 then some d.toNat
  else if -3 ≤ d ∧ d ≤ -1 then some (d.natAbs + 3)
  else none

/-- Its inverse: apply code `c` to the previous link `p`. -/
def step (p c : Nat) : Nat := if c ≤ 3 then p + c else p - (c - 3)

/-- Codes for a column of links, starting from `prev = 0`. -/
def codes (xs : List Nat) : List (Option Nat) :=
  (List.zip (0 :: xs) xs).map fun (p, x) => code (x - p : Int)

#eval codes [1, 1, 1, 4]   -- [some 1, some 0, some 0, some 3]
#eval codes [2, 3, 5, 5]   -- [some 2, some 1, some 2, some 0]

-- step undoes code for every delta in the window
example : ∀ p : Fin 8, ∀ d : Fin 7,
    let d' : Int := d.val - 3
    0 ≤ p.val + d' → (code d').map (step p) = some (p.val + d').toNat := by decide

A delta is written as c+1c+1 in 3 bits, so 0 never occurs as a delta. A flag column (with a 2-bit prefix for all-zero, all-one or mixed) records delta or literal per link. The free 3-bit zero is the run escape: four or more consecutive links with the same 3-bit value become 000, a count in the short code (2-bit selector, then 2, 3 or 4 bits, or LEB128 from 16 up), and the code once. For [1..9] the value links are code 1 then eight zero deltas: 3+(3+6+3)=153 + (3 + 6 + 3) = 15 bits instead of 27.

Literals use a running width WW that is never transmitted. Because a literal is also stored as value +1+1, a zero at the current width can only mean “widen”.

-- the bitstream: read `w` bits MSB-first; past the end it reads as zeros
abbrev Dec := StateM (List Bool)

def read (w : Nat) : Dec Nat := modifyGet fun bs =>
  let v := (List.range w).foldl (fun a i => 2 * a + if bs.getD i false then 1 else 0) 0
  (v, bs.drop w)

def readLEB : Nat → Dec Nat            -- fuel = max bytes
  | 0 => pure 0
  | k + 1 => do
    let b ← read 8
    if b < 128 then pure b else return b - 128 + 128 * (← readLEB k)

/-- Short code: 2-bit selector, then 2, 3 or 4 bits, or LEB128 from 16 up. -/
def readShort : Dec Nat := do
  match ← read 2 with
  | 0 => read 2 | 1 => read 3 | 2 => read 4 | _ => readLEB 10

/-- A literal at running width `W`: a zero means "widen by one". -/
def readLiteral : Nat → Nat → Dec (Nat × Nat)   -- fuel, W ↦ (value, new W)
  | 0, w => pure (0, w)
  | k + 1, w => do
    let x ← read w
    if x = 0 then readLiteral k (w + 1) else pure (x - 1, w)
-- continues the definitions above
/-- Decode one link column, given its flags (true = delta, false = literal). -/
def decodeLinks (flags : List Bool) (prev W : Nat) : Dec (List Nat) :=
  match flags with
  | [] => pure []
  | false :: fs => do
    let (x, W) ← readLiteral 64 W
    return x :: (← decodeLinks fs x W)
  | true :: fs => do
    let x ← read 3
    if x ≠ 0 then
      let p := step prev (x - 1)
      return p :: (← decodeLinks fs p W)
    else                                    -- run escape
      let n ← readShort
      let c := (← read 3) - 1
      let run := true :: fs.take (n - 1)    -- each entry keeps its own flag
      let (last, out) := run.foldl (init := (prev, []))
        fun (p, out) f => let q := if f then step p c else c; (q, q :: out)
      return out.reverse ++ (← decodeLinks (fs.drop (n - 1)) last W)
termination_by flags.length
decreasing_by all_goals simp_wf; all_goals (try simp [List.length_drop]); omega

def bits (s : String) : List Bool := s.toList.filterMap fun
  | '0' => some false | '1' => some true | _ => none

def links? (flags : List Bool) (s : String) : List Nat :=
  ((decodeLinks flags 0 1).run (bits s)).1

The encoder mirrors this. Before a literal it computes the width the current slot count needs and writes one zero at the old width for every step up. WW never shrinks, so the escapes cost 1+2+⋯+(Wmax⁡−1)=Wmax⁡(Wmax⁡−1)/21 + 2 + \dots + (W_{\max} - 1) = W_{\max}(W_{\max}-1)/2 bits per column in total, or O(log⁡2n)O(\log^2 n), however many literals there are. In {x:{y:{z:1}},w:2} the value link 6 is written as 0 00 111: two widen steps, then 7 in 3 bits.

decodeLinks flags 0 1 starts a fresh document at W0=1W_0 = 1. Run on the bits of Figure 2 below, on the [1..9] run and on the widening example, it gives back the links:

-- continues the definitions above
def ones (k : Nat) := List.replicate k true

#eval links? (ones 4) "011 010 011 001"           -- [2, 3, 5, 5]
#eval links? (ones 4) "010 001 001 100"           -- [1, 1, 1, 4]
#eval links? (ones 9) "010 000 10 1000 001"       -- [1, 1, 1, 1, 1, 1, 1, 1, 1]
#eval links? [false, true] "0 00 111 010"         -- [6, 7]

example : links? (ones 4) "011010011001" = [2, 3, 5, 5] := by native_decide
example : links? (ones 9) "010000101000001" = List.replicate 9 1 := by native_decide
example : links (.obj [("x", .obj [("y", .obj [("z", .num 1)])]), ("w", .num 2)])
    = (7, [1, 2, 3, 4, 5, 1], [6, 7]) := by native_decide

The worked example, bit by bit

For {a:1,b:2,c:[3,4]} there are 5 slots and r=4r = 4 leaves. The key links 1,1,1,41,1,1,4 give deltas 1,0,0,31, 0, 0, 3. The value links 2,3,5,52,3,5,5 give deltas 2,1,2,02, 1, 2, 0. All four numbers are positive integers, so the type column is a single run of type 4. The number column is a run of four “delta +1+1” codes against a starting value of 0.

  • header and flag prefixes
  • shape
  • values
  • padding
Fig. 2The whole encoding of the example object: 100 data bits in twelve columns (empty columns emit nothing), plus 4 bits of zero padding, so 13 bytes.

The bits break down as 6+2+12+2+12+22+18+11+15=1006 + 2 + 12 + 2 + 12 + 22 + 18 + 11 + 15 = 100. Key characters take 6 bits each because they are in the URL-safe 64-symbol alphabet. Keys and string values share one dictionary in first-seen pre-order, and a repeat of either is written as length 0 plus a short index. A minimal byte-oriented tag-per-value encoding of this object takes 12 bytes (one map header, three 1-byte key headers with one character each, two 1-byte integers, one array header and two 1-byte integers), so on tiny inputs the per-column overhead roughly matches a tag-per-value format.

Grouping by kind, and what it costs

The columns group values by kind: every number goes into one number column in pre-order, whatever its path. Record shredding groups by path: each schema field has its own column, and each value carries a repetition level (at which repeated ancestor a new element starts) and a definition level (how many optional or repeated ancestors are present), from which a per-schema state machine rebuilds records. Path grouping needs a schema. Kind grouping does not, since the shape travels in the link columns, but adjacent entries in a column may come from unrelated fields.

Sizes computed from the specification on data from a fixed-seed pseudorandom generator, compared with the shortest MessagePack encoding of the same value, show both sides:

  • Record arrays (id, short name, age, boolean, two-decimal score, small tag array): 52–55% of MessagePack’s size at 10, 100 and 1,000 records (54.8%, 52.4% and 53.8%). Repeated keys become dictionary references, booleans cost at most a bit, and a two-decimal float is a scaled integer, where MessagePack repeats every key and spends 9 bytes per float64.
  • Time series (1,000 rows of {t, v}, where t advances by 60 from about 1.7×1091.7 \times 10^9 and v takes random-walk steps in [−5,5][-5, 5]): 14,040 bytes against 11,617, which is 21% larger. The number column alternates between t and v, so consecutive differences are never within ±3\pm 3 and every number becomes a full literal. Path grouping would put the v values next to each other, where 7 of the 11 possible steps fall inside the delta window. Neither layout uses the constant stride of t, because the delta code has no second-order term.

Succinct trees answer a different question. LOUDS writes node degrees in unary in level order (2n+12n+1 bits). Balanced parentheses write the pre-order traversal (2n2n bits). Both approach the log⁡2Cn−1≈2n\log_2 C_{n-1} \approx 2n lower bound for ordinal trees and, with o(n)o(n) extra bits for rank and select, navigate in constant time. The encoding here is not succinct: a literal link costs about log⁡2n\log_2 n bits, every slot pays a 2-bit kind, and nodes are reachable only by sequential decoding. In exchange, by the stack property the key-link column has O(m)O(m) change points however many siblings each container has.

Edits as payloads against a materialized table

A history is a chain of payloads: payload 0 is a full encoding, the anchor, and each later payload is an ordinary bitstream whose links address the current state.

State. S=(slots,leaves,dictionary)S = (\text{slots}, \text{leaves}, \text{dictionary}), the decoded tables before the tree is rebuilt.

Delta. A bitstream decoded with slot numbering, and the starting literal width, initialised from the slot count nSn_S of SS. Existing slots are addressed directly, and new keys get slots nS,nS+1,…n_S, n_S+1, \dots (links nS+1,nS+2,…n_S+1, n_S+2, \dots). Besides ordinary leaves, a delta can carry a removal marker addressed to an existing slot, and a long string can carry a character-level diff. The bit layout of these markers belongs to the escape grammar discussed under the open questions below.

Apply. apply(S,δ)=compact(merge(S,decode(δ;nS)))\mathrm{apply}(S, \delta) = \mathrm{compact}(\mathrm{merge}(S, \mathrm{decode}(\delta; n_S))). Merge appends δ’s leaves after those of SS. A removal marker removes every leaf with the same owner and cascades to the slot’s descendants. For an object key the later value wins, and array elements are concatenated. Compact drops slots that no leaf can reach, renumbers the remaining slots densely in order, and renumbers the dictionary densely, keeping only strings that occur at least twice.

Incrementing {count:0} to {count:1} gives an 18-bit payload: mode 0, leaf count 00 01, flag prefix 01, value link 011 (owner slot 1), type 100, number 00 001 (delta +1+1 from 0). Padded, that is 3 bytes.

Prefix replay. Let S0=decode(p0)S_0 = \mathrm{decode}(p_0) and Sk=apply(Sk−1,pk)S_k = \mathrm{apply}(S_{k-1}, p_k). For a chain p0…pKp_0 \dots p_K, every prefix p0…pkp_0 \dots p_k is itself a valid chain, and it decodes to SkS_k.

Proof. Replay is a left fold of apply over the payloads. Truncating the input of a fold gives the fold’s intermediate value. □\square

A payload is not meaningful on its own. Compaction renumbers slots, so an address in pkp_k means a position in Sk−1S_{k-1} and nothing else. Take {a:1,b:2,c:3} with slots object 0, a 1, b 2, c 3. If p1p_1 removes b, c becomes slot 2, and a p2p_2 writing slot 2 means c; applied to S0S_0 the same bits would overwrite b. The dictionary behaves the same way: compaction keeps only strings that occur at least twice, so whether a payload can name a string by a short index or must spell it out depends on the state it is applied to. Payloads are strictly sequential, and reading version kk costs kk applications.

Framing. Each payload is byte-aligned and stored as LEB128(length) ‖ payload. The length is necessary: the decoder reads bits past the end of a buffer as zeros (as read does above), so the bitstream does not mark its own end, and a payload’s grammar may extend past its last stored byte into implicit zeros. Concatenated without lengths, such a payload would take the first bits of the next payload in place of those zeros.

Re-anchoring. An edit that the delta grammar cannot express against the current table, such as replacing the root with a value of another type, is stored as a new anchor that starts a new chain.

ScenarioAnchorUpdate payloadsChainAll versions in full
Counter: 0 → 1, 2, 100, 1000008 B3, 3, 3, 5 B27 B44 B (1.6×)
User record, 6 edits (bool flip, nested int, nested string, add key, array append, remove key)86 B2, 3, 7, 10, 7, 2 B124 B610 B (4.9×)
450-character string: one word changed, then 3 characters appended459 B18, 12 B493 B1,384 B (2.8×)

“Chain” includes the length prefixes. “All versions in full” is the sum of a full encoding of every version, anchor included.

counter, chain
27 B
counter, full
44 B
record, chain
124 B
record, full
610 B
Fig. 3Storing a history as one anchor plus deltas, compared with storing every version in full. Byte sizes from the table above.

Limitations and open questions

  • Locality across fields. Kind grouping loses when numeric fields alternate. Splitting the number column by owning key, only for keys repeated across sibling records, would stay schema-free; a stride code would handle timestamps. How much of the loss either recovers is open.
  • Sequential access. Decoding a document and reaching version kk are both linear scans. Can rank and select structures sit beside the pre-order link columns without losing the run-length gains? Can a chain carry checkpoints instead of discarding history at a re-anchor?
  • Address stability. Dense renumbering keeps addresses short but ties each delta to its predecessor. Stable identifiers would permit reordering and merging concurrent edits at the cost of wider links.
  • Path grammar. Deltas are produced from textual paths, so key escaping must be injective; otherwise a key containing . collides with a nested path.
  • Escape grammar. The escapes inside variable-width fields (run escapes, widen markers, alphabet escapes in keys, removal markers) should be specified as a formal grammar, so that decode ∘ encode = id can be proved for every input rather than argued case by case.