本文是2017年秋季北大研究生課程《數(shù)據(jù)庫原理與技術(shù)》的復(fù)習(xí)筆記铝穷。視角為數(shù)據(jù)庫系統(tǒng)自身的設(shè)計與實現(xiàn)，主要包括存儲佳魔、索引曙聂、查詢處理/優(yōu)化、事務(wù)鞠鲜、并發(fā)處理宁脊、恢復(fù)系統(tǒng)断国、并行數(shù)據(jù)庫7個部分。

基礎(chǔ)概念

關(guān)系代數(shù)6個基本操作

選擇榆苞，投影稳衬，并，差坐漏，笛卡爾積薄疚，重命名

建表代碼

create table department (
    dept_name varchar(20),
    building varchar(10),
    budget int);
insert into department values
    ('Comp. Sci.', 'Taylor', 100000);
create table instructor (
    id varchar(5),
    name varchar(20),
    dept_name varchar(20),
    salary int);
insert into instructor values
    ('33456', 'Gold', 'Comp. Sci.', 75000);
select dept_name, id, name
    from department natural join instructor;
select department.dept_name, instructor.name
    from department, instructor
    where department.dept_name = instructor.dept_name

視圖（子查詢）

從一個或多個表導(dǎo)出的虛擬的表，其內(nèi)容由查詢定義赊琳。具有普通表的結(jié)構(gòu)街夭，但是不實現(xiàn)數(shù)據(jù)存儲。
例子：

create view v_id as select id from instructor;
select * from v_id;
drop view v_id;

存儲和文件結(jié)構(gòu)

RAID（Redundant Array of Independent Disk）

高效性躏筏、可靠性板丽；RAID 1、RAID 5

文件組織

塊的概念

定長記錄：空閑鏈表

變長記錄：單條記錄的結(jié)構(gòu)（空位圖）+ 多條記錄的結(jié)構(gòu)（分槽的頁結(jié)構(gòu)）+ 記錄間的順序（堆趁尼、順序埃碱、散列）

多表聚簇文件組織：優(yōu)缺點

數(shù)據(jù)字典（數(shù)據(jù)庫元數(shù)據(jù)）

數(shù)據(jù)庫緩沖區(qū)

緩沖區(qū)概念：內(nèi)存中用于存儲磁盤塊拷貝的那一部分。

緩沖區(qū)替換策略：LRU酥泞、CLOCK乃正、MRU的適用場景

索引和散列

順序索引

索引項按序存儲

分類：主索引/輔助索引，稠密索引/稀疏索引

順序索引的插入/刪除婶博，多級索引

B+樹索引

順序索引的缺點：（不考慮重組）隨數(shù)據(jù)規(guī)模增大瓮具，查找性能下降；不適合頻繁的插入/刪除

B+樹定義凡人，查找

插入：1. 分裂時upper(n/2)個key給左邊名党； 2.分裂后，右邊節(jié)點的第一個key需要上移（如果是葉節(jié)點則copy up挠轴，非葉節(jié)點push up）

刪除：1. 葉節(jié)點合并時传睹，父節(jié)點先考慮和兄弟合并，合并不了需要拉上祖父節(jié)點重新分配指針岸晦；2. 如果合并時發(fā)現(xiàn)兄弟節(jié)點已滿欧啤，則在兩個節(jié)點間重新分配指針，這時候往往只需要再修改父節(jié)點中的key值

刪除操作可能導(dǎo)致B+樹非葉節(jié)點含有葉節(jié)點中并不存在的key值

通過復(fù)合多個碼來解決單一碼對應(yīng)記錄不唯一的問題

靜態(tài)散列

哈希函數(shù)會把記錄映射到一個固定大小的桶集合启上，桶溢出時采用溢出桶方案邢隧。隨著數(shù)據(jù)的增長效率會變差硫麻，解決方案：為每個桶預(yù)留x%空間凿跳，定期重組（代價很高）

