第2章一維索引組織結(jié)構(gòu)

2023年2月5日1高級(jí)數(shù)據(jù)庫(kù)課程第2章：一維索引組織結(jié)構(gòu)

第一部分?jǐn)?shù)據(jù)庫(kù)系統(tǒng)基礎(chǔ)

第二部分?jǐn)?shù)據(jù)庫(kù)的數(shù)據(jù)存儲(chǔ)管理

第三部分?jǐn)?shù)據(jù)庫(kù)查詢(xún)處理引言

整個(gè)關(guān)系在儲(chǔ)存中如何存儲(chǔ)與表示？以及怎樣才能有效檢索與定位？比如，如何回答象

SELECT*FROMR

這樣一個(gè)簡(jiǎn)單查詢(xún)？2023年2月5日2引言我們可能不得不檢索輔存中的與數(shù)據(jù)庫(kù)文件對(duì)應(yīng)的每個(gè)存儲(chǔ)塊，且還得依賴(lài)塊首部中存在足夠得信息來(lái)表明該塊記錄從什么地方開(kāi)始，塊中記錄屬于什么關(guān)系；有效的解決方案――－采用索引結(jié)構(gòu)；2023年2月5日3索引：索引是一種數(shù)據(jù)結(jié)構(gòu)，它以記錄的特征（通常是一個(gè)或多個(gè)字段的值）為輸入，并能“快速地”找出具有該特征的記錄2023年2月5日4引言查找鍵---建立索引的字段索引方法（1）順序文件上的簡(jiǎn)單索引（2）非排序文件上的輔助索引（3）B樹(shù),一種可以在任何文件上建立索引的常用方法（4）散列表2023年2月5日52.1順序文件上的索引—相關(guān)概念數(shù)據(jù)文件存放一個(gè)關(guān)系所有元組數(shù)據(jù)的文件；順序文件按關(guān)系中指定的一個(gè)或多個(gè)字段組合值（鍵）排序的數(shù)據(jù)文件；索引文件為方便檢索數(shù)據(jù)文件中元組，而建立的一個(gè)獨(dú)立的輔助文件或輔助關(guān)系；索引項(xiàng)或索引記錄通常包含兩個(gè)字段：鍵和指針；索引表通常很小;按索引項(xiàng)（記錄或元組）與關(guān)系中元組的對(duì)應(yīng)方式，可將索引分為稠密索引和稀疏索引兩類(lèi)。2023年2月5日62.1順序文件上的索引—稠密索引稠密索引的數(shù)據(jù)結(jié)構(gòu)組織形式

稠密索引文件的特點(diǎn)使用稠密索引文件的好處2023年2月5日7索引文件數(shù)據(jù)文件：元組按主鍵排序每個(gè)存儲(chǔ)塊只存放兩個(gè)記錄2.1順序文件上的索引—稠密索引稠密索引的數(shù)據(jù)結(jié)構(gòu)組織形式

稠密索引文件的特點(diǎn)是一個(gè)獨(dú)立文件，占用系列存儲(chǔ)塊，塊中僅存放記錄鍵和指向記錄的指針；每個(gè)索引項(xiàng)對(duì)應(yīng)相應(yīng)數(shù)據(jù)文件中的一條記錄；通常其大小要明顯小于數(shù)據(jù)文件；

稠密索引的查找使用稠密索引文件的好處2023年2月5日82.1順序文件上的索引—稠密索引稠密索引的數(shù)據(jù)結(jié)構(gòu)組織形式

稠密索引文件的特點(diǎn)稠密索引的查找

支持按給定鍵值查找相應(yīng)記錄的查詢(xún)給定一個(gè)鍵值K

（1）現(xiàn)在索引塊中查找K

（2）找到K后，按照K所對(duì)應(yīng)的指針到數(shù)據(jù)文件中尋找相應(yīng)的記錄使用稠密索引文件的好處2023年2月5日92.1順序文件上的索引—稠密索引稠密索引的數(shù)據(jù)結(jié)構(gòu)組織形式

