第7章 數(shù)據(jù)庫存儲(chǔ)結(jié)構(gòu)課件

1、第7章 數(shù)據(jù)庫存儲(chǔ)結(jié)構(gòu)目 錄B+樹索引樹索引7.4文件組織文件組織7.1記錄組織記錄組織7.2順序索引順序索引7.37.57.6物理數(shù)據(jù)庫設(shè)計(jì)物理數(shù)據(jù)庫設(shè)計(jì)散列散列存儲(chǔ)介質(zhì)的分類 幾種有代表性的存儲(chǔ)介質(zhì)：高速緩沖存儲(chǔ)器(cache)、主存儲(chǔ)器(main memory)、快閃存儲(chǔ)器(flash memory)、磁盤存儲(chǔ)器(magnetic-disk storage)、光存儲(chǔ)器(optical storage)和磁帶存儲(chǔ)器(tape storage)等。 計(jì)算機(jī)的三級存儲(chǔ)體系 ：根據(jù)不同存儲(chǔ)介質(zhì)的速度和成本，可以把它們按層次結(jié)構(gòu)組織起來，層次越高，每單位存儲(chǔ)容量價(jià)格越貴，但速度越快。如圖7-1所示

2、。 存儲(chǔ)易失性問題 ：易失性存儲(chǔ)在設(shè)備斷電后將丟失所有內(nèi)容。一級存儲(chǔ)為易失性存儲(chǔ)，而二、三級存儲(chǔ)系統(tǒng)都是非易失性存儲(chǔ)。 磁盤的主要性能指標(biāo)訪問時(shí)間(access time)是從發(fā)出讀寫請求到數(shù)據(jù)開始傳輸之間的時(shí)間。 為了訪問(即讀或?qū)?磁盤上指定扇區(qū)的數(shù)據(jù)，磁盤臂首先需要移動(dòng)以定位到正確的磁道，所需時(shí)間稱為尋道時(shí)間(seek time)； 然后等待磁盤旋轉(zhuǎn)直到指定的扇區(qū)出現(xiàn)在它下方，所需的時(shí)間稱為旋轉(zhuǎn)等待時(shí)間(rotational latency time) 。 訪問時(shí)間=尋道時(shí)間+旋轉(zhuǎn)等待時(shí)間。數(shù)據(jù)傳輸率(data-tranfer rate)是從磁盤獲得數(shù)據(jù)或者向磁盤存儲(chǔ)數(shù)據(jù)的速率。 磁盤的

3、平均故障時(shí)間(mean time to failure, MTTF)是指磁盤無故障連續(xù)運(yùn)行時(shí)間的平均值。磁盤塊(block)是一個(gè)邏輯單元，它是包含固定數(shù)目的連續(xù)扇區(qū)。數(shù)據(jù)在磁盤和主存儲(chǔ)器之間以塊為單位傳輸。 存儲(chǔ)訪問 緩沖區(qū)(buffers)是主存儲(chǔ)器中用于存儲(chǔ)磁盤塊的副本的區(qū)域。緩沖區(qū)中的每個(gè)塊總有一個(gè)副本存放在磁盤上，但是在磁盤上的副本可能比在緩沖區(qū)中的副本舊。 負(fù)責(zé)緩沖區(qū)空間分配和管理的子系統(tǒng)稱為緩沖區(qū)管理器。 數(shù)據(jù)庫系統(tǒng)通過緩沖區(qū)實(shí)現(xiàn)對磁盤上數(shù)據(jù)的存儲(chǔ)訪問。 在數(shù)據(jù)庫管理系統(tǒng)中，數(shù)據(jù)的存取過程如圖7-2所示。 具體步驟如下：(1) 應(yīng)用程序通過DML向DBMS發(fā)出存取請求，如Sele

4、ct語句；(2) 對命令進(jìn)行語法檢查，正確后檢查語義和用戶權(quán)限（通過數(shù)據(jù)字典DD），并決定是否接收；(3) 執(zhí)行查詢優(yōu)化，將命令轉(zhuǎn)換成一串單記錄的存取操作序列；(4) 執(zhí)行存取操作序列反復(fù)執(zhí)行以下各步，直到結(jié)束：(5) 在緩沖區(qū)中找記錄，若找到轉(zhuǎn)在緩沖區(qū)中找記錄，若找到轉(zhuǎn)(10)，否則轉(zhuǎn)，否則轉(zhuǎn)(6)；(6) 查看存儲(chǔ)模式，決定從哪個(gè)文件、用什么方式讀取物理記錄；查看存儲(chǔ)模式，決定從哪個(gè)文件、用什么方式讀取物理記錄；(7) 根據(jù)根據(jù)(6)的結(jié)果向操作系統(tǒng)的結(jié)果向操作系統(tǒng)(OS)發(fā)出讀取記錄的命令；發(fā)出讀取記錄的命令；(8) OS執(zhí)行該命令，并讀取記錄數(shù)據(jù)；執(zhí)行該命令，并讀取記錄數(shù)據(jù)；(9) 在

