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

1、2022-2-216.1數(shù)據(jù)庫存儲(chǔ)設(shè)備 計(jì)算機(jī)中有兩級(jí)存儲(chǔ)計(jì)算機(jī)中有兩級(jí)存儲(chǔ),分別是分別是主存主存和和輔存輔存根據(jù)訪問數(shù)據(jù)的速度根據(jù)訪問數(shù)據(jù)的速度、成本和可靠性成本和可靠性,存儲(chǔ)介存儲(chǔ)介質(zhì)質(zhì)可分成以下六類可分成以下六類:第1頁/共77頁2022-2-22第2頁/共77頁2022-2-233. 磁盤存儲(chǔ)器（Magnetic-Disk Storage） 磁盤是目前最磁盤是目前最常用的常用的外部存儲(chǔ)器外部存儲(chǔ)器,由磁性材料制由磁性材料制成成,數(shù)據(jù)存儲(chǔ)在磁盤表面數(shù)據(jù)存儲(chǔ)在磁盤表面。 磁盤是一種大容量的可直接存取的外部存儲(chǔ)設(shè)磁盤是一種大容量的可直接存取的外部存儲(chǔ)設(shè)備備。在掉電或系統(tǒng)崩潰后在掉電或系統(tǒng)崩潰

2、后,仍能保持?jǐn)?shù)據(jù)不丟失仍能保持?jǐn)?shù)據(jù)不丟失。 硬磁盤的特性硬磁盤的特性：第3頁/共77頁2022-2-24硬磁盤的物理特性硬磁盤的物理特性 硬磁盤的總?cè)萘繛橛泊疟P的總?cè)萘繛椋?盤面數(shù)目盤面數(shù)目 每盤面的磁道數(shù)每盤面的磁道數(shù) 每磁道的盤塊數(shù)每磁道的盤塊數(shù) 每盤塊的字節(jié)數(shù)每盤塊的字節(jié)數(shù) 磁盤是一種直接存儲(chǔ)設(shè)備磁盤是一種直接存儲(chǔ)設(shè)備，可隨機(jī)讀寫任一可隨機(jī)讀寫任一盤塊。盤塊地址的形式是盤塊。盤塊地址的形式是：圖6.1 磁盤塊地址形式示意圖 第4頁/共77頁2022-2-25磁盤的性能指標(biāo)磁盤的性能指標(biāo) 磁盤的性能用磁盤的性能用磁盤的容量容量、存取時(shí)間存取時(shí)間、數(shù)據(jù)數(shù)據(jù)傳輸速度傳輸速度和和可靠性可靠性四個(gè)

3、參數(shù)衡量四個(gè)參數(shù)衡量。 內(nèi)內(nèi)外存間的數(shù)據(jù)交換外存間的數(shù)據(jù)交換 訪問的數(shù)據(jù)不在主存時(shí)訪問的數(shù)據(jù)不在主存時(shí), 需通過外存加載需通過外存加載，所以內(nèi)外存間要頻繁地進(jìn)行數(shù)據(jù)交換所以內(nèi)外存間要頻繁地進(jìn)行數(shù)據(jù)交換，每交換一每交換一次數(shù)據(jù)次數(shù)據(jù)，就稱為一次就稱為一次 I/O 操作操作。第5頁/共77頁2022-2-26第6頁/共77頁2022-2-27廉價(jià)磁盤冗余陣列廉價(jià)磁盤冗余陣列 (Redundant Array of Inexpensive（或Indscendent） Disks，簡稱RAID)它是利用一臺(tái)磁盤陣列控制器來統(tǒng)一管理和控制一組 ( ( 幾臺(tái)到幾十臺(tái) ) ) 磁盤驅(qū)動(dòng)器，組成一個(gè)高度可靠的

