數(shù)據(jù)庫(kù)系統(tǒng)課件：ch12 Indexing and Hashing

1、1索引與散列陳健華南理工大學(xué)軟件學(xué)院2Indexing-Introduction文件的索引就像書(shū)本的目錄一樣索引是一個(gè)數(shù)據(jù)結(jié)構(gòu)，它對(duì)存儲(chǔ)在磁盤上數(shù)據(jù)記錄進(jìn)行分類整理，目的是獲得更好的查詢速度。One-level IndexingPrimary indexingClustering indexingSecondary indexingmultilevel IndexingISAM (index-sequential access method)B+ tree陳健華南理工大學(xué)軟件學(xué)院3Indexing-Classification順序文件上的索引結(jié)構(gòu)非順序文件上的輔助索引 (Secondary I

2、ndexes)B+樹(shù)散列表 (Hash Tables)一、順序文件上的索引順序文件（ Sequential File ）Suitable for applications that require sequential processing of the entire file The records in the file are ordered by a search-key陳健華南理工大學(xué)軟件學(xué)院4陳健華南理工大學(xué)軟件學(xué)院5主索引(primary indexing)是建立在有序文件中的搜索碼字段上；搜索碼字段用于對(duì)磁盤上的文件記錄進(jìn)行物理排序。主索引是一個(gè)有序文件，它的每個(gè)記錄包含兩個(gè)字

3、段的定長(zhǎng)記錄。第1個(gè)字段與數(shù)據(jù)文件的搜索碼字段(即primary key)有相同的數(shù)據(jù)類型；第2個(gè)字段是指向一個(gè)數(shù)據(jù)塊的指針(塊地址)。對(duì)于數(shù)據(jù)文件中的每一塊，在索引文件中都對(duì)應(yīng)一個(gè)索引入口(index entry，或者索引記錄index record)。把索引記錄i的兩個(gè)字段值記作。一、順序文件上的索引search-keypointer陳健華南理工大學(xué)軟件學(xué)院61、主索引data block 0data block 1data block 2data block 3前三個(gè)索引入口索引入口的總數(shù)和有序數(shù)據(jù)文件所占的磁盤塊數(shù)相同。數(shù)據(jù)文件每一塊中的記錄叫做該塊的錨記錄(anchor record

4、，或塊錨block anchor)陳健華南理工大學(xué)軟件學(xué)院72、稠密索引(Dense Indexes)每個(gè)記錄都有一個(gè)索引項(xiàng)索引項(xiàng)按搜索碼排序Sequential File201040306050807010090Dense Index102030405060708090100110120索引項(xiàng)10搜索碼 指向記錄 地址的指針查找：查找索引項(xiàng)，跟蹤指針即可陳健華南理工大學(xué)軟件學(xué)院82、稠密索引(Dense Indexes)Sequential FileDense Index陳健華南理工大學(xué)軟件學(xué)院92、稠密索引(Dense Indexes)為什么使用稠密索引？記錄通常比索引項(xiàng)要大可以快速查找索

5、引（例如二分法）索引可以常駐內(nèi)存要搜索碼值為K的記錄是否存在，不需要訪問(wèn)磁盤數(shù)據(jù)塊稠密索引缺點(diǎn)？索引占用太多空間用稀疏索引改進(jìn)陳健華南理工大學(xué)軟件學(xué)院103、稀疏索引(Sparse Indexes)僅部分記錄有索引項(xiàng)一般情況：為每個(gè)數(shù)據(jù)塊的第一個(gè)記錄建立索引Sequential File201040306050807010090Sparse Index1030507090110130150170190210230查找：查找索引項(xiàng)，跟蹤指針找到數(shù)據(jù)塊，并在塊中順序查找索引項(xiàng)10搜索碼指向數(shù)據(jù)塊第一條記錄地址的指針陳健華南理工大學(xué)軟件學(xué)院11Sparse IndexesSequential Fil

6、eSparse Indexdata block 0data block 1data block 2陳健華南理工大學(xué)軟件學(xué)院123、稀疏索引(Sparse Indexes)有何優(yōu)點(diǎn)？節(jié)省了索引空間對(duì)同樣的記錄，稀疏索引可以使用更少的索引項(xiàng)有何缺點(diǎn)？對(duì)于“是否存在碼值為K的記錄？”，需要訪問(wèn)磁盤數(shù)據(jù)塊主索引對(duì)于數(shù)據(jù)文件的每個(gè)數(shù)據(jù)塊有一個(gè)入口，而不是對(duì)每個(gè)記錄都有一個(gè)入口，因此，主索引是稀疏索引。對(duì)于主索引：索引入口比數(shù)據(jù)文件中的記錄少；索引入口只包括兩個(gè)字段。從而，一個(gè)數(shù)據(jù)塊可以容納比數(shù)據(jù)記錄多很多的索引入口；因此，在索引文件上執(zhí)行二分查找比數(shù)據(jù)文件上的二分查找需要塊訪問(wèn)的次數(shù)更少。陳健華南理工大

