Inside Gin's Radix Tree: How Route Matching Works with Zero Allocations

The radix tree in tree.go is the reason Gin exists. Forked from Julien Schmidt's httprouter—still credited in the file's copyright header—this data structure is what makes Gin one of the fastest Go web frameworks. It compresses common path prefixes into shared edges, matches routes without heap allocations, and reorders children by access frequency. This article dissects the tree node by node, traces how routes are inserted and looked up, and explains the performance tricks that keep allocations at zero on the hot path.

The Radix Tree Data Structure

A radix tree (also called a Patricia trie or compact prefix tree) compresses chains of single-child nodes into single edges. Where a standard trie would have one node per character, a radix tree stores the entire shared prefix as a single edge label. For HTTP routing, this means /api/users and /api/orders share the edge /api/, with children users and orders branching from there.

The node struct at tree.go#L99-L108 is compact:

type node struct {
    path      string
    indices   string
    wildChild bool
    nType     nodeType
    priority  uint32
    children  []*node
    handlers  HandlersChain
    fullPath  string
}

Each field serves a specific purpose:

Field	Purpose
path	The compressed edge label (e.g., /api/ or users)
indices	One character per child—the first byte of each child's path, concatenated into a string for fast lookup
wildChild	Whether this node has a :param or *catchAll child
nType	One of static, root, param, or catchAll
priority	Access frequency counter, used to reorder children
children	Child nodes; wildcard children are always last
handlers	The HandlersChain registered at this path (nil for intermediate nodes)
fullPath	The complete original route path, used for debugging

The four node types defined at tree.go#L90-L97 represent:

• static: Regular path segments
• root: The tree root (one per HTTP method)
• param: A :name wildcard capturing a single path segment
• catchAll: A *name wildcard capturing everything after it

graph TD
    ROOT["/ (root)<br/>path='/'<br/>indices='au'"]
    API["api/<br/>nType=static"]
    USERS["users<br/>handlers=✓"]
    ORDERS["orders/<br/>indices=':'"]
    PARAM[":id<br/>nType=param<br/>handlers=✓"]
    ABOUT["about<br/>handlers=✓"]

    ROOT --> API
    ROOT --> ABOUT
    API --> USERS
    API --> ORDERS
    ORDERS --> PARAM

    style ROOT fill:#e1f5fe
    style PARAM fill:#fff3e0

The indices string is a clever optimization. Instead of iterating all children to find a match, the router checks the first byte of the remaining path against the indices string. For a node with children users and orders, the indices string would be "uo". This turns child dispatch into a single-character comparison loop.

Route Registration: addRoute() and Edge Splitting

The addRoute() method at tree.go#L135-L249 is where the tree takes shape. It walks the existing tree, character by character, until the new route diverges from existing routes. At that point, it may need to split an existing edge.

Consider inserting /api/users into a tree that already has /api/orders. The tree currently has an edge with path /api/orders. The new path shares the prefix /api/, so addRoute() splits the edge:

flowchart TD
    subgraph "Before: Single route"
        A1["root<br/>path='/api/orders'<br/>handlers=✓"]
    end

    subgraph "After: Edge split"
        B1["root<br/>path='/api/'<br/>indices='ou'"]
        B2["orders<br/>handlers=✓"]
        B3["users<br/>handlers=✓"]
        B1 --> B2
        B1 --> B3
    end

    A1 -.->|"Insert /api/users"| B1

The splitting logic at lines 156–175 creates a new child node with the remainder of the original edge, copies over the original node's properties, and truncates the current node to the common prefix:

// Split edge
if i < len(n.path) {
    child := node{
        path:      n.path[i:],      // remainder: "orders"
        wildChild: n.wildChild,
        indices:   n.indices,
        children:  n.children,
        handlers:  n.handlers,       // move handlers to child
        priority:  n.priority - 1,
        fullPath:  n.fullPath,
    }
    n.children = []*node{&child}
    n.indices = bytesconv.BytesToString([]byte{n.path[i]})
    n.path = path[:i]               // truncate to "/api/"
    n.handlers = nil                 // parent has no handlers
}

