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由二叉树演变而来。

让我们从头说起

• 顺序查找

1598125336423.png

顺序查找:就是从第一个元素开始，按索引顺序遍历待查找序列，直到找出给定目标或者查找失败
缺点:效率低-需要遍历整个待查序列

• 二分法查找

1598125467230.png

二分法查找:也称为折半法，是一种在有序数组中查找特定元素的搜索算法。工作原理是先将目标元素与中间节点进行比较，如果比中间节点大那么再与右边部分中间节点进行比较，以此类推直到找到目标元素。
二分查找原理是不是跟二叉树有些类似呢?

• 二叉树

1598125555757.png

1598125586422.png

二叉树也存在缺点，就是当数据是顺序插入时会改变树的形态

• 平衡二叉树实现过程

1598125896407.png

数据插入过程：

1598125919067.png

当有连续三个节点在一条直线时，旋转结构：

1598125945483.png

1598125955476.png

1598125963196.png

1598125971219.png

1598125979093.png

1598126035292.png

1598126043829.png

平衡二叉树经过条件的控制，再通过旋转的方式，完成树的平衡，不过，旋转次数过多。

1598126103861.png

在平衡二叉树稳定性的基础上，再优化一下，减少旋转次数，保证树的平衡性。 树的查找性能取决于树的高度，让树尽可能平衡，就是为了降低树的高度。

当数据存在内存中，红黑树效率非常高，但是文件系统和数据库都是存在硬盘上的，如果数据量大的话，不一定能一次性加载到内存。 所以一棵树都无法一次性加载进内存， 又如何谈查找。 因此就出现了专为磁盘等存储设备而设计的一种平衡多路查找树，也就是B树 与红黑树相比，在相同的的节点的情况下，一颗B/B+树的高度远远小于红黑树的高度。

• B树：

B树即平衡查找树，一般理解为平衡多路查找树，也称为B-树、B_ 树。
B树是一种自平衡树状数据结构，一般较多用在存储系统上，比如数据库或文件系统。

• B树结构---三阶B树

1598126514747.png

当达到三个节点时，将中间节点向上提，左右分别为其左右节点：

1598126526851.png

当根有两个节点时，小于左根节点的为左子节点，大于左根小于右根为中子节点，大于右根为右子节点

1598126537930.png

1598126546131.png

1598126558635.png

1598126569803.png

1598126582858.png

1598126698861.png

1598126764764.png

通过上面的三个案例就发现了几个问题
1.查找7和10所用步数不一样，就意味着时间不同，效率就不均衡，有的可能快，有的可能慢；
2.在进行范围查找时，需要反复的返回上一节点， 在进入下一节点,这种情况其实是树的遍历，叫做中序遍历，消耗了时间；
3.还有最重要的一点，在B树中，由于每一个节点就是一行数据，那么就是一次I0读取的节点更少。

1598126867067.png

1598126893323.png

1598126920044.png

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.查询速度更稳定

聚簇索引和非聚簇索引 索引又分为聚簇索引和非聚簇索引两种。 在索引的分类中，我们可以按照索引的键是否为主键来分为“主索引”和“辅助索引" 使用主键键值建立的索引称为“主索引”，其它的称为“辅助索引”。 因此主索引只能有一个，辅助索引可以有很多个。

1598128448762.png