5物理模式設(shè)計

1、5 november 20211第第5章章: 物理模式設(shè)計物理模式設(shè)計l主要內(nèi)容5.1物理模式設(shè)計簡介5.2索引的原理與設(shè)計原則5 november 20212數(shù)據(jù)庫系統(tǒng)概念-導(dǎo)論5.1數(shù)據(jù)庫的三級模式數(shù)據(jù)庫的三級模式l物理模式 數(shù)據(jù)的存儲結(jié)構(gòu)，研究數(shù)據(jù)如何存儲 也稱作稱存儲模式、內(nèi)模式 l邏輯模式 全體數(shù)據(jù)的邏輯結(jié)構(gòu) 又稱作全局模式l外模式 具體用戶看到的數(shù)據(jù)的邏輯結(jié)構(gòu) 又稱作子模式、用戶模式5 november 20213數(shù)據(jù)庫系統(tǒng)概念-導(dǎo)論5.1數(shù)據(jù)庫的三級模式關(guān)系示意圖數(shù)據(jù)庫的三級模式關(guān)系示意圖app1app2外模式外模式1外模式外模式2外模式外模式邏輯模式邏輯模式物理模式物理模式hd

2、app3app.三級模式及兩級映像示意圖三級模式及兩級映像示意圖物理映像物理映像邏輯映像邏輯映像5.1物理模式設(shè)計的目標(biāo)物理模式設(shè)計的目標(biāo)l物理模式設(shè)計目標(biāo) 在硬件及系統(tǒng)環(huán)境限制下，為邏輯模式的實現(xiàn)提供最理想的支持 主要是性能支持5 november 202145.1物理模式設(shè)計在工程中的位置物理模式設(shè)計在工程中的位置l數(shù)據(jù)的物理獨立性 當(dāng)物理模式發(fā)生變化時，通過調(diào)整物理/邏輯模式映像，可以保持邏輯模式不變，進(jìn)而應(yīng)用程序不需改變；這種數(shù)據(jù)和程序的獨立性，稱為數(shù)據(jù)的物理獨立性。l物理模式設(shè)計在工程中的位置 在邏輯模式設(shè)計完成后、程序開發(fā)之前進(jìn)行 可以在系統(tǒng)上線實施調(diào)整 在系統(tǒng)運行期間，根據(jù)實際情

3、況繼續(xù)調(diào)整5 november 202155.2索引的原理與設(shè)計原則索引的原理與設(shè)計原則l本節(jié)要點 5.2.1數(shù)據(jù)訪問類型分析 5.2.2索引的基本工作原理介紹 5.2.3順序文件與主索引 5.2.4輔助索引 5.2.5常見的索引結(jié)構(gòu) 5.2.6索引的相關(guān)說明 5.2.7索引設(shè)計的原則5 november 202165 november 202175.2.1:數(shù)據(jù)訪問類型分析數(shù)據(jù)訪問類型分析l數(shù)據(jù)訪問的類型 查詢 修改 據(jù)調(diào)查：數(shù)據(jù)查詢的訪問數(shù)量遠(yuǎn)大于數(shù)據(jù)修改的數(shù)量數(shù)據(jù)查詢的訪問數(shù)量遠(yuǎn)大于數(shù)據(jù)修改的數(shù)量l數(shù)據(jù)查詢的類型 特定值查詢例如：select * from s where sno=200

4、9012689 值范圍查詢例如：select * from sc where score=60 and score705 november 202185.2.2索引的基本工作原理索引的基本工作原理l許多查詢只涉及文件中的少量記錄 找出計算機(jī)系的所有女學(xué)生 找出學(xué)號為s01的學(xué)生姓名l只涉及少量記錄查詢的實現(xiàn) 讀取所有記錄并一一檢查：非常低效 理想目標(biāo)：快速甚至直接定位查詢記錄l索引 為了實現(xiàn)快速數(shù)據(jù)定位，對數(shù)據(jù)文件設(shè)計的附加結(jié)構(gòu) 與圖書館中圖書索引的原理相同5 november 202195.2.2:索引設(shè)計基本原理示意索引設(shè)計基本原理示意s9999s0002s0001 b5826t1t2t5

