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

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

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

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

4、ct語句；(2) 對命令進行語法檢查，正確后檢查語義和用戶權(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) 查看存儲模式，決定從哪個文件、用什么方式讀取物理記錄；查看存儲模式，決定從哪個文件、用什么方式讀取物理記錄；(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ù)進行相應(yīng)處理。應(yīng)用程序?qū)ぷ鲄^(qū)中讀出的數(shù)據(jù)進行相應(yīng)處理。定長記錄與變長記錄 文件在邏輯上可看作記錄的序列，這些記錄被映射到磁盤的物理塊上。 用文件表示邏輯數(shù)據(jù)模型的

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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