6.1 文件組織

　　6.1.1 數據庫的物理結構

　　1、 數據庫中的應用數據是以文件形式存儲在外存上的，文件在邏輯上被組織成記錄的序列，即每個DB文件可看作是邏輯記錄的集合;

　　2、 一個文件在磁盤上占有一定的物理存儲空間，文件中的每個邏輯記錄被映射存儲到某個特定的磁盤塊上，一個文件在物理上可以看作是由存放文件記錄的一系列磁盤塊組成，稱為物理文件;

　　3、 文件的邏輯記錄與磁盤間的映射關系是由操作系統(tǒng)或DBMS來管理的，當需要對一個文件的邏輯記錄進行操作時，先要根據這種映射關系找到該邏輯記錄所在的磁盤塊，然后再進行操作。

　　4、 從數據庫物理結構角度需要解決如下問題：

　　(1) 文件的組織;

　　(2) 文件的結構;

　　(3) 文件的存取;

　　(4) 索引技術;

　　6.1.2 文件組織

　　1、 數據庫與文件的對應關系

　　(1) 在外存中，數據庫以文件形式組織，文件由邏輯記錄組成，記錄由多個域組成;

　　(2) 一個關系數據庫包括一張或多張關系表，關系表與文件的對應關系有如下方式：

　　(A) 每張關系表單獨用一個文件來存儲，由DBMS通過OS的文件管理功能來管理;

　　(B) 現代中大型DBMS是由OS直接分配一塊大的磁盤空間，DBMS將該磁盤空間作為數據庫磁盤文件直接管理，DB的所有關系表都存儲在該文件中;

　　(1) 關系表在邏輯上由一系列元組組成，元組由多個屬性組成，每個元組可以用磁盤文件中的一個邏輯記錄來存儲，記錄包括多個域，對應元組的多個屬性;

　　2、文件記錄格式：

　　(1) 數據庫文件通常采用兩種邏輯記錄格式：定長記錄格式和變長記錄格式;

　　6.2 文件結構與存取

　　6.2.1 堆文件

　　1、 堆文件也稱無序文件，記錄隨機在存儲在文件物理空間是，新插入的記錄存儲在文件的末尾;

　　2、 堆文件常常用作存儲那些將來使用，但目前不清楚如何使用的記錄，為了實現文件記錄的有效存取，堆文件經常與附加的存取路徑一起使用;

　　3、 查找操行平均需要搜索(B+1)/2個磁盤塊，效率比較低;

　　4、 插入操作十分簡單，先讀文件頭，找到最末磁盤地址，將最末磁盤塊讀入內存，將需插入的新記錄寫入磁盤塊的末端，最后將修改過的磁盤塊寫回磁盤;

　　5、 刪除比較復雜，可以先找到被刪除記錄所在的磁盤塊，讀入內存后在內存緩沖區(qū)刪除記錄，最后再寫回磁盤;也可以在每個記錄的磁盤空間增加一個刪除標志位，當需要刪除記錄時，將標示位置1;

　　6.2.2 順序文件

　　1、 順序文件按照文件記錄在查詢碼上的取值的大小順序排列各個記錄;

　　2、 順序文件的每個記錄中有一個指針字段，根據查詢碼大小用指針將各個記錄按序連接起來;

　　3、 文件建立時，應盡量使記錄的物理順序與查找碼的順序一致，以減少訪問磁盤塊的次數;

　　4、 根據查詢條件對順序文件進行查詢時，如查詢條件定義在查找碼上，則使用二分法查找技術快速找到記錄，如條件不在查找碼上，則必須從頭到尾依次掃描磁盤塊，與堆文件一致，所以順序文件的訪問效率也不高;

　　5、 順序文件插入工作包括定位和插入：

　　(1) 定位：在指針鏈中找到插入的位置，即插入記錄在哪個記錄的前面;

　　(2) 插入：如有自由空間，則在該位置插入新記錄，如沒有自由空間，則只能插入溢出塊中，重新調整記錄指針鏈關系，保證記錄順序;

　　6.2.3 聚集文件

　　1、 聚集文件是一種具有多種記錄類型文件，存儲了來自多個關系表的數據，每個關系表對應文件中的一種記錄類型;

