勿以浮沙筑高台

• 什么是索引。

• 索引种类

• 主键索引

• 普通索引

• 联合索引（前导索引）

• 唯一索引

• 哈希表

• 有序数组

• 二分法查找

• 二叉查找树 BST(Binary Search Tree)

• AVL树 AVL Trees (Balanced binary search trees)

• 多路树（B-Tree）

• 加强版多路树（B+-Tree）

• MyISAM——非聚簇索引

• InnoDb——聚簇索引

• 列的离散度

• 组合索引最左匹配

• 回表

• 那些情况下会破坏索引

索引基础

什么是索引。

索引是在内存空间里开辟了一片空间地址，用来存储数据的地址指针，类似我们的目录，表明上只有1一条数据，点过去却是一整片数据。

索引种类

主键索引

当一张表，把某个列设为主键的时候，则该列就是主键索引

create table a (
id int primary key auto_increment, #设置为主键自增；类型为id
name varchar(20) not null default ''
);


创建表之后添加：

alter table 表名 add primary key (列明);


普通索引

在普通列上建立的索引即是普通索引;

create index 索引名 on 表名(列名);
alter table table_name add index 索引名(column1);


联合索引（前导索引）

ALTER TABLE 'table_name' ADD INDEX 索引名('列名A','列名B','列名C');


联合索引是前导索引构成
以上面语句为列，必须找到列名A才能找到列名B最后找到列名C；
下面举个例子：

ALTER TABLE 'student' ADD INDEX com_index('name','age','score');
#这个时候会走索引
explain select * from student where name = "1" and age = 12 and score = 13
#Mysql8中做了优化也会走索引
explain select * from student where name = "1" and score = 13 and age = 12
#只会走3分之1索引，因为中间断了，没有前导索引了
explain select * from student where name = "1" and age = 12
#不走索引，没有前导索引
explain select * from student where score = 13 and age = 12
#走索引
explain select * from student where name = "1" and score = 13 and age > 12
#走三分之1索引
#范围查询会破坏前导索引，后面的索引不生效
explain select * from student where name = "1" and age > 12 and score = 13
#模糊查询
#完全破坏索引
explain select * from student where name = "1" and age like "%12%" and score = 13
#模糊查询
#走三分之一的索引
explain select * from student where name = "1" and age like "12%" and score = 13


唯一索引

见名知义，索引列中的值必须是唯一的，但是允许为空值。于主键索引相比，主键不能为空

create table d(
id int primary key auto_increment ,
name varchar(32) unique
)


索引存储数据结构

哈希表

结构如下，主键计算hash值存放在内存地址上，如果有相同的则将数据发到最前面，是为了时间复杂度为0(1)；

这里图是有序的，实际上内存空间里存放的时候是无序的因此不适合范围查找。所以哈希表这种结构适用于只有等值查询的场景，比如Memcached及其他一些NoSQL引擎。

有序数组

即开辟一段连续的空间，存入进去，无论是查询还是范围查找，我们只有第一个的下标加上偏移量就可以查找。但是这种办法语句插入或者删除效率就不好，比如删除第二节没那么后面的节点都要往前移动一位，插入后面的值就需要往后移动一位。

上面2种数据结构都有相对明显的优点和缺点因此都不是我们常用的数据结构，常用的数据结构是B tree结构。

二分法查找

先对数据进行排序，然后长度除以2获得种中间长度mid，判断需要寻找的值再那个区间，区间里再再寻找到中间值除以2，得到中间的值，再次匹配，直到找到值或者前后双指针想等退出

算法链接：https://blog.csdn.net/qq_35059264/article/details/117286848

为了构建一个满足二分法查找，又满足快速查找和快速搜索的结构出现了。

二叉查找树 BST(Binary Search Tree)

二叉数有个顶根，比更小的数字放在左边，比根大的数字放在右边。数据结构如图

但是二叉数有个问题，如果顶端是数据比较小，就会变成单向链表如下图：并且随着数据的不断增加，插入检索的数据也会越来越多。效率越来越慢。为了解决这个问题，通过左右旋的方式，AVL Trees (Balanced binary search trees) 就出现了。

AVL树 AVL Trees (Balanced binary search trees)

AVL Trees (Balanced binary search trees) 平衡二叉树的定义:左右子树深度差绝对值不能超过 1。

如上图所示，当发现双边树根值差大于一，则会进行一个旋转，将顶根变为2.这样左右差值就平衡了。
右旋：实际变化这样的数据结构很好的利用了二分法查找，比顶根大的在右边，比顶根小的在左边。

虽然这样的结构能够优化我的读写速度但是还是不是最优的，想象一下我们读一次节点信息就是一次IO操作，那么随着数据量的增加，节点层次会变得越来越多，我们的读取数据也越来越慢。
那么我们如何才能解决呢？

多路树（B-Tree）

解决办法：

（1）让每个节点存储更多的数据。

（2）让节点上有更多的关键字。

