下载文档原格式
Trie树路由查找算法在网络处理器中的实现张琦;金胤丞;李苗;章建雄【期刊名称】《计算机工程》【年(卷),期】2014(000)001【摘要】Trie tree data structure is flexible to realize and require small storage space, and it is the preferred to realize high speed routing lookup and packet forwarding. In order to meet the design requirements of micro engine of 10 Gb/s line speed in Network Processor(NP), an optimal balance, multilayer storage routing lookup algorithm based on Trie tree is proposed. That is to establish a balanced compression tree structure, then the adjacent multi nodes are compressed to a storage node. It constructs a specific tree structure to reduce the tree search depth, exchanging space for time, improving the efficiency of lookup and packet forwarding. Router lookup algorithm based on Trie tree is implemented in NP design, and the algorithm performance is analyzed. A single micro engine lookup speed is up to 4.4 Mb/s, and it has an advantage of small storage and high update speed.%Trie树数据结构的实现方法灵活，所需存储器空间小，是实现高速路由查找和分组转发的理想选择。
Trie树在IP地址匹配中的应用Trie树是一种特殊的树状数据结构，用于高效地存储和搜索字符串。
它在很多应用领域中发挥着重要的作用，其中包括IP地址匹配。
本文将探讨Trie树在IP地址匹配中的应用，并介绍其原理和实现方式。
IP地址是计算机网络中用于唯一标识主机的一串数字。
IPv4地址由32位组成，而IPv6地址由128位组成。
在网络设备处理数据包时，常需要根据目标IP地址进行匹配，以确定下一步的路由或操作。
传统的IP地址匹配方法有两种：前缀匹配和精确匹配。
前缀匹配是指在一组IP地址中，找到与给定IP地址前缀最长匹配的规则；而精确匹配则是指在所有IP地址中精确匹配给定的IP地址。
为了能够高效地进行IP地址匹配，Trie树提供了一种有效的解决方案。
Trie树，也称为前缀树，是一种多叉树结构，每个节点代表一个字符。
Trie树的根节点为空，其他节点的子节点代表这个字符可能出现的下一个字符。
例如，我们可以用一个简单的Trie树来存储一些单词，如"apple"、"app"、"apricot"和"banana"：```root/ \a b/ \ \p b a/ / \p a n/ / \l n a/ \e n```在IP地址匹配中，Trie树的每个节点表示IP地址的一级字节，从根节点到叶子节点的路径就是一个IP地址的前缀。
Trie树的每个节点都可以包含额外的信息，如存储与该前缀匹配的规则或其他相关数据。
使用Trie树进行IP地址匹配的过程如下：1. 根据已有的IP地址和对应的规则，构建Trie树。
2. 收到一个待匹配的IP地址。
3. 从Trie树的根节点开始，依次匹配IP地址的每个字节。
如果找到一个匹配的子节点，则继续向下匹配；如果遇到空节点或没有匹配的子节点，则停止匹配。
4. 当完成IP地址的匹配时，可以获取与该IP地址匹配的规则或其他相关数据。
昆明学院2012届毕业设计（论文）设计（论文）题目基于Hash和Trie树的IPv6高速查找和快速增量更新路由算法设计与实现子课题题目姓名刘晓青学号 20081101420所属系信息技术学院专业年级08级计算机科学与技术指导教师何英2012年5月摘要由于Internet的速度不断提高、网络流量不断增加和网络规模不断扩大，使得路由器成为制约Internet性能的主要瓶颈之一。
随着路由器技术的发展，路由查找速度依然是进一步提高路由器性能的关键要素。
本论文首先研究了各种经典的IPv6路由查找算法，并分析了各种路由查找算法的复杂度和存在的问题，对IPv4向IPv6过度的路由查找算法的存在的问题以及路由查找算法的性能参数和复杂度，给出了一种基于hash和trie树高速查找和快速增量更新路由查找算法；其次，对路由缓存优化策略进行改进，并就路由节点进行生物智能化处理，使得路由负载平衡得到改善；最后，通过仿真实验，得出该算法优于以往算法。
关键字：路由查找；最长前缀匹配；Hash表；Trie树；生物智能AbstractWith the development of the internet,the increasing of throughput and the expanding of network,making the router becomes the one of the main bottleneck restricting the internet performance.With the development of routing technology,the speed of the routing lookup is still a key element to further improvement of router performance.This paper studied various classic IPv6 routing lookup algorithms firstly, then analysis the complexity of the various routing lookup algorithms and some existing problems,find the exiting problems in routing lookup algorithms from IPv4 to IPv6 and the performance parameters and complexity of routing lookup algorithms,i served a high speed lookup and fast incremental update routing lookup algorithms based on hash and trie tree;Secondly,i have been done for route cache optimization strategies improvement and conducted route nodal biological intelligent,make the routing load balancing improving;Finally,via the simulation experiment,i know that this algorithm is better than before.Keywords :Route lookup；Longest prefix match；Hash table；Tire；Biological intelligence；目录第一章绪论 (1)1.1 研究背景及现状 (1)1.2 本文研究内容、意义、价值 (1)第二章相关技术概述 (2)第三章 HT6路由查找算法的实现 (4)3.1算法设计 (4)3.1.1HT6算法基本思想 (4)3.1.2数据结构设计 (5)3.1.3 HT6查找设计 (8)3.1.4路由更新 (11)3.2算法改进 (13)3.2.1缓存优化 (13)3.2.2生物智能节点 (17)第四章模拟仿真及实验数据分析 (23)4.1仿真环境搭建 (23)4.2算法仿真及分析 (24)第五章总结与展望 (26)5.1全文总结 (26)5.2研究展望 (26)参考文献 (27)致谢 (28)第一章绪论1.1 研究背景及现状互联网在人类生活中扮演着重要的角色。
trie树查找和hash查找⽐较（⼤量数据）trie树代码#include<iostream>#include<stdio.h>#include<iostream>#include<string>#include<stdlib.h>#include<fstream>#include<sstream>#include<vector>#include<string>#include<time.h>using namespace std;class trienode{public:char *word;int count;trienode *branch[26];public:trienode(){word = NULL;count = 0;//词频memset(branch, NULL, sizeof(trienode*) * 26);}};class trie{public:trienode *root;public:trie();~trie();void Insert(char *str);bool Search(char*str, int &count);//索引void printall(trienode *root);//字符排序void printpre(char *str);//前缀匹配};trie::trie(){root = new trienode();}trie::~trie() {}void trie::Insert(char *str){int index;trienode *tt = root;for (int i = 0; str[i]; i++){index = str[i] - 'a';if (index < 0 || index>26){return;}if (tt->branch[index] == NULL){tt->branch[index] = new trienode();}tt = tt->branch[index];}if (tt->word){tt->count++;return;}else{tt->count++;tt->word = new char[strlen(str) + 1];strcpy_s(tt->word, strlen(str) + 1, str);}}bool trie::Search(char *str, int &count){int index = -1;trienode *tt = root;while (tt&&*str){index = *str - 'a';if (index < 0 || index>26) return false;tt = tt->branch[index];str++;}if (tt&&tt->word){count = tt->count;return true;}return false;}void trie::printall(trienode *root){trienode *t = root;if (!t) return;if (t->word){cout << t->word << endl;}for (int i = 0; i < 26; i++){printall(t->branch[i]);}}void trie::printpre(char *str){trienode *t = root;int index = -1;while (t&&*str){index = *str - 'a';if (index < 0 || index>26) return;t = t->branch[index];str++;}if (t){printall(t);}}int main(){clock_t startTime, endTime;startTime = clock();trie *t = new trie();ifstream it("C:/Users/ww/Desktop/string.txt");string sline;string str = "";while (it&&getline(it, sline)){str += sline + "";}it.close();for (int i = 0; i < str.length(); i++){if (str[i] == '.' || str[i] == ',' || str[i] == '(' || str[i] == '(') {str.erase(i, 1);}}string word;stringstream ss(str);vector<string> vec;while (ss >> word){vec.push_back(word);}vector<string>::iterator iter;for (iter = vec.begin(); iter != vec.end(); iter++){t->Insert((char*)(*iter).data());}int val = -1;if (t->Search("the", val)){cout << val << endl;}else{cout << "empty" << endl;}endTime = clock();cout << "the running time is " << (double)(endTime - startTime) << endl; return0;}hash代码#include<iostream>#include<fstream>#include<sstream>#include<string>#include<vector>#include<stdlib.h>#include<time.h>using namespace std;class hashnode{public:char *p;hashnode *next;};class hashmap{public:hashnode *hashps[1000];public:hashmap();~hashmap();int String2Int(char *p);void Insert(char *p);bool Find(char *p);};hashmap::hashmap(){for (int i = 0; i < 1000; i++){hashps[i] = new hashnode();}for (int i = 0; i < 1000; i++){hashps[i]->next = NULL;}}hashmap::~hashmap() {}int hashmap::String2Int(char *p){int num = 0;while (*p){num += *p;p++;}return num % 1000;}void hashmap::Insert(char *p){int index = String2Int(p);hashnode *hash = hashps[index];hashnode *newr = new hashnode();newr->p = new char[strlen(p) + 1];strcpy_s(newr->p, strlen(p) + 1, p);newr->next = hash->next;hash->next = newr;}bool hashmap::Find(char *p){int index = String2Int(p);hashnode *t = hashps[index]->next;if (!t){return false;}else{hashnode *w = t;while (w){if (strcmp(p, w->p)==0){return true;}w = w->next;}}}int re(int *p){return *p;}int main(){clock_t startTime, endTime;startTime = clock();hashmap *t = new hashmap();ifstream it("C:/Users/ww/Desktop/string.txt");string sline;string str = "";while (it&&getline(it, sline)){str += sline + "";}it.close();for (int i = 0; i < str.length(); i++){if (str[i] == '.' || str[i] == ',' || str[i] == '(' || str[i] == '('){str.erase(i, 1);}}stringstream ss(str);string word;vector<string> vec;while (ss >> word){vec.push_back(word);}vector<string>::iterator iter;for (iter = vec.begin(); iter != vec.end(); iter++){t->Insert((char*)(*iter).data());}cout << "the result is: " << t->Find("the") << endl;endTime = clock();cout << "the running time is " << (double)(endTime - startTime) << endl;return0;}trie树查找时间是O(L)L是字符串长度，⽽hash是O(LL)，LL是关键字对应哈希地址链表长度,都和数据的⼤⼩⽆关，查找都很⾼效。
什么是Internet路由--常见路由相关知识全解在当今高度互联的信息时代，互联网已经成为了人们生活中不可或缺的一部分。
而作为互联网的基础设施，Internet路由在其中担当着至关重要的角色。
本文将全面解析什么是Internet路由以及相关的常见路由知识，为读者提供更深入的了解。
一、什么是Internet路由Internet路由是指将网络中的数据包从源主机传输到目标主机的过程，这个过程涉及到在网络中选择最佳路径的决策。
在互联网中，数据被划分成小的数据包，通过特定的路由协议在网络中进行传输。
这个过程是由路由器完成的，而路由器则是互联网中扮演重要角色的网络设备。
在Internet路由中，路由器通过比较目标主机的IP地址，以及其它的相关信息，来决定数据包传输的最佳路径。
这个最佳路径是根据当前网络的拓扑情况和路由器的路由表等信息来决定的。
二、路由器的基本工作原理1. 路由器的分类路由器可以按照其功能和应用场景的不同进行分类。
根据规模和使用环境的不同，可以将路由器分为家庭路由器、企业级路由器和互联网骨干路由器等。
不同类型的路由器具有不同的特点和性能指标，以满足不同需求的网络环境。
2. 路由器的工作原理路由器的工作原理可以简单概括为以下几个步骤：（1）接收数据包：路由器通过接收数据包来进行后续的处理。
数据包中包含了目标主机的IP地址等关键信息。
（2）查找路由表：路由器会根据目标主机的IP地址来查找自己的路由表，以确定下一跳路由器和传输路径。
（3）转发数据包：路由器根据路由表的查找结果，将数据包转发给下一跳路由器，直到最终到达目标主机。
（4）更新路由表：路由器会定期更新自己的路由表，以适应网络拓扑的变化和路由器之间的通信。
三、常见的路由协议在Internet路由中，存在着一些常见的路由协议，用于路由器之间的通信和路由表的更新。
以下是一些常见的路由协议：1. RIP（Routing Information Protocol）：RIP是一种基于距离向量的内部网关协议，常用于小型网络中。
路由器中的硬件IP路由表查找技术Internet的迅速开展给我们的生活带来了宏大的变化。
随之而来的是网络流量的迅速增长。
网络流量的增长对于Internet上的路由器来说是一个很大的挑战，特别是核心路由器。
它需要高速有效的包调度.转发和路由策略。
本文针对路由器的路由查找，提出了一种高效的.便于用硬件实现的技术。
1. 路由器的体系构造图1给出了一般路由器的逻辑体系构造。
它主要由下面几部分组成：路由引擎、转发引擎、路由表、网络适配器和相关的逻辑电路等。
转发引擎负责把从一个网络适配器来的数据包转发到另一个网络适配器出去。
IP协议，包括对路由表的查找，构成了转发引擎中最主要的部分。
由于每个通过路由器并需要其转发的数据包都要对路由表进展查找，所以路由表的查找效率如何往往决定了整个路由器的性能。
路由引擎那么包括了高层协议，特别是路由协议，它负责对路由表的更新。
由于路由引擎不涉及通过路由器的数据通路，故它可用通用的CPU代替。
2．硬件路由表的数据构造设计一般路由器中路由表的每一项至少有这样的信息：目的地址、网络隐码、下一跳地址。
假设对每一个IP地址都要一个表项，那么需要占用很大的2323*4字节的存储器，而且其中必定有很多的表项没有被使用，这就会造成极大的资源浪费。
为了用硬件实现路由表的查找，查找算法需要满足如下的条件：1〕实时的实现路由表的查找；2〕有效的实现路由表的插入和删除；3〕提供有效的最长前缀匹配；4〕具有良好的可扩展性；5〕支持播送和组播；6〕有效的对Memory进展利用；7〕硬件上容易实现，并具有良好的性能。
我们考虑，假设在对路由表的查找中，把子网隐码和IP地址结合起来，对IP地址进展相应的分段，并把它们相连。
这样在路由表的表项中，只有IP地址的一部分及其相应的隐码部分，可以实现良好的可扩展性，只要对Memory进展有效的管理，可以灵敏的动态的实现对路由的插入和删除。
鉴于此，我们设计该表的构造〔如下面的表一所示〕：它的思想是：把32位IPv4地址主要分成4部分，每部分8位。
Internet路由之路由表查找算法概述-哈希/LC-Trie树/256-way-mtrie 树引：路由是互联网的一个核心概念，广义的讲，它使分组交换网的每个节点彼此独立，通过路由耦合在一起，甚至在电路交换网中，虚电路的建立也依赖路由，路由就是网络中数据通路的指向标。
狭义的讲，路由专指IP路由，它支撑着整个IP网络。
由于IP是数据报网络，它是不建立连接的，因此IP分组是一跳一跳被转发，通路是通过路由信息一跳一跳的被打通的，因此路由直接关系到整个基于IP的网络的连通性。
由于IP协议没有方向，甚至它都没有会话的概念，因此路由必然要是双向的，否则数据就有去无回了(有人提倡用NAT来解决反向路由问题，实际上NAT在公共核心网络上口碑十分不咋地，它甚至破坏了IP协议的原则，记住，NAT一般只用于端点)。
互联网如此之大，每个路由器上的路由信息会非常之多，路由器是怎么在海量的路由信息中用最快的速度-显然很重要-检索出自己需要的呢？另外如此海量的路由信息又是怎么生成的呢？本文着重回答第一个问题，关于第二个问题请参考《Internet路由结构(第二版)》(Cisco Press,想看就赶快买，不买就买不到了，Cisco有几本书真的很火爆，总是不好买)1 .基本概念路由的概念：路由是一种指向标，因为网络是一跳一跳往前推进的，因此在每一跳都要有一系列的指向标。
实际上不仅仅是分组交换网需要路由，电路交换网在创建虚电路的时候也需要路由，更实际的例子，我们日常生活中，路由无处不在。
简单的说，路由由三元素组成：目标地址，掩码，下一跳。
注意，路由项中其实没有输出端口-它是链路层概念，Linux操作系统将路由表和转发表混为一谈，而实际上它们应该是分开的(分开的好处之一使得MPLS更容易实现)。
路由项通过两种途径加入内核，一种是通过用户态路由协议进程或者用户静态配置配置加入，另一种是主机自动发现的路由。
所谓自动发现的路由实际上是“发现了一个路由项和一个转发表”，其含义在主机某一个网卡启动的时候生效，比如eth0启动，那么系统生成下列路由表项/转发项：往eth0同一IP网段的包通过eth0发出。
路由表：路由表包含了一系列的表项，包括上述的三元素。
路由框架的层次：路由大致分为两个要素，也可以看成两个层次。
第一个层次是路由表项的生成；第二个层次是主机对路由表项的查找。
路由表项生成算法：生成路由表项的方式有两种，第一种是管理员手工配置，第二种为通过路由协议动态生成。
路由查找算法：本文着重于主机层面上对路由表项的查询算法。
毕竟这是一个纯技术活儿...相反的，路由协议的实现和配置更讲究人为的策略，如果你人为配置RIP或者OSPF只需要配几条命令就OK了，那么配一个BGP试试，它讲究大量的策略，不是纯技术能解决的。
如果有时间，我会单独写一篇文章谈路由协议的，但是今天，只谈路由器/主机对路由表项的查找过程。
这个过程很重要，如果路由器的查找算法效率提高了，那么很显然，端到端的延迟就降低了，这是一定的。
2.Linux 的哈希查找算法这是Linux操作系统的经典的路由查找算法，直到现在还是默认的路由查找算法。
然而它很简单。
由于它的简单性，内核(kernel)开发组一直很推崇它，虽然它有这样那样的局限性，但由于Linux内核的哲学就是“够用即可”，因为Linux几乎从来不被用于专业的核心网络路由系统，因此哈希查找法一直都是默认的选择。
2.1 .查找过程查找顺序如下图所示：为了实现最长前缀匹配，从最长的掩码开始匹配，每一个掩码都有一个哈希表，目的IP 地址哈希到这些哈希表的特定的桶中，然后遍历其冲突链表得到最终结果。
注意，哈希查找算法是基于掩码的遍历来实现严格的最长前缀匹配的，也就是说如果一条最终将要通过默认网关发出的数据报，它起码要匹配32次才能得到结果。
这种方式十分类似于传统的Netfilter 的filter 表的过滤方式-一个一个尝试匹配，而不像HiPac 的过滤方式，是基于查找的。
接下来我们会看到，高性能的路由器在查找路由的时候使用的都是基于查找型数据结构的方式，最常用的就是查找树了。
2.2 .局限性我们知道，哈希算法的可扩展性一直都是一个问题，一个特定的哈希函数只适合一定数量的匹配项，几乎很难找到一个通用的哈希函数，能够适应从几个匹配项到几千万个匹配项的情形，一般而言，随着匹配项的增加，哈希碰撞也会随着增加，并且其时间复杂性不可控，这是一个很大的问题，这个问题阻止了哈希路由查找算法走向核心专用路由器，限制了Linux路由的规模，它根本不可能使用哈希来应对大型互联网络或者BGP之类的域间路由协议产生的大量路由信息。
核心路由器上，使用哈希算法无疑是不妥的，必定需要找到一种算法，使得其查找的时间复杂度限制在一个范围(我们不关心空间复杂度，这和端到端用户的体验没有关系，只和他们花的钱多少有关，花10万买的路由器有4G内存，花100万买的路由器则支持64G内存...)。
我们知道，基于树的查找算法可以做到这一点，实际上，很多的路由器都是使用基于树的查找算法来实现的。
我们先从Linux的trie树开始。
便于查阅代码(虽然本文不分析代码...)。
3.Linux的LC-Trie 树查找算法trie算法分为三大块，第一块是查找，第二块是插入/删除，第三块是平衡。
我们首先先不管其名称为何这么叫，也不必非要去深入理解一下Trie树的概念，直接实践就是了。
虽然很多的教科书都喜欢最后讲查找型数据结构的插入，而我这里却要先说插入，因为一旦你明白了插入，查找就不言自明了，另外，讲完插入之后，接下来我要说的是trie树的平衡以及多路操作，因为这样的话，最终的查找才会变得高效。
我们权当高效的查找操作是一个必然结果吧。
3.1 .基本理论很不好意思，这里没什么理论，一切都很简单。
我们可以通过电话号码来认识trie树，trie树本质上是一棵检索树，和全球电话号码簿一样，我们知道，电话号码有三部分组成：国家码+地区号+号码，比如086+372+5912345，如果从美国拨出这个号码，首先要决定送往哪个国家，所要做的就是用确定位数的国家码和出口交换机的转发表的国家码部分进行匹配，发现086正好是中国，然后该号码到达中国后，再匹配区号，发现要送往安阳市，最后到达安阳市，然后将请求发往5912345这个号码。
现在的问题是，在每一个环节如何使用最快的方式检索到请求下一步要发往哪里？我想最好的方式就是使用“桶算法”，举个例子，在美国的电话请求出口处放置一张表，表项有X个，其中X代表全球所有国家和地区的总和，中国的国家码是086，那么它就是第86个表项，这样直接取第86个表项，得到相应的交换信息，电话请求通过信息中指示的链路发往中国...另外一个例子就是计算机的页表，这个我们在3.3节再谈。
trie树，其实和上述的结构差不多，只不过上述结构的检索分段是固定的，比如电话号码就是3位10进制数字等，且匹配检测索引的位置也是固定的，比如电话号码的地区号就是从第4位十进制数字开始等。
对于trie树而言，需要检测的位置不是固定的，它用pos表示，而检测索引的长度也不固定，它由bits表示，我们把每一个检测点定为一个CheckNode，它的结构体如下：CheckNode{int pos;int bits;Node children[1<<bits];}union Node{Leaf entry;CheckNode node;}图解如下：可见pos 和bits 是一个CheckNode 的核心，pos 指示从哪一位开始检测，bits 指示了孩子结点数组，直接取key[pos...pos+bits]即可直接取到孩子结点。
3.2.trie 树的插入我以为，研究一种树型结构的时候，首先理解其插入算法无疑是最好的，然而很多的教科书都是从检索开始，然后将插入操作一笔带过，这是很不妥的。
我认为只要把插入操作理解深刻了，接下来的查询和删除就很简单了，毕竟插入是第一步！插入虽然重要，但是想学习的人不要认为它很难，要知道，只要是人想出的东西，理解它们都不会很难，难的是什么？难的是你不会首先想不出来！插入应该怎么进行呢？：第一步，如果一个CheckNode节点都没有，则创建根CheckNode节点，并且创建一个叶子，结束。
注意，每一个路由项都是一片叶子。
如果已经有了根CheckNode，则需要计算新节点插入的位置。
第二步，计算插入位置前的位置匹配。
步骤如下：根据已有CheckNode的pos/bits信息，从根开始执行一系列比较：1).取出根CheckNode2).设当前CheckNode为PreCheckNode3).判断是否需要继续匹配。
4).如果需要继续匹配，则看看自己是其哪个孩子或者该孩子的分支，并且取出该孩子Child-CheckNode为当前CheckNode，回到2。
5).如果不需要继续匹配，退出匹配过程其中判断CheckNode是否需要继续匹配其Child-CheckNode的算法如下：NewKey和CheckNode在上述的蓝色虚线区域内只要有不同的bit，则不必再和Child-CheckNode继续匹配了，可以确定，NewKey肯定插入后作为PreCheckNode的某个孩子了。
如果需要继续匹配，判断是哪个孩子的方式如下：第三步，确定插入位置并且插入，步骤如下：0).如果没有发生第二步中的和Child-CheckNode不匹配的情形，则直接将NewKey作为叶子作为PreCheckNode的第NewKey[PreCheckNode的pos...PreCheckNode的pos+PreCheckNode 的bits]插入，结束。
否则执行下面的步骤，处理和Child-CheckNode的冲突1).创建一个CheckNode，然后看下图：假设上图中的绿色圈起来的位是Child-CheckNode和NewKey首次不匹配的地方，记为miss，那么NewKey将创建一个新的CheckNode，记为NewNode，其POS为miss，其bits为1，这样原来的Child-CheckNode就成了NewNode的一个孩子，而待插入的NewKey创建一个新的叶子，作为NewNode的另一个孩子。
NewNode代替Child-CheckNode作为PreCheckNode的孩子插入其孩子数组中。
第四步，完毕基本上，上述的过程已经很清楚了，然而给出一个例子会更好些，接下来我给出一个例子，依次插入3条路由项：1:192.168.10.0/242:192.168.20.0/243:2.232.20.0/24然后我们看图说话，首先看一下比特图：接下来看一下插入trie的情形：3.3.trie 平衡以及多路trie如果仅仅看3.2节所论述的内容，我们发现trie 不过是一棵二叉查找树而已，这又有何好说的呢？然而作为路由表结构的trie 却远不止这么简单。
