第14講數(shù)據(jù)庫的存儲管理_第1頁
第14講數(shù)據(jù)庫的存儲管理_第2頁
第14講數(shù)據(jù)庫的存儲管理_第3頁
第14講數(shù)據(jù)庫的存儲管理_第4頁
第14講數(shù)據(jù)庫的存儲管理_第5頁
已閱讀5頁,還剩106頁未讀 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報或認(rèn)領(lǐng)

文檔簡介

第6章數(shù)據(jù)庫的存儲管理

數(shù)據(jù)庫的存儲管理文件的組織結(jié)構(gòu)邏輯文件中的數(shù)據(jù)在物理文件中如何存儲文件的存儲結(jié)構(gòu)邏輯文件中的數(shù)據(jù)在磁盤存儲器上如何存放文件的存取方法針對某種存儲結(jié)構(gòu)的文件怎樣去查找、插入和刪除記錄等問題。數(shù)據(jù)庫的存儲管理數(shù)據(jù)庫存儲管理的數(shù)據(jù)磁盤上數(shù)據(jù)的存儲文件的組織結(jié)構(gòu)文件的存儲結(jié)構(gòu)索引文件的概念數(shù)據(jù)庫存儲管理的數(shù)據(jù)數(shù)據(jù)庫系統(tǒng)實現(xiàn)的一個重要問題如何以最優(yōu)的形式組織和存放數(shù)據(jù)庫中大量有結(jié)構(gòu)的綜合性的持久數(shù)據(jù)最優(yōu)是指存儲效率高,節(jié)省空間存取效率高,代價低數(shù)據(jù)庫存儲管理的數(shù)據(jù)數(shù)據(jù)庫的存儲管理的基本問題數(shù)據(jù)庫是大量有結(jié)構(gòu)的相關(guān)的持久數(shù)據(jù)集合。存儲在存儲介質(zhì)上的數(shù)據(jù)被組織為記錄文件每個記錄是數(shù)據(jù)值的一個集合數(shù)據(jù)值描述了有關(guān)實體、實體屬性及其聯(lián)系存儲4個方面的數(shù)據(jù)數(shù)據(jù)描述,即數(shù)據(jù)外模式、模式、內(nèi)模式數(shù)據(jù)本身數(shù)據(jù)之間的聯(lián)系存取路徑數(shù)據(jù)庫存儲管理的數(shù)據(jù)數(shù)據(jù)庫系統(tǒng)存儲的數(shù)據(jù)數(shù)據(jù)描述系統(tǒng)運(yùn)行時所涉及的各種對象及其屬性的描述信息描述數(shù)據(jù)庫結(jié)構(gòu)及其約束的數(shù)據(jù)庫模式、視圖、存取路徑(索引、散列等)、訪問權(quán)限以及數(shù)據(jù)庫狀態(tài)信息的記錄和統(tǒng)計。系統(tǒng)中對象之間關(guān)系的描述信息包括各級模式間的映射關(guān)系、用戶與子模式間的對應(yīng)關(guān)系等數(shù)據(jù)庫存儲管理的數(shù)據(jù)數(shù)據(jù)庫系統(tǒng)存儲的數(shù)據(jù)數(shù)據(jù)描述有關(guān)數(shù)據(jù)的描述(稱為元數(shù)據(jù))存儲在數(shù)據(jù)庫的數(shù)據(jù)字典中。數(shù)據(jù)字典是數(shù)據(jù)庫系統(tǒng)運(yùn)作的基礎(chǔ),任何數(shù)據(jù)庫操作都要參照數(shù)據(jù)字典的內(nèi)容。關(guān)系數(shù)據(jù)庫中數(shù)據(jù)字典的組織通常與數(shù)據(jù)本身的組織相同。按內(nèi)容的不同在邏輯上組織為若干張表,在物理上就對應(yīng)若干文件而不是一個文件。由于每個文件中存放數(shù)據(jù)量不大,可簡單地用順序文件來組織。數(shù)據(jù)庫存儲管理的數(shù)據(jù)數(shù)據(jù)庫系統(tǒng)存儲的數(shù)據(jù)

數(shù)據(jù)及數(shù)據(jù)間的聯(lián)系在RDBMS中數(shù)據(jù)和數(shù)據(jù)之間的聯(lián)系兩者組織方式相同。數(shù)據(jù)和數(shù)據(jù)之間的聯(lián)系都用一種數(shù)據(jù)結(jié)構(gòu)——“表”來表示。在數(shù)據(jù)庫的物理組織中,每一個表通常對應(yīng)一種文件存儲結(jié)構(gòu)。文件存儲結(jié)構(gòu)是定義一個關(guān)系表文件中記錄的特定組織形式。數(shù)據(jù)庫存儲管理的數(shù)據(jù)數(shù)據(jù)庫系統(tǒng)存儲的數(shù)據(jù)

存取路徑是實現(xiàn)數(shù)據(jù)訪問和存儲的基本手段。在關(guān)系數(shù)據(jù)庫中是指訪問一個關(guān)系表文件中記錄集合的特殊技術(shù)。存取路徑基于表存儲結(jié)構(gòu),或基于所選擇的表上可用的索引。索引是附屬的數(shù)據(jù)庫結(jié)構(gòu),可能是單獨(dú)存儲的一個文件,它支持對表中行的快速訪問。存取路徑的物理組織通常采用B+樹類文件結(jié)構(gòu)和HASH類文件結(jié)構(gòu)。在關(guān)系數(shù)據(jù)庫中,存取路徑和數(shù)據(jù)是分離的,對用戶是隱蔽的。數(shù)據(jù)庫存儲管理的數(shù)據(jù)數(shù)據(jù)庫系統(tǒng)存儲的數(shù)據(jù)

