MySQL中索引指的是什么

mysql"/>索引是什么?一张表有 500 万条数据,在没有索引的 name 字段上执行一条 where 查询:select * from user_innodb where name =小马;如果 name 字段上面

本文将详细说明MySQL中的索引指的是什么,边肖认为挺实用的,所以分享给大家参考,希望大家看完这篇文章能有所收获。

索引是什么?

一个表有500万条数据,在没有索引的名称字段上执行where查询:

选择* from user _ innodbewhere name=' pony ';如果名称字段上有索引怎么办?在名称字段上创建索引,并再次执行相同的查询。

alteretableuser _ innoddropdindexidx _ name;

alteretableuser _ innodaddindexidx _ name(名称);与没有索引的查询相比,有索引的查询效率相差数倍。

通过这个案例,我们应该能够直观地感受到索引极大地提高了数据检索的性能。

那么到底什么是指数呢?为什么会对我们的询价有这么大的影响?创建索引时发生了什么?

00-1010数据库索引是数据库管理系统(DBMS)中的一种排序数据结构,有助于快速查询和更新数据库表中的数据。

MySQL中索引指的是什么

数据以文件的形式存储在磁盘上,每行数据都有自己的磁盘地址。如果没有索引,我们必须从500万行数据中检索一条数据,我们只能依次遍历这个表中的所有数据,直到找到这条数据。

但是,我们有了索引之后,只需要在索引中搜索这个数据,因为它是专门用于快速检索的特殊数据结构。找到存储数据的磁盘地址后,就可以得到数据了。

00-1010在InnoDB中,有三种类型的索引:普通索引、唯一索引(主键索引是一种特殊的唯一索引)和全文索引。

普通(Normal):也叫非唯一指数,它是最常见的没有任何限制的指数。

唯一(Unique):唯一索引要求键值不能重复。另外需要注意的是,主键索引是一个特殊的唯一索引,它还有一个限制条件,要求键值不能为空。主键索引是用主键创建的。

全文(Fulltext):对于相对较大的数据,例如,如果我们存储消息内容并且有几千字节的数据,如果我们想解决like查询效率低的问题,我们可以创建一个全文索引。只有文本类型的字段才能创建全文索引,如char、varchar和text。

索引是一种数据结构,那么为了实现高效的数据检索,应该选择什么样的数据结构呢?

索引定义

索引类型

双十一过去后,你女朋友跟你玩了一个猜数字的游戏。猜猜我昨天买了多少钱。我给你五次机会。

10000?很低。30000?很高。接下来你会猜多少?20000。为什么不猜11000或者29000?

这是二分搜索法的一个想法,也叫二分搜索法。每次,我们都会将候选数据减少一半。如果数据已经排序,这种方法效率更高。

首先,我们可以考虑使用有序数组作为索引数据结构。

有序数组的等价查询和比较查询效率很高,但在更新数据时存在一个问题,可能需要移位大量数据(改变索引),因此只适合存储静态数据。

为了支持频繁的修改,比如插入数据,我们需要使用链表。如果是单一链表,其搜索效率还是不够高。

那么,有没有可以用二分搜索法的链表呢?

为了解决这个问题,我们称之为二叉查找树的二进制搜索树诞生了。

00-1010左子树中的所有节点都小于父节点,右子树小于父节点。

有的节点都大于父节点。投影到平面以后,就是一个有序的线性表。

MySQL中索引指的是什么

二叉查找树既能够实现快速查找,又能够实现快速插入。

但是二叉查找树有一个问题:查找耗时是和这棵树的深度相关的,在最坏的情况下时间复杂度会退化成 O(n)。

什么情况是最坏的情况呢?

还是刚才的这一批数字,如果我们插入的数据刚好是有序的,2、10、12、15、 21、28

这个时候 BST 会变成链表( “斜树”),这种情况下不能达到加快检索速度的目的,和顺序查找效率是没有区别的。

MySQL中索引指的是什么

造成它倾斜的原因是什么呢?

因为左右子树深度差太大,这棵树的左子树根本没有节点——也就是它不够平衡。

所以,我们有没有左右子树深度相差不是那么大,更加平衡的树呢?

这个就是平衡二叉树,叫做 Balanced binary search trees,或者 AVL 树。

