Lucene On-Disk Data Structures — Intensive

A Lucene segment is not an opaque blob. It is a small zoo of files, each one a precisely specified byte format written by a Codec component, and each one a data structure you can name, decode by hand, and validate. The Segments and Codecs chapter taught you the file zoo — .tim, .doc, .kdd, .dvd, .vec — and the Codec SPI that defines them. This masterclass goes one level deeper: what is actually in the bytes, the algorithm that produced them, and the org.apache.lucene.* class that reads them back. By the end you should be able to take a raw segment file, xxd its header, name its codec, and reason about its internal layout from first principles — and to walk into a Lucene *Format source file and recognize the structure on the page.

This is the byte-level companion to three chapters you should have read first:

• Inverted Index and Postings — terms, FST, postings.
• Points and BKD Trees — numeric/geo points.
• DocValues (columnar) — per-doc values.
• HNSW Vector Search — the vector format.

Where those chapters explained concepts, this one nails down formats. The four labs then make every format concrete in runnable Java: Lab LD1 (FST terms dict), Lab LD2 (postings + BKD), Lab LD3 (HNSW files), Lab LD4 (DocValues encodings).

After this chapter you can: name every segment file extension and the *Format that owns it; explain how a term lookup descends an FST in .tip then a block in .tim; describe the 128-int FOR/PForDelta postings blocks; trace a BKD range query through .kdi/.kdd; identify the numeric DocValues encoding a field got; read a CodecUtil header with xxd; and recognize corruption symptoms by file.

The master file map

Every file Lucene writes shares a structure: a CodecUtil header (magic + codec name + version + segment id + a per-file suffix), the payload, and a footer (a magic + a CRC32 of every preceding byte). That envelope is what makes corruption detectable and what CheckIndex validates. Inside the envelope, the payload differs per format. Memorize this table — it is the spine of the whole masterclass.

Note: The Lucene90/Lucene99/Lucene101 prefixes are version stamps that bump only when the byte format changes — not on every release. Stored fields, norms, and DocValues have stayed Lucene90 for many releases; postings and vectors moved to Lucene99/Lucene101. Never hard-code the number; grep your checkout. A Lucene upgrade in OpenSearch is precisely "the default codec version moved." Find the current set:

# In an apache/lucene checkout, list the per-format versions the default codec wires:
ls lucene/core/src/java/org/apache/lucene/codecs/lucene*/
grep -n "FieldInfosFormat\|SegmentInfoFormat\|PostingsFormat\|DocValuesFormat\|\
StoredFieldsFormat\|PointsFormat\|KnnVectorsFormat\|NormsFormat" \
  lucene/core/src/java/org/apache/lucene/codecs/lucene*/Lucene*Codec.java

The CodecUtil envelope

Before any format-specific bytes, every file begins with a header written by CodecUtil.writeIndexHeader and ends with a footer from CodecUtil.writeFooter:

HEADER (CodecUtil.writeIndexHeader):
  int32  magic          = 0x3FD76C17   (CODEC_MAGIC; big-endian on disk)
  string codecName      e.g. "Lucene90StoredFieldsFastData"  (writeString: vInt len + UTF-8)
  int32  version        format version
  byte[16] objectID     the segment's StringHelper.randomId() (per-segment unique)
  string suffix         a per-file suffix (often "", used by per-field formats)

... payload (format-specific) ...

FOOTER (CodecUtil.writeFooter):
  int32  magic          = 0xC02893E8   (FOOTER_MAGIC)
  int32  algorithmID    = 0            (CRC32)
  int64  checksum       CRC32 of every byte from offset 0 up to here

The magic 0x3FD76C17 is the four bytes 3F D7 6C 17 at the very start of every Lucene file. You will see it in xxd in Lab LD3:

xxd -l 16 /path/to/shard/index/_0.vec
# 00000000: 3fd7 6c17 1d4c 7563 656e 6539 3948 6e73  ?.l..Lucene99Hns
#           ^^^^^^^^^^ CODEC_MAGIC  ^^ len  ^^^^^^^^^^ codec name begins

grep -n "CODEC_MAGIC\|FOOTER_MAGIC\|writeIndexHeader\|writeFooter\|checkFooter\|retrieveChecksum" \
  lucene/core/src/java/org/apache/lucene/codecs/CodecUtil.java

