radixtree

Compressed trie with O(key-length) lookups and no allocation for reads Link to heading

For more information see radixtree at github

radixtree implements a radix tree, also known as a compressed trie or compact prefix tree. Use it to look up values by key, find values whose keys share a common prefix, or find values whose keys lie along the path to a given key.

Why I created this project Link to heading

I needed a trie for searching for sets items that had common prefixes, like Geohash and OID data. I wanted something that would compress paths that had no branches, and of course I wanted something fast and efficient. Other implementations had APIs that were more cumbersome than I needed or performance issues that would take more than a simple change to improve. So, I wrote my own and benchmarked it against many others, so that I had what I was looking for.