在Linux内核里面有很多很多的库和函数，形成了很多数据结构和算法，今天研究一种数据结构，也就是基数树，有两个文件lib/radix-tree.c和include/linux/radix-tree.h可以实现。
工具/原料
1
计算机
2
虚拟机
方法/步骤
1
首先介绍一下基数树，是一种二进制的压缩的字典树，深度是32位，主要应用在ip查找上面，是一种以关联数组接口的数据结构，字典树的节点存储单个字符的标签，Linux 内核中的基数树是把值映射到整形键的一种数据结构。
2
要建立基数树就需要从结构上下手，先结构初始化，然后进行RADIX_TREE 宏，传递name的参数，通过RADIX_TREE 宏定义和初始化基数树的名称。
3
在RADIX_TREE 宏进行之前，需要给定义的名称再一次定义，定义为radix_tree_root的结构体实例，用mask去调用函数，使用RADIX_TREE_INIT 宏对定义的结构体实例进行初始化。
4
或者进行手动定义结构体实例，这里把结构体定义为radix_tree_root，利用如图的代码实现，定义之后把它和mask一起上传给INIT_RADIX_TREE 宏。
5
其实在一刚开始就应该先定义INIT_RADIX_TREE 宏，但是最后定义可以修改，提前定义修改比较麻烦，还是将INIT_RADIX_TREE 宏进行初始化，代码实现如图。
6
最后进行建立基数的根和引键，需要两个函数radix_tree_lookup和radix_tree_lookup_slot，一个在树中查找给定的键，一个起到返回包含数据的指针，返回的是记录的个数。 results 中的结果，按键排序，并从第一个索引开始。返回的记录个数将不会超过max_items 的值。
下一篇：数据结构二叉树的遍历