動態(tài)散列（可擴(kuò)展散列茄螃、線性散列）

在靜態(tài)散列的基礎(chǔ)上增加一個桶地址表假残，根據(jù)記錄數(shù)量動態(tài)選取哈希值的前綴待诅，哈希值先映射到地址表中的表項在映射到桶介袜，插入/刪除會增加桶偎漫，視情況決定是否需要增加桶地址項再登。（在數(shù)據(jù)傾斜嚴(yán)重時，也需要溢出桶）

線性散列與可擴(kuò)展散列的區(qū)別在于桶地址表的擴(kuò)大速度付秕，前者每次增加一項兰珍，后者翻倍。同時询吴，線性散列分裂的未必是當(dāng)前溢出的桶俩垃。

位圖索引

適用于記錄中那些只能取少量屬性值的屬性，如：性別汰寓，工資分檔口柳。如有n條記錄，為每個可取的屬性值建立一個n維的0-1向量有滑。（有時跃闹，B+樹的葉子節(jié)點存儲這個搜索碼的位圖會比存儲記錄的地址節(jié)省空間

查詢處理

磁盤平均訪問時間Ts，磁盤傳輸時間Tr

查詢處理代價衡量：訪問磁盤次數(shù)毛好，傳輸?shù)拇疟P塊數(shù)

選擇操作

假設(shè)索引使用B+樹望艺，樹高度為H，以下操作的代價：

排序

外排序（M路歸并排序，內(nèi)存大小為M+1個塊）

連接

對表s和表r做自然連接吼驶，表s在磁盤上占S個塊惩激，表r占R個塊(S<R)，內(nèi)存大小M個塊蟹演。

塊嵌套循環(huán)連接

樸素的二重循環(huán)风钻，在小表可以放入內(nèi)存時，作為內(nèi)層循環(huán)可以提高效率酒请；否則應(yīng)當(dāng)把小表放在外層循環(huán)減少磁盤訪問時間（Ts>>Tr）

索引嵌套循環(huán)連接

在內(nèi)層循環(huán)時骡技，使用索引而非遍歷來查找對應(yīng)記錄，如果用B+樹組織索引羞反，這樣磁盤訪問次數(shù)會正比于記錄數(shù)布朦，在實際中未必比樸素的二重循環(huán)快。

假設(shè)r為外表昼窗，有Nr條記錄是趴，B+樹高度為h

歸并連接（sort-merge join）

對表r和s先按照連接屬性排序，再類似歸并排序的方法讀進(jìn)內(nèi)存合并膏秫。假設(shè)一次讀進(jìn)Br個r表塊和Bs個s表數(shù)據(jù)塊:

散列連接

在連接屬性上建立散列函數(shù)右遭，只有被分到同一個桶的記錄才需要考慮連接做盅。對于在同一個桶內(nèi)的r表記錄和s表記錄缤削，為其中一個創(chuàng)建哈希索引（build phase）窘哈，用另外一個的記錄來探查連接值相等的記錄（probe phase）

遞歸劃分/混合散列連接

表達(dá)式計算

兩種方式：物化和流水線

查詢優(yōu)化

為了找到代價最小的查詢執(zhí)行計劃，查詢優(yōu)化器需要以下三步：1）產(chǎn)生邏輯上與給定表達(dá)式等價的表達(dá)式亭敢；2）對產(chǎn)生的表達(dá)式已不同的方式做注釋滚婉，產(chǎn)生不同的查詢計劃；3）估計執(zhí)行代價帅刀，選擇代價最小的一個計劃

表達(dá)式等價轉(zhuǎn)換

關(guān)系代數(shù)層面让腹，如：連接操作的交換律、結(jié)合律

表達(dá)式結(jié)果集大小估計

數(shù)據(jù)庫會存儲一些統(tǒng)計信息：