稠密索引文件的特點(diǎn)稠密索引的查找使用稠密索引文件的好處索引數(shù)據(jù)塊通常比數(shù)據(jù)塊少，I/0次數(shù)少，如果索引足夠小，甚至可以將整個(gè)索引放在內(nèi)存緩沖區(qū)中，則只需一次性讀入索引的I/O，就可以定位任意的記錄；由于索引文件中鍵被排序，可用二分法快速查找，若有n個(gè)索引項(xiàng)，最多只需要查log2n個(gè)塊；2023年2月5日102.1順序文件上的索引—稀疏索引稀疏索引的數(shù)據(jù)結(jié)構(gòu)組織形式

稀疏索引文件的特點(diǎn)2023年2月5日112.1順序文件上的索引—稀疏索引稀疏索引的數(shù)據(jù)結(jié)構(gòu)組織形式

稀疏索引文件的特點(diǎn)為每個(gè)存儲(chǔ)塊設(shè)一個(gè)鍵-指針對(duì)鍵值是每個(gè)數(shù)據(jù)塊中第一個(gè)記錄的對(duì)應(yīng)值稀疏索引的查找與稠密索引比較2023年2月5日122.1順序文件上的索引—稀疏索引稀疏索引的數(shù)據(jù)結(jié)構(gòu)組織形式

稀疏索引文件的特點(diǎn)稀疏索引的查找

找出鍵值為K的記錄（1）在索引中查找鍵值小于或等于K的最大鍵值（2）根據(jù)指針找到相應(yīng)數(shù)據(jù)塊（3）搜索數(shù)據(jù)塊以找到鍵值為K的記錄與稠密索引比較2023年2月5日132.1順序文件上的索引—稀疏索引稀疏索引的數(shù)據(jù)結(jié)構(gòu)組織形式

稀疏索引文件的特點(diǎn)稀疏索引的查找與稠密索引比較（1）節(jié)省了存儲(chǔ)空間（2）查找給定值的記錄需要更多時(shí)間例：查詢(xún)“是否存在鍵值為K的記錄？”稠密索引只需考慮鍵K在索引中的存在稀疏索引要執(zhí)行I/O操作去檢索可能存在鍵值為K的記錄的塊2023年2月5日142.1順序文件上的索引—多級(jí)索引在索引的基礎(chǔ)上，再建索引

2023年2月5日152.1順序文件上的索引—多級(jí)索引如對(duì)主索引再建立一級(jí)稀疏索引,即對(duì)每個(gè)索引塊建立一個(gè)索引記錄,就形成了二級(jí)索引·此時(shí)外層索引塊可常駐內(nèi)存,在查找記錄時(shí)內(nèi)層索引塊只要讀1次就行·如果外層索引塊的數(shù)目太多,不能全部進(jìn)內(nèi)存,那么可對(duì)最外層索引再外建一層索引,這就形成了多級(jí)索引技術(shù)。二級(jí)以上索引肯定是稀疏索引；一級(jí)索引通常是稠密的；多級(jí)索引的性能及管理的方便性不如B樹(shù)結(jié)構(gòu)；2023年2月5日162.2輔助索引

—應(yīng)用背景

在實(shí)際的DB應(yīng)用中，經(jīng)常需要進(jìn)行針對(duì)非主屬性的查詢(xún)，為了加快查詢(xún)的速度，也可以對(duì)非主屬性建立索引：

SELECTname,addressFROMmovieStarWHEREbirthDate=DATE(‘1995-01-01’)；可在屬性上建立索引：

CREATEINDEXi_birthDateONmovieStar(birthDate)

相對(duì)與主鍵索引，我們稱(chēng)之為輔助索引。

2023年2月5日172.2輔助索引

—基本特點(diǎn)與設(shè)計(jì)輔助索引的特點(diǎn)可能存在重復(fù)鍵；數(shù)據(jù)文件一般不按輔助索引鍵排序；輔助索引設(shè)計(jì)必須是稠密的索引結(jié)構(gòu)；索引文件中索引項(xiàng)按鍵值排序；可根據(jù)需要建立二級(jí)或多級(jí)索引存在空間浪費(fèi)，如某個(gè)鍵在數(shù)據(jù)文件中出現(xiàn)n次，那么這個(gè)鍵值將在索引文件中出現(xiàn)n次。2023年2月5日182.2輔助索引