5、在OS控制下，將讀出的記錄送入控制下，將讀出的記錄送入系統(tǒng)緩沖區(qū)系統(tǒng)緩沖區(qū)；(10) RDBMS根據(jù)查詢命令和根據(jù)查詢命令和DD的內(nèi)容導(dǎo)出用戶所要讀取的記錄格式；的內(nèi)容導(dǎo)出用戶所要讀取的記錄格式；(11) RDBMS將數(shù)據(jù)從將數(shù)據(jù)從系統(tǒng)緩沖區(qū)系統(tǒng)緩沖區(qū)中送入中送入用戶工作區(qū)用戶工作區(qū)；(12) RDBMS將執(zhí)行狀態(tài)信息將執(zhí)行狀態(tài)信息(成功或不成功等成功或不成功等)返回給應(yīng)用程序；返回給應(yīng)用程序；(13) 應(yīng)用程序?qū)ぷ鲄^(qū)中讀出的數(shù)據(jù)進(jìn)行相應(yīng)處理。應(yīng)用程序?qū)ぷ鲄^(qū)中讀出的數(shù)據(jù)進(jìn)行相應(yīng)處理。定長記錄與變長記錄 文件在邏輯上可看作記錄的序列，這些記錄被映射到磁盤的物理塊上。 用文件表示邏輯數(shù)據(jù)模型的

6、不同方式：定長記錄和變長記錄 所謂定長記錄指文件中所有記錄均具有同樣的字節(jié)長度，如圖7-3所示： 這種簡單的方法明顯地有兩個(gè)問題： 刪除一條記錄比較困難。要么填充被刪空間，要么標(biāo)記被刪記錄； 除非塊的大小恰好是記錄大小的倍數(shù)，否則有的記錄會(huì)跨塊存儲(chǔ)。對于跨塊存儲(chǔ)的記錄的訪問需要涉及兩次磁盤I/O操作。 一般對被刪除結(jié)點(diǎn)做標(biāo)記，且使用空閑記錄鏈表來管理記錄的插入和刪除，如圖7-4所示：n 在文件開始處，分配一定數(shù)量的字節(jié)作為在文件開始處，分配一定數(shù)量的字節(jié)作為文件頭文件頭(file header)，文件頭中存儲(chǔ)有關(guān)文件的各種信息。到目前為止，需要在文件文件頭中存儲(chǔ)有關(guān)文件的各種信息。到目前為止，

7、需要在文件頭中存儲(chǔ)的信息只有一個(gè)，即第一條被刪除記錄頭中存儲(chǔ)的信息只有一個(gè)，即第一條被刪除記錄(即第一條可用即第一條可用記錄記錄)的地址。的地址。 變長記錄指文件中的記錄具有不同的存儲(chǔ)字節(jié)數(shù)。 在數(shù)據(jù)庫系統(tǒng)中，以下幾種情況會(huì)導(dǎo)致使用變長記錄： 多種記錄類型(即多個(gè)關(guān)系表)在一個(gè)文件中存儲(chǔ)； 允許記錄類型中包含一個(gè)或多個(gè)變長字段； 允許記錄類型中包含重復(fù)字段，如數(shù)組等。 有多種變長記錄的存儲(chǔ)管理技術(shù)，這里僅介紹分槽頁結(jié)構(gòu)(slotted-page structure)。分槽頁結(jié)構(gòu)一般用于在塊中組織記錄，如圖7-5所示。 每個(gè)塊的開始處有一個(gè)塊頭，塊頭中包含的信息有： 塊頭中已存儲(chǔ)的條目(entr

8、y)個(gè)數(shù)#E(number of entries)； 塊中空閑空間的末尾地址EFS(end of free space)； 條目數(shù)組，每個(gè)條目中存儲(chǔ)了該條目所對應(yīng)變長記錄的大小ES(entry size)和地址EP (entry pointer)。目 錄B+樹索引樹索引7.4文件組織文件組織7.1記錄組織記錄組織7.2順序索引順序索引7.37.57.6物理數(shù)據(jù)庫設(shè)計(jì)物理數(shù)據(jù)庫設(shè)計(jì)散列散列文件組織 文件中組織記錄的常用方法有：堆文件組織、順序文件組織、多表聚集文件組織、B+樹文件組織和散列（hashing）文件組織等。本節(jié)對前3種進(jìn)行介紹。 堆文件組織 ：一條記錄可以放在文件中的任何地方，只要那

