索引與散列實(shí)用教案

1、內(nèi)容提要(ni rn t yo) 1 索引 1.1 作用 1.2 分類及術(shù)語 1.3 SQL中索引的定義 2 樹型索引 2.1 靜態(tài)(jngti)索引ISAM 2.2 動(dòng)態(tài)索引B+Tree 3散列索引 3.1 散列文件 3.2 散列索引 3.3 可擴(kuò)充的散列索引 多碼訪問第1頁/共54頁第一頁，共54頁。1 概述(i sh) 有時(shí)要通過限定某些列的取值來查找數(shù)據(jù) 如：在學(xué)生表里，查找系別是計(jì)算機(jī)的學(xué)生 查找年齡小于18的學(xué)生。 文件上的索引是基于磁盤的數(shù)據(jù)結(jié)構(gòu)，它能加快查找特定條件數(shù)據(jù)的速度。 一個(gè)關(guān)系的列的所有子集都可能做為一個(gè)查詢條件。 索引鍵（搜索碼）不一定(ydng)是關(guān)系的主鍵。 一

2、個(gè)索引包含一個(gè)數(shù)據(jù)入口的集合，根據(jù)檢索碼，支持高效檢索所有符合條件的數(shù)據(jù)。第2頁/共54頁第二頁，共54頁。1.1 問題(wnt) 使用(shyng)索引支持什么樣的選擇? 選擇的條件如：fieldNamevalue 等值選擇：= 范圍選擇：,=,=,between 更復(fù)雜的選擇 兩維范圍查詢：長江以北，黃河以南；京廣線以西，京九線以東的地區(qū)。 兩維距離查詢：北京200公里內(nèi)的地區(qū)。 查詢結(jié)果排序：離北京最近的10個(gè)地級(jí)城市。 染色體組匹配 常見的n維索引：R-tree(oracle中支持)第3頁/共54頁第三頁，共54頁。1.2 索引(suyn)的分類 支持什么樣的選擇:范圍、等值 索引中數(shù)

3、據(jù)(shj)入口的表示 1、真實(shí)數(shù)據(jù)(shj) 2、 3、 聚集（ Clustered ）索引與非聚集索引 單鍵索引與復(fù)合鍵索引 基于樹的索引、基于hash的索引 稀疏索引與稠密索引注：一個(gè)文件可以有多個(gè)索引。一般來講，索引含有些輔助信息幫助找到所需的數(shù)據(jù)(shj)入口。第4頁/共54頁第四頁，共54頁。1.2 索引(suyn)項(xiàng)中是真實(shí)數(shù)據(jù)的索引(suyn) 該索引結(jié)構(gòu)是數(shù)據(jù)組織在一起的文件（如堆文件或索引文件）。 在一個(gè)給定的數(shù)據(jù)集上，只能(zh nn)有一個(gè)這樣的索引。即只能(zh nn)排一個(gè)次序存放數(shù)據(jù)。 節(jié)省用指針?biāo)阉鲾?shù)據(jù)的時(shí)間，但插入數(shù)據(jù)與刪除數(shù)據(jù)開銷大。第5頁/共54頁第五頁，

4、共54頁。1.2 索引(suyn)中數(shù)據(jù)入口的表示2、3、對(duì)于上面的兩種方案來說，比存放真實(shí)數(shù)據(jù)的要易于維護(hù)。方案3比2要節(jié)省空間(kngjin)，但要用變長記錄，且長度不定，有可能超過磁盤塊的大小。第6頁/共54頁第六頁，共54頁。1.2 聚集(jj)與非聚集(jj)索引 聚集索引：如果搜索碼值順序與記錄的物理順序一致，那么在這個(gè)搜索碼上建立的索引就是主索引，主索引也叫聚集索引。 假定(jidng)索引項(xiàng)采用形式，且數(shù)據(jù)記錄存儲(chǔ)在一個(gè)堆文件中。Index entriesData entriesdirect search for (Index File)(Data file)Data Reco

