數(shù)據(jù)庫管理系統(tǒng)基本技術(shù)課件

1、數(shù)據(jù)庫管理系統(tǒng)基本技術(shù)主要內(nèi)容數(shù)據(jù)庫存儲(chǔ)技術(shù)數(shù)據(jù)庫查詢技術(shù)3參考書Raghu Ramakrishnan, Johannes Gehrke, DataBase Management Systems(Second Edition), McGraw-HillHector Garcia-Molina, Jeffrey D. Ullman, Jennifer Widom, DataBase systems the complete book, Prentice HallAbraham Silberschatz, Henry F. Korth,etc. Database System Concepts,M

2、c Graw Hill4數(shù)據(jù)庫存儲(chǔ)結(jié)構(gòu)5數(shù)據(jù)庫存儲(chǔ)結(jié)構(gòu)物理存儲(chǔ)介質(zhì)RAID磁盤系統(tǒng)DBMS對(duì)磁盤空間的管理DBMS從磁盤讀取數(shù)據(jù)的方法文件中管理頁(page)的方法頁中記錄的處理形式單條記錄的存儲(chǔ)方式6物理存儲(chǔ)介質(zhì)磁盤空間管理文件管理緩沖區(qū)管理控制磁盤上可用的空間以記錄的文件的形式提供給高層的DBMS進(jìn)行訪問，向磁盤空間管理器申請(qǐng)或釋放空間將記錄從磁盤讀到Buff Pool7存儲(chǔ)介質(zhì)層次高速緩存內(nèi)存快閃存磁盤存儲(chǔ)器光存儲(chǔ)器磁帶存儲(chǔ)器第二級(jí)存儲(chǔ)器（secondary storage）第三級(jí)存儲(chǔ)器（tertiary storage）Primary storage8存儲(chǔ)結(jié)構(gòu)分級(jí)存儲(chǔ)的原因價(jià)格因素主存

3、是磁盤的100倍尋址的問題32位機(jī)的主存大小小于232數(shù)據(jù)需要永久保存磁帶的特點(diǎn)價(jià)格便宜，存儲(chǔ)量大順序讀取9磁盤基本概念硬件上的最小單位是sector,是硬件的不可變屬性Block是數(shù)據(jù)存儲(chǔ)的最小單元，由若干sector構(gòu)成硬盤上的同心圓構(gòu)成track相同半徑的同心圓構(gòu)成Cylinder存放數(shù)據(jù)的盤片為Platter每個(gè)面有一個(gè)讀頭，通過磁盤臂進(jìn)行移動(dòng)磁盤轉(zhuǎn)動(dòng)，讀頭不動(dòng)10磁盤11磁盤硬盤的容量記錄盤面數(shù)每記錄盤面的磁道數(shù)每磁道的盤塊數(shù)每個(gè)盤塊的字節(jié)數(shù)數(shù)據(jù)的定位信息柱面號(hào)磁頭號(hào)盤塊號(hào)，系統(tǒng)對(duì)盤塊進(jìn)行統(tǒng)一編號(hào)磁盤的性能指標(biāo)磁盤容量：10180，000M存取時(shí)間Seek timeRotationa

4、l delayTransfer time傳輸速度：15MB/秒可靠性：38萬小時(shí)12磁盤讀寫的并行性一般的系統(tǒng)不支持讀頭間讀取數(shù)據(jù)的并行性少數(shù)支持有限度的并行，如兩個(gè)并行，主要原因在于讀頭無法并行移動(dòng)磁盤控制器負(fù)責(zé)實(shí)現(xiàn)對(duì)磁盤的基本操作，如移動(dòng)讀頭，定位傳輸數(shù)據(jù)等Checksum用于檢測數(shù)據(jù)是否正確地讀寫，讀寫時(shí)各算一遍記錄的存取方式不跨塊方式跨塊方式13磁盤結(jié)構(gòu)對(duì)性能的影響DBMS在操作時(shí)數(shù)據(jù)在內(nèi)存中磁盤和內(nèi)存間數(shù)據(jù)交換的單位是Block,一次傳輸為一次I/O操作為了提高速度，最好將同時(shí)讀寫的數(shù)據(jù)放在接近的地方，如同一block、track、clinderCreate tables space

5、overhead. transfer.14第三級(jí)存儲(chǔ)器光盤CDDVDWORM磁帶膠片15RAID磁盤系統(tǒng)磁盤是數(shù)據(jù)庫管理系統(tǒng)性能的瓶頸微處理器速度的提高為每年50%磁盤訪問的速度的提高為每年10%數(shù)據(jù)傳輸?shù)乃俣鹊奶岣邽槊磕?0%磁盤陣列（Disk Array）通過數(shù)據(jù)條帶（Data Striping）分布將多個(gè)磁盤變成一個(gè)整體若干磁盤組織在一起，通過并行提高速度通過冗余提高數(shù)據(jù)的可靠性Redundant array of independent disk=RAID16數(shù)據(jù)條帶磁盤間的并行性提高了磁盤組數(shù)據(jù)讀取的性能數(shù)據(jù)條帶數(shù)據(jù)被分成等長的分區(qū)，分布在多個(gè)盤上，每個(gè)分區(qū)的大小為一個(gè)條帶單元(st

6、riping unit)17磁盤空間管理DBMS結(jié)構(gòu)的最底層以頁為單位組織數(shù)據(jù)，主要操作包括讀、寫、申請(qǐng)和釋放經(jīng)常訪問的數(shù)據(jù)可放在連續(xù)的空間中隔離上層模塊和底層的軟、硬件平臺(tái)18磁盤空間管理管理空閑塊的方法記錄哪些塊正在使用，每一頁的位置通過一個(gè)空閑塊鏈表或空閑塊位圖來記錄空閑的塊實(shí)現(xiàn)方法利用操作系統(tǒng)文件系統(tǒng)管理磁盤空間自己實(shí)現(xiàn)對(duì)磁盤的訪問選擇的因素跨平臺(tái)的要求有的功能操作系統(tǒng)不提供19緩沖區(qū)管理器負(fù)責(zé)將磁盤上的數(shù)據(jù)讀入內(nèi)存并寫回磁盤的軟件層管理器管理的內(nèi)存空間稱為Buffer PoolBuffer Pool中的每個(gè)頁稱為Frame(每個(gè)Frame包含若干slot)如Buffer Pool有1