—基本特點(diǎn)與設(shè)計(jì)如果查找鍵的值的順序與主文件的順序不一致,那么這種索引稱(chēng)為輔助索引,或非聚集索引。輔助索引總是稠密索引，通常有重復(fù)值輔助索引的索引項(xiàng)按鍵值排序輔助索引的指針不是指向一個(gè)或幾個(gè)連續(xù)存儲(chǔ)塊，而是指向很多不同的塊。例：k=20

要查找兩個(gè)索引塊，還要訪(fǎng)問(wèn)指針指向的三個(gè)不同的數(shù)據(jù)塊2023年2月5日192.2輔助索引

—應(yīng)用堆文件（1）最基本最簡(jiǎn)單的文件結(jié)構(gòu)（2）記錄不以任何順序存放（3）記錄可能放在不鄰接的塊上聚簇文件（1）RDB單關(guān)系上的聚簇---將記錄按某個(gè)字段順序排列在塊中（2）RDB多關(guān)系上的聚簇----一個(gè)塊中存儲(chǔ)不同類(lèi)型的記錄，兩個(gè)或多個(gè)關(guān)系的元組被混在一起2023年2月5日202.2輔助索引

—應(yīng)用順序文件建立附加索引堆結(jié)構(gòu)的主索引文件聚簇文件2023年2月5日212.2輔助索引

—應(yīng)用聚簇文件例：Movie(title,year,length,studioname)Studio(name,address,president)

SELECTpresidentFROMMovie,StudioWHEREtitle=‘Star’ANDMovie.studioname=S

為了使此種連接效率更高，采用聚簇文件結(jié)構(gòu)：關(guān)系Movie的元組和Studio的元組存放在相同的一系列塊中，每個(gè)Studio元組后面存放關(guān)系Movie中該制片廠(chǎng)的所有電影元組2023年2月5日222.2輔助索引

—應(yīng)用間接索引層(桶)2023年2月5日232.2輔助索引

—應(yīng)用間接索引層(桶)索引結(jié)構(gòu)組織間接層的桶中只存放指針；只要鍵值的總長(zhǎng)度大于指針，就可以較好克服一般輔助索引中的空間浪費(fèi)現(xiàn)象；可以在不訪(fǎng)問(wèn)數(shù)據(jù)文件記錄的前提下，利用桶指針幫助問(wèn)題以下一些問(wèn)題：當(dāng)查詢(xún)有多個(gè)條件，且每個(gè)條件都有可用的索引時(shí)，可以通過(guò)在主存中對(duì)指針集合求交集，來(lái)找出滿(mǎn)足所有條件的記錄，然后，只需檢索交集中指針指向的記錄，從而節(jié)省了不必要的I/O。2023年2月5日242.2輔助索引

—應(yīng)用間接索引層(桶)輔助索引可以采用上面的方法實(shí)現(xiàn):仍然為每個(gè)查找鍵值建立一個(gè)索引記錄,內(nèi)容包括查找鍵值和一個(gè)指針,但這個(gè)指針不指向主文件中的記錄,而是指向一個(gè)桶,桶內(nèi)存放指向具有同一查找鍵值的主記錄的指針。如上圖所示,輔助索引的指針并不直接指向文件,而是每個(gè)指針指向一個(gè)包含文件指針的存儲(chǔ)桶，存儲(chǔ)桶中的每個(gè)指針都指向文件中的記錄。使用桶介于輔助索引和數(shù)據(jù)文件之間，節(jié)約空間，避免鍵值重復(fù)。2023年2月5日252.2輔助索引

—應(yīng)用間接索引層(桶)2023年2月5日26可以通過(guò)在主存中對(duì)指針集合求交來(lái)找到滿(mǎn)足所有條件的指針，只需要檢索交集中指針指向的記錄。SELECTtitleFROMMovieWHEREstudioname=‘Disney’ANDyear=1995;2.3數(shù)據(jù)文件修改期間的索引維護(hù)