9、個(gè)地方有空間存放該記錄。也就是說，文件中的記錄是沒有順序的，是堆積起來的。通常每個(gè)關(guān)系使用一個(gè)單獨(dú)的文件。 順序文件組織：順序文件是為了高效地按某個(gè)搜索碼的順序排序處理記錄而設(shè)計(jì)的。為了快速地按搜索碼的順序獲取記錄，通常通過指針把記錄邏輯上有序地鏈接起來。每個(gè)記錄的指針指向搜索碼順序的下一條記錄。同時(shí)，為了減少順序文件處理中磁盤塊的訪問數(shù)量，在物理上按搜索碼順序或者盡可能地接近搜索碼順序存儲(chǔ)記錄。如圖7-6所示： 順序文件中插入操作的處理： 在文件中定位按搜索碼順序處于插入記錄之前的那條記錄（記為記錄A）。 如果記錄A所在塊中有空記錄(可能刪除后留下來的空間)，就在這里插入新的記錄；否則將新記

10、錄插入在一個(gè)溢出塊中。 不管哪種情況，都要調(diào)整指針，使其能按搜索碼順序把記錄鏈接起來。 插入情況如圖7-7所示：多表聚集文件組織 問題的提出：兩個(gè)關(guān)系中作連接運(yùn)算時(shí)，最壞的情況下，每個(gè)相匹配的記錄都處在不同的磁盤塊中，這將導(dǎo)致為獲取所需的每一條記錄都要讀取一個(gè)磁盤塊。 問題的解決 ：將兩個(gè)關(guān)系的元組混合在一起聚集存儲(chǔ)，從而支持高效的連接運(yùn)算。如圖7-8所示的兩個(gè)關(guān)系，為了支持高效連接運(yùn)算，可以采用圖7-9所示的多表聚集文件結(jié)構(gòu)。n 多表聚集文件組織多表聚集文件組織(Multitable Clustering File Organization)是是一種在每一個(gè)塊中存儲(chǔ)兩個(gè)或多個(gè)關(guān)系的相關(guān)記錄的

11、文件結(jié)一種在每一個(gè)塊中存儲(chǔ)兩個(gè)或多個(gè)關(guān)系的相關(guān)記錄的文件結(jié)構(gòu)。構(gòu)。n 對于圖對于圖7-9所示的所示的多表聚集文件結(jié)構(gòu)多表聚集文件結(jié)構(gòu)，可以加速，可以加速特定連接特定連接的處的處理，但是它將導(dǎo)致理，但是它將導(dǎo)致其它類型查詢的處理變慢其它類型查詢的處理變慢。在圖。在圖7-10中，中，通過指針將一個(gè)關(guān)系中的所有記錄鏈接起來以方便查找。通過指針將一個(gè)關(guān)系中的所有記錄鏈接起來以方便查找。 目 錄B+樹索引樹索引7.4文件組織文件組織7.1記錄組織記錄組織7.2順序索引順序索引7.37.57.6物理數(shù)據(jù)庫設(shè)計(jì)物理數(shù)據(jù)庫設(shè)計(jì)散列散列 兩種基本的索引類型： 順序索引(ordered index)：基于搜索碼的

12、值的順序排列，包括索引順序文件和B+樹索引文件等。 順序索引主要用于支持快速地對文件中的記錄進(jìn)行順序或隨機(jī)地訪問。順序索引的結(jié)構(gòu)是按順序存儲(chǔ)搜索碼的值，并將搜索碼的值與包含該搜索碼值的記錄關(guān)聯(lián)起來 。索引基本概念 l 散列索引散列索引(hash index)：通過搜索碼值的散列函數(shù)：通過搜索碼值的散列函數(shù)(也稱哈希函也稱哈希函數(shù)數(shù))的值將所有記錄平均、隨機(jī)地分布到若干個(gè)散列桶中。的值將所有記錄平均、隨機(jī)地分布到若干個(gè)散列桶中。n 搜索碼搜索碼(search key)：用于在文件中查找記錄的屬性或：用于在文件中查找記錄的屬性或?qū)傩约＝?jīng)常需要在一個(gè)文件上建立多個(gè)索引，此時(shí)該屬性集。經(jīng)常需要在一個(gè)

