mysql为什么要用b+树,不用平衡二叉树做索引结构?

请先 登录 后评论

1 个回答

匿名

要分析这个问题,我们首先来分别看一下B+树,B树,平衡二叉树的结构特征。

平衡二叉树

1.非叶子节点最多拥有两个子节点。

2.非叶子节值大于左边子节点、小于右边子节点。

3.树的左右两边的层级数相差不会大于1。

4.没有值相等重复的节点。

94b6f6780c7a4fa985ce90eb41baf571

B-树

B-树和平衡二叉树稍有不同的是B-树属于多叉树又名平衡多路查找树(查找路径不只两个)。

  • 1.在一个节点中,存放着数据(包括key和data)以及指针,且相互间隔。
  • 2.同一个节点,key增序。
  • 3.一个节点最左边的指针不为空,则它指定的节点左右的key小于最左边的key。右边同理。中间的指针指向的节点的key位于相邻两个key的中间。
  • 4.B-Tree中不同节点存放的key和指针可能数量不一致,但是每个节点的域和上限是一致的,所以在实现中B-Tree往往对每个节点申请同等大小的空间。
  • 5.每个非叶子节点由n-1个key和n个指针组成,其中d<=n<=2d。
caf0cdbbb84a40538bfa273b5d6e7d65

B+树

0ff4725e241c44f5bf4da7ab7be6d561
  • 1.内节点不存储data,只存储key和指针;叶子节点不存储指针,存key和data。
  • 2.内节点和叶子节点大小不同。
  • 3.每个节点的指针上限为2d而不是2d+1。

平衡二叉树的问题

为了解决二叉树数据有序时出现的线性插入树太深问题,树的深度会明显降低,虽然极大提高性能,但是当数据量很大时,一般mysql中一张表达到3-5百万条数据

是很普遍,因此平衡二叉树的深度会非常大,mysql读取时会消耗大量IO。

不仅如此,计算机从磁盘读取数据时以页(4KB)为单位的,每次读取4096byte。平衡二叉树每个节点只保存了一个关键字(如int即4byte),浪费了4092byte,极大的浪费了读取空间。

B-树相对于平衡二叉树的优点

平衡二叉树基本都是存储在内存中才会使用的数据结构。

在大规模数据存储的时候,平衡二叉树往往出现由于树的深度过大而造成磁盘IO读写过于频繁,进而导致效率低下的情况。

我们知道要获取磁盘上数据,必须先通过磁盘移动臂移动到数据所在的柱面,然后找到指定盘面,接着旋转盘面找到数据所在的磁道,最后对数据进行读写。

磁盘IO代价主要花费在查找所需的柱面上,树的深度过大会造成磁盘IO频繁读写。根据磁盘查找存取的次数往往由树的高度所决定。

所以,只要我们通过某种较好的树结构减少树的结构尽量减少树的高度,B-树可以有多个子女,从几十到上千,可以降低树的高度,解决了平衡二叉树读取消耗大量内存空间的问题。

B-树的其他优点

数据库系统的设计者巧妙利用了磁盘预读原理,将一个节点的大小设为等于一个页,这样每个节点只需要一次I/O就可以完全载入。

为了达到这个目的,在实际实现B-Tree还使用了如下技巧:

每次新建节点时,直接申请一个页的空间,这样就保证一个节点物理上也存储在一个页里,加之计算机存储分配都是按页对齐的,就实现了一个node只需一次I/O。

另外如果经常访问的数据离根节点很近,而B树的非叶子节点本身存有关键字其数据的地址,所以这种数据检索的时候会相对其他数据结构更快。

B+树相对B-树的优点

B+树只有叶节点存放数据,其余节点用来索引,而B-树是每个索引节点都会有Data域。

所以从Mysql(Inoodb)的角度来看,B+树是用来充当索引的,一般来说索引非常大,尤其是关系性数据库这种数据量大的索引能达到亿级别。

所以为了减少内存的占用,索引也会被存储在磁盘上。那么Mysql如何衡量查询效率呢?– 磁盘IO次数。

B-树/B+树 的特点就是每层节点数目非常多,层数很少,目的就是为了就少磁盘IO次数。

但是B-树的每个节点都有data域(指针),这无疑增大了节点大小,增加了磁盘IO次数,磁盘IO一次读出的数据量大小是固定的,单个数据变大,每次读出的就少,IO次数增多,一次IO多耗时。

所以我们可以看到B+树的优点:

1、B+树的层级更少。

相较于B树B+每个非叶子节点存储的关键字数更多,树的层级更少所以查询数据更快;

2、B+树查询速度更稳定。

B+所有关键字数据地址都存在叶子节点上,所以每次查找的次数都相同所以查询速度要比B树更稳定;

3、B+树天然具备排序功能。

B+树所有的叶子节点数据构成了一个有序链表,在查询大小区间的数据时候更方便,数据紧密性很高,缓存的命中率也会比B树高。

4、B+树全节点遍历更快。

B+树遍历整棵树只需要遍历所有的叶子节点即可,而不需要像B树一样需要对每一层进行遍历,这有利于数据库做全表扫描。

请先 登录 后评论

扫一扫下方二维码,关注本站官方公众号
回复:面试题
获取永久解锁本站全部文章的验证码