Building an Index Without Outgrowing Memory

For microsoft/tgrep, a useful query plan is only possible because a durable physical index can answer small lookups cheaply. This chapter follows the path from sorted trigram keys to posting lists, file paths, and coverage metadata, then explains how tgrep builds that structure without keeping an entire large repository’s postings in memory. The goal is to understand which component owns each responsibility and why bounded construction is part of the search design, not an unrelated implementation detail.

A lookup table points to just the evidence a query needs

Tgrep separates the index into a small number of cooperating representations. The sorted lookup table maps a trigram key to a range in the postings file. Each lookup entry contains the trigram, a byte offset, and a length. When the reader needs a trigram, it binary-searches the sorted table, jumps to that range, and decodes only the associated postings.

The posting record carries a file identifier and the compact masks associated with that trigram. It does not repeat the file’s path. A single integer can therefore participate in many posting lists without copying a long path into every one. After candidate selection, tgrep uses the file table to translate the identifier back to a repository-relative path and then to the full path it must read.

The file table is a separate variable-length mapping from dense file IDs to paths. Keeping IDs dense makes the lookup path simple and makes the ID range useful for compact arrays and sorted operations. The reader loads the path table so it can resolve results, while it memory-maps the lookup and postings sections for selective access. Memory mapping means the operating system can bring in the pages that a query actually touches without requiring tgrep to copy the whole index into ordinary heap allocations.

That separation follows the query planner’s access pattern. The planner produces a small set of trigram keys. The reader finds those keys with binary search. Each key leads to one posting range. The posting ranges produce candidate IDs. Only then does tgrep read candidate content and ask the full matcher for exact results. A physical design that stored every file’s full text in the lookup path would erase the advantage of doing selective lookups in the first place.

Tgrep also keeps a second membership question separate from content search. Some files belong to the traversed repository but do not produce searchable content postings: a binary image, a file rejected by its extension, or a file that could not be read during a build. The files-extra.bin sidecar stores those filename-only paths. This lets --files describe the admitted tree without pretending that every listed path has content trigrams.

The sidecar is not accepted in isolation. Hidden-file visibility is recorded separately, and the sidecar carries the identity of the file table it accompanies. The metadata records whether the index is complete and whether hidden-file coverage is proven.