1、機(jī)械自動(dòng)化學(xué)院機(jī)械自動(dòng)化學(xué)院20152015主講：主講： 顧顧 曦曦 電話：電話：1569718107915697181079EmailEmail：主要內(nèi)容文件、記錄的組織索引B樹索引散列物理數(shù)據(jù)庫設(shè)計(jì)*2*31.1 存儲(chǔ)介質(zhì)的分類計(jì)算機(jī)的三級(jí)存儲(chǔ)體系: 層次越高，每單位存儲(chǔ)容量價(jià)格越貴，但速度越快存儲(chǔ)易失性問題 ：易失性存儲(chǔ)在設(shè)備斷電后將丟失所有內(nèi)容。一級(jí)存儲(chǔ)為易失性存儲(chǔ)，而二、三級(jí)存儲(chǔ)系統(tǒng)都是非易失性存儲(chǔ)。 1.2 磁盤*5扇區(qū)（section）： 磁盤上劃分的區(qū)域 磁盤最小的物理存儲(chǔ)單元 磁盤驅(qū)動(dòng)器在向磁盤讀取和寫入數(shù)據(jù)時(shí)，以扇區(qū)為單位。 每個(gè)扇區(qū)可存放512個(gè)字節(jié)。磁盤塊（block）

2、 文件系統(tǒng)層的概念，最小數(shù)據(jù)存儲(chǔ)單元。 大小是扇區(qū)的2n倍磁盤的主要性能指標(biāo)訪問時(shí)間訪問時(shí)間(access time):從發(fā)出讀寫請求到數(shù)據(jù)開始傳輸之間的時(shí)間。尋道時(shí)間尋道時(shí)間(seek time):為了訪問(即讀或?qū)?磁盤上指定扇區(qū)的數(shù)據(jù)，磁盤臂磁盤臂移動(dòng)以定位到正確的磁道所需的時(shí)間；旋轉(zhuǎn)等待時(shí)間旋轉(zhuǎn)等待時(shí)間(rotational latency time)：等待磁盤磁盤旋轉(zhuǎn)直到指定的扇區(qū)出現(xiàn)在它下方所需的時(shí)間。訪問時(shí)間訪問時(shí)間=尋道時(shí)間尋道時(shí)間+旋轉(zhuǎn)等待時(shí)間旋轉(zhuǎn)等待時(shí)間磁盤的主要性能指標(biāo)（續(xù)）數(shù)據(jù)傳輸率數(shù)據(jù)傳輸率(data-tranfer rate)從磁盤磁盤獲得數(shù)據(jù)或者向磁盤磁盤存儲(chǔ)數(shù)據(jù)

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

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

5、結(jié)果向操作系統(tǒng)的結(jié)果向操作系統(tǒng)(OS)發(fā)出讀取記錄的命令；發(fā)出讀取記錄的命令；(8) OS執(zhí)行該命令，并讀取記錄數(shù)據(jù)；執(zhí)行該命令，并讀取記錄數(shù)據(jù)；(9) 在在OS控制下，將讀出的記錄送入系統(tǒng)緩沖區(qū)；控制下，將讀出的記錄送入系統(tǒng)緩沖區(qū)；(10) RDBMS根據(jù)查詢命令和根據(jù)查詢命令和DD的內(nèi)容導(dǎo)出用戶所要讀取的記錄格式；的內(nèi)容導(dǎo)出用戶所要讀取的記錄格式；(11) RDBMS將數(shù)據(jù)從系統(tǒng)緩沖區(qū)中送入用戶工作區(qū)；將數(shù)據(jù)從系統(tǒng)緩沖區(qū)中送入用戶工作區(qū)；(12) RDBMS將執(zhí)行狀態(tài)信息將執(zhí)行狀態(tài)信息(成功或不成功等成功或不成功等)返回給應(yīng)用程序；返回給應(yīng)用程序；(13) 應(yīng)用程序?qū)ぷ鲄^(qū)中讀出的數(shù)據(jù)進(jìn)行