13、文件上建立多個(gè)索引，此時(shí)該文件就有多個(gè)搜索碼。文件就有多個(gè)搜索碼。 建立了索引的文件稱為索引文件。索引文件中的記錄自身可以按照某種排序順序存儲(chǔ)。一個(gè)索引文件可以有多個(gè)索引，分別對應(yīng)于不同的搜索碼。 如果索引文件中的記錄按照某個(gè)搜索碼值指定的順序物理存儲(chǔ)，那么該搜索碼對應(yīng)的索引就稱為主索引(primary index)，也叫聚集索引(clustering index)。 與此相反，搜索碼值順序與索引文件中記錄的物理順序不同的那些索引稱為輔助索引(secondary index)或非聚集索引(nonclustering index)。 索引基本概念 對索引技術(shù)的評價(jià)需要全面考慮以下因素： 訪問類型

14、：索引能有效支持的數(shù)據(jù)訪問類型。例如，根據(jù)指定的屬性值進(jìn)行查詢，根據(jù)給定的屬性值的范圍進(jìn)行查詢。 訪問時(shí)間：通過索引找到一條特定記錄或記錄集所需要的時(shí)間。 插入時(shí)間：在文件中插入一條新記錄所需要的時(shí)間，包括找到插入新記錄的正確位置和插入該記錄所需要的時(shí)間以及更新索引結(jié)構(gòu)所需要的時(shí)間。 刪除時(shí)間：在文件中刪除一條記錄所需要的時(shí)間，包括找到待刪除記錄的正確位置和刪除該記錄所需要的時(shí)間以及更新索引結(jié)構(gòu)所需要的時(shí)間。 空間開銷：索引結(jié)構(gòu)所需要的額外存儲(chǔ)空間。一般來說，索引是用空間代價(jià)來換取系統(tǒng)性能的提高，這就要進(jìn)行空間與時(shí)間的折衷。索引順序文件 建立了主索引的索引文件稱為索引順序文件(index-se

15、quential file)。也就是說，索引順序文件是按某個(gè)搜索碼值物理有序存儲(chǔ)。 對于索引順序文件，順序索引有兩類：稠密索引和稀疏索引。 稠密索引。對應(yīng)索引文件中搜索碼的每一個(gè)值在索引中都有一個(gè)索引記錄(或稱為索引項(xiàng))。每一個(gè)索引項(xiàng)包含搜索碼值和指向具有該搜索碼值的第一個(gè)數(shù)據(jù)記錄的指針，如圖7-11所示，其中studentName是搜索碼。 稀疏索引。稀疏索引只為索引文件中搜索碼的某些值建立索引記錄(或稱為索引項(xiàng))。每一個(gè)索引項(xiàng)包含搜索碼值和指向具有該搜索碼值的第一個(gè)數(shù)據(jù)記錄的指針，如圖7-12所示。多級索引 即使采用稀疏索引，對于一個(gè)大型數(shù)據(jù)庫而言，索引本身也可能變得很大。 如果索引過大，

16、主存中不可能讀入所有的索引塊，也就是大部分索引塊只能存儲(chǔ)在磁盤上，這樣在查詢處理過程中，搜索索引就必須讀大量的磁盤塊。 通過多級索引技術(shù)能夠較好地解決上述問題。所謂多級索引就是在索引之上再建立索引。 像對待其他順序文件那樣對待索引，在聚集索引上再構(gòu)造一個(gè)稀疏索引，如圖7-13所示。 事實(shí)上索引就是一個(gè)順序文件，索引記錄是按搜索碼值有序存放的。多級索引 索引的更新 刪除記錄 ：為了刪除數(shù)據(jù)文件中的一條記錄，系統(tǒng)首先要查找定位該記錄，記待刪除記錄的搜索碼值為KD。 接下來的操作要分稠密索引和稀疏索引來討論。 對于稠密索引，如圖7-11所示， 索引更新的規(guī)則如下： 如果被刪除的記錄是唯一具有KD值的

17、記錄，則從索引中刪除相應(yīng)的索引項(xiàng)(索引記錄)，如刪除“劉方晨”的記錄。 否則（即搜索碼值為KD的記錄有多條），采取如下操作： 如果索引項(xiàng)中存儲(chǔ)的指針指向待刪除的記錄，則更新該指針，使其指向文件中的下一條數(shù)據(jù)記錄， 如刪除學(xué)號為0701001的“李小勇”的記錄； 否則索引不必更新，如刪除學(xué)號為0803025的“李小勇”的記錄。 對于稀疏索引，如圖7-12所示，索引更新的規(guī)則如下：1、如果索引中不包含搜索碼值為、如果索引中不包含搜索碼值為KD的索引項(xiàng)，則索引不必更的索引項(xiàng)，則索引不必更新，新，如刪除如刪除“李小勇李小勇”、“王紅敏王紅敏”的記錄的記錄。 對于稀疏索引，如圖7-12所示，索引更新的規(guī)

