正如你所知道的， Linux 内核通过许多不同库以及函数提供各种数据结构以及算法。这个部分我们将介绍其中一个数据结构 Radix tree。Linux 内核中有两个文件与 radix tree 的实现和 API 相关：
　　include/linux/radix-tree.h
　　lib/radix-tree.c
　　首先说明一下什么是 radix tree ，Radix tree 是一个 压缩 trie， trie 是一种通过保存关联数组（associative array）来提供 关键字-值（key-value） 存储与查找的数据结构。通常关键字是字符串，不过也可以是其他数据类型。 Trie 结构的节点与 n-tree 不同，其节点中并不存储关键字，取而代之的是存储单个字符标签。关键字查找时，通过从树的根开始遍历关键字相关的所有字符标签节点，直至到达终的叶子节点。下面是个例子：

　　这个例子中，我们可以看到 trie 所存储的关键字信息 go 与 cat，压缩 trie 或 radix tree 与 trie 所不同的是，对于只有一个孩子的中间节点将被压缩。
　　Linux 内核中的 Radix 树将值映射为整型关键字，Radix 的数据结构定义在 include/linux/radix-tree.h 文件中 :
　　struct radix_tree_root {
　　unsigned int            height;
　　gfp_t                   gfp_mask;
　　struct radix_tree_node  __rcu *rnode;
　　};
　　上面这个是 radix 树的 root 节点的结构体，它包括三个成员：
　　height：从叶节点向上计算出的树高度。
　　gfp_mask：内存申请的标识。
　　rnode：子节点指针。
　　这里首先要讨论的结构体成员是 gfp_mask :
　　Linux 底层的内存申请接口需要提供一类标识（flag） – gfp_mask ，用于描述内存申请的行为。这个以 GFP_ 前缀开头的内存申请控制标识主要包括，GFP_NOIO 禁止所有 IO 操作但允许睡眠等待内存，__GFP_HIGHMEM 允许申请内核的高端内存，GFP_ATOMIC 高优先级申请内存且操作不允许被睡眠。
　　接下来说的节结构体成员是 rnode：
　　struct radix_tree_node {
　　unsigned int    path;
　　unsigned int    count;
　　union {
　　struct {
　　struct radix_tree_node *parent;
　　void *private_data;
　　};
　　struct rcu_head rcu_head;
　　};
　　/* For tree user */
　　struct list_head private_list;
　　void __rcu      *slots[RADIX_TREE_MAP_SIZE];
　　unsigned long   tags[RADIX_TREE_MAX_TAGS][RADIX_TREE_TAG_LONGS];
　　};
　　这个结构体中包括这几个内容，节点与父节点的偏移以及到树底端的高度、子节点的个数、节点的存储数据域，具体描述如下：
　　path：与父节点的偏移以及到树底端的高度
　　count：子节点的个数。
　　parent：父节点的指针。
　　private_data：存储数据内容缓冲区。
　　rcu_head：用于节点释放的 RCU 链表。
　　private_list – 存储数据。
　　结构体 radix_tree_node 的后两个成员 tags 与 slots 是非常重要且需要特别注意的。每个 Radix 树节点都可以包括一个指向存储数据指针的 slots 集合，空闲 slots 的指针指向 NULL。 Linux 内核的 Radix 树结构体中还包含用于记录节点存储状态的标签 tags 成员，标签通过位设置指示 Radix 树的数据存储状态。
　　至此，我们了解到 radix 树的结构，接下来看一下 radix 树所提供的 API。