7、學(xué)軟件學(xué)院134、存在重復(fù)碼值時(shí)的索引對(duì)于稠密索引為重復(fù)碼值建立重復(fù)索引項(xiàng)每個(gè)不同的碼值建立一個(gè)索引項(xiàng)對(duì)于稀疏索引為每個(gè)塊的第一個(gè)記錄建立索引項(xiàng)為每個(gè)塊的最小新碼值建立索引項(xiàng)陳健華南理工大學(xué)軟件學(xué)院144、存在重復(fù)碼值時(shí)的索引101020103020303045401010102020303030101020103020303045401010102020303030稠密索引：為重復(fù)碼值建立重復(fù)索引項(xiàng)查找：查找給定碼值的所有索引項(xiàng)，再跟蹤指針陳健華南理工大學(xué)軟件學(xué)院154、存在重復(fù)碼值時(shí)的索引101020103020303050401020304050607080稠密索引：每個(gè)不同碼值建立一個(gè)

8、索引項(xiàng)查找：查找給定碼值的索引項(xiàng)（一個(gè)），然后跟蹤指針，并繼續(xù)查找后面的數(shù)據(jù)塊陳健華南理工大學(xué)軟件學(xué)院164、存在重復(fù)碼值時(shí)的索引1010201030203030454010102030稀疏索引：每個(gè)塊的首記錄建立一個(gè)索引項(xiàng)查找：找到給定碼值的第一個(gè)索引項(xiàng)，找到塊，查找塊以及后續(xù)塊，還要查找該塊的前一塊陳健華南理工大學(xué)軟件學(xué)院174、存在重復(fù)碼值時(shí)的索引1010302030304030505010204050稀疏索引：每個(gè)塊的最小新碼值建立一個(gè)索引項(xiàng)查找：找到給定碼值的第一個(gè)索引項(xiàng)，找到塊，查找塊以及后續(xù)塊陳健華南理工大學(xué)軟件學(xué)院185、多級(jí)索引(Multi-level Index)索引上再建

9、索引二級(jí)索引三級(jí)索引一級(jí)索引塊的塊地址指針陳健華南理工大學(xué)軟件學(xué)院195、多級(jí)索引(Multi-level Index)多級(jí)索引的好處？一級(jí)索引可能還太大而不能常駐內(nèi)存查找一級(jí)索引塊需要某種數(shù)據(jù)結(jié)構(gòu)和磁盤I/O二級(jí)索引更小，可以常駐內(nèi)存減少磁盤I/O次數(shù)陳健華南理工大學(xué)軟件學(xué)院205、多級(jí)索引(Multi-level Index)例：一塊4KB。一級(jí)索引10,000個(gè)塊，每個(gè)塊可存100個(gè)索引項(xiàng)，共40MB。二級(jí)稀疏索引100個(gè)塊，共400KB。按一級(jí)索引查找：平均 log21000013 次I/O定位索引塊，加一次數(shù)據(jù)塊I/O，共約14次I/O按二級(jí)索引查找：定位二級(jí)索引塊0次I/O，讀入一

10、級(jí)索引塊1次I/O，讀入數(shù)據(jù)塊1次I/O，共2次I/O陳健華南理工大學(xué)軟件學(xué)院215、多級(jí)索引(Multi-level Index)當(dāng)一級(jí)索引過(guò)大而二級(jí)索引可常駐內(nèi)存時(shí)有效二級(jí)索引僅可用稀疏索引思考：二級(jí)稠密索引有用嗎？一般不考慮三級(jí)以上索引維護(hù)多級(jí)索引結(jié)構(gòu)有更好的索引結(jié)構(gòu)B樹(shù)陳健華南理工大學(xué)軟件學(xué)院226、索引順序文件上的修改索引順序文件上的修改動(dòng)作創(chuàng)建或刪除一個(gè)空存儲(chǔ)塊創(chuàng)建或刪除一個(gè)溢出塊插入一條記錄到一個(gè)空塊中刪除記錄將記錄移動(dòng)相鄰的塊中陳健華南理工大學(xué)軟件學(xué)院236、索引順序文件上的修改修改動(dòng)作對(duì)索引的影響 行為 稠密索引 稀疏索引創(chuàng)建空溢出塊 無(wú) 無(wú)刪除空溢出塊 無(wú) 無(wú)創(chuàng)建空順序塊

