| 講演名 | 2002/7/10 CSS-treeの挿入処理の高速化 本田 喜久, 川島 英之, 今井 倫太, 安西 祐一郎, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | 近年,キャッシュを意識して探索を高速化するメモリ索引構造が提案されている.中でも,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倍速くなることがわかった. |
| 抄録(英) | In recent years, memory index structures that accelerate search speed utilizing the structure of CPU cache have proposed. Especially, the Full Cache Sensitive Search Tree (CSS-tree) proposed in 1999 is faster than hash depending on data size and require smaller amount of space than B-tree. On the other hand, reconstructing the CSS-tree is so slow that it has been considered that the CSS-tree is only useful under static environments such as OLAP. However, if updating is limited only to additional insertions, the reconstruction cost can be dramatically decreased. Then, in this research, we propose the new techniques that accelerate insertion processing to the C-SS-tree. The technique consists of (1) preliminary acquiring excess index structure space to reduce cost for node expanding and (2) omitting leaf nodes to reduce cost for remapping the leaf nodes and instead, storing key value into internal nodes. To evaluate the proposed technique, we implemented an experimental system with C language and assemblers on SunOS 5.6 and measured the insertion time and the size of memory space for the structure. The result showed that the proposed technique accelerates 7.18 times faster than original technique. |
| キーワード(和) | CSS-tree / データベースシステム / メモリ索引構造 / キャッシュメモリ |
| キーワード(英) | CSS-tree / database System / memory index structure / cache memory |
| 資料番号 | DE2002-20 |
| 発行日 |
| 研究会情報 | |
| 研究会 | DE |
|---|---|
| 開催期間 | 2002/7/10(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Data Engineering (DE) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | CSS-treeの挿入処理の高速化 |
| サブタイトル（和） | |
| タイトル（英） | Accelerating insertion processing to the CSS-tree |
| サブタイトル（和） | |
| キーワード(1)（和/英） | CSS-tree / CSS-tree |
| キーワード(2)（和/英） | データベースシステム / database System |
| キーワード(3)（和/英） | メモリ索引構造 / memory index structure |
| キーワード(4)（和/英） | キャッシュメモリ / cache memory |
| 第 1 著者 氏名（和/英） | 本田 喜久 / Yoshihisa HONDA |
| 第 1 著者 所属（和/英） | 慶應義塾大学大学院 理工学研究科 Graduate School of Science and Technology, Keio University |
| 第 2 著者 氏名（和/英） | 川島 英之 / Hideyuki KAWASHIMA |
| 第 2 著者 所属（和/英） | 慶應義塾大学大学院 理工学研究科 Graduate School of Science and Technology, Keio University |
| 第 3 著者 氏名（和/英） | 今井 倫太 / Michita IMAI |
| 第 3 著者 所属（和/英） | 慶應義塾大学大学院 理工学部 Faculty of Science and Technology, keio University |
| 第 4 著者 氏名（和/英） | 安西 祐一郎 / Yuichiro ANZAI |
| 第 4 著者 所属（和/英） | 慶應義塾大学大学院 理工学部 Faculty of Science and Technology, keio University |
| 発表年月日 | 2002/7/10 |
| 資料番号 | DE2002-20 |
| 巻番号（vol） | vol.102 |
| 号番号（no） | 207 |
| ページ範囲 | pp.- |
| ページ数 | 6 |
| 発行日 | |