索引文件是順序文件，到目前為止，我們都假設(shè)數(shù)據(jù)文件和索引文件由一些連續(xù)的、裝滿(mǎn)某種類(lèi)型記錄的存儲(chǔ)塊組成。由于在實(shí)際應(yīng)用中，總是需要不斷地對(duì)數(shù)據(jù)進(jìn)行插入、刪除、修改，這勢(shì)必會(huì)導(dǎo)致順序文件這樣的組織發(fā)生變化和調(diào)整。2023年2月5日272.3數(shù)據(jù)文件修改期間的索引維護(hù)當(dāng)數(shù)據(jù)文件變化后，通常必須對(duì)索引文件進(jìn)行相應(yīng)的調(diào)整，以適應(yīng)數(shù)據(jù)文件的變化；索引文件的調(diào)整可借鑒數(shù)據(jù)文件中所用的一些策略：2023年2月5日282.4基于B樹(shù)的索引--B樹(shù)的結(jié)構(gòu)特點(diǎn)2023年2月5日29B樹(shù)結(jié)構(gòu)B樹(shù)查詢(xún)B樹(shù)插入B樹(shù)刪除B樹(shù)效率應(yīng)用方式2.4基于B樹(shù)的索引--B樹(shù)的結(jié)構(gòu)特點(diǎn)

m階B樹(shù)節(jié)點(diǎn)的子節(jié)點(diǎn)數(shù)約束最大約束：每個(gè)節(jié)點(diǎn)至多有m個(gè)子節(jié)點(diǎn)；最少約束根節(jié)點(diǎn)：最少要有兩個(gè)子節(jié)點(diǎn)葉節(jié)點(diǎn)：可以沒(méi)有子節(jié)點(diǎn)；內(nèi)節(jié)點(diǎn)：至少有m/2子節(jié)點(diǎn)所有的葉節(jié)點(diǎn)都在同一層；非葉節(jié)點(diǎn)的鍵與指針有j個(gè)鍵的非葉節(jié)點(diǎn)，恰好包括j＋1個(gè)子節(jié)點(diǎn)指針節(jié)點(diǎn)的形式：P0,K0,P1,K1,P2,K2,…,Pj-1,Kj-1,Pj將B樹(shù)擴(kuò)展為B+樹(shù)，使之適合于DB索引應(yīng)用每個(gè)葉節(jié)點(diǎn)至少有(m+1)/2個(gè)指針指向數(shù)據(jù)記錄；最后一個(gè)指針指向它右邊的下一個(gè)右節(jié)點(diǎn)（最后1個(gè)葉節(jié)點(diǎn)的最后1個(gè)指針可為空）；

2023年2月5日30B樹(shù)2.4基于B樹(shù)的索引--B樹(shù)的結(jié)構(gòu)特點(diǎn)

2023年2月5日31B樹(shù)2.4.2基于B樹(shù)的索引--B樹(shù)的查找

歸納查找基礎(chǔ)：若已經(jīng)處于葉節(jié)點(diǎn)；(則只需在結(jié)點(diǎn)內(nèi)搜索)歸納：若處于某內(nèi)部節(jié)點(diǎn)，且它的鍵值為

K1,K2,…,Kj-1；如k<k1，第一個(gè)子節(jié)點(diǎn)；k1=<k<k2

第2個(gè)節(jié)點(diǎn)…例：查找k=41的記錄2023年2月5日32

范圍查找只要先找到下限起點(diǎn)，然后順著找下去，直到找到一個(gè)大于上限的鍵為止；例：查找范圍（10，25）B樹(shù)2.4.3基于B樹(shù)的索引--B樹(shù)的插入定位合適的葉節(jié)點(diǎn)(令為N)，如有空，插入即可結(jié)束如無(wú)空，在N右邊創(chuàng)建一個(gè)新的節(jié)點(diǎn)M，并按下面步驟進(jìn)行調(diào)整安排：

重排插入新鍵后N中的鍵序，共(n+1)個(gè)前(n+1)/2個(gè)鍵－指針對(duì)留在N中，其它移入M中（至少有(n+1)/2個(gè)）

