When you type a URL and hit Enter, does it just magically find what to load in the page? Or when building your own server, just adding app.get("/user/:id") will do all the magic itself?

The simple answer is NO. We usually never think much about routing and how it works, but its one of the major factors that affect the performance of a framework and a server.

😮‍💨 The Normal Approach

The simplest way we all think first when asked about how to implement routing is to use a basic for loop.
1️⃣ Store the routes in an array.
2️⃣ When a request is made, search for that route in the array using a for loop.
3️⃣ If the route is found, the corresponding logic is executed.

The problem? Speed.
Imagine a huge server with 1000+ routes. Then, to search for a specific route using this approach, what is the time required? O(n), n being the number of routes, i.e. 1000 here. That's a huge blow to the performance.

🚀 The Better Approach

You may be wondering, what should be done then? The answer lies in a magical little data structure, Trie.

A trie is basically a tree, which stores strings character-by-character, branching out whenever required (see image for better understanding). This reduces unnecessary comparisons, and you can just follow the path in the trie and find the matching path.

The time complexity? Just a mere O(s), s being the length of route. So, if "/users" is the URL, s is 6. No matter how many thousands of routes exist in the server, this approach only thinks about the route that is being requested, significantly reducing the time taken and enhancing performance.

🔥 The Even Better Approach

Now, is there any way to make this approach even more performant? The answer is to use a HashMap.

The trie is still going to store every route as it used to store earlier, character-by-character. However, this seems inefficient too, as most routes that get requested to a server are usually just static sites ("/users", "/dashboard" etc).

So, we use a hashmap here. While storing the routes, we get all the static parts (words) of the route (ex 'dashboard' and 'home' in "/home/dashboard") and store them in the hashmap as keys. Their values will store the ending node of the trie where these static words end.

When a request comes in, we first check if each part is static or dynamic. If its static, we instantly look in the hashmap first. If found, we get at which node of the trie it ends, and start searching from there again.

This updated approach helps in jumping through the static words stored in the trie and only check for dynamic parts (like 'id' in "/user/:id").

Since most requested routes contain static routes, this approach improves performance significantly. Although the time complexity is still O(s) theoretically, in practice, most routes, especially ones with just static parts, get searched in just O(1).

So What's The Takeaway?

Routing isn't just about matching URLs to functions—it directly impacts server performance.

❌ A simple for loop works, but it doesn’t scale well.
✅ A Trie speeds things up, as lookup time depends only on route length.
🚀 Combining it with a HashMap makes it even more efficient, allowing many static routes to be matched in near O(1) time.

Many modern frameworks use optimized routing techniques under the hood, but knowing how they work gives you the power to build faster, more scalable applications. So, the next time you write app.get("/user/:id") you'll know the real magic behind it 😉

For more informative stuff, follow me on LinkedIn and Twitter.