11、無(wú) 插入刪除空順序塊 無(wú) 刪除插入記錄 插入 更新？刪除記錄 刪除 更新？移動(dòng)記錄 更新 更新？陳健華南理工大學(xué)軟件學(xué)院246、索引順序文件上的修改例子20104030605080701030507090110130150稀疏索引上的刪除：刪除30陳健華南理工大學(xué)軟件學(xué)院256、索引順序文件上的修改例子20104040605080701040507090110130150稀疏索引上的刪除：刪除30，塊外指針不能指向塊內(nèi)記錄MovedUpdated陳健華南理工大學(xué)軟件學(xué)院266、索引順序文件上的修改例子20104030605080701030507090110130150 delete reco

12、rds 30 & 405070陳健華南理工大學(xué)軟件學(xué)院27二、輔助索引(Secondary Index)主索引（Primary Index）順序文件上的索引記錄按索引屬性值有序根據(jù)索引值可以確定記錄的位置輔助索引(Secondary Index)數(shù)據(jù)文件不需要按搜索碼有序根據(jù)索引值不能確定記錄在文件中的順序陳健華南理工大學(xué)軟件學(xué)院281、輔助索引概念Name上創(chuàng)建了主索引，記錄按name有序Address上創(chuàng)建輔助索引Create Index adIndex On MovieStar(address)MovieStar(name char(10) PRIMARY KEY, address ch

13、ar(20)陳健華南理工大學(xué)軟件學(xué)院291、輔助索引概念輔助索引只能是稠密索引稀疏的輔助索引有意義嗎？陳健華南理工大學(xué)軟件學(xué)院301、輔助索引概念50307020408010100609030208010090.No sense！有助于查詢碼值為10的記錄嗎？陳健華南理工大學(xué)軟件學(xué)院312、輔助索引設(shè)計(jì)50307020408010100609010203040506070.稠密索引陳健華南理工大學(xué)軟件學(xué)院322、輔助索引設(shè)計(jì)50307020408010100609010203040506070.稠密索引105090.二級(jí)稀疏索引陳健華南理工大學(xué)軟件學(xué)院333、輔助索引中的間接桶Indirect

14、 Bucket重復(fù)碼值采用稠密索引浪費(fèi)空間間接桶介于輔助索引和數(shù)據(jù)文件之間陳健華南理工大學(xué)軟件學(xué)院343、輔助索引中的間接桶10204020401040104030102030405060.buckets搜索碼值大于指針時(shí)節(jié)省空間陳健華南理工大學(xué)軟件學(xué)院35Where we are？順序文件上的索引結(jié)構(gòu)非順序文件上的輔助索引 (Secondary Indexes)B+樹(shù)散列表 (Hash Tables)Next陳健華南理工大學(xué)軟件學(xué)院36三、B+樹(shù)一種樹(shù)型的多級(jí)索引結(jié)構(gòu)樹(shù)的層數(shù)與數(shù)據(jù)大小相關(guān)，通常為3層所有結(jié)點(diǎn)格式相同：n個(gè)值，n1個(gè)指針?biāo)腥~結(jié)點(diǎn)位于同一層適用于主索引，也可用于輔助索引陳健華

15、南理工大學(xué)軟件學(xué)院371、葉結(jié)點(diǎn) 1個(gè)指向相鄰葉結(jié)點(diǎn)的指針 n對(duì)鍵指針對(duì) 至少(n+1)/2 個(gè)指針指向碼值account的B+樹(shù)索引上的一個(gè)葉結(jié)點(diǎn)陳健華南理工大學(xué)軟件學(xué)院38陳健華南理工大學(xué)軟件學(xué)院392、中間結(jié)點(diǎn) n個(gè)碼值劃分n+1個(gè)子樹(shù) 第 i 個(gè)碼值是第 i+1 個(gè)子樹(shù)中的最小碼值 至少 (n+1)/2 個(gè)指針指向子樹(shù) 根結(jié)點(diǎn)至少 2 個(gè)指針陳健華南理工大學(xué)軟件學(xué)院40B+樹(shù)結(jié)點(diǎn)例子n3陳健華南理工大學(xué)軟件學(xué)院413、B+樹(shù)查找從根結(jié)點(diǎn)開(kāi)始沿指針向下，直到到達(dá)葉結(jié)點(diǎn)在葉結(jié)點(diǎn)中順序查找Find record with search-key value V.C=rootWhile C is

