Tries: Autocomplete, Prefix Search and Memory Cost in C#

Version note: The code in this post was built with .NET 10, C# 14 and ASP.NET Core 10 and verified with xUnit v3 4.0.2 tests; measurements were taken with BenchmarkDotNet 0.15.8 and the database examples with PostgreSQL 18.6. The Angular component was type-checked with the TypeScript compiler against Angular 22.2 packages.

Guess First

The /usr/share/dict/words file on macOS leaves 234,456 English words once lowercased and deduplicated; 2,248,668 characters in total. Keeping them in a sorted string[] takes 11.7 MB. We put the same words into a trie for autocomplete:

long trieBytes = Measure(() => { Trie t = new(); foreach (string w in words) t.Insert(w); return t; }, out object t1);

A trie shares common prefixes: "algorithm", "algorithmic" and "algorism" store the leading "algo" letters once. So does a trie take less space than the array? 5 MB, 12 MB, 50 MB? The answer is halfway through the post, and it is not what most people expect.

What a Trie Is: A Tree, Character by Character

A trie (the name comes from "retrieval") is a tree that stores keys character by character instead of as a whole. Every path starting at the root is a prefix; the node where a word ends is marked. "dune" and "dune messiah" share the first four nodes, "dracula" only the first "d". To find out whether a prefix exists you take as many steps as the prefix has characters: O(m), where m is the prefix length, regardless of how many words are stored.

public sealed record Suggestion(string Text, int Weight);

public sealed class Trie
{
    private sealed class Node
    {
        public Dictionary<char, Node>? Children;
        public string? Word;   // set only on nodes where a word ends
        public int Weight;
    }

    private readonly Node _root = new();

    public int Count { get; private set; }
    public int NodeCount { get; private set; } = 1;

    public void Insert(string key, int weight = 0, string? display = null)
    {
        Node node = _root;
        foreach (char c in key)
        {
            node.Children ??= [];
            if (!node.Children.TryGetValue(c, out Node? next))
            {
                next = new Node();
                node.Children.Add(c, next);
                NodeCount++;
            }

            node = next;
        }

        if (node.Word is null)
        {
            Count++;
        }

        node.Word = display ?? key;
        node.Weight = weight;
    }

    public bool Contains(string key) => Find(key)?.Word is not null;

    public bool StartsWith(string prefix) => Find(prefix) is not null;

    private Node? Find(string prefix)
    {
        Node? node = _root;
        foreach (char c in prefix)
        {
            if (node.Children is null || !node.Children.TryGetValue(c, out node))
            {
                return null;
            }
        }

        return node;
    }
}

There are three design decisions. We keep the word itself (Word) on the node, so we do not have to reassemble the path when producing suggestions, and the key can differ from the text shown on screen (useful in a moment for Turkish characters). The Children dictionary is created lazily; most leaf nodes never get children. And Contains("dun") and StartsWith("dun") are different things: "dun" exists as a prefix but not as a word.

The Best N Suggestions

In autocomplete we want to show the user who typed "d" the five most likely suggestions, not thousands of words. We give every word a weight (sales count, search frequency), go down to the prefix's node, walk the subtree below it and keep the best N with the size-K heap from the previous post:

public List<Suggestion> Suggest(string prefix, int limit)
{
    Node? start = Find(prefix);
    if (start is null || limit <= 0)
    {
        return [];
    }

    // The weakest candidate on top: lower weight, or alphabetically later on a tie
    PriorityQueue<Suggestion, (int Weight, string Text)> best = new(
        Comparer<(int Weight, string Text)>.Create((a, b) =>
            a.Weight != b.Weight ? a.Weight.CompareTo(b.Weight) : string.CompareOrdinal(b.Text, a.Text)));
    Stack<Node> stack = new();
    stack.Push(start);
    while (stack.Count > 0)
    {
        Node node = stack.Pop();
        if (node.Word is not null)
        {
            Suggestion s = new(node.Word, node.Weight);
            if (best.Count < limit)
            {
                best.Enqueue(s, (s.Weight, s.Text));
            }
            else if (best.TryPeek(out _, out (int Weight, string Text) min)
                     && (s.Weight > min.Weight || (s.Weight == min.Weight && string.CompareOrdinal(s.Text, min.Text) < 0)))
            {
                best.DequeueEnqueue(s, (s.Weight, s.Text));
            }
        }

        if (node.Children is not null)
        {
            foreach (Node child in node.Children.Values) stack.Push(child);
        }
    }

    List<Suggestion> result = [];
    while (best.TryDequeue(out Suggestion? s, out _)) result.Add(s);
    result.Reverse();
    return result;
}