平衡二叉树(AVL Tree)

平衡二叉树的定义:左右子树深度差绝对值不能超过 1。

是什么意思呢?比如左子树的深度是 2,右子树的深度只能是 1 或者 3。

这个时候我们再按顺序插入 1、2、3、4、5、6,一定是这样,不会变成一棵“斜树”。

MySQL中索引指的是什么

那 AVL 树的平衡是怎么做到的呢?怎么保证左右子树的深度差不能超过 1 呢? 例如:插入 1、2、3。

当我们插入了 1、2 之后,如果按照二叉查找树的定义,3 肯定是要在 2 的右边的,这个时候根节点 1 的右节点深度会变成 2,但是左节点的深度是 0,因为它没有子节点,所以就会违反平衡二叉树的定义。

那应该怎么办呢?因为它是右节点下面接一个右节点,右-右型,所以这个时候我们要把 2 提上去,这个操作叫做左旋。

MySQL中索引指的是什么

同样的,如果我们插入 7、6、5,这个时候会变成左左型,就会发生右旋操作,把 6 提上去。

MySQL中索引指的是什么

所以为了保持平衡,AVL 树在插入和更新数据的时候执行了一系列的计算和调整的操作。

平衡的问题我们解决了,那么平衡二叉树作为索引怎么查询数据? 在平衡二叉树中,一个节点,它的大小是一个固定的单位,作为索引应该存储什么内容?

第一个:索引的键值。比如我们在 id 上面创建了一个索引,我在用 where id =1 的条件查询的时候就会找到索引里面的 id 的这个键值。

第二个:数据的磁盘地址,因为索引的作用就是去查找数据的存放的地址。

第三个因为是二叉树,它必须还要有左子节点和右子节点的引用,这样我们才能找到下一个节点。比如大于 26 的时候,走右边,到下一个树的节点,继续判断。

MySQL中索引指的是什么

如果是这样存储数据的话,我们来看一下会有什么问题。

首先,索引的数据,是放在硬盘上的。查看数据和索引的大小:

select CONCAT(ROUND(SUM(DATA_LENGTH/1024/1024),2),'MB') AS data_len, 
CONCAT(ROUND(SUM(INDEX_LENGTH/1024/1024),2),'MB') as index_len 
from information_schema.TABLES 
where table_schema='gupao' and table_name='user_innodb';

当我们用树的结构来存储索引的时候,因为拿到一块数据就要在 Server 层比较是不是需要的数据,如果不是的话就要再读一次磁盘。访问一个节点就要跟磁盘之间发生一次 IO。InnoDB 操作磁盘的最小的单位是一页(或者叫一个磁盘块),大小是 16K(16384 字节)。

那么,一个树的节点就是 16K 的大小。 如果我们一个节点只存一个键值+数据+引用,例如整形的字段,可能只用了十几个或者几十个字节,它远远达不到 16K 的容量,所以访问一个树节点,进行一次 IO 的时候,浪费了大量的空间。

所以如果每个节点存储的数据太少,从索引中找到我们需要的数据,就要访问更多的节点,意味着跟磁盘交互次数就会过多。

如果是机械硬盘时代,每次从磁盘读取数据需要 10ms 左右的寻址时间,交互次数越多,消耗的时间就越多。

比如上面这张图,我们一张表里面有 6 条数据,当我们查询 id=37 的时候,要查询两个子节点,就需要跟磁盘交互 3 次,如果我们有几百万的数据呢?这个时间更加难以估计。

所以我们的解决方案是什么呢?

第一个,就是让每个节点存储更多的数据。

第二个,节点上的关键字的数量越多,我们的指针数也越多,也就是意味着可以有更多的分叉。

因为分叉数越多,树的深度就会减少(根节点是 0)。这样,我们的树是不是从原来的高瘦高瘦的样子,变成了矮胖矮胖的样子?

这个时候,我们的树就不再是二叉了,而是多叉,或者叫做多路。

多路平衡查找树(B Tree)

跟 AVL 树一样,B 树在枝节点和叶子节点存储键值、数据地址、节点引用。

它有一个特点:分叉数(路数)永远比关键字数多 1。比如我们画的这棵树,每个节点存储两个关键字,那么就会有三个指针指向三个子节点。

