Redis has a beautiful Radix Tree implementation in ANSI C.
This brings it to Rust and creates a safe Map like wrapper
for it. This is very similar in utility to a BTreeMap, but
RAX is likely much faster and more efficient. Naive testing
showed a 2x-4x improvement for all common operations. The only
disadvantage to BTreeMap is that BTree’s allow much more flexibility
in regards to comparing keys. Radix trees are lexicographically only.
Composite keys where the non-last member is variable length could
be something BTrees could handle much easier.
Same as RaxMap except values are not pointers to heap allocations.
Instead the “data pointer” in the RAX is the value. This means we
have sizeof worth of bytes to play with. Perhaps, in the future
we could create data values of any size, but for now we have the size
of pointers to work with or null which has no added size to a rax node.
Rax internally makes calls to “malloc”, “realloc” and “free” for all of it’s
heap memory needs. These calls can be patched with the supplied hooks.
Do not call this method after Rax has been used at all. This must
be called before using or calling any other Rax API function.