radix 树路由表的设计原理

trie树是字符串算法里很常见的一种数据结构。用于存储多个串。它本质上是一个自动机。又叫字典树。如果用trie树存储一个词典，要查找某个词是否在字典里，理论上是可以获得O（n）的复杂度的，而空间开销上，理论上也不会超过各个串长度之和，甚至要小于它们的长度之和。