本章介紹的是存儲在 外存上的數據結構 (文件)的有關概念各種文件的特點組織方法及查詢和更新操作我們只要對它們有一些了解就可以了本章不是重點
一文件的基本概念( 識記 )
對數據結構來說 文件 是性質相同的 記錄 的集合(這不同於我們說的操作系統中的文件概念)
與文件有關的概念還有 記錄 是文件中存取的 基本單位 數據項 是文件可使用的 最小單位 數據項有時稱 字段 或者 屬性 主關鍵字項 (唯一標識一個記錄的字段) 次關鍵字項 主關鍵字 次關鍵字 單關鍵字文件 多關鍵字文件 等
文件的 邏輯結構 是一種 線性結構
文件上的操作主要有兩類 檢索和維護 並有 實時 和 批量處理 兩種處理方式
文件的存儲結構是指文件在外存上的組織方式 基本 的 組織方式 有 順序組織 索引組織 散列組織和鏈組織 文件組織的各種方式往往是這四種基本方式的結合
常用的 文件組織方式 順序文件 索引文件 散列文件和多關鍵字文件
評價一個文件組織的 效率 是執行文件操作所花費的 時間 和文件組織所需的 存儲空間 通常文件組織的主要目的是為了能高效方便地對文件進行操作而 檢索功能的多寡和速度的快慢 是衡量文件操作 質量 的 重要標志
二順序文件( 識記 )
順序文件 是指按記錄進入文件的先後順序存放其邏輯順序和物理順序一致的文件
一切存儲在順序存儲器(如磁帶)上的文件都只能順序文件 這種順序文件只能按順序查找法存取(注意沒有折半法了)
存儲在 直接存取存儲器(如磁盤) 上的順序文件可以順序查找法存取也可以用分塊查找法或二分查找法存取
順序文件多用於磁帶
三索引文件( 識記 )
索引文件的組織方式通常是在文件本身(主文件)之外另外建立一張表它指明邏輯記錄和物理記錄之間一一對應的關系這張表就叫做 索引表 它和主文件 一起 構成 索引文件
索引非順序文件中的索引表為 稠密索引 索引順序文件中的索引表為 稀疏索引
若記錄很大使得索引表也很大時可對索引表再建立索引稱為 查找表 通常可達四級索引
四索引順序文件( 識記 )
索引順序文件是最常用的文件組織 因為索引順序文件的主文件也是有序的所以它既適合於隨機存取也適合於順序存取另一方面索引非順序文件的索引是稠密索引而索引順序文件的稀疏索引占用空間較少因此索引順序文件是最常用的一種文件組織
索引順序文件 常用的有兩種 ISAM 文件和 VSAM 文件
五散列文件( 識記 )
散列文件是利用散列存儲方式組織的文件亦稱為直接存取文件
它類似於散列表即根據文件中關鍵字的特點設計一個散列函數和處理沖突的方法將記錄散列到存儲設備上與散列表不同的是對於文件來說記錄通常是成組存放的若干個記錄組成一個存儲單位稱為桶 對散列而言處理沖突的方法主要采用拉鏈法
散列文件的優點是:文件隨機存放記錄不需要排序;插入刪除方便;存取速度快;不需要索引區節省存儲空間缺點是不能進行順序存取只能按關鍵字隨機存取且詢問方式限地簡單詢問需要重新組織文件
六多關鍵字文件( 識記 )
對被查詢的次關鍵字也建立相應的索引則這種 包含有多個次關鍵字索引的文件稱為 多關鍵字文件
兩種多關鍵字文件的組織方法 多重表文件 和 倒排表
一般的文件組織中是先找記錄然後再找到該記錄所含的各次關鍵字;而倒排文件是先給定次關鍵字然後查找含有該次關鍵字的各個記錄因此稱為倒排
第十章 文件 復習要點
本章在試卷中所占比例不多一般占%左右考試內容多為基本概念
文件的概念要注意這裡的文件不是指操作系統意義上的文件而是指導數據庫意義上的文件這樣的文件指的是帶有結構的記錄集合
明確記錄是文件中存取的基本單位數據項(字段)是文件可使用的最小單位主關鍵字項和次關鍵字項的含義關鍵字的含義
文件上的操作主要有兩類檢索和維護
文件的基本組織方式(存儲結構)有四種順序組織索引組織散列組織和鏈組織相應的文件有順序文件索引文件散列文件和多關鍵字文件
評價一個文件組織的效率是執行文件操作所花費的時間和文件組織所需的存儲空間而檢索功能的多寡和速度的快慢是衡量文件操作質量的重要標志
磁帶只適用於存儲順序文件而磁盤則適用於存儲各種文件
一切存儲在順序存取存儲器(如磁帶)上的文件只能是順序文件只能按順序查找法查找而存儲在直接存儲存儲器(如磁盤)上的順序文件則可以用順序查找法存取也可以用分塊法或二分法進行存取
什麼是索引文件?
索引表的索引稱為查找表最高可達四級
B+樹與B樹的差異是什麼?
散列文件亦稱為直接存取文件根據文件中關鍵字的特點設計一個散列函數和處理沖突的方法將記錄散列到存儲設備上散列文件中的存儲單位叫做桶
From:http://tw.wingwit.com/Article/program/sjjg/201311/23685.html