　　2、 當數據庫中數據量效大時，對數據庫查詢需要多次訪問磁盤文件，嚴重影響性能指標，為了降低多表操作時的磁盤訪問次數，提高多表查詢速度，可采用聚集文件;

　　3、 聚集文件將不同關系表中有關聯關系的記錄存儲在同一磁盤塊內，從而減少多表查詢時磁盤塊的訪問次數，提高處理速度;

　　6.2.4 索引文件

　　是一種利用索引技術技術快速文件訪問的文件組織和存取方法;

　　6.2.4 散列文件

　　是一種利用散列函數支持快速文件訪問的文件組織和存取方法;

　　6.3 索引技術

　　6.3.1 基本概念

　　1、 索引技術：是一種快速文件訪問技術，它將一個文件的每個記錄在某個或某些域(屬性)上的取值與該記錄的物理地址直接聯系起來，提供了一種根據記錄域的取值快速訪問文件記錄的機制;它的關鍵是建立取值域到記錄的物理地址劉的映射關系，這種映射關系叫索引;

　　2、 索引技術分類：

　　(1) 有序索引技術：利用索引文件實現記錄域(查找碼)取值到記錄物理地址間的映射關系，索引文件由索引記錄組成，每個記錄中記載一個索引項，索引項記錄了某個特定的查找碼值和具有該值的數據文件記錄的物理地址;

　　(2) 散列技術：利用一個散列函數實現記錄域取值到記錄物理地址間的直接映射關系;

　　(3) 有序索引：有序索引作為基于索引文件的索引技術，需要考慮兩個問題：(1)如何組織索引文件中的索引記錄;(2)如何從索引文件出發(fā)，訪問數據文件中的數據記錄;

　　(A) 當需要采用有序索引機制快速訪問數據文件時，首先要為該數據文件建立一個索引文件，它是索引記錄和索引項的集合;

　　(B) 索引文件建立的方法：首先選定某些記錄域作為查找碼，然后建立數據記錄在查找碼上的取值與物理地址間的映射關系，組成索引項。所有索引項作為索引記錄存儲在索引文件中，索引文件根據某個特定的查找碼值的順序組織為順序文件;

　　(C) 一個數據文件可以有多個查找碼和索引文件;

　　6.3.2 有序索引的分類及特點

　　1、 聚集索引與非聚集索引

　　(1) 對數據文件和它的一個特定的索引文件，如果數據文件中數據記錄的排列順序與索引文件中索引項的排列順序相一致，則該索引文件稱為聚集索引，否則稱為非聚集索引;

　　(2) 在一個數據文件上除了建立一個聚集索引外，還可建立多個非聚集索引;

　　2、 稠密索引和稀疏索引

　　如果數據文件中的每個查找碼都在索引文件中都對應一個索引記錄，稱為稠密索引，如果只一部分對應，則稱為稀疏索引;

　　3、 主索引和輔索引

　　在數據文件包含主碼的屬性集上建立索引稱為主索引，在非主碼屬性上建立的索引稱為輔索引;

　　4、單層索引和多層索引

　　(1) 單層索引(線性索引)：索引項根據鍵值在索引文件中順序排列，組織成一維線性結構，每個索引項直接指向數據文件中的數據記錄;

　　(2) 當數據文件很大時，即使采用稀疏索引，建成的索引文件也很大，導致效率低下，為解決該問題，可對索引文件中的索引項本身再建立一級稀疏索引，組成2層索引結構;進一步地，可建立多層樹型索引結構來快速定位;

　　6.4 散列技術

　　6.4.1 散列文件

　　1、 散列是一種快速查找技術，它利用定義在文件記錄上的查找碼，通過計算一個散列函數，以散列函數值作為記錄的物理地址，實現對文件記錄直接快速訪問。

　　2、 首先指定文件記錄的一個域作為查找碼(散列域)，然后定義一個查找碼上的函數(散列函數)，函數的輸入為查找碼值，輸出為物理地址;

　　3、 一般使用桶作為基本的存儲單位，一個桶可存放多個文件記錄，物理地址可以是記錄所在的桶號，散列函數的輸出可以是桶號;

　　6.4.2 散列函數

　　1、 散列方法依賴于好的散列函數，它應該盡可能均勻地將查找碼分布到各個桶中，具體要滿足如下兩個條件：

