MySQL 索引原理
MySQL索引深入剖析
MySQL索引深入剖析
官方定义是: 索引(Index)是帮助MySQL高效获取数据的数据结构,简单来说,索引是一种数据结构。快速访问数据表中的特定信息,提高检索速度、 更新数据库表中数据。
索引的基本原理:
- 把创建索引列的内容进行排序
- 对排序的结果生成倒排表
- 在倒排表内容上拼接上数据行地址
- 查询数据时,先拿到倒排表内容,在取出数据行地址,从而拿到具体的数据
数据是以文件的形式存放在磁盘上面的,每一行数据都有它的磁盘地址,如果没有索引的话,我们要从千万行数据里面检索一条数据,只能依次遍历这张表的全部数据, 直到找到这条数据。但是我们有了索引之后,只需要在索引里面去检索这条数据就行了,因为它是 特殊的专门用来快速检索的数据结构,我们找到数据存放的磁盘地址以后,就可以拿到数据了。
生活中随处可见索引的例子,如火车站的车次表、图书的目录等。它们的原理都是一样的,通过不断的缩小想要获得数据的范围来筛选出最终想要的结果,同时把随机的事件变成顺序的事件,也就是我们总是通过同一种查找方式来锁定数据。
一:索引类型
1.1逻辑维度
- 主键索引:是一 种特殊的唯一索引它还多了一个限制条件,要求键值不能为空。主键索引用primay key 创建。
- 普通(Normal):也叫非唯一索引,是最普通的索引,没有任的限制。
- 联合索引:多个字段创建的索引,使用时遵循最左前缀原则。
- 唯一 (Unique):索引列中的值必须是唯一的,但是允许为空值。
- 空间索引:MySQL5.7之后支持空间索引,在空间索引这方面遵循OpenGIS几何数据模型规则。
1.2数据结构维度
- 哈希索引: 适合等值查询,检索效率高,一次到位。
- B+树索引:所有数据存储在叶子节点,复杂度为O(logn),适合范围查询。
- 全文(Fulltext):针对比较大的数据,比如我们存放的是消息内容、一篇文章,有 几KB的数据的这种情况,如果要解决like査询在全文匹配的时候效率低的问题,可以创建全文索引。只有文本类型的字段才可以创建全文索引,比如char、varchar、text。
- R-Tree索引: 用来对GIS数据类型创建SPATIAL索引
1.3物理存储维度
聚集索引与非聚集索引 都是B+树结构
-
聚集索引:聚集索引就是以主键创建的索引,在叶子节点存储的是表中的数据。
- 优点:
- 查询通过聚集索引可以直接获取数据,相比非聚集索引需要第二次查询(非覆盖索引情况下)效率高
- 对范围查询效率很高,因为数据是按照大小排列的
- 适合排序的场景,非聚集索引不适合
- 缺点:
- 维护索引代价很高,特别插入新行或者更新主键导致导致页的分裂
- 如果主键是随机ID(比如UUID),导致存储稀疏(磁盘碎片),可能比全表扫描还慢,或者主键比较大,导致辅助索引变的很大(节点占用更多的物理空间),这也是建议自增id作为主键的根本原因
- 优点:
-
非聚集索引:非聚集索引就是以非主键创建的索引,在叶子节点存储的是主键和索引列。
二:索引存储模型推演
2.1、二分查找
二分查找的一种思想,也叫折半查找,每一次,我们都把候选数据缩小了一半。如果数据已经排过序的话,这种方式效率比较高。 所以第一个,我们可以考虑用有序数组作为索引的数据结构。
2.2、模型推演
1、有序数组,它用于等值查询和比较查询效率非常高,但是更新数据的时候会出现一个问题, 可能要挪动大量的数据(改变index),所以只适合存储静态的数据。
2、哈希结构,类似k-v结构,也就是,key和value是一对一关系。它用于等值查询还可以,但是范围查询它是无能为力的。
- Mysql中使用较多的是hash索引和B+树索引,innodb默认是B+树索引,对于hash索引底层数据结构就是哈希表,因此如果需求场景为单条记录查询时(等值查询),可以选择哈希索引,查询性能最快,其余大部分场景建议选择B+树索引
3、为了支持频繁的修改,比如插入数据,我们需要采用链表。链表的话,如果是单链 表,它的查找效率还是不够高,所以,有没有可以使用二分査找的链表呢?为了解决这个问题,BST (Binary Search Tree)也就是我们所说的二叉査找树诞生
4、二叉查找树的特点是什么?
- 每个结点最多两个子树,分别称为左子树和右子树
- 左子节点的值小于当前节点的值,当前节点值小于右子节点值
- 顶端的节点称为根节点,没有子节点的节点值称为叶子节点
投影到平面以后,就是一个有序的线性表。二叉查找树既能够实现快速查找,又能够实现快速插入。
但是二叉查找树有一个问题,就是它的查找耗时是和这棵树的深度相关的,二叉树在最坏的情况下会退化成一个链表,在最坏的情况下时间复杂度会退化成O(n),相当于全表扫描。因此,一般二叉树不适合作为索引结构。
5、造成它倾斜的原因是什么呢?
因为左右子树深度差太大,这棵树的左子树根本没有节点——也就是它不够平衡。
所以,我们有没有左右子树深度相差不是那么大,更加平衡的树呢,这个就是平衡二叉树,叫做Balanced binary search trees,或者AVL树
平衡二叉树特点:它也是一颗二叉查找树,任何节点的两个子树高度最大差为1。所以就不会出现特殊化一个链表的情况
6、AVL树用于存储索引数据
首先,索引的数据,是放在硬盘上的。查看数据和索引的大小,当我们用树的结构来存储索引的时候,访问一个节点就要跟磁盘之间发生一次10操作。InnoDB操作磁盘的最小的单位是一页(或者叫一个磁盘块),大小是16K(16384 字节)。那么,一个树的节点必须设计成16K的大小,不然就会出现读不完或者读不够的情况。
如果我们一个节点只存一个键值+数据+引用,例如整形的字段,可能只用了十几个或者几十个字节,它远远达不到16K的容量。
想象一下,我们基于索引査找数据的时候,肯定是希望一次从磁盘加载很多的数据 到内存中进行比较,这样就可以尽快拿到完整的数据。如果一个节点只存1个这样的单 元,就需要读更多的节点,发生更多的I/O操作。如果是机械硬盘时代,每次从磁盘读取数据需要10ms左右的寻址时间,交互次数 越多,消耗的时间就越多
所以AVL树就会有下面的问题:
- 平衡二叉树插入或者更新时,需要左旋右旋维持平衡,维护代价大
- 如果数量多的话,树的高度会很高。因为数据是存在磁盘的,以它作为索引结构,每次从磁盘读取一个节点,操作IO的次数就多,消耗的时间就越多。
7、怎么解决这个问题?
- 第一个就是让每个节点存储更多的数据。
- 第二个节点上的关键字的数量越多,也就是意味着可以有更多的分叉(我们把它叫做"路数”)
- 第三因为分叉数越多,树的深度就会减少
这样,我们的树是不是从原来的高瘦高瘦的样子,变成了矮胖矮胖的,这个时候,我们的树就不再是二叉了,而是多叉,或者叫做多路。
8、多路平衡查找树(Balanced Tree)
这个就是B树,B树在枝节点和叶子节点存储键值、数据地址、节点引用。
特点:
- 分叉数(路数)永远比关键字数多1
比如:我们画的这棵树,每个节 点存储两个关键字,那么就会有三个分叉指向三个子节点(当然肯定不只存3个这么少)
9、那B树又是怎么实现一个节点存储多个关键字,还保持平衡的呢?跟AVL树有什 么区别?
B Tree在做检索时,检索效率非常高,但是在做数据插入和删除时,会破坏B Three本身的平衡,所以为了保持B Tree的平衡,需要对节点进行分裂、合并、转移等操作,跟AVL树的左旋和右旋是不一样的,而这个操作在节点数量较多的情况下性能影响较大。,所以 解释了为什么我们不要在频繁更新的列上建索引,或者为什么不要更新主键。
节点的分裂和合并,其实就是InnoDB页的分裂和合并。如果索引键值有序,写满一页接着开辟一个新的页,如果索引键值无序,存储过程造成大量磁盘碎片,带来频繁的page分裂和合并。
B树相对于平衡二叉树,就可以存储更多的数据,高度更低。但是最后会选择B+树呢?因为B+树是B树的升级版
10、B+Tree
- B+树非叶子节点上是不存储数据的,仅存储键值,而B树节点中不仅存储键值,也会存储数据。innodb中页的默认大小是16KB,如果不存储数据,那么就会存储更多的键值,相应的树的阶数(节点的子节点树)就会更大,树就会更矮更胖,如此一来我们查找数据进行磁盘的IO次数有会再次减少,数据查询的效率也会更快。
- B+树索引的所有数据均存储在叶子节点,而且数据是按照顺序排列的,链表连着的。那么B+树使得范围查找,排序查找,分组查找以及去重查找变得异常简单。
总结一下,InnoDB中的B+Tree索引带来的优势:
-
它是BTree的变种,BTree能解决的问题,它都能解决
B Tree解决的两大问题 :每个节点存储更多关键字;路数更多 -
扫库、扫表能力更强
如果我们要对表进行全表扫描,只需要遍历叶子节点就可以 了,不需要遍历整棵B+Tree拿到所有的数据 -
B+Tree的磁盘读写能力相对于B Tree来说更强
根节点和枝节点不保存数据区, 所以一个节点可以保存更多的关键字,一次磁盘加载的关键字更多 -
排序能力更强
因为叶子节点上有下一个数据区的指针,数据形成了链表 -
效率更加稳定
永远是在叶子节点拿到数据,所以I0次数是稳定的
同样索引带来的问题或者缺点?
- 会降低插入、删除、更新表的速度,因为执行写操作时,还有操作索引文件
- 索引需要占用物理空间,除了数据表占数据空间之外,每个索引还要占一定的物理空间,如何要建立聚集索引,需要的空间更大,如何非聚集索引很多,一旦聚集索引改变,所有的非聚集索引都会跟着变动。所以建议不要随便改变主键值。
三:为什么不用红黑树?
红黑树也是BST树,但是不是严格平衡的,不需要像AVL树那样严格平衡,通过变色和旋转来保持平衡。
- 节点分为红色或者黑色。
- 根节点必须是黑色的。
- 叶子节点都是黑色的N U LL节点。
- 不允许两个相邻的红色节点。
- 从任意节点出发,至惧每个叶子节点的路径中包含相同数量的黑色节点。
- 从根节点到叶子节点的最长路径(红黑相间的路径)不大于最短路径(全部是黑色节点)的2倍。
为什么不用红黑树?
- 1、只有两路,树层数过高
- 2、不够平衡
红黑树一般只放在内存里面用。例如Java的Map,它可以用来实现一致性哈希。
四:B+Tree作为索引的数据结构带来的好处
由于在B+ Tree中,每个节点不存存储数据区,只需要存储键值+指针,使得B+ Tree在每个节点存储的路数更多。
假设索引字段+指针大小一共是16个字节,那么一个Page页(一个节点)能存储1000个这样的单元(键值+指针)。假设一条记录是16bytes,一个叶子节点(一页)可以存储10条记录!
当数的深度是3的时候,就有1000^2个叶子节点,可存储的数据为1000 x1000 x 10 =10000000(千万)
也就是说,在InnoDB中B+树的深度在3层左右,就能满足千万级别的数据存储。
4.1、InnoDB 索引存储:每张InnoDB的表有两个文件(.frm和.ibd)
在InnoDB的某个索引的叶子节点上,它直接存储了我们的数据。 所以,为什么说在InnoDB中索引即数据,数据即索引,就是这个原因。
-
但是这里会有一个问题,一张InnoDB的表可能有很多个多索弓|,数据肯定是只有—份的那数据在哪个索引的叶子节点上呢?
这里的就是聚集索引(聚簇索引),就是索引键值的逻辑顺序跟表数据行的物理存储顺序是一致的。InnoDB组织数据的方式就是(聚集)索引组织表(clustered index organize table)如果说一张表创建了主键索引,那么这个主键索引就是聚集索引,决定数据行的物理存储顺序。
-
那主键索引之外的索引,会不会也把完整记录在叶子节点放一份呢?
并不会,因为这会带来额外的存储空间浪费和计算消耗。刚才已经讲了,如果有主键索引,那么主键索引就是聚集索引。其他的索引统一叫做"二级索引”(secondary index)。二级索引存储的是二级索引的键值,例如在name上建立索引,节点上存的是name 的值(很明显,它的键值逻辑顺序跟物理行的顺序不一致)。而二级索引的叶子节点存的是这条记录对应的主键的值。
-
二级索引检索数据的流程是这样的
当我们用name索引查询一条记录,它会在二级索引的叶子节点找到,然后拿到主键值,然后再到主键索引的叶子节点拿到数据。
-
为什么不存地址而是存键值?因为地址会变化。
从这个角度来说,因为主键索引比二级索引少扫描了一棵B+Tree (避免了回表), 它的速度相对会快一些。
-
如果一张表没有主键怎么办?
那完整的记录放在哪个索引的叶子节点?或者, 这张表根本没有索引呢?数据放在哪里?
1、 如果我们定义了主键(PRIMARY KEY),那么InnoDB会选择主键作为聚集索弘
2、 如果没有显式定义主键,则InnoDB会选择第一个不包含有NULL值的唯一索引 作为主键索引。
3、 如果也没有这样的唯一索引,则InnoDB会选择内置6字节长的ROWID作为隐 藏的聚集索引,它会随着行记录的写入而主键递增。
五:B+树 索引搜索过程
###表结构
CREATE TABLE `user` (
`id` int(11) NOT NULL,
`name` varchar(255) DEFAULT NULL,
`age` int(11) DEFAULT NULL,
`sex` int(1) DEFAULT NULL,
PRIMARY KEY (`id`),
KEY `idx_age` (`age`) USING BTREE
) ENGINE=InnoDB DEFAULT CHARSET=utf8;
insert into user values(100,'1',43,'0');
insert into user values(200,'2',48,'0');
insert into user values(300,'3',36,'1');
insert into user values(400,'4',32,'0');
insert into user values(500,'5',37,'1');
insert into user values(600,'6',49,'0');
insert into user values(700,'7',28,'1');
select * from user where age=32;
- idx_age索引的索引结构图:
id主键索引,聚族索引结构图
- 1搜索idx_age索引树,将磁盘块1加载到内存,由于32<37,搜索左路分支,到磁盘寻址磁盘块2。
- 2将磁盘块2加载到内存中,在内存继续遍历,找到age=32的记录,取得id = 400.
- 3拿到id=400后,回到id主键索引树。
- 4搜索id主键索引树,将磁盘块1加载内存,在内存遍历,找到了400,但是B+树索引非叶子节点是不保存数据的。索引会继续搜索400的右分支,到磁盘寻址磁盘块3.
- 5将磁盘块3加载内存,在内存遍历,找到id=400的记录,拿到R4这一行的数据,好的,大功告成。
什么是回表?拿到主键再回到主键索引查询的过程,就叫做「回表」
六:覆盖索引
覆盖索引:在查询的数据列里面,不需要回表去查,直接从索引列就能取到想要的结果。换句话说,你SQL用到的索引列数据,覆盖了查询结果的列,就算上覆盖索引了。
这就是项目中不要select *
, 而是要使用具体的字段 select id,age
的原因
七:索引下推
可以在索引遍历过程中,对索引中包含的字段先做判断,直接过滤掉不满足条件的记录,减少回表次数。
八:联合索引之最左前缀原则
- 联合索引的最左N个字段。比如组合索引(a,b,c)可以相当于建了(a),(a,b),(a,b,c)三个索引,大大提高了索引复用能力。
- 最左前缀也可以是字符串索引的最左M个字符。
九:索引创建建议
1、在用于where判断order排序和join的(on)、group by的字段上创建索引
2、索引的个数不要过多——浪费空间,更新变慢。
3、过长的字段,建立前缀索引。
4、区分度低的字段,例如性别,不要建索引——离散度太低,导致扫描行数过多。
5、频繁更新的值,不要作为主键或者索引——B+树的平衡导致 页分裂 ,影响效率
6、随机无序的值,不建议作为索引,例如身份证、UUID、MD5——无序,分裂
7、组合索引把散列性高(区分度高)的值放在前面
8、创建复合索引,而不是修改单列索引
9、查询不涉及的列、重复值较多的列、text、blob数据类型不要建立索引
9.1、大表添加索引
可以参考以下方法:
1.先创建一张跟原表A数据结构相同的新表B。
2.在新表B添加需要加上的新索引。
3.把原表A数据导到新表B
4.rename新表B为原表的表名A,原表A换别的表名;
十:索引失效
1、查询条件包含or,可能导致索引失效
2、如果字段类型是字符串,where时一定用引号括起来,否则索引失效
3、like条件中前面带%
4、联合索引,查询时的条件列不是联合索引中的第一个列,索引失效。
5、在索引列上使用mysql的内置函数,列运算(如,+、-、*、/),索引失效。
6、字符串不加引号,出现隐式的类型转化
7、负向查询:索引字段上使用(!= 或者 < >,not in,not like)时,可能会导致索引失效。
8、索引字段上使用is null, is not null,可能导致索引失效。
9、左连接查询或者右连接查询查询关联的字段编码格式不一样,可能导致索引失效。
10、mysql估计使用全表扫描要比使用索引快,则不使用索引
更多推荐
所有评论(0)