Wildcard parameters add complexity. When addRoute() encounters a : or * in the path, it delegates to insertChild() at tree.go#L288-L397, which creates param or catchAll nodes. Wildcard conflicts are detected eagerly—you can't register both /users/:id and /users/:name because they'd be ambiguous.

The Engine wraps this tree-level insertion at gin.go#L364-L386, tracking maxParams and maxSections for pre-allocation:

func (engine *Engine) addRoute(method, path string, handlers HandlersChain) {
    root := engine.trees.get(method)
    if root == nil {
        root = new(node)
        root.fullPath = "/"
        engine.trees = append(engine.trees, methodTree{method: method, root: root})
    }
    root.addRoute(path, handlers)

    if paramsCount := countParams(path); paramsCount > engine.maxParams {
        engine.maxParams = paramsCount
    }
    if sectionsCount := countSections(path); sectionsCount > engine.maxSections {
        engine.maxSections = sectionsCount
    }
}

Tip: If you ever see a panic like "conflicts with existing wildcard" during startup, it means you've registered routes with conflicting parameter names at the same path position. Gin detects these at registration time, not at request time.

Route Lookup: The Zero-Allocation getValue() Hot Path

The getValue() method at tree.go#L418-L599 is the most performance-critical function in the entire framework. It's called on every HTTP request and must find the matching handler chain without allocating memory on the heap.

The method signature reveals the zero-allocation strategy:

func (n *node) getValue(path string, params *Params, skippedNodes *[]skippedNode, unescape bool) (value nodeValue)

Both params and skippedNodes are pointers to pre-allocated slices. They're created once per Context in allocateContext() and reused across requests. The key insight is that by passing a pointer to a slice (not a slice directly), the function can append to the slice's backing array without the slice header escaping to the heap.

sequenceDiagram
    participant S as ServeHTTP
    participant H as handleHTTPRequest
    participant T as tree.getValue()
    participant N as node walk loop

    S->>H: handleHTTPRequest(c)
    H->>H: Linear scan method trees
    H->>T: root.getValue(path, c.params, c.skippedNodes, unescape)
    loop Walk tree
        N->>N: Compare path prefix with n.path
        N->>N: Check indices for child dispatch
        alt Wildcard child
            N->>N: Save skippedNode for backtracking
        end
        alt Param node
            N->>N: Extract param value, append to *params
            Note over N: No heap allocation—<br/>grows within pre-allocated capacity
        end
    end
    T-->>H: nodeValue{handlers, params, fullPath}
    H->>H: c.handlers = value.handlers
    H->>H: c.Next()

The parameter saving logic at tree.go#L498-L522 carefully avoids allocation:

if params != nil {
    if cap(*params) < int(globalParamsCount) {
        newParams := make(Params, len(*params), globalParamsCount)
        copy(newParams, *params)
        *params = newParams
    }
    if value.params == nil {
        value.params = params
    }
    i := len(*value.params)
    *value.params = (*value.params)[:i+1]  // grow within capacity
    (*value.params)[i] = Param{Key: n.path[1:], Value: val}
}

Because maxParams was tracked during route registration and the Params slice was pre-allocated to that capacity in allocateContext(), the cap(*params) < int(globalParamsCount) check almost never triggers. The slice grows within its existing capacity, which means no heap allocation.

The skippedNodes slice handles a subtle problem: when a static route and a wildcard route could both match, the tree tries the static route first (via indices dispatch) but saves a "bookmark" in case it doesn't lead to a match. If the static path fails, the tree backtracks to the wildcard. This is visible in the backtracking loop at lines 459–473.

Priority Reordering and Performance Tricks

Gin doesn't just store children in insertion order—it reorders them by access frequency. The incrementChildPrio() method at tree.go#L111-L131 increments a child's priority counter and bubbles it toward the front of the children slice:

func (n *node) incrementChildPrio(pos int) int {
    cs := n.children
    cs[pos].priority++
    prio := cs[pos].priority

    newPos := pos
    for ; newPos > 0 && cs[newPos-1].priority < prio; newPos-- {
        cs[newPos-1], cs[newPos] = cs[newPos], cs[newPos-1]
    }

    if newPos != pos {
        n.indices = n.indices[:newPos] +
            n.indices[pos:pos+1] +
            n.indices[newPos:pos] + n.indices[pos+1:]
    }
    return newPos
}

