第14講數(shù)據(jù)庫(kù)的存儲(chǔ)管理

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

log2104

+1≈13.3+1≈15

稠密索引和稀疏索引訪問(wèn)索引文件的磁盤I/O索引文件的概念

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

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

log2103

+1≈9.97+1≈11

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

100個(gè)磁盤塊在該二級(jí)稀疏索引文件上再建立一個(gè)稀疏索引，新建立的稀疏索引文件中有102個(gè)索引項(xiàng)，需要占用：

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

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

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

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

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

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