5、rdsdata entriesData entriesData RecordsCLUSTEREDUNCLUSTERED第7頁/共54頁第七頁，共54頁。1.2 采用聚集(jj)索引的利弊 好處 有利于范圍選擇。 可以有一定程度的壓縮（稀疏索引）。 由于(yuy)位置的原因，帶來好的效益。（按所排序訪問數(shù)據(jù)，減少I/O） 弊 維護(hù)較復(fù)雜,立即或批量整理。第8頁/共54頁第八頁，共54頁。1.2稀疏(xsh)索引與稠密索引Data Records稠密索引Data Records稀疏索引第9頁/共54頁第九頁，共54頁。1.2 復(fù)合(fh)索引 在列的組合上建立 為何需要復(fù)合索引？單獨(dú)的條件查找的結(jié)

6、果都很多，結(jié)合在一起的查詢(chxn)結(jié)果一般卻很少?；驈?fù)合條件查詢(chxn)的比例特別高。第10頁/共54頁第十頁，共54頁。1.2 多級(jí)索引(suyn) 多級(jí)索引：象對(duì)待任何其他順序文件那樣(nyng)來對(duì)待索引結(jié)構(gòu)，即在主索引上再構(gòu)造一個(gè)稀疏索引，以避免要訪問的索引結(jié)構(gòu)過于龐大而影響性能；索索引引塊塊1 1.數(shù)據(jù)塊數(shù)據(jù)塊0 0數(shù)據(jù)塊數(shù)據(jù)塊1 1數(shù)據(jù)塊數(shù)據(jù)塊m m數(shù)據(jù)塊數(shù)據(jù)塊n n索索引引塊塊0 0外層索引外層索引內(nèi)層索引內(nèi)層索引第11頁/共54頁第十一頁，共54頁。1.3 SQL1.3 SQL中索引中索引(suyn)(suyn)的定義的定義創(chuàng)建索引(suyn)create index

7、on ()create index stdno_index on students (stdno)刪除索引(suyn)drop index Drop index stdno_index第12頁/共54頁第十二頁，共54頁。2 樹形索引(suyn) 樹形索引支持等值檢索與范圍檢索。 有多種索引方法可以對(duì)數(shù)據(jù)進(jìn)行定位，對(duì)于同一數(shù)據(jù)可以有多個(gè)索引。 ISAM: 靜態(tài)的結(jié)構(gòu); B+ tree: 動(dòng)態(tài)結(jié)構(gòu), 在插入(ch r)與刪除時(shí)處理得很好。 ISAM: Indexed Sequential Access Method 是一種很老的索引方法，通常來講B+Tree會(huì)更好些。 比B+tree簡單，但有許

8、多相似的思想。第13頁/共54頁第十三頁，共54頁。2 樹形檢索(jin su)與二分查找 對(duì)于排序后的數(shù)據(jù)，通過二分查找有助于加快索引速度。 平均檢索時(shí)間是O(log2n)。若每次都要訪問一次磁盤(c pn)，需要O(log2n)次訪盤。當(dāng)n很大時(shí)，需要的I/O會(huì)難以接受。 解決辦法，2-大。通過創(chuàng)建索引，加大每次查找的分支來實(shí)現(xiàn)。Page 1Page 2Page NPage 3Data Filek2kNk1Index File第14頁/共54頁第十四頁，共54頁。2.1 ISAM 為什么要按頁組織各個(gè)(gg)節(jié)點(diǎn)？P0K1P1K2P2KmPmindex entry* 葉子 包含數(shù)據(jù)入口No

9、n-leafPagesPagesOverflow pagePrimary pagesLeaf第15頁/共54頁第十五頁，共54頁。2.1 ISAM說明(shumng) 文件的創(chuàng)建：先創(chuàng)建頁（數(shù)據(jù)）結(jié)點(diǎn)，并按索引碼排序； 然后創(chuàng)建索引頁。 在插入記錄時(shí)根據(jù)需要分配溢出頁。 索引項(xiàng)是，由它來引導(dǎo)檢索，找到數(shù)據(jù)。 插入：到對(duì)應(yīng)的頁然后插入，若沒有剩余空間，使用溢出頁。 刪除：找到所在(suzi)的頁，然后刪除，可能回收溢出頁。 靜態(tài)結(jié)構(gòu)：插入、刪除不影響非葉結(jié)點(diǎn)的結(jié)構(gòu)，這些結(jié)構(gòu)在創(chuàng)建時(shí)就確定了。第16頁/共54頁第十六頁，共54頁。2.1 例子(l zi)10*15*20*27*33*37*40*4