We also folded alphabetical order on equal weights into the priority; otherwise, as we saw in the previous post, the order of equal priorities is undefined and tests break at random. We walk the subtree with an explicit Stack rather than recursion, so depth is never an issue with a long word list (the 5th post of the series). The cost is O(m) to reach the prefix plus the number of nodes in the subtree; a short prefix like "a" walks a large part of the dictionary. We will come back to that in the measurement section.

Two of the tests:

[Fact]
public void Contains_PrefixOnly_ReturnsFalse()
{
    Trie trie = CreateCatalog();
    Assert.True(trie.Contains("dune"));
    Assert.False(trie.Contains("dun"));
    Assert.True(trie.StartsWith("dun"));
    Assert.False(trie.StartsWith("x"));
}

[Fact]
public void Suggest_ReturnsHighestWeightFirst()
{
    List<Suggestion> result = CreateCatalog().Suggest("d", 3);
    Assert.Equal(["Dune", "Dracula", "Don Quixote"], result.Select(s => s.Text));
}

Memory Cost: A Dictionary or a Fixed Array

The classic textbook trie keeps an alphabet-sized array in every node: 26 slots for lowercase English. A lookup is a single index operation, no hashing:

public sealed class AsciiTrie
{
    private sealed class Node
    {
        public readonly Node?[] Children = new Node?[26];
        public bool IsWord;
    }

    private readonly Node _root = new();

    public int NodeCount { get; private set; } = 1;

    public bool Insert(string word)
    {
        Node node = _root;
        foreach (char c in word)
        {
            int i = c - 'a';
            if ((uint)i >= 26)
            {
                return false; // only 'a'..'z'
            }

            if (node.Children[i] is null)
            {
                node.Children[i] = new Node();
                NodeCount++;
            }

            node = node.Children[i]!;
        }

        node.IsWord = true;
        return true;
    }
}

Now the answer to the opening question. To measure the live heap I ran a full GC (Garbage Collector) before and after each measurement and looked at GC.GetGCMemoryInfo(GCKind.FullBlocking).PromotedBytes, the bytes that survived the GC (on this machine GC.GetTotalMemory did not give reliable results; in a control measurement it reported a 240 MB array as 472 MB):

static long LiveBytes()
{
    GC.Collect(2, GCCollectionMode.Forced, blocking: true, compacting: true);
    return GC.GetGCMemoryInfo(GCKind.FullBlocking).PromotedBytes;
}

words: 234,456, characters: 2,248,668
sorted string[]               11.7 MB
HashSet<string>               16.1 MB
Trie (Dictionary children)   148.9 MB  nodes=758,897
AsciiTrie (26-slot array)    191.1 MB  nodes=758,880

The trie uses 13 times more memory than the sorted array holding the same words. Prefix sharing does reduce 2.25 million characters to 759 thousand nodes, so it really saves something; but a character is 2 bytes inside a string while a node is tens or hundreds of bytes. In AsciiTrie each node's 26-reference array alone is 232 bytes (a 16-byte header, 8 bytes of length, 26 × 8-byte slots), and most slots are empty. The dictionary version takes less, because leaf nodes never create a dictionary; but a populated dictionary is itself expensive with its bucket and entry arrays (the 6th post of the series).

This does not mean tries are bad; it means you need to know what you are paying for. There are more compact variants: the radix tree (compressed trie), which merges single-child chains into one node, the double-array trie, which keeps nodes in arrays, and the DAFSA (Deterministic Acyclic Finite State Automaton), which also merges shared suffixes. All of them reduce memory in exchange for implementation complexity.

Turkish Characters and Case Folding

The Bookstore catalog has "İstanbul Hatırası", and the user types istan or ISTAN into the search box. Is lowercasing the key enough? The real output:

CultureInfo tr = CultureInfo.GetCultureInfo("tr-TR");
string[] samples = ["İstanbul", "ISTANBUL"];
foreach (string s in samples)
{
    string inv = s.ToLowerInvariant();
    string trLower = s.ToLower(tr);
    Console.WriteLine($"{s,-9} invariant={inv} (len {inv.Length})  tr-TR={trLower} (len {trLower.Length})  fold={SearchKey.Fold(s)}");
}

İstanbul  invariant=İstanbul (len 8)  tr-TR=istanbul (len 8)  fold=istanbul
ISTANBUL  invariant=istanbul (len 8)  tr-TR=ıstanbul (len 8)  fold=istanbul

