Boost Node.js Routing Performance with Trie Prefix Trees

Background

The author previously built a Node.js web framework and needed an efficient routing system, which led to using a prefix‑tree (Trie) for fast route lookup.

What is a Prefix Tree?

A Trie (also called a dictionary tree) stores strings as a hierarchy of character nodes, sharing common prefixes to reduce query time.

Key properties:

The root node holds no character; every other node holds a single character.

The path from the root to a node spells the string represented by that node.

Sibling nodes never contain the same character.

Routing Scenarios

Routes are URL paths without protocol, domain, or port, split by “/”. Many routes share a common prefix, e.g., /api/user/list and /api/user/create share /api/user, which makes a Trie suitable for storing them.

Applying the Trie to Routing

Each component of a route (the strings between slashes) becomes a node in the Trie. The tree stores components rather than single characters, and leaf nodes hold the handler for the route.

Inserting a Route into the Trie

Code example showing addToTree implementation.

addToTree(urlPattern: string, handler: any) {
    let p = this.root;
    // Padding an element to the rear of the array to make the leaf node.
    const urlPatternComponents = [...urlPattern.split('/').filter(Boolean), LEAF_SIGN];

    urlPatternComponents.forEach(component => {
      const { quickMap } = p;

      // If quickMap has this component, it means the route has the same namespace
      // with existed route, so get to the next level directly. If the node is a leaf
      // node, just return cause it means redundant route is adding to the tree, we dont need it.
      if (p.quickMap.has(component as string)) {
        const node = p.quickMap.get(component as string)!;
        if (isLeafNode(node)) {
          return;
        }
        p = node;
        return;
      }

      if (component === LEAF_SIGN) {
        const newNode = new RouterTreeLeafNode(handler);
        quickMap.set(LEAF_SIGN, newNode);
        return;
      }

      const newNode = new NTreeNode(component as string);
      p.quickMap.set(component as string, newNode);
      // When the expression like ':id' shows in the route, it should
      // treat it as a parameter node. One tree node can only have one parameter node.
      if ((component as string).indexOf(':') > -1) {
        p.paramNode = newNode;
      }
      p = newNode;
    });
}

Static Route Matching

During a request, the URL is split into components and traversed from the root. If each component matches a child node, the traversal continues until a leaf node is reached, returning its handler. If a component cannot be matched, a “Route not found” error is thrown.

getHandlerFromTree(url: string): any{
    const [urlWithParams, _] = url.split('?');
    const urlComponents = urlWithParams.split('/').filter(Boolean);
    let p = this.root;
    let i = 0;
    let res;
    let path = '';
    while (p) {
      const component = urlComponents[i ++];

      // If the quickMap has the component, return it if it's also a leaf node.
      // Or just move to the next level and store the path.
      if (p.quickMap.has(component)) {
        const node = p.quickMap.get(component)!;
        if (isLeafNode(node)) {
          res = node.value;
          break;
        }
        path += '/' + node.value;
        p = node;
        continue;
      }

      const leafNode = p.quickMap.get(LEAF_SIGN);

      if (leafNode == null) {
        // If quickMap has other node, it means static route cannot be matched.
        if (p.quickMap.size > 0) {
          const err = { message: 'Route not defined', statusCode: 404, statusMessage: 'Not found' };
          throw err;
        }

        // Else it means no handler was defined.
        const err = { message: 'Handler not defined', statusCode: 500, statusMessage: 'Not found' };
        throw err;
      }

      res = leafNode.value;
      break;
    }

    return {
      handler: res,
      path
    };
}

Dynamic Route Matching

Dynamic segments like /api/user/:id are stored in a special paramNode. When a static match fails, the router falls back to the parameter node, treating the unmatched component as the dynamic value.

if (p.quickMap.has(component)) {
    const node = p.quickMap.get(component)!;
    if (isLeafNode(node)) {
      res = node.value;
      break;
    }
    path += '/' + node.value;
    p = node;
    continue;
}
if (component) {
    path += '/' + p.paramNode.value;
    p = p.paramNode;
    continue;
}

Regular‑Expression Matching

Routes expressed as regular expressions are kept under the root to avoid interfering with the Trie structure. If no parameter node is available, the router attempts regex matching.

if (component) {
    // If no parameter node found, try regular expression matching.
    if (!p.paramNode) {
        const { handler, matched } = this.getHandlerFromRegExpNode(url);
        res = handler;
        path = matched;
        break;
    }
    path += '/' + p.paramNode.value;
    p = p.paramNode;
    continue;
}

addRegExpToTree(urlPattern: RegExp, handler: Function) {
    const root = this.root;

    root.children.push(new RouterRegExpLeafNode(urlPattern, handler));
}

Analysis

Using a Trie balances space and lookup speed: common prefixes are shared, reducing memory usage similar to gzip compression. The worst‑case lookup time is linear in the depth of the tree. However, if routes have few shared prefixes, the Trie can approach O(m·n) space, so developers should aim to group routes under common namespaces.

Conclusion

Compared with a plain hash table for static routes and brute‑force traversal for dynamic routes, a Trie offers a middle ground that leverages shared prefixes while supporting static, dynamic, and regex matching efficiently.