數(shù)據(jù)庫(kù)系統(tǒng)實(shí)現(xiàn)實(shí)現(xiàn)技術(shù)

第九章數(shù)據(jù)庫(kù)系統(tǒng)實(shí)現(xiàn)實(shí)現(xiàn)技術(shù)9.1數(shù)據(jù)庫(kù)的存儲(chǔ)結(jié)構(gòu)存儲(chǔ)介質(zhì)內(nèi)外存數(shù)據(jù)交換數(shù)據(jù)庫(kù)引擎中的存儲(chǔ)管理器，主要兩個(gè)部件：緩沖區(qū)管理器和文件管理器。數(shù)據(jù)庫(kù)運(yùn)行時(shí)，內(nèi)外存間要頻繁地進(jìn)行數(shù)據(jù)交換，每交換一次數(shù)據(jù)稱(chēng)為一次I/O操作。數(shù)據(jù)庫(kù)系統(tǒng)需OS支持進(jìn)行I/O。I/O操作是很慢的，數(shù)據(jù)調(diào)出外存要緩存在緩沖區(qū)中供后續(xù)的操作使用(讀/寫(xiě))。讀不命中或?qū)懡Y(jié)果按策略更新時(shí)進(jìn)行I/O。每次交換的數(shù)據(jù)量稱(chēng)為一個(gè)數(shù)據(jù)塊，一個(gè)塊可以等于一個(gè)或幾個(gè)磁盤(pán)塊。塊大對(duì)順序訪(fǎng)問(wèn)有利，對(duì)隨機(jī)訪(fǎng)問(wèn)不利。內(nèi)存中緩沖區(qū)的大是若干個(gè)數(shù)據(jù)塊。數(shù)據(jù)庫(kù)的存儲(chǔ)結(jié)構(gòu)磁盤(pán)冗余陣列(RAID)RAID是數(shù)據(jù)庫(kù)服務(wù)器最常用的外存儲(chǔ)介質(zhì)，有若干同樣的磁盤(pán)組成的陣列，從RAID0-RAID8有多種組合方式。通過(guò)冗余改善可靠性。同一數(shù)據(jù)同時(shí)寫(xiě)入兩個(gè)磁盤(pán)若干個(gè)磁盤(pán)數(shù)據(jù)用一個(gè)磁盤(pán)保存校驗(yàn)位。通過(guò)數(shù)據(jù)條塊化提高速度數(shù)據(jù)大體均勻地存放于若干磁盤(pán)上。當(dāng)多用戶(hù)請(qǐng)求數(shù)據(jù)庫(kù)數(shù)據(jù)時(shí)，I/O操作可以隨機(jī)地落在不同的磁盤(pán)，磁盤(pán)陣列并行I/O從而提高速度。備份數(shù)據(jù)和歷史數(shù)據(jù)通過(guò)網(wǎng)絡(luò)存儲(chǔ)存放到物理上分離的地方(防火、水、震等)移動(dòng)硬盤(pán)或光盤(pán)、磁帶等大容量離線(xiàn)存儲(chǔ)設(shè)備。數(shù)據(jù)庫(kù)的存儲(chǔ)結(jié)構(gòu)文件內(nèi)記錄的存儲(chǔ)數(shù)據(jù)庫(kù)數(shù)據(jù)以文件形式在外存中存儲(chǔ)。數(shù)據(jù)庫(kù)的邏輯記錄在物理文件中如何實(shí)現(xiàn)，是記錄的存儲(chǔ)方法問(wèn)題。定長(zhǎng)記錄格式：每個(gè)數(shù)據(jù)庫(kù)記錄占有定長(zhǎng)文件記錄。例：Employer(Enamechar(10),eNochar(10),Salaryreal)設(shè)一個(gè)實(shí)數(shù)占8字節(jié)，則一個(gè)記錄28字節(jié)，文件的邏輯機(jī)構(gòu)為：刪除操作空位處理其它記錄依次上移最后記錄填補(bǔ)空位被刪空位鏈接、插入時(shí)用記錄0LiuA-1026000記錄1WenB-3067000記錄2HeF-2578000記錄3ZhangA-2146000記錄4ZhouC-3437500記錄5LiuB-2158000數(shù)據(jù)庫(kù)的存儲(chǔ)結(jié)構(gòu)變長(zhǎng)紀(jì)錄：每條數(shù)據(jù)庫(kù)記錄長(zhǎng)度不同例：Salsepson的屬性adress是變長(zhǎng)的Salseperson(empID:char(3),empName:char(8),sex:char(1),birthday:date,spTelNo:number(12),address:varchar(50))字符串格式：把每個(gè)數(shù)據(jù)庫(kù)記錄看作是連續(xù)的字節(jié)串，尾部加記錄尾標(biāo)記符。(大多數(shù)操作系統(tǒng)支持按行存取文件)下面的關(guān)系empIDempNamesexBirthdayspTelNoaddresssp1劉女士F70-1-20082354北京市宣武區(qū)牛街街道雙槐里小區(qū)22樓2-101

