數(shù)據(jù)庫存儲設(shè)備文件組織與結(jié)構(gòu)

數(shù)據(jù)庫存儲設(shè)備文件組織與結(jié)構(gòu)主要內(nèi)容6.1數(shù)據(jù)庫存儲設(shè)備

6.2

6.3文件結(jié)構(gòu)

6.4索引技術(shù)5/18/202326.1數(shù)據(jù)庫存儲設(shè)備計算機中有兩級存儲,分別是主存和輔存根據(jù)訪問數(shù)據(jù)的速度、成本和可靠性,存儲介質(zhì)可分成以下六類:5/18/20233

1．高速緩沖存儲器（Cache）簡稱為“高速緩存”，也就是一般說的Cache。Cache訪問速度快，但貴，容量小。2.主存儲器（MainMemory）

主存儲器簡稱為主存,或內(nèi)存。主存中的數(shù)據(jù)在掉電或系統(tǒng)崩潰時,會全部丟失。

5/18/202343.磁盤存儲器（Magnetic-DiskStorage）磁盤是目前最常用的外部存儲器,由磁性材料制成,數(shù)據(jù)存儲在磁盤表面。磁盤是一種大容量的可直接存取的外部存儲設(shè)備。在掉電或系統(tǒng)崩潰后,仍能保持?jǐn)?shù)據(jù)不丟失。硬磁盤的特性：5/18/20235①硬磁盤的物理特性硬磁盤的總?cè)萘繛椋?/p>

盤面數(shù)目×每盤面的磁道數(shù)×每磁道的盤塊數(shù)×每盤塊的字節(jié)數(shù)

磁盤是一種直接存儲設(shè)備，可隨機讀寫任一盤塊。盤塊地址的形式是：柱面號磁頭號盤塊號圖6.1磁盤塊地址形式示意圖

5/18/20236②磁盤的性能指標(biāo)

磁盤的性能用磁盤的容量、存取時間、數(shù)據(jù)傳輸速度和可靠性四個參數(shù)衡量。③內(nèi)外存間的數(shù)據(jù)交換

訪問的數(shù)據(jù)不在主存時,需通過外存加載，所以內(nèi)外存間要頻繁地進行數(shù)據(jù)交換，每交換一次數(shù)據(jù)，就稱為一次I/O操作。5/18/20237

數(shù)據(jù)塊的長度不一定恰好等于記錄的整數(shù)倍，通常有兩種組塊方式：不跨塊方式：

一個數(shù)據(jù)塊只包含若干完整記錄，不足以容納一個記錄的零頭空間放棄不用。跨塊方式：

允許一個記錄跨在不同數(shù)據(jù)塊。這種組塊方式雖然可節(jié)省空間，但實現(xiàn)比較困難，用得較少。5/18/20238④廉價磁盤冗余陣列

(RedundantArrayofInexpensive（或Indscendent）Disks，簡稱RAID)

它是利用一臺磁盤陣列控制器來統(tǒng)一管理和控制一組(幾臺到幾十臺)磁盤驅(qū)動器，組成一個高度可靠的、快速的大容量磁盤系統(tǒng)。

實現(xiàn)途徑有兩個：

數(shù)據(jù)重復(fù)存儲和通過并行提高數(shù)據(jù)傳輸速度

RAID按照其基本特性，可分為八級。

5/18/202394磁帶磁帶是一種順序存儲設(shè)備,即磁帶只能順序訪問，不能隨機訪問。主要用于數(shù)據(jù)備份或數(shù)據(jù)歸檔。磁帶的可靠性較好，主要有兩大用途：

作為磁盤的后援存儲器，存儲數(shù)據(jù)庫文件的副本

用來存儲磁盤上存儲不了的大型數(shù)據(jù)庫文件,數(shù)據(jù)庫中不常用的數(shù)據(jù)庫文件或歷史數(shù)據(jù)可以存儲在磁帶上。

5/18/2023105光存儲器

