原创 Linux中idr_tree算法描述

       Idr_tree是内核提供的一种算法，其实现了整型id号与一个内核指针之间的映射。Idr_tree算法的实现采用了radix_tree的思想，其数据结构定义与radix tree有着类似之处。Idr_tree在2003年的时候引入至内核，目前在scsi盘符空间的管理、i<?xml:namespace prefix = st1 ns = "urn:schemas-microsoft-com:office:smarttags" />2c总线设备号与设备结构之间的映射方面都有应用。

       在整型id与内存指针之间的映射可以采用数组的方式，但是随着存储规模的增大，数组的方式显然不能满足应用的需求；另一种方式可以采用链表进行映射信息的管理，同样不能管理较大的映射资源。所以，在Linux中采用树进行映射资源的管理。这种树就是idr_tree。

<?xml:namespace prefix = o ns = "urn:schemas-microsoft-com:office:office" />

采用idr_tree来管理整型id与内存指针之间的映射关系具有如下两方面对优势：

1、  具有很好的映射关系查找效率。

2、  能够很好的扩展存储规模，动态增大树的规模对查找性能影响不是很大。

       Idr_tree的结构示意图描述如下图所示：

       Idr_tree的叶子节点用于存储用户定义的数据，通常用于存储用户需要查找的内存指针。树中的每个节点定义为idr_layer，该数据结构中包含了一个bitmap位图，用于描述下层节点的属性。当下层节点不存在空穴（空闲节点）时，上层节点bitmap位图中的对应位置位。因此在查找过程中，从顶层节点开始，判断每个节点的bitmap信息，然后遍历第一个bit位为0的下层节点，直到遍历到叶子节点为止。由此可见，Idr_tree的算法复杂度与树的层次数量相关。Idr_tree是动态生成的，随着叶子节点的增多，树的层次将会不断增大。

    Linux中带中文注释的idr实现源码https://static.assets-stash.eet-china.com/album/old-resources/2009/4/2/50103c41-c090-4854-9458-148c3e9f144c.rar