M和N中鍵－指針對(duì)個(gè)數(shù)肯定都能滿(mǎn)足約束條件！轉(zhuǎn)下一步：調(diào)整N,M的上層父節(jié)點(diǎn)；調(diào)整N/M的上層父節(jié)點(diǎn)（NP/MP）遞歸調(diào)整NP/MP的上層節(jié)點(diǎn)，直到完成，必要時(shí)可能還要增加樹(shù)的層數(shù)。2023年2月5日33B樹(shù)2.4.3基于B樹(shù)的索引--B樹(shù)的插入調(diào)整M,N的上層節(jié)點(diǎn)在原N的父節(jié)點(diǎn)NP中插入一個(gè)新的鍵－值指針對(duì)，重排NP鍵值重調(diào)整NP的所有子結(jié)點(diǎn)指針；如鍵值數(shù)不超限，插入結(jié)束；否則轉(zhuǎn)下一步分裂NP；分裂NP為(NP,MP)，MP是新的緊靠NP右邊的兄弟節(jié)點(diǎn)；前n+1/2指針留在NP中；后n+1/2指針移入MP中；前n/2個(gè)鍵保留在節(jié)點(diǎn)NP中，后n/2個(gè)鍵移到節(jié)點(diǎn)MP中，中間的鍵K會(huì)被結(jié)點(diǎn)NP和MP的父結(jié)點(diǎn)用來(lái)劃分在這兩個(gè)結(jié)點(diǎn)之間的查找重計(jì)算NP,MP中的鍵值，必要時(shí)調(diào)整NP,MP的父節(jié)點(diǎn)（N的祖父節(jié)點(diǎn)），以正確劃分NP,MP中的鍵；遞歸調(diào)整NP，MP的上層節(jié)點(diǎn)，直到完成，必要時(shí)可能還需增加樹(shù)的層數(shù)。

舉例：在圖4-23中插入鍵值402023年2月5日34B樹(shù)2.4.4基于B樹(shù)的索引--B樹(shù)的刪除刪除首先是查找定位，找到所在葉節(jié)點(diǎn)(令為N)后刪除鍵－指針對(duì)；如刪除后違反樹(shù)約束，則需要進(jìn)行相應(yīng)調(diào)整若N有1鍵－指針對(duì)個(gè)數(shù)超過(guò)最小數(shù)的兄弟節(jié)點(diǎn)，則直接從中借用一個(gè)，但會(huì)導(dǎo)致上層父節(jié)點(diǎn)需要調(diào)整；若無(wú)兄弟節(jié)點(diǎn)可借，則可合并N到它的一個(gè)兄弟節(jié)點(diǎn)。這樣，也可能會(huì)導(dǎo)致上層違反約束，則可能要從遠(yuǎn)親借一個(gè)近鄰的表兄弟節(jié)點(diǎn)(整個(gè)節(jié)點(diǎn))沿樹(shù)遞歸地刪除；舉例（在圖4-23中分別刪除7和11,教材P120-121）2023年2月5日35B樹(shù)2.4.5

B樹(shù)的特點(diǎn)與效率

能自動(dòng)保持與數(shù)據(jù)文件大小相適應(yīng)的索引層次；能對(duì)所使用的空間進(jìn)行管理，使得每個(gè)塊的充滿(mǎn)度在半滿(mǎn)與全滿(mǎn)之間，索引不需要溢出塊讀有B樹(shù)索引的數(shù)據(jù)塊的I/O次數(shù)＝B樹(shù)的層數(shù)＋1當(dāng)B樹(shù)階數(shù)m很大時(shí)，插入/刪除引起的調(diào)整大多限在葉子節(jié)點(diǎn)層，基本上可忽略B數(shù)重組帶來(lái)的I/O開(kāi)銷(xiāo)；可讓B數(shù)的根結(jié)點(diǎn)永久駐留內(nèi)存；把B數(shù)的第二層節(jié)點(diǎn)保存在主存緩沖區(qū)也是合理的；2023年2月5日36B樹(shù)2.4.6

B樹(shù)的應(yīng)用方式

查找鍵是主鍵，索引是稠密的；文件主鍵排序，B樹(shù)稀疏索引（每個(gè)數(shù)據(jù)塊對(duì)應(yīng)B樹(shù)葉節(jié)點(diǎn)的一個(gè)指針）；用于非主鍵屬性，且有重復(fù)鍵的情形（需修改內(nèi)部節(jié)點(diǎn)的部分含義，引入最小新鍵的概念）。葉節(jié)點(diǎn)中為數(shù)據(jù)文件里出現(xiàn)的每個(gè)屬性值K設(shè)有一個(gè)鍵-指針對(duì)，其中指針指向排序鍵值為K的記錄中的第一個(gè)。2023年2月5日37B樹(shù)2.5基于散列的索引

2.5.1散列(hash)的數(shù)據(jù)結(jié)構(gòu)