16、 not a leaf node Let i be least value s.t. V Ki.If no such exists, set C = last non-null pointer in C Else if (V= Ki ) Set C = Pi +1 else set C = PiLet i be least value s.t. Ki = VIf there is such a value i, follow pointer Pi to the desired record.Else no record with search-key value k exists.3、B+樹(shù)查

17、找算法B+樹(shù)查找分析If there are K search-key values in the file, the height of the tree is no more than logn/2(K).A node is generally the same size as a disk block, typically 4 kilobytesand n is typically around 100 (40 bytes per index entry).With 1 million search key values and n = 100at most log50(1,000,00

18、0) = 4 nodes are accessed in a lookup.Contrast this with a balanced binary tree with 1 million search key values around 20 nodes are accessed in a lookupabove difference is significant since every node access may need a disk I/O, costing around 20 milliseconds陳健華南理工大學(xué)軟件學(xué)院444、B+樹(shù)插入查找插入葉結(jié)點(diǎn)若葉結(jié)點(diǎn)中有空閑位置（鍵

19、），則插入若沒(méi)有空間，則分裂葉結(jié)點(diǎn)葉結(jié)點(diǎn)的分裂可視作是父結(jié)點(diǎn)中插入一個(gè)子結(jié)點(diǎn)遞歸向上分裂分裂過(guò)程中需要對(duì)父結(jié)點(diǎn)中的鍵加以調(diào)整例外：若根結(jié)點(diǎn)分裂，則需要?jiǎng)?chuàng)建一個(gè)新的根結(jié)點(diǎn)陳健華南理工大學(xué)軟件學(xué)院45B+樹(shù)插入例子(a) Insert key = 32n=3351130313010032陳健華南理工大學(xué)軟件學(xué)院46B+樹(shù)插入例子(b) Insert key = 7n=335113031301003577陳健華南理工大學(xué)軟件學(xué)院47B+樹(shù)插入例子(c) Insert key = 160n=3100120150180150156179180200160180160179陳健華南理工大學(xué)軟件學(xué)院48B+

20、樹(shù)插入例子(d) New root, insert 45n=31020301231012202530324040454030new root陳健華南理工大學(xué)軟件學(xué)院495、B+樹(shù)刪除查找要?jiǎng)h除的碼值，并刪除之若結(jié)點(diǎn)的碼值填充低于規(guī)定值，則調(diào)整若相鄰的葉結(jié)點(diǎn)中鍵填充高于規(guī)定值，則將其中一個(gè)碼值移到該結(jié)點(diǎn)中否則，合并該結(jié)點(diǎn)與相鄰結(jié)點(diǎn)合并可視作在父結(jié)點(diǎn)中刪除一個(gè)子結(jié)點(diǎn)遞歸向上刪除若刪除的是葉結(jié)點(diǎn)中的最小碼值，則需對(duì)父結(jié)點(diǎn)的碼值加以調(diào)整陳健華南理工大學(xué)軟件學(xué)院50B+樹(shù)刪除例子(a) Simple deleteDelete 3010401001020304050n=4陳健華南理工大學(xué)軟件學(xué)院51B+樹(shù)

21、刪除例子(b) Coalesce with siblingDelete 50104010010204050n=440陳健華南理工大學(xué)軟件學(xué)院52B+樹(shù)刪除例子(c) Redistribute keysDelete 501040100102030354050n=43535陳健華南理工大學(xué)軟件學(xué)院536、B+樹(shù)的效率訪問(wèn)索引的I/O代價(jià)樹(shù)高（B樹(shù)不常駐內(nèi)存）0（常駐內(nèi)存）樹(shù)高通常不超過(guò)3層，因此索引I/O代價(jià)不超過(guò)3（總代價(jià)不超過(guò)4）通常情況下，根節(jié)點(diǎn)常駐內(nèi)存，因此索引I/O代價(jià)不超過(guò)2（總代價(jià)不超過(guò)3）陳健華南理工大學(xué)軟件學(xué)院546、B+樹(shù)的效率設(shè)塊大小8KB，鍵2B（smallint），指針2