This envelope is why OpenSearch's Store.checkIndex / Store.MetadataSnapshot can detect a single flipped bit anywhere in a file: the footer CRC won't match, and Lucene throws CorruptIndexException. See the storage engine masterclass for how OpenSearch wraps this in Store.

Terms dictionary: BlockTree, the FST, and the blocks

The terms dictionary is the most intricate format and the one worth understanding deeply because the FST it uses appears all over Lucene (synonyms, suggesters, MultiTermQuery). The implementation is BlockTreeTermsWriter (write side) and Lucene90BlockTreeTermsReader (read side), the on-disk format spans three files:

What an FST is, exactly

An FST (finite-state transducer) is a deterministic automaton that, given an input byte sequence, both accepts/rejects it and emits an output. In the terms index the input is a term prefix (bytes) and the output is a long — a file pointer into .tim. Three properties make it the right structure:

1. Shared prefixes — like a trie, common leading bytes share states. apple and apply share the path a→p→p→l.
2. Shared suffixes — unlike a trie, the FST is minimized: states with identical futures are merged. The trailing e/y and shared tails collapse, so the structure is closer to a DAG than a tree. This is what makes it small.
3. Outputs on arcs — each arc carries a partial output; the output for a term is the sum (for PositiveIntOutputs, the addition) of the arc outputs along its path. Outputs are pushed toward the root as far as possible during construction, so common prefixes carry the shared part of the pointer.

The result is a near-minimal, perfect-hashing-like byte array: compact enough to keep in RAM, cache-friendly to traverse, and exact (no false positives within its key set). Lucene stores it as a flat byte[] (FST.getBytesReader()), not an object graph — pointer arithmetic, not object headers.

# The FST core — read FST.java once; it is one of the highest-return hours in Lucene:
find lucene/core/src/java/org/apache/lucene -path "*util/fst/FST.java"
grep -rn "class FSTCompiler\|class FST\b\|PositiveIntOutputs\|ByteSequenceOutputs\|readFirstTargetArc\|findTargetArc" \
  lucene/core/src/java/org/apache/lucene/util/fst/

Lab LD1 builds one of these directly with FSTCompiler + PositiveIntOutputs and traverses it arc by arc.

How a term lookup descends FST → block

The terms index FST does not contain every term — that would defeat the point. It contains just enough prefixes to land you on the right block in .tim, where a short linear scan finds the exact term. A block holds up to ~maxItemsInBlock (default 48) terms sharing a prefix; when a prefix has too many terms the block is split into sub-blocks, forming the "tree" of BlockTree.

flowchart TD
    Q["TermsEnum.seekExact('brown')"] --> FST["FST in .tip (RAM)"]
    FST -->|"walk arcs b → r → o ..."| Arc["accumulate output = file pointer"]
    Arc -->|"floor block pointer"| Blk["term block in .tim (on disk)"]
    Blk -->|"linear scan within block"| Term["exact term 'brown' found?"]
    Term -->|yes| Meta["term metadata: docFreq, totalTermFreq,\nfile pointers into .doc/.pos/.pay"]
    Term -->|no| Miss["term does not exist"]
    Meta --> Doc[".doc postings (FOR blocks)"]

The seek algorithm in SegmentTermsEnum.seekExact:

1. Walk the FST arc-by-arc consuming the term's bytes, accumulating the output. The FST returns the file pointer of the floor block — the on-disk block whose first term is ≤ the target.
2. seek .tim to that pointer, read the block header (prefix length, term count, whether terms or sub-blocks).
3. Scan terms within the block, comparing the suffix bytes, until you find the term or pass it. Within a block terms are stored as prefix-suffix: the shared block prefix once, then each term's distinct suffix.
4. On a match, read the term's metadata: docFreq, totalTermFreq, and the file pointers (docStartFP, posStartFP, payStartFP) into the postings files.

grep -rn "class BlockTreeTermsWriter\|maxItemsInBlock\|writeBlock\|FieldMetaData" \
  lucene/core/src/java/org/apache/lucene/codecs/lucene*/Lucene*BlockTreeTermsWriter.java
grep -rn "class SegmentTermsEnum\|seekExact\|class IntersectTermsEnum" \
  lucene/core/src/java/org/apache/lucene/codecs/lucene*/