Two separate traps. ToLowerInvariant() does not change "İ" (U+0130) at all; as the output shows, .NET's invariant casing leaves this letter alone, so "İstanbul" stays in the trie with a capital İ and a search for "istan" cannot find it. ToLower(tr-TR) converts "İ" correctly, but this time it turns the ASCII (American Standard Code for Information Interchange) "I" into "ı": if someone without a Turkish keyboard types "ISTANBUL", we search for "ıstanbul". This is the search engine version of the Turkish I trap from the "Strings in C#" post of the C# Basics series.

The solution for search keys is to use the same folding function both when storing and when searching: lowercase with Turkish rules, split letters into base letter and accent with Unicode NFD (Normalization Form D), drop the accents, and map "ı" to "i":

public static class SearchKey
{
    private static readonly CultureInfo Turkish = CultureInfo.GetCultureInfo("tr-TR");

    // "İstanbul", "ISTANBUL" and "istanbul" all become "istanbul"; "Şiir" becomes "siir"
    public static string Fold(string text)
    {
        string lower = text.Trim().ToLower(Turkish).Normalize(NormalizationForm.FormD);
        StringBuilder sb = new(lower.Length);
        foreach (char c in lower)
        {
            if (CharUnicodeInfo.GetUnicodeCategory(c) == UnicodeCategory.NonSpacingMark)
            {
                continue; // accents such as ş = s + U+0327, ç = c + U+0327, ğ = g + U+0306
            }

            sb.Append(c == 'ı' ? 'i' : c);
        }

        return sb.ToString().Normalize(NormalizationForm.FormC);
    }
}

[Theory]
[InlineData("İstanbul", "istanbul")]
[InlineData("ISTANBUL", "istanbul")]
[InlineData("  Şiir Kitabı ", "siir kitabi")]
[InlineData("Çağlayan", "caglayan")]
public void Fold_TurkishText_ProducesAsciiLikeKey(string input, string expected) =>
    Assert.Equal(expected, SearchKey.Fold(input));

This is a deliberate loss: "sık" and "şık" fall onto the same key. For search and autocomplete that is exactly what we want, because users may not type Turkish characters; but do not use the key as an identity (a unique constraint, an equality check). Since we keep the display text separately (the display parameter), the user still sees "İstanbul Hatırası". The trie's tests:

Test run summary: Passed!
  total: 10
  failed: 0
  succeeded: 10
  skipped: 0
  duration: 306ms

End to End: A Minimal API and an Angular Search Box

We build the trie once at startup and register it as a singleton; the endpoint only reads it, so nothing extra is needed for thread safety:

using Algorithms.Trees;

var builder = WebApplication.CreateBuilder(args);
builder.Services.AddSingleton(_ => BuildCatalogTrie());

var app = builder.Build();

app.MapGet("/api/suggest", (string? q, Trie trie) =>
{
    if (string.IsNullOrWhiteSpace(q) || q.Length > 50)
    {
        return Results.Ok(Array.Empty<Suggestion>());
    }

    return Results.Ok(trie.Suggest(SearchKey.Fold(q), limit: 5));
});

app.Run();

static Trie BuildCatalogTrie()
{
    // In production: titles and weekly sales come from the database at startup.
    (string Title, int Sales)[] catalog =
    [
        ("Dune", 950), ("Dune Messiah", 310), ("Dracula", 720), ("Don Quixote", 400),
        ("Dubliners", 120), ("Şu Çılgın Türkler", 85), ("İstanbul Hatırası", 240), ("Ince Memed", 530),
        ("Emma", 150), ("Middlemarch", 90)
    ];

    Trie trie = new();
    foreach ((string title, int sales) in catalog)
    {
        trie.Insert(SearchKey.Fold(title), sales, display: title);
    }

    return trie;
}

Asking Kestrel with curl (in the URL (Uniform Resource Locator) "İ" is encoded in UTF (Unicode Transformation Format) 8 as %C4%B0 and "ı" as %C4%B1):