100028sp2李先生M67-5-2213146北京市海淀區(qū)玉泉路甲19號(hào)100049sp3何女士F62-9-7352210山東省日照市276534數(shù)據(jù)庫(kù)的存儲(chǔ)結(jié)構(gòu)下述文件存儲(chǔ)是字符串格式0sp1│劉女士│F│70-1-20北京市宣武區(qū)牛街街道雙槐里小區(qū)22樓2-101│1370100028

1│┴│1sp2│李先生│M│67-5-22北京市海淀區(qū)玉泉路甲19號(hào)100049│┴│2sp3│何女士│F│62-9-7山東省日照市276534│┴│字符串格式的缺點(diǎn)被刪除的位置難以重新利用。某記錄要伸長(zhǎng)很困難(移動(dòng)大量記錄)。改進(jìn)：分槽式頁(yè)結(jié)構(gòu)(shottedpagestructure)記錄從塊的尾部鄰接存放。中間是自由空間(伸長(zhǎng)記錄用)。塊的開(kāi)始是塊首部，記錄塊中記錄數(shù)、每個(gè)記錄大小和位置。分槽式變長(zhǎng)記錄結(jié)構(gòu)變長(zhǎng)記錄的定長(zhǎng)表示預(yù)留空間(按最大)固定塊+溢出塊格式數(shù)據(jù)庫(kù)的存儲(chǔ)結(jié)構(gòu)sp1劉女士F70-1-20082354sp2李先生M67-5-2213146sp3何女士F62-9-7352210北京市宣武區(qū)牛街街道雙槐里小區(qū)22樓2-101

100028┴北京市海淀區(qū)玉泉路甲19號(hào)100049┴山東省日照市276534┴固定塊溢出塊數(shù)據(jù)庫(kù)的存儲(chǔ)結(jié)構(gòu)文件內(nèi)記錄的組織一個(gè)文件包含了成千上萬(wàn)個(gè)記錄，這些記錄按什么順序或方式安排，是數(shù)據(jù)庫(kù)記錄在文件內(nèi)的組織問(wèn)題。對(duì)某種組織的文件怎樣去查找、插入和刪除，是文件中記錄的存取方法問(wèn)題。不同的組織方式存取效率有很大差別。記錄的組織方式堆文件組織：記錄可以放在文件的任何位置，以輸入順序?yàn)樾颉h除、插入操作不需移動(dòng)數(shù)據(jù)。順序文件組織：記錄按查找鍵值的升序或降序的順序邏輯存儲(chǔ)的。一般使用指針鏈結(jié)構(gòu)。散列文件組織(hashingfile)：某個(gè)屬性值通過(guò)哈希函數(shù)求得的值作為記錄的存儲(chǔ)地址。聚類(lèi)文件組織：一個(gè)文件可存儲(chǔ)多個(gè)有聯(lián)系的關(guān)系，有聯(lián)系的記錄存儲(chǔ)在同一塊內(nèi)，以提高I/O速度。數(shù)據(jù)庫(kù)的存儲(chǔ)結(jié)構(gòu)順序文件組織記錄的物理順序和查找鍵值一致：插入、刪除需移動(dòng)數(shù)據(jù)。用指針邏輯鏈接：插入：找到鍵值位置；插入到空閑位置；修改指針；刪除：修改指針；回收空閑位置。記錄0HeF-257800記錄1LiuB-2158000記錄2LiuA-1026000記錄3WenB-3067000記錄4ZhangA-2146000記錄5ZhouC-3437500記錄0HeF-257800記錄1LiuB-2158000記錄2LiuA-1026000記錄4WenB-3067000記錄5ZhangA-2146000記錄6ZhouC-3437500記錄3MaB-547500數(shù)據(jù)庫(kù)的存儲(chǔ)結(jié)構(gòu)聚類(lèi)文件組織聚類(lèi)文件的組織方式與查詢(xún)的類(lèi)型有關(guān)，一個(gè)文件內(nèi)有兩個(gè)或多個(gè)關(guān)系的記錄類(lèi)型。例：教學(xué)數(shù)據(jù)庫(kù)中的關(guān)系S和SC，經(jīng)常進(jìn)行自然連接查詢(xún)操作，如SELECT

S.S#,Sname,C#,Grade