7、0個(gè)頁，表中有100個(gè)頁，如何進(jìn)行掃描工作決定內(nèi)存中那些頁應(yīng)該被替換的策略稱為Replacement Policy20工作流程DB高層代碼的頁請(qǐng)求Buffer PoolFree FrameDirty FrameDB高層代碼的頁請(qǐng)求Buffer PoolFree FrameDirty Frame如果所需的頁不在BufferPool中且Buffer Pool已滿則用Replace Policy進(jìn)行調(diào)度正在訪問的frame已訪問完且未被修改的數(shù)據(jù)21數(shù)據(jù)結(jié)構(gòu)和流程每個(gè)frame包括：pin_count,dirtypin_count:正在訪問該frame的事務(wù)的個(gè)數(shù)Dirty:已經(jīng)被修改過的Frame

8、請(qǐng)求處理的流程查看Buffer pool是否包含此頁，如沒有，則找一個(gè)pin_cout為的frame，pin_cout+如dirty為true,則將其寫入磁盤將相應(yīng)的頁讀入此frame將frame的地址返回22幾點(diǎn)補(bǔ)充Dirty代表此frame的數(shù)據(jù)已被修改，在Dirty frame被替換之前需要同步到磁盤上申請(qǐng)新的frame時(shí)如沒有可替換的frame，則等待如何處理多個(gè)事務(wù)同時(shí)訪問一個(gè)frame中的數(shù)據(jù)？23緩沖區(qū)的替換策略最早使用策略(Lest recently used,LRU)當(dāng)pin_count=0時(shí)該frame成為可選擇，但并不是馬上被替換，因?yàn)樵诖酥坝锌赡茉俅伪辉L問最早變成可選

9、擇的頁被首先替換Clock策略將所有的frame排成一個(gè)圈，下一個(gè)被替換的頁是圈上的下一個(gè)可選擇的頁使用referenced標(biāo)志避免剛被訪問過的frame被再次訪問，其想法是referenced在第一遍訪問時(shí)變成true，第二遍才替換24緩沖區(qū)的替換策略實(shí)際系統(tǒng)中的Buffer PoolDB2：clock,允許有多個(gè)Buffer PoolSybase ：LRU,允許有多個(gè)Buffer PoolInformax,Oracle: LRU,單個(gè)Buffer PoolSql Server: clock,單個(gè)Buffer Pool25Buffer Pool的預(yù)取Buffer Pool與virtual m

10、emory區(qū)別在于Buffer Pool能夠發(fā)現(xiàn)頁訪問模式頁訪問模式產(chǎn)生的原因在于，頁的訪問方式由上層的查詢代數(shù)和操作決定頁的預(yù)取DB2中的Prefetchingdirty frame的強(qiáng)制寫盤26文件與索引每個(gè)頁中包含若干條記錄，每個(gè)文件中包含若干個(gè)頁每個(gè)記錄有一個(gè)唯一的標(biāo)識(shí)符:rid，它包括頁號(hào)和在頁中的位置不同的數(shù)據(jù)庫管理系統(tǒng)的rid的定義略有不同27堆文件數(shù)據(jù)在文件中以記錄為單位無序地存儲(chǔ)，是最簡單的文件形式提供的功能包括：創(chuàng)建、刪除文件，插入刪除記錄需要討論的問題記錄頁中的空閑區(qū)間記錄有空閑區(qū)間的頁如何維護(hù)文件空閑區(qū)域的位置頁的鏈表頁字典28頁的鏈表每個(gè)文件記錄其第一個(gè)頁該頁連接兩條

11、鏈表缺點(diǎn)對(duì)非定長記錄則全在空鏈表中頭表數(shù)據(jù)頁數(shù)據(jù)頁數(shù)據(jù)頁.含空閑區(qū)間的頁數(shù)據(jù)頁數(shù)據(jù)頁數(shù)據(jù)頁.不含空閑區(qū)間的頁29頁字典用一個(gè)字典記錄每個(gè)頁的信息，包括空閑的空間大小字典的長度相對(duì)數(shù)據(jù)部分較小分配空間前將字典讀入.數(shù)據(jù)頁1數(shù)據(jù)頁2數(shù)據(jù)頁n字典頭頁30順序文件根據(jù)查找鍵的值的順序存儲(chǔ)記錄的文件每個(gè)記錄有一個(gè)指針，按鍵值大小創(chuàng)建鏈表通過自由空間管理，管理空閑空間HeF-257800LiuA-102600ZhouC-34375031順序文件插入操作尋找插入位置申請(qǐng)空閑空間維護(hù)鏈表HeF-257800LiuA-102600ZhouC-343750MaB-547500刪除操作32聚集文件一個(gè)文件中存儲(chǔ)多個(gè)

12、關(guān)系中的元組根據(jù)鍵屬性進(jìn)行數(shù)據(jù)組織S1 Wang 20 MS2 Liu 21 FS3 Chen 22 MS1 C1 80S1 C2 70S3 C1 90S3 C2 85S3 C3 95SSCS1Wang20S1S1C1C28070S2Liu21S3Chen22S3S3S3C1C2C3908595MFM33代價(jià)模型代價(jià)用與于估算不同的查詢操作的代價(jià)基本的符號(hào)B:數(shù)據(jù)庫中數(shù)據(jù)頁的數(shù)量R:每頁中記錄的個(gè)數(shù)D:讀寫一頁的時(shí)間C:處理一條記錄的時(shí)間（對(duì)相應(yīng)的屬性進(jìn)行比較）H:對(duì)一條記錄執(zhí)行執(zhí)行Hash函數(shù)的時(shí)間34代價(jià)計(jì)算的單位磁盤讀寫操作和計(jì)算的代價(jià)差巨大D=15毫秒，C,H=100納秒上述差距將越來

