2.1 Treeの管理データ

Radix Treeの管理の大元のデータとしてstruct radix_tree_rootがある。このデータはRadix Tree関連関数でどのTreeに対して操作を行うのか指定するのに使われる。

このデータのrnodeがルートノード(Treeトップのノード)を指している。heightはTreeの高さを表しており、例えばheight=1だと、ルートノードのみの1段のTreeであることを意味する。

2.2 Treeのノード

Treeの各ノードはstruct radix_tree_nodeが使われる。

この構造体にはslots[]配列があり、子ノードへのポインタを保持している。末端のノードの場合はslots[]は検索対象のオブジェクト(item)へのポインタを格納している(*1)。子ノードやitemが無い場合はslots[]の該当要素にはNULLが格納されている。現状slots配列は64エントリ存在し、Radix Treeは64分木を構成することになる。

countフィールドは、そのノードに子がいくついるかを示すカウンタ。つまり、slots[]に有効なポインタがいくつ格納しているかを表している。

(*1) ページキャッシュのRadix Treeの場合は、itemはstruct pageになる。

2.3 検索キー

LinuxのRadix Treeでは検索キー(index)は32bit値に限定されている。

検索キーは図1に示すようにRADIX_TREE_MAP_SHIFT(6) bit毎に区切られる。

検索キーの区切られた部分の値がTree各段のノードのslots[]のインデクスとなり、Treeを下っていくことができる(*2)。

なお、6bit区切りだと端数がでるので、検索キーの上位は2bitのみになる。このため、図1では1段目でも64分岐するように描いているが、実際には4分岐しかしない。