InnoDB中的B+Tree和MVCC

之前做了個(gè)InnoDB的分享，主要是關(guān)于InnoDB中B+Tree的結(jié)構(gòu)和MVCC的實(shí)現(xiàn)。 paper writing services PPT:?BpTree_MVCC 下面把PPT內(nèi)容稍微整理一下。 首先是B+Tree，下面給出InnoDB中B+Tree的結(jié)構(gòu)（via） 有如下特點(diǎn)： 尋道次數(shù)固定，且次數(shù)少（因?yàn)闃?shù)高度比較

之前做了個(gè)InnoDB的分享，主要是關(guān)于InnoDB中B+Tree的結(jié)構(gòu)和MVCC的實(shí)現(xiàn)。

paper writing services

PPT:?BpTree_MVCC

下面把PPT內(nèi)容稍微整理一下。

首先是B+Tree，下面給出InnoDB中B+Tree的結(jié)構(gòu)（via）

有如下特點(diǎn)：

1. 尋道次數(shù)固定，且次數(shù)少（因?yàn)闃?shù)高度比較低），而HD的尋道是非常費(fèi)時(shí)
2. 數(shù)據(jù)存儲(chǔ)連續(xù)，非葉節(jié)點(diǎn)只存儲(chǔ)指針，數(shù)據(jù)都在葉節(jié)點(diǎn)。索引容易緩存
3. 每條數(shù)據(jù)都由雙向鏈表組織，范圍查詢(xún)快
4. 數(shù)據(jù)和葉節(jié)點(diǎn)在一起，查詢(xún)快（不需要再次尋道），插入慢（分裂/合并需要對(duì)更多數(shù)據(jù)進(jìn)行移動(dòng)）。相比MyIASM，葉節(jié)點(diǎn)只存指針，插入塊，查詢(xún)慢（多尋道）
5. 葉節(jié)點(diǎn)每個(gè)塊內(nèi)部雖然在連續(xù)的磁盤(pán)空間中，但葉節(jié)點(diǎn)本身并不是連續(xù)存儲(chǔ)的。經(jīng)過(guò)較長(zhǎng)時(shí)間的運(yùn)行，會(huì)碎片化，影響范圍查詢(xún)的效率。不過(guò)mysql提供了對(duì)此的優(yōu)化方法。

這里強(qiáng)烈推薦?B+Tree index structures in InnoDB 這篇文章，詳細(xì)介紹了InnoDB中B+Tree的具體實(shí)現(xiàn)結(jié)構(gòu)。

隨后是關(guān)于MVCC。

MVCC是多版本并發(fā)控制，用于在實(shí)現(xiàn)事務(wù)操作時(shí)，替代單純的讀寫(xiě)鎖。單純的讀寫(xiě)鎖會(huì)對(duì)所有讀過(guò)的數(shù)據(jù)加讀寫(xiě)鎖，讀了就不能寫(xiě)，寫(xiě)了就不能讀。

既然是解決讀寫(xiě)沖突的問(wèn)題，那何時(shí)能寫(xiě)何時(shí)能讀就是要考慮的重點(diǎn)，為此有“隔離級(jí)別”的概念。這個(gè)概念強(qiáng)調(diào)的就是在什么情況下，允許讀，什么情況下，允許寫(xiě)。

InnoDB的MVCC支持四種隔離級(jí)別，分別是READ UNCOMMITTED、READ COMMITTED、REPEATABLE READ、SERIALIZABLE。其中最常用的是“READ?COMMITTED：讀已提交”和“REPEATABLE READ：可重復(fù)讀”。

1. READ?COMMITTED：讀已提交。SELECT的時(shí)候無(wú)法保證重復(fù)讀數(shù)據(jù)是一樣的，即同一個(gè)事務(wù)中兩次執(zhí)行同樣的查詢(xún)語(yǔ)句，若在第一次與第二次查詢(xún)之間時(shí)間段，其他事務(wù)又剛好修改了其查詢(xún)的數(shù)據(jù)且提交了，則兩次讀到的數(shù)據(jù)不一致。就是“讀”“已提交”的事務(wù)。
2. REPEATABLE READ：可重復(fù)讀。任意一次事務(wù)中，任何數(shù)據(jù)的可見(jiàn)性都是在本次事務(wù)開(kāi)始前的狀態(tài)，即使其它事務(wù)提交了，對(duì)當(dāng)前事務(wù)依然不可見(jiàn)。即“可重復(fù)”“讀”到相同的內(nèi)容。