22、B，則一個(gè)塊可放2048個(gè)索引項(xiàng)層數(shù)索引大?。▔K數(shù)/大?。┧饕涗浛臻g11/8KB20472(12048)/約16M約419萬(wàn)(222)3(1+211+222)/約32G約85億(233)陳健華南理工大學(xué)軟件學(xué)院55Where we are？順序文件上的索引結(jié)構(gòu)非順序文件上的輔助索引 (Secondary Indexes)B+樹(shù)散列表 (Hash Tables)Next陳健華南理工大學(xué)軟件學(xué)院56四、散列表(Hash Table)散列函數(shù)(Hash Functions)h：搜索碼(散列鍵) 0B 1桶(Buckets), numbered 0,1, B-1散列索引方法給定一個(gè)搜索碼K，對(duì)應(yīng)的記

23、錄必定位于桶h(K)中若一個(gè)桶中僅一塊，則 I/O次數(shù)1否則由參數(shù)B決定，平均總塊數(shù)/B陳健華南理工大學(xué)軟件學(xué)院571、散列表概念Kh(K)decbaf0123Hash Function2 records/block1 block/bucketh(a)=h(f)=3h(d)=0h(e)=h(c)=1h(b)=2陳健華南理工大學(xué)軟件學(xué)院58Example of Hash File OrganizationThere are 10 buckets,The binary representation of the ith character is assumed to be the integer

24、i.The hash function returns the sum of the binary representations of the characters modulo 10E.g. h(Perryridge) = 5 h(Round Hill) = 3 h(Brighton) = 3Hash file organization of account file, using branch_name as key (See figure in next slide.)陳健華南理工大學(xué)軟件學(xué)院59Example of Hash File Organization Hash file o

25、rganization of account file, using branch_name as key(see previous slide for details).陳健華南理工大學(xué)軟件學(xué)院602、散列表查找查找對(duì)于給定的散列碼值K，計(jì)算h(K)根據(jù)h(K)定位桶查找桶中的塊h(Perryridge) = 5 陳健華南理工大學(xué)軟件學(xué)院613、散列表插入計(jì)算插入記錄的h(K)，定位桶若桶中有空間，則插入否則創(chuàng)建一個(gè)溢出塊并將記錄置于溢出塊中陳健華南理工大學(xué)軟件學(xué)院62插入例子decbaf0123g插入g，h(g)=1Overflow BlockHash Tableh(a)=h(f)=3h(

26、d)=0h(e)=h(c)=1h(b)=2陳健華南理工大學(xué)軟件學(xué)院633、散列表刪除根據(jù)給定碼值K計(jì)算h(K)，定位桶和記錄刪除回收溢出塊？陳健華南理工大學(xué)軟件學(xué)院64散列表刪除例子0123abcedEXAMPLE: deletionDelete:effgmaybe move“g” upcd陳健華南理工大學(xué)軟件學(xué)院654、散列表空間利用率問(wèn)題空間利用率實(shí)際碼值數(shù) / 所有桶可放置的碼值數(shù)80：溢出問(wèn)題50到80之間（GOOD！）陳健華南理工大學(xué)軟件學(xué)院665、文件增長(zhǎng)數(shù)據(jù)文件的增長(zhǎng)使桶的溢出塊數(shù)增多，增加I/O采用動(dòng)態(tài)散列表解決可擴(kuò)展散列表（Extensible Hash Tables）成倍增

27、加桶數(shù)目線性散列表（Linear Hash Tables）線性增加陳健華南理工大學(xué)軟件學(xué)院676、可擴(kuò)展散列表散列函數(shù)h(k)是一個(gè)b(足夠大)位二進(jìn)制序列，前i位表示桶的數(shù)目。i的值隨數(shù)據(jù)文件的增長(zhǎng)而增大00110101bib位二進(jìn)制序列，前i位用于區(qū)分桶h(k)陳健華南理工大學(xué)軟件學(xué)院686、可擴(kuò)展散列表前i位構(gòu)成一個(gè)桶數(shù)組1000121001101021100000110112i =0111b4i2h(k)的前i位桶陳健華南理工大學(xué)軟件學(xué)院69Dynamic Hashing Represent the hash value of each record in binary.E.g., t

28、he hash value of “Brighton” = 93 = (00101101111110110010110000110000)2陳健華南理工大學(xué)軟件學(xué)院70ExampleThe original table陳健華南理工大學(xué)軟件學(xué)院71in memoryAt the beginning (when no tuple is inserted), there is only one empty bucket.We keep, in memory, a bucket address table.Next we see how the hash structure changes as mo