散列函數(shù)及其選擇原則要求:隨機(jī)分布好、易計(jì)算；散列鍵（散列函數(shù)的參數(shù)）與散列值（散列函數(shù)結(jié)果值）維數(shù)為B的桶數(shù)組：0～B-1；被散列對(duì)象將根據(jù)其鍵值，計(jì)算散列值，然后保存到相應(yīng)的桶中；桶內(nèi)對(duì)象，按鏈連接起來(lái)，構(gòu)成對(duì)象鏈。2023年2月5日382.5.1散列(hash)的數(shù)據(jù)結(jié)構(gòu)2023年2月5日39key→h(key)<key>可以是記錄或指向記錄的指針h(k)散列函數(shù)：以查找鍵為參數(shù)并計(jì)算出一個(gè)介于0----B-1的整數(shù)。k是整數(shù)--------k/B的余數(shù)K是字符串---每個(gè)字符看成整數(shù)累加/B的余數(shù)2.5.1輔存散列表（靜態(tài)散列表）

桶數(shù)組為一組存儲(chǔ)塊；散列的插入:空間不夠（桶溢出），可增加溢出鏈塊；散列刪除，刪除后如某溢出塊空，則應(yīng)刪除相應(yīng)的溢出塊；輔存散列的效率理想情況只需一次I/O；非理想情況可能需要多次I/O（存在對(duì)象鏈、溢出塊鏈）；2023年2月5日402.5.1輔存散列表（靜態(tài)散列表）例：假定每個(gè)存儲(chǔ)塊只能存放2個(gè)記錄

B=4散列函數(shù)h的返回值0~3之間鍵值為a~fh(d)=0h(c)=h(e)=1h(b)=2h(a)=h(f)=3則記錄在塊中的分布如圖所示2023年2月5日410123dcebaf鏈接溢出塊2.5.1輔存散列表（靜態(tài)散列表）散列表的插入查找鍵為k的記錄需要被插入：(1)計(jì)算h(k)(2)如果桶號(hào)為h(k)的桶還有空間，把記錄存放到此桶的存儲(chǔ)塊中(3)存儲(chǔ)塊沒(méi)有空間時(shí)存儲(chǔ)到塊鏈上的某個(gè)溢出塊中(4)如果桶的所有存儲(chǔ)塊都沒(méi)有空間，增加一個(gè)新溢出塊到該桶的鏈上，并把新記錄存入該塊例：增加一個(gè)鍵值為g的記錄，且h(g)=1

把記錄加到1號(hào)桶增加一個(gè)新塊，鏈到桶1的第1塊上鍵值為g的記錄插入到這一塊中2023年2月5日420123dcebafg2.5.1輔存散列表（靜態(tài)散列表）散列表索引的效率理想情況是存儲(chǔ)器有足夠多的桶，使絕大多數(shù)桶都只由一個(gè)塊組成，這樣查詢(xún)1次I/O，比稀疏索引、稠密索引、B+樹(shù)好得多。所以應(yīng)設(shè)法減少每個(gè)桶的塊數(shù)靜態(tài)散列表----通的數(shù)目B不變動(dòng)態(tài)散列表----允許B改變，使B近似于：記錄總數(shù)/塊中容納記錄數(shù)目的：每個(gè)桶大約有一個(gè)存儲(chǔ)塊2023年2月5日432.5.2可擴(kuò)展的散列表引入一個(gè)間接層做桶，桶中僅保存指針；指針桶數(shù)組能增長(zhǎng)，它的長(zhǎng)度為2n，每次增長(zhǎng)nn+1，桶數(shù)組長(zhǎng)度擴(kuò)一倍；多個(gè)連續(xù)的桶可共享（共同指向）一個(gè)數(shù)據(jù)塊，每個(gè)數(shù)據(jù)塊中有一個(gè)小凸塊標(biāo)記資格位數(shù)（j）；散列的結(jié)果值――為K位二進(jìn)制數(shù)（K可達(dá)到32位，足夠!）；實(shí)際用的桶編號(hào)位數(shù)i<=k,用K的前(左邊)i位i值作為結(jié)構(gòu)一部分被保存；2023年2月5日44相對(duì)靜態(tài)散列表的增強(qiáng)

