本文引用文章如链接:
http://www.codinglabs.org/html/theory-of-mysql-index.html#more-100
参考书籍:Mysql技术内幕
本文主要是阐述mysql索引机制,主要是说明存储引擎Innodb
第一部分主要从数据结构及算法理论层面讨论MySQL数据库索引的数理基础。
第二部分结合MySQL数据库中InnoDB数据存储引擎中索引的架构实现讨论聚集索引、非聚集索引及覆盖索引等话题。
第三部分讨论MySQL中高性能使用索引的策略。
一、数据结构及算法理论
Innodb存储引擎实现索引的数据结构是B+树,下面介绍几种数据结构,一步步阐述为什么要使用B+树
1.1
B+树索引的构造类似于二叉树,根据键值快速找到数据。但是B+树种的B不是代表二叉,而是代表平衡。注意:B+树索引能找到的只是被查找数据行所在的页。然后数据库通过把页读入内存,再在内存中进行查找,最后查到数据。
下面介绍二分查找法:将记录按有序化(递增或递减)排列,查找过程中采用跳跃式方式查找,例如:5、10、19、21、31、37、42、48、50、52这10个数,如图所示:
用了三次查找速度就能找到48。如果是顺序查找的话,则需要8次。对于上面10个数来说,顺序查找的平均查找次数为5.5次,而二分查找法为2.9次,在最坏的情况下,顺序查找的次数为10,而二分查找的次数为4。二分查找在innodb中Page Directory中的槽是按照主键的顺序存放的,对于每一条具体记录的查询时通过对Page Directory进行二分查找。
1.2
二叉查找树
数字代表每个节点的键值,二叉查找树中,左子树的键值总是小于跟的键值,右子树的键值总是大于跟的键值。通过中序遍历得到键值:2、3、5、6、7、8。
二叉查找树的平均查找次数为2.3次。但是二叉查找树是可以任意构建,如构造如图:
但是这样跟顺序查找就差不多,所以就引用了平衡二叉树的思想,AVL树。
1.3
定义:符合二叉查找树的定义,其次必须满足任何节点的左右两个子树的高度最大差为1。
平衡二叉树虽然查找速度非常快但是维护一颗平衡二叉树的代价是非常大,通常需要1次或多次左旋和右旋来得到插入或更新后树的平衡性。
1.4
B+树的特性:
所有记录都在叶节点,并且是顺序存放,各个叶节点(页为单位)都是逻辑的连续存放,是一个双向循环链表。
B+树插入必须保证插入后叶节点中的记录依然排序,所以在插入时必须考虑以下三种情况:
B+树索引在数据库中有一个特点就是其高扇出性,因此在数据库中,B+树高度一般在2-3层,也就是寻找某一键值的行记录,最多2-3次IO,而一般的磁盘每秒至少可以做100次IO,2-3次的意味着查询时间只需0.02-0.03秒。
二、
聚集索引、非聚集索引
聚集索引与非聚集索引的区别是:页节点是否存放一整行记录
2.1 聚集索引
InnoDB存储引擎表是索引组织表,即表中数据按照主键顺序存放。而聚集索引就是按照每张表的主键构造一颗B+树,并且叶节点中存放着整张表的行记录数据,因此也让聚集索引的叶节点成为数据页。聚集索引的这个特性决定了索引组织表中的数据也是索引一部分。同时B+树数据结构一样,每个数据页都通过一个双向链表来进行链接。
实际数据也只能按照一颗B+树进行排序,因此每张表只能拥有一个聚集索引。在许多情况下,查询优化器非常倾向于采用聚集索引,因为聚集索引能够让我们在索引的叶节点直接找到数据。此外,由于定义了数据的逻辑顺序,聚集索引能够快速地访问针对范围值得到查询。查询优化器能够快速发现某一段范围的数据需要扫描。注意每一个页中的记录也是双向链表维护的。
2.2 非聚集索引
也称辅助索引,页级别不包含行的全部数据。页节点除了包含键值以外,每个页级别中的索引中还包含了一个书签,该书签用来告诉InnoDB存储引擎,哪里可以找到与索引相对应的行数据。因为InnoDB存储引擎表是索引组织表,因此InnoDB存储引擎的辅助索引书签就是相应行数据的聚集索引键。下图是聚集索引和辅助索引的关系:
当通过辅助索引来寻找数据时,InnoDB存储引擎会遍历辅助索引并通过叶级别的指针获得指向主键索引的主键,然后再通过主键索引来找到了一个完整的行记录。举例来说:一颗高度为3的辅助索引树中查找数据,那么需要对这颗辅助索引遍历3次找到指定主键;如果聚集索引树的高度同样为3,那么还需要对聚集索引进行三次查找,才能查找一个完整的行数据所在的页,因此需要6次的逻辑Io来访问最终的一个数据页。
- 大小: 9.4 KB
- 大小: 13.3 KB
- 大小: 11.2 KB
- 大小: 18.4 KB
- 大小: 37.4 KB
- 大小: 29.8 KB
- 大小: 51.6 KB
分享到:
相关推荐
数据库索引原理,索引的实现,索引的使用注意事项
MySQL数据库的创建、查看、删除、使用命令。 表结构创建和修改、表约束的创建和修改; 表数据的插入、删除和修改; 表联系的创建和修改。
头歌MySQL数据库实训答案有目录.pdf
《MySQL索引原理及如何建立高效索引.pptx》主要讲述mysql数据库索引底层原理、作用、 索引使用、索引失效等核心技术点。非常实用!!!
本文以MySQL数据库为研究对象,讨论与数据库索引相关的一些话题。特别需要说明的是,MySQL支持诸多存储引擎,而各种存储引擎对索引的支持也各不相同,因此MySQL数据库支持多种索引类型,如BTree索引,哈希索引,全文...
从数据结构底层实现,阐述B树、B+树的特点,到mysql为什么选择了B+树作为索引存储结构。接着介绍mysql底层存储实现段簇页,和聚簇索引非聚簇索引包括联合索引的关系。最后列举一些sql是否可走索引,涉及最左匹配原则...
西安电子科技大学MySQL数据库上机2 1、基于第一次上机创建的银行数据库,创建一个视图branch_detail,能够显示所有支行的存款客户数量、存款总额、贷款客户数量、贷款总额。 2、在account的account_number属性上建立...
单表的索引数不要超过6个:这个是数据库软件的限制,在早期oracle数据库上会有此限制,但mysql等就不会存在这个限制。但读者也要清楚的知道,索引数据过多会影响写的性能; 不应该索引不稳定的列:一般认为更新速度...
特别需要说明的是, MySQL支持诸多存储引擎,而各种存储引擎对 索引的支持也各不相同,因此MySQL数据库支 持多种索引类型,如BTree索引,哈希索引, 全文索引等等。为了避免混乱,本文将只关注 于BTree索引,因为这...
课程内容进行了精华的浓缩,有四大内容主旨,MySQL架构与执行流程,MySQL索引原理详解,MySQL事务原理与事务并发,MySQL性能优化总结与MySQL配置优化。课程安排的学习的教程与对应的学习课件,详细的学习笔以及课程...
目录网盘文件永久链接 1.Mysql数据库入门及安装.mp4 ...14.MySQL数据库索引及慢查询讲解.mp4 15.MySQL数据库高效优化解析.mp4 16.构建MySQL+keepalived高可用自动切换.mp4 17.构建MySQL+DRBD+Keepalived高可用集群.mp4
数据库Mysql索引的本质\Mysql索引的底层原理\Mysql索引的实战经验\MyISAM存储引擎在使用索引查询数据时,会先根据索引查找到数据地址,再根据地址查询到具体的数据。并且主键索引和辅助索引没有太多区别。
本文实例讲述了MySQL数据库优化之索引实现原理与用法。分享给大家供大家参考,具体如下: 索引 什么是索引 索引用来快速地寻找那些具有特定值的记录,所有MySQL索引都以B-树的形式保存。如果没有索引,执行查询时...
索引原理 13 Mysql索引管理 14 索引的两大类型hash与btree比较 15 索引原则 15 索引无法命中 15 慢查询 16 DB锁 17 乐观锁悲观锁 17 JVM内存结构 19 内存结构 19 Java堆 20 JVM GC过程 20 GC执行机制(回收器) 21 ...
背景MySQL凭借着出色的性能、低廉的成本、丰富的资源,已经成为绝大多数互联网公司的首选关系型数据库。虽然性能出色,但所谓“好马配好鞍”,如何能够更好的使用它,
20. MYSQL表高速缓存工作原理 9 21. MYSQL扩展/优化-提供更快的速度 9 22. MYSQL何时使用索引 10 23. MYSQL何时不使用索引 10 24. 学会使用EXPLAIN 10 25. 学会使用SHOW PROCESSLIST 11 26. 如何知晓MYSQL解决一条...
想要了解mysql数据库索引的知识的道友们,可以看一下相关文档!
17-第十七部-老男孩MySQL数据库索引优化及数据丢失案例-3节 18-第十八部-老男孩MySQL数据库生产场景核心优化精讲-05-节 19-第十九部-老男孩MySQL读写分离开发实现及软件实现-物理备份-高可用分享-5节
7-MySQL数据库参数索引优化生产方案及细节精讲03.avi 8-MySQL数据库SQL优化生产方案及细节精讲04.avi 9-MySQL数据库架构优化生产方案及细节精讲05.avi 第十六部 MySQL业务变更流程与安全管理思想(7节) 01-安全...
实际上,您可以把索引理解为一种特殊的目录。微软的SQLSERVER提供了两种索引:聚集索引(clustered index,也称聚类索引、簇集索引)和非聚集索引(nonclustered index,也称非聚类索引、非簇集索引)。