这样我们的B树就悠然而生，定为每个节点包含的信息个数，，一个节点包含多个信息。这样树的高度就会缩减，但是宽度却会增加。
以下图为例：节点包容度为4，意思是只要满4个节点，则将任意节点往上提一层
这个时候我们插入16
1）会在15右边多个16节点信息。
2）其他任意节点会向上提一层问题：

1）B树不支持范围查询的快速查找，你想想这么一个情况如果我们想要查找10和35之间的数据，查找到15之后，需要回到根节点重新遍历查找，需要从根节点进行多次遍历，查询效率有待提高。

2）当存储数据量变大，所占空间会变大，这个时候一个磁盘块的存储数据不够，就会新增磁盘块，导致节点数据变高，磁盘IO次数就会变多。

所以加强版的B树出现了。

加强版多路树（B+-Tree）

真实的节点数据我们不存储data数据信息，只存节点信息，真正的数据信息再最后一层，下图为例:

05节点上面出现过了，但是最后一行数据还是出现了，这就是因为05的出现只是节点信息，并非真正的data信息。

举个例子:假设一条记录是1K，一个叶子节点(一页)可以存储16条记录。非叶子节点可以存储多少个指针?

假设索引字段是bigint类型，长度为8字节。指针大小在InnoDB源码中设置为6字节，这样一共14字节。非叶子节点(一页)可以存储16384/14=1170个这样的 单元(键值+指针)，代表有1170个指针。

树深度为2的时候，有1170^2个叶子节点，可以存储的数据为1170117016=21902400。

在查找数据时一次页的查找代表一次IO，也就是说，一张2000万左右的表，查询数据最多需要访问3次磁盘。

所以在InnoDB中B+树深度一般为1-3层，它就能满足千万级的数据存储。

因为节点信息占用的内存空间小，所以所有的节点信息子啊mysql启动的时候就加载导内存空间了。查询的时候只用检索节点信息找到对应的磁盘信息就可。

聚簇索引和非聚簇索引

MyISAM——非聚簇索引

MyISAM存储引擎采用的是非聚簇索引，非聚簇索引的主键索引和辅助索引基本上是相同的，只是主键索引不允许重复，不允许空值，他们的叶子结点的key都存储指向键值对应的数据的物理地址。

如下图：

在非聚簇索引当中的数据是根据数据的插入顺序保存。因此非聚簇索引更适合单个数据的查询。插入顺序不受键值影响。

辅助索引即普通索引，作用是当查询没有用到主键的时候用辅助索引

InnoDb——聚簇索引

InnoDb聚簇索引存储的值是data本身，而非聚簇索引存储的是主键的地址，因此聚簇索引的值越小越好。

聚簇辅助索引存储的是主键的键值，因此可以在数据行移动或者页分裂的时候降低成本，因为这时不用维护辅助索引。但是由于主键索引存储的是数据本身，因此聚簇索引会占用更多的空间。

聚簇索引值不能重复，插入新数据时需要检测主键是否重复，这需要遍历主索引的所有叶节点，在插入的时候会比非聚簇索引的值慢许多。而非聚簇索引保存的是节点地址，因此占用的空间更小，分布更集中，插入和查询都会比聚簇索引更快

索引使用原则

列的离散度

列的离散度公式

count(distinct(column_name)) : count(*)

列的全部不同值和所有数据行的比例。数据行数相同的情况下，分子越大，列的离散度就越高。
简单来说如果列的重复值越多，离散度就越低，重复值越少，离散度就越高。

举例：sex和name

select * from students from sex="男"

这个时候列的离散度较低，会回表查询多次。当回表查询次数和全文检索效率差不多时，其实并没有什么意义，反而会占用内存空间。

select * from students from name="zhangshan"

想法这种离散度低，节点更数少的，使用索引更有意义。

组合索引最左匹配

组合索引的本质既将多个列设定为普通索引，但是索引之间存在链路关系如图：

既要按前导索引进行匹配，不可让索引链路断掉。组合链路情况上面组合索引处又详细介绍。

回表

什么是回表，在Innodb当中辅助索引指向的就是聚簇索引的顶根节点，走玩非聚簇索引节点后又再次聚簇索引节点的这个过程就叫回表。

那些情况下会破坏索引

1、where后面索引列上使用函数

2、字符串不加引号，出现隐式转换(mysql8已优化)

3 、like 条件中前面带“% "

4、负向查询 NOT LIKE 不能 

5、 索引不会包含有NULL值的列 只要列中包含有NULL值都将不会被包含在索引中，复合索引中只要有一列含有NULL值，那么这一列对于此复合索引就是无效的。所以我们在数据库设计时不要让字段的默认值为NULL. 

6、排序的索引问题 MySQL查询只使用一个索引，因此如果where子句中已经使用了索引的话，那么order by中的列是不会使用索引的。（用联合索引解决）

注意一个SQL语句是否使用索引，跟数据库版本、数据量、数据选择度都有关系。