存儲4個方面的數(shù)據(jù)數(shù)據(jù)描述,即數(shù)據(jù)外模式、模式、內(nèi)模式數(shù)據(jù)本身數(shù)據(jù)之間的聯(lián)系存取路徑數(shù)據(jù)庫系統(tǒng)中的這些數(shù)據(jù)都要采用一定的文件組織來組織、存儲起來SQLServer的存儲架構(gòu)數(shù)據(jù)庫存儲管理的數(shù)據(jù)SQLServer的存儲架構(gòu)數(shù)據(jù)庫存儲管理的數(shù)據(jù)SQLServer的存儲架構(gòu)數(shù)據(jù)庫存儲管理的數(shù)據(jù)數(shù)據(jù)庫的存儲管理數(shù)據(jù)庫存儲管理的數(shù)據(jù)磁盤上數(shù)據(jù)的存儲文件的組織結(jié)構(gòu)文件的存儲結(jié)構(gòu)索引文件的概念磁盤上數(shù)據(jù)的存儲計算機(jī)存儲系統(tǒng)的層次結(jié)構(gòu)寄存器高速緩存主存儲器磁盤緩存固定磁盤可移動存儲介質(zhì)磁盤的物理特性S磁盤上數(shù)據(jù)的存儲磁盤的物理特性容量磁盤的總?cè)萘?盤面數(shù)×每盤面的磁道數(shù)×每磁道的扇區(qū)數(shù)×每扇區(qū)的字節(jié)數(shù)。目前磁盤的容量可以達(dá)到1TB。存取時間從發(fā)出讀/寫請求到數(shù)據(jù)傳輸開始這一段時間數(shù)據(jù)傳輸速率磁頭傳輸數(shù)據(jù)的速率,取決于盤片的旋轉(zhuǎn)速度和盤片表面的位密度。每秒可達(dá)幾十兆字節(jié)。磁盤的可靠性用平均故障時間來說明磁盤無故障連續(xù)運(yùn)行的特性。一般在3~8萬小時(3.4~9.1年)內(nèi)不出故障。磁盤上數(shù)據(jù)的存儲磁盤的物理特性存取時間尋道時間(磁頭定位)磁頭定位于包含扇區(qū)S的柱面上方所用的時間。平均尋道時間是1~10ms。旋轉(zhuǎn)延遲時間磁頭處于柱面的上方到定位扇區(qū)S的開始處的上方。平均約需轉(zhuǎn)半圈的時間,1~10ms。傳輸時間盤片旋轉(zhuǎn)經(jīng)過扇區(qū)S所花費(fèi)的時間,受旋轉(zhuǎn)時間的限制。<1msS磁盤上數(shù)據(jù)的存儲磁盤上數(shù)據(jù)的緩沖存取

磁盤是一種低速設(shè)備通常情況下,訪問一個扇區(qū)的時間是10ms級。CPU可以利用訪問一個扇區(qū)的時間執(zhí)行成百上千條指令。優(yōu)化主存和磁盤之間的信息流以優(yōu)化一個數(shù)據(jù)庫系統(tǒng)的性能。DBMS通過在內(nèi)存中開辟“緩沖區(qū)”,采用“預(yù)先讀延遲寫”的磁盤緩沖存取技術(shù)來匹配磁盤和內(nèi)存的存取速度。磁盤上數(shù)據(jù)的存儲磁盤上數(shù)據(jù)的緩沖存取磁盤塊和磁盤緩沖區(qū)數(shù)據(jù)在磁盤上以稱為“塊”的定長存儲單位形式組織。塊是一個磁道上順序存儲的多個相鄰扇區(qū)。只需一次時間延遲來將磁頭定位于包含該塊的起始處。塊(也稱作“頁”)是內(nèi)、外存數(shù)據(jù)交換的基本單位。磁盤中的塊稱為“物理磁盤塊”(或“磁盤塊”),內(nèi)存中臨時存放磁盤塊內(nèi)容的塊稱為“緩沖塊”,所有的內(nèi)存“緩沖塊”組成了“磁盤緩沖區(qū)”。磁盤上數(shù)據(jù)的存儲磁盤上數(shù)據(jù)的緩沖存取磁盤塊和磁盤緩沖區(qū)典型的磁盤塊的大小為4~64KB磁盤塊應(yīng)足夠大,以便能容得下特定應(yīng)用所要訪問的記錄從而避免對磁盤的另一次訪問。磁盤塊增大,數(shù)據(jù)的傳輸時間會增加,大的磁盤塊要求內(nèi)存中有大的緩沖區(qū),而且也可能大大地超出應(yīng)用實際要訪問的信息(如超出一個表所包含的信息)。磁盤上數(shù)據(jù)的存儲磁盤上數(shù)據(jù)的緩沖存取緩沖區(qū)管理器負(fù)責(zé)為數(shù)據(jù)庫上的查詢等處理過程提供內(nèi)存緩沖區(qū)空間分配和管理的子系統(tǒng)。職責(zé)是使處理過程得到它們所需的內(nèi)存,并且盡可能縮小延遲和減少不可滿足的要求。磁盤上數(shù)據(jù)的存儲數(shù)據(jù)庫緩沖區(qū)DiskMemoryXInputOutputI/O操作程序工作區(qū)Read(X)Write(X)X磁盤上數(shù)據(jù)的緩沖存取緩沖區(qū)管理器磁盤上數(shù)據(jù)的存儲緩沖區(qū)管理器磁盤上數(shù)據(jù)的緩沖存取緩沖區(qū)管理器使用緩沖-替換策略對磁盤緩沖區(qū)進(jìn)行維護(hù)。原則:最近被訪問的磁盤塊是活動的,它在不久的將來被再次引用的概率很高,所以這個磁盤塊應(yīng)保存在磁盤緩沖區(qū)中。最近最少使用(LRU,LeastRecentlyUsed)策略其規(guī)則就是丟出最長時間沒有讀或?qū)戇^的塊。一般來說,長時間沒有使用的緩沖塊比那些最近被訪問過的緩沖塊有更小的最近訪問的可能性,LRU是一個有效的策略。近年來在主要的操作系統(tǒng)和數(shù)據(jù)庫系統(tǒng)中,一種改進(jìn)的自適應(yīng)緩存管理替換算法LIRS(LowInter-ReferencerecencySet)及其近似實現(xiàn)方法逐步取代了LRU,更新了存儲管理的關(guān)鍵技術(shù)。磁盤上數(shù)據(jù)的存儲磁盤上數(shù)據(jù)的緩沖存取緩沖區(qū)管理器I/O操作(Input或Output操作)是由操作系統(tǒng)中的文件系統(tǒng)完成的,數(shù)據(jù)庫管理系統(tǒng)只需要調(diào)用操作系統(tǒng)的這一功能。數(shù)據(jù)庫存儲在一個Megatron747磁盤上,它能夠以11ms級別的時間讀取16KB的磁盤塊。在11ms中,一個現(xiàn)代處理器可以執(zhí)行幾百萬的指令。因此在主存中執(zhí)行搜索的附加時間將比塊訪問時間的1%還要少,可以安全地忽略之。磁盤上數(shù)據(jù)的存儲