13、越大本書采用磁盤頁的讀寫作為代價(jià)標(biāo)準(zhǔn)在本書只是討論影響操作的主要因素本書沒有討論塊的讀寫問題，由于一塊上有若干頁，而且是硬件操作的基本單位。但頁是DBMS系統(tǒng)的讀寫單位，所以選用了頁35三種文件組織方式的比較三種文件組織方式隨機(jī)排序文件，堆文件對(duì)一系列屬性進(jìn)行排序的文件對(duì)一系列屬性執(zhí)行Hash操作的文件Search Key:用于排序和Hash的列36基本操作Scan讀取文件中所有的記錄Search with equality selection讀取文件中滿足某一相等條件的記錄Search with range selection讀取文件中滿足區(qū)間條件的記錄Insert將特定記錄插入文件Dele

14、te將特定記錄從文件中刪除37堆文件Scan代價(jià)為B(D+RC)Search with equality selection如事先知道只有一個(gè)結(jié)果，則為0.5B(D+RC),否則同ScanSearch with range selection代價(jià)為B(D+RC)Insert2D+C(數(shù)據(jù)加在關(guān)系的最后面)DeleteD+C(數(shù)據(jù)已經(jīng)在內(nèi)存中，可用rid中的page id訪問)38排過序的文件Scan代價(jià)為B(D+RC)Search with equality selection代價(jià)為Dlog2B+Clog2R(沒有重復(fù)的情況，且對(duì)查詢屬性排序)Search with range selecti

15、on同上InsertB(D+RC)(數(shù)據(jù)是連續(xù)存放的情況)DeleteB(D+RC)(數(shù)據(jù)是連續(xù)存放的情況)39Hashed的文件文件被分解為筐(Bucket)通過一個(gè)Hash函數(shù)找到相應(yīng)的筐需要考慮溢出的情況Hash函數(shù)Bucket1Bucket2Bucket3Bucket4Bucket540Hashed的文件Scan代價(jià)為1.25B(D+RC)(由于在文件中保存了一定的空閑)Search with equality selection代價(jià)為H+D+0.5RC(只有一個(gè)結(jié)果)Search with range selection代價(jià)為1.25B(D+RC)Insert代價(jià)為2DDelete代

16、價(jià)為C+D41頁的格式頁由一系列的記錄構(gòu)成每個(gè)記錄為一個(gè)slot記錄的id為(page id, slot number)42記錄格式記錄格式定長記錄變長記錄系統(tǒng)catalog中記錄了相關(guān)的信息43定長記錄每條記錄的長度是固定的，即沒有變長字段，一個(gè)頁存放記錄的數(shù)量和位置也是確定的刪除方法44定長記錄slot1slot2slotn.nPackedslot1slot2slotn.mUnpacked1 0 1. 0 1空閑空間m m-1 . 2 1每次刪除了記錄就將該頁最后一條記錄移到被刪除的位置，所有的空閑空間均在頁的下部，但rid會(huì)不斷調(diào)整記錄數(shù)記錄數(shù)每次刪除了記錄不做移動(dòng)，所有的空閑空間的信息

17、記錄在頁的尾部45定長記錄數(shù)據(jù)連續(xù)存放每個(gè)字段有固定的位置各種數(shù)據(jù)的方法基本相同F(xiàn)1 F2 F3 F4 . L1 L2 L3 L4Fi=field iLi=Length of field iBase address(B)Address=B+L1+L2+L346變長記錄記錄中包含變長字段，所以記錄的長度是可變的無法分配定長的slot為了避免大量的零碎空間，每次刪除后需要對(duì)頁上的空間進(jìn)行調(diào)整。但是要保證rid不變解決方法：用slot字典存放記錄的起始位置和記錄的長度，用記錄在slot字典中的位置代替slot的實(shí)際起始位置47變長記錄數(shù)據(jù)頁inSlot字典 頁中slot數(shù)量記錄（i，1）記錄（i，n

18、）記錄（i，2）48變長記錄兩種存放方法數(shù)據(jù)連續(xù)存放用分割符分開：需要掃描無用信息在記錄的前端用指針指向響應(yīng)的位置F1 $ F2 $ F3 $ F4 . Fi=field iF1 F2 F3 F4 49變長記錄對(duì)一個(gè)列的修改需要移動(dòng)其它列的位置一條記錄修改后可能造成記錄的長度超過目前該頁所能提供的空間，需要存入其它的頁，為了保證rid不變需要記錄該記錄的目前位置如長度超過一個(gè)頁的大小，則要分頁實(shí)際系統(tǒng)中Oracle不限制記錄長度DB2等限制長度，但提供大對(duì)象數(shù)據(jù)類型50文件組織和索引文件組織是當(dāng)文件存儲(chǔ)在磁盤上時(shí)在文件中組織記錄的方法不同的方法有不同的作用索引是查詢操作的性能的工具51文件組織

19、形式的選擇在實(shí)際系統(tǒng)可能并不是完全排序，也不是完全的連續(xù)存放52索引簡介索引是加速查詢操作的輔助文件結(jié)構(gòu)對(duì)要訪問的屬性值進(jìn)行重新組織，每個(gè)索引項(xiàng)包含（屬性值，rid）包括樹型索引和Hash索引一個(gè)索引可認(rèn)為是一個(gè)data entry的集合，通過它可快速地找到相應(yīng)的記錄所在的位置需要考慮的兩個(gè)問題為了方便查詢?nèi)绾谓M織data entrydata entry的構(gòu)成53索引的例子Smith,44,3000Jones,40,6003Tracy,44,5004Ashby,25,3000Basu,33,4003Bristow,29,2007Cass,50,5004Daniels,22,6003ageh1H

20、(age)=00H(age)=01H(age)=10300030005004salh2H(sal)=00H(sal)=1150044003200760036003File hashed on ageFile of pairs hashed on sal54索引中各種不同的data entry三種類型k*:包含了整個(gè)記錄search key為k的記錄search key為k的記錄集合用k*就沒有必要再存儲(chǔ)相應(yīng)的記錄，所以可作為一種特殊的文件組織形式兩種方式廣泛地應(yīng)用于各種索引結(jié)構(gòu)，特別是一個(gè)表上不只有一 個(gè)索引的情況55索引的特性Clustered versus UnClustered Inde

