An autocomplete trie sized for ASCII blows its memory ceiling on a multilingual catalog — how do you decide what to change?

**Decompose the number before choosing a fix** Total memory is *node count* x *bytes per node*. A symbol-range change moves only the second factor, and it moves it violently, so the first diagnostic is a histogram, not a redesign: how many nodes, what is each one's fanout, how many bytes does each occupy. In nearly every version of this incident the answer is that most nodes have one or two children while each reserves capacity for the entire symbol range. **Lever 1: how a node represents its children** - **Fixed array over the symbol range.** Child lookup is a single index, which is the fastest per step and the reason the prototype was written this way. Cost scales with the symbol range and is paid by every node whether or not it has children. Fine for a tiny alphabet, ruinous for a universal one. - **Small sorted list of (symbol, child) pairs.** Cost is proportional to actual children. For fanout one to four — the overwhelming majority of nodes — a linear scan of a contiguous few pairs is both smaller and, thanks to locality, often faster than anything cleverer. Binary search inside the node handles the rare wide node. - **Per-node hash map.** Cost is also proportional to actual children, and per-step lookup is a hash plus a probe. The catch is fixed overhead per map instance, which for a node with a single child can exceed the child pointer several times over; use it only for genuinely wide nodes. - **Adaptive nodes.** Pick the representation per node by current fanout, promoting a small list to an indexed array when a node becomes wide. This is what serious radix-trie designs do, and it is also the option with the most code to maintain. **Lever 2: compression, which attacks the other factor** Collapse every maximal non-branching chain into one edge labelled with the whole substring. Node count drops from proportional-to-total-symbols to proportional-to-key-count. On a catalogue where most entries have a long unique tail this is usually the single largest win, and it composes with any children representation. It does not reduce the symbols compared during a lookup, and it complicates insertion, which must now split an edge when a new key diverges mid-label. **Lever 3: index bytes instead of symbols** If keys are stored in a variable-width encoding, build the trie over the encoded bytes. Fanout is then capped at 256 and compact per-node arrays become affordable again. Two consequences must be stated aloud, because this is where correctness bugs enter: 1. Paths get up to four times deeper for non-Latin text, so lookups chase more pointers. 2. A byte prefix is not a user-visible character prefix. A partially consumed multi-byte symbol must never surface as a completion, and prefixes must be **normalized and casefolded before insertion and before query**, or the same visible word will fail to match itself depending on how it was composed. Decide once, at the boundary, and store the folded form. **Lever 4: stop storing a trie** The structure is a means. If the only query is "top-k completions for this prefix": - **Precompute per prefix.** For prefixes up to k symbols, store the ranked completion list directly. Memory is bounded by a number you choose, latency is one lookup, and rebuilds are a batch job. You lose arbitrary-depth prefixes, which for a search box is usually acceptable after a handful of symbols. - **Sorted keys plus binary search.** Keys in sorted order make any prefix a contiguous range, found in O(L log n) comparisons. Memory is near the raw key bytes with no structural overhead, and the layout is contiguous and cache-friendly. - **Deduplicate shared suffixes.** Merging identical suffix subtrees turns the trie into an acyclic word graph, which is dramatically smaller for a word list. The cost is that per-key payloads no longer hang naturally off nodes, and incremental updates become hard — a good fit for a structure rebuilt offline, a bad one for live writes. **The judgment, which is the actual question** Rank the levers against three constraints rather than against smallest-wins: - *The ceiling and the budget.* How much do you need to save, and what per-lookup latency can you spend to save it? Compression plus a compact children representation typically clears an order of magnitude with no exotic structure; reach for a succinct encoding only if that is not enough. - *The write path.* If the catalogue updates continuously, structures that must be rebuilt offline are out regardless of their size, or need a two-structure design with a small live overlay merged periodically. - *Who maintains it.* A succinct structure one engineer understands is a liability at 3am, and its debugging story is much worse than a sorted array's. Choosing the second-smallest option that any team member can reason about is a defensible senior-leadership call, and saying so explicitly is what distinguishes this answer from a list of data structures. Finally, sequence the migration: correctness first (normalization and folding, which change *results*), then the space fixes, and keep the old index queryable behind a flag until the new one's completion sets match on real traffic. **The one-line takeaway** Alphabet size attacks bytes-per-node, so fix the children representation and compress the chains before considering exotic structures — and pick the option the team can operate, not the smallest one on paper.