← Back
Home › Systems › CI/CD and developer tooling

code-search

code search at scale

Zoekt, Sourcegraph

SystemTechniques · 9Primitives · 31 code-search Code symbol indexingcompilers · medium: Extract definitions and references per file, give each symbol a stable string id, and store symbol to occurrences, re-indexing only files whose content hash changed.›Incremental parsingcompilers · medium: Reparse only the region an edit damaged and splice the new subtrees into the old tree, sharing everything else; O(edit) instead of O(file).›Scatter-gather querydistributed · medium: Send a query only to shards that can match, merge their small partial results, and bound the wait for stragglers.›Linear-time regular expression matc…search-sort · medium: Match a regular expression in O(pattern x text) worst case by tracking all live parse positions at once, then cache the state sets as a lazily built DFA for speed.›Trigram indexsearch-sort · medium: Trigram posting lists accelerating regex and substring searchInverted indexstorage · medium: Map each term to a sorted, compressed list of the documents containing it; the core of full-text search and other fast set queries.›Language server protocolcompilers · medium: One JSON-RPC conversation over a pipe lets any editor drive any language's analysis server; the cost is keeping a live, edited document in sync and answering before it changes.›Top-k selectionsearch-sort · low: Keep the k best of n items without sorting all n - bounded min-heap for streams, quickselect for arrays, threshold pruning to skip most items.›SIMD substring searchsearch-sort · low: Find bytes or substrings by comparing 16-64 haystack positions per instruction against the needle's first and last byte, then verifying the rare candidates.›Delta encodingcompression · low: Store differences between consecutive values instead of the values, turning sorted IDs, timestamps and counters into small numbers that pack into few bits.›Varint (LEB128)compression · low: Variable-length integers in 7-bit groups with a continuation bit; small numbers take 1 byte, the wire format of Protobuf, WebAssembly and DWARF.›BM25 rankingsearch-sort · low: The standard lexical relevance score: IDF-weighted term frequency with saturation (k1) and length normalization (b); default in Lucene, Elasticsearch and SQLite FTS5.›Roaring bitmapscompression · low: Compressed set of 32-bit integers in 64K-value chunks, each a sorted array, bitmap or run list; fast intersections, the standard for bitmap indexes.›Consistent hashingdistributed · low: Hash nodes and keys onto a ring; each key belongs to the next node clockwise, so membership changes move only about 1/n of keys.›mmap and the page cachehardware-os · low: How read() and mmap reach file data through the kernel page cache, what readahead and madvise do, and why databases use their own buffer pool instead.›Fuzzy finder scoringsearch-sort · low: Subsequence matching with gap/position scoring (fzf-style)Suffix arraysearch-sort · low: Sorted array of all suffix start positions of a text; finds every occurrence of any substring by binary search, at 4-5 bytes per text byte.›Name resolutioncompilers · low: Bind every use of a name to its declaration with a scope stack, handling shadowing, hoisting and closure capture in one AST walk.›Protobuf wire formatnetworking · low: Protocol Buffers wire format: tags, varints, length-delimited fields and schema evolutionRecursive-descent parsingcompilers · low: Hand-written top-down parser with one function per grammar rule; simple, fast, with full control over error messages and recovery.›Ropegraphics · low: A balanced tree of small string chunks with cached byte and newline counts, so seek, insert, delete and snapshot cost O(log n) instead of O(n).›K way mergesearch-sort · low: Merge k sorted streams with a heap or loser tree (merging iterators)Deadline propagationsystems · low: Carry an absolute deadline and cancellation along a call chain+ 2 more techniques+ 15 more primitives

Similar systems

Share the most building blocks with this one.

codebase-indexing 26 %search-engine 25 %vector-db 23 %timeseries-db 21 %metrics 21 %