21、xesDense versus Sparse IndexesPrimary versus Secondary IndexesComposite Search key 的索引56Clustered versus UnClustered Indexes如果文件中記錄的次序同索引中data entry的次序是相同的，則這個(gè)索引是Clustered(簇聚的)第一種data entry是Clustered只有當(dāng)記錄的順序用索引對(duì)應(yīng)的屬性排序時(shí)，第二、三種data entry對(duì)應(yīng)的索引才是clustered57Clustered versus UnClustered Indexes一個(gè)表只有一個(gè)Clust

22、ered索引多個(gè)unclustered索引鑒于高昂的維護(hù)代價(jià)，即使是一個(gè) Clustered索引也經(jīng)常是不嚴(yán)格排序的用溢出鏈表的形式定期重新排序update操作與Clustered對(duì)Range查詢Clustered的作用比較大58Clustered Indexes.Index entryData entryData RecordsIndex fileData file59UnClustered Indexes.Index entryData entryData RecordsIndex fileData file60Dense versus Sparse Indexes如果表在該屬性上出現(xiàn)的所

23、有值在索引文件中均至少有一個(gè)data entry與之相對(duì)應(yīng)則為dens索引。Sparse索引中每個(gè)頁有一個(gè)data entry第一種 data entry只能用于dense索引第二種 data entry能用于兩種索引第三種 data entry通常用于dense索引Sparse索引只能是Clustered的索引61例子Smith,44,3000Jones,40,6003Tracy,44,5004Ashby,25,3000Basu,33,4003Bristow,30,2007Cass,50,5004Daniels,22,60032225303340444450AshbyCassSmithSpa

24、rse indexon nameDATADense indexon age62Primary and Secondary Indexes如果索引建在包含Primary Key的屬性上則為Primary Index，其它的為Secondary Index另一種解釋為第一種data entry對(duì)應(yīng)的索引為Primary Index,另兩種為Secondary index如果兩個(gè)data entry在索引屬性上對(duì)應(yīng)的值是相同的，則該索引為duplicates index,否則為unique index63Composite Search key 的索引包含多個(gè)屬性的索引是Composite Sear

25、ch key 的索引Bob 12 10Cal 11 80Joe 12 20Sue 13 75Name age sal11121213Index 10207580Index 11,8012,1012,2013,75Index 10,1220,1275,1380,11Index 64索引的定義在SQL-92中并沒有關(guān)于索引的語句，在SQL中也沒有涉及索引所有的商用DBMS均提供了與索引相關(guān)的語句CREATE INDEX IndAgeRating on Student WITH STRUCTURE=BTREE KEY=(age,gpa)65結(jié)構(gòu)索引索引提供高效查詢操作方法和動(dòng)態(tài)維護(hù)方法B+TREE是

26、一種動(dòng)態(tài)的索引結(jié)構(gòu)，適用于各種情況基于Hash的索引結(jié)構(gòu)66B+樹一種動(dòng)態(tài)的索引結(jié)構(gòu)靜態(tài)方法的缺點(diǎn)在于當(dāng)插入刪除過多時(shí)造成溢出鏈過長，影響效率。也不利于序列連續(xù)存放M階B+樹的特點(diǎn)每個(gè)結(jié)點(diǎn)至多有m棵子樹，至少有m/2棵子樹根結(jié)點(diǎn)或?yàn)槿~結(jié)點(diǎn)，或至少有兩棵子樹在insert,delete操作中樹保持平衡搜索時(shí)只需要訪問樹的高度次所有葉結(jié)點(diǎn)在同一層次，data entry層用雙向鏈表連接，便于訪問67B+樹的結(jié)構(gòu).Index entryData entryIndex file68B+樹索引結(jié)點(diǎn)的結(jié)構(gòu)B+樹結(jié)點(diǎn)的格式每個(gè)結(jié)點(diǎn)由n個(gè)數(shù)值和n+1個(gè)指針構(gòu)成pi指向的子樹上的結(jié)點(diǎn)的值k,有ki=k=ki+1

27、通常用第二種或第三種data entryData Entry 本身可以看成為是記錄的文件，如果data entry包含整個(gè)記錄，則文件就是數(shù)據(jù)本身，否則是一個(gè)單獨(dú)的文件。69搜索Func tree_search(nodepointer, search key value K) returns nodepointerIf *nodepointer is a leaf, return nodepointer;else,if KKm then return tree_search(Pm,K)else,find i such that Ki=KKi+1;return tree_search(Pi,K)

28、;Endfunc70B_樹的例子13 1724 302* 3*5* 7*19* 20*22*29* 24* 27*14* 16*33* 34*38* 39*d=271Insert首先從根結(jié)點(diǎn)出發(fā)向下，找到插入數(shù)據(jù)所在的位置。將數(shù)據(jù)插入到相應(yīng)的位置。當(dāng)結(jié)點(diǎn)滿的時(shí)候，進(jìn)行分解操作。逐層向上分解直到不需要分解的時(shí)候。當(dāng)結(jié)點(diǎn)滿時(shí)另一種方案是：當(dāng)該結(jié)點(diǎn)的兄弟結(jié)點(diǎn)不滿時(shí)，也可以進(jìn)行重新分配，以減少分解的數(shù)量。72InsertProc Insert(nodepointer,entry,newchildentry)If *nodepointer is a non-leaf node,say N find I

29、such that Ki=entrys key value Ki+1 insert(Pi,entry,newchildentry) if newchildentry is null, return; else, if N has space put*newchildentry on it, set newchildentry to null, return; else split N; first d key values and d+1 nodepointers stay, last d key values and d+1 nodepointers move to new node N2,

30、 newchildentry=&()73insertif N is the root create new node with make the trees root-node pointer point to the new nodes return; If *nodepointer is a leaf node, say L if L has space put entry on it,set newchildentry to null, and return; elsesplit L: first d entries stay, rest move to brand new node L

