配列を用いたキャッシュコンシャスな索引木の提案

概要

論文の詳細を見る
近年の研究において,キャッシュコンシャスな索引構造は優れた性能を示している.キャッシュコンシャスな索引木における重要な考えは,ノードからのポインタの削除にある.ポインタを削除することにより,ノードが持つ子ノードの数は増加し木の高さは低くなる.その結果として効果的なキャッシュの利用が可能となる.本稿では,キャッシュコンシャスな索引木「Array-Based Cache conscious trees」(ABC木)を提案する.ABC木では,木構造を完全木として配列により表現する.この索引木の構造や操作方法はB^+木に類似しているが,B^+木のように子ノードへのポインタを格納しない.ノード間の相対的な位置関係を計算することで目的のノードを得る.また,その高さの完全木を構築するのに必要となる領域をあらかじめ確保しノード間の位置関係を保つことで更新処理にも柔軟に対応する.そのため,ノードのオーバーフローやアンダーフローが発生した場合のコストも比較的低くなる.
社団法人情報処理学会の論文
2002-07-17