URLとそのストレージを操作する

さて、ここにデータベースの最もおいしい部分の1つがあります-それは何十億もの異なるリンクを保存し、それらをランダムな順序でアクセスします。



最初は、すべてのURLがサイト内でグループ化されていることは明らかです。 1つのサイト内のすべてのリンクは、速度を上げるために一緒に保存できます。 私はサイトのURLを選択し、サイトのリストを個別に保存し始めました-現在60万あり、前述の別のデータベーステーブルで簡単に対処できます。 すべての既知のサイトのCRCを含むAVLツリーは常にメモリに配置され、URLの存在を最初に確認し、データベースに既に存在する場合は、それに対応するサイトIDを取得します。



リンクの残りの部分-サイトの名前に加えて、私は切断し、CRCを考えると、それをハッシュと呼びましょう。 したがって、リンクには比較的明確にインデックス（サイトID、ハッシュ）があります。 すべてのリンクは別のサイト内でハッシュによって並べ替えることができ、既存またはそうでないものを簡単に検索できます-目的のハッシュを満たすか、より大きなハッシュに出会うまで、このサイト上のすべてのリンクのリストを調べます-リンクはありません。 加速度はそれほど大きくありませんが、平均して2倍です。



インデックス内で占有するスペースが少なくなるように、各リンクにIDを割り当てたと言う必要があります-2 * 4ではなく4バイト。 個別のテーブルには、データID-（サイトID、ハッシュ）が含まれており、すばやく取得できます。



100万のリンクのリストを保存し、さらに60万のサイトに分類する方法についても少し説明します。 このために、別のタイプのテーブルが実装されています-2次元インデックス、つまり まず、ID1によって、ID2でソートされたデータのリストにアクセスします。特に、ほとんどの場合、ID2は1〜Nである必要はありません。 また、このようなテーブルを使用して逆インデックスを保存しましたが、より効果的なソリューションがそこで機能しています。 テーブル自体は、ID2をリストに追加してもリストのソートが維持されるように実装されます。



URLのすべてのデータはID1によって64の部分に分割され、テーブルKにはサイトID％64 = Kのサイトに関するレコードが含まれ、各テーブルは特定のID1ごとに割り当てられたセグメントに分割されます。 レコードの特定のリストにアクセスする必要がある場合-ID1により、それらはすべてディスク上の行に既に横たわっており、シークを行う位置とバッファリングされた読み取りを開始する位置はすぐにわかります。 必要なハッシュに達する瞬間まで正確に読みます



そのようなテーブルへの挿入は非常に高速ではありません。一方、大きなキャッシュと1つのレコードの少量により、パッケージをすばやく挿入できます。 更新パッケージは蓄積されています-現在、各テーブルに約32,000のリンクがあり、1パスで挿入されています-キャッシュのデータと古いテーブルがマージされるテーブルの一時コピーが作成されます。



wwwを含むURLと含まないURLは同じものとして考慮されます-最初のリンクがメインリンクと見なされたものに応じて、データベースに追加され、他のすべてのリンクはそれに接着されます。 これにより、wwwを無断で切断または切断しないようにすることができます-結局、このサイトはwwwなしでは機能しない可能性がありますが、wwwのあるアドレスとないアドレスの異なるサイトがあるという事実に関連するすべての問題を完全に解決するわけではありません



最も骨の折れる作業は、相対リンクを解決することでした-例：

「site.ru/index」ページにリンク「./」があり、「site.ru/」で解決する必要がありますが、最初のリンク「site.ru/index/」にスラッシュを追加すると、同じ場合もありますがサイトのページでは、許可されるリンクは「site.ru/index/」になるため、最後のスラッシュ、リンク引数、および実行可能ファイルの名前を切り捨てることはできません。



一般に、リンクをプロトコル、サイト、パス、ファイル名、引数、名前付きリンク（すべて＃の後）に分割します

カットされた2つのリンクから、リストを調べて、結果の欠落要素（必要な場合）を置き換えることにより、新しいリンクを収集します。

次に、「./././././」という形式の構造があることを忘れてはならず、それらを削除する必要があります。また、「../../../」を削除し、「＃」、「」を削除または置換する必要があります。 ？」

一般に、このプロセスは長くはありませんが、考えられるすべての組み合わせを処理するテストと方法を考えるのは非常に面倒です。 しかし、私が書いたとき-すべてがすでに正常に動作しています



検索エンジンに関する私の記事の全内容とリストはここで更新されます： http : //habrahabr.ru/blogs/search_engines/123671/