6、相應(yīng)處理。應(yīng)用程序?qū)ぷ鲄^(qū)中讀出的數(shù)據(jù)進(jìn)行相應(yīng)處理。存儲(chǔ)訪問的具體步驟：存儲(chǔ)訪問的具體步驟：1.4 定長記錄與變長記錄 文件在邏輯上可看作記錄的序列記錄的序列記錄被映射到磁盤的物理塊上。表示邏輯數(shù)據(jù)模型方式：1.4.1 定長記錄定長記錄定長記錄指文件中所有記錄均具有同樣的字節(jié)長度同樣的字節(jié)長度。*11存儲(chǔ)Score記錄的文件存在的兩個(gè)問題：刪除一條記錄比較困難。要么填充被刪空間，要么標(biāo)記被刪記錄；除非塊的大小恰好是記錄大小的倍數(shù)，否則有的記錄會(huì)跨塊存跨塊存儲(chǔ)，儲(chǔ)，會(huì)涉及兩次磁盤I/O操作。 在文件開始處，分配一定數(shù)在文件開始處，分配一定數(shù)量的字節(jié)作為文件頭量的字節(jié)作為文件頭(file head

7、er)文件頭中存儲(chǔ)有關(guān)文件的各文件頭中存儲(chǔ)有關(guān)文件的各種信息。種信息。其中包括第一條被刪除記錄其中包括第一條被刪除記錄(即第一條可用記錄即第一條可用記錄)的地址。的地址。 處理辦法：對被刪除結(jié)點(diǎn)做標(biāo)記，且使用空閑記錄鏈表來管理記錄的插入和刪除；1.4.2 變長記錄變長記錄指文件中的記錄具有不同的存儲(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)一般用于在塊

8、中組織記錄。*14每個(gè)塊的開始處有一個(gè)塊頭，塊頭中包含的信息有： 塊頭中已存儲(chǔ)的條目(entry)個(gè)數(shù)個(gè)數(shù)#E(number of entries)； 塊中空閑空間的末尾地址末尾地址EFS(end of free space)； 條目數(shù)組條目數(shù)組，其中每個(gè)條目中存儲(chǔ)了該條目所對應(yīng)變長記錄的大小ES(entry size)和地址EP (entry pointer)。*15文件組織的常用方法2.1 堆文件組織 一條記錄可以放在文件中的任何地方，只要那個(gè)地方有空間存放該記錄。文件中的記錄是沒有順序的，是堆積起來的。通常每個(gè)關(guān)系使用一個(gè)單獨(dú)的文件。兩種堆文件結(jié)構(gòu)頁鏈接式結(jié)構(gòu)頁目錄結(jié)構(gòu)*17首頁數(shù)據(jù)頁2

9、.2 順序文件組織順序文件是為了高效地按某個(gè)搜索碼的順序排序處理記錄而設(shè)計(jì)的。為了快速地按搜索碼搜索碼的順序獲取記錄，通常通過指針通過指針把記錄邏輯上有序地鏈接起來邏輯上有序地鏈接起來。每個(gè)記錄的指針指向搜索碼順序的下一條記錄。在物理上按搜索碼順序按搜索碼順序或者盡可能地接近搜索碼順序存儲(chǔ)記錄，以減少順序文件處理中磁盤塊的訪問數(shù)量。問題：插入、刪除*18順序文件中插入操作的處理在文件中定位，按搜索碼順序處于插入記錄之前的那條記錄（記為記錄A）。如果記錄A所在塊中有空記錄(可能刪除后留下來的空間)，就在這里插入新的記錄；否則將新記錄插入在一個(gè)溢出塊中。 搜索碼與物理順序不一致過多時(shí)，需重組，代價(jià)

10、較高。記錄A2.3 多表聚集文件組織問題的提出：兩個(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)記錄的文件結(jié)一種在每一個(gè)塊中存儲(chǔ)兩個(gè)或多個(gè)關(guān)系的相關(guān)記錄的文件結(jié)構(gòu)。構(gòu)。n 對于圖對于圖7-9所示的