4、、快速的大容量磁盤系統(tǒng)。 u 實(shí)現(xiàn)途徑有兩個(gè)：數(shù)據(jù)重復(fù)存儲(chǔ)數(shù)據(jù)重復(fù)存儲(chǔ) 和通過并行提高數(shù)據(jù)傳輸速通過并行提高數(shù)據(jù)傳輸速度度 RAID 按照其基本特性，可分為八級(jí) 。 第7頁/共77頁2022-2-284 磁帶u磁帶是一種順序存儲(chǔ)設(shè)備 , ,即磁帶只能順序訪問，不能隨機(jī)訪問。u主要用于數(shù)據(jù)備份或數(shù)據(jù)歸檔。u磁帶的可靠性較好，主要有兩大用途： 作為磁盤的后援存儲(chǔ)器，存儲(chǔ)數(shù)據(jù)庫文件的副本 用來存儲(chǔ)磁盤上存儲(chǔ)不了的大型數(shù)據(jù)庫文件, ,數(shù)據(jù)庫中不常用的數(shù)據(jù)庫文件或歷史數(shù)據(jù)可以存儲(chǔ)在磁帶上。 第8頁/共77頁2022-2-295 5 光存儲(chǔ)器 光存儲(chǔ)器是多媒體信息的主要存儲(chǔ)設(shè)備光存儲(chǔ)器是多媒體信息的主要存

5、儲(chǔ)設(shè)備，作為作為分布式軟件的主要存儲(chǔ)介質(zhì)分布式軟件的主要存儲(chǔ)介質(zhì)，可存儲(chǔ)音頻、圖可存儲(chǔ)音頻、圖像一類的數(shù)據(jù)像一類的數(shù)據(jù) 。 目前流行的光存儲(chǔ)器是光盤只讀存儲(chǔ)器 (CD-(CD-ROM) ROM) 。第9頁/共77頁2022-2-210第10頁/共77頁2022-2-2116.2 文件組織 外存中，數(shù)據(jù)庫以文件形式組織，而文件又是由記錄組成。記錄在物理文件中的實(shí)現(xiàn)就是本節(jié)討論的內(nèi)容。 文件組織的兩種方式：定長格式和變長格式。 第11頁/共77頁2022-2-212定長記錄 就是每條記錄都是占用一定長度的字節(jié)數(shù)。記錄的排列也就是一張表格每行有相同的長度，以一行為單元進(jìn)行增加刪除等修改操作。第12頁

6、/共77頁2022-2-213SnumCnumScoreS003160S001283S005480S004185S006375S003280S002285S004260S003340圖6.2 定長記錄的文件 第13頁/共77頁2022-2-214 第14頁/共77頁2022-2-215如上圖每條記錄包含姓名、學(xué)號(hào)、班級(jí)三條信息。在每條記錄中對(duì)應(yīng)的信息占相同的字節(jié)數(shù)，所以每條記錄的長度一定，構(gòu)成了一個(gè)含有四條記錄的定長記錄的文件。存在的兩個(gè)問題：1. 刪除：刪除后是在其位置補(bǔ)充一個(gè)記錄還是忽略這個(gè)位置；2. 長度：若物理上每個(gè)塊的大小不等于每個(gè)記錄的長度倍數(shù)，則必然在讀這樣的記錄時(shí)要訪問兩個(gè)塊。

7、 第15頁/共77頁2022-2-216刪除方法 1. 刪除記錄后，把記錄依次上移。 缺點(diǎn)移動(dòng)次數(shù)過多。2. 把最后的記錄補(bǔ)到刪除的位置。 只需移動(dòng)一次。 以上兩個(gè)方法都需要移動(dòng)結(jié)點(diǎn)，操作不靈活，處于靈活的考慮必然會(huì)想到指針，就是第三種方法。第16頁/共77頁2022-2-2173. 把刪除的結(jié)點(diǎn)用指針鏈接起來首先，文件增設(shè)“文件首部”，其中有一個(gè)指針指向第一個(gè)被刪除的記錄位置，所有被刪除記錄的位置都用指針鏈接起來，構(gòu)成“空閑記錄鏈表”。缺點(diǎn)：這些被指針鏈接的記錄被稱為“被拴記錄”，若被刪記錄被刪掉，則指向記錄的指針稱為“懸掛指針”，所指空間稱為“垃圾”，也就是別人無法使用而又被空閑著。第17

