(For the record, the reason why I have stared at this as much as I have just now is because I study these kinds of data structures and therefore want to understand what is new and compelling about this specific one.)

So, tries have the property of being only as balanced as the distribution of their alphabets. It is very easy to end up in a situation where worst case performance of a trie is linear in the number of items in the trie. There are some researchers who were doing work on a concept called "stratified indexes" that allow you to index into deeply skew'd tries that you may find interesting.

Regardless, the claims in this article are somewhat off. For example: they state that red-black trees "write out a lot of memory". Any full binary tree with N leaf nodes has N-1 non-leaf nodes. That statement is just as true of red-black trees as it is of this data structure. It is definitely true that the STL red-black tree implementation is inefficient (allocating memory for empty nodes), but that should not be held against the algorithm.

The documentation is even weirder. "Unlike either red-black trees or most hash tables, nedtries can store as many items with identical keys as you like." That is certainly not true, and isn't even true of the STL, which has a red-black tree without unique restriction called std::multimap.

The documentation also claims that hashtables can store arbitrarily large keys and nedtries can't, which is only as true of hashtables as it is for nedtries. As hashtables aren't ordered, and in fact require fixed-length keys, you can (and do: normally this statement would be going in the other direction of causality) use hash algorithms to hash the information to fit into the key length and then verify the value when you find it. The same thing could be used for nedtries.

I'm also having a difficult time understanding why red-black trees are not an "in place algorithm" and nedtries are. I'm not even certain I understand what it would mean for a search tree to be "in place", but the documentation makes claims about "dynamic memory allocation" being its key distinction, and I see no reason why a red-black tree need require that for search or deletion. Insert requires a single allocation, but so does a trie; and, even with the STL most people use a custom pool allocator for that purpose.

To be clear, I am not at all stating that "nedtries aren't faster than other implementations", just that that has nothing to do with their algorithm. The algorithm seems to just be an array of tries, where the array is designed to help with the common case of "there are a large number of zeros at the top of the key" (caused by using small numbers as keys).

Unfortunately, that makes the distribution among the bin-level tries drastically uneven, making that first "which bucket do I end up in" question severely unfairly unbalanced.

That specific optimization, then, doesn't seem to offer anything over a patricia trie, which itself would dramatically decrease the number of non-leaf node traversals (as nedtries does not describe using any kind of path compression at all). These path-compressed tries are what people normally use for high-performance lookup like routing.