情報処理学会 第84回全国大会 会期:2022年3月3日~5日 情報処理学会 第84回全国大会 会期:2022年3月3日~5日

2N-03
Bw木およびBz木における範囲走査性能の評価
○平野匠真,杉浦健人,石川佳治,陸 可鏡(名大)
B+木をロックフリー化した索引構造としてBw木およびBz木が提案されている.
Bw木はB-link木に基づき全ての兄弟ノードが単方向リンクを持つ一方,Bz木は親ノードから子ノードへの単方向リンクしか持たない.
そのため,Bz木では葉ノードをまたぐ範囲走査において次の葉ノードを根ノードから読み直す必要があるが,
Bz木の提案論文では範囲走査についてBw木を超える性能が得られたと示されている.
しかし,提案論文では短い範囲走査しか行われておらず,葉ノードをまたいでいない可能性がある.
そこで,本論文では兄弟リンクを持つBw木と持たないBz木における範囲走査をより網羅的に検証し,
それぞれの索引構造が範囲走査に与える影響を再評価する.