FROMS,SCWHERES.S#=SC.S#當(dāng)數(shù)據(jù)量很大時(shí)，兩個(gè)文件內(nèi)記錄的連接操作是很慢的。聚類(lèi)文件格式如右圖：關(guān)系S和SCS#SnameAgeSexS1Liu21FS2Wang20MS3Chen22MS#C#GradeS1C180S1C270S3C190S3C285S3C395記錄0S1Liu21FS1C180S1C270記錄1S2Wang20M記錄2S3Chen22MS3C190S3C285S3C395聚類(lèi)文件數(shù)據(jù)庫(kù)的存儲(chǔ)結(jié)構(gòu)索引技術(shù)當(dāng)文件中記錄的數(shù)目和數(shù)據(jù)量很大時(shí)，直接查找速度會(huì)很慢。必須建立索引機(jī)制。索引是獨(dú)立于主文件記錄的一個(gè)只含索引屬性的小的文件，且按索引值排序，查找速度可很快。常用的索引或一、二級(jí)索引可以讀入緩沖區(qū)以加快速度。索引分類(lèi)有序索引：根據(jù)記錄中某種排序順序建立的索引。散列索引：根據(jù)記錄中某個(gè)屬性值，通過(guò)散列函數(shù)得到值作為存儲(chǔ)空間的桶號(hào)。有序索引分類(lèi)：主文件可建立幾個(gè)索引文件。主索引(聚類(lèi)索引)：索引的查找鍵值的順序與主文件順序一致。這種文件稱(chēng)作索引順序文件。主索引只有一個(gè)。非聚類(lèi)索引：索引的查找鍵值的順序與主文件順序不一致。數(shù)據(jù)庫(kù)的存儲(chǔ)結(jié)構(gòu)主索引稠密索引：對(duì)于主文件中的每一個(gè)查找鍵值建立一個(gè)索引記錄(索引項(xiàng))，索引記錄包括查找鍵值和指向具有該值的主文件中第一個(gè)記錄的指針。例：稀疏索引：在主文件中，若個(gè)個(gè)查找鍵值才建立一個(gè)所以記錄，索引記錄的內(nèi)容與稠密索引相同。例：要找到Liu，先

找到He指向的主文件

然后順鏈找到Liu。HeF-2577000LiuB-2158000LiuA-1026000WenB-3067000ZhangA-2146000ZhangB-4676000ZhouC-3438000HeLiuWenZhangZhouHeZhang數(shù)據(jù)庫(kù)的存儲(chǔ)結(jié)構(gòu)多級(jí)索引：即使采用稀疏索引，可能建成的索引還是很大，以致于查詢(xún)效率不高。例：主文件100000個(gè)記錄，每塊可存儲(chǔ)10個(gè)記錄，需10000個(gè)數(shù)據(jù)塊。若以塊為單位建立稀疏索引，索引需10000項(xiàng)。雖然索引記錄比主記錄小得多，如每塊可存100個(gè)索引項(xiàng)，索引塊仍需100塊，緩沖區(qū)就很難放得下。解決的辦法是對(duì)主索引再建立一級(jí)索引，

如圖所示的二級(jí)索引。如果外層索引數(shù)據(jù)量還是太大，可建立3級(jí)、4級(jí)

索引。多級(jí)索引可用B+樹(shù)或B樹(shù)實(shí)現(xiàn)。數(shù)據(jù)庫(kù)的存儲(chǔ)結(jié)構(gòu)索引的更新刪除：為了在主文件中刪除一條記錄，需①找到主文件記錄，刪除。②如果符合索引鍵值的記錄有多個(gè)，索引不用修改。③否則，對(duì)稠密索引，刪除相應(yīng)的索引項(xiàng)；對(duì)稀疏索引，如果被刪記錄的索引值在索引塊中出現(xiàn)，則用主文件被刪記錄的下一個(gè)記錄的查找鍵A替換，若A已出現(xiàn)在索引塊，則刪除被刪記錄的對(duì)應(yīng)多音鍵。插入：①用插入記錄的查找鍵找到插入位置，執(zhí)行主文件插入。②對(duì)稠密索引且查找鍵未在索引塊出現(xiàn)，在索引中插入。③對(duì)稀疏索引，每塊數(shù)據(jù)對(duì)應(yīng)一個(gè)索引項(xiàng)。若數(shù)據(jù)塊有空閑放得下新數(shù)據(jù)，不用修改索引；否則，加入新數(shù)據(jù)塊，在索引塊中插入一個(gè)新索引項(xiàng)。數(shù)據(jù)庫(kù)的存儲(chǔ)結(jié)構(gòu)輔助索引在其他屬性上建立索引，也可以提高以這些屬性為查找鍵值的查找速度，稱(chēng)為輔助索引。但由于相同查找鍵值的記錄分散在主文件中(已按主索引順序存儲(chǔ))，輔助索引需新的結(jié)構(gòu)。輔助索引的指針不直接指向主文件記錄，而是指向一個(gè)桶，桶內(nèi)存放指向具有同一查找鍵值的主記錄指針。輔助索引(最末級(jí))不能是稀疏索引。例：在Salary建索引HeF-2577000LiuB-2158000LiuA-1026000WenB-3067000ZhangA-2146000ZhangB-4676000ZhouC-3438000600070008000數(shù)據(jù)庫(kù)的存儲(chǔ)結(jié)構(gòu)B+樹(shù)索引B+樹(shù)的結(jié)構(gòu)：一顆M階的B+樹(shù)，按下列方式組織：①每個(gè)結(jié)點(diǎn)至多有m-1個(gè)查找鍵值和m個(gè)指針。如下圖②葉結(jié)點(diǎn)指針指向主文件中的記錄或桶。③非葉結(jié)點(diǎn)指針數(shù)m/2≤n≤m，Pi指向的子樹(shù)中所有鍵值均小于Ki，而大于等于Ki-1。例：下圖是一顆