18、則如下：2、否則（即索引中包含搜索碼值為、否則（即索引中包含搜索碼值為KD的索引項(xiàng)）的索引項(xiàng)）2.1 如果被刪除的記錄在數(shù)據(jù)文件中是唯一具有如果被刪除的記錄在數(shù)據(jù)文件中是唯一具有KD值的記值的記錄，采取如下操作：錄，采取如下操作： 用數(shù)據(jù)文件中下一個(gè)搜索碼值的記錄更新該索引項(xiàng)用數(shù)據(jù)文件中下一個(gè)搜索碼值的記錄更新該索引項(xiàng)(包括搜包括搜索碼值和指針都要更新索碼值和指針都要更新)，如刪除如刪除“李宏冰李宏冰”的記錄的記錄； 如果數(shù)據(jù)文件中下一個(gè)搜索碼值的記錄在索引中已經(jīng)有一個(gè)如果數(shù)據(jù)文件中下一個(gè)搜索碼值的記錄在索引中已經(jīng)有一個(gè)索引項(xiàng)，則刪除該索引項(xiàng)，索引項(xiàng)，則刪除該索引項(xiàng)，如刪除如刪除“劉方晨劉方晨

19、”的記錄的記錄。 對于稀疏索引，如圖7-12所示，索引更新的規(guī)則如下：2.2 否則否則(即索引中包含搜索碼值為即索引中包含搜索碼值為KD的索引項(xiàng)，且數(shù)據(jù)文的索引項(xiàng)，且數(shù)據(jù)文件中包含多條搜索碼值為件中包含多條搜索碼值為KD的記錄的記錄)，采取如下操作：，采取如下操作：如果索引項(xiàng)中存儲(chǔ)的指針指向待刪除的記錄，則更如果索引項(xiàng)中存儲(chǔ)的指針指向待刪除的記錄，則更新該指針，使其指向文件中的下一條數(shù)據(jù)記錄，新該指針，使其指向文件中的下一條數(shù)據(jù)記錄，如如刪除學(xué)號為刪除學(xué)號為0701008的的“王王 紅紅”的記錄的記錄；否則索引不必更新，否則索引不必更新，如刪除學(xué)號為如刪除學(xué)號為0703045的的“王王 紅紅”

20、的記錄的記錄。 插入記錄 對于稠密索引，如圖7-11所示。 如果待插入記錄的搜索碼值不在索引中，則把該搜索碼值插入到索引中，如插入一條姓名為“彭國強(qiáng)”的記錄； 否則索引不必更新，如插入一條學(xué)號為0701004、姓名為“王 紅”的記錄。 對于稀疏索引，假設(shè)索引為每個(gè)塊保存一個(gè)索引項(xiàng)。 如果系統(tǒng)產(chǎn)生一個(gè)新塊 (不是指溢出塊)，將新塊中第一條記錄的搜索碼值(即新塊中最小的搜索碼值)插入到索引中建立一個(gè)索引項(xiàng)，新建的索引項(xiàng)指向新塊。 如果沒有新塊產(chǎn)生，且插入記錄在該塊中具有最小的且唯一的搜索碼值，則更新索引中指向該塊的索引項(xiàng)的搜索碼值；否則索引不必更新。 多級索引的插入和刪除算法是對上述算法的一個(gè)簡單

21、擴(kuò)充。 在插入或刪除時(shí)，對底層索引的更新如上所述。 而對于第二層而言，底層索引就是一個(gè)包含索引記錄的按搜索碼值有序的順序文件。因此，如果底層索引發(fā)生改變(插入或刪除索引記錄)，第二層索引就可以像上面描述的那樣進(jìn)行更新。 如果還有更高層的索引，類似處理。輔助索引 在數(shù)據(jù)文件中，記錄按主索引而不是輔助索引的搜索碼值順序物理存儲(chǔ)，因此具有同一個(gè)搜索碼值的記錄可能分布在文件的各個(gè)地方。 所以，輔助索引必須是稠密索引，即對于每個(gè)搜索碼值都必須有一個(gè)索引項(xiàng)，而且該索引項(xiàng)要存放指向數(shù)據(jù)文件中具有該搜索碼值的所有記錄的指針。 可以通過指針桶的方式實(shí)現(xiàn)，即將數(shù)據(jù)文件中具有該搜索碼值的所有記錄的指針存放在一個(gè)指針