10、6*51*55*63*97*2033516340索引的根KKl=數(shù)據(jù)(shj)kK=數(shù)據(jù)(shj)krKlKr第17頁/共54頁第十七頁，共54頁。2.1 例子(l zi) 插入(ch r) 23*, 48*, 41*, 42* .10*15*20*27*33*37*40*46*51*55*63*97*2033516340Root23*48*41*42*OverflowPagesLeafIndexPagesPagesPrimary第18頁/共54頁第十八頁，共54頁。2.1 例子(l zi) 然后(rnhu)，刪除 42*, 51*, 97*注意 51出現(xiàn)在索引中, 但是51*在數(shù)據(jù)(shj)

11、頁上沒有 !10*15*20*27*33*37*40*46*55*63*2033516340Root23*48*41*第19頁/共54頁第十九頁，共54頁。2.2 B+Tree:使用(shyng)最廣的索引 插入、刪除的代價(jià)(diji)也是O(log F N )。其中F稱為扇出系數(shù)；N為頁結(jié)點(diǎn)的數(shù)目。 除了根結(jié)點(diǎn)外，其它的節(jié)點(diǎn)至少是半滿的。每個(gè)結(jié)點(diǎn)包含d = m = 24*的所有數(shù)據(jù) .Root1724302*3*5*7*14* 16*19* 20* 22*24* 27* 29*33* 34* 38* 39*13第21頁/共54頁第二十一頁，共54頁。2.2 實(shí)際(shj)中的B+Tree(假

12、定( jidng)OS頁面8192Bytes)典型的級(jí): 100. 典型的填充系數(shù): 67%.平均扇出 = 133典型容量:樹高4: 1334 = 312,900,700 條記錄樹高3: 1333 = 2,352,637 條記錄經(jīng)常將上面幾層常駐內(nèi)存Level 1 = 1 page = 8 KbytesLevel 2 = 133 pages = 1 MbyteLevel 3 = 17,689 pages = 133 MBytes 第22頁/共54頁第二十二頁，共54頁。2.2.1插入(ch r) 1、找到正確的葉結(jié)點(diǎn)L。 2、準(zhǔn)備把數(shù)據(jù)入口插入該結(jié)點(diǎn) 若當(dāng)前(dngqin)結(jié)點(diǎn)有空間，插入。

13、否則，L分裂成L,L 在L,L上平均分配原有L的數(shù)據(jù)入口。 將中間值(L的第一個(gè)索引碼)與指向L的指針插入L的父結(jié)點(diǎn)。 3、遞歸執(zhí)行 若該結(jié)點(diǎn)需要分裂，將后一半索引項(xiàng)分到新結(jié)點(diǎn)，并將中間項(xiàng)刪除后與指向新節(jié)點(diǎn)的指針插入到父節(jié)點(diǎn)。 4、根節(jié)點(diǎn)的分裂將導(dǎo)致樹增高一層。 樹可以向?qū)捲鲩L，也可以向高增長。第23頁/共54頁第二十三頁，共54頁。2.2.1 插入(ch r)8*Root1724302*3*5*7*14* 16*19* 20* 22*24* 27* 29*33* 34* 38* 39*132*3*Root17243014* 16*19* 20* 22*24* 27*29*33* 34* 38

14、* 39*1357*5*8*插入(ch r)8*第24頁/共54頁第二十四頁，共54頁。2.2.1 Inserting 8* 葉節(jié)點(diǎn)( ji din)與內(nèi)部節(jié)點(diǎn)( ji din)都盡量少占用空間。 為什么拷貝，為什么移動(dòng)？2*3*5*7*8*5拷上來的.524301713移上來的B+Tree葉節(jié)點(diǎn)(ji din)分裂B+Tree內(nèi)部節(jié)點(diǎn)(ji din)分裂第25頁/共54頁第二十五頁，共54頁。2.2.2 從 B+ Tree刪除一數(shù)據(jù)(shj)入口 1、從根節(jié)點(diǎn)開始，找到數(shù)據(jù)入口所在的葉節(jié)點(diǎn)L。 2、刪除該數(shù)據(jù)入口后 若L至少是半滿的（m=d）,結(jié)束。 若L不是半滿的（m=d-1），則試圖從相

