本文引用文章如链接:
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的逻辑架构、并发控制、事务处理等方面。 首先,MySQL的逻辑架构分为三层...
在《MySQL数据库原理及应用(第2版)(微课版)》中,我们通常会深入探讨数据库的基本概念、设计原则以及实际操作技巧。这份教学资料包含了一个Mysql数据库的备份文件,为学习者提供了实践平台,便于理解和掌握...
《MySQL数据库原理及应用》是一门深入探讨关系型数据库管理系统MySQL的课程,旨在教授学生如何设计、创建和管理数据库,以及如何在实际应用场景中高效利用MySQL。教案详细涵盖了该课程的所有章节,为教学提供了全面...
《MySQL数据库原理及应用(第2版)(微课版)》是一本深入浅出介绍MySQL技术的教材,配合配套教案,旨在帮助学生和学习者全面理解和掌握数据库设计与管理的核心概念。 该教程可能涵盖以下关键知识点: 1. **数据库...
《MySQL数据库原理及应用》从教学实际出发,系统地介绍了MySQL数据库的有关原理和基本操作,主要内容包括数据库技术概述、MySQL概述、数据库基本操作、数据表、索引、结构化查询语言SQL、视图、触发器、存储过程和...
### MySQL Innodb 索引原理详解 #### 1. 各种树形结构 在深入探讨MySQL Innodb索引之前,我们先了解几种基本的树形数据结构,包括二叉搜索树、B树、B+树以及B*树。...对于理解和优化MySQL数据库的性能至关重要。
MySQL数据库是世界上最...这些知识点构成了MySQL数据库原理与应用的基础,对于理解和操作MySQL数据库至关重要。学习和掌握这些内容将有助于学生在期末考试中取得好成绩,并为未来在互联网行业中使用MySQL奠定坚实基础。
《Oracle与MySQL数据库索引设计与优化》这本书深入探讨了两个主流关系型数据库管理系统——Oracle和MySQL中的索引设计和优化策略。索引是数据库性能的关键因素,它们能够加速数据检索,提高系统效率,尤其在大数据量...
总的来说,这个网络玩具销售系统的数据库设计展示了如何利用MySQL数据库原理进行实际应用开发,包括实体关系建模、关系模式规范化、索引优化和视图的使用,这些都是数据库设计中的核心知识点。理解并掌握这些内容,...
《MySQL数据库原理及应用(第2版)(微课版)》是一套全面介绍MySQL数据库系统的核心知识与实际应用的教学资料。本课程旨在帮助学习者深入理解MySQL的内部机制,掌握其基本操作,并能将其应用于实际项目开发中。以下...
《MySQL数据库原理及应用(第2版)(微课版)》是一门深入解析MySQL数据库核心技术与实际应用的课程。该课程旨在帮助学习者掌握数据库的基础理论,理解MySQL的架构和工作原理,以及如何在实际项目中有效地运用MySQL...
"数据库索引那些事(数据库索引原理)" 数据库索引是数据库的一种对象,它保存数据库表中一列或多列组合的排序。索引提供指向存储在表的指定列中的数据值的指针,然后根据指定的排序顺序对这些指针排序。数据库使用...
本资源摘要信息主要是基于 MySQL 数据库武洪萍版第五章习题与答案,涵盖了数据库索引、视图、触发器、存储过程和函数等多个方面的知识点。 1. 数据库索引:索引是数据库中用于提高查询速度的一种数据结构。它可以...
数据库原理及应用_MySQL 实验任务及指导书 MySQL 是一种流行的关系数据库管理系统(RDBMS),广泛应用于各种 Web 应用程序和企业级应用程序。MySQL 的实验任务及指导书旨在帮助学生掌握 MySQL 的基础知识和基本...
本压缩包“数据库系统原理及MySQL应用教程习题答案.zip”显然为学习者提供了宝贵的参考资料,特别是对正在学习这门课程的人来说,能够帮助他们理解和巩固所学知识。 首先,我们要理解数据库系统的基本概念。数据库...
**MySQL数据库原理** MySQL是一种广泛使用的开源关系型数据库管理系统(RDBMS),它以其高效、稳定和易用性在全球范围内赢得了广大用户的喜爱。本PPT将深入探讨MySQL的基本原理、功能特性和应用实践。 1. **数据库...
MySQL 数据库索引优化是提高查询效率的关键技术。索引是一种数据结构,它允许数据库快速找到存储在表中的特定记录,而无需遍历整个表。在处理大量数据时,索引能够显著减少查询时间,尤其是在涉及多行的复杂查询中。...
MySQL数据库索引优化是数据库管理员和开发人员在提升数据库性能方面的一个关键点,涉及BTree索引和Hash索引以及索引优化的策略。索引是数据库中一种非常重要的数据结构,它能够大幅提升查询的效率,但也需要恰当的...
【MySQL数据库索引的研究】 MySQL数据库索引是提高数据检索速度的关键技术,它涉及数据库管理系统中的数据结构和算法。在关系型数据库中,如MySQL,索引被广泛应用于加速查询操作,尤其对于大型数据集,索引的作用...
《MySQL数据库入门》是针对初学者的一本指南,旨在帮助读者快速掌握MySQL的基本概念和操作。这本教材的配套资源包含了一系列辅助学习材料,如教学PPT、教学大纲、教学设计、课后习题及答案,以及源代码,旨在提供全...