$ curl -s "http://127.0.0.1:5712/api/suggest?q=du"
[{"text":"Dune","weight":950},{"text":"Dune Messiah","weight":310},{"text":"Dubliners","weight":120}]
$ curl -s "http://127.0.0.1:5712/api/suggest?q=d"
[{"text":"Dune","weight":950},{"text":"Dracula","weight":720},{"text":"Don Quixote","weight":400},{"text":"Dune Messiah","weight":310},{"text":"Dubliners","weight":120}]
$ curl -s "http://127.0.0.1:5712/api/suggest?q=%C4%B0stan"
[{"text":"İstanbul Hatırası","weight":240}]
$ curl -s "http://127.0.0.1:5712/api/suggest?q=istan"
[{"text":"İstanbul Hatırası","weight":240}]
$ curl -s "http://127.0.0.1:5712/api/suggest?q=SU"
[{"text":"Şu Çılgın Türkler","weight":85}]
$ curl -s "http://127.0.0.1:5712/api/suggest?q=%C4%B1nce"
[{"text":"Ince Memed","weight":530}]
$ curl -s "http://127.0.0.1:5712/api/suggest?q=xyz"
[]

İstan, istan, SU and ınce all find the right book. On the client we do not want a request per keystroke. In Angular we push the input into a Subject and slow it down with RxJS (Reactive Extensions for JavaScript) operators:

import { Component, inject } from '@angular/core';
import { HttpClient, HttpParams } from '@angular/common/http';
import { toSignal } from '@angular/core/rxjs-interop';
import { Subject, debounceTime, distinctUntilChanged, map, of, switchMap } from 'rxjs';

interface Suggestion {
  text: string;
  weight: number;
}

@Component({
  selector: 'app-book-search',
  template: `
    <input type="search" placeholder="Search books" (input)="query$.next($any($event.target).value)" />
    <ul>
      @for (s of suggestions(); track s.text) {
        <li>{{ s.text }}</li>
      }
    </ul>
  `,
})
export class BookSearchComponent {
  private readonly http = inject(HttpClient);
  protected readonly query$ = new Subject<string>();

  protected readonly suggestions = toSignal(
    this.query$.pipe(
      map(q => q.trim()),
      debounceTime(250),
      distinctUntilChanged(),
      // switchMap: a new keystroke cancels the previous request
      switchMap(q => q.length < 2
        ? of([] as Suggestion[])
        : this.http.get<Suggestion[]>('/api/suggest', { params: new HttpParams().set('q', q) })),
    ),
    { initialValue: [] as Suggestion[] },
  );
}

debounceTime(250) waits until the user pauses for 250 ms, distinctUntilChanged does not send the same query again, and switchMap cancels the old HTTP (Hypertext Transfer Protocol) request when a new query arrives, so a late old response never overwrites the new result. We covered debounce itself in the "JavaScript Performance Tips" post of the JavaScript Advanced series.

Comparing Alternatives and Measuring

The trie's most serious rival is a sorted array with binary search. Words starting with a prefix sit next to each other in a sorted array; you find the first one with the lower bound from the 10th post of the series and move forward until the prefix ends:

// words must be sorted with StringComparer.Ordinal
public static List<string> StartsWith(string[] words, string prefix, int limit)
{
    int lo = 0, hi = words.Length;
    while (lo < hi)
    {
        int mid = lo + (hi - lo) / 2;
        if (string.CompareOrdinal(words[mid], prefix) < 0) lo = mid + 1;
        else hi = mid;
    }

    List<string> result = [];
    for (int i = lo; i < words.Length && result.Count < limit && words[i].StartsWith(prefix, StringComparison.Ordinal); i++)
    {
        result.Add(words[i]);
    }

    return result;
}

I measured the three approaches on the same job: give each of the 234,456 words a random weight and find the 10 heaviest among those starting with the prefix. The sorted array version finds the start of the range with binary search and scans the range, the linear scan walks the whole list; both use the same size-K heap for the top 10. 40 words start with "algo" and 3,032 with "pre".

The measurements were taken on an Apple M5 (10 cores), macOS 27.0.1, .NET 10.0.13 and BenchmarkDotNet 0.15.8. I ran the benchmarks one at a time, but other work was running on the machine; look at the ratios, not the absolute numbers.

| Method            | Prefix | Mean         | Ratio | Allocated |
|------------------ |------- |-------------:|------:|----------:|
| Trie_Top10        | algo   |   1,035.9 ns | 0.004 |    2752 B |
| SortedArray_Top10 | algo   |     200.1 ns | 0.001 |     344 B |
| LinearScan_Top10  | algo   | 242,784.8 ns | 1.002 |     296 B |
|                   |        |              |       |           |
| Trie_Top10        | pre    |  68,517.4 ns |  0.28 |   99312 B |
| SortedArray_Top10 | pre    |   7,501.6 ns |  0.03 |     344 B |
| LinearScan_Top10  | pre    | 248,770.7 ns |  1.00 |     296 B |