31、2; newchildentry=&(); set sibling pointers in L and L2 Return ;Endproc74例子5 132* 3*19* 20*22*29* 24* 27*14* 16*33* 34*24 30175* 7*8*增加8以后38* 39*75重新調(diào)整的例子8 1724 302* 3*5* 7*19* 20*22*29* 24* 27*8* 14* 16*33* 34*增加8以后38* 39*76刪除首先從根結(jié)點(diǎn)出發(fā)向下，找到刪除數(shù)據(jù)所在的位置。將數(shù)據(jù)相應(yīng)的位置刪除。當(dāng)結(jié)點(diǎn)過空的時(shí)候，進(jìn)行合并操作。逐層向上合并直到不需要合并的時(shí)候。當(dāng)該結(jié)點(diǎn)的兄弟

32、結(jié)點(diǎn)不空時(shí)，可以考慮重新分配，以減少合并的數(shù)量。該調(diào)整不僅作用在頁結(jié)點(diǎn)上，也可作用在非頁結(jié)點(diǎn)上77刪除Proc delete(parentpointer,nodepointer,entry,oldchildentry)If *nodepointer is a non-leaf node,say N find i such that Ki=entrys key value 1while there are runs to be merge from previous pass is choose next two runs(from previous pass)read each run int

33、o an input buffer;Merge the runs and write to the output bufferforce output buffer to disk one page at a timeendproc計(jì)算量分析若輸入文件大小為2k,k為一個(gè)整數(shù)Pass 0，產(chǎn)生2k個(gè)run，每個(gè)1頁P(yáng)ass 1，產(chǎn)生2k-1個(gè)run，每個(gè)2頁P(yáng)ass 2，產(chǎn)生2k-2個(gè)run，每個(gè)4頁總共需要log2N +1次pass,N為文件的頁數(shù)，對(duì)每一頁做一次讀，一次寫總共的開銷為：2N*(log2N +1)例子3,46,2 2 9,48,75,63,13,42,6 2 4,97,85,

34、61,32,3 4,6 2 4,7 8,91,3 5,6 2,3 4,4 6,7 8,91,2 3,5 6 1,2 2,3 3,4 4,5 6, 6 7,8 9 外部Merge排序若內(nèi)存中有B個(gè)pages。如何利用2路Merge排序的思想，進(jìn)行排序操作？在pass 0一次性讀入B個(gè)頁的數(shù)據(jù)進(jìn)行排序。在pass 1,2,一次性讀入B個(gè)頁的數(shù)據(jù)進(jìn)行排序。利用B-1個(gè)Buffer頁作為輸入，將最后一個(gè)Buffer頁作為輸出的緩沖區(qū)，進(jìn)行B-1路的Merge排序。算法Proc exsort(file)Read B page into memory, sort them, write out a run

35、While the number of runs at end of previous pass 1while there are runs to be merged from previous passchoose next B-1 runs(from previous pass)read each run into an input buffer; page at at timeMerge the runs and write to the output bufferforce output buffer to disk one page at a timeendproc圖示DiskDis

36、kInput 1Input 2Input B-1output 1Pass i0計(jì)算量分析第一次產(chǎn)生N1= N/B個(gè)runs對(duì)數(shù)據(jù)掃描的遍數(shù)，變?yōu)閘ogB-1N1+1最終的I/O次數(shù)為2N* logB-1N1+1性能實(shí)例NB=3B=5B=9B=17B=129B=257102743211103105432210413754221051796533106201075331072312864310826149744109301510854如何減少run的個(gè)數(shù)在Pass 0的過程中，可使用一些技巧，使得最初的run的長度平均為2B基本想法有一個(gè)頁的輸入緩沖區(qū)、一個(gè)頁的輸出緩沖區(qū)和一個(gè)當(dāng)前排序緩沖區(qū)首先將

37、數(shù)據(jù)調(diào)入當(dāng)前排序緩沖區(qū)（B-2頁）進(jìn)行排序不斷將大于輸出緩沖區(qū)中數(shù)據(jù)的最小的記錄從當(dāng)前排序緩沖區(qū)讀出送入輸出緩沖區(qū)，并不斷從輸入緩沖區(qū)中補(bǔ)充數(shù)據(jù)。直到當(dāng)前緩沖區(qū)中沒有可選的數(shù)據(jù)為止，則當(dāng)前run結(jié)束例子12 4 2 8 10 3 5 當(dāng)前緩沖區(qū)輸出緩沖區(qū)輸入緩沖區(qū)減少I/O代價(jià)的優(yōu)化性能的評(píng)價(jià)是一I/O的次數(shù)為標(biāo)準(zhǔn)的如果一次對(duì)連續(xù)的數(shù)據(jù)進(jìn)行讀寫將提高性能如何提高CPU的使用率塊I/O以緩沖區(qū)Block（若干個(gè)page）為單位進(jìn)行讀寫將提高單個(gè)Page讀寫的速度(減少了磁頭移動(dòng)的次數(shù))每次只能進(jìn)行F=(B-b)/b個(gè)run的合并，其中B為緩沖區(qū)中頁的數(shù)量，b為一個(gè)塊中頁的個(gè)數(shù)，總的掃描遍數(shù)為lo

38、gFN2+1,其中N2= N/2B應(yīng)用實(shí)例NB=103B=5*103B=104B=5*10410211111031111104221110532221063222107433210853321095433雙緩沖區(qū)排序的時(shí)間包括I/O的時(shí)間和CPU計(jì)算的時(shí)間在前面的方法中CPU計(jì)算的時(shí)間同I/O的時(shí)間不是并行的對(duì)每個(gè)run多加一個(gè)緩沖區(qū)，一個(gè)緩沖區(qū)在進(jìn)行I/O操作的同時(shí)，對(duì)另一個(gè)緩沖區(qū)的數(shù)據(jù)進(jìn)行計(jì)算圖示DiskDiskInput 1 Input 2 Input B-1 output 1 Input 1Input 2Input B-1output 1使用B+樹進(jìn)行排序聚集的索引由于磁盤上的數(shù)據(jù)是已

