**転置インデックスは、語からその語を含むドキュメントへの対応を持ちます。**検索のたびに全ドキュメントを最初から最後まで読まずに、候補を見つけられます。
本の巻末索引を思い浮かべてください。語を引き、示されたページへ移動します。検索エンジンでは、ページ番号の代わりにドキュメント識別子を使います。
3つのドキュメントがあり、テキストを小文字にして単語に分ける単純なアナライザーを使うとします。アナライザーは、テキストを検索可能な語に変える処理の組み合わせです。
D1: Red apple
D2: Green apple
D3: Red car
apple -> D1, D2
car -> D3
green -> D2
red -> D1, D3
元の方向はドキュメントから単語です。索引では語からドキュメントへ方向を反転するため、この名前が付きます。各語に対応するドキュメントの一覧をposting listと呼びます。
redとappleの両方が必要なら、2つのposting listの共通部分を取ります。D1が両方にあります。どちらかを含めばよいなら和集合を取り、D1、D2、D3が候補です。
この例は一致の説明であり、順位の説明ではありません。複数が一致したら、語の出現頻度や集合全体での珍しさなどを使って点数を付けられます。一致を見つけることと順序を決めることは、関係する別の段階です。
クエリはインデックス内の語と互換性のある方法で解析する必要があります。登録時にRedをredへ変えても、検索が文字どおりのRedを探すと、意図した一致を逃す可能性があります。
適切な解析はフィールドによります。商品説明にはテキスト解析が有効ですが、注文IDは通常、完全一致が必要です。識別子を普通の単語に分けると意味が変わることがあります。Elasticの全文検索の説明を参照してください。
redとappleを含む文書が、red appleというフレーズを含むとは限りません。フレーズ検索には、順序と隣接を確認するための語の位置が必要です。
情報を増やすと豊かな検索を支えられますが、索引サイズと構築処理が増えます。必要な索引は、アプリケーションが支える検索で決まります。
元テキストが変われば、検索索引も更新しなければなりません。Elasticsearchなどはデータをセグメントで管理し、時間とともに統合します。更新のたびに、既存の全posting listをその場で書き直すわけではありません。検索に見えるタイミングはリフレッシュの動作にも依存します。
追加保存領域、索引作成コスト、書き込みから検索で見つかるまでの遅れを考慮します。転置インデックスは語に基づくテキスト検索に特に有効ですが、完全一致、範囲検索、トランザクション処理用の索引を万能に置き換えるものではありません。
ジュニアからシニアまで、詳細な回答付きのIT面接質問ライブラリ。
寄付する