DBMS でのハッシュ: 静的および動的ハッシュ手法
フィオナ・ブラウン
⚡ スマートサマリー
DBMSにおけるハッシュ化とは、インデックスをたどることなく、レコードのキーから直接ディスク上の位置を計算する手法です。ハッシュ関数は検索キーをデータバケットにマッピングし、静的ハッシュ化または動的ハッシュ化によって、これらのバケットの拡張方法が管理されます。
DBMS におけるハッシュとは何ですか?
DBMSにおいて、ハッシュ化はインデックス構造を使用せずにディスク上の目的のデータの位置を直接検索する技術です。ハッシュ化方式は、データベース内の項目をインデックス化して取得するために使用されます。これは、元の値ではなく、より短いハッシュキーを使用して特定の項目を検索する方が高速であるためです。データは、ハッシュ関数を適用してアドレスが生成されるデータブロックの形式で格納されます。これらのレコードが格納されるメモリ位置は、 データブロックまたはデータバケット.
ハッシュ化が必要な理由とは？
DBMSにおいてハッシュ法を適用する必要がある状況は以下のとおりです。
- 巨大なデータベース構造の場合、すべてのインデックス値をすべてのレベルにわたって検索し、目的のデータブロックに到達して目的のデータを取得するのは困難です。
- ハッシュ化は、データベース内の項目をインデックス化して検索するために使用されます。これは、元の値よりも短いハッシュ化されたキーを使用して特定の項目を検索する方が高速であるためです。
- ハッシュ化は、インデックス構造を使用せずに、ディスク上のデータレコードの直接的な位置を計算するための理想的な方法です。
- これは、辞書を実装する場合にも役立つテクニックです。
ハッシュにおける重要な用語
ハッシュ化で使用される重要な用語を以下に示します。
- データバケット: データバケットとは、レコードが格納されるメモリ上の場所のことです。ストレージの単位とも呼ばれます。
- キー： a DBMSキー は、リレーション（テーブル）内の行（タプル）を識別するのに役立つ属性または属性のセットです。
- ハッシュ関数: 地図ping 検索キーのすべてを、実際のレコードが格納されているアドレスにマッピングする関数。
- 直線プローブ法： プローブ間の間隔は一定です。この方法では、古いレコードを上書きするのではなく、次に利用可能なデータブロックを使用して新しいレコードを入力します。
- 二次プロービング： 二次多項式の連続する出力を元の計算で得られた開始値に加算することで、新しいバケットアドレスを決定するのに役立ちます。
- ハッシュインデックス: データブロックのアドレス。ハッシュ関数は、単純な数学関数でも複雑な関数でも構いません。
- Double ハッシュ： ハッシュテーブルにおいて、2つ目のハッシュ関数を適用することで衝突を解決するために用いられる手法。
- バケツオーバーフロー: バケットオーバーフローの状態は衝突と呼ばれます。これは、静的ハッシュ関数にとって致命的な段階です。
ハッシュ手法の種類
DBMSにおけるハッシュ化手法には、主に2種類あります。
- 静的ハッシュ
- 動的ハッシュ
次の2つのセクションで説明するように、両者の主な違いは、バケットの数が固定されているかどうかという点にある。
静的ハッシュ
静的ハッシュの場合、結果として得られるデータバケットのアドレスは常に同じままです。
したがって、たとえば、アドレスを生成すると、 学生ID = 10 ハッシュ関数を使用する mod(3)、結果のバケットアドレスは常に次のようになります。 1そのため、バケットアドレスに変更は表示されません。
したがって、静的ハッシュ方式では、メモリ内のデータバケットの数は常に一定に保たれる。
静的ハッシュ関数
- レコードの挿入: テーブルに新しいレコードを挿入する必要がある場合、そのレコードのハッシュキーを使用してアドレスを生成します。アドレスが生成されると、レコードはそのアドレスに格納されます。
- 検索中： レコードを取得する必要がある場合、同じハッシュ関数を使用して、データが保存されているバケットのアドレスを取得します。
- レコードを削除する： ハッシュ関数を使用する場合、まず削除したいレコードを取得し、次にメモリ上のそのアドレスからレコードを削除します。
静的ハッシュはさらに以下のように分類されます。
- オープンハッシュ
- クローズドハッシュ
オープンハッシュ
オープンハッシュ方式では、古いレコードを上書きするのではなく、次に利用可能なデータブロックを使用して新しいレコードを入力します。この方式は、線形プロービングとも呼ばれます。
例えば、A2は挿入したい新しいレコードです。ハッシュ関数はアドレス222を生成しますが、このアドレスは既に別の値で占有されています。そのため、システムは次のデータバケットである501を探し、A2をそこに割り当てます。
クローズドハッシュ
クローズドハッシュ方式では、バケットがいっぱいになると、同じハッシュ値に対して新しいバケットが割り当てられ、その結果が前の結果の後にリンクされます。
動的ハッシュ
動的ハッシュは、データバケットを動的に、かつ必要に応じて追加および削除するメカニズムを提供します。このハッシュ方式では、ハッシュ関数が多数の値を生成するのに役立ち、構造はデータに応じて拡大または縮小します。そのため、静的ハッシュではスペースの無駄遣いやオーバーフローが発生するような、サイズを事前に予測できないテーブルに最適です。
順序付きインデックスとハッシュの違い
インデックス作成とハッシュ化の主な違いは以下のとおりです。
| 技術パラメータ | 順序付きインデックス | ハッシング |
|---|---|---|
| アドレスの保存 | メモリ内のアドレスは、主キーと呼ばれるキー値に基づいてソートされます。 | アドレスは常にキー値のハッシュ関数を使用して生成されます。 |
| パフォーマンス | データ量が増えるにつれて、データ量は減少する可能性があります。これは、データがソートされた状態で保存され、挿入、削除、更新のたびにデータが再配置されるためです。 | データの追加と削除が頻繁に行われる場合、パフォーマンスは最適になります。大規模なデータベースでは、ハッシュファイルのメンテナンスコストが高くなります。 |
| のために使用します | 特定の範囲のデータを取得する範囲検索に適しています。 | 検索キーに基づいて特定のレコードを取得するのに最適であり、ハッシュ関数が検索キーに適用されている場合にのみ優れたパフォーマンスを発揮します。 |
| メモリ管理 | 削除や更新操作によって発生する未使用のデータブロックは多く、再利用のために解放することはできないため、定期的なメンテナンスが必要です。 | 静的ハッシュと動的ハッシュでは、メモリは常に管理され、静的ハッシュを拡張するためにバケットオーバーフローが処理されます。 |
要するに、順番に選択してください インデキシング 範囲クエリと、キーに対する完全一致検索のためのハッシュ化。
衝突とは何ですか？
ハッシュ衝突とは、データセット内の 2 つ以上の項目から生成されたハッシュが、誤って同じ場所にマッピングされる状態です。 ハッシュ表.
ハッシュ衝突への対処方法
ハッシュ衝突を回避するために使用できる手法は2つあります。
- 再考: このメソッドは、二次ハッシュ関数を呼び出し、レコードを配置できる空きスロットが見つかるまで、この関数を継続的に適用します。
- 連鎖: 連鎖方式では、キーのハッシュ値が同じ項目のリンクリストを作成します。この方式では、テーブルの各位置にリンクフィールドを追加する必要があります。
