1、第八章 物理存儲結構生物醫(yī)學軟件工程本章概要數(shù)據(jù)庫存儲設備文件與文件記錄無序文件有序文件HASH文件索引文件B_樹和B_+樹索引結構8.1 數(shù)據(jù)庫存儲設備磁盤存儲器磁盤容量的計算公式:硬盤容量=面數(shù)(道數(shù)/面)(扇數(shù)/道) (字節(jié)數(shù)/扇).使用磁頭存取磁盤數(shù)據(jù)的時間稱為存取時間，由三部分組成： 存取時間=尋道時間+旋轉延遲+數(shù)據(jù)傳輸前兩項機械運動的時間為主要部分磁盤緩沖處理技術磁盤驅動器和CPU可并行工作，在主存設置多個緩沖區(qū)，當磁盤驅動器與一個緩沖區(qū)交換數(shù)據(jù)時，CPU同時處理另一個緩沖區(qū)中的數(shù)據(jù)。讀數(shù)據(jù)a入第i塊讀數(shù)據(jù)b入塊i+1讀數(shù)據(jù)a入塊i+2讀數(shù)據(jù)b入塊i+3在第i塊處理a在塊i+1處

2、理b在塊i+2處理a在塊i+3處理b磁盤驅動器工作CPU工作時間緩沖區(qū)1緩沖區(qū)2主存磁盤CPU磁盤的調(diào)度策略磁盤讀寫效率主要取決于尋道和旋轉操作，磁盤的調(diào)度策略的目的是減少機械運動。 以下是優(yōu)化尋道時間的幾個策略：先來先服務近者優(yōu)先全程移動掃描移動掃描分組掃描間歇式掃描磁盤容錯技術磁盤可能會出現(xiàn)故障，當發(fā)生故障時，如果數(shù)據(jù)沒有備份到另一個介質(zhì)中，數(shù)據(jù)將會被永久的丟失。這就需要磁盤冗余技術來解決。以下是常用的RAID策略：簡單RAID策略RAID4策略RAID5策略RAID6策略本章概要數(shù)據(jù)庫存儲設備文件與文件記錄無序文件有序文件HASH文件索引文件B_樹和B_+樹索引結構8.2 文件與文件記錄

3、記錄：記錄是數(shù)據(jù)的一種存儲形式。它由一組相關的數(shù)據(jù)項排列而成。每個數(shù)據(jù)項稱為記錄的一個域。每個域都具有名字和數(shù)據(jù)類型。記錄型：一組域名字及其對應的數(shù)據(jù)類型構成了記錄型。文件：文件是具有相同記錄型的記錄序列。定長記錄文件：記錄長度一致的文件。變長記錄文件：記錄長度不一致的文件。記錄存儲方式跨塊存儲記錄方式非跨塊存儲記錄方式允許一個記錄儲存在不同磁盤塊。若記錄長度大于磁盤塊容量，則存儲于由磁盤塊組成的鏈表。不允許一個記錄跨塊儲存。連續(xù)存儲ii+1i+2ijk鏈接存儲索引存儲ijk刪除操作三種方法：(1)逐個磁盤塊讀進內(nèi)存緩沖區(qū)搜索，找到符合條件的記錄即將其刪除，然后把帶空泡的塊寫回磁盤。(2)在前

4、法中對記錄增設標記位，對刪除記錄作出標識并作周期處理。(3)在定長記錄的情況下，把文末記錄移動到被刪除記錄的位置。插入：在文件頭獲得末塊地址，將末塊讀入內(nèi)存追加新記錄，然后將文件塊寫回到磁盤查詢：采用順序搜索法，即逐個文件塊讀入內(nèi)存，逐條記錄檢驗條件。若文件占B個磁盤塊，滿足條件的記錄只有一條，則平均搜索(B+1)/2個塊修改：經(jīng)查找，把含目標記錄的文件塊讀入內(nèi)存，修改記錄后，把文件塊寫回磁盤。8.3 無序文件刪除操作：同樣需要移動記錄。但若使用刪除標記和周期整理磁盤空間的方法，則可提高效率。修改操作：若修改非排序域，對記錄定位后，連塊讀入內(nèi)存，修改后把塊寫回磁盤；若修改排序域，可采用先刪除后