三階B+樹(shù)P1K1P2…Pn-1Kn-1Pn對(duì)于m階、K個(gè)鍵的B+樹(shù)，查找次數(shù)≤logm/2K第九章數(shù)據(jù)庫(kù)系統(tǒng)實(shí)現(xiàn)實(shí)現(xiàn)技術(shù)9.2事務(wù)事務(wù)(Transaction)的概念定義：事務(wù)是DBMS中一個(gè)邏輯工作單元，通常由一組數(shù)據(jù)庫(kù)的操作組成，滿(mǎn)足原子性、一致性、隔離性和持久性四個(gè)性質(zhì)。事務(wù)的ACID性質(zhì)原子性(Atomic)：構(gòu)成事務(wù)的所有操作要么全部執(zhí)行，反映到數(shù)據(jù)庫(kù)中；要么全部不執(zhí)行，沒(méi)有對(duì)數(shù)據(jù)庫(kù)中的數(shù)據(jù)造成影響。一致性(Consistency)：事務(wù)的操作使數(shù)據(jù)庫(kù)從一個(gè)一致?tīng)顟B(tài)(所有對(duì)象滿(mǎn)足各自的約束)轉(zhuǎn)變?yōu)榱硪粋€(gè)一致?tīng)顟B(tài)。隔離性(Isolation)：在多用戶(hù)環(huán)境下，事務(wù)的執(zhí)行不受同時(shí)執(zhí)行的其它事務(wù)的影響。例：多售票點(diǎn)售票的例子。持久性(Durability)：一個(gè)事務(wù)如果成功執(zhí)行，其對(duì)數(shù)據(jù)庫(kù)的影響是持久的，不因故障而失效。事務(wù)事務(wù)的例子例1：向客戶(hù)1003銷(xiāo)售pCode=101的產(chǎn)品10個(gè)UpdateProductsetqty=qty-10wherepCode=‘101’;InsertintoOrder(‘25’,’1002’,2016-3-11,2016-3-12);InsertintoOrderdetail(‘25’,’101’,10,0.05);Commit;例2：銀行數(shù)據(jù)庫(kù)的轉(zhuǎn)賬事務(wù)，從賬號(hào)A轉(zhuǎn)50元到賬戶(hù)BRead(A);A:=A-50;Write(A);Read(B);B:=B+50;Write(B);Commit;事務(wù)事務(wù)的標(biāo)識(shí)由begintransaction語(yǔ)句和endtransection顯式定義事務(wù)的開(kāi)始和結(jié)束。隱式定義：從一個(gè)讀寫(xiě)語(yǔ)句開(kāi)始，遇到rollback或commit語(yǔ)句時(shí)終止(SQL-92)。Commit：提交，確認(rèn)事務(wù)執(zhí)行。Rollback：回滾，將此前的執(zhí)行的操作影響恢復(fù)到操作前。事務(wù)的大小與回滾機(jī)制事務(wù)執(zhí)行過(guò)程中出現(xiàn)錯(cuò)誤、或不可執(zhí)行的操作(如訂單已插入、結(jié)賬時(shí)發(fā)現(xiàn)賬戶(hù)余額不足)需回滾。因此DBMS將事務(wù)的執(zhí)行緩存在回滾段(表空間一個(gè)區(qū)域)，執(zhí)行rollback或commit后清除?；貪L段大小、回滾緩沖區(qū)大小影響事務(wù)的大小、并發(fā)事務(wù)數(shù)和執(zhí)行效率。事務(wù)如何保證上述事務(wù)滿(mǎn)足ACID性質(zhì)？回滾機(jī)制和故障恢復(fù)機(jī)制保證了事務(wù)的原子性。如果一個(gè)事務(wù)沒(méi)有執(zhí)行到commit，前面的操作不反映到數(shù)據(jù)庫(kù)數(shù)據(jù)中。只要事務(wù)定義的合理，其原子性能保證結(jié)果得一致性。持久性需要數(shù)據(jù)庫(kù)的故障恢復(fù)系統(tǒng)將發(fā)生故障時(shí)尚未將操作結(jié)果體現(xiàn)到數(shù)據(jù)庫(kù)中的操作進(jìn)行適當(dāng)處理，以確保操作結(jié)果正確。關(guān)于持久性，與數(shù)據(jù)庫(kù)文件系統(tǒng)的緩存機(jī)制密切相關(guān)。因?yàn)閿?shù)據(jù)的讀寫(xiě)操作是在緩沖區(qū)進(jìn)行的，在還沒(méi)有寫(xiě)回磁盤(pán)文件前發(fā)生故障，就出現(xiàn)了持久性問(wèn)題。故障恢復(fù)機(jī)制：在事務(wù)的執(zhí)行過(guò)程中，如果發(fā)生了故障，系統(tǒng)采取適當(dāng)措施取消一個(gè)未完成的事務(wù)對(duì)數(shù)據(jù)庫(kù)的影響，或?qū)⒁呀?jīng)執(zhí)行完的事務(wù)結(jié)果反映的數(shù)據(jù)庫(kù)存儲(chǔ)文件中。事務(wù)的隔離性需要復(fù)雜的并發(fā)控制機(jī)制來(lái)實(shí)現(xiàn)。第九章數(shù)據(jù)庫(kù)系統(tǒng)實(shí)現(xiàn)實(shí)現(xiàn)技術(shù)9.3并發(fā)控制為什么需要并發(fā)事務(wù)為有效響應(yīng)多用戶(hù)實(shí)時(shí)數(shù)據(jù)庫(kù)操作，提高吞吐量，數(shù)據(jù)庫(kù)事務(wù)內(nèi)的操作都是交錯(cuò)執(zhí)行的，即并發(fā)執(zhí)行事務(wù)。因?yàn)樘岣咄掏铝浚菏聞?wù)的吞吐量是指單位時(shí)間內(nèi)平均完成的事務(wù)個(gè)數(shù)。一個(gè)事務(wù)設(shè)計(jì)兩類(lèi)操作：一類(lèi)I/O操作，如從磁盤(pán)讀寫(xiě)數(shù)據(jù)，速度較慢；一類(lèi)是CPU操作，速度較快。如果允許不同事務(wù)的讀、寫(xiě)、CPU運(yùn)算、網(wǎng)絡(luò)傳輸?shù)炔僮鞑⑿袌?zhí)行，則可有效提高事務(wù)的吞吐量。進(jìn)程調(diào)度都是這樣做的。有利于短事務(wù)的快速執(zhí)行：事務(wù)交錯(cuò)執(zhí)行有利于短事務(wù)的快速完成，從而縮短事務(wù)的平均完成時(shí)間。并發(fā)控制并發(fā)事務(wù)調(diào)度調(diào)度：多個(gè)事務(wù)包含的操作之間，按照一定的順序執(zhí)行的方式稱(chēng)為一種調(diào)度。調(diào)度類(lèi)型：如果每個(gè)事務(wù)的草阿諾與其它事務(wù)的操作的執(zhí)行順序沒(méi)有交錯(cuò)，則稱(chēng)為串行調(diào)度；反之，稱(chēng)為并發(fā)調(diào)度。假設(shè)事務(wù)的定義是正確的，即可保證數(shù)據(jù)庫(kù)從一個(gè)一致?tīng)顟B(tài)轉(zhuǎn)換為另一個(gè)一致的狀態(tài)，

