在數(shù)據(jù)庫(kù)里，數(shù)據(jù)都是存在Page里的， 然后Pages是存放在Disk里的。

每一個(gè)Data Page里，有一個(gè)Page Header， 然后是Records。 可以設(shè)計(jì)為所有數(shù)據(jù)都是一樣的長(zhǎng)度的這種。 壞處是可能有的數(shù)據(jù)才1Byte，你給所有人都設(shè)計(jì)10Bytes的大小，浪費(fèi)。好處是，從header里可以很容易找到哪個(gè)record是空的，哪個(gè)是滿的。因?yàn)槟阒纑ecord section起始點(diǎn)，然后知道每個(gè)record的大小。這樣就很好iterate page里的東西。

對(duì)于Variable的records，我們用Slot Directory. 每個(gè)Record ID都記錄在slot table. Slot Directory里每個(gè)Id 用一個(gè)pointer, 指向record所在的地方。要?jiǎng)h除東西的時(shí)候，設(shè)置pointer to Null. 要插入東西的話， 把record放在free space, 然后create pointer in next open slot in slot directory.

知道了page長(zhǎng)什么樣，所以要用什么數(shù)據(jù)結(jié)構(gòu)存儲(chǔ)數(shù)據(jù)呢？這個(gè)數(shù)據(jù)結(jié)構(gòu)要在搜索，刪除，插入上都非常牛逼。

B+ Tree:?

整個(gè)儲(chǔ)存data，查找數(shù)據(jù)， insert data之類的都會(huì)非?？焖?。

External Sorting是面試重點(diǎn)中的重點(diǎn)，設(shè)計(jì)了內(nèi)存，大數(shù)據(jù)的考點(diǎn)。

External Sorting過(guò)程： 假設(shè)我們有10 個(gè)page空間的內(nèi)存。memory里一次可以放10個(gè)page

Input 為 90 page的File。

Phase0: 把90個(gè)Page依次存入內(nèi)存里。 每次用B個(gè)Buffer，先進(jìn)10個(gè)， output出來(lái)，再進(jìn)10個(gè)。

每次存10個(gè)Page， 【因?yàn)閮?nèi)存也就10個(gè)page】，然后內(nèi)存會(huì)在里面sorting，Sort成一個(gè)chunk of data.

最后一共會(huì) output出9個(gè)chunk of data， 每個(gè)chunk 里面有10個(gè)page都排好序了.

Phase 1: 從這9個(gè)chunk里，每個(gè)chunk拿出第一張page，也就是每個(gè)chunk里最小的數(shù)據(jù)出來(lái)，裝入內(nèi)存里 進(jìn)行排序。 這個(gè)時(shí)候內(nèi)存的9個(gè)buffer裝著9張page，然后拿一個(gè)buffer用來(lái)output to Disk. 每排序好一張page of data from 9 pages, buffer就打包這些到disk。當(dāng)9個(gè)page里有一個(gè)page沒有數(shù)據(jù)了，我們?cè)赿isk里， 從那個(gè)page 所屬的chunk里read more data to memory. 重復(fù)此操作直到結(jié)束。

計(jì)算Number of Pass:

pass0： 是會(huì)分出N/B chunk of data

pass1,2.... 每個(gè) Pass 可以merge B-1 Pages. 因?yàn)閮?nèi)存容量是B pages, 一個(gè)page要作為output to disk的工具，所以每次只能merge B-1 pages。?

所以Number of pass: 1+logb-1[N/B]. ? 也就是pass 0 分出的chunk數(shù)量 能夠除 Memory每次能merge的Page 數(shù) ?的次數(shù) +1

Join Optimization:

在沒學(xué)過(guò)database之前，我一直覺得join 就是把兩個(gè)page的data全部丟在一起。雖然確實(shí)是這樣，但是操作順序上的不同會(huì)引起極大的效率上的不一樣。這里最主要是涉及到了內(nèi)存這個(gè)東西。 因?yàn)槊看蝚oin，都要把page里的數(shù)據(jù)load 進(jìn)內(nèi)存，在內(nèi)存里真正join.?

