InnoDB中的B+Tree和MVCC

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

之前做了個InnoDB的分享，主要是關于InnoDB中B+Tree的結構和MVCC的實現。

paper writing services

PPT:?BpTree_MVCC

下面把PPT內容稍微整理一下。

首先是B+Tree，下面給出InnoDB中B+Tree的結構（via）

有如下特點：

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

這里強烈推薦?B+Tree index structures in InnoDB 這篇文章，詳細介紹了InnoDB中B+Tree的具體實現結構。

隨后是關于MVCC。

MVCC是多版本并發控制，用于在實現事務操作時，替代單純的讀寫鎖。單純的讀寫鎖會對所有讀過的數據加讀寫鎖，讀了就不能寫，寫了就不能讀。

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

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

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

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

InnoDB是如何實現事務的多版本呢，我在演講的時候也請出了網易何登成大神的PPT

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

這個PPT詳細介紹了MVCC的具體實現，包括鎖相關的實現，下面我簡單總結下重點。

InnoDB通過ReadView（視圖）來實現上述隔離級別。ReadView會記錄當前狀態下：

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

同時，事務修改字段時，在修改原來的值的時候，會標注當前事務的ID，同時把舊的數據和舊的事務ID放到回滾段。

有了上述兩項操作，那么ReadView的作用就體現出來了，即Select語句讀取：

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

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

因此可以發現，READ?COMMITTED、REPEATABLE READ這兩個級別的差別，就在于ReadView的創建時機。前者再語句開始時創建ReadView，語句結束后Drop；后者在事務開始時創建，事務提交后Drop。即可實現其功能。

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

ReadView的存儲結構，或者是更深入的研究，可以去看前述的PPT，不再重復。

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

zp8497586rq

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

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