那么，串行調(diào)度的最終結(jié)果

一定是一致?tīng)顟B(tài)。但并發(fā)調(diào)度若不加適當(dāng)控制，

則有可能出現(xiàn)異常，使

數(shù)據(jù)庫(kù)的一致性遭到破壞。T1T2Read(A)A:=A-1Read(A)A:=A-1Write(A)Write(A)Read(C)并發(fā)控制并發(fā)調(diào)度異常丟失更新異常-寫(xiě)寫(xiě)(ww)沖突即重寫(xiě)未提交數(shù)據(jù)(overwritinguncommitteddata)，指的是事務(wù)T1修改了對(duì)象A的值，在T1尚未提交前，事務(wù)T2頁(yè)修改了A的值，將T1對(duì)A的修改覆蓋了。設(shè)A是庫(kù)存，初值500，T1和T2

分別銷(xiāo)售100、200，正確的結(jié)

果是200。但右圖的調(diào)度執(zhí)行結(jié)

果為300。T1T2Read(A)A:=A-100Read(A)A:=A-200Write(A)Write(A)commitWrite(A)commit并發(fā)控制讀臟數(shù)據(jù)異常-寫(xiě)讀(WR)異常即讀未提交的數(shù)據(jù)(readinguncommitteddata)，指的是事務(wù)T2讀取了被T1修改但尚未提交的數(shù)據(jù)。設(shè)A是庫(kù)存、B是銷(xiāo)量，T1完

成銷(xiāo)售100，A初值100，B初值500；T2統(tǒng)計(jì)庫(kù)存量加銷(xiāo)量(應(yīng)與

進(jìn)貨量平衡)。T2正確結(jié)果(串行順序不同，結(jié)果可不同)：先T1后T2，A=0,B=600;先T2后T1，A=100,B=500。C都是600。但右圖的調(diào)度C=500，A=0，B=500。T1T2Read(A)A:=A-100Write(A)Read(A)Read(B)C:=A+BCommitRead(B)B:=B+100Write(B)Commit并發(fā)控制不能重復(fù)讀異常-讀寫(xiě)(RW)沖突是由讀寫(xiě)(RW)沖突導(dǎo)致的。指的是一個(gè)事務(wù)T1讀取某個(gè)數(shù)據(jù)對(duì)象A，但是在T1尚未提交時(shí)，A被另外一個(gè)事務(wù)T2修改。若T1再讀A得到的是與前一次不同的值。讀臟數(shù)據(jù)和不可恢復(fù)調(diào)度讀臟數(shù)據(jù)異常也可能由于回滾造成。T1將銷(xiāo)量A(初值500)增加100，T2讀取銷(xiāo)售數(shù)據(jù)加到總銷(xiāo)量B(初值1000)上。T1對(duì)A的修改被取消，但回滾前被T2