加速數(shù)據(jù)庫操作,提高數(shù)據(jù)庫的性能的關(guān)鍵技術(shù)是安排好數(shù)據(jù),使得當(dāng)某一個磁盤塊中有數(shù)據(jù)被訪問時,大約在同時很有可能該塊上的其他數(shù)據(jù)也需要被訪問。數(shù)據(jù)庫系統(tǒng)所要解決的問題記錄如何存儲在數(shù)據(jù)文件中,使得應(yīng)用所要訪問的記錄盡量在相同的磁盤塊上,應(yīng)用訪問所需的磁盤I/O操作次數(shù)最少;怎樣盡快找到記錄所在的磁盤塊,使得找到該記錄所需磁盤I/O操作次數(shù)最少。磁盤上數(shù)據(jù)的存儲文件存儲結(jié)構(gòu)文件存取方法數(shù)據(jù)庫的存儲管理數(shù)據(jù)庫存儲管理的數(shù)據(jù)磁盤上數(shù)據(jù)的存儲文件的組織結(jié)構(gòu)文件的存儲結(jié)構(gòu)索引文件的概念在磁盤上,數(shù)據(jù)庫以文件形式組織,文件由記錄組成。記錄表示一個數(shù)據(jù)對象(例如元組)在磁盤塊中的連續(xù)字節(jié)存放。每條記錄由一些字段(相關(guān)數(shù)據(jù)值或數(shù)據(jù)項)集合組成。字段名及其相應(yīng)數(shù)據(jù)類型的值集合即構(gòu)成了一個記錄類型或記錄格式定義。表示數(shù)據(jù)庫(關(guān)系)中數(shù)據(jù)對象的記錄放在一個或多個磁盤塊中。文件的組織結(jié)構(gòu)文件的組織結(jié)構(gòu)記錄的物理表示定長記錄定長記錄是最基本、最常見的記錄存儲方式。在定長記錄中,記錄的每個字段的長度都是固定的。系統(tǒng)可以確定每個字段相對于記錄開始位置的起始字節(jié)位置,定位字段值。變長記錄文件中的不同記錄的大?。ㄗ止?jié)數(shù))不同。文件的組織結(jié)構(gòu)定長記錄對于關(guān)系模式S(SNO,SN,SEX,SB,SD)若進(jìn)行如下定義:CREATETABLES(SNOCHAR(10)PRIMARYKEY,

SNCHAR(20)NOTNULL,

SEXCHAR(2),

SBDATETIME,

SDCHAR(20),

CHECK(SEXIN(‘男’,‘女’)));文件的組織結(jié)構(gòu)定長記錄一個定長的S記錄的格式文件的組織結(jié)構(gòu)定長記錄定長記錄在磁盤塊中的一種存儲方式

塊首部存儲如下一些信息:與一個或多個其他相關(guān)塊的鏈接。塊中的元組屬于哪個關(guān)系的信息。一個給出每一條記錄在塊內(nèi)的偏移量的“目錄”;指明最后一次修改和/或存取塊的時間戳。文件的組織結(jié)構(gòu)變長記錄文件記錄均屬于同一記錄類型,但有一個或多個字段是大小變化的不同類型的相關(guān)記錄在磁盤塊中聚集存儲,文件包含不同的記錄類型的記錄等。文件的組織結(jié)構(gòu)變長記錄在變長記錄中的字段存在如下不同格式:大小變化的數(shù)據(jù)項重復(fù)字段如果在一個對象的記錄中存儲關(guān)聯(lián)的對象的記錄,則有多少對象被關(guān)聯(lián)到指定對象,則在該記錄中就會存儲多少關(guān)聯(lián)的記錄??勺兏袷降挠涗浻袝r無法事先確定記錄的字段是什么,或每一個字段出現(xiàn)多少次。比如表示一個XML元素的一條記錄,該XML元素可沒有任何約束,或可能有重復(fù)的子元素和可選屬性等。極大的字段現(xiàn)代DBMS支持屬性值非常大的屬性,字段可能是一些非結(jié)構(gòu)化的大對象數(shù)據(jù),如圖像、數(shù)字視頻或音頻流,或者自由文本,被稱為BLOB(BinaryLargeObjects,二進(jìn)制大對象)。例如,一個電影記錄可能有一個2G大小的MPEG編碼字段,還有一些普通的字段,比如電影標(biāo)題等。文件的組織結(jié)構(gòu)變長記錄對于關(guān)系模式S(SNO,SN,SEX,SB,SD)若進(jìn)行如下定義:CREATETABLES(SNOCHAR(10)PRIMARYKEY,

SNVARCHAR(20)

NOTNULL,

SEXCHAR(2),

SBDATATIME,

SDVARCHAR(20),

CHECK(SEXIN(‘男’,‘女’)));文件的組織結(jié)構(gòu)變長記錄

