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 set intersections and full-text relevance ranking in sub-millisecond time.

Interactive Architecture Diagram
100%Fit100%
Synthesizing vector architecture diagram...

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:

$\text{Score}(D, Q) = \sum_{i=1}^{n} \text{IDF}(q_i) \cdot \frac{f(q_i, D) \cdot (k_1 + 1)}{f(q_i, D) + k_1 \cdot \left(1 - b + b \cdot \frac{|D|}{\text{avgdl}}\right)}$

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.
• Skip-List Binary Search Jumping: $O(M \log(N/M))$ comparisons using forward skip pointers every $\sqrt{N}$ elements.
• Roaring Bitmaps: Hardware SIMD bitwise AND operations executing at $> 10\text{ GB/sec}$.