SQL性能优化系列——索引的原理[五]

2019年8月19日01:03:33 发表评论 70
摘要

1.为什么索引要存放到硬盘上?如何评价索引的数据结构设计的好坏?
2.使用平衡二叉树作为索引的数据结构有哪些不足?
3.B树和B+树的数据结构是怎样的?为什么常用B+树作为索引的数据结构?

既然前面说索引其实是一种数据结构,那么索引的数据结构究竟是怎样的?

如何评价索引的数据结构好坏

数据库服务器有两种存储介质:硬盘和内存。内存为临时存储,容量有限,且发生断电或故障重启时会造成数据丢失;硬盘属于永久性存储,所以需要把数据存储在硬盘上。

虽然内存读取速度很快,但还是需要将索引存到硬盘上,当在硬盘上进行查询时,也就产生了磁盘的I/O操作。相比内存的存取来说,磁盘I/O存取消耗的时间要高很多。通过索引查找某行数据时,需要计算磁盘I/O次数,次数越多,消耗时间越长。如果索引的数据结构尽可能减少磁盘的I/O操作,则消耗的时间也越少。

二叉树的局限性

二分查找法是一种高效的数据检索方式,时间复杂度为O(log2n),是不是二叉树就适合做索引呢?

先看最基础的二叉搜索树,搜索某个节点和插入节点的规则一样,假设搜索插入的数值为key:

1.如果key大于根节点,则在右子树中查找;

2.如果key小于根节点,则在左子树中查找;

3.如果key等于根节点,则直接返回根节点即可。

例如,对数列(34,22,89,5,23,77,91)创造出来的二叉树,如下图所示:

SQL性能优化系列——索引的原理[五]

但是存在特殊情况,就是二叉树的深度非常大。比如给出的数据顺序为(5,22,23,34,77,89,91),创造出来的二叉树如下图所示:

SQL性能优化系列——索引的原理[五]

能看出,第一个树深度是3,也就是说最多需要3次比较就可以找到节点,第二个树深度是7,最多需要7次比较才能找到节点。

第二棵树也是二分查找树,但是性能上已经退化成了一条链表,查找数据的时间复杂度变成了O(n)。为解决这个问题,人们提出了平衡二叉搜索树(AVL树),它在二分搜索树的基础上增加了约束,每个节点的左子树和右子树的高度差不得超过1,也即是说节点的左子树和右子树仍然为平衡二叉树。

注:常见平衡二叉树包括:平衡二叉搜索树、红黑树、数堆、伸展树。平衡二叉搜索树是最早提出来自平衡的二叉搜索树,当提到平衡二叉树时一般就是指平衡二叉搜索树。

上面说过数据查询的时间主要依赖于磁盘I/O的次数,如果采用二叉树的形式,即使通过平衡二叉树进行改进,树的深度也是O(log2n),当n比较大时,深度依然很高。比如:

SQL性能优化系列——索引的原理[五]

每访问一个节点就需要进行一次磁盘I/O操作,对于上面的树来说,需要进行5次I/O操作。虽然平衡二叉树比较的效率高,但是树的深度也同样高,意味着磁盘I/O操作次数多,会影响整体查询效率。

如果针对同样的数据将二叉树改造成M叉树(M>2)呢?当M=3时,同样的31个节点可以由下面的三叉树存储:

SQL性能优化系列——索引的原理[五]

能看到,当数据量大的时候,以及树的分叉M大的时候,M叉树的高度会远小于二叉树的高度。B树也就由此产生了。

什么是B树

B树英文名叫Balance Tree,平衡的多路搜索树,它的高度远小于平衡二叉树的高度,在文件系统和数据库系统中常用B树作为索引的数据结构。

B树数据结构如下:

SQL性能优化系列——索引的原理[五]

B树作为平衡的多路搜索树,它的每一个节点最多包含M个子节点,M称为B树的阶。同时能看到,每个磁盘块中包括了关键字和子节点的指针。如果一个磁盘块中包括了x个关键字,那么指针数就是x+1个。对于一个100阶的B树来说,如果有3层的话最多可以存储约100万的索引数据,对于大量的索引数据来说,采用B数的结构是非常适合的,因为高度远小于二叉树。

一个M阶的B树有如下特性:

1.根节点的儿子数的范围是[2,M];

