DBMS動態哈希

動態哈希方法用於克服桶溢出等靜態哈希問題。
在此方法中，隨著記錄的增加或減少，數據桶會增大或減小。 此方法也稱為可擴展哈希方法。
該方法使哈希動態化，即，它允許插入或刪除而不會導致性能不佳。

如何搜索一個鍵

• 首先，計算鍵的哈希地址。
• 檢查目錄中使用了多少位，這些位稱為i。
• 取哈希地址的最不重要的i位。 這給出了目錄的索引。
• 現在使用索引，轉到目錄並查找記錄可能位於的存儲區地址。

如何插入新記錄

• 首先，必須按照相同的步驟進行檢索，最後才會進入某個存儲桶。
• 如果存儲桶中仍有空間，則將記錄放入其中。
• 如果存儲桶已滿，則將拆分存儲桶並重新分配記錄。

示例：
考慮將以下將鍵分組到桶中，具體取決於其哈希地址的首碼：

2和4的最後兩位是00。所以它將進入桶B0。 5和6的最後兩位是01，因此它將進入存儲桶B1。 1和3的最後兩位是10，因此它將進入桶B2。 7的最後兩位是11，所以它將進入B3。

將帶有哈希地址10001的鍵9插入上述結構中：

• 由於鍵9具有散列地址10001，因此它必須進入第一個桶。 但是桶B1已滿，所以它要分裂。
• 分裂將從5分離5,9，因為最後三位5,9是001，所以它將進入桶B1，最後三位6是101，因此它將進入桶B5。
• 鍵2和鍵4仍在B0中。 B0中的記錄由000和100條目指向，因為條目的最後兩位都是00。
• 鍵1和鍵3仍在B2中。 B2中的記錄由010和110條目指示，因為兩個條目的最後兩位都是10。
• 鍵7仍在B3中。 B3中的記錄由111和011條目指向，因為兩個條目的最後兩位都是11。

動態哈希的優點

• 在這種方法中，性能不會隨著系統中數據的增長而降低。它只是增加記憶體大小以容納更多的數據。
• 在這種方法中，隨著數據的增長和縮小，記憶體得到了很好的利用。不會有任何未使用的記憶體。
• 這種方法適用於數據增長和頻繁縮小的動態資料庫。

動態哈希的缺點

• 在這種方法中，如果數據大小增加，則桶大小也增加。 這些數據地址將保存在存儲區地址表中。 因為隨著存儲桶的增長和縮小，數據地址將不斷變化。 如果數據量大幅增加，則維護存儲區地址表變得乏味。
• 在這種情況下，也會發生桶溢出情況。 但是，與靜態哈希相比，可能需要很少時間就遇到(達到)這種情況。