讀出，這是臟數(shù)據(jù)。(1500→1600)T1T2Read(A)Read(A)A:=A+500Write(A)CommitRead(A)CommitT1T2Read(A)A:=A+100Write(A)Read(A)Read(B)B:=B+AWrite(B)Commitrollback并發(fā)控制基于封鎖的并發(fā)控制技術(shù)為了避免并發(fā)調(diào)度帶來(lái)的各種異常以及不可恢復(fù)調(diào)度情況的發(fā)生，可以使用基于封鎖(lock)的并發(fā)控制機(jī)制對(duì)事務(wù)之間的相互作用加以控制。封鎖可以看作是對(duì)一個(gè)數(shù)據(jù)庫(kù)對(duì)象進(jìn)行操作的許可。一個(gè)事務(wù)在對(duì)某對(duì)象進(jìn)行操作之前必須按照某種封鎖協(xié)議先獲得該對(duì)象的某種封鎖，而能否獲得封鎖要根據(jù)對(duì)同一對(duì)象的操作是否存在沖突決定。封鎖的類(lèi)型及相容矩陣共享鎖(sharelock,S鎖)

通常是對(duì)讀對(duì)象加的鎖排他鎖(exclusivelock,X鎖)

對(duì)要寫(xiě)的對(duì)象施加的鎖S鎖X鎖S鎖truefalseX鎖falsefalse并發(fā)控制嚴(yán)格的兩段鎖協(xié)議(strict2PL)如果一個(gè)事務(wù)T需要讀取一個(gè)數(shù)據(jù)庫(kù)對(duì)象，那么它必須首先獲得對(duì)該對(duì)象的共享鎖；如果T要修改一個(gè)數(shù)據(jù)庫(kù)對(duì)象，它必須首先獲得對(duì)該對(duì)象的排他鎖。T申請(qǐng)到的所有封鎖一直擁有，直到T結(jié)束才釋放。定義：如果事務(wù)的某一并行調(diào)度對(duì)數(shù)據(jù)庫(kù)作用的結(jié)果與某一串行調(diào)度相同，則認(rèn)為此調(diào)度是正確的，稱(chēng)為可串行化調(diào)度。嚴(yán)格的兩段鎖協(xié)議可保證調(diào)度的可串行化。例：前例不能重復(fù)讀異常，實(shí)施嚴(yán)格

兩段鎖的結(jié)果是T1、T2完全串行。T1T2Slock(A)Xlock(A)Read(A)Read(A)CommitXlock(A)Read(A)A:=A+500Write(A)Commit并發(fā)控制如果兩個(gè)事務(wù)的操作不存在沖突，兩段鎖協(xié)議仍然可以使操作交錯(cuò)執(zhí)行。例但嚴(yán)格兩段鎖協(xié)議使并發(fā)度降低了。兩段鎖協(xié)議(可提前釋放封鎖)如果一個(gè)事務(wù)T需要讀取一個(gè)數(shù)據(jù)庫(kù)

對(duì)象，那么它必須首先獲得對(duì)該對(duì)象

的共享鎖；如果T要修改一個(gè)數(shù)據(jù)庫(kù)對(duì)

象，它必須首先獲得對(duì)該對(duì)象的排他鎖。T釋放了一個(gè)封鎖后，就不能在獲得

新的封鎖。兩段鎖協(xié)議也可以使調(diào)度串行化，

但可能引發(fā)級(jí)聯(lián)回滾。T1T2Slock(A)Read(A)Slock(A)Read(A)Xlock(B)Read(B)Write(B)commitXlock(C)Read(C)Write(C)commit并發(fā)控制兩段鎖協(xié)議例子T1沒(méi)有結(jié)束，unlock(A)后T2即可取得A的X鎖，從而并發(fā)執(zhí)行。但若T2執(zhí)行完write(A)后，T1發(fā)生故障需要回滾，則

引發(fā)T2的級(jí)聯(lián)回滾。封鎖粒度申請(qǐng)封鎖的數(shù)據(jù)庫(kù)對(duì)象的大小

