Dbms-hashing
DBMS-ハッシュ
巨大なデータベース構造の場合、すべてのレベルですべてのインデックス値を検索し、目的のデータブロックに到達して目的のデータを取得することはほとんど不可能です。 ハッシュは、インデックス構造を使用せずにディスク上のデータレコードの直接の場所を計算するための効果的な手法です。
ハッシュは、データレコードのアドレスを生成するためのパラメーターとして検索キーを持つハッシュ関数を使用します。
ハッシュ編成
- バケット-ハッシュファイルはバケット形式でデータを保存します。 バケットはストレージの単位と見なされます。 通常、バケットには1つの完全なディスクブロックが格納され、ディスクブロックには1つ以上のレコードが格納されます。
- ハッシュ関数-ハッシュ関数、* h、は、検索キー *K のすべてのセットを実際のレコードが配置されるアドレスにマッピングするマッピング関数です。 これは、検索キーからバケットアドレスまでの機能です。
静的ハッシュ
静的ハッシュでは、検索キー値が提供されると、ハッシュ関数は常に同じアドレスを計算します。 たとえば、mod-4ハッシュ関数が使用される場合、生成されるのは5つの値のみです。 出力アドレスは、その機能に対して常に同じでなければなりません。 提供されるバケットの数は常に変更されません。
操作
- 挿入-静的ハッシュを使用してレコードを入力する必要がある場合、ハッシュ関数 h は、レコードが保存される検索キー K のバケットアドレスを計算します。 +バケットアドレス= h（K）
- 検索-レコードを取得する必要がある場合、同じハッシュ関数を使用して、データが保存されているバケットのアドレスを取得できます。
- 削除-これは単に削除操作が続く検索です。
バケットオーバーフロー
バケットオーバーフローの状態は*衝突*と呼ばれます。 これは、静的ハッシュ関数にとって致命的な状態です。 この場合、オーバーフローチェーンを使用できます。
- オーバーフローチェーン-バケットがいっぱいになると、同じハッシュ結果に新しいバケットが割り当てられ、前のバケットの後にリンクされます。 このメカニズムは Closed Hashing と呼ばれます。
- 線形探査-ハッシュ関数がデータが既に保存されているアドレスを生成するとき、次の空きバケットがそれに割り当てられます。 このメカニズムは、 Open Hashing と呼ばれます。
動的ハッシュ
静的ハッシュの問題は、データベースのサイズが拡大または縮小しても動的に拡大または縮小しないことです。 動的ハッシュは、データバケットが動的にオンデマンドで追加および削除されるメカニズムを提供します。 動的ハッシュは、*拡張ハッシュ*とも呼ばれます。
動的ハッシュのハッシュ関数は、多数の値を生成するために作成され、最初に使用されるのはごくわずかです。
組織
ハッシュ値全体のプレフィックスは、ハッシュインデックスとして取得されます。 バケットアドレスの計算には、ハッシュ値の一部のみが使用されます。 すべてのハッシュインデックスには、ハッシュ関数の計算に使用されるビット数を示す深度値があります。 これらのビットは、2n個のバケットをアドレス指定できます。 これらのビットがすべて消費されると、つまり、すべてのバケットがいっぱいになると、深さの値は線形的に増加し、バケットの2倍が割り当てられます。
操作
- クエリ-ハッシュインデックスの深さの値を確認し、それらのビットを使用してバケットアドレスを計算します。
- 更新-上記のようにクエリを実行し、データを更新します。
- 削除-クエリを実行して目的のデータを見つけ、削除します。
- 挿入-バケットのアドレスを計算する
- バケットがすでにいっぱいの場合。
- さらにバケットを追加します。
- ハッシュ値にビットを追加します。
- ハッシュ関数を再計算します。
- Else
- バケットにデータを追加し、
- すべてのバケットがいっぱいの場合は、静的ハッシュの対策を実行します。
データが何らかの順序で編成されており、クエリが一連のデータを必要とする場合、ハッシュは好ましくありません。 データが離散的でランダムな場合、ハッシュが最高のパフォーマンスを発揮します。
ハッシュアルゴリズムは、インデックス作成よりも複雑です。 すべてのハッシュ操作は一定時間で実行されます。
