Trie's are my favorite data structure. The implementation in the Linux kernel is a lock free RCU structure (http://lxr.free-electrons.com/source/lib/radix-tree.c). It is used for the page cache among other things.