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

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

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

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

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

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

SELECT*FROMR

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

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

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

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

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

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

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

（2）找到K后，按照K所對應(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ù)少，如果索引足夠小，甚至可以將整個索引放在內(nèi)存緩沖區(qū)中，則只需一次性讀入索引的I/O，就可以定位任意的記錄；由于索引文件中鍵被排序，可用二分法快速查找，若有n個索引項(xiàng)，最多只需要查log2n個塊；2023年2月5日102.1順序文件上的索引—稀疏索引稀疏索引的數(shù)據(jù)結(jié)構(gòu)組織形式

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

稀疏索引文件的特點(diǎn)為每個存儲塊設(shè)一個鍵-指針對鍵值是每個數(shù)據(jù)塊中第一個記錄的對應(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é)省了存儲空間（2）查找給定值的記錄需要更多時間例：查詢“是否存在鍵值為K的記錄？”稠密索引只需考慮鍵K在索引中的存在稀疏索引要執(zhí)行I/O操作去檢索可能存在鍵值為K的記錄的塊2023年2月5日142.1順序文件上的索引—多級索引在索引的基礎(chǔ)上，再建索引

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

—應(yīng)用背景

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

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

CREATEINDEXi_birthDateONmovieStar(birthDate)

相對與主鍵索引，我們稱之為輔助索引。

2023年2月5日172.2輔助索引

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

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

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

—應(yīng)用堆文件（1）最基本最簡單的文件結(jié)構(gòu)（2）記錄不以任何順序存放（3）記錄可能放在不鄰接的塊上聚簇文件（1）RDB單關(guān)系上的聚簇---將記錄按某個字段順序排列在塊中（2）RDB多關(guān)系上的聚簇----一個塊中存儲不同類型的記錄，兩個或多個關(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的元組存放在相同的一系列塊中，每個Studio元組后面存放關(guān)系Movie中該制片廠的所有電影元組2023年2月5日222.2輔助索引

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

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

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

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

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

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

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

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

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

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

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

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

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

M和N中鍵－指針對個數(shù)肯定都能滿足約束條件！轉(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ù)。2023年2月5日33B樹2.4.3基于B樹的索引--B樹的插入調(diào)整M,N的上層節(jié)點(diǎn)在原N的父節(jié)點(diǎn)NP中插入一個新的鍵－值指針對，重排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個鍵保留在節(jié)點(diǎn)NP中，后n/2個鍵移到節(jié)點(diǎn)MP中，中間的鍵K會被結(jié)點(diǎn)NP和MP的父結(jié)點(diǎn)用來劃分在這兩個結(jié)點(diǎn)之間的查找重計(jì)算NP,MP中的鍵值，必要時調(diào)整NP,MP的父節(jié)點(diǎn)（N的祖父節(jié)點(diǎn)），以正確劃分NP,MP中的鍵；遞歸調(diào)整NP，MP的上層節(jié)點(diǎn)，直到完成，必要時可能還需增加樹的層數(shù)。

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

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

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

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

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

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

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

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

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(k)的桶還有空間，把記錄存放到此桶的存儲塊中(3)存儲塊沒有空間時存儲到塊鏈上的某個溢出塊中(4)如果桶的所有存儲塊都沒有空間，增加一個新溢出塊到該桶的鏈上，并把新記錄存入該塊例：增加一個鍵值為g的記錄，且h(g)=1

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

計(jì)算h(k)，并取結(jié)果（散列值）的前i位，根據(jù)它找到桶及對應(yīng)的存儲塊；如存儲塊中有空間，插入即可，如無空間，按如下的兩種情形處理：(1)資格位數(shù)j<i分裂存儲塊，然后根據(jù)散列值從左邊算起的第j+1位的值，劃分記錄到分裂后的兩個塊中（＝1放在在新塊中，=0放在原塊中）；分裂后的兩個塊資格位j均增加1；調(diào)整桶數(shù)組中的指針（針對新塊）(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個塊（2）該塊已滿需要分裂（3）j=i=1將桶數(shù)組加位i=2（4）根據(jù)第2位，為0：記錄1001，1010劃分到原塊；為1：記錄1100劃分到新塊（5）分裂后的兩個塊成員資格位j均增加1變?yōu)?；（6）調(diào)整桶數(shù)組中的指針（針對新塊）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;存在問題當(dāng)桶數(shù)組翻倍時，要做大量的工作；翻倍后，主存可能放不下，會導(dǎo)致系統(tǒng)性能驟然下降；雖然記錄不多，但因某些桶記錄過分集中，可能導(dǎo)致桶編號位數(shù)（i）很大，空桶過多；例：i=20j=20,j=3,j=10

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

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

r<=1.7n（桶的平均充滿度不會超過存儲塊容量的85%，

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

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

0000在0桶

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

01桶（0001，0101）

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

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