11、所示的多表聚集文件結(jié)構(gòu)多表聚集文件結(jié)構(gòu)，可以加速特定連接的處，可以加速特定連接的處理，但是它將導(dǎo)致其它類型查詢的處理變慢。在圖理，但是它將導(dǎo)致其它類型查詢的處理變慢。在圖7-10中，中，通過指針將一個(gè)關(guān)系中的所有記錄鏈接起來以方便查找。通過指針將一個(gè)關(guān)系中的所有記錄鏈接起來以方便查找。 *213.0 索引的作用當(dāng)表中有大量記錄時(shí)，若要對表進(jìn)行查詢有兩種方法：全表搜索：全表搜索：將所有記錄一一取出，和查詢條件進(jìn)行一一對比，然后返回滿足條件的記錄，這樣做會(huì)消耗大量數(shù)據(jù)庫系統(tǒng)時(shí)間，并造成大量磁盤I/O操作；1.在表中建立索引在表中建立索引，然后在索引中找到符合查詢條件的索引值，最后通過保存在索引中的

12、ROWID（相當(dāng)于頁碼）快速找到表中對應(yīng)的記錄。索引的作用索引有助于更快地獲取特定特定數(shù)據(jù)；保證數(shù)據(jù)記錄的唯一性；實(shí)現(xiàn)表與表之間的參照完整性；在使用ORDER by、group by子句進(jìn)行數(shù)據(jù)檢索時(shí)，利用索引可以減少排序和分組的時(shí)間。*233.1 基本概念 索引，使用索引可快速訪問數(shù)據(jù)庫表中的特定信息特定信息。索引是對數(shù)據(jù)庫表中一列或多列的值進(jìn)行排序進(jìn)行排序的一種結(jié)構(gòu)。索引是一個(gè)單獨(dú)的、物理的數(shù)據(jù)庫結(jié)構(gòu)，它是某個(gè)表中一列或若干列值的集合和相應(yīng)的指向表中物理標(biāo)識(shí)這些值的數(shù)據(jù)頁的邏輯指針邏輯指針清單。在關(guān)系數(shù)據(jù)庫中，索引是一種與表有關(guān)的數(shù)據(jù)庫結(jié)構(gòu)，它可以使對應(yīng)于表的SQL語句執(zhí)行得更快語句執(zhí)行得

13、更快。基本概念搜索碼搜索碼(search key)：用于在文件中查找記錄的屬性屬性或?qū)傩约瘜傩约＝?jīng)常需要在一個(gè)文件上建立多個(gè)索引，此時(shí)該文件就有多個(gè)搜索碼。兩種基本的索引類型：順序索引順序索引(ordered index)：基于搜索碼的值的順序排列，包括索引順序文件和B+樹索引文件等。散列索引散列索引(hash index)：通過搜索碼值的散列函數(shù)(也稱哈希函數(shù))的值將所有記錄平均、隨機(jī)地分布到若干個(gè)散列桶中。基本概念索引文件索引文件：建立了索引的文件。索引文件中的記錄自身可以按照某種排序順序存儲(chǔ)。一個(gè)索引文件可以有多個(gè)索引，分別對應(yīng)于不同的搜索碼。索引順序文件索引順序文件：根據(jù)主索引建立的

14、索引文件。主索引主索引(聚集索引聚集索引)：索引文件中的記錄按照該搜索碼值指定的順序物理存儲(chǔ)。輔助索引（非聚集索引）輔助索引（非聚集索引）：搜索碼值順序與索引文件中記錄的物理順序不同的那些索引。 3.2 索引技術(shù)的評價(jià)因素訪問類型：索引能有效支持的數(shù)據(jù)訪問類型。訪問時(shí)間：通過索引找到一條特定記錄或記錄集所需要的時(shí)間。插入時(shí)間：在文件中插入一條新記錄所需要的時(shí)間，包括找到插入新記錄的正確位置和插入該記錄所需要的時(shí)間以及更新索引結(jié)構(gòu)所需要的時(shí)間。刪除時(shí)間：在文件中刪除一條記錄所需要的時(shí)間，包括找到待刪除記錄的正確位置和刪除該記錄所需要的時(shí)間以及更新索引結(jié)構(gòu)所需要的時(shí)間。空間開銷：索引結(jié)構(gòu)所需要的額