29、re and more tuples are inserted.Example陳健華南理工大學(xué)軟件學(xué)院72InsertionAssume each page can hold 2 records. Situation after inserting 2 records:The original tableThe next insertion incurs a page overflow.A-217 Brighton 750 A-101 Downtown 500 - 陳健華南理工大學(xué)軟件學(xué)院73Page Overflow Handlinginserting:A-217 Brighton 750

30、A-101 Downtown 500 - A110 Downtown 600 Split the page into 2.Distribute the records using the first bit of their binary representation.Note the changes here:These two “1” indicate these two buckets were split based on the first bit.陳健華南理工大學(xué)軟件學(xué)院74Page Overflow Handling (cont.)Need to double the addre

31、ss table. 0 1Note陳健華南理工大學(xué)軟件學(xué)院75Insertion (Cont.)0 1Inserting the next record “Mianus” incurs another overflow.The original table陳健華南理工大學(xué)軟件學(xué)院76Handling OverflowSplit the overflowing page into 2.Distribute the records using the first 2 bits of their binary representation.Note the changes in the red ci

32、rcles.Also need to double the bucket address table.0 1陳健華南理工大學(xué)軟件學(xué)院77Handling OverflowDouble the bucket address table.Note two pointers are pointing to the first bucket.Question: How do we find accounts in “Downtown” using the current hash table?陳健華南理工大學(xué)軟件學(xué)院78Insertion (Cont.)Inserting the next recor

33、d “A-102 Perryridge 400”.The original table陳健華南理工大學(xué)軟件學(xué)院79Insertion (Cont.)Inserting the next record “A-102 Perryridge 400”.陳健華南理工大學(xué)軟件學(xué)院80Insertion (Cont.)Inserting the next record “A-201 Perryridge 900” = overflows.The original table陳健華南理工大學(xué)軟件學(xué)院81Insertion (Cont.)Inserting the next record “A-201 Per

34、ryridge 900” = overflows.陳健華南理工大學(xué)軟件學(xué)院82Insertion (Cont.)Inserting the next record “A-218 Perryridge 700” = overflows.Should we split the 4-th bucket?NO!Why?Overflow still exists try it yourself.The original table陳健華南理工大學(xué)軟件學(xué)院83Insertion (Cont.)Hash structure after inserting three Perryridge records陳健

35、華南理工大學(xué)軟件學(xué)院84Insertion (Cont.)Final structure after all insertions.The original tableInserting the next record “A-222 Redwood 700” Inserting the next record “A-305 Round Hill 350” 陳健華南理工大學(xué)軟件學(xué)院85Insertion (Cont.)Final structure after all insertions.陳健華南理工大學(xué)軟件學(xué)院866、可擴(kuò)展散列表優(yōu)點(diǎn)： 當(dāng)查找記錄時(shí)，只需查找一個(gè)存儲(chǔ)塊。缺點(diǎn)： 桶增長(zhǎng)速度快

36、，可能會(huì)導(dǎo)致內(nèi)存放不下整個(gè)桶數(shù)組，影響其他保存在主存中的數(shù)據(jù)，波動(dòng)較大。陳健華南理工大學(xué)軟件學(xué)院877、線性散列表h(k)仍是二進(jìn)制位序列，但使用右邊(低)i位區(qū)分桶桶數(shù)n，h(k)的右i位m若mn，則記錄位于第m個(gè)桶若n m 2i,則記錄位于第 m-2i-1 個(gè)桶n的選擇：總是使n與當(dāng)前記錄總數(shù)r保持某個(gè)固定比例意味著只有當(dāng)桶的填充度達(dá)到超過(guò)某個(gè)比例后桶數(shù)才開(kāi)始增長(zhǎng)例子兩個(gè)桶，每個(gè)桶占一個(gè)存儲(chǔ)塊，桶的編號(hào)為0和1。所有散列值以0結(jié)尾的記錄存入第一個(gè)桶，而所有散列值以1結(jié)尾的記錄存入第二個(gè)桶。參數(shù)i(當(dāng)前被使用的散列函數(shù)值的位數(shù))、n（當(dāng)前的桶數(shù)）和r（當(dāng)前散列表中的記錄總數(shù)）也是這一結(jié)構(gòu)的一部分。比率r/n將受到限制，使一般的桶都只 需要約一個(gè)磁盤存儲(chǔ)塊。在選擇桶數(shù)n時(shí)，采用的策略是使數(shù)據(jù)文件中記錄的個(gè)數(shù)不超過(guò)1.7n，即r1.7n。陳健華南理工大學(xué)軟