第6章數(shù)據(jù)庫存儲結構(編輯修改稿)
2025-03-17 15:22 本頁面
【文章內容簡介】 為溢出塊。 2/1/2023 27圖圖 變長記錄的指針表示方式變長記錄的指針表示方式 2/1/2023 28圖圖 固定塊和溢出塊結構固定塊和溢出塊結構 2/1/2023 29 文件結構? 文件中記錄的組織方式有 無序?件、有序文件、聚集文件 和 HASH 文件四種。 ? 無序文件也稱為 堆文件 ．無序文件的操作比較簡單，但查找效率比較低．? 無序文件的刪除操作比較復雜，常用的方法主要有以下三種：2/1/2023 30（１）首先找到被刪記錄所在的磁盤塊，然后讀到主存緩沖區(qū)，在緩沖區(qū)中刪除記錄，最后把緩沖區(qū)內容寫回到磁盤文件．（２）在每個記錄的存儲空間增加一個標志位，標識記錄刪除與否，一般該標志常為空。刪除一個記錄時，將此記錄的標志位置 “1”, 以后查找記錄時跳過有該標志的記錄。（３）常用于定長記錄文件，刪除一個記錄時，總是把文件末尾記錄移到被刪記錄位置。 2/1/2023 31 有序文件? 有序文件是指記錄按某個（或某些）域的值的大小順序組織，一般最為常用的是按關鍵字的升序或降序排列，即每個記錄增加一個指針字段，根據(jù)主鍵的大小用指針把記錄鏈接起來。 ? 文件中每個記錄增加一個指針字段，根據(jù)查找鍵的大小用指針把記錄連接起來。2/1/2023 32圖圖 順序文件順序文件 2/1/2023 33u 有序文件操作 ? 刪除 ：只需修改指針即可。同定長記錄的方法三? 插入 ： 1）定位：找到要插的位置。按查找鍵的順序 2）插入：在找到記錄的塊內，如果自由空間有空閑紀錄，那么插入；若沒有就插入到溢出塊中。? 在初始的時候，可以保持無力順序和查找鍵的順序一致，以提高速度，若多次操作后變化很大，有必要重新組織一次。2/1/2023 34 聚集文件? 文件允許一個文件有多個關系的記錄組成，即記錄類型文件。例：可以把有關一個人的全部記錄信息放在相鄰的位置，按人查找信息時就會很方便。2/1/2023 35圖圖 插入一個記錄后的順序文件插入一個記錄后的順序文件 2/1/2023 36圖圖 聚集文件例子聚集文件例子 2/1/2023 37 HASH 文件? 哈稀 (HASH) 文件又稱為 散列文件 ，是一種支持快速存取的文件存儲方法。1．散列的概念： 設 K是所有查找鍵值的集合， B是所有桶地址的集合。散列函數(shù) h是從 K到 B的函數(shù)，它把每個查找鍵值映射到地址集合中的地址。其中每個桶的大小一定。 查找鍵集K桶地址集B主文件記錄2/1/2023 38? 檢索：? 1）檢索 Ki的記錄，首先計算 h(Ki)在 B集合中 2）根據(jù)桶地址找到桶 3）桶內查找 特點： 不同的查找鍵值的記錄可能在同一個桶內，找到桶后仍然有進行檢測。? 刪除：找到記錄直接刪除即可。2/1/2023 392．散列函數(shù) ? 要滿足兩個條件： 1）使地址分布均勻； 2）地質分布隨機。? 常用方法： 質數(shù)除余法 。? 缺點：函數(shù)的設計，若設計不好會造成很大的不均勻性，查找時間的浪費。2/1/2023 40 ? 問題 ： 由于同所存儲的記錄數(shù)是一定的，再插入操作時很容易發(fā)生溢出。? 原因 ：一是桶的數(shù)目少；二是散列的均勻性不好。? 解決： 1）溢出鏈法：每個同都作為基本桶存在， 若溢出系統(tǒng)提供一處同連接在基本桶后面。 2）開放式散列法：只存在基本桶，若溢 出就插入其他空閑的桶。有兩種選擇方式： 1。在溢出桶下面的一個空閑桶； 2。采用二次散列的方法。2/1/2023 41圖圖 散列結構的溢出鏈散列結構的溢出鏈 2/1/2023 42４ .散列方法 ? 常用的 HASH 方法有 簡單 HASH 方法，動態(tài) HASH 方法 和 可擴展的 HASH 方法 ．? 評價 ：散列方法必須選取恰當?shù)纳⒘泻瘮?shù)。2/1/2023 43 圖圖 HASH桶目錄示例桶目錄示例 2/1/2023 44 HASH 方法。 ? 該方法采用固定個數(shù)的 HASH 桶，即把文件劃分為 N 個 HASH桶，每個 HASH 桶對應一個磁盤塊，每個 HASH 桶有一編號。? 缺點： ⑴ 只能有效地支持
教學課件相關推薦
鄂ICP備17016276號-1