15、外存儲(chǔ)空間。一般來說，索引是用空間代價(jià)來換取系統(tǒng)性能的提高，這就要進(jìn)行空間與時(shí)間的折衷。3.3 聚集索引 （主索引）聚集索引中鍵值的邏輯順序決定了表中相應(yīng)行的物理順序。聚集索引文件稱為索引順序文件。順序索引有兩類：稠密索引稠密索引。對應(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所示。多級(jí)

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

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

18、。對于稀疏索引，如圖7-12所示，索引更新的規(guī)則如下：2、否則（即索引中包含搜索碼值為、否則（即索引中包含搜索碼值為KD的索引項(xiàng)）的索引項(xiàng)）2.1 如果被刪除的記錄在數(shù)據(jù)文件中是唯一具有如果被刪除的記錄在數(shù)據(jù)文件中是唯一具有KD值的記錄值的記錄，采取如下操作：，采取如下操作：用數(shù)據(jù)文件中下一個(gè)搜索碼值的記錄更新該索引項(xiàng)用數(shù)據(jù)文件中下一個(gè)搜索碼值的記錄更新該索引項(xiàng)(包括搜索碼值和指針包括搜索碼值和指針都要更新都要更新)，如刪除如刪除“李宏冰李宏冰”的記錄時(shí)用李小勇更新之的記錄時(shí)用李小勇更新之；如果數(shù)據(jù)文件中下一個(gè)搜索碼值的記錄在索引中已經(jīng)有一個(gè)索引項(xiàng)，則刪如果數(shù)據(jù)文件中下一個(gè)搜索碼值的記錄在索引

19、中已經(jīng)有一個(gè)索引項(xiàng)，則刪除該索引項(xiàng)，除該索引項(xiàng)，如刪除如刪除“劉方晨劉方晨”的記錄的記錄。對于稀疏索引，如圖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é)號(hào)為如刪除學(xué)號(hào)為0701008的的“王王 紅紅”的記錄的記錄；否則索引不必更新，否則

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

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

22、搜索碼值具有該搜索碼值的所有記錄所有記錄的指針。指針桶即將數(shù)據(jù)文件中具有該搜索碼值的所有記錄的指針存放在一個(gè)指針桶中，索引項(xiàng)中的指針域再存放指向指針桶的指針(可以理解為指向指針數(shù)組的指針)。*38輔助索引在數(shù)據(jù)庫更新的時(shí)候會(huì)增加很多開銷直接使用輔助索引存在的問題原因：有些文件組織，即使記錄本身沒有更新，記錄的位置也可能改變。比如說一個(gè)磁盤損壞了，我們將其存儲(chǔ)的記錄移動(dòng)到新的磁盤。這個(gè)時(shí)候更新輔助索引很困難，因?yàn)槊總€(gè)磁盤存儲(chǔ)了很多記錄，而每個(gè)記錄可能被分配到每個(gè)輔助索引的不同位置，這樣一來，更新的代價(jià)就太大了，可能會(huì)涉及幾十次的I/O訪問。如何解決？在輔助索引中，不再存儲(chǔ)指向所有記錄的指針指向所

23、有記錄的指針，而是存儲(chǔ)主索引搜索碼主索引搜索碼的屬性值。*39聚集索引和非聚集索引的使用動(dòng)作描述使用聚集索引使用非聚集索引列經(jīng)常被分組排序應(yīng)應(yīng)返回某范圍內(nèi)的數(shù)據(jù)應(yīng)不應(yīng)極少不同值不應(yīng)不應(yīng)小數(shù)目的不同值應(yīng)不應(yīng)大數(shù)目的不同值不應(yīng)應(yīng)頻繁更新的列不應(yīng)應(yīng)外鍵列應(yīng)應(yīng)主鍵列應(yīng)應(yīng)頻繁修改索引列不應(yīng)應(yīng)*403.7 索引的缺點(diǎn)索引需要占物理空間；隨著文件的增大，索引查找的性能和數(shù)據(jù)順序掃描的性能都會(huì)下降，可以通過對文件進(jìn)行重組來改善。頻繁地進(jìn)行重組非常消耗資源。*424.1 B+樹概述1）二叉二叉排序樹排序樹（Binary Sort Tree）：。所有非葉子結(jié)點(diǎn)至多擁有兩個(gè)子（Left和Right）所有結(jié)點(diǎn)存儲(chǔ)一個(gè)

