Hash索引(數(shù)據(jù)庫)
時間：2022-12-25 22:30:01 | 來源：信息時代
時間：2022-12-25 22:30:01 來源：信息時代
Hash索引 : 也稱散列,其基本思想是利用Hash函數(shù)把檢索字段的值映射到桶號,從而找到待查數(shù)據(jù)項所在的頁。
Hash索引按照搜索鍵對數(shù)據(jù)項進行Hash,如圖1所示。
圖1 靜態(tài)Hash
Hash索引將搜索鍵及相應指針組織成Hash文件結構。Hash索引的構造如下,將Hash函數(shù)作用于搜索鍵以確定對應的桶,然后將此搜索鍵及相應指針存入此桶(或溢出桶,如果對應的主桶頁面已經(jīng)放滿)中。Hash索引既可用來組織文件結構也可用于索引結構。嚴格地說,Hash索引應該只表示輔助索引結構,而不能作為主索引結構,因為Hash索引不能保證索引鍵值之間的順序關系。
由于函數(shù)本身所具有的性質,不同的索引鍵值可能被Hash到相同的值,即同一個桶中,這種現(xiàn)象稱為Hash沖突。解決Hash沖突的一個自然的辦法是使用如圖1所示的溢出頁面鏈來保存發(fā)生沖突的索引記錄。一個Hash索引的查詢性能的好壞取決于溢出頁面鏈的長度,因此在溢出頁面鏈的查找時間是線性的。溢出頁面鏈的長度實際上取決于Hash函數(shù)的散列能力,因為Hash函數(shù)的散列能力越強,索引記錄就越能均勻地散列到各個主桶頁中,這樣溢出頁面鏈的長度就短。
在Hash索引上的隨機查詢過程非常簡單。首先使用相同的Hash函數(shù)將查詢鍵值進行Hash,得到該查詢鍵值所在的桶號,然后在對應的主桶頁中進行查找,如果找到就返回結果,如果找不到就順著對應的溢出頁面鏈查找,直到找到或到達溢出頁面鏈末端為止。
在線咨詢