MySQL索引详解--InnoDB
1.索引的概述与分类
索引:索引是帮助mysql高效获取数据的数据结构;类似于图书的目录,可以提高数据检索效率,降低数据库IO成本。
索引的分类:
-
主键索引
即主索引,根据主键建立索引,不允许重复,不允许空值
如果表中没有定义主键,InnoDB会选择一个唯一的非空索引代替
如果没有这样的索引,InnoDB会隐式定义一个主键来作为聚簇索引
-
唯一索引
用来建立索引的列的值必须是唯一的,允许空值
-
普通索引
用表中的普通列构建的索引,无限制
-
全文索引
用大文本对象的列构建的索引
img主要用来查找文本中的关键字,而不是直接与索引中的值相比较。
fulltext索引跟其它索引大不相同,它更像是一个搜索引擎,而不是简单的where语句的参数匹配。
-
组合索引
用多个列组合构建的索引,这多个列中不允许有空值
组合索引的‘最左’原则
1598124783690.png
2.索引原理-索引与B+Tree
只有memory (内存)存储引擎支持哈希索引,哈希索引用索引列的值计算该值的hashCode,然后在hashCode相应的位置存执该值所在行数据的物理位置,因为使用散列算法,因此访问速度非常快,但是一个值只能对应一个hashCode, 而且是散列的分布方式,因此哈希索引不支持范围查找和排序的功能。 正常情况下,如果不指定索引的类型,那么一般是指B+Tree索引(或者B+Tree索引)。 存储引擎以不同的方式使用B+Tree索引。性能也各有不同,但是InnoDB按照原数据格式进行存储。
什么是B+Tree
B+Tree由B-Tree演变而来,B-Tree由二叉树演变而来。
让我们从头说起
- 顺序查找
顺序查找:就是从第一个元素开始,按索引顺序遍历待查找序列,直到找出给定目标或者查找失败
缺点:效率低-需要遍历整个待查序列
- 二分法查找
二分法查找:也称为折半法,是一种在有序数组中查找特定元素的搜索算法。工作原理是先将目标元素与中间节点进行比较,如果比中间节点大那么再与右边部分中间节点进行比较,以此类推直到找到目标元素。
二分查找原理是不是跟二叉树有些类似呢?
- 二叉树
二叉树也存在缺点,就是当数据是顺序插入时会改变树的形态
- 平衡二叉树实现过程
数据插入过程:
当有连续三个节点在一条直线时,旋转结构:
平衡二叉树经过条件的控制,再通过旋转的方式,完成树的平衡,不过,旋转次数过多。
在平衡二叉树稳定性的基础上,再优化一下,减少旋转次数,保证树的平衡性。 树的查找性能取决于树的高度,让树尽可能平衡,就是为了降低树的高度。
当数据存在内存中,红黑树效率非常高,但是文件系统和数据库都是存在硬盘上的,如果数据量大的话,不一定能一次性加载到内存。 所以一棵树都无法一次性加载进内存, 又如何谈查找。 因此就出现了专为磁盘等存储设备而设计的一种平衡多路查找树,也就是B树 与红黑树相比,在相同的的节点的情况下,一颗B/B+树的高度远远小于红黑树的高度。
- B树:
B树即平衡查找树,一般理解为平衡多路查找树,也称为B-树、B_ 树。
B树是一种自平衡树状数据结构,一般较多用在存储系统上,比如数据库或文件系统。
- B树结构---三阶B树
当达到三个节点时,将中间节点向上提,左右分别为其左右节点:
当根有两个节点时,小于左根节点的为左子节点,大于左根小于右根为中子节点,大于右根为右子节点
通过上面的三个案例就发现了几个问题
1.查找7和10所用步数不一样,就意味着时间不同,效率就不均衡,有的可能快,有的可能慢;
2.在进行范围查找时,需要反复的返回上一节点, 在进入下一节点,这种情况其实是树的遍历,叫做中序遍历,消耗了时间;
3.还有最重要的一点,在B树中,由于每一个节点就是一行数据,那么就是一次I0读取的节点更少。
1.磁盘读写代价更低 B树的数据和索引都在同一个节点上,那么每个块中包含的索引是少量的,如果想要取出比较深层 的数据,意味着要读取更多的块,才能得到想要的索引和数据,那么就增加了I0次数 而B+树中每个块能存储的索引是B树的很多倍,那么获取比较深层的数据,也只需要读取少量的块 就可以,那么就减少了磁盘的I0次数
2.随机IO的次数更少 B+树的优势是什么? 随机I/0是指读写操作时间连续,但访问地址不连续时长约为10ms(假设)。 顺序I/O是指读取和写入操作基于逻辑块逐个连续访问来自相邻地址的数据,时长约为0.1ms。 在相同情况下,B树要进行更多的随机I0,而B+树需要更多的顺序I0,因此B+树,效率也更快
3.查询速度更稳定 由于B+Tree非叶子节点不存储数据(data) ,因此所有的数据都要查询至叶子节点,而叶子节点的 高度都是相同的,因此所有数据的查询速度都是一样的。
总结
在数据库中,索引是提高数据的检索速度的,而索引是基于B+Tree的数据结构实现的。
而使用B+Tree的好处是:
1.降低了磁盘读写代价
2.顺序I/O提高效率
3.查询速度更稳定
聚簇索引和非聚簇索引 索引又分为聚簇索引和非聚簇索引两种。 在索引的分类中,我们可以按照索引的键是否为主键来分为“主索引”和“辅助索引" 使用主键键值建立的索引称为“主索引”,其它的称为“辅助索引”。 因此主索引只能有一个,辅助索引可以有很多个。