光存儲器是多媒體信息的主要存儲設(shè)備，作為分布式軟件的主要存儲介質(zhì)，可存儲音頻、圖像一類的數(shù)據(jù)。目前流行的光存儲器是光盤只讀存儲器(CD-ROM)。5/18/2023116快擦寫存儲器（FlashMemory）快擦寫存儲器又稱為“電可擦可編程只讀存儲器”，快閃存在掉電后仍能保持?jǐn)?shù)據(jù)不丟失?？扉W存的缺陷是只能支持有限次擦寫。而且不能直接重寫，必須先擦去整組存儲器的內(nèi)存，然后再寫數(shù)據(jù)進去。

5/18/2023126.2文件組織

外存中，數(shù)據(jù)庫以文件形式組織，而文件又是由記錄組成。記錄在物理文件中的實現(xiàn)就是本節(jié)討論的內(nèi)容。文件組織的兩種方式：定長格式和變長格式。5/18/2023136.2.1定長記錄就是每條記錄都是占用一定長度的字節(jié)數(shù)。記錄的排列也就是一張表格每行有相同的長度，以一行為單元進行增加刪除等修改操作。Sn1000001甲Sn2000002乙Sn3000003丙Sn4000004丁5/18/202314SnumCnumScoreS003160S001283S005480S004185S006375S003280S002285S004260S003340

圖6.2定長記錄的文件

5/18/202315圖6.3刪除記錄2，5，7后的文件結(jié)構(gòu)

5/18/202316如上圖每條記錄包含姓名、學(xué)號、班級三條信息。在每條記錄中對應(yīng)的信息占相同的字節(jié)數(shù)，所以每條記錄的長度一定，構(gòu)成了一個含有四條記錄的定長記錄的文件。存在的兩個問題：刪除：刪除后是在其位置補充一個記錄還是忽略這個位置；長度：若物理上每個塊的大小不等于每個記錄的長度倍數(shù)，則必然在讀這樣的記錄時要訪問兩個塊。

5/18/2023176.2.1.1刪除方法1.刪除記錄后，把記錄依次上移。缺點移動次數(shù)過多。2.把最后的記錄補到刪除的位置。只需移動一次。

以上兩個方法都需要移動結(jié)點，操作不靈活，處于靈活的考慮必然會想到指針，就是第三種方法。5/18/2023183.把刪除的結(jié)點用指針鏈接起來首先，文件增設(shè)“文件首部”，其中有一個指針指向第一個被刪除的記錄位置，所有被刪除記錄的位置都用指針鏈接起來，構(gòu)成“空閑記錄鏈表”。缺點：這些被指針鏈接的記錄被稱為“被拴記錄”，若被刪記錄被刪掉，則指向記錄的指針稱為“懸掛指針”，所指空間稱為“垃圾”，也就是別人無法使用而又被空閑著。5/18/2023196.2.1.2.插入方法可以根據(jù)刪除的方法而定，直接插入尾部，或插到空位置。6.2.2變長記錄實際應(yīng)用中定長記錄格式文件較多,但為了增強文件的靈活性,在數(shù)據(jù)庫系統(tǒng)中，有時需要文件中的記錄是變長格式。變長記錄的表示有字節(jié)串形式和定長形式兩種。

5/18/2023206.2.2.1變長記錄的字節(jié)串表示形式

①尾標(biāo)志法

把每個記錄看成連續(xù)的字節(jié)串，然后在每個記錄的尾部附加“記錄尾標(biāo)志符”（∧）,表明記錄結(jié)束。圖6.2的定長記錄文件可以用圖6.4的格式表示。

②記錄長度法

記錄的開始加一個記錄長度的字段來實現(xiàn)，讀取數(shù)據(jù)時以此作為記錄結(jié)束與否的標(biāo)志。

5/18/202321SnumCnumScoreCnumScoreCnumScore

S003160280340∧S001283

∧

S005480

∧

S004185260∧

S006375

∧

S002285

∧

圖6.4變長記錄的字節(jié)串表示形式

5/18/202322字節(jié)串表示形式缺點：每條記錄長度不一，被刪除后的位置難于使用。記錄要增長很難?！胺植凼巾摻Y(jié)構(gòu)”：每塊的開始設(shè)置一個“塊首部”，包含以下信息：塊中的記錄數(shù)目，只想塊中自由空間尾部的指針，登記每個記錄近的開始位置和大小的信息。5/18/202323圖6.5分槽式頁結(jié)構(gòu)5/18/2023246.2.2.2變長記錄的定長表示形式預(yù)留空間技術(shù)取所有記錄中最長的一個記錄的長度作為存儲空間的記錄長度，來存儲變長記錄。對于預(yù)留空間，仍如同定長格式的表格狀。缺點：如果每個記錄的差別很大，就會造成大量空間的浪費。