15、同父親的兄弟結(jié)點(diǎn)分來一個(gè)。 若重新分配失敗(shbi)，則將L與它的兄弟節(jié)點(diǎn)合并。 3、若進(jìn)行了合并，則在L的父節(jié)點(diǎn)中刪除指向L或那個(gè)兄弟節(jié)點(diǎn)的項(xiàng)。 4、合并可能向上傳遞，直到根節(jié)點(diǎn)，降低B+Treed的高度。第26頁/共54頁第二十六頁，共54頁。2.2.2 例： 刪除(shnch) 19*刪除(shnch)19*2* 3*Root17243014*16*19*20*22*24* 27*29*33*34*38*39*1357*5*8*2*3*Root17243014* 16*20*22* 24* 27*29*33* 34* 38* 39*1357*5*8*第27頁/共54頁第二十七頁，共54

16、頁。2.2.2 例：刪除(shnch) 20* .2*3*Root173014* 16*33* 34*38* 39*1357*5*8*22*24*2727* 29*2*3*Root17243014* 16*20*22* 24* 27*29*33* 34* 38* 39*1357*5*8*刪除(shnch)20從右兄弟(xingd)分配第28頁/共54頁第二十八頁，共54頁。2.2.2 例：刪除(shnch)24*2*3*Root173014* 16*33* 34*38* 39*1357*5*8*22*24*2727* 29*刪除(shnch)24*3022*27*29*33*34*38*39*

17、（轉(zhuǎn)下頁）第29頁/共54頁第二十九頁，共54頁。2.2.2 例：刪除(shnch)24*Root14* 16*22*27* 29*2*3*173033* 34*38* 39*1357*5*8*（接上頁）2*3*7*14* 16*22* 27*29*33* 34* 38* 39*5*8*Root3013517合并(hbng)第30頁/共54頁第三十頁，共54頁。2.2.2 例：內(nèi)部(nib)節(jié)點(diǎn)重新分配Root1351720223014*16*17*18*20*33*34*38*39*22*27*29*21*7*5*8*3*2*刪除(shnch)時(shí)的中間狀態(tài)重新分配14*16*33*34*38

18、*39*22*27*29*17*18*20*21*7*5*8*2* 3*Roo左兄弟(xingd)分配重新分配索引項(xiàng)為20的就能滿足要求了；重新分配17是為了進(jìn)一步說明.第31頁/共54頁第三十一頁，共54頁。2.2.3 搜索(su su)碼值壓縮 在索引項(xiàng)中，搜索碼值只起導(dǎo)向的作用，比較出大小(dxio)即可，不要求精確，故可以壓縮。如：搜索碼值abch把 所有的數(shù)據(jù)分為,abcg與abci,兩部分。則，搜索碼值abch在索引中可以簡記為：abch。通過它能進(jìn)行相同的引導(dǎo)。 能增大扇出系數(shù)嗎？為什么？第32頁/共54頁第三十二頁，共54頁。2.2.4 B+Tree的

19、大批(dp)裝載(Bulk-Loading)有時(shí)需要一次增加很多的數(shù)據(jù)。方案(fng n)1：一次插入一條，很慢。方案(fng n)2：針對(duì)要插入的數(shù)據(jù)，對(duì)索引的數(shù)據(jù)入口按照搜索碼值排序，然后在原有的B+Tree中插入這些數(shù)據(jù)入口。方案(fng n)3：刪除原有的B+Tree索引，然后對(duì)索引項(xiàng)按照搜索碼值排序，最后重新創(chuàng)建B+Tree。第33頁/共54頁第三十三頁，共54頁。2.2.4根據(jù)排序(pi x)的數(shù)據(jù)入口創(chuàng)建B+TreeSorted pages of data entries; not yet in B+ tree3* 4*6* 9*10*11* 12*13* 20*22* 23*3

20、1* 35*36* 38*41* 44*Root3* 4*6* 9* 10*11* 12*13*20*22*23*31*35*36* 38*41* 44*RootData entry pages not yet in B+ tree352312610 20指向葉節(jié)點(diǎn)的索引(suyn)項(xiàng)總是進(jìn)入上層的最右節(jié)點(diǎn)。當(dāng)它充滿時(shí)，便分裂。（轉(zhuǎn)下頁）第34頁/共54頁第三十四頁，共54頁。2.2.4 根據(jù)排序的數(shù)據(jù)(shj)入口創(chuàng)建B+Tree3*4*6*9*10* 11*12* 13*20* 22*23* 31*35* 36*38* 41*44*6Root101223203538not yet in B

