InnoDB中的B+Tree和MVCC
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了InnoDB中的B+Tree和MVCC,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含3496字,纯文字阅读大概需要5分钟。
内容图文
![InnoDB中的B+Tree和MVCC](/upload/InfoBanner/zyjiaocheng/557/0b0e86ca596a42edac28275e7ad5d2ed.jpg)
之前做了个InnoDB的分享,主要是关于InnoDB中B+Tree的结构和MVCC的实现。 paper writing services PPT:?BpTree_MVCC 下面把PPT内容稍微整理一下。 首先是B+Tree,下面给出InnoDB中B+Tree的结构(via) 有如下特点: 寻道次数固定,且次数少(因为树高度比较
之前做了个InnoDB的分享,主要是关于InnoDB中B+Tree的结构和MVCC的实现。
PPT:?BpTree_MVCC
下面把PPT内容稍微整理一下。
首先是B+Tree,下面给出InnoDB中B+Tree的结构(via)
有如下特点:
- 寻道次数固定,且次数少(因为树高度比较低),而HD的寻道是非常费时
- 数据存储连续,非叶节点只存储指针,数据都在叶节点。索引容易缓存
- 每条数据都由双向链表组织,范围查询快
- 数据和叶节点在一起,查询快(不需要再次寻道),插入慢(分裂/合并需要对更多数据进行移动)。相比MyIASM,叶节点只存指针,插入块,查询慢(多寻道)
- 叶节点每个块内部虽然在连续的磁盘空间中,但叶节点本身并不是连续存储的。经过较长时间的运行,会碎片化,影响范围查询的效率。不过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:可重复读”。
- READ?COMMITTED:读已提交。SELECT的时候无法保证重复读数据是一样的,即同一个事务中两次执行同样的查询语句,若在第一次与第二次查询之间时间段,其他事务又刚好修改了其查询的数据且提交了,则两次读到的数据不一致。就是“读”“已提交”的事务。
- REPEATABLE READ:可重复读。任意一次事务中,任何数据的可见性都是在本次事务开始前的状态,即使其它事务提交了,对当前事务依然不可见。即“可重复”“读”到相同的内容。
需要注意的是,无论任何隔离级别,一旦某条记录被UPDATE/DELETE/SELECT FOR UPDATE,即加X锁后,事务提交前就不能再被更新(加X锁)了。
InnoDB是如何实现事务的多版本呢,我在演讲的时候也请出了网易何登成大神的PPT
地址:?InnoDB Transaction Lock and MVCC:微盘地址??Slideshare地址
这个PPT详细介绍了MVCC的具体实现,包括锁相关的实现,下面我简单总结下重点。
InnoDB通过ReadView(视图)来实现上述隔离级别。ReadView会记录当前状态下:
- 最小的活跃事务的事务ID(全局唯一,自增)
- 当前事务的ID
- 所有活跃事务ID所组成的链表
同时,事务修改字段时,在修改原来的值的时候,会标注当前事务的ID,同时把旧的数据和旧的事务ID放到回滚段。
有了上述两项操作,那么ReadView的作用就体现出来了,即Select语句读取:
- 拥 有大于最小活跃事务ID的、当前非活跃事务中事务ID最大的 事务ID的 数据
- 再组织一下语言,即通过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都要详细、优雅的多,推荐有兴趣的同学去看看。
原文地址:InnoDB中的B+Tree和MVCC, 感谢原作者分享。
内容总结
以上是互联网集市为您收集整理的InnoDB中的B+Tree和MVCC全部内容,希望文章能够帮你解决InnoDB中的B+Tree和MVCC所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。