How do "Suggested Usernames" actually work?

We’ve talked about Redis Hashes for storage and Bloom Filters for the "Bouncer" at the door.

But what happens when ateebHussain is taken and you need to suggest:

• ateebHussain_1
• ateebHussain_pro
• ateeb_h

If you try to do this with LIKE %ateeb% in a SQL database with 10 million rows... RIP your latency.

Enter: The Trie Structure (Prefix Tree)

A Trie is a specialized tree used to store associative arrays. Instead of storing whole strings, it stores characters as nodes.

Imagine it like a path:
A -> T -> E -> E -> B

Why this is a Game Changer:

1. Autocomplete in $O(L)$ Time: Where $L$ is the length of the word. It doesn't matter if your DB has 1 billion names; finding "ateeb" takes the same amount of time.
2. Prefix Matching: It’s built for "starts with" queries. You can find every username starting with "ateeb" in milliseconds.
3. Memory Sharing: Usernames like ateeb1, ateeb2, and ateeb_dev all share the same "ateeb" prefix nodes. It’s incredibly efficient for overlapping data.

Where to use it?

• Search Bars: That "Search as you type" feature? Probably a Trie.
• Username Suggestions: Instantly finding the next available variation.
• IP Routing: High-speed networking uses this to route your data packets!

Building a Trie from scratch in production can be overkill for a small LMS or a simple store. But understanding how it works separates the "I just use frameworks" devs from the "I design systems" engineers.

If you’re using Next.js, you can actually implement a simple version of this in an Edge Function for insane performance.

Next post: B+ Trees. (The reason your PostgreSQL indexes actually work).

Have you ever tried implementing a Trie, or do you just let your frontend handle the filtering? Let’s talk architecture!