22、桶中，索引項(xiàng)中的指針域再存放指向指針桶的指針(可以理解為指向指針數(shù)組的指針)。如圖7-14所示。 索引順序文件組織的最大不足在于： 隨著文件的增大，索引查找的性能和數(shù)據(jù)順序掃描的性能都會(huì)下降。 雖然這種性能下降可以通過對文件進(jìn)行重組來彌補(bǔ)，但頻繁地進(jìn)行重組也是我們所不希望的。目 錄B+樹索引樹索引7.4文件組織文件組織7.1記錄組織記錄組織7.2順序索引順序索引7.37.57.6物理數(shù)據(jù)庫設(shè)計(jì)物理數(shù)據(jù)庫設(shè)計(jì)散列散列B+樹索引的結(jié)構(gòu) B+樹索引的結(jié)構(gòu)滿足： B+樹索引是一個(gè)多級索引，但其結(jié)構(gòu)不同于多級順序索引。 B+樹索引采用平衡樹結(jié)構(gòu)，即每個(gè)葉結(jié)點(diǎn)到根的路徑長度相同。江宏江宏李勇李勇彭好彭好王

23、紅王紅劉強(qiáng)劉強(qiáng)黃紅黃紅黃勇黃勇江宏江宏李冰李冰李立李立李勇李勇劉歡劉歡指 向 文 件 記指 向 文 件 記錄錄劉強(qiáng)劉強(qiáng) 孟晨孟晨 聶東聶東彭好彭好邱南邱南王紅王紅 張可張可趙雪趙雪指向文件記錄指向文件記錄B+樹索引的結(jié)構(gòu) B+樹索引的結(jié)構(gòu)滿足： B+樹索引是一個(gè)多級索引，但其結(jié)構(gòu)不同于多級順序索引。 B+樹索引采用平衡樹結(jié)構(gòu)，即每個(gè)葉結(jié)點(diǎn)到根的路徑長度相同。 B+樹索引中的所有結(jié)點(diǎn)的結(jié)構(gòu)都相同，它最多包含n-1個(gè)搜索碼值K1, K2, , Kn-1，以及n個(gè)指針P1, P2, , Pn，每個(gè)結(jié)點(diǎn)中的搜索碼值升序存放，即如果ij，那么KiKj。典型的B+樹索引中的結(jié)點(diǎn)結(jié)構(gòu)如圖7-15所示。 每個(gè)

24、非葉結(jié)點(diǎn)有 n/2 到n個(gè)孩子結(jié)點(diǎn)，n對特定的樹是固定的。B+樹索引的結(jié)構(gòu)樹索引的結(jié)構(gòu) 葉結(jié)點(diǎn)的結(jié)構(gòu)：對i=1, 2, , n-1，指針Pi指向具有搜索碼值Ki的一條文件記錄或指向一個(gè)指針桶，且指針桶中的每個(gè)指針指向具有搜索碼值Ki的一條文件記錄。桶結(jié)構(gòu)只在搜索碼不是候選碼且文件記錄不按搜索碼順序存放時(shí)才使用。指針Pn有特殊的作用，稍后再討論。江宏江宏李勇李勇彭好彭好王紅王紅劉強(qiáng)劉強(qiáng)黃紅黃紅黃勇黃勇江宏江宏李冰李冰李立李立李勇李勇劉歡劉歡指 向 文 件 記指 向 文 件 記錄錄劉強(qiáng)劉強(qiáng) 孟晨孟晨 聶東聶東彭好彭好邱南邱南王紅王紅 張可張可趙雪趙雪指向文件記錄指向文件記錄 每個(gè)葉結(jié)點(diǎn)最多可存放n

25、-1個(gè)搜索碼值，最少也要存放 (n-1)/2 個(gè)搜索碼值。各個(gè)葉結(jié)點(diǎn)中的搜索碼值不重復(fù)且不相交，并要使B+樹索引成為稠密索引，即數(shù)據(jù)文件中的所有互不相同的搜索碼值必須在某個(gè)葉結(jié)點(diǎn)出現(xiàn)且只出現(xiàn)一次。 每個(gè)葉結(jié)點(diǎn)中的搜索碼值升序排列，所以可以利用各個(gè)葉結(jié)點(diǎn)的指針Pn將所有葉結(jié)點(diǎn)按搜索碼值的排序順序鏈接在一起。這種葉結(jié)點(diǎn)的鏈接排序能夠高效地實(shí)現(xiàn)對數(shù)據(jù)文件的順序處理，而B+樹索引中的其他結(jié)構(gòu)能夠高效地實(shí)現(xiàn)對數(shù)據(jù)文件的隨機(jī)處理。如圖7-16所示。 B+樹索引的結(jié)構(gòu) 非葉結(jié)點(diǎn)的結(jié)構(gòu)： B+樹索引中的非葉結(jié)點(diǎn)形成葉結(jié)點(diǎn)上的一個(gè)多級(稀疏)索引。 非葉結(jié)點(diǎn)的結(jié)構(gòu)與葉結(jié)點(diǎn)相同，只不過非葉結(jié)點(diǎn)中的所有指針都是指向

