numtrie

numtrie is a generic digit-indexed trie for numeric keys, with O(k) longest-prefix lookup and vanity letter folding, allocating nothing on the read path.

-
Updated:

Table of contents

Part of nurago, a collection of independent Go packages for backend services.

import "github.com/tecnickcom/nurago/pkg/numtrie"

A prefix tree indexed by digits, holding a value of any type, answering longest-prefix queries.

root := numtrie.New[Route]()
root.Add("1",     &defaultUSRoute)
root.Add("1212",  &newYorkRoute)
root.Add("44",    &ukRoute)
root.Add("44207", &londonRoute)

val, status := root.Get("+1-212-555-0100")
// val == &newYorkRoute, the longest matching prefix "1212"

Longest-prefix, which a map cannot do

A map[string]Route answers exact-match questions. Numbering plans are not exact-match problems.

+1 is North America, +1212 is New York, and a lookup on a full number has to find the most specific prefix that matches, not the whole number and not the shortest prefix. Prefix lengths vary with no rule you can apply in advance, so you cannot try a fixed set of substring lengths either.

Walking the digits and remembering the deepest node that carried a value is what a trie does naturally, in O(k) for a key of k digits, independent of how many prefixes are stored. A million routing entries costs the same lookup as ten.

The same shape appears in IP routing tables, dial plans, and any hierarchical numeric classification. countryphone is built on this.

Build once, read many

Operationns/opB/opallocs/op
Add (building a table)86,220106,9481,114
Get (longest prefix)28.700
GetExact19.700

Measured with go test -bench on Go 1.27.1, linux/amd64, Intel Core i7-1260P. Run go test -bench=. ./pkg/numtrie/ to reproduce them on your own hardware; the absolute values will differ, the ratios much less so.

The read path allocates nothing. No intermediate strings, no slices, no boxing: the walk is pointer traversal over a pre-built structure, so it adds no garbage collection pressure however often it runs.

Construction allocates, as it must, since it builds the nodes. Build the trie once at startup and treat it as read-only afterwards, which also makes it safe to share across goroutines without a lock.

GetExact is about a third cheaper than Get because it stops at the first mismatch instead of tracking the best match seen so far.

Vanity letters fold to digits

Keys may contain alphabetic characters, folded to their ITU E.161 keypad digits through phonekeypad. 1-800-FLOWERS and 18003569377 reach the same node.

Separators are dropped rather than rejected, so input can be passed in whatever form it arrived: +1 (212) 555-0100, +1-212-555-0100, or the bare digits.

The status return

Get returns a value and a status. The status separates three outcomes that a single nil cannot:

  • an exact match on the full key
  • a partial match, where a shorter prefix carried a value
  • no match at all

For a routing table, a partial match is a usable answer and a non-match is an error, so collapsing them would lose the distinction.

Values are stored as supplied and returned as supplied. The trie holds your pointer rather than copying, so a large value costs one pointer per node.

Digits only

The index is digit-based: ten children per node, addressed 0 to 9. Alphabetic input is folded into that space rather than extending it, so two letters on the same key are indistinguishable after folding. FLOWERS and any other word mapping to 3569377 reach the same node.

That is correct for dial plans, where the keypad mapping is the point, and it means this is a numeric trie rather than a general string trie.

Dependencies

This package reaches no external module: it uses only the Go standard library, plus phonekeypad for letter folding.