如果按下圖的方法來(lái)join， R是一個(gè)數(shù)據(jù)庫(kù)Table，S是一個(gè)數(shù)據(jù)庫(kù)Table。 對(duì)于每個(gè)record in R, 他都會(huì)和所有的record in S依次join一遍。 這樣并沒有make use of 內(nèi)存。因?yàn)槊恳粋€(gè)record都要load進(jìn)內(nèi)存在比較的話實(shí)在是太慢了?！菊_姿勢(shì)應(yīng)該是page 全部load進(jìn)內(nèi)存，然后record就自動(dòng)在內(nèi)存里了】

如果是Page-Oriented Nested Loop Join

先從R取出一整張的data Page， 然后從S里的每一個(gè)Page依次拿出一張一張page。 每次把R的Page 和S的Page Load進(jìn)內(nèi)存里，然后每個(gè)record 之間join起來(lái)。這樣算一下，操作量就減少了很多。

之所以Page-Oriented 快，因?yàn)槲覀僤o comparison in a page-to-page level. 假設(shè)內(nèi)存RAM的容量是2 Pages。 一開始我們要load 1 page of R 和1 page of S 進(jìn)內(nèi)存。 cost 2 IOS. ?假設(shè)這兩張page一張叫r1, 一張叫s1. 現(xiàn)在我們要compare each record in r1 with each record in s1. 但是呢，因?yàn)樗麄円呀?jīng)在memory了，所以我們不用花任何的IOs. 比較完畢之后，把s1換成s2, 重復(fù)compare的操作。

Block Nested Loop Join的話就不止是一次性只Load 一個(gè)page From R, 一個(gè)Page From S了。他是根據(jù)Memory的大小，盡量把memory能放下的pages全load進(jìn)去。

Query Optimization

當(dāng)要查找某個(gè)數(shù)據(jù)的時(shí)候，大家一般都用SQL的語(yǔ)言來(lái)查找，給定一些condition來(lái)過(guò)濾掉不要的來(lái)找想要的數(shù)據(jù)。 但是SQL的寫法順序其實(shí)也是對(duì)速度有很大的影響。 比如下面的例子：

上述例子是先把兩個(gè)Table Join起來(lái)然后再過(guò)濾尋找。但是這時(shí)候Table Join好以后變得特別大，要過(guò)濾的數(shù)據(jù)也多了很多。

好一點(diǎn)的方法是，把operation push到下方。在Table join前，先把沒用的賽選掉，這樣工作量就小很多

------上面的都是database里比較基本的東西， 下面才是主菜---------------

一個(gè)好的數(shù)據(jù)庫(kù)真正要解決的問(wèn)題是當(dāng)同時(shí)有許多人在用你的數(shù)據(jù)庫(kù)，更新數(shù)據(jù)的時(shí)候不會(huì)發(fā)生混亂。還有，當(dāng)transaction 取消/故障的時(shí)候，有辦法恢復(fù)數(shù)據(jù)庫(kù)。

Consistency: 表示每個(gè)人看到的同一個(gè)數(shù)據(jù)的值要一樣。Durability是，如果transaction執(zhí)行成功，并且commits了，就算之后數(shù)據(jù)庫(kù)爆炸了，你也得給他恢復(fù)到原樣，這個(gè)成功保存的資料不能丟失。Isolation： 某個(gè)數(shù)據(jù)我在用的時(shí)候，其他transaction不能來(lái)動(dòng)他。

隔離別的transaction的基本做法： 按時(shí)間順序來(lái)執(zhí)行，先來(lái)的先做事，你后來(lái)就等著。 Serial Execution的壞處就是會(huì)很慢很慢。

T1想要轉(zhuǎn)100刀從A賬戶給B賬戶

T2 想給A賬戶和B賬戶加10%的利息。

底下這個(gè)行程表，雖然看起來(lái)不是按serial[一個(gè)完整執(zhí)行完，再執(zhí)行第二個(gè)]。但是其實(shí)可以轉(zhuǎn)化為Serial Schedule. 因?yàn)門2 干的事情對(duì)T1其實(shí)順序上沒什么影響。

Conflicting Operation概念：

Two operations are conflict if they are by different transactions, 并且是on the same Objects. 并且兩個(gè)operation中至少有一個(gè)是Write. 這個(gè)東西理解起來(lái)不是很難其實(shí)。 假設(shè)transaction是人。 小明和小黃兩個(gè)人，都想操作same object data x.? 小明想要write， 小黃想要read。 這里會(huì)形成一個(gè)conflict 因?yàn)樾↑Sread出來(lái)數(shù)據(jù)以后加以修改， 然后以后再write進(jìn)A。假設(shè)小黃先read到x=10現(xiàn)在。 然后小黃10天后再去更新x的數(shù)據(jù)，x=x*0.8,想要改成11. 但是呢 小紅在小黃read完以后馬上修改了x的數(shù)據(jù)。這樣小黃read到的數(shù)據(jù)就被改寫了，之后的update也就不對(duì)了。

