# How does a Trie work?

Specifically, many say that to speed up an HTTP routing code going from regex to a Trie is the solution. Sometimes also a compressed Trie or Radix Tree.

The problem though is that after reading everything I think I could read from Wikipedia to blog articles and even Stack Exchange answers I couldn't wrap my head on how this is implemented. Maybe it's simpler than I think but I'm looking at it from the wrong perspective, no idea.

So let's take this HTTP request:

GET /hello HTTP/1.1
Host: www.stackoverflow.com
User-Agent: Mozilla/4.0 (compatible; MSIE5.01; Windows NT)
Accept: */*


With a Trie are you going to iterate on GET, then "/" then "hello" then "HTTP" then "1.1" etc until you get to the end of the request with matches or does it work differently than this?

               root
/  /   \  \
GET POST PUT DELETE
/
"/"
...
/
"HTTP"
/
"1"
/  \
"0" "1"


I have a hunch that that's not exactly the case because it has the potential to lock a loop or function where it's executed in, or waste resources if event'ed. Given the fact that this solution is considered when the HTTP routing itself becomes a problem it must work differently?

• You seem to be asking two questions: 1. "does it work like this" and 2. "Isn't there are problem if we do it like this". I think it is better to edit your question to simply state how you think a trie works and then ask only about what you think the problem is with that. This would make it more clear where the source of your confusion lies, I think. – Discrete lizard Apr 23 '18 at 14:23

For instance for the set {abc, aa, cdf}, the root node accepts {a, c}. Then the son a accepts {a, b} and the son c accepts {d}. And so on.