5、t9997t9998t9999b1b5555 select * from s where sno=s4567;全表掃描，全表掃描，o(n)，n=10,000，平，平均讀入均讀入1700磁盤塊磁盤塊索引掃描，索引掃描，o (logn) ，n=10,000, 除去索引塊，只需讀入除去索引塊，只需讀入1磁盤塊，磁盤塊，而索引所占空間小的多而索引所占空間小的多s:t1t2snos0001s0002s9999sname甲甲乙乙丁丁dept計計軟軟文文索引索引5.2.3:順序文件與主索引順序文件與主索引l數(shù)據(jù)塊數(shù)據(jù)塊 可用的磁盤空間被劃分為很多塊可用的磁盤空間被劃分為很多塊 塊是磁盤空間輸入和輸出的最小單

6、位塊是磁盤空間輸入和輸出的最小單位l索引記錄（索引項）索引記錄（索引項） 由一個搜索碼值和指向具有該搜索碼值的一個或多個記錄的由一個搜索碼值和指向具有該搜索碼值的一個或多個記錄的指針構(gòu)成指針構(gòu)成 指向記錄的指針包括磁盤塊的標(biāo)識和標(biāo)識磁盤塊內(nèi)記錄的塊指向記錄的指針包括磁盤塊的標(biāo)識和標(biāo)識磁盤塊內(nèi)記錄的塊內(nèi)偏移量內(nèi)偏移量l順序文件順序文件 元組在塊中按照搜索碼的升序存儲元組在塊中按照搜索碼的升序存儲l主索引（聚集索引）主索引（聚集索引） 順序文件中搜索碼對應(yīng)的索引順序文件中搜索碼對應(yīng)的索引 有主索引的順序文件稱作索引順序文件有主索引的順序文件稱作索引順序文件5 november 2021105 no

7、vember 2021115.2.3:順序文件與主索引示意順序文件與主索引示意l順序文件與主索引示意 主索引可以采用稀疏索引 稀疏索引只為搜索碼的某些值建立索引l主索引一般可以駐留內(nèi)存 特定值查詢、值范圍查詢：非常高效l一個表至多有一個主索引5 november 2021125.2.4:輔助索引輔助索引l輔助索引（非聚集索引） 文件中元組物理存儲順序與搜索碼順序不同的索引 一個表可以有多個輔助索引 輔助索引必須采用稠密索引5 november 2021135.2.5常見的索引結(jié)構(gòu)常見的索引結(jié)構(gòu)l索引文件的主要組織類型 散列索引 順序索引l散列索引 將值平均分布到若干散列桶中 能很好地支持特定值

8、查詢 不能有效支持值范圍查詢l順序索引 基于值的大小順序組織的索引 能很好地支持特定值查詢、值范圍查詢 典型代表：b+樹索引，是目前主流的索引結(jié)構(gòu)5.2.5:b樹簡介樹簡介l一棵 m 序b樹是一顆滿足下列條件的樹：1、每個結(jié)點至多有m個孩子；2、除根結(jié)點和葉結(jié)點外，其它每個結(jié)點至少有 m/2個孩子；3、根結(jié)點至少有兩個孩子；4、所有葉結(jié)點在同一層，葉結(jié)點不包含任何關(guān) 鍵字信息；5、有k個孩子的非葉結(jié)點恰好包含k-1個關(guān)鍵字。5 november 2021145.2.5:b樹示意樹示意l一個3序b樹示意5 november 2021155.2.5:b樹查詢的高效性分析樹查詢的高效性分析1.每個結(jié)

9、點包含每個結(jié)點包含1000個關(guān)鍵字，故在第三層上有個關(guān)鍵字，故在第三層上有100多萬個葉結(jié)點，這些葉節(jié)點可容納多萬個葉結(jié)點，這些葉節(jié)點可容納10億多個關(guān)鍵字。億多個關(guān)鍵字。2.通常根結(jié)點可始終置于內(nèi)存中，因此在這棵通常根結(jié)點可始終置于內(nèi)存中，因此在這棵b樹中查樹中查找任一關(guān)鍵字至多只需二次訪問外存。找任一關(guān)鍵字至多只需二次訪問外存。5 november 2021165.2.5:b+樹簡介樹簡介lb+樹是一種b樹的變形 一棵m階的b+樹和b樹的差異在于：1.所有的葉子結(jié)點中包含了全部關(guān)鍵字的信息，及指向含這些關(guān)鍵字記錄的指針，且葉結(jié)點依關(guān)鍵字的大小從小到大順序鏈接。2.非葉結(jié)點僅具有索引作用，結(jié)

