靜態散列要求桶的數目始終固定，那麼在確定桶數目和選擇散列函數時，如果桶數目過小，隨著數據量增加，性能會降低；如果留一定餘量，又會帶來空間的浪費；或者定期重組散列索引結構，但這是一項開銷大且耗時的工作。為了應對這些問題，為此提出了幾種動態散列(dynamic hashing)技術，可擴展動態散列(ex ...
靜態散列要求桶的數目始終固定，那麼在確定桶數目和選擇散列函數時，如果桶數目過小，隨著數據量增加，性能會降低；如果留一定餘量，又會帶來空間的浪費；或者定期重組散列索引結構，但這是一項開銷大且耗時的工作。為了應對這些問題，為此提出了幾種動態散列(dynamic hashing)技術，可擴展動態散列(extendable hashing)便是其一。
一、可擴展動態散列
A)用一個數組來存儲桶指針的目錄，數組的位數為2的D次方，桶的容量為2的L次方，D和L分別稱為全局位深度和局部位深度。每次發生桶溢出時，溢出桶分裂，容量變為2的L+1次方，其它桶的容量保持不變，同時數據目錄的深度變為D+1。擴展容量時，只是調整了局部的桶容量和目錄的容量，性能開銷比較小。
上圖中，目錄深度為2，目錄項有4個。然後開始插入數據d1和d2，假定h(d1)=13、h(d2)=20，由於13=1101，且全局位深度為2，則根據後兩位01確定應插入b桶，b桶有空間，可直接插入。20=10100，應插入a桶，但a桶以及滿了，於是開始分裂，a桶的局部位深度變為3，容量擴展為8，如果擴展後的局部位深度超過了全局位深度，則全局位深度等於這個最大的局部位深度，於是全局位深度也隨之變為3。
如上圖所示，a桶分裂為a1、a2，目錄變為三位，對原來a桶中的元素進行重組，由於目錄位多了一位，要根據000、100來分別存儲到a1、a2桶。雖然目錄發生了翻倍，但未進行分裂的桶的局部深度仍然為2，所以會有多個目錄項指向這些桶，比如001、101的後兩位都是01，都指向b桶。
B)對於查找操作，根據當前的全局位深度，通過目錄直接定位到桶地址，隨後在桶內部逐一查找。
C)對於刪除操作，與查找操作類似，刪除元素後，如果發現桶變為空，可與其兄弟桶進行合併，並使局部位深度減一。如果所有的局部位深度都小於全局位深度，則目錄數組也進行收縮。
二、靜態散列與動態散列對比
與靜態散列相比，動態散列的主要優勢在於其性能不會隨著記錄數增長而下降，另外還具有最小的空間占用。缺點在於它會額外增加一次查詢定位，因為在查詢bucket本身前，需要先查找目錄來定位bucket。
另一種動態散列技術-線性散列(linear hashing)可以避免額外的查詢定位，但可能這種方式需要更多的溢出桶，日後學習。
三、順序索引與散列的適用場景
每種索引結構都有其優缺點。如果是select
* from a where
b=c這樣的定值查詢，散列比順序索引跟適合，順序索引會隨著記錄數的增加而性能降低，散列則相對穩定。而對於where b>c and
b<d這樣的範圍搜索，則順序索引更適合，散列的隨機特性使得無法定位搜索的bucket。所以散列只適合根據搜索碼搜索且不是範圍查詢的場合。
學習資料：Database System Concepts, by Abraham Silberschatz, Henry F.Korth, S.Sudarshan
https://www.cnblogs.com/kegeyang/archive/2012/04/05/2432608.html
