一、什么是索引?

索引(Index)是帮助MySQL高效获取数据的数据结构

本质上是一个文件,文件中按照特定的顺序记录数据字段(可能是主键,可能是其他字段,可能是rowid,也可能是好几个字段)和实际数据存储位置。

有了索引,我们只需要在索引里去检索这条数据就行了,找到数据存放在的磁盘地址后,就能找到相应的数据。

二、索引的类型有哪些?

普通(Normal)索引:嗯...就真的很普通,没有任何限制,也叫非唯一索引;

ALTER TABLE tbl_name ADD INDEX index_name (column_list);

唯一(Unique)索引:键值不能重复;主键(index)索引是一种特殊的唯一索引,它的键值不能为空。

ALTER TABLE tbl_name ADD PRIMARY KEY (column_list);

ALTER TABLE tbl_name ADD UNIQUE index_name (column_list);

全文(Fulltext)索引:只能对char/varchar/text类型的字段创建,可解决like查询效率低的问题。

ALTER TABLE tbl_name ADD FULLTEXT index_name (column_list);

三、索引是一个什么样的数据结构?

如下展开推演:

1.二叉查找树BST(Binary Search Tree)

原理:

二叉查找树的左子树所有节点都小于父节点,右子树所有的节点都大于父节点。
1.png

缺点:

如果插入的数据是有序的,例如1、2、3、4、5,会产生一种极端的情况:
2.png

这样的数据结构查询效率很不稳定,树的结构完全取决于插入顺序,左右不够平衡。

2.平衡二叉树AVL Tree

(AVL树的名字来源于它的发明作者G.M. Adelson-Velsky 和 E.M. Landis,又名Balanced Binary Search Tree)

原理:

左右子树深度差绝对值不能超过1。

按照我们之前“斜树”的顺序插入数据:

3.png
但插入后的结构违反定义的规则后,会发生左旋和右旋保证深度。

下图仅演示左旋和右旋的含义:
4.png
左旋示例(https://www.cnblogs.com/ZenoLiang/p/10954174.html)
5.jpg
左旋动图展示(https://www.pianshen.com/article/9358141953/)
6.png
右旋示例(https://www.cnblogs.com/ZenoLiang/p/10954174.html)
7.gif
右旋动图展示(https://www.pianshen.com/article/9358141953/)
那么这个树的节点是怎么存储索引的呢?

节点上存储了:索引的键值、这个节点对应数据的磁盘地址以及左右两个节点的引用。
7.png
平衡二叉树存储结构(来源:古泡笔记)
虽然看起来已经很不错了!但是每个节点存储的数据太少了;这表明,如果我们在查找数据时,可能会访问大量的节点,这也就意味着我们和磁盘交互的次数可能非常多!嗯,还得继续进化!

3.多路平衡查找树B Tree(Balanced Tree)

原理:

分叉数(路数)永远比关键字数多1;节点上的键值数量即为关键字数。
8.png
三路平衡查找树(来源:古泡笔记)
三路平衡查找树深度为n时,最多能存储3的n次方个节点,每个节点能存放2个键值;路数增加带来的深度减小,显而易见。

嗯,感觉已经很强了......但是还能超进化!

4.加强版多路平衡查找树B+T
9.jpg
加强版多路平衡查找树示例 (http://www.liuzk.com/410.html)
10.jpg
加强版多路平衡查找树示例(来源:古泡笔记)
和B-T不同的地方:

A.B+树关键字的个数路数相同;

B.B+树除了叶子节点都不存放数据(地址),仅存放键值以及子节点的引用。

C.B+树的叶子节点有指向相邻叶子节点的指针,每个叶子节点的最后一个数据都会只想下一个叶子节点的第一个数据(如果存在下一个叶子节点),形成一个有序链表的结构。

不同点 =》优点

优点:

A.非叶子节点不存放数据(地址),使得节点可以存储更多的关键字,从而拥有更多的路数;磁盘读写能力更强,一次磁盘加载的关键字更多;

B.扫表、扫库的能力更强(只需要遍历叶子节点,就可以获得所有的数据);

C.效率稳定(只能在叶子节点拿到数据,但是要注意了,这个树的深度更浅,且io的次数是固定的)

四、另一种索引方式:HASH
哈希查询速度快呀,根据关键字的值计算哈希码,通过哈希表直接找到数据存放的地址,时间复杂度O(1);

缺点:

A.哈希索引里的数据不是按照顺序存储的,因此不能用于排序;

B.根据关键字的值计算哈希码才能找数据的位置,因此不能用于范围查询,只能用于等值连接;

C.数据重复造成哈希冲突,降低效率。

五、B+树在不同存储引擎中的实现

1.MyISAM的实现

从存储上来看,共有.frm、.MYD、.MYI三个文件。

.frm:描述表结构的文件

.MYD:MyISAM的数据文件

.MYI:MyISAM的索引文件

索引文件 =》数据文件

2.InnoDB的实现

从存储上来看,共有.frm、.ibd两个文件。

.ibd:索引文件和数据文件是一个文件,InnoDB直接以主键为索引来组织数据的结构的存储。

(聚集索引:索引键值的逻辑顺序和表数据行的物理存储顺序是一致的;因此,主键就是聚集索引,其他就是非聚集索引)

主键索引:存储索引和数据

辅助索引:存储索引和主键值

辅助索引获取到主键值 =》去主键索引中拿数据

(多扫描了一个索引树,我们称它为“回表”)

主键索引的“主键“如何进行选择?

A.先找有没有主键;.

B.没有主键的话,找有没有不包含null值的唯一索引;

C.都没有的话,选择隐藏的rowid。

六、索引使用原则

1.在离散度高的列上建立索引;

2.联合索引

采用联合索引,需注意,创建index(a,b,c)相当于创建了三个索引index(a)、index(a,b)、index(a,b,c);联合索引的使用从最左边开始匹配,若sql语句不满足索引条件,则不能使用。

3.覆盖索引

select的数据列只用索引中的就能够取到,不需要再去数据区读取,这时候的索引我们称之为覆盖索引。

例如,对username、password建立联合索引,我用username、password去查询用户表,查询结果为username。

七、索引的使用

1.在用于where判断order排序和join的(ON)字段上创建索引;

2.索引的个数不能太多;(索引文件很大,过多的索引文件会会浪费我们的空间,降低查询效率)

3.离散度低的列,会扫描更多的行,不能建立索引;

4.频繁更新的列,不建立索引;

5.不能使用随机无序的值(身份证、UUID)作为主键索引;(页分裂)

6.联合索引要将离散度高的列放前面

7.索引列上不要使用函数以及数学表达式

8.like %用不到索引,可使用全文索引;

9.负向查询可能用不到索引。(优化器可能进行优化)

Q.E.D.

知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议

一个喜欢拔刀的萌新Coder