radix tree

PATRICIA - "Practical Algorithm To Retrieve Information Coded In Alphanumeric"
Radix Tree gives fastest possible ways to search prefixes.
With radix tree every internal node has at least two children.

radix trees are useful:
1. for constructing associative arrays with keys expressed as strings.
2. in the area of IP routing.
3. inverted indexes of text documents in information retrieval.
4. to map between real and virtual IRQ numbers.
5. in the memory management code, to quickly find pages which are dirty.



reference:
http://en.wikipedia.org/wiki/Radix_tree
http://lwn.net/Articles/175432
http://code.google.com/p/radixtree