以及索引的一些統(tǒng)計信息（如：B+樹深度）用于估計查詢中中間結(jié)果的大小

執(zhí)行計劃選擇

1）基于代價的的搜索：通常搜索范圍大扣溺，在特定問題（如：連接順序）上可用巧妙的算法優(yōu)化骇窍；
2）基于啟發(fā)式規(guī)則的：盡早做選擇，投影（規(guī)則并不一定能減少代價锥余，但是會不考慮數(shù)據(jù)情況直接使用）
3）其他優(yōu)化方法：嵌套子查詢的優(yōu)化腹纳，物化視圖，top-K驱犹，連接極小化嘲恍，多查詢優(yōu)化，參數(shù)化查詢優(yōu)化

事務(wù)

ACID

原子性（Atomicity）雄驹、一致性（Consistency）佃牛、隔離性（Isolation）、持久性（Durability）

事務(wù)狀態(tài)

沖突可串行化

I和J是不同事務(wù)在同樣的數(shù)據(jù)項上的操作医舆，如果I俘侠、J中至少有一個是寫操作，則稱I和J是沖突的蔬将。在調(diào)度S中兼贡，如果相鄰的兩條指令沒有沖突，那么可以調(diào)換這兩條指令的順序得到一個等價的新調(diào)度S'娃胆。如果可以通過一系列的指令調(diào)換從當(dāng)前調(diào)度S得到某個串行的調(diào)度S'遍希，那么稱S是沖突可串行化的。

檢測方法：拓?fù)渑判?/p>

可恢復(fù)調(diào)度和無級連調(diào)度

可恢復(fù)調(diào)度：如果事務(wù)Tj讀取了事務(wù)Ti寫的值里烦，那么Tj必須在Ti提交之后提交

無級連調(diào)度：如果事務(wù)Tj讀取了事務(wù)Ti寫的值凿蒜，那么Ti的提交必須在Tj這一讀操作之前

事務(wù)隔離性級別

可串行化，可重復(fù)讀胁黑，已提交讀废封，未提交讀。前三種都只允許讀已提交的數(shù)據(jù)丧蘸，已提交讀不要求同一事務(wù)內(nèi)對同一數(shù)據(jù)項兩次讀的結(jié)果一樣漂洋，只要求讀已提交的數(shù)據(jù)。許多數(shù)據(jù)庫默認(rèn)的隔離性級別就是已提交讀。

并發(fā)控制

鎖的基本概念

共享鎖：事務(wù)T獲得了數(shù)據(jù)Q上的共享鎖刽漂，則T可讀但不可寫Q

排他鎖：事務(wù)T獲得了數(shù)據(jù)Q上的排他鎖演训，則T可以讀也可以寫Q

死鎖的例子，讀寫數(shù)據(jù)項完成后立即釋放鎖可能帶來的不一致現(xiàn)象贝咙，餓死的處理方法

兩階段鎖協(xié)議

該協(xié)議要求事務(wù)按照兩個階段申請/釋放鎖：1）增長階段（growing phase）：事務(wù)可以申請鎖样悟，不能釋放鎖；2）縮減階段（shrinking phase）：事務(wù)可以釋放鎖庭猩，但不能申請鎖窟她。

封鎖點：遵守兩階段鎖協(xié)議的事務(wù)獲得最后一把鎖后的時間點。

變種：嚴(yán)格兩階段鎖協(xié)議震糖，強兩階段鎖協(xié)議，帶鎖升級的兩階段鎖協(xié)議

死鎖處理

分為死鎖預(yù)防趴腋、死鎖檢測/恢復(fù)兩類方案吊说。

死鎖預(yù)防

