第6章數(shù)據(jù)庫存儲結(jié)構(gòu)(參考版)
2025-03-01 15:22本頁面
【正文】 ③ 8 階。就下面三種情況建立三棵 B+ 樹 :? ① 4 階 。? 7. 設查找鍵值集為 {2,3,5,7,11,17,19,23,29,31}。 2/1/2023 77習題? 5. 在散列文件組織中，是什么原因引起桶溢出的 ? 有什么辦法能減少桶溢出的次數(shù) ?? 6. 試舉一個數(shù)據(jù)庫應用例子，說明在表達變長記錄時，有時指針形式比預留空間方法好。2/1/2023 76習題? 3. 比較有序文件和無序文件的優(yōu)缺點，什么情況下應該使用有序文件，什么情況下應該使用無序文件。2/1/2023 75習題1. 解釋下列術語 :? (1) 文件，記錄，定長記錄文件，變長記錄文件，跨塊記錄，非跨塊記錄。靜態(tài)散列所用的桶地址集合是固定的 ,不容易適應數(shù)據(jù)庫數(shù)據(jù)量的快速增長。2/1/2023 74小結(jié)? 順序文件需要一個索引結(jié)構(gòu)來定位數(shù)據(jù)。主要缺陷在于整體的復雜性以及結(jié)點大小給定時減少了扇出。 B樹索引和 B+樹索引類似。 B+樹索引是平衡樹 ,即從樹根到樹葉所有路徑長度相等。索引順序文件組織的主要缺陷是隨著文件的增大 ,性能會下降。為了提高查找速度 ,可以為文件建立索引或散列機制。實現(xiàn)變長記錄的技長記錄的技 術術 有多種有多種 ,包括分槽式頁結(jié)構(gòu)、指針方包括分槽式頁結(jié)構(gòu)、指針方法和保留空間等方法法和保留空間等方法 。文件組織有兩種方法有兩種方法 ：： 一種是把記錄設計成定長格式一種是把記錄設計成定長格式 ,也就也就是每個文件只存儲某一確定長度的記錄是每個文件只存儲某一確定長度的記錄 ；； 另一種另一種是變長格式是變長格式 ,使之能存放不同長度的記錄。2/1/2023 71? 在磁盤中在磁盤中 ,數(shù)據(jù)庫以文件形式組織。2/1/2023 69圖圖 在圖在圖 中刪除主碼值為中刪除主碼值為 26的數(shù)據(jù)記錄后的Ｂ＋樹的數(shù)據(jù)記錄后的Ｂ＋樹 2/1/2023 70小結(jié)? 數(shù)據(jù)庫是數(shù)據(jù)的有序集合，需保留在計算機外存介質(zhì)上反復應用。 2/1/2023 67 圖 圖 在圖在圖 41數(shù)據(jù)記錄后的Ｂ＋樹數(shù)據(jù)記錄后的Ｂ＋樹 2/1/2023 68? 引起合并的刪除 在刪除葉結(jié)點后，引起結(jié)點不符合定義，將被刪除，若父結(jié)點中有也將刪除，導致合并的發(fā)生。? 引起分裂的插入 。2/1/2023 66? 不引起索引結(jié)點合并的刪除 。2/1/2023 652．修改操作：．修改操作：?不引起索引結(jié)點分裂的插入不引起索引結(jié)點分裂的插入 若以在葉結(jié)點出現(xiàn)，直接插入記錄；若以在葉結(jié)點出現(xiàn)，直接插入記錄； 否則，找到第一個大于的查找鍵值，在其否則，找到第一個大于的查找鍵值，在其前面插入，其后的都向后移。 2/1/2023 62圖圖 20 B+樹的模型樹的模型 2/1/2023 63 圖圖 圖圖 ＋樹中的Ｂ樹的Ｂ＋樹2/1/2023 64? 查詢： 方法： 先找第一個大于 k的查找鍵值，沿其左面的指針到達下一層，以此查找下去。向下一葉結(jié)點。如上圖。 每一個記錄索引塊能容納的記錄索引項也是個奇數(shù) ， 且n=2e1≥3。其格式為 : ? 葉結(jié)點上不包含數(shù)據(jù)記錄本身，而是由記錄索引項組成的記錄索引塊，每個記錄索引 項包含有主碼值和地址指針。? 在插入操作較多的應用中采用稀疏索引方式是不太適宜的。 線性索引? 線性索引可分為 稠密索引 和 稀疏索引 兩種。刪除后如桶為空，桶也刪除，還有可能引起桶地址的收縮。申請新的桶空間，原來的桶分出后一半指針指向新的桶，從新分配分裂的桶中的記錄。情況二： 指向這個桶有多個指針。增加 i的值，桶地址表加倍，每一項之分列成相鄰的兩項，但是指向同一個桶。? 查找： 求出 h(Ki)前 i位值 m,沿桶地指表位置 m處的指針到達某個同中去找記錄。? HASH 桶的數(shù)量不是固定的，而是隨文件記錄的變化而增加或減少的。 ⑵ 由于 HASH 桶的數(shù)量一成不變，當 文件記錄較少時 ，影響記錄的存取效率。 ? 該方法采用固定個數(shù)的 HASH 桶，即把文件劃分為 N 個 HASH桶，每個 HASH 桶對應一個磁盤塊，每個 HASH 桶有一編號。2/1/2023 41圖圖 散列結(jié)構(gòu)的溢出鏈散列結(jié)構(gòu)的溢出鏈 2/1/2023 42４ .散列方法 ? 常用的 HASH 方法有 簡單 HASH 方法，動態(tài) HASH 方法 和 可擴展的 HASH 方法 ．? 評價 ：散列方法必須選取恰當?shù)纳⒘泻瘮?shù)。在溢出桶下面的一個空閑桶； 2。
教學課件相關推薦
鄂ICP備17016276號-1