5、插入的方法。插入操作：需要將插入位置之后的記錄依次后移，騰出空間存儲新記錄。記錄移動量平均是總記錄數(shù)的一半。查找操作：若查詢條件不定義在排序域，則只能象無序文件那樣采用順序搜索法；若查詢條件定義在有序文件的排序域，則可用二分法尋找記錄，查詢的時間復雜性O(log2N)，其中N是文件的記錄數(shù)。8.4 有序文件8.5 HASH文件HASH文件是一種支持快速存取的文件存儲方法。需要指定文件的一個域為hash域，域上的每個值都對應一個磁盤塊的地址。介紹三種HASH方法：簡單HASH方法 動態(tài)HASH方法可擴展的HASH方法索引的創(chuàng)建Create index on (列名, );Alter table

6、add index on(列名,.);在創(chuàng)建表的時候直接指定索引普通索引唯一索引：unique，與普通索引類似，但索引列的值必須唯一，且可以有空值；如果是組合索引，則列值的組合必須唯一。主鍵索引：是一種特殊的唯一索引，不允許有空置，一般是在建表的時候，同時創(chuàng)建主鍵索引。組合索引：是與單列索引對比而言的。索引是按對象特征借助索引文件獲取存儲指針的快速查詢技術。用這種方法查詢的基本步驟是：根據(jù)查詢條件，在數(shù)據(jù)文件選定一個或一組域(稱之為索引域)；建立索引文件，該文件包括兩個域：索引域和塊指針，索引文件的記錄稱為索引項，全體索引項按索引域排序；用戶按索引域值借助索引文件，獲取塊指針并讀取記錄。因為索

7、引文件是有序文件，能應用兩分查找法等算法，故能提高查找速度。數(shù)據(jù)文件越大，索引查找的效益就越明顯。索引項數(shù)與數(shù)據(jù)記錄數(shù)之比可以是1:n，也可以是1:1 ；數(shù)據(jù)文件可以按索引域排序，也可以是無序文件。8.6 索引文件何時創(chuàng)建索引？一般，在where中出現(xiàn)的列需要建立索引在mysql中，只對, , =, between , in, 及某些時候的like才使用索引。索引有那些不足之處？提高了查詢速度，降低更新表的速度。更新表時，不僅有保存數(shù)據(jù)文件，還要保存索引文件建立索引會生成索引文件，占用磁盤空間。一般這種問題不嚴重，但如果在一個大表創(chuàng)建了多種組合索引，索引文件會膨脹很快。使用索引的注意事項：索引

8、中不會包含有null值使用短索引Like語句操作不要在列上進行運算不使用not in 和 操作Mysql 中不區(qū)分聚集索引和非聚集索引主索引文件：有序文件索引域是鍵聚集索引：有序文件索引域是一個非鍵域輔助索引：索引域建立在數(shù)據(jù)文件非排序域多級索引本章概要數(shù)據(jù)庫存儲設備文件與文件記錄無序文件有序文件HASH文件索引文件B_樹和B_+樹索引結構8.7 B_樹和B_+樹索引結構B_樹和B+_樹是樹型數(shù)據(jù)結構的特例，是重要的動態(tài)文件索引結構，用于數(shù)據(jù)庫的多級索引。 B_樹最早出現(xiàn)于1972年。由于這種結構具有高效、易變、平衡和獨立于硬件結構的優(yōu)點，因而在數(shù)據(jù)庫系統(tǒng)中得到廣泛的應用，成為最重要的動態(tài)文件

9、索引結構。 B_+樹是B_樹的改進。本節(jié)介紹：索引樹、B_樹、B_+樹一、索引樹索引樹是一種特殊的樹型數(shù)據(jù)結構。上節(jié)介紹的多級索引結構可視作索引樹。P1K1Ki-1PiKiKq-1PqXXXXK1Ki-1XKiKq-1X定義：秩為P的索引樹是一個滿足下述條件的樹形數(shù)據(jù)結構:每個結點存儲如下的信息: (p1,k1, p2,k2,pq-1,kq-1 ,pq), qP.每個pi是一個指向子結點的指針或空指針，ki是來自有序集合的索引值,k1k2 kq-1pi 所指子樹中的所有值x滿足：當1iq時有ki-1xki；當i=1時xkq-1.369178512索引樹滿足動態(tài)文件要求，但有如下缺點：樹不平衡，