　　(1) 地址的分布是均勻的;

　　(2) 地址的分布是隨機的;

　　6.4.3 桶溢出

　　1、 產生桶溢出的兩個原因：

　　(1) 文件初始設計時，為文件記錄預留的存儲空間不足;

　　(2) 散列函數的均勻分布性不好;

　　2、 設計散列函數時，應根據文件大小決定物理空間，一般應有20%余量，再設計合適的桶數目和桶大小，盡可能留有一些空閑桶，降低桶溢出的可能性;

　　3、 桶溢出的現象是難免的，需要DBS采用相應的桶溢出處理機制;

　　4、 散列方法的缺點：為了避免桶溢出。必須選一合適的散列函數，但這比較復雜，而且不象索引文件那樣可以據數據記錄變化動態(tài)調整。

　　6.5 數據字典

　　1、 數據字典(系統(tǒng)目錄)中存儲了數據庫對象的各類描述信息和DBMS所需的控制信息，全稱數據庫元數據;

　　2、 數據庫對象的各類描述信息：包括外模式、模式、內模式以及它們之間的映射的描述;

　　3、 DBMS所需的控制信息：包括查詢優(yōu)化、安全性檢查、用戶權限驗證等;

　　4、 數據字典主要包括：

　　(1) 關系模式信息;

　　(2) 與視圖描述有關的信息;

　　(3) 關系的存儲結構和存取方法信息;

　　(4) 完整性約束信息;

　　(5) 安全性有關信息;

　　(6) 數據庫運行統(tǒng)計信息;

　　6.6 數據庫物理設計

　　6.6.1 設計步驟和內容

　　1、 數據庫物理結構設計：在具體的硬件環(huán)境、OS、DBMS約束下，根據數據庫邏輯設計結果，設計合適的數據庫物理結構。目標是存儲空間占用少、訪問效率高和維護代價低;

　　2、 一旦選定了硬件平臺、OS和DBMS，數據庫的數據存儲和存取方式等可用的物理模式也就隨之確定了;

　　3、 數據庫物理設計主要包括以下步驟：

　　(1) 數據庫邏輯模式調整：將數據庫邏輯模式及其視圖轉換為DBMS支持的基本表和視圖，并利用DBMS提供的完整性機制設計業(yè)務規(guī)則;

　　(2) 文件組織與存取設計：配置基本表的文件組織形式，據實際情況為基本表設計合適的存取方法和路徑;

　　(3) 數據分布設計：

　　(4) 安全模式設計：

　　(5) 確定系統(tǒng)配置：

　　(6) 物理模式評估：

　　6.6.2 數據庫邏輯模式調整

　　1、 物理數據庫設計首先需要根據數據庫邏輯結構信息，設計目標DBMS平臺支持的基本表的模式信息，這些模式信息代表了所要開發(fā)的具體目標數據庫的結構，這個過程稱為數據庫邏輯模式調整，主要包括如下設計內容：

　　(1) 實現目標數據庫基本表和視圖：采用目標DBMS所支持的建表方法，設計基本表及其面向模型的完整性約束;

　　(2) 設計基本表業(yè)務規(guī)則;

　　6.6.3 DB文件組織與存取設計

　　1、分析事務的數據訪問特性

　　(1) 使用事務-基本表交叉引用矩陣，分析系統(tǒng)內數據庫事務對各個基本表的訪問情況，確定事務訪問了哪些基本表，對這些基本表執(zhí)行了何種操作，并進一步分析各操作涉及到的基本表屬性;

　　(2) 估計各事務的執(zhí)行頻率;

　　(3) 對每張基本表，匯總所有作用于該表上的各事務的操作頻率信息;

　　2、 了解并選擇數據庫文件結構

　　(1) 如果數據庫中的一個基本表中的數據量很少，并且操作非常頻繁，該基本表可采用堆文件組織方式;

　　(2) 順序文件支持基于查找碼的順序訪問，也支持快速二分查找;

　　(3) 如果用戶查詢是基于散列域值的等值匹配，特別是如果訪問順序是隨機的，散列文件比較合適。但散列文件組織不適合以下情況：

　　(A) 基于散列值域的非精確查詢;

　　(B) 基于非散列域進行查詢時;