2.5.2可擴(kuò)展的散列表2023年2月5日45i=10100011001110011例:(1)假定k=4,即h產(chǎn)生4位二進(jìn)制序列；(2)使用位i=1，所以桶數(shù)組項(xiàng)：21=2項(xiàng)（0，1）(3)桶數(shù)組的項(xiàng)指向二個(gè)塊：第一塊存放當(dāng)前所有查找鍵被散列成以0開(kāi)頭的二進(jìn)制序列的記錄第二塊存放所有查找鍵被散列成以1開(kāi)頭的二進(jìn)制序列的記錄(4)為方便，顯示的記錄鍵是散列函數(shù)將這些鍵轉(zhuǎn)換成的二進(jìn)制位序列(5)每個(gè)存儲(chǔ)塊的“小凸塊”顯示1，表明由散列函數(shù)得到的位序列中有多少位用于確定記錄在該塊中的成員資格。j2.5.2可擴(kuò)展的散列表--插入

計(jì)算h(k)，并取結(jié)果（散列值）的前i位，根據(jù)它找到桶及對(duì)應(yīng)的存儲(chǔ)塊；如存儲(chǔ)塊中有空間，插入即可，如無(wú)空間，按如下的兩種情形處理：(1)資格位數(shù)j<i分裂存儲(chǔ)塊，然后根據(jù)散列值從左邊算起的第j+1位的值，劃分記錄到分裂后的兩個(gè)塊中（＝1放在在新塊中，=0放在原塊中）；分裂后的兩個(gè)塊資格位j均增加1；調(diào)整桶數(shù)組中的指針（針對(duì)新塊）(2)資格位數(shù)j＝iii+1，將桶數(shù)組擴(kuò)大1倍，新桶數(shù)組W0,W1指向原W指向的塊；按步驟(1)處理；

2023年2月5日462.5.2可擴(kuò)展的散列表--操作示例2023年2月5日472.5.2可擴(kuò)展的散列表--操作示例2023年2月5日482.5.2可擴(kuò)展的散列表--操作步驟上例插入1010（1）第1位是1，屬于第2個(gè)塊（2）該塊已滿(mǎn)需要分裂（3）j=i=1將桶數(shù)組加位i=2（4）根據(jù)第2位，為0：記錄1001，1010劃分到原塊；為1：記錄1100劃分到新塊（5）分裂后的兩個(gè)塊成員資格位j均增加1變?yōu)?；（6）調(diào)整桶數(shù)組中的指針（針對(duì)新塊）2023年2月5日492.5.2可擴(kuò)展的散列表--操作示例插入鍵值分別為0000和0111的記錄2023年2月5日50i=2000000010111100110101100222200011011因?yàn)閖=1i=2j<I所以不用調(diào)整桶數(shù)組2.5.2可擴(kuò)展的散列表—應(yīng)用優(yōu)點(diǎn)好處：查找非常直接！查桶數(shù)組+記錄所在數(shù)據(jù)塊內(nèi)查找；桶數(shù)組通常駐留內(nèi)存，實(shí)際只需1次I/O;存在問(wèn)題當(dāng)桶數(shù)組翻倍時(shí)，要做大量的工作；翻倍后，主存可能放不下，會(huì)導(dǎo)致系統(tǒng)性能驟然下降；雖然記錄不多，但因某些桶記錄過(guò)分集中，可能導(dǎo)致桶編號(hào)位數(shù)（i）很大，空桶過(guò)多；例：i=20j=20,j=3,j=10

記錄總數(shù)遠(yuǎn)遠(yuǎn)小于2202023年2月5日512.5.3線(xiàn)性散列—結(jié)構(gòu)特點(diǎn)結(jié)構(gòu)參數(shù)：桶數(shù)n；桶編號(hào)位數(shù)i；記錄總數(shù)r桶數(shù)n(<2n)，桶編號(hào)位數(shù)log2n＝i，且從散列值的右邊（低位）取相應(yīng)位；桶數(shù)n增加緩慢，每插入一個(gè)記錄，檢查記錄總數(shù)r與桶數(shù)n的比值r/n是否超過(guò)設(shè)定的上限，如超過(guò)則增加一個(gè)桶；n增加后，檢查編號(hào)位i是否需要加大，如增加則原有桶編號(hào)高位用0補(bǔ)齊;存儲(chǔ)塊并不總是可分裂（只有在增加一個(gè)桶時(shí)，才會(huì)引起一次塊分裂），因此，可增加溢出塊；結(jié)構(gòu)參數(shù)與索引數(shù)據(jù)一同保存；2023年2月5日522.5.3線(xiàn)性散列—結(jié)構(gòu)特點(diǎn)2023年2月5日5300001010111101i=1n=2r=3例1：圖中二個(gè)桶：0，1