8、頁/共77頁2022-2-218插入方法 可以根據(jù)刪除的方法而定，直接插入尾部，或插到空位置。變長記錄 實(shí)際應(yīng)用中定長記錄格式文件較多, ,但為了增強(qiáng)文件的靈活性, ,在數(shù)據(jù)庫系統(tǒng)中，有時(shí)需要文件中的記錄是變長格式。 變長記錄的表示有字節(jié)串形式和定長形式兩種。 第18頁/共77頁2022-2-219變長記錄的字節(jié)串表示形式 尾標(biāo)志法 把每個(gè)記錄看成連續(xù)的字節(jié)串把每個(gè)記錄看成連續(xù)的字節(jié)串，然后在然后在每個(gè)記錄的尾部附加每個(gè)記錄的尾部附加 “ 記錄尾標(biāo)志符記錄尾標(biāo)志符 ” （）, 表明記錄結(jié)束表明記錄結(jié)束。圖 6.2 6.2 的定長記錄文件可以用圖 6.4 6.4 的格式表示。 記錄長度法 記錄的

9、開始加一個(gè)記錄長度的字段來實(shí)現(xiàn)記錄的開始加一個(gè)記錄長度的字段來實(shí)現(xiàn)，讀取數(shù)據(jù)時(shí)以此作為記錄結(jié)束與否的標(biāo)志讀取數(shù)據(jù)時(shí)以此作為記錄結(jié)束與否的標(biāo)志。 第19頁/共77頁2022-2-220SnumCnumScoreCnumScoreCnumScoreS003160280340S001283S005480S004185260S006375S002285 圖6.4 變長記錄的字節(jié)串表示形式 第20頁/共77頁2022-2-221字節(jié)串表示形式缺點(diǎn)： 每條記錄長度不一，被刪除后的位置難于使用。 記錄要增長很難 。 “分槽式頁結(jié)構(gòu)”：每塊的開始設(shè)置一個(gè)“塊首部”，包含以下信息：塊中的記錄數(shù)目，只想塊中自由空

10、間尾部的指針，登記每個(gè)記錄近的開始位置和大小的信息。第21頁/共77頁2022-2-222第22頁/共77頁2022-2-223變長記錄的定長表示形式 1.預(yù)留空間技術(shù) 取所有記錄中最長的一個(gè)記錄的長度作為存儲(chǔ)空間的記錄長度，來存儲(chǔ)變長記錄。對(duì)于預(yù)留空間，仍如同定長格式的表格狀。缺點(diǎn)：如果每個(gè)記錄的差別很大，就會(huì)造成大量空間的浪費(fèi)。 第23頁/共77頁2022-2-224 例如圖 6.4 的字節(jié)串表示形式可以用圖 6.6 的預(yù)留空間技術(shù)實(shí)現(xiàn)。該方法一般在大多數(shù)記錄的長度接近最大長度時(shí)才使用，否則使用時(shí)空間浪費(fèi)很大。SnumCnumScoreCnumScoreCnumScoreS00316028

11、0340S001283S005480S004185260S006375S002285 圖6.6 變長記錄的預(yù)留空間表示形式第24頁/共77頁2022-2-2252.指針技術(shù) 解決記錄長度差很大的方法，省去過多的空間浪費(fèi)。每個(gè)定長記錄后面增加指針指向在上一方法中可以合并為同一記錄的其他記錄。被指向的整體成為溢出塊。 第25頁/共77頁2022-2-226 第26頁/共77頁2022-2-227第27頁/共77頁2022-2-2286.3 文件結(jié)構(gòu) 文件中記錄的組織方式有無序件、有序文件、聚集文件和HASH 文件四種。 無序文件 無序文件也稱為堆文件無序文件的操作比較簡單，但查找效率比較低 無序文