39、經(jīng)排序的，而且上層有一個(gè)索引結(jié)構(gòu)，所以查詢和排序操作性能均很高。非聚集的索引Data entry中的數(shù)據(jù)是排序的，但數(shù)據(jù)在磁盤上的存儲(chǔ)次序是雜亂無章的。計(jì)算量是(f+p)*N,N是數(shù)據(jù)頁的數(shù)量，p是每頁平均包含的記錄數(shù)，f是data entry中每條記錄的長度同記錄的長度的比關(guān)系操作的執(zhí)行查詢過程簡介Selection 操作General Selection操作Project 操作Join 操作Set操作聚集操作緩沖區(qū)的影響查詢過程介紹影響查詢操作算法性能的因素?cái)?shù)據(jù)庫表的大小、索引、排序情況、緩沖區(qū)的大小和置換策略各個(gè)操作實(shí)現(xiàn)時(shí)常用的基本技術(shù)Iteration:對(duì)數(shù)據(jù)庫的表和data entr

40、y中的數(shù)據(jù)逐個(gè)進(jìn)行檢測Indexing:如果選擇和連接操作中有限制條件，可通過索引找到滿足條件的元組Partitioning:將一個(gè)表分成若干部分，從而降低操作的執(zhí)行代價(jià)，常用排序和散列進(jìn)行分區(qū)訪問路徑(Access Paths)各種從關(guān)系表中訪問記錄的方法稱為訪問路徑訪問路徑的方式文件掃描(File Scan)索引加上選擇匹配條件，如attr op value索引要建在attr上op包括,訪問路徑的選擇率(selectivity)是總共訪問的頁數(shù)(包括索引訪問部分)，查詢優(yōu)化的目的是選擇高選擇率的訪問路徑(即訪問的頁數(shù)少的) 例子和相關(guān)參數(shù)Sailors(sid:integer,sname:

41、string,rating:integer,age:real)Reserves(sid:integer, bid:integer, day:date,rname:string)每個(gè)reserve記錄長為40個(gè)字節(jié)，一頁100條記錄，共1000頁每個(gè)sailors記錄長為50個(gè)字節(jié)，一頁80條記錄，共500頁只考慮I/O的頁數(shù)忽略結(jié)果的大小，因?yàn)橥粋€(gè)操作的不同實(shí)現(xiàn)方法都一樣選擇操作討論目標(biāo)：Select * from Reserves R where R.name=Joe對(duì)應(yīng)的查詢代數(shù)操作為：name=Joe(R)沒有索引，數(shù)據(jù)不排序需要掃描整個(gè)表代價(jià)是1000次I/O操作選擇率差，代價(jià)比較大

42、選擇操作沒有索引，數(shù)據(jù)排序采用折半查找的方法代價(jià)是O(log21000)，約為10次I/O操作選擇率高，代價(jià)比較小如約束是attr5，則首先找到5所在的位置，然后從5開始遍歷一般情況下數(shù)據(jù)的排序往往是和索引相關(guān)的。選擇操作使用B+樹索引查詢方法首先找到約束數(shù)據(jù)所在的位置從相應(yīng)的data entry開始向后逐個(gè)檢測直到找到所有滿足條件的data entry根據(jù)data entry找到相應(yīng)的元組代價(jià)分析一般找到起始的葉節(jié)點(diǎn)只需要2-3次讀寫主要代價(jià)在于滿足條件的記錄數(shù)和索引的是否是簇聚的選擇操作使用B+樹索引如果索引是簇聚的，檢測滿足條件的元組的代價(jià)一般為一次 I/O如果索引不是簇聚的，檢測滿足條

43、件的元組的代價(jià)為滿足條件的元組的個(gè)數(shù)次 I/O，如果事先對(duì)涉及的pageid進(jìn)行排序，則將減少I/O次數(shù)避免對(duì)同一頁進(jìn)行重復(fù)讀假設(shè)查詢條件改為rname“c%”，則結(jié)果數(shù)為表的大小的10%如果索引是簇聚的，則代價(jià)約為100次I/O操作如果索引是不是簇聚的，則代價(jià)最壞為10000次I/O操作，pageid 排序后最壞約為1000次I/O操作選擇率高，代價(jià)比較小選擇操作Hash索引，相等選擇執(zhí)行過程首先找到相應(yīng)的桶，在桶中的數(shù)據(jù)進(jìn)行檢測從數(shù)據(jù)文件中找到相應(yīng)的元組如果Hash不是簇聚的，有10個(gè)緩沖區(qū)，100個(gè)查詢結(jié)果查找相應(yīng)的rid的代價(jià)是1-2次I/O操作查找結(jié)果元組的代價(jià)是1-100次I/O操