26、B+樹中下一層結(jié)點(diǎn)的指針。 每個(gè)非葉結(jié)點(diǎn)最多可存放n個(gè)指針(對應(yīng)于存放n-1個(gè)搜索碼)，最少也要存放 n/2 個(gè)指針(對應(yīng)于存放 (n-1)/2 個(gè)搜索碼)。 一個(gè)結(jié)點(diǎn)中存放的指針數(shù)稱為該結(jié)點(diǎn)的扇出。B+樹索引的結(jié)構(gòu) 假設(shè)一個(gè)非葉結(jié)點(diǎn)中存放了m個(gè)指針， n/2 mn。 若mnr/fr，否則肯定會(huì)發(fā)生桶溢出。其中nr表示將要存儲(chǔ)的記錄總數(shù)，fr表示一個(gè)桶中能存放的記錄數(shù)目。當(dāng)然，這是以在選擇散列函數(shù)時(shí)記錄總數(shù)已知為前提的。 偏斜。某些桶分配到的記錄比其他桶多，所以，即使其他桶仍有空間，有些桶仍可能溢出，稱為桶偏斜。 偏斜發(fā)生的原因有兩個(gè)： 多個(gè)記錄可能具有相同的搜索碼值； 所選擇的散列函數(shù)可能會(huì)

27、造成搜索碼值的分布不均勻。桶溢出的處理 桶溢出的處理方法：主要有閉散列和開散列二種方法。 閉散列： 如果一條記錄必須插入桶b中，而桶b已滿，系統(tǒng)會(huì)為桶b提供一個(gè)溢出桶，并將此記錄插入到這個(gè)溢出桶中。 如果溢出桶也滿了，系統(tǒng)會(huì)再提供一個(gè)溢出桶，如此繼續(xù)下去。 一個(gè)給定桶的所有溢出桶用一個(gè)鏈接列表鏈接在一起，如圖所示. 使用這種鏈接列表的溢出處理稱為溢出鏈。溢出鏈的散列結(jié)構(gòu)稱為閉散列。 桶溢出的處理 開散列： 它的桶的數(shù)量是固定的，沒有溢出鏈； 當(dāng)一個(gè)桶滿了以后，系統(tǒng)將記錄插入到初始桶集合B的其他桶中去。 選擇其他桶的策略有： 使用下一個(gè)(按輪轉(zhuǎn)順序)未滿的桶，該策略稱為線性探查法； 用進(jìn)一步計(jì)算

28、散列函數(shù)的方法（再散列法）。 散列索引 散列索引(hash index)將搜索碼值及其相應(yīng)的文件記錄指針組織成散列文件結(jié)構(gòu)。 散列索引的構(gòu)建方法： 將散列函數(shù)作用于一條文件記錄的搜索碼值，以確定索引項(xiàng)的散列桶； 將由該搜索碼值以及相應(yīng)文件記錄指針組成的索引項(xiàng)存入散列桶(或溢出桶)中。 圖7-22所示的是Student文件的一個(gè)輔助散列索引，其搜索碼是studentNo，散列函數(shù)是計(jì)算studentNo值的各位數(shù)字之和后按5取模。由于studentNo是主碼，所以每個(gè)搜索碼值只對應(yīng)一個(gè)記錄指針。一般情況下，每個(gè)搜索碼值可能對應(yīng)多個(gè)指針。散列索引散列索引 散列索引只能是一種輔助索引結(jié)構(gòu)。 散列索引

29、從來不需要作為主索引(聚集索引)來使用，因?yàn)橐粋€(gè)文件如果自身是按散列組織的，就不必再在其上另外建立一個(gè)獨(dú)立的散列索引了。 不過，既然散列文件組織能像索引那樣提供對記錄的直接訪問，不妨就認(rèn)為以散列形式組織的文件上也有一個(gè)聚集散列索引了。 動(dòng)態(tài)散列 前面介紹的散列技術(shù)稱為靜態(tài)散列，它要求在選擇散列函數(shù)時(shí)就知道記錄的總數(shù)，即桶的數(shù)量必須事先確定。 然而，大多數(shù)數(shù)據(jù)庫都會(huì)隨時(shí)間而變大。對于規(guī)模變化的數(shù)據(jù)庫使用靜態(tài)散列，有3種選擇： 根據(jù)當(dāng)前文件大小選擇散列函數(shù)。這種選擇會(huì)使性能隨數(shù)據(jù)庫增大而下降。 根據(jù)預(yù)計(jì)的將來某個(gè)時(shí)刻文件的大小選擇散列函數(shù)。盡管這樣可以一定程度上避免性能下降，但初始時(shí)會(huì)造成相當(dāng)大的