稱(chēng)為封鎖粒度。封鎖粒度有數(shù)據(jù)庫(kù)鎖、表級(jí)鎖、頁(yè)面鎖(物理單元)、行級(jí)鎖、和列級(jí)鎖。封鎖粒度越小，并發(fā)度越高，管理封鎖代價(jià)越高。T1T2Xlock(A)Read(A)Slock(B)Read(B)Write(A)Unlock(A)Xlock(C)…Xlock(A)Read(A)Write(A)Commit并發(fā)控制幻像問(wèn)題幻象問(wèn)題發(fā)生在表中的元組被插入或刪除的情況。例:T1查詢(xún)足球類(lèi)產(chǎn)品的總銷(xiāo)量A(初值100)和健美類(lèi)產(chǎn)品的總銷(xiāo)量B(200)；T2首先插入一行健美類(lèi)產(chǎn)品的銷(xiāo)售記錄(20)，然后再插入一條足球類(lèi)產(chǎn)品銷(xiāo)售記錄(10)。串行結(jié)果:T1T2=100,200;T2T1=110,220行級(jí)鎖結(jié)果：100,220，與任一串行結(jié)果不同。原因是T1讀取了一個(gè)之前并不存在的行(不存在插入操作不加鎖)，即所謂幻行。T1T2Slock(A)Read(A)Insert(t1)Slock(B)Read(B)Insert(t2)CommitCommit幻像問(wèn)題可采用表級(jí)鎖或?qū)λ饕渔i解決并發(fā)控制SQL-92規(guī)定的并發(fā)級(jí)別及可解決的并發(fā)調(diào)度異常Serializable:可保證調(diào)度的可串行化，默認(rèn)級(jí)別。Repeatableread:允許重復(fù)讀，兩次讀之間其它事務(wù)不能修改。Readcommitted:只能讀取已提交的數(shù)據(jù)。Readuncommitted:允許讀未提交數(shù)據(jù)。數(shù)據(jù)封鎖的申請(qǐng)和釋放是由DBMS自動(dòng)加入到事務(wù)中的。但SQL提供了設(shè)置某并發(fā)級(jí)別的命令。例：SQLServerSettransactionisolationlevelreadcommitted調(diào)度可解決異常丟失更新讀臟數(shù)據(jù)不可重復(fù)讀幻像SerializableYYYYRepeatablereadYYYNReadcommittedYYNNReaduncommittedYNNN并發(fā)控制Upgrade機(jī)制為了提高并發(fā)度，一種廣泛使用的加鎖、解鎖機(jī)制為：T對(duì)A進(jìn)行讀操作時(shí)，申請(qǐng)S鎖；當(dāng)要寫(xiě)該對(duì)象時(shí)，首先檢查T(mén)在A上是否有S鎖，若有，則用upgrade升級(jí)為X鎖，否則，直接申請(qǐng)排他鎖。例:T1T2Xlock(A)Read(A)Slock(B)Read(B)…Write(A)Unlock(A)Slock(A)Read(A)T1T2Slock(A)Read(A)Slock(B)Read(B)…Upgrade(A)Write(A)Unlock(A)Slock(A)Read(A)Unlock(A)提高了并發(fā)度第九章數(shù)據(jù)庫(kù)系統(tǒng)實(shí)現(xiàn)實(shí)現(xiàn)技術(shù)9.4數(shù)據(jù)庫(kù)的恢復(fù)緩沖區(qū)工作原理事務(wù)開(kāi)始執(zhí)行時(shí)在內(nèi)存都有一個(gè)專(zhuān)用的工作區(qū)，用于存放它訪(fǎng)問(wèn)和修改的數(shù)據(jù)。事務(wù)結(jié)束時(shí)釋放該緩沖區(qū)。一個(gè)事務(wù)要存取數(shù)據(jù)項(xiàng)X的值，首先需要將其讀到工作區(qū)相應(yīng)的變量x中，即read(X)。讀操作的步驟：檢查緩沖區(qū)中是否包含X的物理塊Bx，若無(wú)，發(fā)出input(Bx)輸入操作命令，將物理塊讀入緩存。讀Bx內(nèi)的X值到工作變量x中。Write(X)寫(xiě)操作的步驟：檢查緩沖區(qū)中是否包含X的物理塊Bx，若無(wú)，發(fā)出input(Bx)輸入操作命令，將物理塊讀入緩存。將工作變量的值x送入Bx的X數(shù)據(jù)項(xiàng)。數(shù)據(jù)庫(kù)的恢復(fù)何時(shí)寫(xiě)回外存(output(Bx))Write(X)并未將X寫(xiě)回外存。為什么？

