はじめに

前回，前々回と転置索引の論理的構造について見てきました。今回は，転置索引の具体的なデータ構造や実装について説明していきます。

辞書の実装

辞書は通常，単語に対応した情報を高速に取得するために，ハッシュや木構造などのデータ構造を取ります。現在は, 安定した性能や単語の順序関係を利用したいなどの理由で，木構造のデータ構造が使われることが多いと思います。最も単純な場合，2分探索木（Binary Search Tree）や2分探索（Binary Search）の実装が考えられます。

2分探索（木）による辞書の実装

では，辞書の具体的なデータ構造について，図を交えて解説していきましょう。

前回も触れましたが，辞書には単語とその単語に対応するポスティングリストの位置情報のペア（のリスト）が格納されています。単語で検索をするので，ペア自体は単語をキーとして並び換えられます。

たとえば, 前回の例の文書における辞書をメモリ上で2分探索木として実装する場合は図1のようになります（各ノード間はポインタによりリンクされます）。

文書1(D1): I like search engines.
文書2(D2): I search keywords in Google.

また，ディスク上に実装する場合は，ペアを単語の辞書順に並べます。ただ，単純に並べただけなので，どこがペア間の区切れかがわかるように，各ペアに対して先頭からのオフセットを保持しておき，検索時はそのオフセットの配列に対して2分探索を行うことになります（図2）。

辞書を全部メモリ上に載せることができる場合は，このような2分木は非常に高速になり，特に木がバランスされている場合は，O(log₂N)回の探索で結果を見つけることができます。しかし，辞書をメモリに載せない場合（または載らない場合）はHDDなどの二次記憶装置に置く必要があり，上記のような2分探索は効率的ではありません。

HDDやSSDなどの二次記憶装置はブロックデバイスと呼ばれ，ブロック単位でI/Oが発行されます（※1）。つまり，ブロック中の1ビットを読むだけでも，そのブロック全体がディスクからメモリに転送されてしまいます。

たとえば，100万件の単語辞書がある場合，2分探索では最低でも20回程度の探索が必要ですが，最悪の場合20ブロックの読み込みが必要となってしまい，1回の探索でディスクI/Oだけでも数10ms～数100msの時間がかかってしまいます。仮に，データ転送時間を3ms/ブロックとすると，ディスクI/Oだけで60msもの時間がかかってしまうことになります。

このため，大きな辞書を保持する場合には，よりブロックデバイスの特性に合ったB+木などの木構造データが使われます。

※1

HDDの場合は512バイトのセクタが単位となります。さらにその上のファイルシステムでは，デバイスのブロックサイズの定数倍をブロック（またはページ）という単位で管理し，その単位でI/Oを発行します。（Linuxでは通常4Kバイト）

B+木による辞書の実装

B+木はB木から派生したデータ構造です。全てのレコードは木の葉ノード（leaf node）に格納され，内部ノード（internal node）にはキーのみが格納される木構造となります（※2）。

B+木は，各ノードをページと呼ばれる単位で管理し，通常はそれをファイルシステムのブロックサイズの定数倍にします。そして，そのページをノードとして木構造を構築することで，検索や構築におけるディスクI/Oを少なくするという仕組みです（図3）。ここでは，概要のみの説明とし，詳しい仕組みは参考文献を参照ください。

先ほどと同様に，100万件の単語辞書がB+木で管理されているとしましょう。ここでは，ブロックサイズとページサイズは共に4Kバイトとします。また，各単語の平均サイズを10バイトとし，ページ内でのオフセットのサイズを2バイト（※3），下段ノードへの参照ポインタのサイズを4バイトとすると，単語ごとに16バイトがページ内で使われます。よって，ページには約250のキー（単語）が格納できることになります（※4）。

各ページに250の単語が格納でき，ページ内の各単語に対して，その単語より小さい単語集合のノード（または大きい単語のノードが）にリンクが張られるため，100万件の単語の格納には，3段のノードがあれば十分となります（250×250×250＝約1500万）。つまり，3つのブロックの読み込みで，いずれの単語も検索することが可能となります。仮に先の例と同様3ms／ブロックとすると，ディスクI/Oは9msとなり，上の例の60msと比較すると違いは歴然です。

このように，大規模な辞書をブロックデバイス上で扱う場合は，B+木を利用することで効率的に管理することができます。

※2

B木と言及していても，B+木を指す場合があるので注意が必要です。上記の特徴で判断するのが良いと思います。

※3

単語は可変長のため，各単語がページ内のどこに保存されているかを示すために，通常はオフセットの配列が管理されています。

※4

ディスクI/Oを見積もるために，非常に大雑把な計算をしています。実際は，各ページにはページ内情報を管理するヘッダ領域があったり，ページ内にN個の単語がある場合はN+1個の参照ポインタが存在します。