Note: A keyword field and a text field both use this exact terms dict — the difference is IndexOptions (what postings are attached), not the dictionary format. A MultiTermQuery (prefix/wildcard/regex) drives IntersectTermsEnum, which intersects an automaton with the terms-dict FST — two automata walked in lockstep. That is why a leading wildcard is slow: the automaton matches a huge slice of the FST.

Postings: 128-int blocks, delta, FOR / PForDelta

Once the terms dict hands you the file pointers, the postings live in .doc (doc-ids + freqs), .pos (positions), and .pay (payloads + offsets). The format is Lucene99PostingsFormat (grep your version). The headline technique is block encoding: postings are stored in fixed blocks of 128 integers, and each block is bit-packed.

Delta + FOR

Doc-ids in a postings list are strictly increasing, so Lucene stores deltas (gaps), which are small. A block of 128 deltas is encoded with FOR (Frame-Of-Reference): find the maximum delta in the block, compute how many bits b it needs, and pack all 128 values at b bits each. A block of deltas that all fit in 5 bits costs 128 × 5 / 8 = 80 bytes instead of 128 × 4 = 512.

ForUtil is the SIMD-friendly bit-packer/unpacker; it has a specialized unrolled decode routine per bit width (decode1, decode2, … decode32). The decode reads b packed longs and fans them out to 128 ints with shifts and masks — branch-free and vectorizable.

grep -rn "class ForUtil\|BLOCK_SIZE\|decode\|encode" \
  lucene/core/src/java/org/apache/lucene/codecs/lucene*/ForUtil.java | head
grep -rn "BLOCK_SIZE\s*=\s*128\|class Lucene99PostingsFormat\|class ForDeltaUtil" \
  lucene/core/src/java/org/apache/lucene/codecs/lucene*/

PForDelta for the tail and for freqs

Pure FOR is wasteful when one outlier delta forces a wide bit width on all 128 values. PForDelta (Patched Frame-Of-Reference, PForUtil) handles this: pick a bit width that fits most values, then store the few exceptions separately as patches. So a block of [3, 4, 2, 5, 1000, 3, 2] packs at the width for ~5 and stores 1000 as a patch — no wasted bits on the common case.

grep -rn "class PForUtil\|exception\|patch\|encodeDeltas" \
  lucene/core/src/java/org/apache/lucene/codecs/lucene*/PForUtil.java | head

Term frequencies ride alongside doc-ids: when a field stores freqs (DOCS_AND_FREQS+), the .doc file interleaves a freq block with each doc-id block (freqs are also FOR-packed). A tail of fewer than 128 postings that doesn't fill a block is written as vInts (variable-length ints), not a packed block.

Skip data

A long postings list embeds a multi-level skip list so advance(target) is sublinear. Conceptually, every 128-doc block gets a level-0 skip entry (doc-id + file pointers); every Nth level-0 entry gets a level-1 entry; and so on. advance walks the top level to get close, then refines down, then decodes only the final block. In the Lucene99 format the skip data is interleaved into .doc rather than a separate file, and competitive-scoring metadata (block max impacts) rides with it so WAND/MaxScore can skip non-competitive blocks.

flowchart LR
    A["PostingsEnum.advance(10000)"] --> L2["skip level: jump to block near 10000"]
    L2 --> L1["refine to the exact 128-doc block"]
    L1 --> Dec["ForUtil.decode the one block"]
    Dec --> Land["binary/linear scan to first doc >= 10000"]

grep -rn "Skip\|class .*SkipReader\|class .*SkipWriter\|blockMaxScore\|impacts" \
  lucene/core/src/java/org/apache/lucene/codecs/lucene*/ | head

Lab LD2 part (a) walks a real PostingsEnum and points you at the ForUtil decode site.

Points / BKD: the block-KD tree

Numeric, date, IP, and geo fields are indexed as points in a BKD tree (a write-optimized, disk-resident, balanced k-d tree). BKDWriter builds it; BKDReader queries it; the format owns three files:

Build algorithm

BKDWriter collects all (packedValue, docId) pairs, then builds a balanced tree top-down by recursive partitioning:

1. If the current set fits in one leaf (≤ maxPointsInLeafNode, default 512), write it as a leaf block to .kdd and stop.
2. Otherwise choose the split dimension = the dimension with the widest value range in this node (most spread → best partition).
3. Partition the points by the median value of that dimension into left/right halves of (nearly) equal size; recurse. The split value goes into .kdi.