This is called during route registration, not during request handling. Routes registered first or more frequently accessed routes bubble to the front, where the linear scan in getValue() finds them faster. The indices string is rearranged in sync with the children slice.

flowchart LR
    subgraph "Method Trees (slice, not map)"
        GET["GET → root"]
        POST["POST → root"]
        PUT["PUT → root"]
        DEL["DELETE → root"]
        DOT["... (≤9 total)"]
    end

    subgraph "Per-method tree"
        ROOT2["root<br/>indices='uao'<br/>(ordered by priority)"]
        U["users/ (prio=150)"]
        A["api/ (prio=80)"]
        O["orders/ (prio=30)"]
        ROOT2 --> U
        ROOT2 --> A
        ROOT2 --> O
    end

The per-method trees themselves are stored as a slice of at most 9 entries at tree.go#L45-L59, not a map[string]*node. This is a conscious performance choice: for 9 or fewer entries, a linear scan beats a map hash. The map would need to hash the method string, handle bucket lookup, and deal with potential cache misses. A linear scan over 9 elements fits in a cache line.

Tip: If you're benchmarking routes, remember that the first child in the indices string is checked first. Routes registered earlier or with higher priority (more sub-routes) get matched faster. In practice, this means your most common routes are naturally optimized.

Special Cases: Escaped Colons, Redirects, and 405 Handling

Escaped Colons

Normally, : starts a parameter wildcard. But what if you need a literal colon in a route path? Gin supports \: as an escape sequence. During registration, the escaped colon is preserved in the tree. Then, on the first request, updateRouteTree() at gin.go#L504-L521 recursively walks the tree and replaces \: with ::

func updateRouteTree(n *node) {
    n.path = strings.ReplaceAll(n.path, escapedColon, colon)
    n.fullPath = strings.ReplaceAll(n.fullPath, escapedColon, colon)
    n.indices = strings.ReplaceAll(n.indices, backslash, colon)
    for _, child := range n.children {
        updateRouteTree(child)
    }
}

This replacement is wrapped in a sync.Once in ServeHTTP(), so it happens exactly once and doesn't affect the request hot path.

Trailing Slash Redirects

When Engine.RedirectTrailingSlash is true (the default), a request to /users that doesn't match but where /users/ has a handler will trigger a 301 redirect (for GET) or 307 redirect (for other methods). The tsr (trailing slash redirect) field in nodeValue signals this condition, and handleHTTPRequest() checks it after a failed match.

Method Not Allowed (405)

When HandleMethodNotAllowed is enabled, and a route isn't found for the requested method, Gin scans all other method trees looking for a matching path. If found, it returns 405 with an Allow header listing the valid methods—compliant with RFC 7231 §6.5.5. This scan at gin.go#L738-L756 is intentionally opt-in because it adds overhead to 404 responses.

flowchart TD
    MATCH{Route matched?}
    MATCH -->|Yes| EXEC[Execute handlers]
    MATCH -->|No| TSR{TSR available?}
    TSR -->|Yes| REDIR[301/307 Redirect]
    TSR -->|No| FIXED{RedirectFixedPath?}
    FIXED -->|Yes, match found| REDIR2[301/307 Redirect]
    FIXED -->|No| METHOD{HandleMethodNotAllowed?}
    METHOD -->|Yes| SCAN[Scan all other method trees]
    SCAN -->|Methods found| RESP405["405 + Allow header"]
    SCAN -->|None| RESP404[404 Not Found]
    METHOD -->|No| RESP404

What's Next

We've now seen how routes are stored and looked up. In the next article, we'll explore the object that getValue() returns its results into: the Context struct. At 1,489 lines, it's Gin's Swiss Army knife—handling flow control, response writing, parameter access, metadata storage, error accumulation, and even implementing Go's context.Context interface. We'll trace its lifecycle from pool allocation through middleware execution to recycling.