具有變長字符串的S記錄格式文件的組織結(jié)構(gòu)變長記錄變長記錄在磁盤塊中的一種有偏移量表的存儲方式數(shù)據(jù)庫的存儲管理數(shù)據(jù)庫存儲管理的數(shù)據(jù)磁盤上數(shù)據(jù)的存儲文件的組織結(jié)構(gòu)文件的存儲結(jié)構(gòu)索引文件的概念文件的存儲結(jié)構(gòu)數(shù)據(jù)庫文件的存儲結(jié)構(gòu)形式堆文件順序文件聚集文件散列文件文件的存儲結(jié)構(gòu)堆文件最簡單的數(shù)據(jù)文件結(jié)構(gòu)。數(shù)據(jù)記錄之間沒有特定的順序,文件行的順序是任意的。將一條新記錄插入到文件中,只需找到一個有一些空閑空間的塊,或當(dāng)塊沒有空閑空間時就找一個新塊,然后將記錄存儲在那里。對于新建立的文件,記錄按照其插入的先后順序存放,新產(chǎn)生的記錄行能有效地追加在文件的尾部。文件的存儲結(jié)構(gòu)堆文件優(yōu)點實現(xiàn)簡單,不需要特殊處理。適用于對表的查詢涉及所有行,且行的訪問順序并不重要的訪問。缺點查詢效率低,對常見的兩類查詢(等值查詢和范圍查詢)無任何優(yōu)勢。刪除操作只是加一個刪除標(biāo)記,導(dǎo)致存儲空間的浪費(fèi),搜索時間變長。文件的存儲結(jié)構(gòu)堆文件用F表示一個文件所占的磁盤塊數(shù),插入、刪除和查詢的平均磁盤I/O次數(shù)為F/2。若表中沒有相同的記錄存在,需要磁盤I/O次數(shù)將是F。

【例】設(shè)一個關(guān)系有106個元組,在每個磁盤塊中可存放10個這樣的元組記錄,則該關(guān)系大約占用105個磁盤塊。若該關(guān)系中的元組構(gòu)成了一個堆文件,進(jìn)行記錄定位所需要的磁盤I/O次數(shù)為:

105/2或105文件的存儲結(jié)構(gòu)順序文件按關(guān)系中某些屬性值的排序順序存儲記錄的文件稱為順序文件,排序所基于的屬性稱為排序?qū)傩裕ㄗ侄危?。關(guān)系表S按屬性SNO進(jìn)行順序存儲文件的存儲結(jié)構(gòu)順序文件優(yōu)點如果查找條件是基于排序?qū)傩缘闹?,可對磁盤文件進(jìn)行二分查找,得到比線性查找更快的存取速度。假設(shè)文件共有F塊,二分查找一般只需存取log2F。如果查找屬性與排序?qū)傩韵嗤?,則可高效地完成等值查詢和范圍查詢。

【例】設(shè)一個關(guān)系有106個元組,在每個磁盤塊中可存放10個這樣的元組,則該關(guān)系大約占用105個磁盤塊。若該關(guān)系中的元組已經(jīng)按照主鍵值從小到大的順序構(gòu)成了一個順序文件。按照一個主鍵值進(jìn)行記錄定位所需要的磁盤I/O次數(shù)為:

log2105≈16.6≈17順序文件文件的存儲結(jié)構(gòu)文件的存儲結(jié)構(gòu)順序文件缺點插入和刪除操作要保持記錄的存儲是有序的,代價很大。在塊中滑動記錄以在合適的地點得到所需的空間,將新記錄插入到塊中,并在此塊的偏移量表中添加指向此記錄的新指針。如果塊中沒有空間用于新記錄的存儲,可能就要到“鄰近塊”中找空間或創(chuàng)建一個溢出塊。如果要刪除一個記錄,則執(zhí)行相反的操作,回收記錄空間,記錄在塊中滑動,讓塊中間總有一個未用的區(qū)域。不能滑動記錄,則需要在塊首部維護(hù)一個可用空間列表,當(dāng)向塊中插入一條新記錄時,可知道可用區(qū)域在哪里。刪除記錄時,通常的方法是在記錄處放一個刪除標(biāo)記,并一直保留到對整個數(shù)據(jù)庫進(jìn)行重構(gòu)。文件的存儲結(jié)構(gòu)順序文件缺點插入和刪除操作要保持記錄的存儲是有序的,代價很大。在文件中,為每個記錄增加一個指針字段,根據(jù)屬性值的大小用指針把記錄連接起來。對于刪除操作,可通過修改指針實現(xiàn)。而將被刪記錄鏈接成一個自由空間,以便插入新記錄時使用。對于插入操作,在指針鏈中找到插入的位置(應(yīng)插到哪個記錄的前面),在找到記錄的塊內(nèi),如果有自由空間,那么就在該位置插入新記錄,并加入到指針鏈中;如果無自由空間,那么就只能插入到溢出塊中。文件的存儲結(jié)構(gòu)順序文件順序文件初始建立時,一般存儲記錄的物理順序和排序鍵值的順序一致,以便訪問數(shù)據(jù)時減少對磁盤塊的操作次數(shù)。多次插入和刪除操作后,很難維持這種一致的狀態(tài)。此時應(yīng)該對文件重組,使其物理順序和排序鍵值的順序一致,以提高查找速度。文件的存儲結(jié)構(gòu)聚集文件聚集,又稱聚簇(cluster)。文件中元組緊縮到能存儲這些元組的盡可能少的塊中。通常聚集文件把某個或某些屬性(稱為聚集碼,clusterkey)上具有相同值的元組集中存放在連續(xù)的物理塊中。聚集功能可以大大提高按聚集碼進(jìn)行查詢的效率。文件的存儲結(jié)構(gòu)聚集文件聚集功能不但適用于單個關(guān)系,也適用于經(jīng)常進(jìn)行連接操作的多個關(guān)系。即把多個連接關(guān)系的元組按連接屬性值聚集存放(連接屬性為聚集碼),從而大大提高連接操作的效率。SELECTS.SNO,SN,CNO,GRADEFROMS,SCWHERES.SNO=SC.SNO;文件的存儲結(jié)構(gòu)聚集文件文件的存儲結(jié)構(gòu)散列文件根據(jù)記錄的屬性值K(一般為主鍵),使用一個散列函數(shù)h(hashfunction,又稱哈希函數(shù))計算得到的函數(shù)值h(K)確定記錄的地址,對記錄進(jìn)行存儲和訪問。該屬性稱為散列鍵(或散列字段)。散列文件使用桶(bucket)作為基本的存儲單位,桶可以是磁盤中的塊,也可以是比較大的空間。文件的存儲結(jié)構(gòu)H(Ki)H(Ki)H(Ki)一個桶中存放散列函數(shù)值相同的多個記錄桶內(nèi)記錄的散列鍵值可能是不相同的文件的存儲結(jié)構(gòu)散列文件優(yōu)點根據(jù)散列鍵值可以直接得到記錄的磁盤塊地址,I/O操作次數(shù)少,訪問性能很高。如果絕大多數(shù)桶都只由單個塊組成,那么一般的查詢只需一次磁盤I/O,文件的插入和刪除也只需要兩次磁盤I/O。缺點只適用于按散列鍵訪問記錄。存在地址沖突問題。在實際應(yīng)用中,記錄在散列鍵值上的分布往往是不均衡的,在某些桶中存在空間浪費(fèi)現(xiàn)象,而在另外一些桶中則存在空間溢出問題。數(shù)據(jù)庫的存儲管理數(shù)據(jù)庫存儲管理的數(shù)據(jù)磁盤上數(shù)據(jù)的存儲文件的組織結(jié)構(gòu)文件的存儲結(jié)構(gòu)索引文件的概念索引文件的概念索引的概念關(guān)系數(shù)據(jù)文件中某屬性(組)上的索引是一種數(shù)據(jù)結(jié)構(gòu),它提供了在該屬性(組)上快速查找具有某個特定值的元組的方法。索引可以建立在記錄的某一屬性或者屬性組上,這個屬性或者屬性組就被稱為索引鍵。針對某個屬性建立索引,就是根據(jù)此屬性值將記錄進(jìn)行邏輯排序(有序索引)。索引文件的概念索引的概念索引結(jié)構(gòu)可以存儲在一個單獨(dú)的文件中,該文件稱為索引文件。存放記錄的索引鍵值以及指向記錄本身的指針(記錄的存儲地址),并且按照索引鍵值的順序進(jìn)行排序。索引文件的每一條記錄被稱為索引項,索引項是一個索引鍵值和一個記錄指針構(gòu)成的鍵-指針對

<索引鍵值,地址指針>索引文件的概念索引的作用使用索引可以明顯加快數(shù)據(jù)查詢的速度。索引記錄中只含有索引鍵值和地址指針,索引文件所占磁盤塊數(shù)量通常比數(shù)據(jù)文件的少,一般可一次讀入內(nèi)存。索引項是經(jīng)過排序的,可以使用二分查找法來查找索引鍵值所在記錄。通過索引可以大大減少了對磁盤的I/O操作次數(shù),節(jié)約處理查詢的時間,加快查詢速度。索引文件的概念索引的概念【例】考慮在例4-1中的“學(xué)生-課程”數(shù)據(jù)庫中進(jìn)行如下查詢:SELECT*FROMSWHERESEX=’女’ANDSD=’計算機(jī)系’;關(guān)系中可能存在10000個學(xué)生元組,但只有大約200人是計算機(jī)系的,其中女同學(xué)只有50個左右。索引文件的概念索引的概念【例】在例4-1中的“學(xué)生-課程”數(shù)據(jù)庫中增加一個專業(yè)系的關(guān)系模式D(DN,DD),其中DN為專業(yè)系名稱,DD為系主任姓名。對于如下查詢SELECTDDFROMS,DWHERESNO=‘s06’ANDS.SD=D.DN;查詢要求找出學(xué)號為“s06”的學(xué)生所在系主任的名字。索引文件的概念索引的分類聚集索引和非聚集索引稠密索引和稀疏索引多級索引索引文件的概念聚集索引和非聚集索引如果在數(shù)據(jù)文件的相同的屬性或?qū)傩越M上,索引記錄和數(shù)據(jù)記錄都是有序的,則稱該有序索引為聚集索引(聚簇索引,ClusteredIndex),否則就稱之為非聚集索引(非聚簇索引,UnclusteredIndex)?!熬奂饕钡慕箶?shù)據(jù)文件中記錄的物理順序與索引記錄的排列順序一致。數(shù)據(jù)文件最多只能在一個排序鍵上排序,最多只有一個聚集索引,聚集索引通常又稱做主索引,非聚集索引通常稱做輔助索引(或次索引)。索引文件的概念聚集索引和非聚集索引聚集索引非聚集索引索引文件的概念聚簇索引和非聚簇索引在聚簇索引中,物理位置上相近的索引項在一定程度上預(yù)示相應(yīng)數(shù)據(jù)記錄的索引鍵值也很近??杉涌彀茨硨傩粤羞M(jìn)行范圍查詢的效率?!纠恳粋€數(shù)據(jù)文件可能存儲在10000個磁盤塊上,但對一個特定的查詢(等值查詢或范圍查詢)來說,只有100條記錄滿足條件。如果數(shù)據(jù)存儲在沒有索引文件的堆文件中,可能需要10000次I/O操作;如果在這個查詢的WHERE子句的查找屬性上有一個非聚集索引是可用的,那么檢索這個數(shù)據(jù)文件最多只需要100次I/O操作。如果在查找屬性上有一個聚集索引是可用的,且每個磁盤塊平均包含20條數(shù)據(jù)記錄,可能只需要5次I/O操作,檢索5個磁盤塊。索引文件的概念聚簇索引和非聚簇索引某些數(shù)據(jù)庫系統(tǒng)中聚簇索引總是與數(shù)據(jù)文件集成為一種存儲結(jié)構(gòu)。索引項包含數(shù)據(jù)記錄,由語句CREATETABLE創(chuàng)建表時同時創(chuàng)建。非聚簇索引存儲在一個單獨(dú)的文件中,由語句CREATEINDEX來創(chuàng)建。索引文件的概念聚簇索引和非聚簇索引定義基本表同時創(chuàng)建索引的語句格式為

