はじめに

今回からは，近年の話題や少し発展した話題について触れていく予定です。

第7回では，転置索引の静的な構築方法について触れました。今回は，索引に対して文書のインクリメンタルに追加していく方法について触れていきます。

動的な索引構築の必要性

第7回の復習になりますが，索引の構築方法には"静的"な方法と"動的"な方法が存在します。英語ではそれぞれ，Offline Index Construction，Online Index Constructionと呼ばれています（※1⁠）⁠。

文書が頻繁に追加される場合や索引が大規模な場合，文書の追加の度に索引を作り直すことは非常に高コストとなり現実的ではありません。このような場合は，動的な構築方法により索引をインクリメンタルに更新していくことで対応することができます。情報が絶えず追加されている近年のWeb上では，とても重要な構築方法となります。

※1）

Online Index Constructionに関しては，日本語の表現が確立されていないため，本連載では"動的な索引構築"と表現することにします。これは，Online Index ConstructionはDynamic Indexingなどとも呼ばれるためです。

メモリ上の索引とディスク上の索引

動的な構築において，既存の索引に新しい文書を追加することは，文書が含む単語数分の新しいポスティングを転置リスト追加することを意味します。通常，1つの文書は数百から数千の単語を保持しているので，各単語のポスティングリストの更新の度にディスク上でシークを行うことになるため，非常にコストが高い処理となってしまいます。

このため，動的な索引構築においてはメモリ上の索引とディスク上の索引の2つの索引を保持し，直近の文書はメモリ上の索引に対して更新し，そのメモリ上の索引を定期的にディスク上の索引と統合するという処理が行われます。この方法は，多くのランダムアクセス処理はメモリ上で行われるため効率的になります。これにより，検索においてはメモリ上の転置リストとディスク上の転置リストを論理的に連結しなければいけないため，検索処理は多少複雑になります。

索引の統合

動的な索引構築においては，メモリ上の索引とディスク上の索引をどのように統合するかがポイントとなります。

大きく分けて以下の2種類の統合方法が存在します。

• インプレイスな更新による統合（Inplace Index Maintenance）
• マージによる統合（Merge-based Index Maintenance）

インプレイスな更新による統合とは，新しいポスティングを既存の転置リストの最後に書き加えることにより，各ステージにおける索引への変更を最小に抑える戦略になります。各ポスティングリストに対して多めに領域を確保しておき，その領域に新しいポスティングを格納します。確保してある領域が埋まってしまった場合は，そのポスティングリストを別の領域に移動することで対応します（別の領域においても多めの領域を確保します⁠）⁠。

この方法は，データベースにおける一般的なデータ管理方法であり，従来は主要な方法となっていました。しかし，更新における統合操作はディスクにおいて大量のシークやデータの移動が発生するため，近年はもう一方のマージによる統合方法がより効率的であると考えられています。

マージによる統合

マージによる統合では，インプレイスな更新による統合とは異なり，既存のディスク上索引を直接更新することはせず，ディスク上の既存の索引とメモリ上の新しい索引をマージし，それをディスク上の新しい領域に書き出す方法となります（※2⁠）⁠。このようなマージによる索引の統合には，幾つかのマージ戦略が考えられていますので，基本的な戦略を紹介します。

以下で紹介する3つのマージ戦略の概念図を図1に示します。図1は，各戦略における索引のマージ過程を表し，メモリ上の索引（青丸）がディスク上の索引（白丸）とどのようにマージされるかを示しています（白丸の左の数値は，メモリ上の索引を1としたときのサイズとなります⁠）⁠。

※2）

「ディスク上の新しい領域に書き出す」とは，新しいファイルとして書き出すことになります。