当前位置:   article > 正文

mysql 节点查根_数据结构与算法之美——B-树和B+树

mysql查询根节点

一、前言

mysql索引基于什么结构? hash表或者B+树。B+树的实现细节是什么?B-树和B+树有什么区别?联合索引在B+树中如何存储?B-树和B+树都是很基础的概念。要明白什么是B+树,要先了解什么是B-树。需要注意的是B-树就是B树,中间的横线并不是减号。

数据库索引为什么要使用树存储?①树的查询效率高,②维持相对顺序。那为什么没有使用二叉查找树来实现呢?二叉查找树查询的时间复杂度是O(logN),性能已经很高了,莫非B树比它更快?其实从算法逻辑上将,二叉查找树的查询次数和比较次数都是最小的。但是我们要考虑磁盘IO。

数据库索引是存储在磁盘上的,当数据量比较大时索引的大小可能有几个G甚至更多。当我们利用索引查询的时候,显然不能把整个索引全部加载到内存中。能做的只有逐一加载每一个磁盘块,这里的磁盘块对应 索引树的节点。

一颗100万的节点的平衡二叉查找树,树高是20。一次查询可能访问20个数据块,在机械硬盘时代,从磁盘随机读一个数据块需要10ms左右的寻址时间。也就是说对于1个100万行的表,如果使用二叉树来存储,单独访问一行可能需要20个10ms的时间。

为了提升读磁盘的效率,就必须访问尽量少的数据块。那么就不能使用二叉树这种“瘦高”的树。而应该使用“矮胖”的N叉树。这就是B-树的特征之一。

二、B树

B树是一种多路平衡查找树,它的每一个节点最多包含k个孩子,k被称为B树的阶,k的大小取决于磁盘块的大小。下面来具体介绍一下B-树(Balance Tree),一个m阶的B树具有如下几个特征:

1.根结点至少有两个子女。

2.每个中间节点都包含k-1个元素和k个孩子,其中 m/2 <= k <= m

3.每一个叶子节点都包含k-1个元素,其中 m/2 <= k <= m

4.所有的叶子结点都位于同一层。

5.每个节点中的元素从小到大排列,节点当中k-1个元素正好是k个孩子包含的元素的值域分划。

下面以一个3阶B-树为例,来看一下B-树的具体结构。树中的具体元素和刚才的二叉查找树是一样的。

98b4316e323f884ad5a449f2a8142d35.png

来看(2,6)节点,该节点有2个元素2和6,又有3个孩子1,(3,5),8。其中1小于元素2,(3,5)在元素(2,6)之间,8大于(3,5)。正好符合刚才所列的几条特征。

ab57f1290447023492b3eb83580ae2c7.png

三、B树查询

演示一下B树的查询过程。假如我们要查询的数值是5。

第一次磁盘IO

dd443d702be938fd1e6e4608ee8b682a.png

在内存中定位(和9比较):

eac3258354ce13967f038ec4eba96fe4.png

第2次磁盘IO:

28377ab804df6fbf0389a0f8448ded4e.png

在内存中定位(和2,6比较):

00ac9ef5932e3f0602974ee44d32f1ed.png

在内存中定位(和3,5比较):

8790d97592c26a2718eddff2cdb293eb.png

通过流程可以看出,B树在查询过程中比较次数其实不比二叉树少。尤其是当单一节点元素数量很多时。相比于磁盘IO的速度,内存中的比较耗时几乎可以忽略。所以只要树的高度足够低,IO次数足够少,就可以提升查询性能。

四、B树插入删除

B树插入新节点的过程比较复杂,而且分成很多种情况,在此只举最经典的例子。假如我们要插入的值是4。自顶向下查找4的节点位置,发现4应当插入到节点元素3,5之间。

25549765018469d3d70f0cc6f0c4d9a5.png

节点3,5已经是2元素节点,无法再增加,父亲节点2,6也是2元素节点。根节点9是单元素节点,可以升级为2元素节点,于是拆分节点3,5与节点2,6。让根节点9升级为2元素节点4,9。节点6独立为根节点的第二个孩子。

8277ea047469d7dc1caeefc19c8c23b9.png

为了插入1个元素,整个B树的多个节点发生了改变。也正因如此,让B树始终能维持多路平衡。这也是b树的一大优势:自平衡。

接下来说一下B树的删除。同样只举1个典型例子,删除元素11。自顶向下查找元素11的节点位置。

0fa143264863fd47c8262eb026e236e8.png

删除节点11之后,节点12只有1个孩子,不符合B树规范。因此找出12,13,15的中位数13取代节点12。节点12自身下移成为第1个孩子。(这个过程称为左旋)

08b9ce7e38e0f949ab7ef8be738666e1.png

6418cc894f0b47a4fa93baf92a47457e.png