21、+ tree3*4*6*9*10* 11*12* 13*20* 22*23* 31*35* 36*38* 41*44*6Root10122320353844（接上頁）第35頁/共54頁第三十五頁，共54頁。2.2.5關(guān)于(guny)B+Tree的級(jí)d 實(shí)際中，很少使用級(jí)的概念，代之以物理空間的半滿。 索引頁通常比葉子有更多的項(xiàng)。 使用變長記錄和變長搜索碼值造成不同的節(jié)點(diǎn)含有的項(xiàng)數(shù)不同。 即使采用定長搜索碼，若采用作為數(shù)據(jù)入口，若多條數(shù)據(jù)記錄搜索碼值相同(xin tn)，也會(huì)產(chǎn)生變長的數(shù)據(jù)入口。 實(shí)際的系統(tǒng)中要求并不嚴(yán)格，有可能是在某個(gè)節(jié)點(diǎn)變空時(shí)才回收空間。第36頁/共54頁第三十六頁，共54頁

22、。樹形索引(suyn)小結(jié) 樹形索引很適合范圍檢索，同時(shí)適合等值檢索。 ISAM：是靜態(tài)的結(jié)構(gòu) 只在葉子上更改，需要(xyo)溢出頁。 溢出頁形成溢出鏈會(huì)造成性能下降，所以需要(xyo)經(jīng)常重新構(gòu)建。 B+Tree：是動(dòng)態(tài)的結(jié)構(gòu) 插入、刪除后，高度是平衡的。O(log F N ) 扇除系數(shù)很大，所以高度一般在3、4層。 一般來說，比維護(hù)一個(gè)排序的文件好。第37頁/共54頁第三十七頁，共54頁。樹形索引(suyn)小結(jié) 通常，平均67%的空間利用率。 通常比ISAM要好，能適應(yīng)變化。 搜索碼值壓縮可以增大扇出系數(shù)，降低樹高。 通過重新創(chuàng)建B+Tree，大批裝載可以比逐個(gè)插入更快。 樹形索引(su

23、yn)是絕大多數(shù)DBMS中采用的索引(suyn)結(jié)構(gòu)，它支持范圍檢索與等值檢索。 索引(suyn)是查詢優(yōu)化要考慮的一個(gè)重要因素。第38頁/共54頁第三十八頁，共54頁。3.1 散列文件組織 (1)在前面(qin mian)介紹的索引類型中，我們必須訪問該索引結(jié)構(gòu)，才能在文件中定位記錄。而基于散列(Hash)的文件組織使我們能夠避免訪問索引結(jié)構(gòu)； 在散列文件組織中，我們用存儲(chǔ)桶來表示能存儲(chǔ)一條或多條記錄的一個(gè)存儲(chǔ)單位。通過計(jì)算搜索碼上的一個(gè)函數(shù)，就可以確定包含該搜索碼值的記錄應(yīng)該存儲(chǔ)在哪個(gè)桶中； 令K表示所有搜索碼值的集合，令B表示所有桶地址的集合，散列函數(shù)h就是一個(gè)從K到B的函數(shù)： h(K)

24、B第39頁/共54頁第三十九頁，共54頁。3.1 散列文件(wnjin)的操作第40頁/共54頁第四十頁，共54頁。3.1 散列函數(shù)(hnsh) 如果散列函數(shù)設(shè)計(jì)的不好，就有可能把所有的搜索碼值都映射到同一個(gè)存儲(chǔ)桶中，這時(shí)，散列已經(jīng)失去了意義。因此，對(duì)散列函數(shù)的基本要求是：分布是均勻的：即每個(gè)存儲(chǔ)桶從所有可能的搜索碼值集合中分配到的值的個(gè)數(shù)差不多相同。這就是散列函數(shù)的均勻性；例如，假設(shè)搜索碼值的可能集合為A.Z分布是隨機(jī)的：一般情況下，不管搜索碼值實(shí)際情況是怎樣的，每個(gè)存儲(chǔ)桶應(yīng)分配到的搜索碼值的個(gè)數(shù)也差不多相同。這就是散列函數(shù)的隨機(jī)性，更確切地說，散列函數(shù)結(jié)果的分布不應(yīng)與搜索碼的任何(rnh)