MySQL中索引指的是什么

B Tree 的查找规则是什么样的呢?

比如我们要在这张表里面查找 15。 因为 15 小于 17,走左边。 因为 15 大于 12,走右边。 在磁盘块 7 里面就找到了 15,只用了 3 次 IO。

这个是不是比 AVL 树效率更高呢? 那 B Tree 又是怎么实现一个节点存储多个关键字,还保持平衡的呢?跟 AVL 树有什么区别?

比如 Max Degree(路数)是 3 的时候,我们插入数据 1、2、3,在插入 3 的时候,本来应该在第一个磁盘块,但是如果一个节点有三个关键字的时候,意味着有 4 个指针, 子节点会变成 4 路,所以这个时候必须进行分裂(其实就是 B+Tree)。把中间的数据 2 提上去,把 1 和 3 变成 2 的子节点。

如果删除节点,会有相反的合并的操作。

注意这里是分裂和合并,跟 AVL 树的左旋和右旋是不一样的。

我们继续插入 4 和 5,B Tree 又会出现分裂和合并的操作。

MySQL中索引指的是什么

从这个里面我们也能看到,在更新索引的时候会有大量的索引的结构的调整,所以解释了为什么我们不要在频繁更新的列上建索引,或者为什么不要更新主键。

节点的分裂和合并,其实就是 InnoDB 页(page)的分裂和合并。

B+树(加强版B Tree)

B Tree 的效率已经很高了,为什么 MySQL 还要对 B Tree 进行改良,最终使用了 B+Tree 呢?

总体上来说,这个 B 树的改良版本解决的问题比 B Tree 更全面。

我们来看一下 InnoDB 里面的 B+树的存储结构:

MySQL中索引指的是什么

MySQL 中的 B+Tree 有几个特点:

  1. 它的关键字的数量是跟路数相等的;

  2. B+Tree 的根节点和枝节点中都不会存储数据,只有叶子节点才存储数据。搜索到关键字不会直接返回,会到最后一层的叶子节点。比如我们搜索 id=28,虽然在第一层直接命中了,但是全部的数据在叶子节点上面,所以我还要继续往下搜索,一直到叶子节点。

  3. B+Tree 的每个叶子节点增加了一个指向相邻叶子节点的指针,它的最后一个数据会指向下一个叶子节点的第一个数据,形成了一个有序链表的结构。

  4. 它是根据左闭右开的区间 [ )来检索数据。

B+Tree 的数据搜寻过程:

  1. 比如我们要查找 28,在根节点就找到了键值,但是因为它不是页子节点,所以会继续往下搜寻,28 是[28,66)的左闭右开的区间的临界值,所以会走中间的子节点,然后继续搜索,它又是[28,34)的左闭右开的区间的临界值,所以会走左边的子节点,最后在叶子节点上找到了需要的数据。

  2. 第二个,如果是范围查询,比如要查询从 22 到 60 的数据,当找到 22 之后,只需要顺着节点和指针顺序遍历就可以一次性访问到所有的数据节点,这样就极大地提高了区间查询效率(不需要返回上层父节点重复遍历查找)。

InnoDB 中的 B+Tree 的特点:

  1. 它是 B Tree 的变种,B Tree 能解决的问题,它都能解决。B Tree 解决的两大问题是什么?(每个节点存储更多关键字;路数更多) ;

  2. 扫库、扫表能力更强(如果我们要对表进行全表扫描,只需要遍历叶子节点就可以了,不需要遍历整棵 B+Tree 拿到所有的数据) ;

  3. B+Tree 的磁盘读写能力相对于 B Tree 来说更强(根节点和枝节点不保存数据区,所以一个节点可以保存更多的关键字,一次磁盘加载的关键字更多) ;

  4. 排序能力更强(因为叶子节点上有下一个数据区的指针,数据形成了链表) ;

  5. 效率更加稳定(B+Tree 永远是在叶子节点拿到数据,所以 IO 次数是稳定的)。

关于“MySQL中索引指的是什么”这篇文章就分享到这里了,希望

内容来源网络,如有侵权,联系删除,本文地址:https://www.230890.com/zhan/35996.html

(0)