12、件的刪除操作比較復(fù)雜，常用的方法主要有以下三種：第28頁/共77頁2022-2-229（）首先找到被刪記錄所在的磁盤塊，然后讀到主存緩沖區(qū)，在緩沖區(qū)中刪除記錄，最后把緩沖區(qū)內(nèi)容寫回到磁盤文件（）在每個(gè)記錄的存儲(chǔ)空間增加一個(gè)標(biāo)志位，標(biāo)識(shí)記錄刪除與否，一般該標(biāo)志常為空。刪除一個(gè)記錄時(shí)，將此記錄的標(biāo)志位置“1”, 以后查找記錄時(shí)跳過有該標(biāo)志的記錄。（）常用于定長記錄文件，刪除一個(gè)記錄時(shí)，總是把文件末尾記錄移到被刪記錄位置。 第29頁/共77頁2022-2-230有序文件 有序文件是指記錄按某個(gè)（或某些）域的值的大小順序組織，一般最為常用的是按關(guān)鍵字的升序或降序排列，即每個(gè)記錄增加一個(gè)指針字段，根據(jù)主

13、鍵的大小用指針把記錄鏈接起來。 文件中每個(gè)記錄增加一個(gè)指針字段，根據(jù)查找鍵的大小用指針把記錄連接起來。第30頁/共77頁2022-2-231 第31頁/共77頁2022-2-232u有序文件操作 刪除：只需修改指針即可。同定長記錄的方法三 插入： 1）定位：找到要插的位置。按查找鍵的順序 2）插入：在找到記錄的塊內(nèi)，如果自由空間有空閑紀(jì)錄，那么插入；若沒有就插入到溢出塊中。 在初始的時(shí)候，可以保持無力順序和查找鍵的順序一致，以提高速度，若多次操作后變化很大，有必要重新組織一次。第32頁/共77頁2022-2-233聚集文件 文件允許一個(gè)文件有多個(gè)關(guān)系的記錄組成，即記錄類型文件。例：可以把有關(guān)一

14、個(gè)人的全部記錄信息放在相鄰的位置，按人查找信息時(shí)就會(huì)很方便。第33頁/共77頁2022-2-234 第34頁/共77頁2022-2-235第35頁/共77頁2022-2-236文件 哈稀 (HASH) 文件又稱為散列文件，是一種支持快速存取的文件存儲(chǔ)方法。1散列的概念： 設(shè)K是所有查找鍵值的集合，B是所有桶地址的集合。散列函數(shù)h是從K到B的函數(shù)，它把每個(gè)查找鍵值映射到地址集合中的地址。其中每個(gè)桶的大小一定。 查找鍵集K桶地址集B主文件記錄第36頁/共77頁2022-2-237 檢索： 1）檢索Ki的記錄，首先計(jì)算h(Ki)在B集合中 2）根據(jù)桶地址找到桶 3）桶內(nèi)查找 特點(diǎn)：不同的查找鍵值的記

15、錄可能在同一個(gè)桶內(nèi)，找到桶后仍然有進(jìn)行檢測。 刪除：找到記錄直接刪除即可。第37頁/共77頁2022-2-2382散列函數(shù) 要滿足兩個(gè)條件：1）使地址分布均勻；2）地質(zhì)分布隨機(jī)。 常用方法：質(zhì)數(shù)除余法。 缺點(diǎn)：函數(shù)的設(shè)計(jì)，若設(shè)計(jì)不好會(huì)造成很大的不均勻性，查找時(shí)間的浪費(fèi)。第38頁/共77頁2022-2-2393.散列碰撞 問題： 由于同所存儲(chǔ)的記錄數(shù)是一定的，再插入操作時(shí)很容易發(fā)生溢出。 原因：一是桶的數(shù)目少；二是散列的均勻性不好。 解決：1）溢出鏈法：每個(gè)同都作為基本桶存在， 若溢出系統(tǒng)提供一處同連接在基本桶后面。 2）開放式散列法：只存在基本桶，若溢 出就插入其他空閑的桶。有兩種選擇方式：