1）要求事務(wù)開始時申請所有需要的鎖，結(jié)束后統(tǒng)一釋放
2）在數(shù)據(jù)項上強制加上偏序關(guān)系于样，如樹形協(xié)議
3）wait-die協(xié)議：基于非搶占機制疏叨。事務(wù)Ti需要事務(wù)Tj持有的數(shù)據(jù)項時，如果Ti老穿剖，那么Ti等待蚤蔓，否則Ti回滾
4）wound/wait協(xié)議：基于搶占機制。事務(wù)Ti需要事務(wù)Tj持有的數(shù)據(jù)項時糊余，如果Ti年輕秀又，那么Ti等待，否則Tj回滾（Tj被傷害）

死鎖檢測/恢復(fù)

有向圖的環(huán)檢測算法+選擇代價最小的事務(wù)回滾

多粒度

應(yīng)允許事務(wù)在不同粒度的數(shù)據(jù)上加鎖贬芥，如：數(shù)據(jù)庫吐辙、表、記錄蘸劈。這些數(shù)據(jù)可以組織成一棵樹昏苏，每次加鎖時不僅需要給當(dāng)前節(jié)點加鎖，還要給從當(dāng)前節(jié)點到根節(jié)點路徑上的所有節(jié)點加鎖威沫，因此引進(jìn)了3種新的意向鎖：
1）共享型意向鎖（IS）：表示當(dāng)前節(jié)點的后代節(jié)點中有共享鎖
2）排他型意向鎖（IX）：表示當(dāng)前節(jié)點的后代節(jié)點中有排他鎖
3）共享排他型意向鎖（SIX）：表示當(dāng)前節(jié)點為根的子樹顯示加了共享鎖贤惯，在后代節(jié)點持有排他鎖。

兼容性矩陣：

基于時間戳的協(xié)議

每個事務(wù)T開始執(zhí)行前被賦予一個時間戳TS(T)棒掠，時間戳決定了串行化順序孵构，如果TS(Ti)<TS(Tj)，系統(tǒng)需保證產(chǎn)生的調(diào)度等價于事務(wù)Ti在事務(wù)Tj前的某個串行調(diào)度烟很。實現(xiàn)中颈墅，每個數(shù)據(jù)項Q維護(hù)兩個值：
1）W-timestamp(Q)：成功執(zhí)行write(Q)的所有事務(wù)的最大時間戳
2）R-timestamp(Q)：成功執(zhí)行read(Q)的所有事務(wù)的最大時間戳蜡镶。
事務(wù)根據(jù)自身時間戳和這兩個值決定回滾還是成功執(zhí)行并更新。

Thomas寫規(guī)則與視圖可串行化