30、空間浪費(fèi)。 隨著文件增大，周期性地對散列結(jié)構(gòu)進(jìn)行重組。重組是一個(gè)復(fù)雜、耗時(shí)的操作，而且重組期間必須禁止對文件的訪問。 動(dòng)態(tài)散列技術(shù)允許散列函數(shù)動(dòng)態(tài)改變，以適應(yīng)數(shù)據(jù)庫增大或縮小的需要。 限于篇幅，這里不對動(dòng)態(tài)散列技術(shù)進(jìn)行討論，有興趣的讀者請參考相關(guān)資料。散列與順序索引的比較 散列其實(shí)就是一種不通過值的比較，而通過值的含義來確定存儲(chǔ)位置的方法，它是為有效地實(shí)現(xiàn)等值查詢而設(shè)計(jì)的。 不幸的是，基于散列技術(shù)不支持范圍檢索。 而基于B+樹的索引技術(shù)能有效地支持范圍檢索，并且它的等值檢索效果也很好。 但是，散列技術(shù)在等值連接等操作中是很有用的，尤其是在索引嵌套循環(huán)連接方法中，基于散列的索引和基于B+樹的索引

31、在代價(jià)上的差別會(huì)很大。散列與順序索引的選擇 在實(shí)際的數(shù)據(jù)庫設(shè)計(jì)中，到底是用索引還是散列要充分考慮以下幾個(gè)問題： 索引或散列的周期性重組的代價(jià)如何？ 在文件中插入和刪除記錄的頻率如何？ 是否愿意以增加最壞情況下的訪問時(shí)間為代價(jià)優(yōu)化平均訪問時(shí)間？ 用戶可能提出哪些類型的查詢？目 錄B+樹索引樹索引7.4文件組織文件組織7.1記錄組織記錄組織7.2順序索引順序索引7.37.57.6物理數(shù)據(jù)庫設(shè)計(jì)物理數(shù)據(jù)庫設(shè)計(jì)散列散列物理數(shù)據(jù)庫設(shè)計(jì) 數(shù)據(jù)庫在物理設(shè)備上的存儲(chǔ)結(jié)構(gòu)與存取方法稱為數(shù)據(jù)庫的物理結(jié)構(gòu)，它依賴于給定的計(jì)算機(jī)系統(tǒng)。 為一個(gè)給定的邏輯數(shù)據(jù)模型選取一個(gè)最適合應(yīng)用環(huán)境的物理結(jié)構(gòu)的過程，就是數(shù)據(jù)庫的物理設(shè)

32、計(jì)。 目標(biāo)： 提高數(shù)據(jù)庫性能，以滿足應(yīng)用的性能需求； 有效利用存儲(chǔ)空間； 在性能和代價(jià)之間做出最優(yōu)平衡。 內(nèi)容： 確定數(shù)據(jù)庫的存儲(chǔ)結(jié)構(gòu)； 為數(shù)據(jù)選擇合適的存取路徑，即索引的設(shè)計(jì)； 對物理結(jié)構(gòu)進(jìn)行評價(jià)，重點(diǎn)是評價(jià)時(shí)間和空間效率。 數(shù)據(jù)庫的物理組織 數(shù)據(jù)庫的基礎(chǔ)是基于操作系統(tǒng)的文件系統(tǒng)，對數(shù)據(jù)庫的操作都要轉(zhuǎn)化為對文件的操作，如何設(shè)計(jì)文件結(jié)構(gòu)以及有效利用操作系統(tǒng)提供的文件存取方法是DBMS要考慮的事情。 因此，選定DBMS后，數(shù)據(jù)庫物理組織的大概框架也就基本確定了，如一個(gè)數(shù)據(jù)庫需要多少個(gè)文件，每個(gè)文件的作用是什么，等等。 關(guān)系數(shù)據(jù)庫中要存儲(chǔ)的數(shù)據(jù)主要包括：關(guān)系表、數(shù)據(jù)字典、索引、日志和備份等。DBMS對不同數(shù)據(jù)的物理組織方式通常是不一樣的。確定數(shù)據(jù)庫存儲(chǔ)結(jié)構(gòu) 確定數(shù)據(jù)存放位置 ：為了提高系統(tǒng)性能，數(shù)據(jù)應(yīng)該根據(jù)應(yīng)用情況將易變部分和穩(wěn)定部分、經(jīng)常存取部分和存取頻率較低部分分開來存放。 確定數(shù)據(jù)庫存儲(chǔ)結(jié)構(gòu) ：確定數(shù)據(jù)庫存儲(chǔ)結(jié)構(gòu)時(shí)要綜合考慮存取時(shí)間、存儲(chǔ)空間利用率和維護(hù)代價(jià)三個(gè)方面的因素。這三個(gè)方面常常是相互矛