5/18/202325例如圖6.4的字節(jié)串表示形式可以用圖6.6的預(yù)留空間技術(shù)實現(xiàn)。該方法一般在大多數(shù)記錄的長度接近最大長度時才使用，否則使用時空間浪費很大。SnumCnumScoreCnumScoreCnumScoreS003160280340S001283

∧∧∧S005480

∧∧∧S004185260∧∧S006375

∧∧∧S002285

∧∧∧圖6.6變長記錄的預(yù)留空間表示形式5/18/202326指針技術(shù)解決記錄長度差很大的方法，省去過多的空間浪費。每個定長記錄后面增加指針指向在上一方法中可以合并為同一記錄的其他記錄。被指向的整體成為溢出塊。5/18/202327圖6.7變長記錄的指針表示方式

5/18/202328圖6.8固定塊和溢出塊結(jié)構(gòu)5/18/2023296.3文件結(jié)構(gòu)

文件中記錄的組織方式有無序?件、有序文件、聚集文件和HASH文件四種。

6.3.1無序文件無序文件也稱為堆文件．無序文件的操作比較簡單，但查找效率比較低．無序文件的刪除操作比較復(fù)雜，常用的方法主要有以下三種：5/18/202330（１）首先找到被刪記錄所在的磁盤塊，然后讀到主存緩沖區(qū)，在緩沖區(qū)中刪除記錄，最后把緩沖區(qū)內(nèi)容寫回到磁盤文件．（２）在每個記錄的存儲空間增加一個標(biāo)志位，標(biāo)識記錄刪除與否，一般該標(biāo)志常為空。刪除一個記錄時，將此記錄的標(biāo)志位置“1”,以后查找記錄時跳過有該標(biāo)志的記錄。（３）常用于定長記錄文件，刪除一個記錄時，總是把文件末尾記錄移到被刪記錄位置。

5/18/2023316.3.2有序文件有序文件是指記錄按某個（或某些）域的值的大小順序組織，一般最為常用的是按關(guān)鍵字的升序或降序排列，即每個記錄增加一個指針字段，根據(jù)主鍵的大小用指針把記錄鏈接起來。文件中每個記錄增加一個指針字段，根據(jù)查找鍵的大小用指針把記錄連接起來。5/18/202332圖6.9順序文件

5/18/202333有序文件操作

刪除：只需修改指針即可。同定長記錄的方法三

插入：1）定位：找到要插的位置。按查找鍵的順序2）插入：在找到記錄的塊內(nèi)，如果自由空間有空閑紀(jì)錄，那么插入；若沒有就插入到溢出塊中。在初始的時候，可以保持無力順序和查找鍵的順序一致，以提高速度，若多次操作后變化很大，有必要重新組織一次。5/18/2023346.3.3聚集文件文件允許一個文件有多個關(guān)系的記錄組成，即記錄類型文件。例：可以把有關(guān)一個人的全部記錄信息放在相鄰的位置，按人查找信息時就會很方便。5/18/202335圖6.10

插入一個記錄后的順序文件

5/18/202336圖6.11聚集文件例子5/18/2023376.3.4HASH文件哈稀(HASH)文件又稱為散列文件，是一種支持快速存取的文件存儲方法。1．散列的概念：設(shè)K是所有查找鍵值的集合，B是所有桶地址的集合。散列函數(shù)h是從K到B的函數(shù)，它把每個查找鍵值映射到地址集合中的地址。其中每個桶的大小一定。查找鍵集K桶地址集B主文件記錄5/18/202338檢索：1）檢索Ki的記錄，首先計算h(Ki)在B集合中2）根據(jù)桶地址找到桶3）桶內(nèi)查找