2PL 保證conflict Serialiablity. 2PL 就是兩個(gè)階段的鎖。 ?

2PL 的意思是分成兩個(gè)階段。 第一階段 只能acquire Locks. 第二階段只能release Locks 不能acquire Lock after lock release

Cascading Aborts的意思就是如果一個(gè)Transaction abort了，會(huì)有其他Transaction也要abort，因?yàn)橐蕾囋谶@個(gè)Transaction上。形象一點(diǎn)就是我先往卡里存了1000塊錢。你拿我卡去買東西。你剛買我告訴你我存錢失敗了，你那筆交易也買不了了

2PL 的話就是我第一個(gè)Phase 大家都是Acquire Locks。

Strict 2PL就是為了解決cascading Aborts問(wèn)題。確認(rèn)了我這個(gè)Transaction已經(jīng)完事了，你才可以拿到access這個(gè)資源的lock。

Strict 2PL 釋放鎖只有當(dāng)Transaction 確定執(zhí)行完畢的時(shí)候。如下圖，T1 先拿到了鎖，讀取A數(shù)據(jù)，寫入A數(shù)據(jù)，然后釋放鎖。這時(shí)候T2才可以拿到鎖，讀取A數(shù)據(jù)，寫入A數(shù)據(jù)。

Lock有幾種，1. S ?可以read 這種鎖可以被好幾個(gè)人拿。就是大家不修改數(shù)據(jù)，只是看看。 2. X ，要修改數(shù)據(jù)的比如write。那他拿了以后別人就不能再拿S或者X鎖了，因?yàn)檫@個(gè)人在改數(shù)據(jù)，別人現(xiàn)在不能read/write.

Deadlock就是一種死循環(huán)的情況。

解決辦法：給每個(gè)Transaction Priority based on Time 1. wait die. 如果Ti 有更高的優(yōu)先權(quán)，Ti waits for Tj, 否則的話， Ti 這個(gè)transaction就取消。

2.wound-wait; 如果Ti 有更高的優(yōu)先權(quán)，Tj transaction直接爆炸，如果Ti沒有更高的優(yōu)先權(quán)，就等著直到Tj release。

DeadLock Detection: 建造一個(gè)wait-for graph, 周期性的檢查有沒有cycle在graph里。 每次添加新的Transaction，都判斷一次會(huì)不會(huì)有deadlock。

----數(shù)據(jù)還原---------

關(guān)鍵詞： checkpoint, log.

大概流程就是 用checkpoint記錄一下我們之前干過(guò)啥事情，周期性更新一次checkpoint。如果在某一步數(shù)據(jù)庫(kù)爆炸了，我們把上次checkpoint到爆炸期間所有的操作重新做一遍， 把a(bǔ)bort的Transaction的事情全部undo。 【這些操作都記錄在log上】

要注意的是： 我們并不是一更新，寫入東西。那些更新就直接真的寫入數(shù)據(jù)庫(kù)了，我們只是把他們寫在log上，當(dāng)前要干嘛干嘛的。然后等到一定周期，把這些全部寫入數(shù)據(jù)庫(kù)【也可以是后臺(tái)他慢慢往數(shù)據(jù)庫(kù)寫，程序不管他們繼續(xù)update】

undo：從Transaction Table里找Max-LSN, 從那個(gè)Transaction往上undo.（往prevLSN) [commit了的Transaction是不會(huì)出現(xiàn)在Transaction Table的]。當(dāng)crash發(fā)生的時(shí)候，這些已經(jīng)執(zhí)行的transaction要撤銷掉，從每個(gè)Transaction干過(guò)的最后一件事情往前undo。 undo完它干過(guò)的所有事情。

Redo也是用來(lái)解決程序crash的問(wèn)題的。 從當(dāng)前Dirty Page Table里min RSN開始Redo。 在Dirty Table的東西就是，數(shù)據(jù)還沒寫入Disk，所以要重新把它們寫入Disk。