10、葉結點層次深度不統(tǒng)一；刪除記錄的操作使某些結點接近于空，使空間利用率低。后邊介紹的B_樹概念通過對樹增加約束，克服了這兩個缺點。二、B_樹索引結構為克服索引樹的缺點，對它增加約束，于是得到B_樹的概念。B_樹定義：以鍵為索引域、秩為D的B_樹是樹形數(shù)據(jù)結構，且滿足：每結點對應一個索引塊，存儲樹指針Ti和索引項的信息： (T1,T2,Tq-1,Tq),k1k2kq-1內(nèi)結點樹指針Ti指向的子樹中,每個索引值x滿足：當1iq-1有ki-1xki ; 當i=1有xkq-1每個非根結點的索引項數(shù)是D/2D，若根結點不是唯一結點，其索引項數(shù)是1D；每個結點的樹指針數(shù)比索引項數(shù)多1；TP1(K1,DP1)

11、(Ki-1,DPi-1)TPi(Ki,DPi)(Kq-1,DPq-1)PqXXXXK1Ki-1XKiKq-1XB_樹查找算法按索引域值k，在B_樹檢索數(shù)據(jù)，返回找到的記錄。P:=根結點的磁盤塊地址；WHILE P不是空指針 DO 讀P指向的結點 (T1,T2,Tq-1,Tq) 到主存； IF 存在一個i使得Ki=k THEN 讀由Di指向的磁盤塊到主存緩沖區(qū)buff ； 在buff中找出索引值為k的記錄； 返回找到的記錄 ； ELSE IF kKq-1 THEN P:=Tq ENDIF ； IF 存在一個i使得Ki-1kKi THEN P:=Ti ENDIF ； ENDIF;ENDWHILE;

12、返回記錄不存在.B_樹插入記錄算法 設索引域是鍵，先把r插入到數(shù)據(jù)文件的磁盤塊Dt，然后按索引值k在B樹找到(類似查找算法)插入的葉結點。若該結點未滿，則把索引項插入其中，否則對該點實行分裂取中操作： 把舊結點的索引項集等分兩半， 按序分配在兩個新結點中， 并把處于中間位置的索引項移升到父結點。 若父結點也滿，則又要對其作分裂處理， 這個過程可能持續(xù)到根結點，此時樹的高度加1。B_樹刪除記錄算法 先按索引值k在B樹找到結點及索引項， 按Dt找到數(shù)據(jù)塊并把記錄r刪除，然后更新樹： 若在葉點，則僅在點內(nèi)刪除， 否則把樹內(nèi)右緊鄰的索引項移來覆蓋。 若改動過的葉結點索引項數(shù)小于秩D，則須與父結點某些索

13、 引項合并到兄弟結點，原則上先考慮左兄弟結點。若合并過 程延續(xù)下去波及到根結點，則樹高減1.下邊是在秩4的B_樹插入記錄的過程例子(設索引項是鍵)：考慮B_樹的一個狀態(tài)(符號A、B、M表示10、11、22)現(xiàn)要在7號結點插入索引域值E。直接插入使7號結點成為BCDEF，索引項數(shù)超限。于是作分裂取中處理：把中間項D移升到(父)3號節(jié)點，左半部分BC留在原結點，右半部分EF存入新結點即71號結點：.A.4.7.G.K.1.2.3.5.6.8.9.B.C.D.F.H.I.J.L.M.123456789.A.4.7.D.G.K.1.2.3.5.6.8.9.B.C.H.I.J.L.M.E.F.77112

14、345689因秩是4，故非根節(jié)點的索引項數(shù)是24下邊是在秩4的B_樹刪除記錄的過程例子(設索引域是鍵)：考慮B_樹的一個狀態(tài)(符號A、B、M表示10、11、22).A.4.7.D.G.K.1.2.3.5.6.8.9.B.C.H.I.J.L.M.E.F.77112345689.A. .D.G.K.BC EF HIJ LM .4.123 5679.D.4.A.G.K.1.2.3.5.6.7.9.B.C.H.I.J.L.M.E.F.7711234589現(xiàn)要在6號結點刪除索引域值8。刪除后結點成為9，索引項數(shù)2。于是和父點的索引值7合并到左兄弟點，使2號點索引項數(shù)2。于是把2號點連同父點的索引值A合并到右兄弟，再分裂取中便完成刪除因秩是4，故非根節(jié)點的索引項數(shù)是24.D.4.A.G.K.1.2.3.5.6.7.9.B.C.H.I.J.L.M.E.F.7711234589.D.4.A.G.J.1.2.3.5.6.7.9.B.C.H.I.L.M.E.F.7711234589現(xiàn)要在3號點刪索引域值K。刪后，右緊鄰的L補上，使9號點成為M，索引項數(shù)2。于是把9號點連同父點的索引值L合并到左兄弟點，得HIJLM.索引項數(shù)超限，對其作分裂取中處理便完成刪除。D 4A123 5679 BC GLEF HIJ M再