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, 感谢原作者分享。