第4章 磁碟雜湊#

雜湊把鍵值直接映射到儲存位置，查詢只要一次 I/O，是磁碟上最快的等值查詢結構。但磁碟上的雜湊與記憶體版本大不相同：雜湊表不能無限擴張，桶（bucket）必須對齊分頁，而「表格長大一倍」在磁碟上意味著重建整個檔案。本章介紹三個解法層次：靜態雜湊最簡單但無法成長；可擴展雜湊（extendible hashing）用目錄加倍來局部重組；線性雜湊（linear hashing）則完全拋棄目錄，以漸進分裂達到平滑擴張。

我們也會討論實務議題：鍵偏斜、溢位鏈、與範圍查詢為何不適合雜湊索引。學完本章，你將能在「查詢速度」與「擴張成本」之間為工作負載選出正確的雜湊結構。