DBMS でのハッシュ: 静的および動的ハッシュ手法

なぜハッシュが必要なのでしょうか?

DBMS でハッシュ法を適用する必要がある状況は次のとおりです。

• 巨大なデータベース構造の場合、そのすべてのレベルですべてのインデックス値を検索するのは困難であり、目的のデータを取得するには目的のデータ ブロックに到達する必要があります。
• ハッシュ法は、元の値を使用する代わりに短いハッシュ キーを使用して特定のアイテムを検索する方が高速であるため、データベース内のアイテムのインデックス付けと取得に使用されます。
• ハッシュは、インデックス構造を使用せずにディスク上のデータ レコードの直接位置を計算する理想的な方法です。
• これは、辞書を実装する場合にも役立つテクニックです。

ハッシュにおける重要な用語

ここでは、ハッシュで使用される重要な用語を示します。

• データバケット – データ バケットは、レコードが保存されるメモリの場所です。 ストレージ単位とも呼ばれます。
• キー： DBMSキー リレーション (テーブル) 内の行 (タプル) を識別するのに役立つ属性または属性のセットです。 これにより、XNUMX つのテーブル間の関係を見つけることができます。
• ハッシュ関数: ハッシュ関数は、すべての検索キーのセットを実際のレコードが配置されるアドレスにマッピングするマッピング関数です。
• リニアプロービング – リニアプロービングは、プローブ間の固定間隔です。 この方法では、古いレコードを上書きするのではなく、次に利用可能なデータ ブロックを使用して新しいレコードを入力します。
• 二次プロービング– 新しいバケットのアドレスを決定するのに役立ちます。 二次多項式の連続出力を元の計算で与えられた開始値に追加することで、プローブ間の間隔を追加するのに役立ちます。
• ハッシュインデックス – データ ブロックのアドレスです。ハッシュ関数は、単純な数学関数から複雑な数学関数までさまざまです。
• Double ハッシング –Double ハッシュは、衝突の問題を解決するためにハッシュ テーブルで使用されるコンピューター プログラミング手法です。
• バケットのオーバーフロー: バケットオーバーフローの状態は衝突と呼ばれます。 これは、静的機能が機能する必要がある場合には致命的な段階です。

ハッシュ手法の種類

SQL ハッシュの方法/技術には主に XNUMX 種類があります。

1. 静的ハッシュ
2. 動的ハッシュ

静的ハッシュ

静的ハッシュでは、結果のデータ バケット アドレスは常に同じままになります。

したがって、たとえばアドレスを生成すると、 学生ID = 10 ハッシュ関数を使って mod(3)、結果のバケットアドレスは常に次のようになります。 1。 したがって、バケット アドレスに変化は見られません。

したがって、この静的ハッシュ方法では、メモリ内のデータ バケットの数は常に一定になります。

静的ハッシュ関数

• レコードを挿入する: 新しいレコードをテーブルに挿入する必要がある場合、ハッシュ キーを使用して新しいレコードのアドレスを生成できます。 アドレスが生成されると、レコードはその場所に自動的に保存されます。
• 検索: レコードを取得する必要がある場合、データを保存するバケットのアドレスを取得するために同じハッシュ関数が役立つはずです。
• レコードを削除する: ハッシュ関数を使用すると、最初に削除したいレコードを取得できます。 その後、メモリ内のそのアドレスのレコードを削除できます。

静的ハッシュはさらに次のように分類されます。

1. オープンハッシュ
2. クローズハッシュ。

オープンハッシュ

オープン ハッシュ法では、古いデータ ブロックを上書きする代わりに、次に利用可能なデータ ブロックを使用して新しいレコードを入力します。この方法は線形プローブとしても知られています。

たとえば、A2 は挿入する新しいレコードです。 ハッシュ関数はアドレス 222 を生成します。しかし、それはすでに他の値によって占有されています。 そのため、システムは次のデータ バケット 501 を探し、それに A2 を割り当てます。

クローズハッシュ

クローズハッシュ法では、バケットがいっぱいになると、同じハッシュに対して新しいバケットが割り当てられ、結果は前のバケットの後にリンクされます。

動的ハッシュ

動的ハッシュは、データ バケットが動的かつオンデマンドで追加および削除されるメカニズムを提供します。 このハッシュ化では、ハッシュ関数を使用すると、多数の値を作成できます。

順序付きインデックスとハッシュの違い

以下は、インデックス作成とハッシュの主な違いです。

衝突とは何ですか？

ハッシュ衝突とは、データセット内の XNUMX つ以上のデータから得られたハッシュが、データセット内の同じ場所に誤ってマッピングされる状態です。 ハッシュ表.

ハッシュ衝突にどう対処するか?

ハッシュの衝突を避けるために使用できる手法が XNUMX つあります。

1. 再ハッシュ: このメソッドは、レコードを配置する空のスロットが見つかるまで継続的に適用される二次ハッシュ関数を呼び出します。
2. 連鎖: 連鎖メソッドは、キーが同じ値にハッシュされる項目のリンクされたリストを構築します。 この方法では、各テーブル位置への追加のリンク フィールドが必要です。

まとめ

• In DBMS, ハッシュとは、インデックス構造を使用せずに、ディスク上の目的のデータの場所を直接検索する手法です。
• ハッシュ法は、元の値を使用する代わりに短いハッシュ キーを使用して特定のアイテムを検索する方が高速であるため、データベース内のアイテムのインデックス付けと取得に使用されます。
• データバケット、キー、ハッシュ関数、線形プローブ、二次プローブ、ハッシュインデックス、 Double ハッシュ、バケット オーバーフローはハッシュで使用される重要な用語です
• ハッシュ方式には 1) 静的ハッシュ、2) 動的ハッシュの XNUMX 種類があります。
• 静的ハッシュでは、結果のデータ バケット アドレスは常に同じままになります。
• 動的ハッシュは、データ バケットが動的かつオンデマンドで追加および削除されるメカニズムを提供します。
• メモリ内のインデックス アドレスは重要な値に従って並べ替えられますが、ハッシュ アドレスは常にキー値のハッシュ関数を使用して生成されます。
• ハッシュ衝突とは、データセット内の XNUMX つ以上のデータから得られたハッシュが、ハッシュ テーブル内の同じ場所に誤ってマッピングされる状態です。
• 再ハッシュとチェーンは、ハッシュの衝突を回避するのに役立つ XNUMX つの方法です。