檔案組織 國立聯合大學資訊管理學系陳士杰老師
Outlines 資料儲存格式 檔案組織 講義 :Ch. 3 原文 :Ch. 13 國立聯合大學資訊管理學系資料庫系統課程 ( 陳士杰 ) 2
資料儲存格式 資料庫儲存資料的階層 : 字元 (Character): 為資料庫中資料表示的最小單位 欄位 (Field): 又稱屬性 (Attribute) 欄(Column), 用來描述個體的某一個屬性 記錄 (Record): 又稱值組 (Tuple) 列(Row), 由多個欄位組成, 用以描述一個個體 關聯 (Relation): 又稱表格 (Table), 為相關記錄的集合 資料庫 (Database): 電腦化的記錄儲存軟體系統, 為相關關聯的集合, 透過資料庫管理系統 (DBMS) 來管理 國立聯合大學資訊管理學系資料庫系統課程 ( 陳士杰 ) 3
例 : 員工關聯表格 國立聯合大學資訊管理學系資料庫系統課程 ( 陳士杰 ) 4
磁碟儲存資料的階層 : 位元 (Bit): 電腦儲存資料的最小單位, 以二進位表示 位元組 (Byte):1 byte = 8bits, 為一般電腦從事資料處理的最小單位 區塊 (Block): 磁碟與記憶體間儲存與傳送資料的單位 磁碟與記憶體的儲存空間皆可切割成許多區塊 若資料記錄的大小較區塊小, 則每個區塊可以容納數筆記錄 國立聯合大學資訊管理學系資料庫系統課程 ( 陳士杰 ) 5
記錄儲存的方法 固定長度 (Fixed Length) 在一個 Block 中, 每一筆記錄長度皆相同 可變長度 (Variable Length) 在一個 Block 中, 每一筆記錄長度不完全相同 不可分割 (Unspanned) 一筆記錄於儲存時, 不允許被分割與跨越區塊邊界 可分割 (Spanned) 一筆記錄於儲存時, 允許被分割與跨越區塊邊界 做法 : 在前一區塊結尾處, 以指標指向記錄其餘部份之區塊 國立聯合大學資訊管理學系資料庫系統課程 ( 陳士杰 ) 6
國立聯合大學資訊管理學系資料庫系統課程 ( 陳士杰 ) 7
Fixed Length 與 Unspanned: 優點 : 容易維護與管理, 存取效率佳 缺點 : 浪費空間 Variable Length 與 Spanned: 優點 : 節省空間 缺點 : 不易維護與管理, 存取效率差 實務上, 目前的 Relational DB 較偏好 Fixed Length 與 Unspanned 國立聯合大學資訊管理學系資料庫系統課程 ( 陳士杰 ) 8
可變長度的使用時機 : 欄位長度大 內容值變化大 空間較時間珍貴 國立聯合大學資訊管理學系資料庫系統課程 ( 陳士杰 ) 9
檔案組織 以檔案資料的存取方式, 區分成以下三種 : 循序檔 (Sequential File) 雜湊檔 (Hashing File) 索引檔 (Index File) 國立聯合大學資訊管理學系資料庫系統課程 ( 陳士杰 ) 10
循序檔 (Sequential File) 循序檔的每一筆記錄, 是依加入順序儲存, 記錄本身無順序關係 另外有一種稱為排序檔 (Ordering File) 的檔案組織, 其每一筆記錄是依照鍵值 (Key Value) 加以排序而存入檔案中 有些書籍將此檔案組織稱為循序檔 國立聯合大學資訊管理學系資料庫系統課程 ( 陳士杰 ) 11
特性 : 依照檔案加入的順序, 將記錄存入檔案的結尾處 新記錄直接插入檔案的結尾, 時間複雜度為 O(1) 記錄搜尋方式採線性搜尋 (Linear Search), 時間複雜度為 O((1+n)/2) = O(n) 刪除做法有以下兩種, 但皆會造成磁碟空間的浪費, 且需要資料重組的動作 複製含有欲刪除記錄之區塊至緩衝區 (Buffer), 自緩衝區刪除記錄, 再寫回磁碟區塊中 每一筆記錄均加入一個刪除標記, 以表示記錄有效或已被刪除 國立聯合大學資訊管理學系資料庫系統課程 ( 陳士杰 ) 12
優點 適合批次作業 程式設計簡單 可儲存於循序性媒體, 如 : 磁帶 加入資料十分有效率 ( 插入尾端 ) 若檔案很少刪除及更新動作時, 十分節省空間 缺點 搜尋速度慢 ( 線性搜尋 ) 處理速度慢, 不適合即時性應用 記錄更新 刪除時, 必須產生額外的暫時檔案 國立聯合大學資訊管理學系資料庫系統課程 ( 陳士杰 ) 13
雜湊檔 (Hashing File) 利用雜湊函數 (Hash Function) 將每筆記錄之鍵值 (Key Value) 或雜湊欄位 (Hash Field) 轉換成相對應之磁碟儲存位址 將欲插入資料的鍵值或雜湊欄位帶入雜湊函數, 轉換成儲存位址, 再將資料插入至此位址 若此位址已有資料, 則採用碰撞 ( 或稱 Overflow) 解決方法加以處理 將欲搜尋資料的鍵值或雜湊欄位帶入雜湊函數, 轉換成儲存位址, 再將資料取出 若此位址的資料並非欲搜尋的資料, 則亦採用碰撞 ( 或稱 Overflow) 解決方法加以處理 國立聯合大學資訊管理學系資料庫系統課程 ( 陳士杰 ) 14
優點 : 存取效率高 ( 前提 : 雜湊函數須設計的好, 碰撞少 ) 適合即時性 線上應用 一般情況下, 插入 搜尋 刪除效率皆十分高 缺點 : 雜湊函數的設計十分重要, 否則可能產生嚴重的碰撞問題, 造成整體效率的急速下降 演算法設計較為複雜 不適合循序性的媒體 國立聯合大學資訊管理學系資料庫系統課程 ( 陳士杰 ) 15
索引檔 (Index File) 索引 (Index) 是一種資料存取的結構, 其目的是在特定的搜尋條件下, 用來加速擷取資料的速度 建立索引的主要好處是用來加速查詢 可分成以下兩種 : 單層索引 (Single-level Index): 依照有序之索引欄位建立索引 主索引 (Primary Index) 次索引 (Secondary Index) 叢集索引 (Clustering Index) 多層索引 (Multi-level Index): 以樹狀結構建立索引 B Tree B + Tree 國立聯合大學資訊管理學系資料庫系統課程 ( 陳士杰 ) 16
特性 : 資料實體儲存不一定要依照特定順序, 另以索引 (Index) 表達資料間的順序關係 插入 更新 刪除皆不需要產生新檔, 利用索引可快速地找到所需之記錄 優點 : 存取效率高 ( 介於循序 雜湊之間 ) 適合即時性 (Real-time) 線上(Online) 應用 資料不需事先排序, 但循序存取時亦十分有效率 使用廣泛, 多數系統皆支援索引結構 國立聯合大學資訊管理學系資料庫系統課程 ( 陳士杰 ) 17
缺點 : 額外的索引佔空間 需耗費額外時間建立索引 程式設計較複雜 資料新增 刪除動作過多時, 可能常需要資料重組 不適合循序性的媒體 國立聯合大學資訊管理學系資料庫系統課程 ( 陳士杰 ) 18
單層索引 (1): 主索引 (Primary Index) 以主鍵 (Primary Key) 為索引欄位 記錄依主鍵值做排序 為非密集索引 索引記錄數 = 資料檔區塊 (Block) 數 索引記錄 = Key value( 索引欄位值 ) + Block Pointer( 區塊指標 ) Block 國立聯合大學資訊管理學系資料庫系統課程 ( 陳士杰 ) 19
密集索引 (Dense Index) 每一筆記錄皆有一筆相對應的索引欄位值及區塊指標 非密集索引 (Non-dense Index) 並非每一筆記錄皆有一筆相對應的索引欄位值及區塊指標 國立聯合大學資訊管理學系資料庫系統課程 ( 陳士杰 ) 20
分成兩種 : 單層索引 (2): 次索引 (Secondary Index) 以次鍵 (Secondary Key) 為索引欄位 以非鍵值欄位 (Non-key Field) 為索引欄位 上述兩種次索引於使用時, 其資料記錄皆未排序 國立聯合大學資訊管理學系資料庫系統課程 ( 陳士杰 ) 21
為密集索引 索引記錄數 = 資料記錄數 以次鍵 (Secondary Key) 為索引欄位 國立聯合大學資訊管理學系資料庫系統課程 ( 陳士杰 ) 22
為非密集索引 以非鍵值欄位 (Non-key Field) 為索引欄位 索引記錄數 = 相異索引欄位數 國立聯合大學資訊管理學系資料庫系統課程 ( 陳士杰 ) 23
單層索引 (3): 叢集索引 (Clustering Index) 以非鍵值欄位 (Non-key Field) 為索引欄位 記錄依非鍵值之索引欄位做排序 為非密集索引 索引記錄數 = 相異索引欄位數 國立聯合大學資訊管理學系資料庫系統課程 ( 陳士杰 ) 24
國立聯合大學資訊管理學系資料庫系統課程 ( 陳士杰 ) 25
多層索引 (Multi-Level Indexes) 多層索引是針對單層索引的索引表本身再建立一層主索引 ; 此時原始的索引檔案稱作第一層索引 (First-level Index), 而索引的索引則稱作第二層索引 (Second-level Index), 以此類推 可適用於各種類型的索引, 不管是主索引, 叢集索引或次索引, 只要第一層索引的每個索引項目都有唯一的 K(i) 且為固定長度即可 為了要保有使用多層索引好處, 同時也降低索引插入與刪除的問題, 通常會採用 B 樹和 B + 樹資料結構來實作, 這種方法稱為動態多層索引 國立聯合大學資訊管理學系資料庫系統課程 ( 陳士杰 ) 26
國立聯合大學資訊管理學系資料庫系統課程 ( 陳士杰 ) 27
動態多層索引 :B tree B tree 中的每個節點即為磁碟中的一個區塊 (Block) 以下為分支度 3 的 B-tree 節點結構 : Key Value 7, 11 7 11 2, 4 9 14, 20 Block Pointer (Pb) Record Pointer (Pr) ( 指向真正的內容 ) 假設每個區塊的大小為 B, 區塊指標的大小為 Pb, 記錄指標的大小為 Pr, 鍵值大小為 K, 每個區塊的分支度最多為 p, 則 : (p Pb) + (p-1) (Pr+K) B 國立聯合大學資訊管理學系資料庫系統課程 ( 陳士杰 ) 28
動態多層索引 :B + tree B + tree 中的每個節點即為磁碟中的一個區塊 (Block) 以下是分支度為 3 的 B + tree: 7, 11 2, 4 9 14, 20 1, 2 4 7 9 11 14 18, 20 21, 23 分支度為 3 之 B + tree 的內部節點 (Internal Node): Key Value 7 11 B+tree 的內部節點所存放的 Key Value, 僅為搜尋用的索引值, 用以往下搜尋找資料 Block Pointer 國立聯合大學資訊管理學系資料庫系統課程 ( 陳士杰 ) 29
分支度為 3 之 B + tree 的葉節點 (Leaf Node): Key Value 1 2 Record Pointer ( 指向真正的內容 ) Block Pointer ( 指向隔壁的 node) B+tree 的 Block Pointer 可用於資料的循序存取 ( 較 B tree 方便 ) 假設每個區塊的大小為 B, 區塊指標的大小為 Pb, 記錄指標的大小為 Pr, 鍵值大小為 K, 每個區塊的分支度最多為 p,p leaf 為在 Leaf Node 內可放的鍵值數量, 則 : ( 內部節點 ) p Pb + (p-1) K B ( 葉節點 ) Pb + p leaf (Pr+K) B 國立聯合大學資訊管理學系資料庫系統課程 ( 陳士杰 ) 30
比較 B tree B + tree 資料所在 樹中所有節點 Leaf Node 分支度 較小 較大 樹的深度 較大 較小 適合的資料量 小 大 搜尋次數 1( 最佳 )~ 樹深 ( 最差 ) 固定為樹深 循序存取 不適用 適用 國立聯合大學資訊管理學系資料庫系統課程 ( 陳士杰 ) 31
練習範例 1 有 50000 筆員工記錄, 員工編號 ( 鍵值 ) 長度為 10bytes, 區塊大小為 1024bytes, 區塊指標為 6bytes, 記錄指標長度為 8bytes, 且每個節點皆約 80% 滿, 請問 : Ans: 若採 B tree, 最多需幾次區塊存取? 先求出 tree 的分支度 p (p Pb) + (p-1) (Pr+K) B (p 6) + (p-1) (8+10) 1024 p 43.42, 取 p = 43 ( 分支度 ) 因為每個 node 只存 80%, 故每個 node 內區塊指標數量 = 43 80% = 34, 鍵值數量 = 33 國立聯合大學資訊管理學系資料庫系統課程 ( 陳士杰 ) 32
Node Pointer 數量 存放鍵值數量 Root 1 34 33 Level 1 34 34 34 = 1156 34 33=1122 Level 2 1156 1156 34 = 39304 1156 33 = 38148 Level 3 39304 1297032 合計大於 50000 因為樹深為 4, 索引的存取次數為 1~4 次, 若再加上一次記錄存取 ( 即 : 利用記錄指標將真正資料取出 ), 故 最多 存取 5 次 國立聯合大學資訊管理學系資料庫系統課程 ( 陳士杰 ) 33
Ans: 續前題, 若採 B + tree, 最多需幾次區塊存取? 先求出 tree 的內部節點與葉節點的分支度 : Internal Node: (p 6) + (p-1) 10 1024 p = 64 因 node 只存 80%, 故區塊指標數量 = 64 80% = 51 Leaf Node: p leaf (10+8) + 6 1024 p leaf = 56 因 node 只存 80%, 故 Node 內鍵值數量 = 56 80% = 44 國立聯合大學資訊管理學系資料庫系統課程 ( 陳士杰 ) 34
Node Pointer 數量 存放鍵值數量 Root 1 51 50 Level 1 51 51 51 = 2601 51 50=2550 Level 2 2601 2601 51 2601 50 = 130050 Leaf Level 2601 2601 44=114444 此層內所能存放的鍵值數已大於 50000, 故不適合再建立此一內部層, 應改設為 Leaf 層 因為樹深為 3 ( 包含 leaf), 索引的存取次數為 3 次, 若再加上一次記錄存取 ( 即 : 利用記錄指標將真正資料取出 ), 故 最多 存取 4 次 國立聯合大學資訊管理學系資料庫系統課程 ( 陳士杰 ) 35
練習範例 2 A file has r = 20,000 STUDENT records of fixed length. Each record has the following fields: NAME(30 bytes), SSN(9 bytes), ADDRESS(40 bytes), PHONE(9 bytes), BIRTHDATE(8 bytes), SEX(1 bytes), MAJORDEPTCODE(4 bytes, integer), and DEGREEPROGRAM(3 bytes). An additional byte is used as a deletion marker. The file is stored on a disk whose block size is 512 bytes. Assuming an unspanned organization, what is the blocking factor? Ans: Blocking Factor(BFR): 每個區塊所能夠存放的記錄數目 區塊大小 (B) = 512 bytes 每筆記錄長 (R) = 30+9+40+9+8+1+4+4+4+3+1 = 113 bytes BFR = B/R =4 BFR 為區塊大小除每筆記錄長, 若有餘數則無條件捨去到整數 ( 餘數表示無法塞下一筆完整記錄的剩餘空間 ) 國立聯合大學資訊管理學系資料庫系統課程 ( 陳士杰 ) 36
練習範例 3 Consider a disk with block size B =512 bytes. A block pointer isp = 6bytes long, and a record pointer Pr = 7 bytes long. A file has r =30,000 EMPLOYEE records of fixed length. Each record has the following fields: NAME (30 bytes), SSN(9 bytes), DEPARTMENTCODE(9 bytes), ADDRESS(40 bytes), PHONE(9 bytes), BIRTHDATE(8 bytes), SEX(1 bytes), JOBCODE(4 bytes), SALARY(4 bytes, real number). An additional byte is used as a deletion marker. Suppose that the file is ordered by the key field SSN and we want to construct a primary index on SSN. What is the index blocking factor? Ans: Index Blocking Factor (BFRi): 每個區塊所能存放之索引記錄數目 索引記錄的組成 = Key Value + Block Pointer 每筆索引記錄的長度 (Ri) = SSN+P = 9+6 = 15 bytes Block Size (B) = 512 bytes Index Blocking Factor = B/Ri = 34 國立聯合大學資訊管理學系資料庫系統課程 ( 陳士杰 ) 37
反轉檔 (Inverted File) 特性 : 表格中每個欄位都可建立次索引, 各擁有並維護其索引表 根據任何欄位來做檢索, 皆可容易地搜尋到相對應的記錄 每建立出一個索引表時, 其原資料表格中的相對應欄位可以刪除, 以節省空間 國立聯合大學資訊管理學系資料庫系統課程 ( 陳士杰 ) 38
範例 : 原始學生成績資料表 記錄所在位址 學號 姓名 物理成績 化學成續 0010 S001 陳一 100 90 0013 S002 林二 72 63 0210 S003 張三 100 53 1005 S004 李四 45 20 0021 S005 王五 15 53 0120 S006 周六 94 100 國立聯合大學資訊管理學系資料庫系統課程 ( 陳士杰 ) 39
以姓名為索引 姓名索引表 姓名 指標 陳一 0010 林二 0013 張三 0210 李四 1005 王五 0021 周六 0120 學生成績資料表 記錄所在位址 學號 物理成績 化學成續 0010 S001 100 90 0013 S002 72 63 0210 S003 100 53 1005 S004 45 20 0021 S005 15 53 0120 S006 94 100 國立聯合大學資訊管理學系資料庫系統課程 ( 陳士杰 ) 40
以物理成績為索引 物理成績索引表 物理成績 指標 100 0010, 0210 72 0013 45 1005 15 0021 94 0120 學生成績資料表 記錄所在位址 學號 姓名 化學成續 0010 S001 陳一 90 0013 S002 林二 63 0210 S003 張三 53 1005 S004 李四 20 0021 S005 王五 53 0120 S006 周六 100 國立聯合大學資訊管理學系資料庫系統課程 ( 陳士杰 ) 41
以化學成績為索引 化學成績索引表 化學成績 指標 90 0010 63 0013 53 0210, 0021 20 1005 100 0120 學生成績資料表 記錄所在位址 學號 姓名 物理成績 0010 S001 陳一 100 0013 S002 林二 72 0210 S003 張三 100 1005 S004 李四 45 0021 S005 王五 15 0120 S006 周六 94 國立聯合大學資訊管理學系資料庫系統課程 ( 陳士杰 ) 42
以姓名 物理成績 化學成績為索引 學生成績資料表 記錄所在位址 學號 0010 S001 0013 S002 姓名索引表 0210 S003 姓名 指標 1005 S004 陳一 0010 0021 S005 林二 0013 0120 S006 張三 0210 李四 1005 王五 0021 周六 0120 物理成績索引表 物理成績 指標 100 0010, 0210 72 0013 45 1005 15 0021 94 0120 化學成績索引表 化學成績 指標 90 0010 63 0013 53 0210, 0021 20 1005 100 0120 國立聯合大學資訊管理學系資料庫系統課程 ( 陳士杰 ) 43
完全反轉檔 關聯表格中有幾個欄位, 就建幾個索引檔 理論上, 表格中的每個欄位皆可建立其各自的索引表 然而, 在實務上礙於一個資料表格至少要有一個欄位存在的系統要求, 所以實作上無法將所有欄位皆刪除掉 優點 : 根據特定欄位的某個搜尋條件進行存取時, 十分迅速 適用於多重鍵之索引 缺點 : 當使用許多欄位建立多個索引表時, 若欲得到一筆完整記錄, 必須查詢所有次索引, 十分耗時 國立聯合大學資訊管理學系資料庫系統課程 ( 陳士杰 ) 44
補充 國立聯合大學資訊管理學系資料庫系統課程 ( 陳士杰 ) 45
Hashing ( 雜湊 ) Def: 為一種資料貯存與搜尋的技術 若要存取某筆資料 x, 則先將 x 經過 Hashing Function 計算, 得出 Hashing Address, 再到 Hash Table 對應的 Bucket 中進行存取 x 的動作 Hash Table 的結構 由一組 Buckets 所組成, 每個 Buckets 由一組 Slot 所組成, 每個 Slot 可存 一筆記錄 Hash Table 圖示 : Hash Table Size = b s Bucket ( 桶子 ) x Hashing Function 存 / 取 H(x) (Hash Address) b 個 Slot ( 槽 ) s 個 國立聯合大學資訊管理學系資料庫系統課程 ( 陳士杰 ) 46
相關術語 Collision Def: 不同的資料 (e.g., x 與 y) 在經由 Hashing Function 計算, 竟得出相同的 Hashing Address ( 即 H(x) = H(y)) 稱之 Overflow Def: 當 Collision 產生, 且 Bucket 中無多餘的 Slot 可存資料稱之 w H(w) x H(x) y H(y) w x y z: Overflow z H(z) 有 Collision 並不一定有 Overflow, 但有 Overflow, 則必有 Collision 發生 若 Bucket 只有一個 Slot, 則 Collision = Overflow 國立聯合大學資訊管理學系資料庫系統課程 ( 陳士杰 ) 47
4 種常見的 Overflow 處理方式 Linear Probing ( 線性探測 ) Quadratic Probing ( 二次方探測 ) Rehashing ( 再雜湊 ) Link List ( 鏈結串列, 或稱 Chain) 國立聯合大學資訊管理學系資料庫系統課程 ( 陳士杰 ) 48
Linear Probing ( 線性探測 ) Def: 又稱 Linear Open Addressing 當 H(x) 發生 overflow, 則循著 H(x)+1, H(x)+2,, H(x)-1 順序, 逐步搜尋, 直到 : 遇見有空的 Bucket 已搜尋完一圈為止 ( 表示 Hash Table Full, 無法 store) 圖示 : x 國立聯合大學資訊管理學系資料庫系統課程 ( 陳士杰 ) 49
Hash Table 有 11 個 buckets ( 編號 : 0~10), 每個 bucket 只有一個 slot, 假設 Hashing Function = x mod 11, 並採取 Linear Probing 處理 overflow 試依照下列資料次序存入 Hash Table, 會得到什麼結果? Sol: 屬於 5 的部落 原本應該屬於位置 6 的資料 17, 被擠到很遠的地方, 要翻山越嶺才能找到它!! Search Time 增加!! 5, 16, 33, 21, 22, 27, 38, 17 0 33 1 22 2 3 4 5 5 6 16 7 27 8 38 9 17 10 21 H(33) H(22) H(5) H(16) H(27) H(38) H(17) H(21) 缺點 : 易形成資料群聚 (Clustering) 現象, 增加 Searching Time 國立聯合大學資訊管理學系資料庫系統課程 ( 陳士杰 ) 50
Quadratic Probing ( 二次方探測 ) Def: 為改善 Clustering 現象而提出 當 H(x) 發生 overflow 時, 則探測 (H(x) ± i 2 ) mod b,b 為 bucket 數,1 i (b- 1)/2 圖示 : 空位的探測次序 : 4 3 2 1 H(x) 國立聯合大學資訊管理學系資料庫系統課程 ( 陳士杰 ) 51
承接上題, 並改採 Quadratic Probing 處理 overflow 則 Hash Table 內容為何? Sol: 5, 16, 33, 21, 22, 27, 38, 17 0 33 1 22 2 3 4 27 5 5 6 16 7 17 8 9 38 10 21 H(33) H(22) H(5) H(16) H(27) H(38) H(17) H(21) 國立聯合大學資訊管理學系資料庫系統課程 ( 陳士杰 ) 52
Rehashing ( 再雜湊 ) Def: 提供一系列的 Hashing Functions: f 1, f 2, f 3, f n 若使用 f 1 發生 overflow, 則改用 f 2 ; 以此類推, 直到 : 沒有 overflow 發生 全部 function 用完 國立聯合大學資訊管理學系資料庫系統課程 ( 陳士杰 ) 53
Link List ( 鏈結串列, 或稱 Chain) 將具有相同 Hashing Address 的資料, 以 Link list 方式串連在同一 Bucket 中 承接上題, 並採 Link List 處理 overflow 則 Hash Table 內容為何? 5, 16, 33, 21, 22, 27, 38, 17 Sol: H(22) H(33) 0 33 H(38) H(27) H(16) H(5) H(17) H(21) 1 2 3 4 5 5 6 17 7 8 9 10 21 22 16 27 38 國立聯合大學資訊管理學系資料庫系統課程 ( 陳士杰 ) 54