Trie & Inverted Index

1. What It Is & Why It Exists

The Core Problem: Prefix Matching & Arbitrary Full-Text Search

Relational databases index scalar values with B-Trees, which support exact match and prefix queries (WHERE name LIKE 'app%') in $O(\log N)$ time. However, modern search architectures require:

1. Ultra-Low Latency Autocomplete ($< 10\text{ ms}$ at $100\text{k+ QPS}$): Finding top-K suggestions matching a typed prefix regardless of total dictionary size.
2. Arbitrary Substring & Multi-Term Search (LIKE '%system%design%'): Querying documents containing multiple keywords in any order across billions of web pages. Standard B-Trees cannot perform substring searches without full table scans.

The First-Principles Solution: Specialized Information Retrieval Structures

• Trie (Prefix Tree): A tree data structure where keys are decomposed along characters. Search time is strictly $O(L)$, where $L$ is the length of the query prefix, completely decoupled from total dictionary size $N$.
• Inverted Index: An associative data structure that maps every unique dictionary term (word) to a sorted list of integer document identifiers (Posting List), enabling fast set intersections and full-text relevance ranking.

Synthesizing vector architecture diagram...

The two panels answer two different search questions. In the "Autocomplete Prefix Trie" panel, a user types s-y-s and the lookup walks one node per letter from the root; the node for 'sys' already stores its top 5 completions, so the suggestions come back after 3 steps no matter how many phrases exist. Typing on to 'system' just continues down the same path to a node with its own top 5. In the "Inverted Index with BM25 Scoring" panel, each word maps to a sorted list of document IDs; a query for "distributed consensus" walks the two lists in parallel with two pointers, keeps the IDs in both (42 and 105), and then ranks them with BM25. Tries answer "what starts with this?" and inverted indexes answer "which documents contain these words?"

2. Mathematical Foundations & Algorithmic Mechanics

1. The Okapi BM25 Ranking Formula

Modern search engines (Elasticsearch, Amazon OpenSearch, Lucene) rank matched documents using the Okapi BM25 probabilistic relevance score:

Where:

• $\text{IDF}(q_i) = \ln\left( \frac{N - n(q_i) + 0.5}{n(q_i) + 0.5} + 1 \right)$: Inverse Document Frequency penalizing ubiquitous terms (e.g. "the", "is").
• $f(q_i, D)$: Term frequency of keyword $q_i$ in document $D$.
• $|D| / \text{avgdl}$: Document length normalized against average corpus length.
• $k_1 \approx 1.2, b \approx 0.75$: Standard saturation tuning parameters.

2. Posting List Intersection Time Complexity

Given two sorted posting lists of lengths $M$ and $N$ ($M \le N$):

• Linear Two-Pointer Intersection: $O(M + N)$ comparisons.
• Galloping (Exponential) Search: $O(M \log(N/M))$ comparisons: for each entry of the short list, jump ahead in the long list by doubling steps, then binary search. Skip pointers (a textbook heuristic places one every $\sqrt{N}$ entries) let the long list jump ahead in a similar way.
• Roaring Bitmaps: Dense chunks are stored as bitmaps and intersected with word-wide (and SIMD) bitwise AND, many document IDs per instruction.