24、關(guān)鍵字非葉子結(jié)點(diǎn)的左指針指向小于其關(guān)鍵字的子樹，右指針指向大于其關(guān)鍵字的子樹；每個(gè)結(jié)點(diǎn)只存儲(chǔ)一個(gè)關(guān)鍵字，等于則命中，小于走左結(jié)點(diǎn)，大于走右結(jié)點(diǎn)；經(jīng)過多次插入與刪除后，有可能導(dǎo)致不同的結(jié)構(gòu)，甚至是線性的。平衡樹(balanced search tree)對一棵查找樹（search tree）進(jìn)行查詢/新增/刪除 等動(dòng)作, 所花的時(shí)間與樹的高度h 成比例, 并不與樹的容量 n 成比例。一般的查詢復(fù)雜度是跟目標(biāo)結(jié)點(diǎn)到樹根的距離（即深度）有關(guān)如果可以讓樹維持矮矮胖胖的好身材(階數(shù)2) , 完成上述工作就很省時(shí)間。能夠一直維持好身材, 不因新增、刪除而長歪的搜尋樹, 叫做平衡樹平衡樹。*442）B-樹1

25、970年，R.Bayer和E.mccreight提出了一種適用于查找的樹，它是一種平衡的多叉樹，稱為B-樹（或B樹、B_樹）。 所有關(guān)鍵字在整顆樹中出現(xiàn)，且只出現(xiàn)一次只出現(xiàn)一次，非葉子結(jié)點(diǎn)可以命中；*453階B樹3）B+樹在B-樹基礎(chǔ)上，為葉子結(jié)點(diǎn)增加鏈表指針鏈表指針，所有關(guān)鍵字都在葉子結(jié)點(diǎn)中出現(xiàn)，非葉子結(jié)點(diǎn)作為葉子結(jié)點(diǎn)的索引；B+樹總是到葉子結(jié)點(diǎn)才命中樹總是到葉子結(jié)點(diǎn)才命中；*46稀疏索引稠密索引4）B*樹*47在B+樹基礎(chǔ)上，為非葉子結(jié)點(diǎn)也增加鏈表指針，將結(jié)點(diǎn)的最低利用率從1/2提高到2/3；稀疏索引稠密索引4.2 B+樹索引的結(jié)構(gòu) B+樹索引是一個(gè)多級(jí)索引B+樹索引采用平衡樹平衡樹結(jié)構(gòu)，

26、即每個(gè)葉結(jié)點(diǎn)到根的路徑長度相同。每個(gè)非葉結(jié)點(diǎn)有 n/2 到n個(gè)子結(jié)點(diǎn)，n對特定的樹是固定的，稱為階數(shù)階數(shù)。B+樹索引中的所有結(jié)點(diǎn)的結(jié)構(gòu)都相同樹索引中的所有結(jié)點(diǎn)的結(jié)構(gòu)都相同，它最多包含n-1個(gè)搜索碼值，以及n個(gè)指針個(gè)指針每個(gè)結(jié)點(diǎn)中的搜索碼值升序存放，即如果ij，那么KiKj。1）葉結(jié)點(diǎn)的結(jié)構(gòu)對i=1, 2, , n-1，指針Pi指向具有搜索碼值Ki的一條文件記錄或指向一個(gè)指針桶，且指針桶中的每個(gè)指針指向具有搜索碼值Ki的一條文件記錄。指針Pn有特殊的作用。圖7-16是Student文件的B+樹索引的葉結(jié)點(diǎn)結(jié)構(gòu)，搜索碼為studentName。由于Student文件中的記錄物理上直接按搜索碼stu

27、dentName有序，所以葉結(jié)點(diǎn)中的指針直接指向文件的記錄。各個(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ī)處理隨機(jī)處理。B+樹索引中的非葉結(jié)點(diǎn)非葉結(jié)點(diǎn)形成葉結(jié)點(diǎn)上的一個(gè)多級(jí)(稀疏)索引。非葉結(jié)點(diǎn)的結(jié)構(gòu)與葉結(jié)點(diǎn)相同，只不過非葉結(jié)點(diǎn)中的所有指針都是指向B+樹中下一層結(jié)點(diǎn)中下一層結(jié)點(diǎn)

