靜態(tài)散列要求桶的數(shù)目始終固定，那么在確定桶數(shù)目和選擇散列函數(shù)時，如果桶數(shù)目過小，隨著數(shù)據(jù)量增加，性能會降低；如果留一定余量，又會帶來空間的浪費；或者定期重組散列索引結(jié)構(gòu)，但這是一項開銷大且耗時的工作。為了應對這些問題，為此提出了幾種動態(tài)散列(dynamic

hashing)技術(shù)，可擴展動態(tài)散列(extendable hashing)便是其一。

一、可擴展動態(tài)散列

A)用一個數(shù)組來存儲桶指針的目錄，數(shù)組的位數(shù)為2的D次方，桶的容量為2的L次方，D和L分別稱為全局位深度和局部位深度。每次發(fā)生桶溢出時，溢出桶分裂，容量變?yōu)?的L+1次方，其它桶的容量保持不變，同時數(shù)據(jù)目錄的深度變?yōu)镈+1。擴展容量時，只是調(diào)整了局部的桶容量和目錄的容量，性能開銷比較小。

上圖中，目錄深度為2，目錄項有4個。然后開始插入數(shù)據(jù)d1和d2，假定h(d1)=13、h(d2)=20，由于13=1101，且全局位深度為2，則根據(jù)后兩位01確定應插入b桶，b桶有空間，可直接插入。20=10100，應插入a桶，但a桶以及滿了，于是開始分裂，a桶的局部位深度變?yōu)?，容量擴展為8，如果擴展后的局部位深度超過了全局位深度，則全局位深度等于這個最大的局部位深度，于是全局位深度也隨之變?yōu)?。

如上圖所示，a桶分裂為a1、a2，目錄變?yōu)槿?，對原來a桶中的元素進行重組，由于目錄位多了一位，要根據(jù)000、100來分別存儲到a1、a2桶。雖然目錄發(fā)生了翻倍，但未進行分裂的桶的局部深度仍然為2，所以會有多個目錄項指向這些桶，比如001、101的后兩位都是01，都指向b桶。

B)對于查找操作，根據(jù)當前的全局位深度，通過目錄直接定位到桶地址，隨后在桶內(nèi)部逐一查找。

C)對于刪除操作，與查找操作類似，刪除元素后，如果發(fā)現(xiàn)桶變?yōu)榭?，可與其兄弟桶進行合并，并使局部位深度減一。如果所有的局部位深度都小于全局位深度，則目錄數(shù)組也進行收縮。

二、靜態(tài)散列與動態(tài)散列對比

與靜態(tài)散列相比，動態(tài)散列的主要優(yōu)勢在于其性能不會隨著記錄數(shù)增長而下降，另外還具有最小的空間占用。缺點在于它會額外增加一次查詢定位，因為在查詢bucket本身前，需要先查找目錄來定位bucket。

另一種動態(tài)散列技術(shù)-線性散列(linear hashing)可以避免額外的查詢定位，但可能這種方式需要更多的溢出桶，日后學習。

三、順序索引與散列的適用場景

每種索引結(jié)構(gòu)都有其優(yōu)缺點。如果是select * from a where b=c這樣的定值查詢，散列比順序索引跟適合，順序索引會隨著記錄數(shù)的增加而性能降低，散列則相對穩(wěn)定。而對于where b>c and b

學習資料：Database System Concepts, by Abraham Silberschatz, Henry F.Korth, S.Sudarshan

https://www.cnblogs.com/kegeyang/archive/2012/04/05/2432608.html