靜态散列要求桶的數目始終固定，那麼在确定桶數目和選擇散列函數時，如果桶數目過小，随着資料量增加，性能會降低；如果留一定餘量，又會帶來空間的浪費；或者定期重組散列索引結構，但這是一項開銷大且耗時的工作。為了應對這些問題，為此提出了幾種動态散列(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