28、的指針。每個(gè)非葉結(jié)點(diǎn)最多可存放n個(gè)指針個(gè)指針(對應(yīng)于存放n-1個(gè)搜索碼)，最少也要存放 n/2 個(gè)指針(對應(yīng)于存放 (n-1)/2 個(gè)搜索碼)。一個(gè)結(jié)點(diǎn)中存放的指針數(shù)稱為該結(jié)點(diǎn)的扇出扇出。2）非葉結(jié)點(diǎn)的結(jié)構(gòu)假設(shè)一個(gè)非葉結(jié)點(diǎn)中存放了m個(gè)指針， n/2 mn。若mnr/fr，其中nr表示將要存儲(chǔ)的記錄總數(shù)，fr表示一個(gè)桶中能存放的記錄數(shù)目。偏斜。某些桶分配到的記錄比其他桶多，所以，即使其他桶仍有空間，有些桶仍可能溢出，稱為桶偏斜。偏斜發(fā)生的原因有兩個(gè)：多個(gè)記錄可能具有相同的搜索碼值；所選擇的散列函數(shù)可能會(huì)造成搜索碼值的分布不均勻。桶溢出的處理桶溢出的處理方法：主要有閉散列和開散列二種方法。閉散列：

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

30、針組織成散列文件結(jié)構(gòu)。散列索引的構(gòu)建方法：將散列函數(shù)作用于一條文件記錄的搜索碼值，以確定索引項(xiàng)的散列桶；將由該搜索碼值以及相應(yīng)文件記錄指針組成的索引項(xiàng)存入散列桶(或溢出桶)中。參見圖7-22所示的Student文件的一個(gè)輔助散列索引散列索引散列索引散列索引只能是一種輔助索引結(jié)構(gòu)。散列索引從來不需要作為主索引(聚集索引)來使用，因?yàn)橐粋€(gè)文件如果自身是按散列組織的，就不必再在其上另外建立一個(gè)獨(dú)立的散列索引了。不過，既然散列文件組織能像索引那樣提供對記錄的直接訪問，不妨就認(rèn)為以散列形式組織的文件上也有一個(gè)聚集散列索引了。 5.6 靜態(tài)和動(dòng)態(tài)散列 靜態(tài)散列：在選擇散列函數(shù)時(shí)就知道記錄的總數(shù)，即桶的數(shù)量

31、必須事先確定。對于規(guī)模變化的數(shù)據(jù)庫使用靜態(tài)散列，有3種選擇：根據(jù)當(dāng)前文件大小選擇散列函數(shù)。這種選擇會(huì)使性能隨數(shù)據(jù)庫增大而下降。根據(jù)預(yù)計(jì)的將來某個(gè)時(shí)刻文件的大小選擇散列函數(shù)。盡管這樣可以一定程度上避免性能下降，但初始時(shí)會(huì)造成相當(dāng)大的空間浪費(fèi)。隨著文件增大，周期性地對散列結(jié)構(gòu)進(jìn)行重組。重組是一個(gè)復(fù)雜、耗時(shí)的操作，而且重組期間必須禁止對文件的訪問。動(dòng)態(tài)散列技術(shù)允許散列函數(shù)動(dòng)態(tài)改變，以適應(yīng)數(shù)據(jù)庫增大或縮小的需要。5.7 散列與順序索引的比較 散列其實(shí)就是一種不通過值的比較，而通過值的含義值的含義來確定存儲(chǔ)位置的方法，它是為有效地實(shí)現(xiàn)等值查詢等值查詢而設(shè)計(jì)的。散列技術(shù)在等值連接等操作中是很有用的，尤其是

32、在索引嵌套循環(huán)連接方法中，基于散列的索引和基于B+樹的索引在代價(jià)上的差別會(huì)很大。基于散列技術(shù)不支持范圍、最大最小值、排序的檢索不支持范圍、最大最小值、排序的檢索。基于B+樹的索引技術(shù)能有效地支持范圍檢索。選擇散列與順序索引時(shí)的考慮索引或散列的周期性重組的代價(jià)如何？在文件中插入和刪除記錄的頻率如何？是否愿意以增加最壞情況下的訪問時(shí)間為代價(jià)優(yōu)化平均訪問時(shí)間？用戶可能提出哪些類型的查詢？推薦讀物*75數(shù)據(jù)結(jié)構(gòu)與問題求解數(shù)據(jù)結(jié)構(gòu)與問題求解(Java語言版語言版)(第第4版版)美 韋斯 (Mark Allen Weiss) 著, 葛秀慧 等 譯清華大學(xué)出版社清華大學(xué)出版社 2011*76InnoDB數(shù)據(jù)

