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
Citations
- Brisaboa et al. (2011): Compressed String Dictionaries, section 2.4
- LevelDB 1.23: BlockBuilder key-prefix encoding and restart offsets
- LevelDB 1.23: TableBuilder::WriteBlock and optional block compression
- LevelDB 1.23: Block::Iter seek and reconstruction
Further reading
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.