2023年2月5日1高級數據庫課程第2章：一維索引組織結構

第一部分數據庫系統基礎

第二部分數據庫的數據存儲管理

第三部分數據庫查詢處理引言

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

SELECT*FROMR

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

稠密索引文件的特點使用稠密索引文件的好處2023年2月5日7索引文件數據文件：元組按主鍵排序每個存儲塊只存放兩個記錄2.1順序文件上的索引—稠密索引稠密索引的數據結構組織形式

稠密索引文件的特點是一個獨立文件，占用系列存儲塊，塊中僅存放記錄鍵和指向記錄的指針；每個索引項對應相應數據文件中的一條記錄；通常其大小要明顯小于數據文件；

稠密索引的查找使用稠密索引文件的好處2023年2月5日82.1順序文件上的索引—稠密索引稠密索引的數據結構組織形式

稠密索引文件的特點稠密索引的查找

支持按給定鍵值查找相應記錄的查詢給定一個鍵值K

（1）現在索引塊中查找K

（2）找到K后，按照K所對應的指針到數據文件中尋找相應的記錄使用稠密索引文件的好處2023年2月5日92.1順序文件上的索引—稠密索引稠密索引的數據結構組織形式

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

稀疏索引文件的特點2023年2月5日112.1順序文件上的索引—稀疏索引稀疏索引的數據結構組織形式

稀疏索引文件的特點為每個存儲塊設一個鍵-指針對鍵值是每個數據塊中第一個記錄的對應值稀疏索引的查找與稠密索引比較2023年2月5日122.1順序文件上的索引—稀疏索引稀疏索引的數據結構組織形式

稀疏索引文件的特點稀疏索引的查找

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

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

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

—應用背景

在實際的DB應用中，經常需要進行針對非主屬性的查詢，為了加快查詢的速度，也可以對非主屬性建立索引：

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

CREATEINDEXi_birthDateONmovieStar(birthDate)

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

2023年2月5日172.2輔助索引

—基本特點與設計輔助索引的特點可能存在重復鍵；數據文件一般不按輔助索引鍵排序；輔助索引設計必須是稠密的索引結構；索引文件中索引項按鍵值排序；可根據需要建立二級或多級索引存在空間浪費，如某個鍵在數據文件中出現n次，那么這個鍵值將在索引文件中出現n次。2023年2月5日182.2輔助索引

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

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

—應用堆文件（1）最基本最簡單的文件結構（2）記錄不以任何順序存放（3）記錄可能放在不鄰接的塊上聚簇文件（1）RDB單關系上的聚簇---將記錄按某個字段順序排列在塊中（2）RDB多關系上的聚簇----一個塊中存儲不同類型的記錄，兩個或多個關系的元組被混在一起2023年2月5日202.2輔助索引

—應用順序文件建立附加索引堆結構的主索引文件聚簇文件2023年2月5日212.2輔助索引

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

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

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

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

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

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

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

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

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

2023年2月5日30B樹2.4基于B樹的索引--B樹的結構特點

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

歸納查找基礎：若已經處于葉節點；(則只需在結點內搜索)歸納：若處于某內部節點，且它的鍵值為

K1,K2,…,Kj-1；如k<k1，第一個子節點；k1=<k<k2

第2個節點…例：查找k=41的記錄2023年2月5日32

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

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

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

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

B樹的特點與效率

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

B樹的應用方式

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

2.5.1散列(hash)的數據結構

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

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

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

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

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

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

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

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

每個桶包含一個存儲塊散列值以0結尾的在0號桶散列值以1結尾的在1號桶i----當前被使用的散列函數值的位數n----當前的桶數r----當前散列表中的記錄總數規則----數據文件中的記錄的個數

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

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

aiai-1…a1；計算該數的二進制值為m；如m<n，插入相應的桶或溢出塊中；如n<m，則把記錄插入（寄存）到ai-1…a1值對應的塊或溢出塊中；計算r/n，如r/n>指定上限，增加一個桶，令桶號為ai＋1ai…a1值，并將該桶原先寄存在0ai…a1桶中的記錄取回本桶。如n>2i，ii+1，所有原桶編號前補0；2023年2月5日542.5.3線性散列—插入記錄舉例2023年2月5日55例2：插入鍵值散列為0101的記錄（1）位序列以1結尾，記錄屬于第二個桶（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）三個記錄按散列鍵的數值順序保存（4）r/n=5/3=1.5<1.7不需要創建新桶2.5.3線性散列—插入記錄舉例例4插入鍵值散列為0111的記錄（1）最后2位為11，但桶11不存在（2）把記錄改為存入01桶，新記錄存入該桶溢出塊中（3）r/n=6/3=2>1.7創建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，看成二進制整數m=2(2)m<n則編號為10的桶存在，到該桶中查找(3)檢查記錄的整個鍵來確定是否所需記錄2023年2月5日592.5.3線性散列—查詢記錄舉例例6查找散列鍵值為1011的記錄(1)i=2查后2位11，看成二進制整數m=3(2)m>=n則編號為11的桶不存在(3)把第1位改為0后重新定位到桶01中(4)查看桶01不存在1011查找失敗2023年2月5日602.6位圖索引的組織結構其基本原理是:

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