前の記事で、検索エンジンの仕事について話したので、難しい技術的なポイントに到達しました。 インデックスには、直接インデックスと逆インデックスの2種類があることを思い出させてください。 直接-一致した単語のドキュメントリストと一致します。 逆-単語は、それが含まれているドキュメントのリストと一致します。 逆索引がクイック検索に最も適しているのは論理的です。 興味深い質問は、ドキュメントがリストに保存される順序についてです。
インデクサーモジュールからの前のステップDataFlowで、直接インデックス、リンク情報、およびページ情報の形式でデータを受け取りました。 通常、私にとっては約200〜300 MBで、約10万ページが含まれています。 時間が経つにつれて、堅実な順方向インデックスを格納する戦略を放棄し、ロールバックできるように、これらすべてのピースと完全な逆方向インデックスのみをいくつかのバージョンで格納します。
逆索引デバイスは単純なように見えます。ファイルを保存します。ファイルの先頭には、各単語のデータの先頭のアドレスのテーブルがあり、次にデータ自体があります。 これは誇張した。 したがって、BrinとPageが書いたように、検索速度を最適化するのに最も有利な形式がわかります。ページをジャンプする必要はありません-1シーク、1リード。 再構築の各繰り返しで、上記の20〜50個の情報を使用します。明らかに、それらのすべての情報をメモリにロードすることはできません。特に、インデックスに関する多くの補助データを保存すると便利です。
この問題や、FS、ディスク、ページの複数のリストへの並列アクセスの制限に関連する他の多くの問題を解決するために、インデックス全体を256の部分に分割しました。 パートIには、WORD_ID％256 = Iという単語のページリストが含まれています
したがって、インデックスをほぼ等しい部分に分割します。 さらに、インデックスの再構築の次の反復でのすべての処理は、1つの部分のフレームワーク内でのみ接続されます。 つまり それぞれ200〜300 Mbのデータベースの20〜50個から、処理された部分に該当する単語に関連付けられているデータのみをダウンロードする必要があります。
合計：同じ手順を256回繰り返します：
- 単語、ページ、およびURLページに関するすべての情報をダウンロードした後、データベースの入力部分から必要なデータを読み取ります。 ソートしたメモリ内で、正しい構造のリストを作成します。 ページに関する情報をパックし、そのID、ハッシュ、その他のデータを追加します。
- 読み取り用に「極端なバージョン」の逆インデックスのバレル（インデックスの断片をそう呼んだ）を開きます。 書き込み用のインデックスの「新しいバージョン」の空のバレルを開きます。
- 単語ごとに、2つのリストを順番にマージします。1つはメモリ内でソートされ、もう1つは読み取り可能でファイル内ですでにソートされています。
- 閉じて、必要なものをすべて追加して、喜んでください。
実際には、ページの外部情報が変更されていない場合にのみ、インデックスの「以前のバージョン」にすでに格納されているリストが新しい反復中にソートされることが自然に判明しましたが、明らかにそうではありません。
実際、Oldをインデックスに蓄積している間に、PRデータ、ページメトリック、テーマサイトなどを再計算できました。 その結果、ソートの係数が変更されます。 リストを同様のパラメータでソートする必要があるかどうかという問題は未解決のままです。 噂によると、Googleはリスト内のページをPRでソートしますが、明らかに、検索時に外皮をすばやく破棄できる必要があります-これはPRによって特別に盛り上げられましたが、テーマは十分ではありません。
私は、ページ上の単語に関する一般情報（会議の数、会議場所-タイトル、メタ、リンク、テキスト、強調表示、書式設定）、テーマメトリック（これまでのところ非常に不十分な開発）、単語ごとのPR（すべての単語のPRもあります）およびその他のPRからのPR。
さらに、高頻度のクエリでは、神がリストの最初の1000〜2000の結果を本当に必要としていることは明らかです。 なぜなら すべての人気のある回答は明らかにそれらに該当します。その後、適切にソートするランキング関数を実行できます。
低頻度のクエリでは、実際に2-3-10の結果が必要な場合、インデックスの完全な通過が不可欠ですが、ページリストの合計長が10万を超える場合はめったにありません。
一般に、リストの最初のN千ページが残りの数百万の中で最高になることを保証できれば、問題は解決され、これを保証することは非常に単純な発見的方法です。 次に、各バレルを正しく再構築するために：
- 再集計するときにどのPRが大きく変わったかを覚えています
- リストから最初のN千をロードし、PR基準、ページメトリックス、およびその他のヒューリスティックに従って残りから少しをロードします
- そこで、入力データから現在のバレルの単語の必要な部分をロードします
- 選択したページについてのみ、すでに正しいデータ、新しいデータ、PR、メトリックですべてのデータを更新しています
- 数千万のメモリの代わりに数十万の結果をソートします
- ソート済みで記述し、残りは前のインデックスから単純にコピーされ、重複を削除します
もちろん、月に1回または6か月に1回、インデックスを最も簡単な直接アルゴリズム全体で再構築する場合は、「全体を更新」機能が必要です。
中間で使用される300万の単語や数字に適用した場合でも、このような大量の作業は容易ではありませんが、完全な再構築と比較すると、大きなメリットがあります。ディスク上で並べ替える必要はありません。また、すべてをメモリにキャッシュすることはできません。
再構築の反復的な方法が、直接インデックスからの逆インデックスの最も単純な構築よりも何倍ものパフォーマンスをもたらすことは面白いです。 もちろん、一部の検索エンジンは、かなり強力なハードウェア上でこれを十分に迅速に行うことができますが、これは最善のアプローチですが、最も正しい方法です。 逆インデックスの長い挿入の数がすべてのプラスを無効にし、ストレージ構造では挿入速度またはシーケンシャル読み取り速度のいずれかが低下することを知っています。