44、作，如果對(duì)page id進(jìn)行排序，則可避免由于緩沖區(qū)小而帶來的重復(fù)調(diào)入的問題General Selection操作一般的查詢條件是一個(gè)邏輯表達(dá)式，通過邏輯連接符和連接的項(xiàng)(term)的表達(dá)式，項(xiàng)的形式為attr1 op attr2或attr1 op valueCNF(Conjunctive normal form)由符連接的conjunct一個(gè)conjunct是由連接的項(xiàng)的表達(dá)式(day (day8/9/94 bid=5 sid=3) (rname=Joe bid=5 sid=3) 如果conjunct包含則稱為disjunctive，或包含disjunctionGeneral Selecti

45、on操作幾個(gè)例子（若查詢條件為rname=Joe bid=5 sid=3 ）如果有一個(gè)Hash索引建立在上，則可直接進(jìn)行檢索，但該索引無法完成查詢條件rname=Joe bid=5如果有一個(gè)B+樹索引建立在上，則可直接進(jìn)行檢索，該索引還可直接完成查詢條件rname=Joe bid=5，但不適于查詢bid=5 sid=3 General Selection操作幾個(gè)例子（若查詢條件為rname=Joe bid=5 sid=3 ）如果有一個(gè)索引(Hash或樹)建立在上，則可直接進(jìn)行檢索，然后對(duì)查詢結(jié)果進(jìn)一步檢測rname的值如果有一個(gè)索引(Hash或樹)建立在上，還有一個(gè)索引建立在rname上，則可

46、提供兩種選擇，每種都可以但都必須做進(jìn)一步的檢測，選擇的標(biāo)準(zhǔn)是選擇率。General Selection操作一個(gè)索引滿足一個(gè)CNF選擇條件的條件如果一個(gè)選擇條件不包含disjunction，如果一個(gè)項(xiàng)為attribute=value，則建在attribute上的索引是滿足的如果一個(gè)選擇條件不包含disjunction，如果若干項(xiàng)為attributei=value，則以這些attributei為前綴的索引是滿足的滿足索引的conjuncts稱為primary conjuncts不包含disjunction的選擇操作的執(zhí)行可以進(jìn)行文件掃描，或先對(duì)選擇率最高的primary conjuncts通過索引

47、進(jìn)行查詢，然后利用非primary conjuncts對(duì)結(jié)果進(jìn)行篩選如果有多個(gè)索引同時(shí)滿足選擇條件首先用每個(gè)索引進(jìn)行篩選，找出相應(yīng)的候選記錄集合將這些集合進(jìn)行合并，可采用先排序再合并的方法用其它的conjuncts進(jìn)行篩選例如查詢條件為day8/9/94 bid=5 sid=3,索引分別建在day和sid上，則先執(zhí)行兩個(gè)選擇，再進(jìn)行合并，最后用bid進(jìn)行篩選不包含disjunction的選擇操作的執(zhí)行實(shí)際系統(tǒng)中的rid集合的交操作Oracle 8位圖的and操作用Hash Join的方法，將兩次查詢的結(jié)果進(jìn)行聯(lián)接Sql Server用索引聯(lián)接的方法DB2用Bloom filter的方法Syba

48、se用位圖的方法Informix也提供了相應(yīng)的方法包含disjunction的選擇操作的執(zhí)行如果有一個(gè)項(xiàng)需要對(duì)整個(gè)文件進(jìn)行掃描，則需要對(duì)整個(gè)文件進(jìn)行掃描若對(duì)rname和sid建了索引，查詢條件是day8/9/94 rname=Joe，由于day8/9/14需要掃描整個(gè)表，則要整個(gè)查詢也需要若查詢是(day8/9/94 rname=Joe) sid=3，則先對(duì)sid進(jìn)行檢索，然后進(jìn)行前半部分的篩選若每一項(xiàng)上均滿足索引，則先在索引上進(jìn)行檢索，再將結(jié)果進(jìn)行合并若對(duì)rename和day建了索引，查詢條件是day30 5sal,用帶in的嵌套查詢，先用索引將所有可能的候選找出用位圖的方法直接用disju

49、nction進(jìn)行篩選Sybase用位圖和union的方法投影操作Select distinct R.sid,R.bidFrom Reserves Rsid,bid Reservesattr1,attr2 (R)主要功能去掉不需要的屬性刪除重復(fù)元組排序或Hashing的方法基于排序的投影方法基本思路掃描關(guān)系R，生成只包含需要屬性的數(shù)據(jù)集對(duì)數(shù)據(jù)集進(jìn)行排序掃描排好序的結(jié)果，通過前后比較去除重復(fù)元組代價(jià)分析第一步代價(jià)為M+T,M是原始表的大小，產(chǎn)生的中間結(jié)果的大小為T，T=O(M),第二步的代價(jià)為O(Tlog2T),第三步代價(jià)為O(T)對(duì)表reserves(1000頁數(shù)據(jù)，每條記錄長為40)，若bid

50、和sid的長度和為10，則T為250頁，所以代價(jià)總和為: 1000+250+2*2*250+250=2500基于排序的投影方法兩種改進(jìn)將第一步同排序操作的pass 0結(jié)合在一起每次做merge的時(shí)候去除重復(fù)元組代價(jià)分析假設(shè)有20頁緩沖區(qū)Pass 0的代價(jià)是1000+250，產(chǎn)生7個(gè)run, pass1的代價(jià)是250，總共為1500基于Hasing的投影方法主要思路分區(qū)階段重復(fù)數(shù)據(jù)刪除分區(qū)階段將數(shù)據(jù)逐條讀如內(nèi)存，用一塊數(shù)據(jù)作為輸入緩沖區(qū)，另B-1塊作為輸出緩沖區(qū)用Hash函數(shù)進(jìn)行映射，將數(shù)據(jù)集分成B-1塊，圖示DiskDiskOuput 1Ouput 2Ouput B-1input 1B塊內(nèi)存緩

51、沖區(qū)H基于Hasing的投影方法重復(fù)數(shù)據(jù)刪除階段將每個(gè)分區(qū)的數(shù)據(jù)逐條讀入內(nèi)存，利用Hash函數(shù)H2在內(nèi)存中進(jìn)行分區(qū)，并刪除重復(fù)數(shù)據(jù)將內(nèi)存中的數(shù)據(jù)寫入硬盤中，將內(nèi)存緩沖區(qū)進(jìn)行清理，準(zhǔn)備下一分區(qū)的處理代價(jià)分析如果內(nèi)存足夠大，即第二階段全部在內(nèi)存中處理。第一階段的代價(jià)為M+T第二階段的代價(jià)為T總的代價(jià)為M+2T,對(duì)前面的例子，代價(jià)為1000+2*250 =1500兩種方法的比較基于排序的方法總體性能比較好產(chǎn)生的結(jié)果是排好序的特別適于內(nèi)存比較小和數(shù)據(jù)分布不均勻的情況一般排序和重復(fù)元組刪除兩部分是分開的基于Hashing的方法當(dāng)BT1/2的時(shí)候兩者性能相差不大投影操作利用索引進(jìn)行投影操作如果相應(yīng)的數(shù)據(jù)項(xiàng)

52、對(duì)應(yīng)索引結(jié)構(gòu)，則可直接在索引結(jié)構(gòu)上進(jìn)行操作，不需要訪問文件中的數(shù)據(jù)由于在索引中數(shù)據(jù)是排序的，所以很容易去除冗余數(shù)據(jù)實(shí)際系統(tǒng)中的投影操作Oracle 、DB2、Sybase ASE用排序的方法Informix用基于Hashing的方法 Sql Server、Sybase Asiq兩種方法都提供方法Join 操作Select *From Reserves R, Sailors SWhere R.sid=S.sidRSJoin操作相當(dāng)于一個(gè)叉乘操作加上一個(gè)選擇和投影操作，所以Join操作的結(jié)果一般比叉乘操作的結(jié)果小Join 操作Join操作的多種實(shí)現(xiàn)方法需要掃描整個(gè)表的方法嵌套循環(huán)join塊嵌套循環(huán)

53、join不需要掃描整個(gè)表的方法Sort-merge join方法Hash join方法分析實(shí)例（R join S）R中有M個(gè)頁，每頁有PR個(gè)元組S中有N個(gè)頁，每頁有PS個(gè)元組Join 操作實(shí)際系統(tǒng)中的Join操作Oracle 8支持基于頁的嵌套循環(huán)、Sort-merge、和Hash JoinSql Server支持基于頁的嵌套循環(huán)、索引嵌套循環(huán)、Sort-merge、Hash Join和Hash teamDB2支持基于塊的嵌套循環(huán)、Sort-merge、和Hash Join Sybase支持基于頁的嵌套循環(huán)、索引嵌套循環(huán)、Sort-merge、Hash Join和Join索引Informix支

54、持基于頁的嵌套循環(huán)、索引嵌套循環(huán)和Hash Join簡單嵌套循環(huán)循環(huán)JoinForeach tuple rR do Foreach tuple sS do if ri=sj then add to resultR為outer關(guān)系，S為inner關(guān)系代價(jià)分析：M+PR*M*N對(duì)前面的例子，有M=1000, PR=100，N=500,所以最后的代價(jià)為1000+5*107兩個(gè)優(yōu)化從M中每次讀一頁進(jìn)行Join,而不是一個(gè)，則代價(jià)公式為：M+M*Nouter關(guān)系選擇較小的表塊嵌套循環(huán)Join查詢Foreach Block of B-2 pages of R do Foreach Page of S do

55、 for all matching in-memory tuples r R-block and s S add to result基本思想將關(guān)系R分成長度為B-2的塊，每次調(diào)用一塊到緩沖區(qū)，遍歷S，讀入數(shù)據(jù)，并同緩沖區(qū)中的數(shù)據(jù)進(jìn)行Join這種方法可有效地減少對(duì)S的遍歷次數(shù)，如R可整個(gè)裝入緩沖區(qū)，則只需代價(jià)：M+N塊嵌套循環(huán)Join查詢?nèi)绾螌?duì)緩沖區(qū)中的數(shù)據(jù)做join將R中讀入緩沖區(qū)的數(shù)據(jù)存入Hash表，對(duì)每條讀入的S中的數(shù)據(jù)通過Hash變換后找到相應(yīng)的R中的數(shù)據(jù)，從而加快了速度代價(jià)分析：M+M/(B-2) *N對(duì)前面的例子，有M=1000,N=500,緩沖區(qū)大小為100頁，最后的代價(jià)為1000