Because it splits at the median and leaves are full, the tree is balanced and its depth is ≈ log2(N / maxPointsInLeafNode). A 10M-point single-dim field with 512-point leaves is ~14.6 levels deep.

Leaf encoding and prefix compression

Within a leaf, points are sorted by the split dimension and stored with prefix compression: the common leading bytes of consecutive packed values are written once. For low-cardinality data a leaf can shrink dramatically. Each leaf also stores its doc-ids (delta-or-bitpacked) so a matching point maps back to a document.

flowchart TD
    Root["root (.kdm root pointer)"] --> N1["split on dim with widest range\nat median value"]
    N1 -->|"value <= split"| L1["left subtree (.kdi)"]
    N1 -->|"value > split"| R1["right subtree (.kdi)"]
    L1 --> Leaf1["leaf: <= 512 points,\nprefix-compressed (.kdd)"]
    R1 --> Leaf2["leaf: <= 512 points (.kdd)"]

Query: intersect with a range

A range query (IntPoint.newRangeQuery) calls PointValues.intersect(visitor), which walks the tree and, per node, asks visitor.compare(minPackedValue, maxPackedValue):

• CELL_OUTSIDE_QUERY — node's bounding box is disjoint from the range → prune the whole subtree (the speedup).
• CELL_INSIDE_QUERY — node's box is fully inside → collect all leaf doc-ids without per-point checks.
• CELL_CROSSES_QUERY — partial overlap → recurse; at a leaf, check each point.

grep -rn "class BKDWriter\|maxPointsInLeafNode\|DEFAULT_MAX_POINTS_IN_LEAF_NODE\|split\b\|class BKDReader" \
  lucene/core/src/java/org/apache/lucene/util/bkd/
grep -rn "CELL_INSIDE_QUERY\|CELL_OUTSIDE_QUERY\|CELL_CROSSES_QUERY\|interface IntersectVisitor" \
  lucene/core/src/java/org/apache/lucene/index/PointValues.java

Lab LD2 part (b) runs intersect and reads the leaf structure via CheckIndex. The concept chapter is Points and BKD Trees.

DocValues: the columnar store and its encodings

DocValues are Lucene's column store — per-doc values laid out by field for fast sequential and random access (sorting, aggregations, faceting, function scoring). The format is Lucene90DocValuesFormat, files .dvd (data) + .dvm (metadata). The cleverness is entirely in the numeric encodings, chosen per field per segment by inspecting the values:

Lucene90DocValuesConsumer (write) picks the encoding by scanning min/max, GCD, and the distinct-count; Lucene90DocValuesProducer (read) re-creates the decoder from .dvm. The metadata for a numeric field records which path was taken.

grep -rn "GCD\|gcd\|class Lucene90DocValuesConsumer\|writeNumericField\|MONOTONIC_BLOCK_SIZE\|numBitsPerValue" \
  lucene/core/src/java/org/apache/lucene/codecs/lucene90/Lucene90DocValuesConsumer.java
grep -rn "DELTA_COMPRESSED\|GCD_COMPRESSED\|TABLE_COMPRESSED\|MONOTONIC_COMPRESSED\|SPARSE_COMPRESSED" \
  lucene/core/src/java/org/apache/lucene/codecs/lucene90/Lucene90DocValuesFormat.java

Ordinals and SORTED_SET

A SORTED/SORTED_SET field stores, per doc, ordinals (small ints) into a single sorted block of the distinct term bytes. So ["us","gb","us","fr"] stores the term block [fr, gb, us] once and per-doc ordinals [2, 1, 2, 0]. Sorting and faceting then operate on cheap ints; only at the end do you resolve an ordinal to its bytes. Across segments these are local ordinals; OpenSearch builds global ordinals to unify them for aggregations — see DocValues and fielddata deep-dive.

Jump tables for sparse fields

If only some docs have a value (a sparse field), the metadata stores a jump table (an IndexedDISI — Doc-Id-Set-Iterator) so advanceExact(docId) skips the gaps in O(1)-ish blocks instead of scanning. Dense fields skip this overhead.

