著者

本田 喜久 川島 英之 今井 倫太 安西 祐一郎

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会技術研究報告. DE, データ工学 (ISSN:09135685)

巻号頁・発行日

vol.102, no.207, pp.49-54, 2002-07-10

---

近年,キャッシュを意識して探索を高速化するメモリ索引構造が提案されている.中でも,1999年に提案されたFull Cache Sensitive Search Tree(CSS-tree)は,探索時間がデータサイズによってはハッシュよりも短く,また索引構造のために必要なメモリ空間使用量がB-treeよりも少ない点で優れている.他方,更新処理が遅いため,CSS-treeが有用であるのはオンライン解析処理のように更新処理が極めて少ない状況に限られると言われている.しかし,更新処理を追加処理のみに限定すれば,索引構造の再構築時間を減らすことができる.そこで本研究では,追加処理のみが発生する状況において,CSS-treeへの挿入処理を高速化する手法を提案する.提案手法は,(1)配列とCSS-treeのノードの拡張に要するコストを減らすために,あらかじめ余分な索引構造領域を獲得しておき,(2)配列とCSS-treeの葉ノードの再マップに要するコストを減らすために,CSS-treeの葉ノードの領域をなくし,CSS-treeの内部ノードのスロットに,配列のキー値を格納する.提案手法の有効性を評価するために,C言語とアセンブラを用いて,SunOS 5.6上に実験用データベースシステムを実装し,挿入処理時間を測定した.実験の結果,提案手法は,更新処理を追加処理に限定しない再構築手法と比べて,最大で7.18倍速くなることがわかった.