最近看了一些
MySQL
相关的书籍和视频太多了,好东西如果不记录一下就会忘记,这里我记录一下感觉是重点的东西。
这里只说InnoDB
引擎
关于索引,我们需要知道哪些东西?
1.从原理上说为什么要使用索引?
使用索引避免全表扫描,提高检索效率,使用索引后就维护了一颗B+
树,B+
树是为磁盘或者其他直接存取辅助设备设计的一种平衡查找树,在B+
树中,所有记录节点都是按键值的大小顺序存放在同一层的叶子结点,各叶子结点通过指针进行连接(这里我默认大家最最基本的数据结构知识都会)。
先给出最简单一张图示意理解一下,但是这图是不全对,对于新手来说,可以用这张图理解概念,后面会说明
非叶子结点存放的就是目录,根据目录去找二分查找叶子结点中的记录,所有记录都在叶子结点上,并且是顺序存放的,如果查找的值小于25
,那么就从前指针指向的叶子里去查找记录,如果大于25
且小于50
,那么就从25
的后指针指向的叶子里去查找。
图放出来就能理解了,全表扫描和建立索引扫描就像你遍历链表和遍历平衡二叉树一样,哪个快一眼就看得出来,建立索引后,你能二分很快定位叶子结点然后去遍历叶子结点的数据。
当然大家也别误解,这个图是有点问题的,你可能会认为5、10、15、20是数组结构?其实是单链表结构,一个叶子结点是一个页,它是InnoDB
管理存储空间的基本单位,一个页的大小是16KB
,也就是最多能保证16KB
的连续存储空间,各个数据页可以组成一个双向链表,而每个数据页中的记录会按照主键值从小到大的顺序组成一个单向链表。所以上图省略了单链表结构,大家可千万不要以为是数组结构。
有人会疑问,一个页大小是16KB
,最多保证16KB
连续存储空间,而单链表怎么能是连续存储空间呢,怎么看都像是数组。其实真正的示意图如下,这个是《MySQL是怎样运行的》
书中的图,写的很好的书。
一个页不仅仅只是存放用户记录,还有很多头信息等标志位之类的东西,关于细节,大家可以看书,这里只说平时需要从逻辑上理解的东西,我们只需要看到User Records
这一块空间,每插入一条记录单链表就多了一个结点,就要从Free Space
这里申请一个记录大小的空间划分到User Records
部分,内存不够就新增下一个页。
来看看User Records
里面是什么样的
INSERT INTO index_demo VALUES(1, 4, 'u'), (3, 9, 'd'), (5, 3, 'y');
插入3条记录,页中的数据是单链表结构
这里可以看到每条记录之间是单链表结构,并不是数组结构。
如果大家对于
B+
树的插入和删除以及叶子左旋右旋感兴趣,可以阅读《MySQL技术内幕:SQL编程》
一书。如果对数据库的用法理解已经出神入化了,可以进阶阅读以下
《MySQL是怎样运行的》——作者: 小孩子4919
2.什么样的信息能成为索引,数据结构时怎么样的?
主键、唯一键或者能让数据有区分性的字段都能成为索引,数据结构主流的都是B+
树。
3.聚集索引和非聚集索引的区别
B+
树索引可以分为聚集索引与非聚集索引,两者的区别仅在于存放的数据内容。
聚集索引是根据主键创建的一棵B+
树,聚集索引的叶子结点不仅保存该列的键值信息,还保存了这一行数据记录的其他值信息,是一个完整的数据记录,聚集索引决定了表的物理排列顺序,一个表只能有一个聚集索引。
非聚集索引(辅助索引)是根据索引键创建的一棵B+
树,与聚集索引不同的是,其叶子节点仅存放索引键值,以及该索引键值指向的主键。非聚集索引定位到叶子结点后仍需要定位到主键信息来获取完整记录,其实这个过程就是回表。这种按照非主键列建立的B+
树需要一次回表操作才可以定位到完整的用户记录,所以这种B+
树也被称为二级索引(英文名secondary index
),或者辅助索引。
为什么我们还需要一次回表呢?直接把完整的用户记录放到叶子节点不就好了么?如果把完整的用户记录放到叶子节点是可以不用回表,但是太占空间了,每建立一棵B+
树都需要把所有的用户记录再都拷贝一遍,这就有点太浪费存储空间了。
辅助索引不包含行记录的所有数据,这就意味着每页可以存放更多的键值,因此其高度一般都要小于聚集索引。
这里只是一个例子,比如name
列添加了索引,条件筛选name
为Ellison
的人,先检索非聚集索引的B+
树查找到主键值14
,然后根据主键值14
继续在聚集索引B+
树进行检索操作,最终到达叶子结点获取整行的数据。这个查找方式也叫书签查找。也就是说,非聚集索引存储索引列信息和对应的主键值,查找可能会有2次,在非聚集索引一次查找,在聚集索引一次查找。
为什么说查找可能会有2次?其实还可能只有一次查找。不要慌,后面会继续讲解。
补充说明
1.如果一个主键被定义,该主键就是聚集索引(有的叫法可能叫聚簇索引、密集索引等)。
2.若没有主键被定义,该表的第一个唯一非空索引则作为聚集索引。
3.若不满足以上条件,innodb
内部会生成一个隐藏主键(聚集索引),这个隐藏主键是一个自增长的6字节的列。
4.回表与索引覆盖
4.1 什么是回表查询?
所谓的回表查询,就是非聚集索引先定位主键值,再到聚集索引定位行记录,它的性能较扫一遍索引树更低。
4.2 什么是索引覆盖?
explain
查询sql
执行计划时,Extra
显示Using index
时,能够触发索引覆盖。索引覆盖无需回表,需要查询的字段已经都在该索引树上了。索引已经“覆盖了”我们的查询需求,所以称为覆盖索引。
4.3 非聚集索引一定会查询多次吗?查询非聚集索引后一定要到聚集索引再次查询吗?
这也是面试问过的题目,答案是不一定!
比如有一个联合索引idx_c2_c3(c2, c3)
,select c3 from 表名 where c2 = 4;
就只需要查询一次辅助索引就可以了,因为我需要查询的值正好是索引之一,一棵索引树上就能获取SQL
所需的列数据(索引覆盖),无需回表,速度更快。如下图,辅助索引的B+
树就有条件筛选后我想要的c2
、c3
两个字段的数据。
我看到的能够比较完美的能解释这个问题的是这张图
每条目录项(非叶子结点)记录都由c2、c3、页号
这三个部分组成,各条记录先按照c2
列的值进行排序,如果记录的c2
列相同,则按照c3
列的值进行排序。
B+
树叶子节点处的用户记录由c2、c3和主键c1列
组成。
注意:当你建立
c2, c3
联合索引之后却看到Extra
显示Using index condition; Using filesort
,一般是使用了where c2 = "xx" order by c3 desc
这样的形式,有人认为Using filesort
就是因为c3
需要order by
才导致外部排序,实际上是你联合索引顺序建反了,index(c2, c3)
错误的写成了index(c3, c2)
,导致B+
树优先按照c3
排序,c3
相同时,才按照c2
排序,这样和写的sql
意义不符合,具体可以和上图结合理解。
你看看,你需要查找的数据字段和条件筛选的字段,在一颗B+
树就可以完成,不需要回表。
也千万要注意,联合索引时创建的仅仅是一个B+
树,如果单独分开创建2
个索引才是2
个B+
树。
本篇是简洁版,想要看数据插入后内存如何变化,请见我下一篇:图文并茂说MySQL索引——入门进阶必备