CREATETABLE<表名>(<列名><類型>|AS<表達(dá)式>[<屬性列約束>][,…][<表約束>])PRIMARYKEYCLUSTERED|NONCLUSTERED定義該屬性列為主鍵并建立聚簇或非聚簇索引。PRIMARYKEY[CLUSTERED|NONCLUSTERED](<列名組>)定義<列名組>為表的主鍵并建立聚簇或非聚簇索引。索引文件的概念聚簇索引和非聚簇索引建立索引的語句格式CREATE[UNIQUE][CLUSTERDE]INDEX<索引名>ON<表名>(<列名>[<次序>][,<列名>[<次序>]]...)[其他參數(shù)];

UNIQUE表示該索引的每一索引值只對應(yīng)唯一的數(shù)據(jù)記錄。CLUSTER表示要建立的索引是聚簇索引?!捌渌麉?shù)”是與物理存儲有關(guān)的參數(shù)。PAD-INDEX:為每一內(nèi)部結(jié)點頁指定分配空間大小。FILEFACTOR=<頁充滿度>:指定葉子數(shù)和索引的充滿度。索引文件的概念聚簇索引和非聚簇索引索引文件的概念聚簇索引和非聚簇索引索引文件的概念稠密索引和稀疏索引按照索引對數(shù)據(jù)庫記錄的覆蓋程度稠密索引(DenseIndices)稀疏索引(SparseIndices)索引文件的概念稠密索引和稀疏索引稠密索引的定義(一)索引鍵為數(shù)據(jù)文件的候選鍵,可為數(shù)據(jù)文件中的每一條記錄建立一個索引記錄(索引項)。

基于堆文件的候選鍵建立的稠密索引(非聚集索引)基于候選鍵排序的順序文件上的稠密索引(聚集索引)索引文件的概念稠密索引和稀疏索引稠密索引的定義(二)索引鍵為數(shù)據(jù)文件的非候選鍵,且數(shù)據(jù)文件為索引鍵上的順序文件,則為數(shù)據(jù)文件中具有相同索引鍵值的記錄建立一個索引記錄,索引記錄包括索引鍵值和指向具有該值的記錄鏈表中第一個記錄的指針?;诜呛蜻x鍵排序的順序文件上的稠密索引(聚集索引)索引文件的概念稠密索引和稀疏索引稠密索引的定義(三)索引鍵為數(shù)據(jù)文件的非候選鍵,且數(shù)據(jù)文件為非順序文件(堆文件),或數(shù)據(jù)文件中記錄順序由其他屬性上主索引確定的,而不是按輔助索引的索引鍵順序物理存儲的,因此索引文件中要存放指向數(shù)據(jù)文件中具有該索引鍵值的所有記錄的指針?;诙盐募姆呛蜻x鍵建立的稠密索引(輔助索引)索引文件的概念稠密索引和稀疏索引稠密索引的定義(三)通過在稠密索引和數(shù)據(jù)文件之間加一個記錄指針桶(bucket)來節(jié)省存儲空間。

可以在不訪問數(shù)據(jù)文件記錄的前提下利用桶的指針來幫助回答一些查詢和減少一些I/O開銷。比如,當(dāng)查詢有多個條件,而每個條件都有一個可用的輔助索引時,可通過在主存中將指針集合求交來找到滿足所有條件的指針,然后只需要檢索交集中指針指向的記錄。索引文件的概念稠密索引和稀疏索引稀疏索引的定義對于順序數(shù)據(jù)文件,可以在索引文件中只為數(shù)據(jù)文件的每個磁盤塊設(shè)一個鍵-指針對,來記錄該磁盤塊中第一條數(shù)據(jù)記錄的索引鍵值及該磁盤塊的首地址?;诤蜻x鍵排序的順序文件上的稀疏索引(聚集索引)基于非候選鍵排序的順序文件上的稀疏索引(聚集索引)索引文件的概念稠密索引和稀疏索引稀疏索引稀疏索引必須是聚集的有序文件才允許定位不被索引引用的記錄。查找一條鍵值為K的記錄,首先在索引文件中找到索引鍵值小于等于K的索引項中索引鍵值最大的索引項。然后根據(jù)這個索引項的指針找到記錄所在磁盤塊,在調(diào)入內(nèi)存的磁盤塊中進(jìn)行搜索,以找到鍵值為K的記錄,或遇到索引鍵值更大的記錄或遇到文件尾為止,此時說明不存在鍵值為K的記錄。