2.每个中间节点的包含k-1个关键字和k个孩子,孩子的数量=关键字的数量+1,k的取值范围为[ceil(M/2),M];(ceil函数为向上取整)

3.叶子节点包括k-1个关键字(叶子节点没有孩子),k的取值范围为[ceil(M/2),M];

4.假设中间节点节点的关键字为:key[1],key[2],。。。,key[k-1],且关键字按照升序排序,即key[i]<key[i+1]。此时k-1个关键字相当于划分了k个范围,也即是对应k个指针,分别为:p[1],p[2],...p[k],其中p[1]指向关键字小于key[1]的子树,p[i]指向关键字属于(key[i-1],key[i])的子树,p[k]指向关键字大于key[k-1]的子树;

5.所有叶子节点位于同一层。

上面的图所示的B树刚好符合上面5点特征。

那么如何用B树来进行查找呢?假设想要查找关键字9,步骤如下:

1.与根节点的关键字(17,35)进行比较,9小于17,得到指针p1;

2.按指针p1找到磁盘块2,关键字为(8,12),9在8和12之间,得到指针p2;

3.按指针p2找到磁盘块6,关键字为(9,10),然后就找到了关键字9.

什么是B+树

B+树基于B树做了改进,主流的DBMS都支持B+树的索引方式,比如MySQL。B+树和B树的差异如下:

1.有k个孩子的节点就有k个关键字。即孩子数量=关键字数量。

2.非叶子节点的关键字也会同时存在在子节点中,并且是在子节点中所有关键字的最大(或最小)。

3.非叶子节点仅用于索引,不保存数据记录,跟记录有关的信息都存在叶子节点中。而B树中,非叶子节点既保存索引,也保存数据记录。

4.所有关键字都在叶子节点中出现,叶子节点构成一个有序链表,而且叶子节点本身按照关键字的大小从小到大顺序链接。

下图就是B+树,阶数为3,根节点中的关键字1、18、35分别是子节点(1,8,14)、(18,24,31)和(35,41,53)中的最小值。每一层父节点的关键字都会出现在下一层的子节点的关键字中,因此在叶子节点中包括了所有关键字的信息,并且每一个叶子节点都有一个指向下一个叶子节点的指针,这样就形成了一个链表。
SQL性能优化系列——索引的原理[五]

比如,要查找关键字16,B+树会自顶向下逐层查找:

1.与根节点(1,18,35)比较,16在1和18之间,得到指针p1(指向磁盘块2);

2.找到磁盘块2,关键字为(1,8,14),16大于14,得到指针p3(指向磁盘块7);

3.找到磁盘块7,关键字为(14,16,17),然后找到关键字16,所以关键字16对应的数据。

整个过程总共进行了3次I/O操作,看起来B+数和B树的查询过程差不多,但是B+树和B树的根本差异在于B+树的中间节点并不直接存储数据。这样好处有什么呢?

首先,B+树查询效率更稳定。“稳定”怎么理解呢?因为B+树每次只有访问到叶子节点才能找到对应的数据,而在B树中,非叶子节点也会存储数据,这样就会造成查询效率不稳定的情况:有时候访问到了非叶子节点就可以找到关键字,而有时需要访问到叶子节点才能找到关键字。

其次,B+树查询效率更高。因为B+树比B树更矮胖(阶数更大,深度更低),查询所需磁盘I/O也会更少。同样的磁盘页大小,B+树可以存储更多的节点关键字。

不仅是对单个关键字的查询上,在查询范围上,B+树的效率也比B树高。因为所有关键字都出现在叶子节点中,并通过有序链表进行了链接。而在B树中则需要通过中序遍历才能完成查询范围的查找,效率要低很多。(何谓中序遍历?中序遍历(LDR)是二叉树遍历的一种,也叫做中根遍历、中序周游。在二叉树中,中序遍历首先遍历左子树,然后访问根结点,最后遍历右子树。)

总结

磁盘的I/O操作次数对索引的使用效率至关重要。B树和B+树都可以作为索引的数据结构,在MySQL中采用的是B+树。通过以上对比,B+树在查询性能上更稳定,在磁盘页大小相同的情况下,树的结构更矮胖,所需进行的磁盘I/O次数更少,更适合进行关键字的范围查询。

(本文完)

  • 我的微信
  • 微信扫一扫
  • weinxin
  • 微信公众号
  • 微信公众号扫一扫
  • weinxin
  • A+
所属分类:SQL

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: