基于磁盘IO角度来看二叉树、B-tree树、B+树

分享 未结
1 1 1 8
小编 2019-07-19发布
收藏 点赞
来源: 波波说运维

概述

前面已经介绍了B-TREE的相关内容,所以这里对其架构就不多做介绍了,主要是从磁盘IO的角度来看,看一下为什么要用B树。

相关概念

B树这种数据结构常常用于实现数据库索引,因为它的查找效率比较高。

1、磁盘IO与预读

磁盘读取依靠的是机械运动,分为寻道时间、旋转延迟、传输时间三个部分,这三个部分耗时相加就是一次磁盘IO的时间,大概9ms左右。这个成本是访问内存的十万倍左右


正是由于磁盘IO是非常昂贵的操作,所以计算机操作系统对此做了优化:预读;每一次IO时,不仅仅把当前磁盘地址的数据加载到内存,同时也把相邻数据也加载到内存缓冲区中。因为局部预读原理说明:当访问一个地址数据的时候,与其相邻的数据很快也会被访问到。每次磁盘IO读取的数据我们称之为一页(page)。一页的大小与操作系统有关,一般为4k或者8k。这也就意味着读取一页内数据的时候,实际上发生了一次磁盘IO。

2、B-Tree与二叉查找树的对比

二叉查找树查询的时间复杂度是O(logN),查找速度最快和比较次数最少,既然性能已经如此优秀,但为什么实现索引是使用B-Tree而不是二叉查找树,关键因素是磁盘IO的次数。

数据库索引是存储在磁盘上,当表中的数据量比较大时,索引的大小也跟着增长,达到几个G甚至更多。当我们利用索引进行查询的时候,不可能把索引全部加载到内存中,只能逐一加载每个磁盘页,这里的磁盘页就对应索引树的节点。

下面先讲讲二叉树

一、 二叉树

先来看二叉树查找时磁盘IO的次数:假设定义一个树高为4的二叉树,查找值为10:


第一次磁盘IO:


第二次磁盘IO


第三次磁盘IO:


第四次磁盘IO:


从二叉树的查找过程了来看,树的高度和磁盘IO的次数都是4,所以最坏的情况下磁盘IO的次数由树的高度来决定。

从前面分析情况来看,减少磁盘IO的次数就必须要压缩树的高度,让瘦高的树尽量变成矮胖的树,所以B-Tree就在这样的背景下诞生了。

二、B-Tree

B-tree


m阶B-Tree满足以下条件:

1、每个节点最多拥有m个子树

2、根节点至少有2个子树

3、分支节点至少拥有m/2颗子树(除根节点和叶子节点外都是分支节点)

4、所有叶子节点都在同一层、每个节点最多可以有m-1个key,并且以升序排列

如下有一个3阶的B树,观察查找元素21的过程:


第一次磁盘IO:


第二次磁盘IO:


这里有一次内存比对:分别跟3与12比对

第三次磁盘IO:


这里有一次内存比对,分别跟14与21比对

从查找过程中发现,B树的比对次数和磁盘IO的次数与二叉树相差不了多少,所以这样看来并没有什么优势。

但是仔细一看会发现,比对是在内存中完成中,不涉及到磁盘IO,耗时可以忽略不计。另外B树种一个节点中可以存放很多的key(个数由树阶决定)。

相同数量的key在B树中生成的节点要远远少于二叉树中的节点,相差的节点数量就等同于磁盘IO的次数。这样到达一定数量后,性能的差异就显现出来了。


三、B树的新增

在刚才的基础上新增元素4,它应该在3与9之间:




四、B树的删除

删除元素9:



五、B+树

完B树,再来说说B+树,B+树和结构很类似,但查询性能上更高,具有如下的特性:

  • 有k个子树的中间节点包含有k个元素(B树中是k-1个元素),每个元素不保存数据,只用来索引,所有数据都保存在叶子节点;
  • 叶子节点中包含了全部元素的信息,按照关键字的大小从左到右排序;
  • 中间节点的元素同时存在于子节点中,在子节点元素中是最大。

下面放张示例图:


从图中可以看出,B+树中间节点和叶子节点有重复的数据,这里声明一下,中间节点保存的只是子树数据的子针,并不是真实的数据,所以中间节点的存储占用空间较少。

同时,叶子节点之间用指针连在一起,换句话说,叶子节点形成了一个链表,把所有的数据都存储了进来。

为什么这样设计,比起B树有什么好处呢?

首先,因为B+树的中间节点只是保存子树的最大数据和子树的子针,本身的占用空间较小,因此可以容纳更多节点元素,也就是说同样数据情况下,B+ 树会 B 树更加“矮胖”,因此查询效率更快。

其次,查找某个范围的数据,只需在B+树的叶子节点链表中遍历即可,不需要像B 树那样挨个中序遍历比较大小。总结来说,B+树的优点就是:

  1. 层级更低,IO 次数更少;
  2. 每次都需要查询到叶子节点;
  3. 查询性能稳定叶子节点形成有序链表,范围查询方便

总结

插入或者删除元素都会导致节点发生裂变反应,有时候会非常麻烦,但正因为如此才让B树能够始终保持多路平衡,这也是B树自身的一个优势:自平衡;B树主要应用于文件系统以及部分数据库索引,如MongoDB,所以目前大部分关系型数据库索引是使用B+树实现。

B树:有序数组+平衡多叉树;

B+树:有序数组链表+平衡多叉树;



回帖
  • 25天前

    s很生动

    0 回复