Mysql为什么添加索引可以提高查询速度

这篇文章我会分为以下部分进行讲解,如果你懂了,那么请绕行,别浪费你宝贵时间!

只有光头才可以变强,如果你要继续看,请保持空杯心态!

为什么添加索引会提高查询速度总结。索引提高了查询速度对增删改有影响吗。索引常用的算法原理分析B树和B+树等。

为什么添加索引会提高查询速度

一句话回答:索引可以将无序内容转换为有序的一个集合(相对),就如同新华字典,如果没有目录,那么查询一个汉字就需要很长时间了。

找到id=8的只需要这几步

最后总结一点:如果没有索引我们查询数据是需要遍历双向链表来定位对应的page,现在通过索引创建的“目录”就可以很快定位对应页上了!

其实底层实现的结构就是B+树,B+树作为树的一种实现能够让我们很快查找出对应内容。

索引可以提高查询速度,但是会降低增删改的速度,为什么

任何事情都有有利有弊,在于你自己权衡利弊。

首先来说B+树就是平衡树的一种。

NOTE:平衡树它就是一颗空树或者说它左右两个子树的高度相差的绝对值不会超过1,并且左右两个子树都是一颗平衡二叉树。

如果一棵普通B树在极端情况下是有可能退化成链表的,这样所谓的查询提速也就不存在了

前面我们就说了B+树本身就是平衡树,所以它是不会退化成链表的,树的高度都是比较低的(矮胖墩),在上面添加索引会提高查询速度中我们介绍的建立索引,说白了就是建立一个B+树。

B+树是一颗平衡树,如果我们对这棵树增删改的话,那肯定会破坏它的原有结构。要维持平衡树,就必须做额外的工作。正因为这些额外的工作开销,导致索引会降低增删改的速度

索引常用的算法原理分析:B树和B+树等

和索引相关的算法:二分查找法、二叉查找树、平衡二叉树、B树、B+树,内容长,但很有用,如果看、耐心看,珍惜时间!

我们在这些数字中用不同算法(1、2、3、5、6、7、9)找出6。

二分查找法原理:先将记录按顺序排列,查找时先按序列的中点位置为比较对象,如果要找的元素值小于该中点元素,则将查询范围缩小为左半部分;如果要找的元素值大于该中点元素,则将查询范围缩小为右半部分。以此类推,直到查到需要的值。

比如我们要找6,用了3次就查找到6这个数字了。如果是顺序查找,则需要查询5次(从第一个数字1开始,如果发现不是6,则继续查找下一个,直到查询到6)。

我们来对比一下这个例子顺序查找和二分查找法的平均查找次数:

顺序查找:(1+2+3+4+5+6+7)/7=4次

二分查找法:(3+2+3+1+3+2+3)/7≈2.4次

显然二分查找法相对顺序查找平均效率更高。

二叉树查找原理:二叉查找树中,左子树的键值总是小于根的键值,右子树的键值总是大于根的键值,并且每个节点最多只有两颗子树。

还是找6,这组数字的平均查找次数为:(3+2+1+2+3+4+5)/7≈2.9次

试想一下,如果3的右子树后面拖更多的数字,那查询效率得多低啊!

此时,平衡二叉树出场了。

平衡二叉树的定义:满足二叉查找树的定义,另外必须满足任何节点的两个子树的高度差最大为1。

如果要查值为6的记录,先找到根(这里是5),这里借用二分查找的思想,因为要找的值6大于中点元素5,所以需要查找的是5的右子树,而又因为6小于7,则应该找7的左子树,找到6这条记录,一共查找了3次。如果查找记录使用顺序查找,找到6这个值需要查5次。

平衡二叉查找树的平均查找次数:(3*4+2*2+1)/7≈2.4次

计算方式:该平衡二叉查找树中4个第三层的值需要查找3次,2个第二层的值需要查找2次,第一层也就是根的值只需要查1次。

上面我们说了顺序查找需要查找4次,比起来显然平衡二叉查找树的平均查找速度比顺序查找更快。

但是平衡二叉树有个缺点就是,每个节点最多只有两个分支,如果数据量比较大,要经历多层节点才能查询在叶子节点的数据。

如果在平衡二叉树的基础上,每个节点可以有多个分支,那即使在叶子节点的数据,是不是查询效率也比较高呢?这就引出了B树结构。

B树可以理解为一个节点可以拥有多于2个子节点的多叉查找树。B树中同一键值不会出现多次,要么在叶节点,要么在叶的子节点上。

比如用1、2、3、5、6、7、9这些数字构建一个B树结构,其图形如下:

与平衡二叉树相比,B树利用多个分支(平衡二叉树只有两个分支)节点,减少获取记录时所经历的节点数。

B树也是有缺点,因为每个节点都包含key值和data值,因此如果data比较大时,每一页存储的key会比较少;当数据比较多时,同样会有:“要经历多层节点才能查询在叶子节点的数据”的问题。这时,B+树站了出来。

B+树是B树的变体,定义基本与B树一致

B树和B+树不同点:

所有叶子节点中包含了全部关键字的信息各叶子节点用指针进行连接非叶子节点上只存储key的信息,这样相对B树,可以增加每一页中存储key的数量。B树是纵向扩展,最终变成一个“瘦高个”,而B+树是横向扩展的,最终会变成一个“矮胖子”。在B+树中,所有记录节点都是按键值的大小顺序存放在同一层的叶子节点上。B+树中的B不是代表二叉(binary)而是代表(balance),B+树并不是一个二叉树。

B+与B树最大的区别就是:B+树它的键一定会出现在叶子节点上,同时也有可能在非叶子节点中重复出现。而B树中同一键值不会出现多次。

总结

到此为止基本mysql查找算法就全部讲完了,我们主要来看mysql的聚簇索引和非聚簇索引。

这篇文章重点知识:为什么索引可以加速查询,加速查询算法的实现原理。




转载请注明:http://www.aierlanlan.com/rzgz/2031.html