Both comfortably beat the linear scan. But the sorted array beats the trie by a factor of 5 to 9. The trie walks every node in the subtree by following pointers and through dictionary enumerators (a foreach over Values on every node, 97 KB of allocations for "pre"); in the sorted array the same 3,032 words sit in contiguous memory. The lesson: for data like this dictionary, loaded once and never changed, "prefix search" alone is not a good enough reason to pick a trie.

The trie really pulls ahead elsewhere. If the data keeps changing, an insert into a sorted array needs an O(n) shift, into a trie O(m). When the user presses a key you can advance one character from the previous node instead of starting the search over. And if every node stores the precomputed best N suggestions of its subtree, Suggest stops walking the subtree entirely and drops to O(m); that is what large search boxes do, at the cost of even more memory.

If the data is already in a database, prefix search is exactly what a B+tree index does well (the 12th post of the series). I loaded the same words into a table in PostgreSQL. With the default en_US.utf8 collation a plain index is not used for LIKE 'algo%'; the planner picks a parallel seq scan. An index created with the text_pattern_ops operator class turns the prefix into a range:

CREATE INDEX ix_words_word_pattern ON words (word text_pattern_ops);
EXPLAIN (ANALYZE, COSTS OFF, TIMING OFF, BUFFERS) SELECT word FROM words WHERE word LIKE 'algo%';

 Index Only Scan using ix_words_word_pattern on words (actual rows=31.00 loops=1)
   Index Cond: ((word ~>=~ 'algo'::text) AND (word ~<~ 'algp'::text))
   Filter: (word ~~ 'algo%'::text)
   Heap Fetches: 31
   Index Searches: 1
   Buffers: shared hit=1 read=3
 Execution Time: 0.046 ms

The range between 'algo' and 'algp' is the very same idea as "start at the lower bound and go until the prefix ends" from binary search; 31 rows (the table is case-sensitive), four pages. Search engines like Elasticsearch do this job distributed and typo-tolerant with structures like edge n-grams and the completion suggester; we will cover that in the upcoming Elasticsearch series.

Production Notes

Measure memory, do not guess. For 50,000 book titles a trie is a few MB and not a problem; for tens of millions of products and description texts, at the ratio above, it can reach gigabytes. Know your container's memory limit, build the trie once with real data and look with GC.GetGCMemoryInfo().

Update strategy. If we build the trie at startup, what happens when the catalog changes? The simple and safe way is to build a new trie in the background and swap it in with a single reference assignment (Volatile.Write, or Interlocked.Exchange on a holder object); readers see either the old or the new trie without waiting on a lock. Mutating the same trie in place races with concurrent reads.

Limit the input. The endpoint has a q.Length > 50 check; very short prefixes (a single letter) walk most of the subtree. Waiting for at least two characters on the client and applying rate limiting on the server are simple defenses for the fact that the autocomplete endpoint is the most frequently called one.

Keep normalization in one place. Using different folding functions for storing and searching is the classic source of hard-to-reproduce bugs reported as "sometimes it doesn't find it". A single function like SearchKey.Fold and its tests close that risk.

Common Pitfalls

Underestimating the trie's memory cost. As the measurement showed, prefix sharing reduces the node count, but a node is tens of times more expensive than a character. A 13x difference is the exact opposite of the "a trie saves space" intuition.

Folding Turkish text with ToLowerInvariant. "İ" stays unchanged and the search silently returns incomplete results; the bug never shows in the logs, the user just says "I couldn't find it".

Confusing a prefix with a word. A validation that uses StartsWith instead of Contains accepts "dun" as a valid title. Test the two separately.

Unicode surrogate pairs. Our trie works on char; characters made of two chars, like emoji, are split across two nodes. If titles have no emoji it does not matter, but if you key on user input, consider working with Rune.

A Small Experiment

★☆☆ Add Remove(string key) to Trie: clear the word mark and walk back up, pruning nodes that no longer lead to any word. Test that NodeCount decreases correctly.

★★☆ Write a variant that stores the best 5 suggestions of its subtree in every node (update them along the path during insert). Rerun the benchmark with the "pre" prefix and redo the memory measurement too: how many times faster did it get, and how much did memory grow?

★★★ Write a radix tree that merges single-child chains (a string fragment per node instead of a single character). For the same 234,456 words compare the node count and live memory with Trie and the sorted array.

With the trie we spread keys across the paths of a tree. In the next post we drop the constraints of a tree entirely: structures where a node can have more than one parent and cycles are possible. Follow relationships, roads between cities, project dependencies; all of them are graphs. We start with adjacency lists, BFS (Breadth-First Search) and DFS (Depth-First Search).