grep -rn "class IndexedDISI\|jump\|DENSE\|SPARSE\|ALL\b" \
  lucene/core/src/java/org/apache/lucene/codecs/lucene90/IndexedDISI.java | head

Lab LD4 makes you observe delta vs GCD vs table by comparing .dvd sizes for high- and low-cardinality fields.

Stored fields: chunked + LZ4 / DEFLATE

Stored fields hold the original field values you can fetch back (OpenSearch's _source is one big stored field). The format is Lucene90StoredFieldsFormat, files .fdt (data), .fdx (index — a monotonic map doc→chunk), .fdm (meta).

Documents are grouped into chunks (by a target size / doc count) and each chunk is compressed as a unit:

Compressing a chunk (not a single doc) lets the compressor find cross-document redundancy — log lines with similar structure compress well together. The .fdx index is itself a monotonic DocValues-style structure mapping doc-id → chunk start, so fetching doc D is "binary-search the chunk, decompress it, skip to D's offset." best_compression affects only these stored-field chunks — not postings, points, or DocValues (a very common misconception). See Segments and Codecs.

grep -rn "BEST_SPEED\|BEST_COMPRESSION\|LZ4\|DeflateWithPreset\|chunkSize\|class Lucene90CompressingStoredFieldsWriter" \
  lucene/core/src/java/org/apache/lucene/codecs/lucene90/Lucene90StoredFieldsFormat.java

Norms, field infos, segment info, the commit

The small-but-essential remainder:

• Norms (.nvd/.nvm, Lucene90NormsFormat): per-field, per-doc length norm — a single byte (a lossy SmallFloat encoding of 1/sqrt(length) ish) used by BM25 for length normalization. Disable with norms: false on a field to save space if you never score it. Read via LeafReader.getNormValues(field).
• Field infos (.fnm, Lucene*FieldInfosFormat): the field schema of the segment — for each field: number, name, IndexOptions, DocValues type, whether it has norms/payloads, point dimensions, vector dimensions + similarity, and an attributes map (this is where the per-field postings/DV/vector format name is recorded so the reader re-instantiates the right *Format).
• Segment info (.si, Lucene*SegmentInfoFormat): per-segment metadata — doc count, codec name, the file set, the index sort (if any), a diagnostics map (Lucene/JVM/OS version that wrote it), and the segment's 16-byte id.
• Commit (segments_N, SegmentInfos): the commit point — generation N, the list of live segments with their codec and per-segment deletion generation, the user data map (OpenSearch stores the translog uuid + history here). This is the one file whose presence makes the index recoverable; see the storage engine masterclass.

grep -rn "class FieldInfo\b\|writeField\|attributes\|class SegmentInfos\|class SegmentInfo \b" \
  lucene/core/src/java/org/apache/lucene/index/ | head

HNSW vectors: .vec, .vex, .vem

Vector fields are written by a KnnVectorsFormat — by default Lucene99HnswVectorsFormat (and its scalar-quantized cousins). The HNSW chapter covers the algorithm; here is the on-disk shape:

The .vec layout is just the vectors back to back — vector for ordinal 0, then 1, … — so random access by ordinal is offset = ord × dims × 4 (for float32). That contiguity is what lets the SIMD distance loops run fast. Scalar quantization (Lucene99HnswScalarQuantizedVectorsFormat) stores int8 components (¼ the bytes) plus per-vector or per-segment quantiles in .vem; the file-size difference is exactly what Lab LD3 measures with du. Map to OpenSearch via the k-NN engines chapter (engine: lucene).

grep -rn "class Lucene99HnswVectorsFormat\|class Lucene99HnswVectorsWriter\|writeGraph\|entryNode\|class Lucene99HnswScalarQuantizedVectorsFormat" \
  lucene/core/src/java/org/apache/lucene/codecs/lucene99/

Worked decode: a tiny terms-dict + postings example

Index two one-field documents and decode the structure by hand. Field body, default analyzer, DOCS_AND_FREQS_AND_POSITIONS:

doc 0: "the quick brown fox"
doc 1: "the lazy brown dog"

After analysis (lowercase, default stopword-free standard analyzer) the sorted terms for body are:

brown  fox  lazy  dog  quick  the     -> sorted: brown, dog, fox, lazy, quick, the

The postings (doc-ids ascending, with freqs and positions):

brown -> docs [0, 1]  freq [1, 1]  pos [[2], [2]]
dog   -> docs [1]     freq [1]     pos [[3]]
fox   -> docs [0]     freq [1]     pos [[3]]
lazy  -> docs [1]     freq [1]     pos [[1]]
quick -> docs [0]     freq [1]     pos [[1]]
the   -> docs [0, 1]  freq [1, 1]  pos [[0], [0]]

Terms dict (.tim/.tip). With only 6 terms, the BlockTree writes a single block (well under maxItemsInBlock = 48). The .tip FST has one arc set leading to that block's file pointer; every seekExact walks the FST to the same block, then scans linearly. The block stores the prefix-suffix layout: no common prefix here, so each term's full bytes plus its metadata (docFreq, totalTermFreq, docStartFP).

Postings (.doc). Each term has < 128 postings, so the doc-ids are written as vInts, not a packed FOR block:

brown: docDelta=0 (doc 0), freq=1 ; docDelta=1 (doc 1 = 0+1), freq=1
the:   docDelta=0 (doc 0), freq=1 ; docDelta=1 (doc 1), freq=1
fox:   docDelta=0 (doc 0), freq=1

Doc-ids are stored as gaps: the's postings are 0, +1, not 0, 1. With freqs on and freq always 1, Lucene uses the optimization where a freq of 1 is implied by a flag bit in the doc-delta (it shifts the delta left one and uses the low bit) — so the common single-occurrence case costs almost nothing.

Positions (.pos). brown at position 2 in both docs → position deltas [2], [2]. Positions are also delta-encoded within a doc.

You can verify all of this for real in Lab LD1 (TermsEnum walk) and Lab LD2 (PostingsEnum walk).

Validation tools: CheckIndex, Luke, find/xxd

Three tools recur in every lab:

# 1. CheckIndex — validate every segment, every CRC footer, and print structure.
#    Run against a COPY of a closed index (it can take a write lock).
java -cp "lucene-core-*.jar" org.apache.lucene.index.CheckIndex /path/to/indexCopy -verbose
# Look for: "test: terms, freq, prox...", "test: points...", "test: docvalues...",
#           "test: vectors...", and per-segment "maxPointsInLeafNode", leaf counts.

# 2. Luke — the GUI. In an apache/lucene checkout:
./gradlew :lucene:luke:run
#    Overview tab: per-field term counts, file sizes. Documents/Terms tab: walk the
#    terms dict. Commits tab: the segments_N and the file list.

# 3. find / du / xxd — the bytes themselves.
find /path/to/shard/index -maxdepth 1 -type f | sed 's/.*\.//' | sort | uniq -c
du -h /path/to/shard/index/*.{tim,doc,kdd,dvd,vec,fdt} 2>/dev/null
xxd -l 32 /path/to/shard/index/_0.tim   # the CODEC_MAGIC + codec name

grep -rn "class CheckIndex\|testPostings\|testPoints\|testDocValues\|testKnnVectors" \
  lucene/core/src/java/org/apache/lucene/index/CheckIndex.java | head

Note: CheckIndex with -exorcise removes bad segments — never run it on a live OpenSearch shard directory; copy first, and prefer OpenSearch's Store.checkIndex path. Use -verbose read-only to learn the structure.

Common bugs and symptoms

Validation: prove you understand this

1. Draw the CodecUtil envelope (header + payload + footer) and say which two magic numbers bracket every file and what the footer protects against.
2. Explain the terms-dict two-step seek: what the FST in .tip returns, what the block in .tim holds, and how a term's postings file pointers are found.
3. Describe FOR vs PForDelta for a 128-int postings block, and when the tail is written as vInts instead.
4. Given a 1M-point single-dimension field with the default leaf size, estimate the BKD tree depth, and explain the three compare outcomes that prune or collect a subtree.
5. Name the four numeric DocValues encodings and the data shape each one wins on; explain SORTED_SET ordinals and what a jump table is for.
6. Map .vec/.vex/.vem to their contents, say which grows with M, and which index.codec setting changes which file.
7. From a find/du/xxd over a real shard, classify every extension, read one CODEC_MAGIC header, and predict which file dominates the size for a logs index vs a vector index.

When you can do all seven, work the four labs in order — they make every format in this table something you have built and decoded with your own hands.