33、存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)MySQL將所有數(shù)據(jù)都邏輯地存放在ib_data1文件中，稱之為表空間。當(dāng)然，也可以一個(gè)表對應(yīng)一個(gè)物理文件（將innodb_file_per_table設(shè)置成ON）。表空間又劃為成段，有數(shù)據(jù)段，索引段，回滾段。表空間由這些段和頁組成。每段又劃為成區(qū)，InnoDB每次最多可以申請4個(gè)區(qū)，即4M的存儲(chǔ)空間。每個(gè)區(qū)又劃為成頁，一個(gè)區(qū)劃分成64頁，每個(gè)頁的大小是16KB，大小不能夠改，這也固定了一個(gè)區(qū)的大小為4M。頁是MySQL操作的最小邏輯單位。*77InnoDB數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)（續(xù)）數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)（續(xù)）InnoDB是面向行的，這就意味著數(shù)據(jù)行存放在頁中，每頁最多能記錄7992行數(shù)據(jù)。

34、MySQL定義了不同作用的頁類型，比如B-Tree Page, Undo Log Page等，我們最關(guān)心的是B-Tree Page(數(shù)據(jù)頁)。實(shí)際數(shù)據(jù)就以這樣的頁邏輯實(shí)體存在于表空間,總是以B+樹結(jié)構(gòu)索引組織的。換句話就說，實(shí)際數(shù)據(jù)一行一行地存放在B-Tree頁中，這些頁都放在數(shù)據(jù)段leaf node segment中。B-Tree Page是B+樹的葉子節(jié)點(diǎn)。*78InnoDB數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)（續(xù)）數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)（續(xù)）一個(gè)B-Tree樹，由7部分構(gòu)成File Header，這里記錄了頁在表空間的一些信息，比如上一頁，下一頁，屬于哪個(gè)表空間等等Page Header, 這里記錄了頁本身的一些存儲(chǔ)信息

35、。比如第一個(gè)記錄的位置，記錄數(shù)，最后插入記錄行的位置，該頁的索引ID等等Infimum & Supermum Records, MySQL虛擬的二個(gè)行記錄，用來界定記錄的邊界。分別代表此頁中任何pk值還小的值和任何pk值還大的值。user records, 實(shí)際存儲(chǔ)的行記錄。*79InnoDB數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)（續(xù)）數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)（續(xù)）free space,空閑空間，同樣是鏈表結(jié)構(gòu)。當(dāng)一個(gè)數(shù)據(jù)記錄刪除后，就會(huì)加入到空閑鏈表中page directory, 存放了記錄的相對位置。注:聚集索引本身找不到具體的一條記錄。而是通過 聚集索引找到該記錄所在的頁，然后再通過Page Directory進(jìn)行

36、二分查找找到具體數(shù)據(jù)。File Trailer, MySQL InnoDB利用它來保證頁完整地寫入磁盤。*80索引的定義索引是加快數(shù)據(jù)檢索的一種工具一張表可以建立多個(gè)索引，可從不同的角度加快查詢速度；如果索引建立得較多，會(huì)給數(shù)據(jù)維護(hù)帶來較大的系統(tǒng)開銷。索引是由的記錄構(gòu)成索引邏輯上按照搜索碼值進(jìn)行排序，但不改變表中記錄的物理順序；索引和基本表分別存儲(chǔ)。如在班級(jí)表中按所屬學(xué)院建立的索引InstituteIdx，它與Class表之間的關(guān)系可以用圖3-30來表示：*81數(shù)據(jù)庫的索引一般按照B+樹結(jié)構(gòu)來組織，但也有Hash索引和位圖索引等。索引的類型有聚集或非聚集兩種，非聚集索引就是普通索引，一張表可以

