front-coding · shipping · also Front-coding, Key-prefix compression

Front coding

Front coding represents a string using its common-prefix length with a preceding string and the remaining suffix.

Dictionary: Lexicographically sorted strings often share prefixes. Bucketed front coding stores each bucket's first string explicitly, then encodes following strings relative to their predecessors. Search can binary-search bucket headers and reconstruct the selected bucket sequentially. [1]

Bytes: LevelDB 1.23 counts shared and unshared key bytes, not Unicode characters. A common byte prefix can end inside a UTF-8 code point; reconstruct the complete bytes before interpreting text. [2]

Storage: Full-key restart entries limit reconstruction dependencies. Entry length fields and restart offsets also consume space, so suffix-byte savings alone do not establish total block savings. Optional whole-block compression is a separate later step. [2] [3]

Scope: Prefix coding is a reversible representation, not a prefix Bloom membership test. Restart spacing trades metadata and repeated key bytes against reconstruction work; it does not predict hardware latency. [4]

Relations

related
SSTable restart point, Lossless compression

Citations

  1. Brisaboa et al. (2011): Compressed String Dictionaries, section 2.4 (accessed 2026-11-17)
  2. LevelDB 1.23: BlockBuilder key-prefix encoding and restart offsets (accessed 2026-11-17)
  3. LevelDB 1.23: TableBuilder::WriteBlock and optional block compression (accessed 2026-11-17)
  4. LevelDB 1.23: Block::Iter seek and reconstruction (accessed 2026-11-17)

Further reading

  1. Hesela: Front coding needs a complete byte ledger (accessed 2026-11-17)
Sources & caveats
  • Primary-source synthesis, with UTF-8 implications derived from byte-prefix semantics. Native LevelDB 1.23 block-builder and reader checks match 658 constructed raw-key, empty-value cases, including the accompanying byte ledger; this is not a database compression or performance benchmark.

JSON: /data/terms/front-coding.json

Published by Hesela team · Updated

Report a correction · Editorial standards · Reuse guidance

Cite this page
Hesela team. Front coding. Hesela. 2026-11-17. https://hesela.dev/terms/front-coding/