The CIDR trie data structure

Also see “poptrie” [0] for an efficient way to do routing table-style lookups for CIDRs (longest prefix match). They basically use the “popcnt trick” to implement sparse arrays, use “direct indexing” for the first however many bits to reduce the number of indirections, and have a cool optimization specific to longest prefix match (“hole punching” in the paper).

[0]: https://dl.acm.org/doi/10.1145/2829988.2787474

I've never really groked tries, so bad for me. But I've built a few IP lookup tables.

For one, I only needed to know a true/false given an ipv4 address (does geolocation of the ip indicate within a specific set of countries), and the lookup needed to be fast and easy.

If you look at every address, a simple boolean array will be too big, 2^29 bytes with 2^3 values per byte covers the address space, but half a gig of memory is too much. Otoh, geolocation by country is unlikely to be more specific than a /24, 2^21 bytes with 2^3 values per byte is only 2 meg of memory devoted to a very fast lookup; less in actual use if you mmap without large pages, because parts of the range will never page in.

That approach isn't great if your value is larger than a boolean or you need ipv6 (you can use /48s as your maximum prefix length, but there's quite a lot of /48s).

If you want a compact table, you can store an ordered set of (low ip, value), and access the table by finding the nearest value equal or less than the observed ip. I used Erlang's ets with ordered set and the ets:prev(Table, IP + 1) which uses a binary tree under the hood, but anything that can handle 128 bit integer should work.

Building the table is a bit of work, because you've got to take inputs of like X.Y.0.0/16 -> A and then X.Y.6.0/24 -> B and turn that into X.Y.0.0 -> A, X.Y.6.0 -> B, X.Y.7.0 -> A ... but all that transformation happens offline.

I think you're more likely to have a language built in for a binary tree than a trie, but some languages have neither.

I ended up using the same basic layout for the database behind a little IP lookup tool I wrote to make lookups somewhat responsive from JavaScript [1]. It ends up working out pretty well.

[1] https://cloud-ips.s3-us-west-2.amazonaws.com/index.html

In networking, these are known as Patricia trees, a special case of the Radix tree/trie.