第6章數(shù)據(jù)庫(kù)存儲(chǔ)結(jié)構(gòu)-資料下載頁
2025-02-27 15:22本頁面
【正文】 高度，因?yàn)槎际窃谌~結(jié)點(diǎn)鏈接主文件。2/1/2023 652．修改操作：．修改操作：?不引起索引結(jié)點(diǎn)分裂的插入不引起索引結(jié)點(diǎn)分裂的插入 若以在葉結(jié)點(diǎn)出現(xiàn)，直接插入記錄；若以在葉結(jié)點(diǎn)出現(xiàn)，直接插入記錄； 否則，找到第一個(gè)大于的查找鍵值，在其否則，找到第一個(gè)大于的查找鍵值，在其前面插入，其后的都向后移。前面插入，其后的都向后移。2/1/2023 66? 不引起索引結(jié)點(diǎn)合并的刪除 。 查找到主文件，刪除記錄； 若主文件中還有同查找鍵的記錄不修改索引； 若無，從葉結(jié)點(diǎn)中刪除相應(yīng)的鍵值和指針。? 引起分裂的插入 。 插入葉結(jié)點(diǎn)后，把多出來的分裂出去；修改父結(jié)點(diǎn)，插入心結(jié)點(diǎn)中的最小值，同理其父結(jié)點(diǎn)進(jìn)行修改。 2/1/2023 67 圖 圖 在圖在圖 41數(shù)據(jù)記錄后的Ｂ＋樹數(shù)據(jù)記錄后的Ｂ＋樹 2/1/2023 68? 引起合并的刪除 在刪除葉結(jié)點(diǎn)后，引起結(jié)點(diǎn)不符合定義，將被刪除，若父結(jié)點(diǎn)中有也將刪除，導(dǎo)致合并的發(fā)生。? B+ 樹的性能分析? 顯著優(yōu)點(diǎn) ： ?搜索代價(jià)較小 ； ?解決了數(shù)據(jù)記錄在插入，刪除和未用回收等存儲(chǔ)組織問題 。2/1/2023 69圖圖 在圖在圖 中刪除主碼值為中刪除主碼值為 26的數(shù)據(jù)記錄后的Ｂ＋樹的數(shù)據(jù)記錄后的Ｂ＋樹 2/1/2023 70小結(jié)? 數(shù)據(jù)庫(kù)是數(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ù)策略的選取十分重要。2/1/2023 71? 在磁盤中在磁盤中 ,數(shù)據(jù)庫(kù)以文件形式組織。文件組織數(shù)據(jù)庫(kù)以文件形式組織。文件組織有兩種方法有兩種方法 ：： 一種是把記錄設(shè)計(jì)成定長(zhǎng)格式一種是把記錄設(shè)計(jì)成定長(zhǎng)格式 ,也就也就是每個(gè)文件只存儲(chǔ)某一確定長(zhǎng)度的記錄是每個(gè)文件只存儲(chǔ)某一確定長(zhǎng)度的記錄 ；； 另一種另一種是變長(zhǎng)格式是變長(zhǎng)格式 ,使之能存放不同長(zhǎng)度的記錄。實(shí)現(xiàn)變使之能存放不同長(zhǎng)度的記錄。實(shí)現(xiàn)變長(zhǎng)記錄的技長(zhǎng)記錄的技 術(shù)術(shù) 有多種有多種 ,包括分槽式頁結(jié)構(gòu)、指針方包括分槽式頁結(jié)構(gòu)、指針方法和保留空間等方法法和保留空間等方法 。2/1/2023 72小結(jié)? 文件結(jié)構(gòu)有堆文件、順序文件、散列文件和聚集文件等四種。為了提高查找速度 ,可以為文件建立索引或散列機(jī)制。? 索引有稠密索引、稀疏索引和多級(jí)索引等形式。索引順序文件組織的主要缺陷是隨著文件的增大 ,性能會(huì)下降。為了克服這個(gè)缺陷 ,可以使用 B、B+樹索引。 B+樹索引是平衡樹 ,即從樹根到樹葉所有路徑長(zhǎng)度相等。這種查找是簡(jiǎn)單有效的 ,但插入和刪除比較復(fù)雜。 B樹索引和 B+樹索引類似。2/1/2023 73小結(jié)? B樹的主要優(yōu)點(diǎn)在于它去除了查找鍵值存儲(chǔ)中的冗余 。主要缺陷在于整體的復(fù)雜性以及結(jié)點(diǎn)大小給定時(shí)減少了扇出。實(shí)際應(yīng)用中 ,人們總是更愿意使用 B+樹索引。2/1/2023 74小結(jié)? 順序文件需要一個(gè)索引結(jié)構(gòu)來定位數(shù)據(jù)。相比之下 ,基于散列的文件允許通過散列函數(shù)直接得到記錄所在的桶地址。靜態(tài)散列所用的桶地址集合是固定的 ,不容易適應(yīng)數(shù)據(jù)庫(kù)數(shù)據(jù)量的快速增長(zhǎng)。可擴(kuò)充散列結(jié)構(gòu)是一種允許修改散列函數(shù)的動(dòng)態(tài)散列技術(shù) ,在數(shù)據(jù)庫(kù)增加或縮減時(shí)它可以通過分裂或合并桶來適應(yīng)數(shù)據(jù)庫(kù)大小的變化。2/1/2023 75習(xí)題1. 解釋下列術(shù)語 :? (1) 文件，記錄，定長(zhǎng)記錄文件，變長(zhǎng)記錄文件，跨塊記錄，非跨塊記錄。? (2) 有序索引，主索引，稠密索引，稀疏索引，多級(jí)索引， B 樹， B+ 樹? ，并說明每一種介質(zhì)的數(shù)據(jù)訪問速度。2/1/2023 76習(xí)題? 3. 比較有序文件和無序文件的優(yōu)缺點(diǎn)，什么情況下應(yīng)該使用有序文件，什么情況下應(yīng)該使用無序文件。? 4. 回答下列問題 :? (1)HASH 文件的桶溢出問題是什么 ? 如何解決 ?? (2) 簡(jiǎn)單 HASH 文件、動(dòng)態(tài) HASH 文件和可擴(kuò)展 HASH 文件之間有什么不同。 2/1/2023 77習(xí)題? 5. 在散列文件組織中，是什么原因引起桶溢出的 ? 有什么辦法能減少桶溢出的次數(shù) ?? 6. 試舉一個(gè)數(shù)據(jù)庫(kù)應(yīng)用例子，說明在表達(dá)變長(zhǎng)記錄時(shí)，有時(shí)指針形式比預(yù)留空間方法好。并作解釋。? 7. 設(shè)查找鍵值集為 {2,3,5,7,11,17,19,23,29,31}。假設(shè)初始時(shí) B+ 樹為空，按升序次序插入鍵值。就下面三種情況建立三棵 B+ 樹 :? ① 4 階 。 ② 6 階 。 ③ 8 階。2/1/2023 7
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1