How Autocomplete Search Engines Work

You type two letters into a search box, and before your finger leaves the key, a list of suggestions appears. Behind that list sits a dataset of millions of terms, and the answer arrives in under 10 milliseconds. This article shows how a Trie makes that possible, and how to build one

Searching Millions of Words Fast

Think of a printed dictionary. If you search for a word, you do not read every page from the beginning. You flip directly to the section for that letter.

Searching a database using a simple string scan checks every entry line by line. As the dataset grows to millions of records, checking every string takes tens of milliseconds. Autocomplete boxes in search engines need to return results in under 10 milliseconds. A prefix tree, also called a Trie, organizes words by their individual characters to make search speeds independent of the total word count.

The Problem with Naive List Scanning

Imagine keeping a list of ten million search terms in an array. When a user types the letters ca, the application loops over all ten million strings to find matches using string.StartsWith("ca").

This operation runs in O(N * L) time, where N is ten million items and L is the length of the string. Under heavy traffic, processing hundreds of simultaneous requests with this approach consumes CPU resources quickly. Memory cache hits drop because array scanning inspects unrelated memory blocks across the heap.

How a Trie Stores Words

Think of a family tree where each child inherits the family name and adds their own middle name. Each step down the tree adds one letter.

A Trie is a tree data structure made of nodes. The root node represents an empty state. Each child node contains a single character, a dictionary of child nodes, and a boolean flag called IsEndOfWord.

public class TrieNode
{
    public Dictionary<char, TrieNode> Children { get; } = new();
    public bool IsEndOfWord { get; set; }
}

When inserting the word car, the algorithm starts at the root node. It checks if a child node for c exists. If not, it creates one. It moves to node c, checks for a, and then checks for r. At node r, it sets IsEndOfWord to true. Inserting cat reuses nodes c and a, creating only a new node for t.

Finding exact matches takes O(L) time, where L is the length of the word. Searching for car in a dataset of ten million words takes exactly three steps.

Collecting Suggestions with Depth-First Search

Think of exploring a maze. You walk down one path until you reach a dead end, then turn back to try the next path.

To generate autocomplete suggestions for a prefix like ca, the application moves down the tree to node a. From that node, it runs a Depth-First Search (DFS) to collect all words in the subtree below it.

public List<string> GetSuggestions(string prefix, int maxResults = 10)
{
    var results = new List<string>();
    var current = _root;
    foreach (char ch in prefix)
    {
        if (!current.Children.TryGetValue(ch, out var child))
            return results;
        current = child;
    }

    CollectWordsDfs(current, prefix, results, ref maxResults);
    return results;
}

private void CollectWordsDfs(TrieNode node, string currentWord, List<string> results, ref int maxResults)
{
    if (maxResults == 0) return;

    if (node.IsEndOfWord)
    {
        results.Add(currentWord);
        maxResults--;
    }

    foreach (var (ch, childNode) in node.Children)
    {
        if (maxResults == 0) break;
        CollectWordsDfs(childNode, currentWord + ch, results, ref maxResults);
    }
}

Limiting the search with a maxResults counter stops the recursive traversal as soon as the target count is reached. This pruning avoids scanning thousands of descendant nodes when only ten suggestions are displayed on screen.

Ranking Suggestions with Pre-Cached Results

Think of a grocery store putting popular items near the checkout counter so customers do not walk to the back of the store.

Users expect autocomplete results sorted by popularity score rather than alphabetical order. Sorting thousands of matching words during a user request slows down response times.

To fix this, each TrieNode stores a small list of its top suggestions directly on the node.

public class TrieNode
{
    public Dictionary<char, TrieNode> Children { get; } = new();
    public bool IsEndOfWord { get; set; }
    public int Frequency { get; set; }
    public List<(string Word, int Score)> TopSuggestions { get; set; } = new();
}

During insertion, the algorithm updates the TopSuggestions list for every node along the word path. When a user queries a prefix, the engine traverses to the prefix node and returns its TopSuggestions list immediately in O(L) time.

This approach creates a clear tradeoff. Query operations become fast, but insertion operations take slightly longer and each node requires additional memory.

Memory Overhead and Radix Trees

Think of a long hallway with ten doors in a row, but nine of them are empty rooms. Merging the empty rooms creates one larger hallway.

In managed runtimes like C#, every class instance on the heap carries object header overhead of around 24 bytes. A standard Trie holding five million nodes can consume over 500 MB of RAM.

A Radix Tree, also called a Compressed Trie, merges single-child node sequences into a single node with a multi-character edge label.

Inserting autocomplete and automation creates a single shared root node with the edge label auto. The tree branches from auto into two child nodes labeled complete and mation. This reduces total node count by over 70 percent.

High Concurrency with ReaderWriterLockSlim

Think of a public notice board. Hundreds of people can read the board at the same time. When someone posts a new notice, readers step back until the update finishes.

Web applications process thousands of read queries per second while background workers continuously update search frequencies. C# dictionaries are not safe for concurrent reading and writing.

Using ReaderWriterLockSlim allows multiple thread reads simultaneously while ensuring write operations run with exclusive access.

public class ConcurrentTrie : IDisposable
{
    private readonly TrieNode _root = new();
    private readonly ReaderWriterLockSlim _rwLock = new();

    public List<(string Word, int Score)> GetTopRankedSuggestions(string prefix)
    {
        _rwLock.EnterReadLock();
        try
        {
            var current = _root;
            foreach (char ch in prefix)
            {
                if (!current.Children.TryGetValue(ch, out var child))
                    return new();
                current = child;
            }
            return current.TopSuggestions.ToList();
        }
        finally
        {
            _rwLock.ExitReadLock();
        }
    }

    public void Insert(string word, int score = 1)
    {
        _rwLock.EnterWriteLock();
        try
        {
            // Traverse path and insert node
        }
        finally
        {
            _rwLock.ExitWriteLock();
        }
    }

    public void Dispose()
    {
        _rwLock.Dispose();
    }
}

Option Comparison

Approach	Lookup Time	Memory Usage	Insertion Complexity	Thread Safety
Naive List Scan	O(N * L)	Lowest	O(1)	Requires external lock
Standard Trie	O(L + K * M)	High	O(L)	Not thread-safe
Pre-Cached Top-K Trie	O(L)	Higher	O(L * K log K)	Not thread-safe
Radix Tree	O(L)	Low	O(L)	Not thread-safe
Concurrent Pre-Cached Trie	O(L)	Higher	O(L * K log K)	Safe for high concurrent reads