特點：不同的查找鍵值的記錄可能在同一個桶內(nèi)，找到桶后仍然有進行檢測。刪除：找到記錄直接刪除即可。5/18/2023392．散列函數(shù)要滿足兩個條件：1）使地址分布均勻；2）地質(zhì)分布隨機。常用方法：質(zhì)數(shù)除余法。缺點：函數(shù)的設(shè)計，若設(shè)計不好會造成很大的不均勻性，查找時間的浪費。5/18/2023403.散列碰撞

問題：由于同所存儲的記錄數(shù)是一定的，再插入操作時很容易發(fā)生溢出。原因：一是桶的數(shù)目少；二是散列的均勻性不好。

解決：1）溢出鏈法：每個同都作為基本桶存在，若溢出系統(tǒng)提供一處同連接在基本桶后面。2）開放式散列法：只存在基本桶，若溢出就插入其他空閑的桶。有兩種選擇方式：1。在溢出桶下面的一個空閑桶；2。采用二次散列的方法。5/18/202341圖6.12

散列結(jié)構(gòu)的溢出鏈

5/18/202342４.散列方法

常用的HASH方法有簡單HASH方法，動態(tài)HASH方法和可擴展的HASH方法．評價：散列方法必須選取恰當(dāng)?shù)纳⒘泻瘮?shù)。5/18/202343圖6.13HASH桶目錄示例

5/18/2023441.簡單HASH方法。

該方法采用固定個數(shù)的HASH桶，即把文件劃分為N個HASH桶，每個HASH桶對應(yīng)一個磁盤塊，每個HASH桶有一編號。缺點：⑴只能有效地支持HASH域上具有相等比較的數(shù)據(jù)操作。⑵由于HASH桶的數(shù)量一成不變，當(dāng)文件記錄較少時，影響記錄的存取效率。

5/18/2023452.動態(tài)HASH方法

動態(tài)HASH方法中，HASH桶與磁盤塊一一對應(yīng)。HASH桶的數(shù)量不是固定的，而是隨文件記錄的變化而增加或減少的。

5/18/202346

圖6.14動態(tài)HASH方法結(jié)構(gòu)5/18/2023473.可擴展的HASH方法特點：按照實際需要申請或釋放空間。查找：求出h(Ki)前i位值m,沿桶地指表位置m處的指針到達某個同中去找記錄。插入：先查找到相應(yīng)的桶，若有空閑空間直接插入；

5/18/202348圖6.15可擴展的HASH方法的結(jié)構(gòu)

5/18/202349分裂桶：情況一：指向這個桶只有一個指針。增加i的值，桶地址表加倍，每一項之分列成相鄰的兩項，但是指向同一個桶。新申請的桶，就得到其中第二個指針。情況二：指向這個桶有多個指針。則桶地址表不用擴大只要分裂桶可以了。申請新的桶空間，原來的桶分出后一半指針指向新的桶，從新分配分裂的桶中的記錄。5/18/202350刪除：查找到Ki的記錄，從桶內(nèi)刪除。刪除后如桶為空，桶也刪除，還有可能引起桶地址的收縮。顯著優(yōu)點：

?數(shù)據(jù)量增長后仍然保持由原有的操作和查詢性能

?空間開銷達到最小5/18/2023516.4索引技術(shù)

索引的組織方式主要有線性索引和樹形索引兩類。6.4.1線性索引線性索引可分為稠密索引和稀疏索引兩種。1.稠密索引對主文件中每一個查找鍵值都建立一個索引記號優(yōu)點:查找、更新數(shù)據(jù)記錄方便,存取速度快缺點:索引項多,索引表大,空間代價大.

5/18/2023522.稀疏索引只對主文件中若干查找鍵值建立一個索引記號。在插入操作較多的應(yīng)用中采用稀疏索引方式是不太適宜的。

5/18/202353K1K2K3…KnA(RK1)A(RK2)A(RK3)…A(RKn)圖6.16.索引結(jié)構(gòu)

5/18/202354圖6.17學(xué)生關(guān)系索引方式

5/18/2023556.4.2B樹1.平衡樹的概念

m階平衡樹或者為空，或者滿足下面條件：每個節(jié)點之多有m棵子樹根節(jié)點或為葉結(jié)點，或至少有兩棵子樹每個非葉結(jié)點至少有[m/2]棵子樹根結(jié)點到葉結(jié)點的每一條路徑都有同樣的長度，即葉結(jié)點在同一層次上平衡樹分為B+樹和B樹