【例】設(shè)一個關(guān)系有106個元組,在每個磁盤塊中可存放10個這樣的元組,則該關(guān)系大約占用105個磁盤塊。假設(shè)每個磁盤塊可以存放100個索引項,且使用二分查找法找到所需索引項。為該數(shù)據(jù)文件按主關(guān)鍵字建立一個稠密索引。則該稠密索引共有106個索引項,需要占用:

104個磁盤塊利用該稠密索引進(jìn)行記錄定位需要的磁盤I/O次數(shù)為:

log2104

+1≈13.3+1≈15

稠密索引和稀疏索引訪問索引文件的磁盤I/O索引文件的概念

【例】設(shè)一個關(guān)系有106個元組,在每個磁盤塊中可存放10個這樣的元組,則該關(guān)系大約占用105個磁盤塊。假設(shè)每個磁盤塊可以存放100個索引項,且使用二分查找法找到所需索引項。若該數(shù)據(jù)文件已經(jīng)按照主關(guān)鍵字值從小到大的順序構(gòu)成了一個順序文件,可為該順序數(shù)據(jù)文件建立一個稀疏索引,則該稀疏索引共有105個索引項,需要占用:

103個磁盤塊利用該稀疏索引進(jìn)行記錄定位需要的磁盤I/O次數(shù)為:

log2103

+1≈9.97+1≈11

稠密索引和稀疏索引索引文件的概念稠密索引和稀疏索引稠密索引與稀疏索引的區(qū)別索引文件的定義不同稀疏索引只能用于順序文件上的索引組織。稠密索引中的每個索引項對應(yīng)數(shù)據(jù)文件中的一條(或多條索引鍵值相同)記錄,而稀疏索引中的每個索引項則對應(yīng)數(shù)據(jù)文件中的一個磁盤塊。需要的磁盤空間大小不同在記錄的查找定位功能上存在差別稠密索引:可以直接回答是否存在鍵值為K的記錄。稀疏索引:需要額外的磁盤操作,即需要將相應(yīng)的數(shù)據(jù)文件中的磁盤塊讀入內(nèi)存后才能判別該記錄是否存在。索引文件的概念索引文件的概念多級索引(MultilevelIndex)為了能夠快速定位查找記錄的索引項,從而更快地找到所需的數(shù)據(jù)記錄,引入多級索引結(jié)構(gòu)將直接建立在數(shù)據(jù)文件上的索引稱為第一級索引,根據(jù)第一級索引文件建立的索引稱為第二級索引,依此類推,從而可以建立一個多級索引結(jié)構(gòu)。在多級索引組織結(jié)構(gòu)中,第一級索引可以是稠密索引,也可以是稀疏索引。從第二級索引開始建立的都是稀疏索引。多級索引索引文件的概念在順序文件上建一級稠密索引、二級稀疏索引在堆文件上建一級稠密索引、二級稀疏索引多級索引索引文件的概念在順序文件上建一級稀疏索引、二級稀疏索引在順序文件上建一級稀疏索引、二級稀疏索引【例】設(shè)一個關(guān)系有106個元組,在每個磁盤塊中可存放10個這樣的元組,則該關(guān)系大約占用105個磁盤塊。假設(shè)每個磁盤塊可以存放100個索引項。為該數(shù)據(jù)文件按主關(guān)鍵字建立一個稠密索引。則該稠密索引共有106個索引項,需要占用104個磁盤塊。在該稠密索引文件上再建立一個稀疏索引,新建立的稀疏索引文件中有104個索引項,需要占用:

100個磁盤塊在該二級稀疏索引文件上再建立一個稀疏索引,新建立的稀疏索引文件中有102個索引項,需要占用:

1個磁盤塊(可常駐內(nèi)存)利用該多級索引進(jìn)行記錄定位需要的磁盤I/O次數(shù)為:

1+1+1=3多級索引索引文件的概念多級索引與單級索引的性能比較多級索引索引文件的概念33索引文件的結(jié)構(gòu)索引可以有多種形式,每種索引都使用一種特定的數(shù)據(jù)結(jié)構(gòu)來實現(xiàn)利用索引提高查詢速度的目的。索引在提高數(shù)據(jù)查詢性能的同時,不僅需要額外的存儲空間,同時還會影響系統(tǒng)進(jìn)行數(shù)據(jù)插入、刪除和修改時的性能。需要根據(jù)實際的數(shù)據(jù)應(yīng)用,綜合考慮各方面的因素,來選擇適合的索引結(jié)構(gòu)。索引文件的結(jié)構(gòu)選用何種數(shù)據(jù)結(jié)構(gòu)主要基于以下考慮:存取類型用戶是根據(jù)屬性值查找記錄,還是根據(jù)屬性值的范圍查找記錄。存取時間通過索引查找特定記錄或記錄集所花費(fèi)的時間。插入時間找到正確的位置插入新記錄所花時間和修改索引結(jié)構(gòu)所花的時間。刪除時間找到被刪記錄并進(jìn)行刪除所花時間和修改索引結(jié)構(gòu)所花的時間。索引空間的開銷索引結(jié)構(gòu)所需要的額外存儲空間。索引實際上是用空間代價來換取系統(tǒng)查詢性能的提高。索引文件的結(jié)構(gòu)常用的索引文件結(jié)構(gòu)采用順序文件來實現(xiàn)單級索引索引順序文件,IBM早期的大量系統(tǒng)中都應(yīng)用了這種文件組織。各級索引都是順序文件,在數(shù)據(jù)文件是非順序文件,或索引鍵值的變化比較頻繁的情況下,索引順序文件自身的維護(hù)非常復(fù)雜,對索引項的插入、修改和刪除操作會導(dǎo)致索引項在索引文件中的大量移動。采用B-樹數(shù)據(jù)結(jié)構(gòu)來實現(xiàn)多級索引為了充分發(fā)揮多級索引的作用,同時減少索引文件的插入和刪除所帶來的問題,目前大多數(shù)數(shù)據(jù)庫系統(tǒng)使用B-樹數(shù)據(jù)結(jié)構(gòu)來實現(xiàn)動態(tài)多級索引?;谏⒘谢蛘咂渌檎覕?shù)據(jù)結(jié)構(gòu)構(gòu)建索引索引文件的結(jié)構(gòu)B+樹結(jié)構(gòu)B-樹是一種多級索引組織方法,是適合于組織存放在外存的大型磁盤文件的一種樹狀索引結(jié)構(gòu)。

