radix tree

这个tree是一种很有趣的tree，我以前都没见过这种树。在linux中，它的非叶节点是一种radix_tree_node结构，叶节点是一个page结构。radix_tree_node包含一个64长度的数组，用来存放叶节点或者非叶节点。每个被插入的page，都有一个index，用来标识这个page应该被插入的位置。比如当这棵树只有一层的时候，根据index的值，将page插入64数组的index位置就可以了（这时index要小于64）。在某个时刻，这棵树可以接受的最大index为pow(2,6*height)。page 的index在树中是这样解释的，index的二进制表示的最高6个有效位，标明在第一层数组中位置。接下来的6个有效位标明下一层的数组位置，以此下去。在linux中标明第一层的是最高有效位的前2位，因为现在是32位的地址。

2009年 03月 02日 星期一 10:03:20 CST