三、B+树

B+树是B树的一种变种,有着比B-树更高的查询性能。

一个m阶的B+树具有如下几个特征:

1.有k个子树的中间节点包含有k个元素(B树中是k-1个元素),每个元素不保存数据,只用来索引,所有数据都保存在叶子节点。

2.所有的叶子结点中包含了全部元素的信息,及指向含这些元素记录的指针,且叶子结点本身依关键字的大小自小而大顺序链接。

3.所有的中间节点元素都同时存在于子节点,在子节点元素中是最大(或最小)元素。

举例来看下B+树的结构。

c685ea1e6ccaea141848c9222d2a6001.png

这种树不但节点之间含有重复元素,而且叶子节点还用指针连在一起。你说的这种就是B+树的几个特点。首先每一个父节点的元素都出现在子节点中,并且是子节点的最大(或最小)元素。

02aead0d690e30dfe7f43ade1a414a41.png

在上面这颗树中,根节点元素8是子节点2,5,8的最大元素,也是叶子节点6,8的最大元素。根节点元素15是子节点11,15的最大元素,也是叶子节点13,15的最大元素。

需要注意的是根节点的最大元素(这里是15)  也就等同于整个B+树的最大元素。以后无论插入删除多少元素,始终保证最大元素在跟节点中。

至于叶子节点,由于父节点的所有元素都出现在子节点,因此所有叶子节点包含了全量元素信息。 并且每一个叶子节点都带有指向下一个节点的指针,形成了一个有序链表。

5a9c4a8b69594ea76f8842e2c0c33787.png

B+树还具有1个特点,这个特点是在索引之外,却是至关重要的特点。那就是“卫星数据”的位置。所谓卫星数据,是指索引元素所执行的数据记录,比如数据库中的某一行在B-树中无论是中间节点还是叶子节点,都带有卫星数据。

B-树中的卫星数据:

80820e49923b747bda6b5e7919a2594b.png

在B+树中只有叶子节点带有卫星数据,其余中间节点仅仅是索引,没有任何数据关联。

B+树中的卫星数据:

c8a0323d1f43dbda79e787b02988d868.png

四、B+树查询

B+树的好处主要体现在查询性能上。下面我们通过单行查询和范围查询来做分析。

1、单元素查询

在单元素查询的时候,B+树会自顶向下逐层查找节点,最终找到匹配的叶子节点。比如我们要查找的是元素3。

第一次IO:

67c55261e3b21c4f8d00cb3741dc2f7a.png

第二次IO:

4a49bf405e944cf56cf4c5671a63b4aa.png

第三次IO:

a513dfca195b79f031dafb19653315a3.png

查询流程看起来和B-树差不多。但又2点不同。首先B+树的中间节点没有卫星数据,所以同样大小的磁盘块可以容纳更多的节点元素。这就意味着数据量相同的情况下B+树的结构比B-树更加“矮胖”,因此查询时IO次数也更少。其次B+树的查询必须找到叶子节点,而B-树只要找到匹配元素即可。无论是叶子节点还是中间节点。因此B-树的查找性能并不稳定(最好情况是只查根节点,最坏情况是查到叶子节点)。而B+树的每一次查找都是稳定的。

2、范围查询

B-树如何做范围查询呢?只能依靠中序遍历,比如我们要查找范围3到11的元素。B-树的范围查找过程如下:

自顶向下,查找到范围的下限(3)

f6331fd04a07fd2ea74eebd4bd3fef82.png

中序遍历到元素6:

966d468f8b2b565ca73412a7a983c3ea.png

中序遍历到元素8:

47ea42584a240318c83398639c5a842b.png

中序遍历到元素9:

96c3b2f1f84d624c723e2adc88ba5475.png

中序遍历到元素11,遍历结束:

a6bf88e137c71e895c25ac8cf96a33b9.png

B-树的范围查询很繁琐。

而B+树的查询,则要简单地多。只需要在链表上做遍历即可。

B+树的范围查找过程:

自顶向下,查找到范围的下限(3):

a1ec0990c915f1ab72ccd7308a44492b.png

通过链表指针,遍历到元素6, 8:

d95d4421ca57aa3d64fba448515d292e.png

通过链表指针,遍历到元素9, 11,遍历结束:

ea89a08cbd8b892cb14fb8ba097dcd2a.png

综上所述,B+树相比B-树的优点有3个:

①单一磁盘块存储更多的元素,使得查询的IO次数更少。

②所有查询都要查找到叶子节点,性能更稳定

③所有叶子节点形成有序链表,范围查找简便。

f6331fd04a07fd2ea74eebd4bd3fef82.png

5a9c4a8b69594ea76f8842e2c0c33787.png

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/不正经/article/detail/442157
推荐阅读
相关标签
  

闽ICP备14008679号