索引是如何提高查询性能的?

引言

问:如何提高一条查询SQL的性能?

答:最常用的方式就是加「索引」。

问:索引为什么就能提高查询性能?

答:索引就像一本书的目录,用目录查当然很快。

问:为什么通过目录就能提高查询速度呢。

答:……

都知道通过书目可以快速查询,这只是表象,背后的原因到底是什么呢?

下面就来扒一扒。



二叉树

由 n( n > 0)个有限节点组成一个具有层次关系的集合,看起来就像一个倒挂的树,因此称这样的数据结构为树。

一个节点的子节点个数叫做度,通俗的讲就是树叉的个数。树中最大的度叫做树的度,也叫做阶。一个 2 阶树最多有 2 个子节点即最多有 2 叉,因此这样的树称为二叉树。

二叉树是树家族中最简单的树。

二分查找

下面这幅动图就为二分查找的基本过程,也是最简单的一种二分查找。
图片

每次都把查询的范围减半,时间复杂度log2(n)。

单纯的一次查询,先排序,再二分查找,不见得比逐一扫描快。但是,大部分数据一生会被查询无数次,如果只在数据产生的时候排一次序,以后是不是就可以直接用二分查找。

优点:

  • 查找快

缺点:

  • 必须有序,需要提前排序
  • 每次查找都需要不断计算中间位置

二分查找树

假设一组数据不常变更,那么他们的位置也基本不变。可是每次查询都需要重新计算中间位置是一种浪费。

我们能不能把所有中间节点组织起来,每次使用时,直接取中间节点?

如图,找到所有单次二分查找的中间节点,把他们连起来,并用手提起最中间的那个节点,就是一棵二分查找树。

优点:

二分查找树就是通过数据结构的方式实现了二分查找算法,通过存储中间节点的数据,弥补了二分查找每次都要计算中间位置的缺点。

平衡二叉树

如果二分查找树不断进行修改,比如删除某些节点,经过一段时间后,最早那个中间节点的数据(根),很可能就不在中间了。

中间位置就像一个天平的支点,如果他不在中间了,那么整个天平就会失衡,失衡的世界就会坍塌成不伦不类的瘸树,甚至是降维成一个链表或者数组。

二分查找算法的关键在于有序和中间节点,而二分查找树的关键是中间节点的维护,如果维护的节点已经不在中间了,那么它就失去了意义。

所以必须保证「二分查找树」是一个正确的树,一个根节点在中心的树,一个左右子树层级(高度)基本相等(高度相差不超过1)的树,一个平衡的树。

平衡二叉树中最常见的就是红黑树:

红黑树规定了一系列节点颜色规则,以及对应的左旋和右旋操作来保证颜色规则,从而达到树的平衡性。

看到这花里胡哨的颜色以及复杂的规则,让人第一眼就望而却步,但所有的这些,也不过是为了保证二叉树的平衡性,由于维持平衡的操作太过麻烦,无法用一句话简单概括,只好用一堆人鬼难分的规则和步骤来实现,只要按着这些步骤就一定能实现二叉树的平衡。

平衡二叉树  =  二分查找树 + 平衡(左右高度相差不超过 1 )

平衡二叉树并未提高二分查找树的性能,它只是保正树不会被二向箔(多次增删改)打击降维成链表或不对称的残缺树,永远维持平衡。

另外,不仅仅是二叉树,其他种类的树,也是需要有序和平衡,才能发挥最大的威力。

多叉树(B-tree)

两个叉的树就能折半查询,理论可以提高一倍性能,那么多个叉是不是能提高更多倍性能?

如下图的 3 叉树

每个节点维护两个数据,并指向最多 3 个子节点。如图 3 个子节点的数据分别为:小于 17, 17 ~ 35 ,大于 35。

假设,从上图中查找 10 这个数,步骤如下:

  • 找到根节点,对比 10 与 17 和 35 的大小,发现 10 < 17 在左子节点,也就是第 2 层节点;
  • 从根节点的指针,找到左子节点,对比 10 与 8 和 12 的大小,发现 8 < 10 < 12,数据在当前节点的中间子节点,也就是第 3 层节点;
  • 通过上步节点的指针,找到中间子节点(第 3 层节点),对比 10 与 9 和 10 的大小,发现 9 < 10 == 10,因此找到当前节点的第二数即为结果。

加上忽略的 12 个数据,从 26 个数据中查找一个数字 10,仅仅用了 log3(26)≈ 3 次,而如果用平衡二叉树,则需要 log2(26)≈ 5 次,事实证明,多叉树确实可以再次提高查找性能。

多叉树是在二分查找树的基础上,增加单个节点的数据存储数量,同时增加了树的子节点数,一次计算可以把查找范围缩小更多。

多叉树之 B+tree

做为数据库的索引,无论用什么样的数据结构维护,这些数据最终都会存储到磁盘中。

鉴于磁盘  I/O 的性能问题,以及每次 I/O 获取数据量上限所限,提高索引本身 I/O 的方法最好是,减少 I/O 次数和每次获取有用的数据。

B-tree 已经大大改进了树家族的性能,它把多个数据集中存储在一个节点中,本身就可能减少了 I/O 次数或者寻道次数。

但是仍然有一个致命的缺陷,那就是它的索引数据与业务绑定在一块,而业务数据的大小很有可能远远超过了索引数据,这会大大减小一次 I/O 有用数据的获取,间接的增加 I/O 次数去获取有用的索引数据。

因为业务数据才是我们查询最终的目的,但是它又是在「二分」查找中途过程无用的数据,因此,如果只把业务数据存储在最终查询到的那个节点是不是就可以了?

理想很丰满,现实很骨瘦如柴,谁知道哪个节点就是最终要查询的节点呢?

B+tree 横空出世,B+ 树就是为了拆分索引数据与业务数据的平衡多叉树。

B+ 树中,非叶子节点只保存索引数据,叶子节点保存索引数据与业务数据。这样即保证了叶子节点的简约干净,数据量大大减小,又保证了最终能查到对应的业务数。既提高了单次 I/O 数据的有效性,又减少了 I/O 次数,还实现了业务。

但是,在数据中索引与数据是分离的,不像示例那样的?

如图:我们只需要把真实的业务数据,换成数据所在地址就可以了,此时,业务数据所在的地址在 B+ 树中充当业务数据。

树的结构最大的优点就是查询性能高,因此所有需要提高查询性能的都可以考虑树。

而现实中也确实有这样的例子,比如:

  • HashMap 中的数据冲突时,链表转化成红黑树;
  • 数据库索引使用的 B+ 树;
  • 搜索引擎倒排索引使用的字典树;

以上只是描述了数据库使用 B+ 树索引为什么能提高查询性能原因及简单过程。

并没有深入各种数据结构的细节,仅仅是,让大家对索引有一个感性的认识。

觉得本文有用,请转发、点赞或点击“在看”聚焦技术与人文,分享干货,共同成长更多内容请关注“数据与人”

为您推荐

发表评论

您的电子邮箱地址不会被公开。