为什么加索引?

在这里插入图片描述

如果上面的表,我们执行SQL语句

select * from table where Col2=89;

这样就会造成全表扫描，从第一行读取到倒数第二行，然后拿到这个89这个对应的值的位置，这样就做了6次才找到对应的值，但是加上索引就不一样了，接下来介绍索引是什么?

MySQL的索引是什么

索引是帮助MySQL高效获取数据的排好序的数据结构

索引的数据结构包括：

二叉树
红黑树
Hash表
B-Tree

索引存储方式

索引存储是按照KV方式进行存储的，key是这个索引元素，比如34，77等，value是这个索引在磁盘上面的文件地址，索引也是落地到磁盘上面的，因为数据是落在磁盘上面的，然后根据这个key对应的value去磁盘上面找到对应的值，然后输出。

数据使用索引的存储方式

二叉树

在这里插入图片描述

这样是不是就很快了

但是二叉树这个数据结构在某些情况下并没有什么效果，比如这个col1这一列，他是1-6的连续数据。

他的二叉树结构就是如下

在这里插入图片描述

虽然还是二叉树，但是这个和没有索引效果是一样的

所以MySQL最终选的不是二叉树
然后第一种二叉树排除了
然后对比一下红黑树

jdk1.8之后hashmap之前就是数组加链表存储的，假如链表非常长的时候，在hashmap里面查找元素性能也不是很好的快速查找所以在jdk1.8之后，在hashmap的底层链表被优化成红黑树，查找性能优化很高

红黑树的索引要是将1-7变成如下

在这里插入图片描述

红黑树也是二叉树，也叫做自平衡二叉树，二叉平衡树

但是MySQL最后之所以没有选择红黑树，因为红黑树在某些场景下并不能满足需求，因为用红黑树存储索引在某些情况下有如下问题：

层级太多，因为我们只有7个数据，层数即高度就这么多，如果要是很多的数据，那样不就更多了，假如树的高度是20，我们查找的元素在叶子结点,最快最快也要经过20次查找，也就要经过20次磁盘io查找。
MySQL是将这个数据结构存储在磁盘上面的，假如你先存储了10个数据，然后过了几天又存储了10个数据，中间间隔了很多天，因为数据都是要写到磁道上面，这段时间间隔可能写了很多其他数据，可能都跨磁道了，这样查询起来更慢了，因为他也是都磁盘上面找的。

树的高度越低，查找速度越快，最好对这个树的高度做一下优化，即使上千万数据，也让这个树的高度小于4，这个是可能的。

因为我们比如插入一条数据，他是先在磁盘上面开辟一个空间，然后再将数据存储上去，我们就可以一次开辟多个空间，这一行存储多个节点，然后这个多个节点又能分出很多只。

在这里插入图片描述

上图就得到了一个B树的结构,
所以就引出了B树，B树就是B-树，两个是一个东西

B树

他就是上面二叉树的变种，只不过每一个节点存储了多了key和value，而不是之前的一个

MySQL底层实际上用的是B树的变种，叫B+树

在这里插入图片描述

B+树他的叶子节点才会存储这个data，这个data对应的是这个数值在磁盘上面存储的位置，即我们最上面说的那个value
B+树每一个节点从左往右是依次递增的，而且15、18是在15-20之间，叶子结点之间用指针链接。
子节点大于等于他左边的父节点，小于右边的父节点
所有叶子结点也是从左往右依次递增，MySQL维护时候也是方便维护的
B+树也叫多路(叉)二叉树，底层也是二叉树

MySQL在B+树下如何查询：

查找30为例

首先将最上面的这个如15、56、77加载到内存，这是一次磁盘的IO操作，然后在内存查找
然后发现30是位于15、56之间，然后去他们两个之间的那个空白节点把下面第二行的地址拿到，然后将这个对应的第二行加载到内存，又是一次磁盘IO操作
然后发现这个30位于20和49之间，然后读这个第二行的20和49之间的地址，将对应的第三行读取到内存，第三次磁盘IO。

疑问：为什么不把所有数据都放在第一行呢？
答：假如数据量很大，几千万行数据，一次把几千万行数据直接加载到内存，那样内存大概率感触几百兆。而且一次磁盘IO撑死几M，可能就几十K，几百兆的一次磁盘IO完成不了，磁盘IO几百兆也需要几秒钟或者几十秒。

所以这个每一行每一点存储多少K的数据，MySQL给我们提供了一个默认的，16K，这个一次磁盘IO读取16K数据还是很简单的，这个值是MYSQL研发人员在多次测试的成果下给设置的默认值，单位是byte

SHOW GLOBAL STATUS LIKE 'Innodb_page_size';

在这里插入图片描述

为什么MYSQL默认设置为16K?

一般索引都是用INT或BIGINT

以bigint为例，比如这个索引15一般MySQL给他存储的是8B，然后他和56之间的空白格，这个是下一排的地址。是一个指针，索引和指针成对出现，这个一般是存储6B，MySQL给的值，所以一行16K*1024/(8+6)=1170个
叶子节点是没有这个空白区域，因为空白区域存放的是指针，叶子节点不需要指向下一位，所以没有这个指针，他的data占用的比较大，大概是1KB左右，所以叶子节点一个是存储16个元素

在这里插入图片描述