DBMS - 雜湊

對於龐大的資料庫結構，遍歷所有索引值併到達目標資料塊以檢索所需資料幾乎是不可能的。雜湊是一種有效的技術，可以計算磁碟上資料記錄的直接位置，而無需使用索引結構。

雜湊使用雜湊函式，並將搜尋鍵作為引數來生成資料記錄的地址。

雜湊組織

• 桶 - 雜湊檔案以桶格式儲存資料。桶被認為是儲存單元。一個桶通常儲存一個完整磁碟塊，而一個磁碟塊又可以儲存一個或多個記錄。

• 雜湊函式 - 雜湊函式 h 是一個對映函式，它將所有搜尋鍵集 K 對映到放置實際記錄的地址。它是一個從搜尋鍵到桶地址的函式。

靜態雜湊

在靜態雜湊中，當提供搜尋鍵值時，雜湊函式始終計算相同的地址。例如，如果使用 mod-4 雜湊函式，則它只會生成 5 個值。對於該函式，輸出地址始終相同。提供的桶數始終保持不變。

操作

• 插入 - 當需要使用靜態雜湊輸入記錄時，雜湊函式 h 計算搜尋鍵 K 的桶地址，記錄將儲存在該地址中。

  桶地址 = h(K)

• 搜尋 - 當需要檢索記錄時，可以使用相同的雜湊函式來檢索儲存資料的桶的地址。

• 刪除 - 這只是一個搜尋然後是刪除操作。

桶溢位

桶溢位的情況稱為衝突。這對任何靜態雜湊函式來說都是致命的狀態。在這種情況下，可以使用溢位鏈。

• 溢位鏈 - 當桶已滿時，為相同的雜湊結果分配一個新桶，並將其連結到前一個桶之後。這種機制稱為閉合雜湊。

• 線性探測 - 當雜湊函式生成一個已經儲存資料的地址時，將為其分配下一個空閒桶。這種機制稱為開放雜湊。

動態雜湊

靜態雜湊的問題在於，它不會隨著資料庫大小的增長或縮小而動態擴充套件或收縮。動態雜湊提供了一種機制，可以透過該機制動態地按需新增和刪除資料桶。動態雜湊也稱為擴充套件雜湊。

在動態雜湊中，雜湊函式被設計為生成大量值，並且最初只使用其中一部分。

組織

整個雜湊值的開頭作為雜湊索引。只有一部分雜湊值用於計算桶地址。每個雜湊索引都有一個深度值，表示用於計算雜湊函式的位數。這些位可以定址 2n 個桶。當所有這些位都被使用時 - 即所有桶都滿了 - 則深度值線性增加，並分配兩倍的桶。

操作

• 查詢 - 檢視雜湊索引的深度值，並使用這些位計算桶地址。

• 更新 - 如上執行查詢並更新資料。

• 刪除 - 執行查詢以找到所需資料並刪除。

• 插入 - 計算桶的地址

  • 如果桶已滿。
    • 新增更多桶。
    • 向雜湊值新增其他位。
    • 重新計算雜湊函式。
  • 否則
    • 將資料新增到桶中，
  • 如果所有桶都滿了，則執行靜態雜湊的補救措施。

當資料以某種順序組織並且查詢需要一定範圍的資料時，雜湊是不利的。當資料是離散且隨機時，雜湊的效能最佳。

雜湊演算法的複雜度高於索引。所有雜湊操作都在恆定時間內完成。