情報処理学会第85回全国大会 会期:2023年3月2日~4日 会場:電気通信大学

1N-04
Bw木におけるマルチスレッドでの構造変更操作に関する性能評価
○平野匠真,杉浦健人,石川佳治,陸 可鏡(名大)
CPUのメニーコア化に伴いマルチスレッドでの性能向上は注目されており,索引構造においてもB+木を基にBw木やBz木といったロックフリー索引が提案された.これらの索引構造ではノードの分割やマージなどの構造変更操作において,構造変更中のノードを観測したスレッドがそのノードの構造変更操作を後追いするという処理がある.しかし,これはキューやスタックといった簡潔なデータ構造において採用された手続きを踏襲したものであり,より複雑な索引構造における後追い処理の有効性は検証されていない.そこで,本論文では再現実装したBw木において後追い処理の有無による性能を比較し,後追い処理の必要性を評価する.