需要注意的是，無(wú)論任何隔離級(jí)別，一旦某條記錄被UPDATE/DELETE/SELECT FOR UPDATE，即加X(jué)鎖后，事務(wù)提交前就不能再被更新（加X(jué)鎖）了。

InnoDB是如何實(shí)現(xiàn)事務(wù)的多版本呢，我在演講的時(shí)候也請(qǐng)出了網(wǎng)易何登成大神的PPT

地址：?InnoDB Transaction Lock and MVCC：微盤(pán)地址??Slideshare地址

這個(gè)PPT詳細(xì)介紹了MVCC的具體實(shí)現(xiàn)，包括鎖相關(guān)的實(shí)現(xiàn)，下面我簡(jiǎn)單總結(jié)下重點(diǎn)。

InnoDB通過(guò)ReadView（視圖）來(lái)實(shí)現(xiàn)上述隔離級(jí)別。ReadView會(huì)記錄當(dāng)前狀態(tài)下：

1. 最小的活躍事務(wù)的事務(wù)ID（全局唯一，自增）
2. 當(dāng)前事務(wù)的ID
3. 所有活躍事務(wù)ID所組成的鏈表

同時(shí)，事務(wù)修改字段時(shí)，在修改原來(lái)的值的時(shí)候，會(huì)標(biāo)注當(dāng)前事務(wù)的ID，同時(shí)把舊的數(shù)據(jù)和舊的事務(wù)ID放到回滾段。

有了上述兩項(xiàng)操作，那么ReadView的作用就體現(xiàn)出來(lái)了，即Select語(yǔ)句讀?。?/p>

1. 擁 有大于最小活躍事務(wù)ID的、當(dāng)前非活躍事務(wù)中事務(wù)ID最大的 事務(wù)ID的 數(shù)據(jù)
2. 再組織一下語(yǔ)言，即通過(guò)ReadView找到最大的非活躍事務(wù)，取得它的事務(wù)ID，再去表中或者其回滾段中，尋找擁有這個(gè)事務(wù)ID的數(shù)據(jù)。

同時(shí)，任何小于“最小的活躍事務(wù)的事務(wù)ID”的數(shù)據(jù)都可以被回收，因?yàn)樗鼈冊(cè)僖膊粫?huì)被讀取到。

因此可以發(fā)現(xiàn)，READ?COMMITTED、REPEATABLE READ這兩個(gè)級(jí)別的差別，就在于ReadView的創(chuàng)建時(shí)機(jī)。前者再語(yǔ)句開(kāi)始時(shí)創(chuàng)建ReadView，語(yǔ)句結(jié)束后Drop；后者在事務(wù)開(kāi)始時(shí)創(chuàng)建，事務(wù)提交后Drop。即可實(shí)現(xiàn)其功能。

要注意的是，即便對(duì)于READ?COMMITTED級(jí)別，如果語(yǔ)句執(zhí)行過(guò)程中又有新的事務(wù)提交，select還是看不到的（極端情況）。

ReadView的存儲(chǔ)結(jié)構(gòu)，或者是更深入的研究，可以去看前述的PPT，不再重復(fù)。

其實(shí)還分享了關(guān)于回滾段、回滾方式，MySQL的X-commit二段提交，對(duì)B+Tree的一些操作，感覺(jué)寫(xiě)字還是有點(diǎn)兒蒼白，況且
Jeremy Cole和何登成的blog和PPT都要詳細(xì)、優(yōu)雅的多，推薦有興趣的同學(xué)去看看。

zp8497586rq

原文地址：InnoDB中的B+Tree和MVCC, 感謝原作者分享。

聲明：本網(wǎng)頁(yè)內(nèi)容旨在傳播知識(shí)，若有侵權(quán)等問(wèn)題請(qǐng)及時(shí)與本網(wǎng)聯(lián)系，我們將在第一時(shí)間刪除處理。TEL:177 7030 7066 E-MAIL:11247931@qq.com