5/18/202356圖6.18多級索引

5/18/202357B樹在上述定義基礎(chǔ)上同時約定：除葉結(jié)點之外的所有其它結(jié)點的索引塊最多可存放m-1個主碼值和m個地址指針。其格式為:

葉結(jié)點上不包含數(shù)據(jù)記錄本身，而是由記錄索引項組成的記錄索引塊，每個記錄索引項包含有主碼值和地址指針。

P0K1P1K2P2…Km-1Pm-15/18/202358一般假設(shè)，每一個索引塊能容納的索引項數(shù)是個奇數(shù)，且m=2d-1≥3;每一個記錄索引塊能容納的記錄索引項也是個奇數(shù)，且n=2e-1≥3。

5/18/202359圖6.19多級索引的B樹5/18/2023606.4.3B+樹1．結(jié)構(gòu)每個結(jié)點之多有m-1各查找鍵Ki，m個指針Pi;如上圖。P1K1P2................Pn-1Kn-1Pn5/18/202361葉結(jié)點：葉結(jié)點的指針指向主文件的記錄；查找鍵在[m-1/2]——m-1之間；葉結(jié)點最后的指針指向下一葉結(jié)點。非葉結(jié)點：組成多級稀疏索引，指針在[m/2]——m之間，指針Pi指向所有查找鍵大于等于Ki-1,小于Ki。5/18/202362圖20B+樹的模型

5/18/202363

圖6.21圖6.19中的Ｂ樹的Ｂ＋樹5/18/202364查詢：

方法：先找第一個大于k的查找鍵值，沿其左面的指針到達下一層，以此查找下去。

特點：查詢的層數(shù)相同為樹的高度，因為都是在葉結(jié)點鏈接主文件。5/18/2023652．修改操作：不引起索引結(jié)點分裂的插入若以在葉結(jié)點出現(xiàn)，直接插入記錄；否則，找到第一個大于的查找鍵值，在其前面插入，其后的都向后移。5/18/202366不引起索引結(jié)點合并的刪除;查找到主文件，刪除記錄；若主文件中還有同查找鍵的記錄不修改索引；若無，從葉結(jié)點中刪除相應(yīng)的鍵值和指針。引起分裂的插入;插入葉結(jié)點后，把多出來的分裂出去；修改父結(jié)點，插入心結(jié)點中的最小值，同理其父結(jié)點進行修改。

5/18/202367圖6.22在圖6.21中插入值為41數(shù)據(jù)記錄后的Ｂ＋樹

5/18/202368引起合并的刪除在刪除葉結(jié)點后，引起結(jié)點不符合定義，將被刪除，若父結(jié)點中有也將刪除，導(dǎo)致合并的發(fā)生。B+樹的性能分析顯著優(yōu)點：?搜索代價較??；

?解決了數(shù)據(jù)記錄在插入，刪除和未用回收等存儲組織問題。5/18/202369圖6.23在圖6.21中刪除主碼值為26的數(shù)據(jù)記錄后的Ｂ＋樹5/18/202370小結(jié)

數(shù)據(jù)庫是數(shù)據(jù)的有序集合，需保留在計算機外存介質(zhì)上反復(fù)應(yīng)用。由于實際應(yīng)用系統(tǒng)數(shù)據(jù)規(guī)模都很龐大,加之經(jīng)常要從數(shù)據(jù)集合中檢索需要的數(shù)據(jù)，所以數(shù)據(jù)組織的方式，數(shù)據(jù)的定位方式，以及數(shù)據(jù)的維護策略的選取十分重要。5/18/202371在磁盤中,數(shù)據(jù)庫以文件形式組織。文件組織有兩種方法：一種是把記錄設(shè)計成定長格式,也就是每個文件只存儲某一確定長度的記錄；另一種是變長格式,使之能存放不同長度的記錄。實現(xiàn)變長記錄的技術(shù)有多種,包括分槽式頁結(jié)構(gòu)、指針方法和保留空間等方法。5/18/202372小結(jié)

文件結(jié)構(gòu)有堆文件、順序文件、散列文件和聚集文件等四種。為了提高查找速度,可以為文件建立索引或