每個(gè)桶包含一個(gè)存儲(chǔ)塊散列值以0結(jié)尾的在0號(hào)桶散列值以1結(jié)尾的在1號(hào)桶i----當(dāng)前被使用的散列函數(shù)值的位數(shù)n----當(dāng)前的桶數(shù)r----當(dāng)前散列表中的記錄總數(shù)規(guī)則----數(shù)據(jù)文件中的記錄的個(gè)數(shù)

r<=1.7n（桶的平均充滿(mǎn)度不會(huì)超過(guò)存儲(chǔ)塊容量的85%，

r/2n<=85%）2.5.3線(xiàn)性散列—插入記錄計(jì)算h(k)，并取散列值的后i位，令為

aiai-1…a1；計(jì)算該數(shù)的二進(jìn)制值為m；如m<n，插入相應(yīng)的桶或溢出塊中；如n<m，則把記錄插入（寄存）到ai-1…a1值對(duì)應(yīng)的塊或溢出塊中；計(jì)算r/n，如r/n>指定上限，增加一個(gè)桶，令桶號(hào)為ai＋1ai…a1值，并將該桶原先寄存在0ai…a1桶中的記錄取回本桶。如n>2i，ii+1，所有原桶編號(hào)前補(bǔ)0；2023年2月5日542.5.3線(xiàn)性散列—插入記錄舉例2023年2月5日55例2：插入鍵值散列為0101的記錄（1）位序列以1結(jié)尾，記錄屬于第二個(gè)桶（2）r/n=4/2>1.7n提高為32.5.3線(xiàn)性散列—插入記錄舉例2023年2月5日56㏒23（3）=2所以桶：00，01，10（4）分裂桶00

0000在0桶

1010在10桶2.5.3線(xiàn)性散列—插入記錄舉例2023年2月5日57例3：增加鍵值散列為0001的記錄（1）最后2位為：01，且01桶存在，把記錄放在01桶中。（2）該桶塊已滿(mǎn)，增加一個(gè)溢出塊（3）三個(gè)記錄按散列鍵的數(shù)值順序保存（4）r/n=5/3=1.5<1.7不需要?jiǎng)?chuàng)建新桶2.5.3線(xiàn)性散列—插入記錄舉例例4插入鍵值散列為0111的記錄（1）最后2位為11，但桶11不存在（2）把記錄改為存入01桶，新記錄存入該桶溢出塊中（3）r/n=6/3=2>1.7創(chuàng)建1個(gè)編號(hào)為11的新桶（4）分裂01桶的4個(gè)記錄：

01桶（0001，0101）

11桶（0111，1111）（5）刪除01桶溢出塊2023年2月5日5800000001010110100111111100011011i=2n=4r=6000000010101101001111111000110i=2n=3r=62.5.3線(xiàn)性散列—查詢(xún)記錄舉例例5查找散列鍵值為1010的記錄(1)i=2查后2位10，看成二進(jìn)制整數(shù)m=2(2)m<n則編號(hào)為10的桶存在，到該桶中查找(3)檢查記錄的整個(gè)鍵來(lái)確定是否所需記錄2023年2月5日592.5.3線(xiàn)性散列—查詢(xún)記錄舉例例6查找散列鍵值為1011的記錄(1)i=2查后2位11，看成二進(jìn)制整數(shù)m=3(2)m>=n則編號(hào)為11的桶不存在(3)把第1位改為0后重新定位到桶01中(4)查看桶01不存在1011查找失敗2023年2月5日602.6位圖索引的組織結(jié)構(gòu)其基本原理是:

假設(shè)一個(gè)表T中有n個(gè)元組，A為表中的一個(gè)屬性，那么，屬性A的一個(gè)簡(jiǎn)單位圖索引是一個(gè)長(zhǎng)度為n的位圖矢量的集合，每一個(gè)位圖矢量對(duì)應(yīng)于屬性A取值域中的一個(gè)值。如果第i個(gè)元組的在屬性A上的取值為vi，那么對(duì)應(yīng)于值vi