6.4 散列技術(shù)
6.4.1 散列文件
1、 散列是一種快速查找技術(shù)，它利用定義在文件記錄上的查找碼，通過計(jì)算一個(gè)散列函數(shù)，以散列函數(shù)值作為記錄的物理地址，實(shí)現(xiàn)對(duì)文件記錄直接快速訪問。
2、 首先指定文件記錄的一個(gè)域作為查找碼(散列域)，然后定義一個(gè)查找碼上的函數(shù)(散列函數(shù))，函數(shù)的輸入為查找碼值，輸出為物理地址;
3、 一般使用桶作為基本的存儲(chǔ)單位，一個(gè)桶可存放多個(gè)文件記錄，物理地址可以是記錄所在的桶號(hào)，散列函數(shù)的輸出可以是桶號(hào);
6.4.2 散列函數(shù)
1、 散列方法依賴于好的散列函數(shù)，它應(yīng)該盡可能均勻地將查找碼分布到各個(gè)桶中，具體要滿足如下兩個(gè)條件：
(1) 地址的分布是均勻的;
(2) 地址的分布是隨機(jī)的;
6.4.3 桶溢出
1、 產(chǎn)生桶溢出的兩個(gè)原因：
(1) 文件初始設(shè)計(jì)時(shí)，為文件記錄預(yù)留的存儲(chǔ)空間不足;
(2) 散列函數(shù)的均勻分布性不好;
2、 設(shè)計(jì)散列函數(shù)時(shí)，應(yīng)根據(jù)文件大小決定物理空間，一般應(yīng)有20%余量，再設(shè)計(jì)合適的桶數(shù)目和桶大小，盡可能留有一些空閑桶，降低桶溢出的可能性;
3、 桶溢出的現(xiàn)象是難免的，需要DBS采用相應(yīng)的桶溢出處理機(jī)制;
4、 散列方法的缺點(diǎn)：為了避免桶溢出。必須選一合適的散列函數(shù)，但這比較復(fù)雜，而且不象索引文件那樣可以據(jù)數(shù)據(jù)記錄變化動(dòng)態(tài)調(diào)整。