Squeezing sorted keys that share prefixes

The idea

Inside a storage block, keys are kept sorted, and sorted neighbours tend to begin with the same bytes — think user:1001 right after user:1000. Rather than write every key out in full, store the length of the prefix a key shares with the one before it, plus only the suffix bytes that differ.

The first key in the block is kept whole as an anchor. To rebuild any later key you inherit the previous key's first shared bytes and append its stored suffix. Long, similar keys collapse to a couple of bytes apiece.

See it work

How it works

Encoding walks the sorted keys once. For each key it counts how many leading bytes match the previous key, then writes that count plus the leftover suffix. Decoding reverses it: take the previous key's first shared bytes and glue the suffix on.

# --- encode one block of SORTED keys ---
def encode(keys, restart_every=16):
    out = []
    prev = ""
    for i, key in enumerate(keys):
        # A restart point stores a full key (shared = 0) so a
        # lookup can begin decoding here without walking from row 0.
        if i % restart_every == 0:
            shared = 0
        else:
            shared = common_prefix_len(prev, key)
        out.append((shared, key[shared:]))   # (count, suffix bytes)
        prev = key
    return out

def common_prefix_len(a, b):
    n = 0
    while n < len(a) and n < len(b) and a[n] == b[n]:
        n += 1
    return n

# --- decode: rebuild key i by walking from the nearest restart ---
def decode(entries, i, restart_every=16):
    start = (i // restart_every) * restart_every   # nearest restart point
    key = ""
    for j in range(start, i + 1):
        shared, suffix = entries[j]
        key = key[:shared] + suffix                # inherit prefix, add suffix
    return key

Cost

Watch out for

• Keys must be sorted for prefixes to line up — on unsorted data it saves nothing and just adds overhead.
• No random access inside a block: without restart points you'd replay from row 0, and a single corrupt or truncated entry breaks the chain for every key up to the next restart point.
• Diminishing returns when keys are short or dissimilar — the per-entry shared count can cost more than it saves.
• Reconstruction burns CPU on hot read paths; if lookups dominate, shrink the restart interval to bound the walk.
• The first key (and every restart point) must be stored in full — forget the anchor and nothing downstream can be rebuilt.

Worked example

Picture a block of 1,000 sorted log-segment keys like eu-west-1/2026/06/26/host-abcd/segment-00042. Consecutive keys share a 30-plus byte prefix (region, date, host) and differ only in the trailing segment number.

Stored in full that's roughly 45 bytes × 1,000 ≈ 45 KB. With prefix compression most rows reduce to a one-byte shared count plus a 5-to-6 byte suffix — the block drops to a few KB. A lookup for one key seeks to the nearest restart point, then walks a handful of entries forward, rebuilding each key by inheriting its predecessor's prefix until it lands on the target.

Check yourself