Bx是一個(gè)數(shù)據(jù)塊，還包含其它數(shù)據(jù)，不急于I/O以提高系統(tǒng)性能。這是緩沖區(qū)的主要目的。當(dāng)緩沖區(qū)滿(mǎn)了，某read(X)不能在緩沖區(qū)命中時(shí)，才按一定算法將某個(gè)緩沖數(shù)據(jù)塊Bx寫(xiě)回外存，調(diào)入所需新數(shù)據(jù)塊。問(wèn)題如果一個(gè)事務(wù)在write(X)后提交了，在output(Bx)之前系統(tǒng)發(fā)生故障，則X得新值沒(méi)有反應(yīng)到數(shù)據(jù)庫(kù)內(nèi)，事務(wù)的持久性被破壞。一個(gè)事務(wù)執(zhí)行了Write(X)，但事務(wù)尚未提交，由于緩沖區(qū)替換導(dǎo)致output(Bx)執(zhí)行，半個(gè)事務(wù)的結(jié)果持久反應(yīng)到數(shù)據(jù)庫(kù)中，數(shù)據(jù)庫(kù)處于不一致?tīng)顟B(tài)，事務(wù)的原子性被破壞。解決：強(qiáng)制寫(xiě)和未提交事務(wù)的緩存不能寫(xiě)來(lái)避免，但緩沖的意義就沒(méi)有了。事實(shí)上這正是數(shù)據(jù)庫(kù)恢復(fù)技術(shù)要解決的問(wèn)題。數(shù)據(jù)庫(kù)的恢復(fù)故障類(lèi)型系統(tǒng)故障(systemcrash)又稱(chēng)為軟故障，是由軟、硬件原因?qū)е庐?dāng)前運(yùn)行的一個(gè)或多個(gè)事務(wù)無(wú)法正常進(jìn)行，但并未導(dǎo)致物理介質(zhì)上的數(shù)據(jù)遭到破壞。常見(jiàn)系統(tǒng)故障：斷電、程序邏輯錯(cuò)誤(如溢出)、死機(jī)等。系統(tǒng)故障導(dǎo)致的問(wèn)題是當(dāng)前和最近運(yùn)行的事務(wù)的狀態(tài)有可能丟失，為保證事務(wù)的原子性和持久性，需要采取相應(yīng)的恢復(fù)措施。介質(zhì)故障(mediafailure)又稱(chēng)硬故障，指的是由于磁盤(pán)等數(shù)據(jù)庫(kù)外存損壞導(dǎo)致的數(shù)據(jù)庫(kù)的一部分或全部數(shù)據(jù)無(wú)法訪(fǎng)問(wèn)。介質(zhì)故障影響正在訪(fǎng)問(wèn)這些數(shù)據(jù)的事務(wù)的正常執(zhí)行，使數(shù)據(jù)庫(kù)處于不一致?tīng)顟B(tài)。除事務(wù)異常外，數(shù)據(jù)庫(kù)系統(tǒng)不能工作，導(dǎo)致整個(gè)應(yīng)用系統(tǒng)癱瘓。數(shù)據(jù)庫(kù)的恢復(fù)日志(log、trail、journal)常用的數(shù)據(jù)庫(kù)故障恢復(fù)方法是基于日志的恢復(fù)技術(shù)。日志是有關(guān)DBMS所執(zhí)行的操作的一個(gè)歷史記錄。日志文件是一個(gè)記錄該歷史的物理文件，由若干日志記錄構(gòu)成。日志記錄的信息日志序列號(hào)；操作信息：如事務(wù)開(kāi)始、更新操作、事務(wù)提交、事務(wù)取消、事務(wù)終止等。例：更新日志記錄，包含事務(wù)標(biāo)識(shí)符、要更新數(shù)據(jù)項(xiàng)的標(biāo)識(shí)符(磁盤(pán)位置)、更新前的值(前像)、更新后的值(后像)等。先寫(xiě)日志原則為確保主要操作都被記錄在日志中，防止故障發(fā)生時(shí)丟失。任何對(duì)數(shù)據(jù)庫(kù)的更新(包括緩沖塊)被寫(xiě)回磁盤(pán)之前，必須保證其更新日志已寫(xiě)到日志文件(寫(xiě)到磁盤(pán)上)。數(shù)據(jù)庫(kù)的恢復(fù)循環(huán)日志：循環(huán)使用固定數(shù)目的日志文件來(lái)記錄日志。設(shè)日志文件數(shù)為n，日志依次寫(xiě)入這n個(gè)文件。n個(gè)文件寫(xiě)滿(mǎn)后循環(huán)使用，新日志記錄覆蓋舊記錄。n的大小應(yīng)保證被覆蓋的日志文件記錄的事務(wù)已經(jīng)結(jié)束且更新數(shù)據(jù)塊已寫(xiě)回外存。循環(huán)日志可恢復(fù)故障發(fā)生時(shí)涉及事務(wù)的完整性。但對(duì)介質(zhì)故障，無(wú)法恢復(fù)到故障發(fā)生時(shí)的狀態(tài)。歸檔日志：將循環(huán)日志覆蓋的日志文件歸檔保存。如保存到磁帶、移動(dòng)磁盤(pán)、網(wǎng)絡(luò)存儲(chǔ)等。數(shù)據(jù)庫(kù)的恢復(fù)系統(tǒng)故障的恢復(fù)系統(tǒng)故障可能導(dǎo)致的數(shù)據(jù)庫(kù)不一致?tīng)顟B(tài)故障發(fā)生時(shí)尚未結(jié)束的事務(wù)，它們的某些更新操作已經(jīng)寫(xiě)回外存。故障發(fā)生前已結(jié)束的事務(wù)，它們對(duì)數(shù)據(jù)庫(kù)的更新還未從緩沖區(qū)寫(xiě)回外存?；謴?fù)技術(shù)UNDO：撤銷(xiāo)事務(wù)外化(externalized)了的數(shù)據(jù)庫(kù)更新操作，使得從數(shù)據(jù)庫(kù)狀態(tài)看，這些操作好像從未執(zhí)行過(guò)。REDO：重復(fù)某些數(shù)據(jù)庫(kù)更新操作。如何確定哪些事務(wù)需要UNDO或REDO?比較耗時(shí)。一般使用檢查點(diǎn)機(jī)制。數(shù)據(jù)庫(kù)的恢復(fù)檢查點(diǎn)(checkpoint)機(jī)制系統(tǒng)按一定周期執(zhí)行檢查點(diǎn)操作：①將緩沖區(qū)中的數(shù)據(jù)強(qiáng)制寫(xiě)回磁盤(pán)的物理數(shù)據(jù)庫(kù)存儲(chǔ)中。②記錄檢查點(diǎn)日志記錄，其描述此時(shí)正在執(zhí)行的事務(wù)列表?；跈z查點(diǎn)的UNDO、REDO事務(wù)確認(rèn)從日志文件尾部向前搜索直到遇到第一個(gè)檢查點(diǎn)記錄，將該記錄中記錄的事務(wù)列表初