Thomas寫規(guī)則：一個事務(wù)T發(fā)出寫請求write(Q)時官还，如果W-timestamp(Q)>TS(T)，在基礎(chǔ)時間戳協(xié)議中叹俏，事務(wù)T需要回滾妻枕。Thomas寫規(guī)則認(rèn)為此時的寫操作可以直接忽略僻族。對于任何事務(wù)T'粘驰，如果TS(T')<W-timestamp(Q)，則應(yīng)當(dāng)回滾述么，如果TS(T')>W-timestamp(Q)蝌数，應(yīng)當(dāng)看到的Q應(yīng)當(dāng)是W-timestamp(Q)對應(yīng)事務(wù)的寫結(jié)果，而不是事務(wù)T中寫操作的結(jié)果度秘。

Thomas寫規(guī)則得到的調(diào)度不是沖突可串行化的顶伞，但是視圖可串行化的，簡而言之剑梳，兩個調(diào)度中每個事務(wù)都讀取相同的值唆貌，最后寫的結(jié)果一致，那就是視圖等價的垢乙。下面這個調(diào)度和串行調(diào)度<T1, T2>是視圖等價的锨咙，而不是沖突等價的：

T1            T2
read(Q)
              write(Q)
write(Q)

基于有效性檢查的協(xié)議

每個事務(wù)分為三階段執(zhí)行：1）讀階段，事務(wù)讀入局部變量追逮，寫操作只對局部變量進(jìn)行酪刀；2）有效性檢查階段；3）通過檢查的事務(wù)把結(jié)果寫回钮孵，否則事務(wù)執(zhí)行失敗骂倘。
根據(jù)步驟2）開始的時間TS(T)排序，得到一個等價的串行化調(diào)度巴席，在檢驗中历涝，滿足TS(Ti)<TS(Tj)的事務(wù)必須滿足兩個條件之一：
1）Tj開始讀階段前，Ti已經(jīng)寫回漾唉；2）Ti的寫階段在Tj的檢驗開始之前完成荧库，并且Ti寫的內(nèi)容和Tj讀的內(nèi)容不相交。

多版本協(xié)議

每個數(shù)據(jù)項有一個版本序列 <Q1, Q2,..., Qn>电爹，每一項包含三個屬性：
1）這個版本的值；2）W-timestamp(Qi)料睛，創(chuàng)建這個版本的事務(wù)時間戳丐箩；3）R-timestamp(Qi)讀過這個版本的最大事務(wù)時間戳

優(yōu)勢：讀操作從不失敗并且不等待

劣勢：引入了額外的R-timestamp更新摇邦；事務(wù)間的沖突完全靠回滾而沒有等待解決。

多版本兩階段鎖協(xié)議

將事務(wù)分為只讀事務(wù)和更新事務(wù)屎勘，只讀事務(wù)不需要鎖施籍，直接讀創(chuàng)建時間戳小于自己時間戳的版本值；更新事務(wù)在讀操作時概漱，需要加共享鎖丑慎，在寫操作時，需要加排他鎖瓤摧，并創(chuàng)建一個時間戳為正無窮的版本竿裂，在更新事務(wù)提交后，再把時間戳改為自己的時間戳照弥。這樣相當(dāng)于確保了寫操作在最后執(zhí)行腻异。因而可恢復(fù)，無級聯(lián)这揣。

恢復(fù)系統(tǒng)

日志

事務(wù)Ti開始：<Ti start>悔常；事務(wù)修改了數(shù)據(jù)項A：<Ti, A, old value, new value>；事務(wù)提交：<Ti commit>给赞；事務(wù)undo結(jié)束：<Ti abort>

系統(tǒng)崩潰后机打，在恢復(fù)時會根據(jù)日志執(zhí)行redo和undo行為，redo把數(shù)據(jù)項更新為new value片迅，undo把數(shù)據(jù)項恢復(fù)成old value残邀。給定一份日志，對于有<Ti start>/<Ti commit>或<Ti start>/<Ti abort>對的事務(wù)障涯，執(zhí)行redo罐旗，對于只有<Ti start>的事務(wù)執(zhí)行undo，undo時會寫新的日志唯蝶，以<Ti abort>結(jié)束九秀。

檢查點

檢查點是為了避免每次掃描所有日志，產(chǎn)生大量不必要的redo粘我。樸素檢查點的做法是：
1）把所有位于內(nèi)存的日志輸出到穩(wěn)定存儲中鼓蜒；
2）把所有緩沖塊的內(nèi)容輸出到穩(wěn)定存儲中；
3）記錄所有當(dāng)前活躍的事務(wù)列表L征字，在日志中寫入<checkpoint L>都弹；
下次恢復(fù)時，只需要恢復(fù)L中的所有事務(wù)匙姜，以及所有在寫入<checkpoint L>后開始的事務(wù)畅厢；
舉例：日志中所有事務(wù)的集合是{T1, T2, ..., T10}，最后一次檢查點內(nèi)容為<checkpoint T7 T9>氮昧，那么下次系統(tǒng)重啟只需要恢復(fù){T7, T9, T10}框杜，并且可以清除T1-T6所有的日志內(nèi)容

樸素檢查點要求在檢查點執(zhí)行過程中浦楣，事務(wù)不能再往主存中寫入新的日志和數(shù)據(jù)項。
模糊檢查點放寬了這一要求咪辱，因為步驟2）可能非常耗時振劳。模糊檢查點策略中先寫checkpoint日志，再進(jìn)行緩沖塊輸出油狂，在輸出過程中历恐，允許事務(wù)更新那些不相關(guān)的緩沖塊。這樣的問題在于如果在2）步驟發(fā)生故障专筷，checkpoint記錄的L列表有可能是不完全的弱贼，因此引入了一個last_checkpoint指針，它指向最后一個完成步驟2）的checkpoint位置仁堪。

并行數(shù)據(jù)庫

架構(gòu)：Share-memory哮洽，Share-disk填渠，Share-nothing

數(shù)據(jù)劃分方式：

range-partition的問題主要在數(shù)據(jù)傾斜上莺葫，可以用直方圖等統(tǒng)計信息幫助均衡

并行的數(shù)據(jù)庫操作：
1）選擇：如果數(shù)據(jù)劃分依據(jù)查詢的屬性，那么只要找相關(guān)的節(jié)點就可以了枪眉，否則并行的查找所有的捺檬；
2）排序：range-partition sort，parallel external merge-sort
3）連接：等值常采用hash join贸铜，非等值的采用fragment-and-replicate join

練習(xí)

1. 哈希連接和歸并連接分別在什么情況下效率更高

答：哈希連接和排序歸并連接在時間復(fù)雜度上相同堡纬，但是哈希連接需要的內(nèi)存更小。因此大部分情況下哈希連接更有效蒿秦，但排序歸并連接在以下情況更有效：
1）輸入表有序烤镐；2）要求輸出表有序；3）非等值連接棍鳖；4）哈希中數(shù)據(jù)偏斜嚴(yán)重

2. 舉一個啟發(fā)式規(guī)則：“盡早做選擇操作”失效的例子

答：考慮查詢：σ_θ(R?S)炮叶，θ是R表的屬性，滿足下面兩個條件時渡处，先在R上做選擇操作未必能加速查詢：
1）R表比S表小很多镜悉；2）R表的θ屬性上沒有索引，但是R和S的連接屬性上有索引医瘫。

3. 結(jié)合一個簡單事務(wù)說明ACID特性的含義及保證措施：

T1: Read(A)
    A := A - 50
    Write(A)
    Read(B)
    B := B - 50
    Write(B)

答：一致性在本例中指A+B在事務(wù)執(zhí)行前后不會改變侣肄。如果本例理解為銀行過戶行為，一致性要求余額不會憑空產(chǎn)生或消失醇份。一致性是由編寫事務(wù)的程序員保證的稼锅；

原子性是指事物要么不執(zhí)行叮喳，要么所有操作全部執(zhí)行。原子性的保證是由恢復(fù)系統(tǒng)保證的缰贝，對于事務(wù)中要寫的數(shù)據(jù)馍悟，log中會記錄事務(wù)發(fā)生前的值，如果事務(wù)未能完全執(zhí)行剩晴，需要恢復(fù)系統(tǒng)根據(jù)log恢復(fù)锣咒；

持久性是指一旦事務(wù)成功執(zhí)行，任何系統(tǒng)故障都不能導(dǎo)致這次事務(wù)執(zhí)行的結(jié)果丟失赞弥。持久性同樣是由恢復(fù)系統(tǒng)保證毅整，事務(wù)成功執(zhí)行后，要么結(jié)果已經(jīng)寫回磁盤绽左，要么相關(guān)的更新信息寫回磁盤悼嫉，下次系統(tǒng)啟動時可以根據(jù)這些信息重新執(zhí)行事務(wù)；

隔離性是指單個事務(wù)的執(zhí)行不應(yīng)該收到其他事務(wù)影響拼窥。隔離性是由并發(fā)控制系統(tǒng)保證的戏蔑，必須保證多個事務(wù)并發(fā)執(zhí)行的效果等價于某個串行事務(wù)序列執(zhí)行的效果。