B-樹把索引文件所占的磁盤存儲塊組織成一棵樹,這棵樹是平衡的。索引文件的結(jié)構(gòu)B+樹結(jié)構(gòu)對應(yīng)于每個B-樹索引都有一個參數(shù)m,它決定了B-樹的所有磁盤存儲塊的布局。在數(shù)據(jù)庫技術(shù)中,一棵m階平衡樹或者為空,或者滿足以下條件:每個結(jié)點至多有m棵子樹;根結(jié)點或為葉結(jié)點,或至少有兩棵子樹;每個非葉結(jié)點至少有[m/2]棵子樹;從根結(jié)點到葉結(jié)點的每一條路徑都有同樣的長度,即葉結(jié)點在同一層次上。索引文件的結(jié)構(gòu)B+樹結(jié)構(gòu)B+樹的組織一棵m階B+樹是平衡樹,按下列方式組織:每個結(jié)點中至多有m-1個索引鍵值K1、K2、…、Km-1m個指針P1、P2、…、Pm,且K1<K2<…<Km-1形式如下:

<<K1,P1>,<K2,P2>,…,<Km-1,Pm-1>,Pm>P1K1P2K2…Pm-1Km-1PmB+樹結(jié)構(gòu)B+樹的組織4階B+樹索引文件的結(jié)構(gòu)索引文件的結(jié)構(gòu)B+樹結(jié)構(gòu)B+樹的組織葉結(jié)點中的指針Pi指向一個索引鍵值為Ki的數(shù)據(jù)文件記錄或一個記錄指針桶,且指針桶中的每個指針指向具有索引鍵值為Ki的一條數(shù)據(jù)文件記錄。每個葉結(jié)點最多可存放m-1個索引鍵值Ki,最少也要存放[(m-1)/2]個索引鍵值Ki。各葉結(jié)點中的Ki值不重復(fù)不相交,構(gòu)成數(shù)據(jù)文件的一級稠密索引,各葉結(jié)點中的索引鍵值Ki按升序排列。利用葉結(jié)點中的最后一個指針Pm,指向下一個鍵值大于Km-1的葉結(jié)點存儲塊,將所有葉結(jié)點按索引鍵值的排序順序鏈接在一起,可提供對數(shù)據(jù)文件的基于索引鍵的有序訪問。指向下一個葉子結(jié)點指向一個索引鍵值為7的數(shù)據(jù)文件記錄或一個記錄指針桶,且桶中的每個指針指向具有索引鍵值為7的一條數(shù)據(jù)文件記錄。

B+樹結(jié)構(gòu)B+樹的組織索引文件的結(jié)構(gòu)最多m-1個索引鍵值,最少也要[(m-1)/2]索引文件的結(jié)構(gòu)B+樹結(jié)構(gòu)B+樹的組織非頁結(jié)點形成了葉結(jié)點上的一個多級稀疏索引,如果非頁結(jié)點有n個指針,則[m/2]≤n≤m,指針的數(shù)目n稱為結(jié)點的“扇出端數(shù)”。結(jié)點中將有n-1個鍵值。對于Pi指向的子樹中的索引鍵值X,有:1<i<n時,Ki-1≤X<Kii=1時,X<Ki,即X<K1i=n時,Ki-1≤X,即Kn-1≤X若n<m,非頁節(jié)點中指針Pn之后的所有空閑空間都作為預(yù)留空間,可用于插入新的索引項。指向23≤K

<31的子樹B+樹結(jié)構(gòu)B+樹的組織索引文件的結(jié)構(gòu)N=2,n-1個鍵值索引文件的結(jié)構(gòu)B+樹結(jié)構(gòu)B+樹的組織根結(jié)點與其他非葉結(jié)點不同,它包含的指針數(shù)可以小于[m/2],但必須至少包含兩個指針。這與只有某級索引需要多個磁盤塊(大于1)存儲時,才需要建上一級索引相一致。所有被使用的鍵和指針通常都存放在結(jié)點的開頭位置,但葉節(jié)點的第n個指針例外,該指針要放在最后,用來指向下一個葉結(jié)點。索引文件的結(jié)構(gòu)B+樹結(jié)構(gòu)B+樹的組織B+樹的結(jié)點較大,一般占一個磁盤塊大小,每個結(jié)點中可以有大量的指針,因此B+樹一般“胖而矮”,不像二叉樹那樣“瘦而高”。一般在存儲塊能容納m-1個鍵值和m個指針的情況下,應(yīng)把m取得盡可能大?!纠考俣ù疟P塊大小為4KB,且整數(shù)型鍵值占4個字節(jié),指針占8個字節(jié)。若不考慮磁盤塊塊首部信息所占空間,那么m值最大可取多少?4(m-1)+8m≤4096的最大整數(shù)值,即m=341索引文件的結(jié)構(gòu)B+樹結(jié)構(gòu)B+樹的查詢在B+樹中查找索引鍵值為K的記錄,查詢開始結(jié)點為T(初始為根節(jié)點),則查詢過程可如下進(jìn)行:(1)如果結(jié)點T的鍵值為K1、K2、…、Kn,只有一個子結(jié)點可找到具有鍵值K的葉結(jié)點。如果K<K1,則為第一個子結(jié)點;如果K1≤K<K2,則為第二個子結(jié)點……如果Kn≤

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論