　　(4) B-樹和B+樹文件是實際數據庫系統(tǒng)中使用非常廣泛的索引文件結構，適合于定義在大數據量基本表上、基于查找碼的等值查詢等;

　　(5) 如果某此重要而頻繁的用戶查詢經常需要進行多表連接操作，可考慮將這些基本表組織為聚集文件;

　　3、 設計存取路徑：

　　(1) 為數據庫文件設計合理的物理存儲位置;

　　(2) 為基本表設計索引機制：索引可以提高文件存取速度，改善訪問性能，但索引由DBMS管理，它的建立、維護需要一定的系統(tǒng)開銷，數據的操作會引起索引的重新調整，還占用一定的存儲空間，可根據如下原則決定是否為一個基本表建立索引：

　　(A) 對于經常需要查詢、連接、統(tǒng)計操作，且數據量大的基本表可考慮建立索引，而對于經常執(zhí)行插入、刪除、更新操作或小數據量的基本表應盡量不建立索引;

　　(B) 一個基本表上除了可以建立一個聚集索引外，還可以建立多個非聚集索引，但索引越多，對表內數據更新所需的開銷越大，對于一個更新頻繁的表應少建或不建索引;

　　(C) 索引可以由用戶根據需要隨時創(chuàng)建或刪除，以提高數據查詢性能;

　　6.6.4 數據分布設計

　　1、不同類型數據的物理分布

　　(1) 各種數據在系統(tǒng)中的作用不同，使用的頻率也不一樣，應根據實際使用情況放在合適的物理介質上;

　　(2) 使用頻率低但數據量大的，可以放在磁帶中，而使用頻繁，要求響應時間短的，必須放在支持直接存取的磁盤存儲介質上;

　　2、 應用數據的劃分和分布

　　(1) 根據數據的使用特征劃分：可將基本表劃分為頻繁使用分區(qū)和非頻繁使用分區(qū)，分別存放在不同的磁盤上，對前者可考慮建立B+樹等多層索引，而后者不建立或只建立單層索引;

　　(2) 根據時間、地點劃分;

　　(3) 分布式數據庫系統(tǒng)中的數據劃分：

　　3、派生屬性數據分布

　　(1) 派生屬性指該屬性的取值可根據表中其他屬性的取值惟一確定;

　　(2) 對帶有派生屬性的基本表可采用兩種實現方式：

　　(A) 將派生屬性作為基本表內單獨一列，稱為派生列;

　　(B) 派生屬性不出現在基本表中;

　　4、 關系模式的去規(guī)范化

　　(1) 在數據庫物理設計階段，可以對考慮數據庫中某些3NF、BCNF模式是否可以降低其規(guī)范化程度，以提高查詢效率，這稱為關系模式的去規(guī)范化處理，但不滿足3NF的關系模式又可能導致數據庫訪問異常，因此，設計基本表時，需在規(guī)范化和查詢效率間權衡;

　　6.6.5 安全模式設計

　　1、系統(tǒng)安全設計

　　(1) 是指為數據庫服務器合法用戶分配用戶名和口令，使其能夠正常登錄服務器訪問所需的數據，還可采用基于CA認證的系統(tǒng)安全控制機制;

　　1、 數據安全設計

　　(1) 是指通過數據庫系統(tǒng)視圖機制和授權機制為用戶對數據庫對象訪問的權限;

　　(2) 引用數據視圖機制，只給用戶需求的那部分數據訪問權限，防止由合法用戶造成信息泄密，另外數據視圖還可以防止基本表發(fā)生改變時，影響用戶的訪問;

　　(3) 權限是允許用戶對一給定的數據庫對象可執(zhí)行的操作;

　　(4) 數據庫安全設計需要根據用戶需求，采用授權機制，為用戶分配合法訪問的權限;

　　6.6.6 確定系統(tǒng)配置

　　1、 要根據實際應用系統(tǒng)的運行情況配置系統(tǒng)參數;

　　6.6.7 物理模式評估

　　1、 在設計過程中，通過對時間效率、空間效率、維護代價和用戶要求權衡考慮，擇優(yōu)采用;

　　2、 評估物理數據庫的方法完全依賴所選用的DBMS，主要從定量估算各方案的存儲空間、存取時間和維護代價入手;