当前位置:Gxlcms > mysql > InnoDB中的B+Tree和MVCC

InnoDB中的B+Tree和MVCC

时间:2021-07-01 10:21:17 帮助过:43人阅读

之前做了个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

人气教程排行