第6章數(shù)據(jù)庫(kù)存儲(chǔ)結(jié)構(gòu)-文庫(kù)吧在線文庫(kù)
【正文】 磁盤是目前最常用的外部存儲(chǔ)器 ,由磁性材料制成 ,數(shù)據(jù)存儲(chǔ)在磁盤表面 。 這種這種組塊方式雖然可節(jié)省空間組塊方式雖然可節(jié)省空間 ， 但實(shí)現(xiàn)比較困難但實(shí)現(xiàn)比較困難 ， 用得用得較少較少 。2/1/2023 116 快擦寫存儲(chǔ)器（快擦寫存儲(chǔ)器（ Flash Memory））?快擦寫存儲(chǔ)器又稱為快擦寫存儲(chǔ)器又稱為 “電可擦可編程只讀存儲(chǔ)器電可擦可編程只讀存儲(chǔ)器 ”，快閃存在掉電后仍能保持?jǐn)?shù)據(jù)不丟失。? 文件組織的兩種方式：定長(zhǎng)格式和變長(zhǎng)格式。 缺點(diǎn)移動(dòng)次數(shù)過(guò)多。? 變長(zhǎng)記錄的表示有 字節(jié)串形式 和 定長(zhǎng)形式 兩種。 ∧ ? “分槽式頁(yè)結(jié)構(gòu) ”：每塊的開(kāi)始設(shè)置一個(gè) “塊首部 ”，包含以下信息：塊中的記錄數(shù)目，只想塊中自由空間尾部的指針，登記每個(gè)記錄近的開(kāi)始位置和大小的信息。 ∧ ∧ ∧S004 1 85 2 60 ∧ ∧S006 3 75 （３）常用于定長(zhǎng)記錄文件，刪除一個(gè)記錄時(shí)，總是把文件末尾記錄移到被刪記錄位置。例：可以把有關(guān)一個(gè)人的全部記錄信息放在相鄰的位置，按人查找信息時(shí)就會(huì)很方便。? 常用方法： 質(zhì)數(shù)除余法 。采用二次散列的方法。 2/1/2023 46 圖圖 動(dòng)態(tài)動(dòng)態(tài) HASH方法結(jié)構(gòu)方法結(jié)構(gòu) 2/1/2023 47 HASH 方法 ? 特點(diǎn)： 按照實(shí)際需要申請(qǐng)或釋放空間。 2/1/2023 50? 刪除： 查找到 Ki的記錄，從桶內(nèi)刪除。 P0 K1 P1 K2 P2 … Km1 Pm12/1/2023 58? 一般假設(shè)，每一個(gè)索引塊能容納的索引項(xiàng)數(shù)是個(gè)奇數(shù)，且 m=2d1 ≥3。 特點(diǎn)： 查詢的層數(shù)相同為樹(shù)的高度，因?yàn)槎际窃谌~結(jié)點(diǎn)鏈接主文件。? B+ 樹(shù)的性能分析? 顯著優(yōu)點(diǎn) ： ?搜索代價(jià)較小 ； ?解決了數(shù)據(jù)記錄在插入，刪除和未用回收等存儲(chǔ)組織問(wèn)題 。2/1/2023 72小結(jié)? 文件結(jié)構(gòu)有堆文件、順序文件、散列文件和聚集文件等四種。2/1/2023 73小結(jié)? B樹(shù)的主要優(yōu)點(diǎn)在于它去除了查找鍵值存儲(chǔ)中的冗余 。? (2) 有序索引，主索引，稠密索引，稀疏索引，多級(jí)索引， B 樹(shù)， B+ 樹(shù)? ，并說(shuō)明每一種介質(zhì)的數(shù)據(jù)訪問(wèn)速度。 ② 6 階 。并作解釋。相比之下 ,基于散列的文件允許通過(guò)散列函數(shù)直接得到記錄所在的桶地址。為了克服這個(gè)缺陷 ,可以使用 B、B+樹(shù)索引。文件組織數(shù)據(jù)庫(kù)以文件形式組織。 查找到主文件，刪除記錄； 若主文件中還有同查找鍵的記錄不修改索引； 若無(wú)，從葉結(jié)點(diǎn)中刪除相應(yīng)的鍵值和指針。P1 K1 P2 ................ Pn1 Kn1Pn2/1/2023 61?葉結(jié)點(diǎn)：葉結(jié)點(diǎn)： 葉結(jié)點(diǎn)的指針指向主文件的記錄；查找鍵在 葉結(jié)點(diǎn)的指針指向主文件的記錄；查找鍵在[m1/2]——m1 之間；葉結(jié)點(diǎn)最后的指針指之間；葉結(jié)點(diǎn)最后的指針指向下一葉結(jié)點(diǎn)。 ? 對(duì)主文件中每一個(gè)查找鍵值都建立一個(gè)索引記號(hào) ? 優(yōu)點(diǎn) :查找、更新數(shù)據(jù)記錄方便 , 存取速度快? 缺點(diǎn) :索引項(xiàng)多 , 索引表大 , 空間代價(jià)大 . 2/1/2023 52 ? 只對(duì)主文件中若干查找鍵值建立一個(gè)索引記號(hào)。新申請(qǐng)的桶，就得到其中第二個(gè)指針。? 缺點(diǎn)： ⑴ 只能有效地支持 HASH 域上具有相 等比較的數(shù)據(jù)操作。? 解決： 1）溢出鏈法：每個(gè)同都作為基本桶存在， 若溢出系統(tǒng)提供一處同連接在基本桶后面。其中每個(gè)桶的大小一定。同定長(zhǎng)記錄的方法三? 插入 ： 1）定位：找到要插的位置。? 被指向的整體成為溢出塊。 2/1/2023 25 例如圖 的字節(jié)串表示形式可以用圖 的預(yù)留空間技術(shù)實(shí)現(xiàn)。S002 2 85 2/1/2023 21Snum Cnum ScoreCnum ScoreCnum Score2/1/2023 183. 把刪除的結(jié)點(diǎn)用指針鏈接起來(lái)? 首先，文件增設(shè) “文件首部 ”，其中有一個(gè)指針指向第一個(gè)被刪除的記錄位置，所有被刪除記錄的位置都用指針鏈接起來(lái)，構(gòu)成 “空閑記錄鏈表 ”。 圖 定長(zhǎng)記錄的文件 2/1/2023 15圖圖 刪除記錄刪除記錄 2， 5， 7后的文件結(jié)構(gòu)后的文件結(jié)構(gòu) 2/1/2023 16? 如上圖每條記錄包含姓名、學(xué)號(hào)、班級(jí)三條信息。而且不能直接重寫，必須先擦去整組存儲(chǔ)器的內(nèi)存，然后再直接重寫，必須先擦去整組存儲(chǔ)器的內(nèi)存，然后再寫數(shù)據(jù)進(jìn)去。? 主要用于數(shù)據(jù)備份或
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1