LPC-trie

最近看linux代码中，FIB(Forward Information Base)信息维护的相关内容的时候，由于看得代码比较早，发现其在维护IP路由信息的时候有两种实现方式，一种是较为传统的HASH方式，即将IP地址信息做hash运算，然后维护到不同地址长度的hash表中。这种方式是内核早期使用的一种方式，这种方式的额缺点就是在遇到特殊情况，即HASH key值一样的情况下，hash查找退化为单链表查找，降低IP包转发速度。所以在新的内核中这部分已经被取代，换为使用trie树来实现信息维护。

传统的trie树很好理解，就是在节点中记录信息，从跟节点遍历到此节点所经过的路径，就是此节点代表的内容。一般trie树常用于字符串的处理，这样拥有同样父节点的子节点则是拥有同样的字符串前缀。

由于IP地址信息化为2进制后，是一种特殊的字符串，只有0，1两种字符。另外字符串有最大的长度。IPv4中是32
，IPv6中则是128位。所以可以使用trie树可以用来维护IP地址信息。

使用传统的trie来维护信息有两个缺点。1.大量中间造成内存资源的浪费；2.大量的中间节点造成查找路径变长。为了解决上述两方面带来的问题，linux内核中使用了LPC-trie树解决。

首先LPC-trie树是PC-trie其中C代表压缩，因为在传统的trie树中会有大量的中间节点存在，其目的只是为了辅助构成有意义节点的前缀。由此可以使用简单的路径压缩，将可以共享的中间几级节点变为一个节点，一个节点不再是只简单的代表或者0，或者1，而是可以代表一段连续的字符串，如"101"。这在传统的trie树中要是用三层节点，使得每次查询就会多三次比较。

当然仅有路径压缩还不能称之为LPC，除了路径压缩外，LPC还采用了L(level)压缩技术。这个也很简单，很容易理解，就是将原来只会有两个孩子节点的中间节点变为会有多个孩子节点的中间节点，为2的幂个数。这样做的好处是能够降低查询时候的比较次数，同时还不会因此内存的增长，当然使用level压缩技术是在原始中间节点中非空节点的数据足够多的情况下，否则无意义，还会造成内存浪费，以2的幂增加，还是很恐怖的。

LPC-trie在维护数据结构树需要进行相应的调整。这也利用了0，1字符串2进制的特性，其中节点有加倍和减半操作，加倍操作就是指将原来中间节点的孩子节点数目增加一辈，然后调整整个LPC-trie，减半操作就是将中间节点的孩子节点数目减少一半（8到4）.
通常情况下，加倍是在非空节点达到一定阈值时触发，而减半操作则是在空节点高到一定阈值时触发。

通过LPC-trie树能够维护路由表信息，从而使得IP转发快速、高效。

后续如果有时间会分析linux内核在此部分的具体实现方式。


另外：LPC-trie跟radix树同属与trie树，但是radix一般更加通用，而LPC-trie只是用于只有0，1字符构成的字符串。