16、1。在溢出桶下面的一個(gè)空閑桶； 2。采用二次散列的方法。第39頁/共77頁2022-2-240 第40頁/共77頁2022-2-241.散列方法 常用的 HASH 方法有簡單 HASH 方法，動(dòng)態(tài) HASH 方法和可擴(kuò)展的 HASH 方法 評(píng)價(jià)：散列方法必須選取恰當(dāng)?shù)纳⒘泻瘮?shù)。第41頁/共77頁2022-2-242 第42頁/共77頁2022-2-2431.簡單 HASH 方法。 該方法采用固定個(gè)數(shù)的 HASH 桶，即把文件劃分為 N 個(gè)HASH桶，每個(gè)HASH 桶對(duì)應(yīng)一個(gè)磁盤塊，每個(gè) HASH 桶有一編號(hào)。 缺點(diǎn)： 只能有效地支持 HASH 域上具有相 等比較的數(shù)據(jù)操作。 由于 HASH 桶

17、的數(shù)量一成不變，當(dāng) 文件記錄較少時(shí) ，影響記錄的存取效率。 第43頁/共77頁2022-2-2442.動(dòng)態(tài) HASH 方法 動(dòng)態(tài) HASH 方法中，HASH 桶與磁盤塊一一對(duì)應(yīng)。 HASH 桶的數(shù)量不是固定的，而是隨文件記錄的變化而增加或減少的。 第44頁/共77頁2022-2-245第45頁/共77頁2022-2-2463.3.可擴(kuò)展的 HASH HASH 方法 特點(diǎn)： 按照實(shí)際需要申請或釋放空間。查找： 求出h(Ki)前i位值m,沿桶地指表位置m處的指針到達(dá)某個(gè)同中去找記錄。插入： 先查找到相應(yīng)的桶，若有空閑空間直接插入； 第46頁/共77頁2022-2-247 第47頁/共77頁2022

18、-2-248 分裂桶：情況一：指向這個(gè)桶只有一個(gè)指針。增加i的值，桶地址表加倍，每一項(xiàng)之分列成相鄰的兩項(xiàng)，但是指向同一個(gè)桶。新申請的桶，就得到其中第二個(gè)指針。情況二：指向這個(gè)桶有多個(gè)指針。則桶地址表不用擴(kuò)大只要分裂桶可以了。申請新的桶空間，原來的桶分出后一半指針指向新的桶，從新分配分裂的桶中的記錄。 第48頁/共77頁2022-2-249刪除： 查找到Ki的記錄，從桶內(nèi)刪除。刪除后如桶為空，桶也刪除，還有可能引起桶地址的收縮。顯著優(yōu)點(diǎn)： 數(shù)據(jù)量增長后仍然保持由原有的操作和查詢性能 空間開銷達(dá)到最小 第49頁/共77頁2022-2-2506.4 索引技術(shù) 索引的組織方式主要有線性索引和樹形索引兩

19、類 。線性索引 線性索引可分為稠密索引和稀疏索引兩種。1.稠密索引 對(duì)主文件中每一個(gè)查找鍵值都建立一個(gè)索引記號(hào) 優(yōu)點(diǎn) :查找、更新數(shù)據(jù)記錄方便, 存取速度快 缺點(diǎn) :索引項(xiàng)多, 索引表大, 空間代價(jià)大 . 第50頁/共77頁2022-2-2512.稀疏索引 只對(duì)主文件中若干查找鍵值建立一個(gè)索引記號(hào)。 在插入操作較多的應(yīng)用中采用稀疏索引方式是不太適宜的。 第51頁/共77頁2022-2-252K1K2K3KnA(RK1)A(RK2)A(RK3)A(RKn) 圖6.16.索引結(jié)構(gòu) 第52頁/共77頁2022-2-253 第53頁/共77頁2022-2-254樹1.平衡樹的概念 m階平衡樹或者為空，

20、或者滿足下面條件：每個(gè)節(jié)點(diǎn)之多有m棵子樹根節(jié)點(diǎn)或?yàn)槿~結(jié)點(diǎn)，或至少有兩棵子樹每個(gè)非葉結(jié)點(diǎn)至少有m/2棵子樹根結(jié)點(diǎn)到葉結(jié)點(diǎn)的每一條路徑都有同樣的長度，即葉結(jié)點(diǎn)在同一層次上 平衡樹分為B+樹和B樹 第54頁/共77頁2022-2-255 第55頁/共77頁2022-2-256B B樹在上述定義基礎(chǔ)上同時(shí)約定： 除葉結(jié)點(diǎn)之外的所有其它結(jié)點(diǎn)的索引塊最多可存放 m -1 m -1 個(gè)主碼值和 m m 個(gè)地址指針。其格式為 : : 葉結(jié)點(diǎn)上不包含數(shù)據(jù)記錄本身，而是由記錄索引項(xiàng)組成的記錄索引塊，每個(gè)記錄索引 項(xiàng)包含有主碼值和地址指針。 第56頁/共77頁2022-2-257 一般假設(shè)，每一個(gè)索引塊能容納的索引