25、外部可見的特性相關(guān)。例如，假設(shè)實(shí)際的搜索碼值是A,B,C,D,E第41頁/共54頁第四十一頁，共54頁。3.1 散列函數(shù)(hnsh)舉例假設(shè)我們需要將26個(gè)大寫英文字母分布到5個(gè)存儲(chǔ)桶中(地址從0到4)，那么散列函數(shù)h該如何設(shè)計(jì)(shj)呢？假設(shè)用Ascii(A)表示A所對(duì)應(yīng)的Ascii碼，A,B,C,Z散列函數(shù)h= Ascii(Search Key) mod 50,1,2,25圖8-4-18-4-1BGLQVCHMRWDINSXEJOTYAFKPUZ桶桶0 0桶桶1 1桶桶2 2桶桶3 3桶桶4 4第42頁/共54頁第四十二頁，共54頁。3 .1桶溢出(y ch)控制發(fā)生溢出的原因(yuny

26、n)有：桶的數(shù)目不足；桶太?。和爸心艽鎯?chǔ)的記錄數(shù)太少。當(dāng)存儲(chǔ)桶溢出時(shí)可采用溢出桶進(jìn)行存儲(chǔ)：桶桶0 0桶桶1 1桶桶2 2第43頁/共54頁第四十三頁，共54頁。3.2 散列索引(suyn) 散列不僅可以用于文件(wnjin)中記錄的組織，還可以用于索引結(jié)構(gòu)的創(chuàng)建。散列索引：散列索引是指將索引入口中的搜索碼及相應(yīng)指針組織成散列文件(wnjin)結(jié)構(gòu)；散列索引的構(gòu)造如下：將散列函數(shù)作用于索引項(xiàng)中的搜索碼以確定對(duì)應(yīng)的存儲(chǔ)桶，然后將此數(shù)據(jù)入口，即搜索碼及相應(yīng)的指針存入此存儲(chǔ)桶（或溢出桶）中，指針指向數(shù)據(jù)文件(wnjin)中的記錄。第44頁/共54頁第四十四頁，共54頁。3.2 散列索引(suyn)hN

27、-1210索引碼值指向數(shù)據(jù)的指針?biāo)阉鞔a值keyK(key)mod n靜態(tài)散列：桶的數(shù)目是固定的。若桶是在磁盤上順序存放，一個(gè)I/O就能找到數(shù)據(jù)入口。(無溢出桶)桶內(nèi)可預(yù)留一定空間，但若增長很多，溢出桶很多，將影響(yngxing)性能。第45頁/共54頁第四十五頁，共54頁。3.3 可擴(kuò)充(kuchng)散列 為了不產(chǎn)生溢出桶，在桶滿的時(shí)候，需要使桶的數(shù)目加倍并平均分配原有的數(shù)據(jù)入口，這樣做整個(gè)文件要讀一次，并寫兩倍。 解決辦法，使用目錄，它指向桶的指針，通過使目錄翻倍來使桶的數(shù)目大小翻倍，并且只分裂產(chǎn)生溢出的桶。 目錄深度(Global depth)：用于標(biāo)識(shí)(biozh)hash函數(shù)的后幾

28、位用于在目錄中確定桶的位置。 桶深度（Local depth）：用于標(biāo)識(shí)(biozh)當(dāng)前的桶是hash函數(shù)后幾位產(chǎn)生的。第46頁/共54頁第四十六頁，共54頁。3.3 可擴(kuò)充(kuchng)散列16*32*313*21*5*1*210*219*7*15*220*12*4*3h3111110101100011010001000索引(suyn)碼值xxx000 xxx111目錄(ml)桶第47頁/共54頁第四十七頁，共54頁。3.3 可擴(kuò)充(kuchng)散列 查找： 1、對(duì)索引(suyn)碼值進(jìn)行hash運(yùn)算，結(jié)果用二進(jìn)制表示。 2、設(shè)目錄深度為dd，則取上面結(jié)果的后dd位。根據(jù)這dd為地址，在目錄中找到桶的地址。 3、訪問桶，在桶中用待查找的索引(suyn)碼值與桶中的索引(suyn)碼值依次比較，若相等，通過桶中相應(yīng)的指針找到數(shù)據(jù)。第48頁/共54頁第四十八頁，共54頁。3.3 可擴(kuò)充(kuchng)散列 插入： 1、2步與查找相同，找到要插入所在的桶。 3、