37、建立多個(gè)普通索引。每張表僅能建立一個(gè)聚集索引聚集索引是按搜索碼值的某種順序(升序/降序)來重新組織表記錄即索引的順序就是表記錄存放的順序聚集索引可以極大地提高查詢速度，但是給數(shù)據(jù)的修改帶來困難一般建立了聚集索引的表不進(jìn)行更新操作，僅執(zhí)行查詢操作，這在數(shù)據(jù)倉庫中使用得較多。創(chuàng)建索引后，與該索引相關(guān)的描述信息會(huì)保存到數(shù)據(jù)字典中去。*82建立索引操作的語法 CREATE UNIQUE CLUSTERED | NONCLUSTERED INDEX ON ( ASC | DESC, ASC | DESC, ) ON *83其中：UNIQUE：表示建立唯一索引；CLUSTERED | NONCLUSTER

38、ED ：表示建立聚集或非聚集索引，默認(rèn)為非聚集索引；：索引的名稱，索引是數(shù)據(jù)庫中的對象，因此在一個(gè)數(shù)據(jù)庫中必須唯一； ( ASC | DESC, ASC | DESC, )：指出為哪個(gè)表的哪些屬性建立索引ASC | DESC為按升序還是降序建立索引，默認(rèn)為升序；ON ：指定索引文件存放在哪個(gè)邏輯設(shè)備上，該邏輯設(shè)備必須是在創(chuàng)建數(shù)據(jù)庫時(shí)定義的，或加入到數(shù)據(jù)庫中的邏輯設(shè)備。缺省該項(xiàng)時(shí)自動(dòng)將對象建立在主邏輯設(shè)備上。*84例3.72 在班級(jí)表中按所屬學(xué)院建立一個(gè)非聚集索引InstituteIdxCREATE NONCLUSTERED INDEX InstituteIdx ON Class(institu

39、te)例3.73 在學(xué)生表中，首先按班級(jí)編號(hào)的升序，然后按出生日期的降序降序建立一個(gè)非聚集索引ClassBirthIdx。CREATE INDEX ClassBirthIdx ON Student(classNo, birthday DESC)*85索引的刪除索引一旦建立，用戶不需要管理它，由系統(tǒng)自動(dòng)維護(hù)；可刪除那些不經(jīng)常使用的索引；刪除索引操作的語法為：DROP INDEX 刪除索引時(shí)，系統(tǒng)會(huì)同時(shí)從系統(tǒng)的數(shù)據(jù)字典中將該索引的描述一起刪除。例3.74 刪除InstituteIdx索引。DROP INDEX InstituteIdx*86使用navCAT建立索引*87*88*89*90*917.

40、0 數(shù)據(jù)庫的物理組織 數(shù)據(jù)庫的基礎(chǔ)是基于操作系統(tǒng)的文件系統(tǒng)，對數(shù)據(jù)庫的操作都要轉(zhuǎn)化為對文件的操作，如何設(shè)計(jì)文件結(jié)構(gòu)以及有效利用操作系統(tǒng)提供的文件存取方法是DBMS要考慮的事情。關(guān)系數(shù)據(jù)庫中要存儲(chǔ)的數(shù)據(jù)主要包括：關(guān)系表、數(shù)據(jù)字典、索引、日志和備份等。DBMS對不同數(shù)據(jù)的物理組織方式通常是不一樣的。7.1 物理數(shù)據(jù)庫設(shè)計(jì)的概念數(shù)據(jù)庫的物理結(jié)構(gòu)數(shù)據(jù)庫的物理結(jié)構(gòu)數(shù)據(jù)庫在物理設(shè)備上的存儲(chǔ)結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)與存取方法存取方法，它依賴于給定的計(jì)算機(jī)系統(tǒng)。數(shù)據(jù)庫的物理設(shè)計(jì)數(shù)據(jù)庫的物理設(shè)計(jì)為一個(gè)給定的邏輯數(shù)據(jù)模型選取一個(gè)最適合應(yīng)用環(huán)境的物理結(jié)構(gòu)的過程。物理數(shù)據(jù)庫設(shè)計(jì)的目標(biāo)和內(nèi)容目標(biāo)目標(biāo)：提高數(shù)據(jù)庫性能，以滿足應(yīng)用的性能需求；有效利用存儲(chǔ)空間；在性能和代價(jià)之間做出最優(yōu)平衡。內(nèi)容內(nèi)容：確定數(shù)據(jù)庫的存儲(chǔ)結(jié)構(gòu)；為數(shù)據(jù)選擇合適