21、項(xiàng)數(shù)是個(gè)奇數(shù)，且 m=2d-1 3; m=2d-1 3; 每一個(gè)記錄索引塊能容納的記錄索引項(xiàng)也是個(gè)奇數(shù)，且且n=2e-13。 第57頁/共77頁2022-2-258第58頁/共77頁2022-2-259樹1結(jié)構(gòu)每個(gè)結(jié)點(diǎn)之多有m-1各查找鍵Ki，m個(gè)指針Pi;如上圖。第59頁/共77頁2022-2-260第60頁/共77頁2022-2-261 第61頁/共77頁2022-2-262第62頁/共77頁2022-2-263查詢： 方法：先找第一個(gè)大于k的查找鍵值，沿其左面的指針到達(dá)下一層，以此查找下去。 特點(diǎn)：查詢的層數(shù)相同為樹的高度，因?yàn)槎际窃谌~結(jié)點(diǎn)鏈接主文件。第63頁/共77頁2022-2-26

22、4第64頁/共77頁2022-2-265不引起索引結(jié)點(diǎn)合并的刪除; 查找到主文件，刪除記錄； 若主文件中還有同查找鍵的記錄不修改索引； 若無，從葉結(jié)點(diǎn)中刪除相應(yīng)的鍵值和指針。引起分裂的插入; 插入葉結(jié)點(diǎn)后，把多出來的分裂出去；修改父結(jié)點(diǎn)，插入心結(jié)點(diǎn)中的最小值，同理其父結(jié)點(diǎn)進(jìn)行修改。 第65頁/共77頁2022-2-266 第66頁/共77頁2022-2-267引起合并的刪除 在刪除葉結(jié)點(diǎn)后，引起結(jié)點(diǎn)不符合定義，將被刪除，若父結(jié)點(diǎn)中有也將刪除，導(dǎo)致合并的發(fā)生。u B+ 樹的性能分析顯著優(yōu)點(diǎn) ： 搜索代價(jià)較小 ； 解決了數(shù)據(jù)記錄在插入，刪除和未用回收等存儲(chǔ)組織問題 。第67頁/共77頁2022-2

23、-268第68頁/共77頁2022-2-269小結(jié) 數(shù)據(jù)庫是數(shù)據(jù)的有序集合，需保留在計(jì)算機(jī)外存介質(zhì)上反復(fù)應(yīng)用。由于實(shí)際應(yīng)用系統(tǒng)數(shù)據(jù)規(guī)模都很龐大,加之經(jīng)常要從數(shù)據(jù)集合中檢索需要的數(shù)據(jù)，所以數(shù)據(jù)組織的方式，數(shù)據(jù)的定位方式，以及數(shù)據(jù)的維護(hù)策略的選取十分重要。第69頁/共77頁2022-2-270第70頁/共77頁2022-2-271小結(jié) 文件結(jié)構(gòu)有堆文件、順序文件、散列文件和聚集文件等四種。為了提高查找速度, ,可以為文件建立索引或散列機(jī)制。 索引有稠密索引、稀疏索引和多級(jí)索引等形式。索引順序文件組織的主要缺陷是隨著文件的增大, ,性能會(huì)下降。為了克服這個(gè)缺陷, ,可以使用B B、B+B+樹索引。B+B+樹索引是平衡樹, ,即從樹根到樹葉所有路徑長度相等。這種查找是簡單有效的, ,但插入和刪除比較復(fù)雜。B B樹索引和B+B+樹索引類似。第71頁/共77頁2022-2-272小結(jié) B B樹的主要優(yōu)點(diǎn)在于它去除了查找鍵值