[5C]索引

13:30 〜 13:55

[5C-01] 同時実行B+木のマルチバージョン化と範囲走査性能の評価

*桑村 真生¹、杉浦 健人¹、石川 佳治¹、陸 可鏡¹ (1. 名古屋大学 情報学研究科)

発表者区分：学生
論文種別：ロングペーパー
インタラクティブ発表：あり

キーワード：

データ構造・索引、多版同時実行制御、インメモリデータ管理

多版同時実行制御（MVCC）を採用したデータベースでは，レコードの古いバージョンが保持されており，データベースのある時点でのスナップショットの読み取りが可能である．これにより，読み取りと書き込みが並行してもそれぞれの一貫性を保つことができる．従来のMVCCでは，読み取り時に線形リストの形で管理されるレコードの各バージョンを常に最新のものから順に確認して適切なバージョンを探索する．このリストに対する線形探索は性能を律速することが知られている．先行研究のvWEAVERでは，各レコードの古いバージョン同士を繋ぐパスによってリストの中間からの走査を実現し，範囲走査におけるバージョン探索を高速化した．我々はロックフリー索引である同時実行B+木の構造を活用し，先行研究のさらなる改善を行った．すなわち，リストをレコード単位ではなく，より粗粒度なB+木のノード単位で構築し，リスト走査のコストを抑えた．これにより，範囲走査と書き込みが並行するワークロードにおいて，提案手法は先行研究を上回る性能を示した．