← Back
Home › Systems › Databases and storage engines

search-engine

full-text search engine

Elasticsearch, Tantivy

SystemTechniques · 8Primitives · 31 search-engine Scatter-gather querydistributed · medium: Send a query only to shards that can match, merge their small partial results, and bound the wait for stragglers.›Primary-backup replicationdistributed · medium: One node orders all writes and ships them to standbys; the acknowledgement rule (none, one, all) sets what a crash loses, and an external arbiter decides who takes over.›Top-k pruning with score upper boun…search-sort · medium: Skip documents that provably cannot enter the top-k, using per-list and per-block maximum scores against the current k-th best score (WAND, Block-Max WAND, MaxScore).›Columnar storagestorage · medium: Store each column contiguously so analytic scans read only the columns they need, compress well and run as tight SIMD loops.›Inverted 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.›LSM compactionstorage · medium: Compaction policies (leveled, tiered, time-window, FIFO) decide which sorted files to merge and when, trading write, read and space amplification and purging tombstones.›LSM-treestorage · medium: Buffer writes in memory, flush them as immutable sorted files and merge in the background; turns random writes into sequential I/O.›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.›Bit packing and PFORcompression · low: Store blocks of integers with exactly b bits each and patch rare outliers separately (PFOR); the fastest integer codec family, billions of values per second.›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.›Sorted-list intersectionsearch-sort · low: Intersect sorted id lists by merging, galloping from the short list into the long one, and skipping whole compressed blocks, shortest list first.›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.›Prefix compressioncompression · low: Front coding / shared-prefix truncation of sorted keys in blocks and index pagesRoaring 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.›Skip listdata-structures · low: Sorted linked list with random express lanes; O(log n) search, simple inserts, and easy lock-free or single-writer concurrent reads.›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.›Finite state transducersearch-sort · low: Minimal acyclic FST mapping sorted keys to values; compact term dictionaries with prefix/fuzzy searchLevenshtein automatasearch-sort · low: Levenshtein automata / edit-distance search over dictionaries for typo toleranceStemmingsearch-sort · low: Porter/Snowball suffix stripping and lemmatisation for term normalisationUnicode text tokenization for searchsearch-sort · low: Turn multilingual text into index terms: segment words (UAX 29 style, CJK bigrams), normalize, case-fold and accent-fold, identically at index and query time.›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 chainHedged requestssystems · low: Sending a backup request after a latency percentile and taking the first answer to cut tail latency+ 1 more techniques+ 15 more primitives

Similar systems

Share the most building blocks with this one.

product-search 27 %vector-db 25 %code-search 25 %web-search 24 %timeseries-db 23 %