10、點中僅含有其子樹中最小關(guān)鍵字。(b樹鍵值只出現(xiàn)一次)3.葉結(jié)點的關(guān)鍵字可以多于m，也可以少于m。5 november 2021175.2.5:一個一個b+樹示意樹示意l一個3序b+樹示意5 november 2021185 november 2021195.2.6:索引索引 的相關(guān)說明的相關(guān)說明l索引的有關(guān)說明 可以動態(tài)地定義索引，即可以隨時建立和刪除索引 不允許用戶在數(shù)據(jù)操作中引用索引，索引是否使用、如何使用、如何維護(hù)完全由系統(tǒng)決定； 一個表上可建多個索引。索引可以提高查詢效率，但索引過多耗費空間，且降低了插入、刪除、更新的效率，并且會增加系統(tǒng)選擇索引的時間代價 有些dbms自動建立以下列上

11、的索引l primary keyl unique5 november 2021205.2.6:索引索引 的相關(guān)說明的相關(guān)說明l索引的定義 格式create unique/distinct cluster index 索引名on 表名 (列名 asc/desc , 列名asc/desc) unique（distinct）：唯一性索引，不允許表中不同的行在索引列上取相同值。若已有相同值存在，則系統(tǒng)給出相關(guān)信息，不建此索引。系統(tǒng)并拒絕違背唯一性的插入、更新 cluster：聚集索引，表中元組按索引項的值排序并物理地聚集在一起。一個基本表上只能建一個聚集索引 asc/desc：索引表中索引值的排序次序

12、，缺省為asc5 november 2021215.2.6:索引索引 的相關(guān)說明的相關(guān)說明 示例： create cluster index s-index on s（sn）l索引的刪除 格式drop index 索引名l索引連接(index-join) 對表2按連接字段建立索引 對表1中的每個元組，依次根據(jù)其連接字段值查詢表2的索引，從中找到滿足條件的元組，找到后就將表1中的第一個元組與該元組拼接起來，形成結(jié)果表中一個元組 5 november 2021225.2.7:索引設(shè)計的原則索引設(shè)計的原則l索引建立原則： 不必為小表創(chuàng)建索引 為表的主碼建立索引 為檢索數(shù)據(jù)時大量使用的列建立輔助索引（

13、如 name） 若經(jīng)常基于外碼訪問數(shù)據(jù)，則為該外碼建立輔助索引 為經(jīng)常有如下情況的列建立輔助索引：選擇或連接條件; order by; group by; 其他含有排序的操作 (如 union 或 distinct) 慎重為經(jīng)常被更新的列或表建立索引 如果查詢將檢索表中記錄的大部分（如25%)，即使表很大，也不建立索引。這時查詢整表要比用索引查詢更有效（選擇率）5 november 2021235.2.7:索引設(shè)計的原則索引設(shè)計的原則l索引與查詢優(yōu)化 有些dbms允許檢查優(yōu)化器的策略，從而可以分析改善查詢的性能；oracle explain plan，db2 explain，access性能分析器 查詢優(yōu)化器依賴于存儲在系統(tǒng)目錄中的數(shù)據(jù)庫統(tǒng)計來選擇最佳策略，每當(dāng)創(chuàng)建索引時，dbms自動將此索引增加到系統(tǒng)目錄中。但是，系統(tǒng)目錄中與表和索引相關(guān)的統(tǒng)計信息的更新，需要數(shù)據(jù)庫用戶自己使用dbms提供的工具完成l索引的刪除 如果維護(hù)索引可能會降低重要的更新事務(wù)，就考慮刪除索引 如果大量的記錄被插入到有索引的表中，可以先刪除索引，再執(zhí)行插入，然后重建索引（若增加表大小超過10%）5 novem