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

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

paper writing services

PPT:?BpTree_MVCC

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

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

有如下特點：

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

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

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

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

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

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

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

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

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

地址：?InnoDB Transaction Lock and MVCC：微盤地址??Slideshare地址

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

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

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

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

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

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

同時，任何小于“最小的活躍事務(wù)的事務(wù)ID”的數(shù)據(jù)都可以被回收，因為它們再也不會被讀取到。

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

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

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

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

zp8497586rq

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

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