How to Design a Typeahead Search System for a Seamless UX

Written by
Iván Ovejero
13 mins
Dec 6, 2024
Subscribe for more insights
Thank you for your interest in the syllabus.

We'll be in touch soon with more information!

In the meantime, if you have any questions, don’t hesitate to reach out to our team.

Oops! Something went wrong while submitting the form.

TLDR - How to Design a Typeahead Search System for a Seamless UX

  • Typeahead Search Expectation: Common across major platforms (Google, Amazon, YouTube); must be fast and relevant.
  • Core Requirements:
    • Speed: Suggestions within ~100ms on each keystroke.
    • Relevance: Based on user input and popularity (frequency of past searches).
  • System Overview:
    • Accept input, process into query + frequency, store for fast retrieval.
    • Retrieval must be optimized for prefix-based queries.
  • Naive SQL Approach Fails:
    • LIKE <prefix>% is too slow at scale due to inefficient range scans.
  • Trie as a Natural Fit:
    • Tree structure to store/query strings by prefix.
    • Mark terminal nodes for valid completions + store frequency.
  • Trie Optimization Steps:
    • Store completions/frequencies at each node to avoid subtree traversals (space–speed tradeoff).
    • Limit prefix length and number of completions per prefix to reduce time complexity to O(1).
  • Prefix Hash Tree:
    • Hash each prefix to a key → completions as values.
    • Enables direct O(1) lookup, great for read-heavy workloads.
  • Redis as Backend Store:
    • Linked List:
      • Fast O(1) reads/writes but very slow O(n) updates.
      • Poor fit for concurrent updates and scaling.
    • Sorted Set:
      • O(log n) reads/writes, O(1) frequency updates via ZINCRBY.
      • Handles sorting, deduplication, and concurrent updates efficiently.
      • Allows limiting set size using an increment trick to keep new entries in rotation.
  • Further Considerations:
    • Move stale prefixes to persistent storage to save memory.
    • Choose a DB that complements prefix hash structure.
    • Design ingestion pipelines and cache strategies.
    • Use browser storage + debouncing to minimize backend requests.
  • We at Codesmith cultivate technologists who are at the intersection of society and tech, able to meet this moment and thrive in an ever-changing world. Ready to become a modern software engineer?

    Typing into a search box and immediately seeing suggestions, also known as typeahead search, is a feature so common as to have become an expectation. Google, Twitter, GitHub, Amazon, YouTube, and many others all offer their own flavor of typeahead search—it is hard to imagine search without it.

    google example of typeahead search

    Effortless as it seems, typeahead search is not trivial to implement at scale. Serving suggestions in the blink of an eye requires a system able to ingest, process, and store constantly changing data—and perhaps most importantly, to query it in milliseconds. How do we strike a balance between speed, relevance, and cost efficiency?

    Let's design a typeahead search system.

    Framing the design

    From the user's perspective, typeahead search requires...

    • Speed: As a user types their query, suggestions must be offered instantly, on every keypress, in the order of 100 milliseconds. Suggestions slower than the average typing speed would defeat the purpose of the feature.
    • Relevance: Relevant suggestions are more likely to make for a successful search. Relevant suggestions are those based on the user's query and popular among other users, as indicated by how many times they have been searched for in the past.

    Functionally, this means that our system must be able to accept user queries from a variety of sources (e.g. web, mobile, and desktop), process those queries into usable records (i.e. text and frequency), and store and serve those records while optimizing for reads. A starting point for the retrieval component might look like this:

    high level design of typeahead search system

    The high-level flow here is straightforward. On receiving a request, we query a cache (or on cache miss, persistent storage) and return relevant results, ensuring the cache is kept fresh. Given that so many of these interactions are common to other systems, we will center our discussion around the most distinctive aspect of typeahead search: the fast retrieval of suggestions relevant to user input.

    Optimizing for reads

    Think of our access pattern. In typeahead search, we query based on user input ("prefix") and our results must be semantically valid strings that follow from it ("completions"), sorted by frequency. The simplest solution might be a SQL query:

    SELECT query_text, frequency FROM queries

    WHERE query_text LIKE <prefix>%

    ORDER BY frequency DESC;

    While viable for small datasets, this SQL approach does not scale. Pattern matching with a wildcard causes inefficient range scans, and string comparisons are computationally expensive. As the dataset grows, our query will become slower and slower, so this approach is a non-starter.

    A more natural fit for text search is the trie, a data structure specialized in storing and finding strings in a vast collection. Typically, a trie is a tree where every node is home to a character, and where every child of a node holds a character that follows the character in the parent node, or the sequence up to that node.

    typeahead search trie without labels

    Each path from root to leaf represents a string, but not all strings are semantically valid. A string in a trie may be a stub like soa, a full word like soap, or a multi-word query like soap opera shows. (Note how whitespace is just another character.) To filter out invalid completions, we can mark the end of a semantically valid sequence of characters by flagging its terminal node. This terminal node is also a good spot to store the frequency of the string.

    typeahead search trie with labels

    How does this help us? To retrieve a string based on user input ("prefix"), we need to traverse the trie until reaching the node that contains the final character of the prefix.

    typeahead traverse to reach prefix node

    From there, we traverse the children of the prefix, i.e. we visit every child in this subtree, collecting all the strings ("completions") that start with the prefix.

    typeahead traverse to find completions

    And finally, we sort the completions we found.

    typeahead sort completions to return

    In other words, retrieval follows three steps:

    1. Reach the end of the prefix: O(n)
    2. Find all its completions: O(n) (worst case)
    3. Sort the completions: O(log n)

    Notice that this is an overall time complexity of O(n), which does not scale. Let's see how we can improve it step by step.

    Consider the second step. Finding all completions is the most expensive step, and it will take longer and longer as the trie grows. To optimize this step, instead of storing a frequency value at each node, we can store all completions and their frequency values for a node at the node itself. In other words, all the information contained in the subtree is now at its root. Much less space-efficient, but we "trim" the tree—we do away with subtree traversals to find completions.

    typeahead store completions at each node

    What about the first step? Reaching the end of the prefix is also O(n), if less expensive than traversing a subtree. It is reasonable to expect that a query is likely to be short, i.e. very long queries like soap opera shows that aired in 2020 in Turkey are statistically unlikely. There are diminishing returns to storing every single prefix for long-query cases, so we can choose to restrict prefix length. The shorter the prefix, the fewer nodes we will need to traverse.

    Now look back at the third step. If it is reasonable to expect that a query is likely to contain only a handful of words, it is also reasonable to expect that a user is likely to only ever need a handful of suggestions, that is, not all children in the entire subtree. Hence, again, if we restrict the number of completions we store for a prefix, we will have less data we need to store and sort through.

    In sum, by holding values constant, we have reduced time complexity from O(n) to O(1), which will scale nicely. Another improvement is in the data structure itself: rather than a regular trie, we can opt for a prefix hash tree, where every prefix is a hash key and completions are the value of that key. Depending on our requirements, we may choose to keep or outright discard semantically invalid strings.

    typeahead prefix hash tree

    This data structure grants us O(1) access to completions for any prefix, eliminating traversals altogether. Once again, we are trading space for speed of retrieval, but this is a tradeoff we are willing to make.

    Storing our data structure

    A prefix hash tree is also a perfect match for a key-value store. And given our use case, we would do well to look at an in-memory key-value store. Redis is a popular choice for typeahead search, being fast, simple and versatile, with native data structures to support our access pattern. Which Redis data structure best fits our use case?

    In a Redis linked list, we can set up a chain of nodes where each holds a completion and its value, with all of them sorted by frequency and lexicographical order. To find completions, we can issue an LRANGE command to fetch the top n suggestions at the top of the list in O(1). And to add a completion, we can issue an RPUSH command to append it to the tail of the list in O(1). In both cases, the time complexity is stellar.

    typeahead redis linked list find append

    But updates pose a problem. To update a node to increment its frequency, we will need to remove it and re-insert it at its new position, a costly multi-step operation:

    1. Retrieve the entire linked list: O(n)
    2. Binary search the list to find the target node: O(log n)
    3. Update the target node to increment its frequency: O(1)
    4. Binary search the list to find the new position of the target node: O(log n)
    5. Find and remove the target node from its current position: O(n)
    6. Find and insert the target node at its new position: O(n)
    typeahead redis linked list update

    All this work is far from ideal:

    • Overall time complexity is O(n).
    • We are making more than one round trip to Redis.
    • We are serving the entire list as a payload.
    • Sorting occurs at the application level.
    • Concurrent updates may become an issue.

    In short, O(1) for search and addition is superb, but not at the cost of O(n) updates, not to mention that this is a poor match for a prefix hash tree. Can we do better?

    In a Redis sorted set, for each letter in the alphabet, we can set up an ordered collection of items, each consisting of a string and a frequency value. Redis itself keeps the set in order (by frequency value and then by lexicographical order) and also takes care of deduplicating strings.

    In a sorted set, retrieval is straightforward: Redis offers the ZRANGE command to retrieve the top n elements in O(log n). Likewise, to add to a sorted set, Redis offers ZADD, which is also O(log n). Both operations are slower than their linked list equivalents at O(1), while still relatively fast.

    But where sorted sets shine is in update operations. Redis offers ZINCRBY to increment the score of a member in O(1), a significant improvement over linked lists, which requires O(n). Refer to the Redis documentation for details on the skip lists that make this possible.

    typeahead redis sorted set increment

    This option addresses most shortcomings of linked lists:

    • Overall time complexity is O(log n).
    • We are making only one round trip to Redis.
    • We are serving only the top n elements as a payload.
    • Sorting and deduplicating are delegated to Redis.
    • Concurrent updates become less likely.

    Sorted sets are therefore a better fit for our use case. But there is one pending issue.

    Earlier we chose to limit the number of completions we store for a prefix. But doing so at the application level would mean retrieving the entire sorted set, removing the least frequent items, and storing the updated set. How do we enforce this limit in sorted sets? The creator of Redis himself offers an elegantly simple solution. On adding a completion that causes the set to overstep the size limit:

    1. Remove the completion with the lowest frequency, but store this value.
    2. Add the new completion to the set, with the stored frequency value plus 1.
    typeahead limit sorted set size

    Why reuse the incremented frequency value for the new completion? If we were to add the new completion with a frequency of 1, the new completion would be the least relevant completion in the set—bound to be removed on the next addition—so this ensures the new completion will not be immediately replaced by the next completion. We afford all completions an equal opportunity to rise to the top.

    Going further

    In this discussion, we laid out a design for the retrieval component of a typeahead search system—zeroing in on optimizing queries, storing our data structure, and translating our choices to performant operations, while keeping an eye on tradeoffs and limitations. We paid careful attention to time complexity, which is essential for creating the search experience users have come to expect.

    But this is only one aspect out of many. As our system grows, keeping all data in memory will soon become infeasible, i.e. we are likely to need persistent storage. In fact, when limiting our sorted set size, we might want to evict stale prefixes to persistent storage, rather than dropping them entirely.

    To keep building out the system, consider:

    • how to select a DB that maps well to our prefix hash tree,
    • how to prime our cache and keep it up to date on cache miss,
    • how to set up an ingestion and processing pipeline for our system,
    • how to harness browser storage to cache completions, and
    • how to debounce keypress events to prevent excess requests.

    In designing a typeahead search system, remember that optimizing retrieval is only the beginning of a larger discussion where there is much more to explore.

    Find out how we cover AI/ML in our updated curriculum
    Get your Syllabus
    Special blog guest offer!

    Explore CS Prep further in our beginner-friendly program.

    Get 50% Off CS Prep
    Learning code on your own?

    Get more free resources and access to coding events every 2 weeks.

    Thank you for your interest in the syllabus.

    We'll be in touch soon with more information!

    In the meantime, if you have any questions, don’t hesitate to reach out to our team.

    Oops! Something went wrong while submitting the form.
    Want to learn more about advancing your career in tech?

    Connect with one of our graduates/recruiters.

    Schedule a Call

    Our graduates/recruiters work at:

    ABOUT THE AUTHOR

    Related Articles

    Understanding the basics of CSS Flexbox

    Tutorial
    JavaScript
    by
    Alex Stewart
    Jun 6, 2025
    |
    8 mins

    How to Design a Typeahead Search System for a Seamless UX

    Tutorial
    by
    Iván Ovejero
    Dec 6, 2024
    |
    13 mins

    Meta Llama 2 vs. GPT-4: Which AI Model Comes Out on Top?

    Tutorial
    AI/ML
    by
    Diana Cheung
    Nov 9, 2024
    |
    14 mins

    Start your journey to a coding career.

    Thank you for your interest in the syllabus.

    We'll be in touch soon with more information!

    In the meantime, if you have any questions, don’t hesitate to reach out to our team.

    Oops! Something went wrong while submitting the form.
    Want to learn more about advancing your career in tech?

    Connect with one of our recruiters to learn about their journeys.

    Schedule a Call

    Our graduates/recruiters work at: