数据结构 4 时间复杂度、B-树 B+树 具体应用与理解

数据结构 4 时间复杂度、B-树 B+树 具体应用与理解

前言

面试中,经常会问到有关于MYSQL 索引的相关概念,我们之前也都学过有关树的概念、以及二叉树、二叉查找树、红黑树等。这一节,来关注经常是数据库索引中使用的B-树

在说这些之前,我们需要了解时间复杂度以及空间复杂度。

时间复杂度

时间复杂度,用于鉴定一个算法的好坏、很多时候,比如跑一个for 循环一个数组排序,有冒泡、二分法等方法。相比于冒泡。二分法很占优势,为什么呢?因为比较的次数少、并且做的无用功少、所以这个算法就好。

时间复杂度就是为了表示一个频繁度,这个频繁度怎么说呢。就是每执行一次循环,这就是一个频繁。

O(频度) 用O大写字符O表示,而不是零。

常见时间复杂度依次从小到大:

  1. O(1) 常数阶
  2. O(logn) 对数阶
  3. O(n) 线性阶
  4. O(n的平方) 平方阶
  5. O(n的立方) 立方阶
  6. O(2的n次方) (指数阶)

空间复杂度

空间复杂度,一般指占用的内存

时间换空间、空间换时间

这两个完全是可以等价交换的。比如我们想用

消耗时间长、换取占用空间少 这样会使应用程序响应变慢。但是占用内存少
消耗大量空间、换取快速的响应 例子:谷歌浏览器

B-树

切记,这里不念做B减数 这里的横岗没有任何意思,就是B树。

来说这个问题之前,首先了解一下:有关索引的简单内容。
我们都知道,索引,就是储存在本地磁盘上的一块数据结构,通过索引,我们能够快速查找数据库指定数据所在的位置。因为需要快速的查找出来。所以性能需要好的数据结构;例如:

  1. 二叉查找树 时间复杂度 O(logN)

一般情况下,二叉查找树以二分法查找,时间能够大大减少、一般遍历的最多次数就是二叉树的层级高度。

我们在上面已经了解过有关时间换空间、空间换时间的概念了。所以数据库的索引必须让其快起来,那就必须使用空间去换取时间,一般的索引库都是很大的。几个G甚至更多。

一般情况下,这么大的索引,我们没办法一次性读入到内存中。必须逐一加载的内存当中才可以。

因为是磁盘,就会有读取和写入(IO),使用二叉树虽然性能很高,但是不得不考虑磁盘的IO性能。

image

假设在使用二叉树来实现索引。我们查找的数字是7 最坏的情况下。也需要读取3次才可找到这个数字,那么有没有情况,就是把这个树的层级减少一些,我们读取的IO次数也就能减少。性能也就能提升。B-树就出来了

概念

将原来瘦高的二叉树变为矮胖的B-树。

B树是一种多路平衡查找树。每一个节点最多包含K个孩子,而K又被称为是B树的阶。这个阶取决于磁盘页大小。

特点

假设这个磁盘决定的B树阶为m

  1. 根节点至少有两个子女。
  2. 中间节点都包含(k-1)个元素和K个孩子,其中 m/2 <= k <= m

总结上面的话,就是说,这个k 就是节点的元素数量的范围取值范围在于
image.png

总是不能大于阶,并且也不能少于阶的一半。

  1. 每一个叶子节点都包含(k-1)个元素,其中 m/2 <= k <= m
  2. 所有叶子节点都是位于同一层的
  3. 每一个节点的元素从小到大排列,它的第(k-1)个元素正好是其k个孩子所包含元素的值域。(有点难以理解)

理解一下

image.png

画出一个B树,按照上面的条条框框 我们来说一下:

  1. B树根节点9 确实有两个子节点
  2. 中间的节点都会包含的元素数=子节点数-1。
  3. 比如2 6 这个元素的位置。

我们假设当前的k=2,所以当前节点的k-1=1 第一个元素2 正好是第2个子元素3,5的值域划分。因为

  1. 2 < 3 < 6
  2. 2 < 5 < 6

画个图,你就理解了。拿出原来的一小部分,我们来分析
image.png

通过箭头的指向,将子元素插入到指定的位置,你会发现什么??
image.png

看到了么?变成了一个线性数组,并且已经排序好了的。
image.png

B- 优势

相比于二叉查找树,我们的B-树在缩短与硬盘的交互次数IO ,提升性能。每次只需要读取一个节点,通过本节点在内存中的交互,即可通过值域的方式确定当前的值在那个节点下,依次找寻即可。

B-树 插入元素

假设我们插入一个4,通过遍历,我们发现,必须要插入到这个位置:

image.png

若这样插入,其实是违反规则的,因为父节点3,5有两个元素,所以它应该有三个儿子节点才对,所以这样行不通,需要改变!

往上方观察,2,6 已经是满节点的状态,并且根节点最多包含两个节点,那只能在根节点入手了。

image.png
就需要拆分节点和发生一系列的改变,其实还是很繁琐的。
这里只需要了解这个过程即可。不需要钻牛角尖
image.png

B树优势

B树最大的优势就是自平衡
以及始终能够维持多路平衡,能够最大程度减少磁盘的IO次数而达到性能提升

应用场景

那就是数据库索引了。以及文件系统。数据库这里常见的就是MongoDB 一款非关系型数据库。

而我们常用的Mysql数据库则用的是B+树作为索引的。我们下来说一说。

B+树

所谓B+树,其实就是B树的Plus版本,更加牛皮,所以牛皮在哪儿呢?那无非就是查询性能上,查询快呗。

既然是B树的一种扩展,那么肯定的,也包含B树该有的性质它都有,B+树有的一些性质,我们这里罗列一下:

特征

假设这里存在一个m阶的B+树,

  1. 有K个子节点的中间节点包含有K个元素,(B树这里是k-1),中间节点的元素不保存数据,只用来索引,所有的数据都保存在叶子节点。
  2. 所有的叶子节点包含了全部的元素信息,以及指向这些元素的指针。叶子节点本身按照关键词的大小自小而大顺序排列。
  3. 所有的中间节点元素都同时存在与子节点中。在子节点元素中是最大或者最小的元素。

是不是很懵逼?懵逼就对了

待会儿我们来解释一下,不要慌
image.png

  1. 中间节点有三个元素,所以它有三个子节点。没毛病
  2. 每个子节点都会包含父节点的一个元素,或者是最大。或者是最小。
  3. 它的所有数据都是储存与叶子节点的,并且使用指针指向下一个叶子节点,形成一个链表

为什么查询性能更优?

我们知道,B树是为了减少磁盘IO而创建出来的,因为二叉树虽然快,但是内存空间有限,一下子读取不了那么多。那就必须按照磁盘页的大小,依次读取节点到内存中。在数据量相同的情况下,因为B树每个节点上都存在数据。而不一样的是,B+树只有在叶子节点才会存在数据,所以呢 同样的情况下,B+树的这种结构,一次性能够放入内存的节点数量就可以增加了。因为B+树中间节点放的是引用地址嘛,这样读取性能又能够翻一翻。

  1. 单一节点储存了更多的元素。使得树更加矮胖,读取次数更少
  2. 查询都需要到达叶子节点,而后通过链表遍历、更加迅速。

小结

总结一下:为了什么发明出B树,因为通过空间换取时间的概念,索引是一个非常庞大的数据结构。而且

电脑的内存大小有限 不能一次性把二叉查找树读取进去,只能一点个节点一个节点的读取到里面。内存考虑完了。

硬盘IO 速度 因为索引的庞大,所以,在磁盘读取的时候,尽量使用少次的IO读取出我们需要的值,那就是最优解,所以呢,这个二叉树看起来很瘦高,要读取的IO数量太多了。所以呢?

B树就被发明出来了。为了啥?让二叉查找树变得矮胖。减少IO次数

B+树呢?作为B树的一个Plus版本。还是由于磁盘页的大小限制,只能读取少量的B树节点到内存中。因为B树节点就带有数据。而B+树就不一样了。因为中间节点不带数据,能够一次性读取好几个节点进去处理。所以呢,性能又提升了!

奥利给!

其实说了这么多,我们可以发现,所有的优化,是建立在当前磁盘不够、IO不够、内存不够大的基础上改善的。

参考

https://mp.weixin.qq.com/s/jRZMMONW3QP43dsDKIV9VQ

# B树  B+ 

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×