radix tire

对于长整型数据的映射。怎样解决Hash冲突和Hash表大小的设计是一个非常头疼的问题。
radix树就是针对这样的稀疏的长整型数据查找，能高速且节省空间地完毕映射。借助于Radix树，我们能够实现对于长整型数据类型的路由。
利用radix树能够依据一个长整型（比方一个长ID）高速查找到其相应的对象指针。这比用hash映射来的简单，也更节省空间，使用hash映射hash函数难以设计，不恰当的hash函数可能增大冲突，或浪费空间。

radix tree是一种多叉搜索树。树的叶子结点是实际的数据条目。每一个结点有一个固定的、2^n指针指向子结点（每一个指针称为槽slot，n为划分的基的大小）

插入、删除

radix Tree(基数树) 事实上就几乎相同是传统的二叉树。仅仅是在寻找方式上。利用比方一个unsigned int的类型的每个比特位作为树节点的推断。

能够这样说，比方一个数1000101010101010010101010010101010，那么依照Radix 树的插入就是在根节点，假设遇到0。就指向左节点。假设遇到1就指向右节点，在插入过程中构造树节点，在删除过程中删除树节点。假设认为太多的调用Malloc的话，能够採用池化技术。预先分配多个节点。
（使用一个比特位推断。会使树的高度过高，非叶节点过多。故在实际应用中，我们通常是使用多个比特位作为树节点的推断，但多比特位会使节点的子节点槽变多。增大节点的体积，一般选用2个或4个比特位作为树节点就可以）

插入：

我们在插入一个新节点时，我们依据数据的比特位，在树中向下查找，若没有对应结点，则生成对应结点，直到数据的比特位訪问完，则建立叶节点映射对应的对象。

删除：

我们能够“惰性删除”，即沿着路径查找到叶节点后，直接删除叶节点，中间的非叶节点不删除。

应用

Radix树在Linux中的应用：

Linux基数树（radix tree）是将long整数键值与指针相关联的机制，它存储有效率。而且可高速查询，用于整数值与指针的映射（如：IDR机制）、内存管理等。
IDR（ID Radix）机制是将对象的身份鉴别号整数值ID与对象指针建立关联表。完毕从ID与指针之间的相互转换。
IDR机制使用radix树状结构作为由id进行索引获取指针的稀疏数组，通过使用位图能够高速分配新的ID，IDR机制避免了使用固定尺寸的数组存放指针。IDR机制的API函数在lib/idr.c中实现。

Linux radix树最广泛的用途是用于内存管理。结构address_space通过radix树跟踪绑定到地址映射上的核心页，该radix树同意内存管理代码高速查找标识为dirty或writeback的页。
其使用的是数据类型unsigned long的固定长度输入的版本号。每级代表了输入空间固定位数。Linux radix树的API函数在lib/radix-tree.c中实现。（把页指针和描写叙述页状态的结构映射起来。使能高速查询一个页的信息。）

Linux内核利用radix树在文件内偏移高速定位文件缓存页。
Linux(2.6.7) 内核中的分叉为 64(2^6)。树高为 6(64位系统)或者 11(32位系统)，用来高速定位 32 位或者 64 位偏移，radix tree 中的每个叶子节点指向文件内相应偏移所相应的Cache项。

【radix树为稀疏树提供了有效的存储，取代固定尺寸数组提供了键值到指针的高速查找。】

后记
Radix树与Trie树的思想有点类似。甚至能够把Trie树看为一个基为26的Radix树。

（也能够把Radix树看做是Tire树的变异）
Trie树一般用于字符串到对象的映射。Radix树一般用于长整数到对象的映射。

trie树主要问题是树的层高。假设要索引的字的拼音非常长非常变态，我们也要建一个非常高非常变态的树么？
radix树能固定层高（对于较长的字符串，能够用数学公式计算出其特征值，再用radix树存储这些特征值）

Trie Tree以及它的衍生优化版Radix Tree。

相比较于字典集的存储方式，Trie Tree将key以树型结构构造，有什么用意呢？一个最大的帮助是公共的前缀被共享了，这样可以避免被重复地存储了。而在普通的字典集结构中，这种重复key前缀都是独立被包含在每个key内的。假设当字典集中所存储的key都带有大量重复的前缀时，Trie Tree将会消耗比普通字典结构更少的空间。
按照树的查询方式，一个查询key长度m，首先我们会将key拆分成m个字符，然后对应每个长度，从根节点依次向下，总共会进行到m次查找。因此我们可以得出，它的查询时间复杂度为O(m)，随着查询key长度的增加，它所消耗的时间将会线性增长。

往深层面来看查询时间的问题，其实本质上这是树的深度引起的问题，对于长key而言，它的key对应的节点构造的深度过深。那么如果说我们将这“棵”树构造得更紧凑一些，会如何呢？于是我们有了另外一个衍生版本树：Radix Tree（基数树）。
Radix Tree名为基数树，它的计数统计原理和Trie Tree极为相似，一个最大的区别点在于它不是按照每个字符长度做节点拆分，而是可以以1个或多个字符叠加作为一个分支。这就避免了长字符key会分出深度很深的节点。

针对Radix Tree的构造规则，它的节点插入和删除行为相比较于Trie Tree来说，略有不同。

对于节点插入而言，当有新的key进来，需要拆分原有公共前缀分支。
对于节点删除而言，当删除一个现有key后，发现其父节点只有另外一个子节点key，则此子节点可以和父节点合并为一个新的节点，以此减少树的比较深度。

的确Trie Tree、Radix Tree在某些应用场景可以帮助我们节省内存使用空间，但是它们也有其使用的局限性。比如这类树结构无法适用于所有的数据类型，目前来看主要适用于能够用string字符等可作为表达式查询key的场景