什么是局部性原理？
數(shù)據(jù)預(yù)讀的思路是：磁盤讀寫并不是按需讀取，而是按頁預(yù)讀，一次會讀一頁的數(shù)據(jù)，每次加載更多的數(shù)據(jù)，以便未來減少磁盤IO
局部性原理：軟件設(shè)計要盡量遵循“數(shù)據(jù)讀取集中”與“使用到一個數(shù)據(jù)，大概率會使用其附近的數(shù)據(jù)”，這樣磁盤預(yù)讀能充分提高磁盤IO
B樹
B樹，如上圖，它的特點是：
(1)不再是二叉搜索，而是m叉搜索；
(2)葉子節(jié)點，非葉子節(jié)點，都存儲數(shù)據(jù)；
(3)中序遍歷，可以獲得所有節(jié)點；
非根節(jié)點包含的關(guān)鍵字個數(shù)j滿足，(┌m/2┐)-1 <= j <= m-1，節(jié)點分裂時要滿足這個條件
B+樹
(1)非葉子節(jié)點不再存儲數(shù)據(jù)，數(shù)據(jù)只存儲在同一層的葉子節(jié)點上；
(2)葉子之間，增加了鏈表，獲取所有節(jié)點，不再需要中序遍歷；
數(shù)據(jù)庫的索引最常用B+樹：
(1)很適合磁盤存儲，能夠充分利用局部性原理，磁盤預(yù)讀。
比如：每個節(jié)點是1頁的大小,4k，key占8個字節(jié)，j = 512, 根據(jù)(┌m/2┐)1 <= j <= m-1, m=j + 1,即513
(2)很低的樹高度，能夠存儲大量數(shù)據(jù)；
(3)索引本身占用的內(nèi)存很小；
(4)能夠很好的支持單點查詢，范圍查詢，有序性查詢；
InnoDB的索引
InnoDB的索引有兩類索引，聚集索引(Clustered Index)與普通索引(Secondary Index)。
InnoDB的每一個表都會有聚集索引：
(1)如果表定義了PK，則PK就是聚集索引；
(2)如果表沒有定義PK，則第一個非空unique列是聚集索引；
(3)否則，InnoDB會創(chuàng)建一個隱藏的row-id作為聚集索引；
索引的結(jié)構(gòu)是B+樹，這里不展開B+樹的細節(jié)，說幾個結(jié)論：
(1)在索引結(jié)構(gòu)中，非葉子節(jié)點存儲key，葉子節(jié)點存儲value；
(2)聚集索引，葉子節(jié)點存儲行記錄(row)；
(3)普通索引，葉子節(jié)點存儲了PK的值；
InnoDB的普通索引，實際上會掃描兩遍：
第一遍，由普通索引找到PK；
第二遍，由PK找到行記錄；
隔離性
事務(wù)ACID特性，其中I代表隔離性(Isolation)
隔離性是指多個并發(fā)事務(wù)之間要相互隔離。
并發(fā)事務(wù)之間相互干擾，可能導(dǎo)致事務(wù)出現(xiàn)讀臟，不可重復(fù)度，幻讀等問題
不隔離可能導(dǎo)致的問題
假設(shè)有InnoDB表：
t(id PK, name);
表中有三條記錄：
1, shenjian
2, zhangsan
3, lisi
case 1
事務(wù)A，先執(zhí)行，處于未提交的狀態(tài)：
insert into t values(4, wangwu);
事務(wù)B，后執(zhí)行，也未提交：
select * from t;
如果事務(wù)B能夠讀取到(4, wangwu)這條記錄，事務(wù)A就對事務(wù)B產(chǎn)生了影響，這個影響叫做“讀臟”，讀到了未提交事務(wù)操作的記錄。
case 2
事務(wù)A，先執(zhí)行：
select * from t where id=1;
結(jié)果集為：
1, shenjian
事務(wù)B，后執(zhí)行，并且提交：
update t set name=xxoo where id=1;
commit;
事務(wù)A，再次執(zhí)行相同的查詢：
select * from t where id=1;
結(jié)果集為：
1, xxoo
這次是已提交事務(wù)B對事務(wù)A產(chǎn)生的影響，這個影響叫做“不可重復(fù)讀”，一個事務(wù)內(nèi)相同的查詢，得到了不同的結(jié)果。
case 3
事務(wù)A，先執(zhí)行：
select * from t where id>3;
結(jié)果集為：
NULL
事務(wù)B，后執(zhí)行，并且提交：
insert into t values(4, wangwu);
commit;
事務(wù)A，首次查詢了id>3的結(jié)果為NULL，于是想插入一條為4的記錄：
insert into t values(4, xxoo);
結(jié)果集為：
Error : duplicate key!
事務(wù)A的內(nèi)心OS是：你TM在逗我，查了id>3為空集，insert id=4告訴我PK沖突？
這次是已提交事務(wù)B對事務(wù)A產(chǎn)生的影響，這個影響叫做“幻讀”。
可以看到，并發(fā)的事務(wù)可能導(dǎo)致其他事務(wù)：
讀臟
不可重復(fù)讀
幻讀
事務(wù)的隔離級別：
按照SQL92標準，InnoDB實現(xiàn)了四種不同事務(wù)的隔離級別：
- 讀未提交(Read Uncommitted)
- 讀提交(Read Committed, RC)
- 可重復(fù)讀(Repeated Read, RR)
- 串行化(Serializable)
不同事務(wù)的隔離級別，實際上是一致性與并發(fā)性的一個權(quán)衡與折衷。
隔離級別實現(xiàn)
InnoDB使用不同的鎖策略(Locking Strategy)來實現(xiàn)不同的隔離級別。
(1)讀未提交：select不加鎖，可能出現(xiàn)讀臟；
(2)讀提交(RC)：普通select快照讀，鎖select /update /delete 會使用記錄鎖，可能出現(xiàn)不可重復(fù)讀；
(3)可重復(fù)讀(RR)：普通select快照讀，鎖select /update /delete 根據(jù)查詢條件情況，會選擇記錄鎖，或者間隙鎖/臨鍵鎖，以防止讀取到幻影記錄；
(4)串行化：select隱式轉(zhuǎn)化為select ... in share mode，會被update與delete互斥；
InnoDB默認的隔離級別是RR，用得最多的隔離級別是RC
mysql的鎖
默認的事務(wù)隔離級別為可重復(fù)讀(Repeated Read, RR)
記錄鎖(Record Locks)
記錄鎖，它封鎖索引記錄，例如：
select * from t where id=1 for update;
它會在id=1的索引記錄上加鎖，以阻止其他事務(wù)插入，更新，刪除id=1的這一行。
需要說明的是：
select * from t where id=1;
則是快照讀(SnapShot Read)，它并不加鎖
間隙鎖(Gap Locks)
間隙鎖，它封鎖索引記錄中的間隔，或者第一條索引記錄之前的范圍，又或者最后一條索引記錄之后的范圍。
依然是上面的例子，InnoDB，RR：
t(id PK, name KEY, sex, flag);
表中有四條記錄：
1, shenjian, m, A
3, zhangsan, m, A
5, lisi, m, A
9, wangwu, f, B
這個SQL語句
select * from t
where id between 8 and 15
for update;
會封鎖區(qū)間，以阻止其他事務(wù)id=10的記錄插入。
為什么要阻止id=10的記錄插入？
如果能夠插入成功，頭一個事務(wù)執(zhí)行相同的SQL語句，會發(fā)現(xiàn)結(jié)果集多出了一條記錄，即幻影數(shù)據(jù)。
間隙鎖的主要目的，就是為了防止其他事務(wù)在間隔中插入數(shù)據(jù)，以導(dǎo)致“不可重復(fù)讀”。
如果把事務(wù)的隔離級別降級為讀提交(Read Committed, RC)，間隙鎖則會自動失效。
臨鍵鎖(Next-Key Locks)
臨鍵鎖，是記錄鎖與間隙鎖的組合，它的封鎖范圍，既包含索引記錄，又包含索引區(qū)間。
更具體的，臨鍵鎖會封鎖索引記錄本身，以及索引記錄之前的區(qū)間。
如果一個會話占有了索引記錄R的共享/排他鎖，其他會話不能立刻在R之前的區(qū)間插入新的索引記錄。
依然是上面的例子，InnoDB，RR：
t(id PK, name KEY, sex, flag);
表中有四條記錄：
1, shenjian, m, A
3, zhangsan, m, A
5, lisi, m, A
9, wangwu, f, B
PK上潛在的臨鍵鎖為：
(-infinity, 1]
(1, 3]
(3, 5]
(5, 9]
(9, +infinity]
臨鍵鎖的主要目的，也是為了避免幻讀(Phantom Read)。如果把事務(wù)的隔離級別降級為RC，臨鍵鎖則也會失效。
共享/排它鎖(Shared and Exclusive Locks)
(1)事務(wù)拿到某一行記錄的共享S鎖，才可以讀取這一行；
(2)事務(wù)拿到某一行記錄的排它X鎖，才可以修改或者刪除這一行；
意向鎖(Intention Locks)
InnoDB支持多粒度鎖(multiple granularity locking)，它允許行級鎖與表級鎖共存，實際應(yīng)用中，InnoDB使用的是意向鎖。
意向鎖是指，未來的某個時刻，事務(wù)可能要加共享/排它鎖了，先提前聲明一個意向。
意向鎖有這樣一些特點：
(1)首先，意向鎖，是一個表級別的鎖(table-level locking)；
(2)意向鎖分為：
意向共享鎖(intention shared lock, IS)，它預(yù)示著，事務(wù)有意向?qū)Ρ碇械哪承┬屑庸蚕鞸鎖
意向排它鎖(intention exclusive lock, IX)，它預(yù)示著，事務(wù)有意向?qū)Ρ碇械哪承┬屑优潘黊鎖
舉個例子：
select ... lock in share mode，要設(shè)置IS鎖；
select ... for update，要設(shè)置IX鎖；
(3)意向鎖協(xié)議(intention locking protocol)并不復(fù)雜：
事務(wù)要獲得某些行的S鎖，必須先獲得表的IS鎖
事務(wù)要獲得某些行的X鎖，必須先獲得表的IX鎖
(4)由于意向鎖僅僅表明意向，它其實是比較弱的鎖，意向鎖之間并不相互互斥，而是可以并行
插入意向鎖(Insert Intention Locks)
對已有數(shù)據(jù)行的修改與刪除，必須加強互斥鎖X鎖，那對于數(shù)據(jù)的插入，是否還需要加這么強的鎖，來實施互斥呢？插入意向鎖，孕育而生。
插入意向鎖，是間隙鎖(Gap Locks)的一種（所以，也是實施在索引上的），它是專門針對insert操作的。
多個事務(wù)，在同一個索引，同一個范圍區(qū)間插入記錄時，如果插入的位置不沖突，不會阻塞彼此
在MySQL，InnoDB，RR下：
t(id unique PK, name);
數(shù)據(jù)表中有數(shù)據(jù)：
10, shenjian
20, zhangsan
30, lisi
事務(wù)A先執(zhí)行，在10與20兩條記錄中插入了一行，還未提交：
insert into t values(11, xxx);
事務(wù)B后執(zhí)行，也在10與20兩條記錄中插入了一行：
insert into t values(12, ooo);
(1)會使用什么鎖？
(2)事務(wù)B會不會被阻塞呢？
回答：雖然事務(wù)隔離級別是RR，雖然是同一個索引，雖然是同一個區(qū)間，但插入的記錄并不沖突，故這里：
使用的是插入意向鎖
并不會阻塞事務(wù)B
自增鎖（Auto-inc Locks）
自增鎖是一種特殊的表級別鎖（table-level lock），專門針對事務(wù)插入AUTO_INCREMENT類型的列。最簡單的情況，如果一個事務(wù)正在往表中插入記錄，所有其他事務(wù)的插入必須等待，以便第一個事務(wù)插入的行，是連續(xù)的主鍵值。
與此同時，InnoDB提供了innodb_autoinc_lock_mode配置，可以調(diào)節(jié)與改變該鎖的模式與行為。
一，案例說明
MySQL，InnoDB，默認的隔離級別(RR)，假設(shè)有數(shù)據(jù)表：
t(id AUTO_INCREMENT, name);
數(shù)據(jù)表中有數(shù)據(jù)：
1, shenjian
2, zhangsan
3, lisi
事務(wù)A先執(zhí)行，還未提交：
insert into t(name) values(xxx);
事務(wù)B后執(zhí)行：
insert into t(name) values(ooo);
問：事務(wù)B會不會被阻塞？
二，案例分析
InnoDB在RR隔離級別下，能解決幻讀問題，上面這個案例中：
(1)事務(wù)A先執(zhí)行insert，會得到一條(4, xxx)的記錄，由于是自增列，故不用顯示指定id為4，InnoDB會自動增長，注意此時事務(wù)并未提交；
(2)事務(wù)B后執(zhí)行insert，假設(shè)不會被阻塞，那會得到一條(5, ooo)的記錄；
此時，并未有什么不妥，但如果，
(3)事務(wù)A繼續(xù)insert：
insert into t(name) values(xxoo);
會得到一條(6, xxoo)的記錄。
(4)事務(wù)A再select：
select * from t where id>3;
得到的結(jié)果是：
4, xxx
6, xxoo
畫外音：不可能查詢到5的記錄，再RR的隔離級別下，不可能讀取到還未提交事務(wù)生成的數(shù)據(jù)。
這對于事務(wù)A來說，就很奇怪了，對于AUTO_INCREMENT的列，連續(xù)插入了兩條記錄，一條是4，接下來一條變成了6，就像莫名其妙的幻影。