56、+10*500=6000頁對(duì)前面的例子，若緩沖區(qū)大小為90頁，最后的代價(jià)為1000+12*500=7000頁對(duì)前面的例子，若緩沖區(qū)大小為100頁，sailer為outer關(guān)系，最后的代價(jià)為500+5*1000 =5500頁圖示DiskDiskouput bufferInput bufferB塊內(nèi)存緩沖區(qū)HB-2塊Ri的Hash表Hash函數(shù)塊嵌套循環(huán)Join查詢塊訪問的影響可以增加inner關(guān)系的緩沖區(qū)的大小，這樣可以減少尋找page的時(shí)間可以考慮double Buffering 的方法索引嵌套循環(huán) JoinForeach tuple rR do Foreach tuple sS where

57、ri=sj add to result基本思想是在Inner關(guān)系的訪問上用索引，用極少的代價(jià)找到滿足條件的元組代價(jià)分析如果索引是B+樹，則找到相應(yīng)的也節(jié)點(diǎn)只需要2-4次讀寫，如果索引是Hash表，則找到相應(yīng)的也節(jié)點(diǎn)只需要1-2次讀寫如果索引是簇聚的，讀取滿足條件的元組的代價(jià)很少，否則為滿足條件的元組的個(gè)數(shù)索引嵌套循環(huán) Join對(duì)前面的例子，有M=1000, PR=100，N=500， Ps=80若在Sailer上有Hash的索引，訪問所需的頁需要1.2次讀寫，因?yàn)閟id是鍵，每次只有一個(gè)結(jié)果，代價(jià)為1000+100000*1.2若在Reserves上有Hash的索引，訪問所需的頁需要1.2次讀

58、寫，假設(shè)每個(gè)sailer對(duì)應(yīng)的reserves均在一個(gè)頁中，代價(jià)為500+40000*1.2若在Reserves上有Hash索引，按平均每個(gè)sailer對(duì)應(yīng)的reserves應(yīng)為2.5個(gè)，所需的讀寫代價(jià)根據(jù)簇聚的情況不同為1-2.5,代價(jià)為500+40000*1 500+40000*2.5Sort-Merge Join基本想法首先將兩個(gè)關(guān)系進(jìn)行排序，并根據(jù)排序的結(jié)果進(jìn)行分區(qū)，每個(gè)分區(qū)在join的屬性上是相同的。用兩個(gè)指針對(duì)兩個(gè)關(guān)系分別從前向后掃描，找到相同的分區(qū)，對(duì)聯(lián)接屬性值相同的分區(qū)進(jìn)行Join操作，輸出結(jié)果算法proc smjoin(R,S,Ri=Sj)If R not sorted on

59、 attribute I,sort it;If S not sorted on attribute j,sort it;Tr=first tuple in R;Ts=first tuple in S;Gs=first tuple in S;While Treof and Gseof dowhile Tri Gsj doGs=next tuple in S after Gs;算法 Ts=Gs; While Tri= Gsj do Ts=Gs while Tsi= Gsj do addto result Ts= next tuple in S after Ts; Tr=next tuple in

60、R after Tr; Gs=Ts例子sidsnameratingage22dustin745.028Yuppy935.031Lubber855.536Lubber636.044Guppy535.058Rusty1035.0sidbiddayrname2810312/04/96Guppy2810311/03/96Yuppy3110110/10/96Dustin3110210/12/96Lubber3110110/11/96Lubber5810311/12/96DustinSailorsReservesSort-Merge Join代價(jià)分析R排序的時(shí)間是O(MlogM), S排序的時(shí)間是O(Nl