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

2N-01
ロックフリー索引BzTreeにおける並列一括挿入法の実装
○中山 宗,杉浦健人,石川佳治,陸 可鏡(名大)
Bz木はmulti-word compare-and-swap命令を用いたロックフリーアルゴリズムに 基づくB+木である.Bz木の提案論文では基礎的な読み書きのAPIに関する記述は ある一方,一括挿入法は提案されていない.しかし,運用開始時における索引の 構築時間の削減は重要な課題である.そこで,本論文ではBz木における一括挿入 法を提案する.提案手法では,一括挿入時には挿入されるレコードがあらかじめ 全て把握できる点に着目し,まず挿入されるレコードを整列する.その後,葉 ノードからボトムアップにBz木を構築することで,構造変更の頻度を抑えながら Bz木全体を構築する.提案する一括挿入法と個々にデータを挿入した際との性能 を比較し,提案手法の有効性を示す.