[5C]索引

14:20 〜 14:45

[5C-03] ロックフリー索引のトライ木化による改善と評価

*井戸 佑¹、杉浦 健人¹、石川 佳治¹、陸 可鏡¹ (1. 名古屋大学大学院情報学研究科)

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

キーワード：

索引構造、ロックフリーアルゴリズム、トライ木

代表的な索引構造であるB+木は様々なデータを格納可能な汎用性の高い索引である．一方で，扱うキーに制限を加え，索引構造を最適化させることで性能を向上させた索引（mass木など）も開発されてきた．本研究では，著者らの研究室で開発しているロックフリーB+木（Bc木）に対し同様の拡張および性能改善を行う．具体的には，扱うキーをバイナリ比較可能なものに制限することでトライ木の構造を適用し，検索性能の向上を図る．また，mass木ではトライ木構造に起因してメモリ利用効率が悪化する可能性があった．そこで本研究ではレコード管理にposting listを用い，既存研究mass木の課題であった空間利用率の改善を図る．