为什么Mysql用B+树做索引而不用B树

先从数据结构的角度来答。
应该知道B-树和B+树最重要的一个区别就是B+树只有叶节点存放数据,其余节点用来索引,而B-树是每个索引节点都会有Data域。
这就决定了B+树更适合用来存储外部数据,也就是所谓的磁盘数据。
从Mysql(Inoodb)的角度来看,B+树是用来充当索引的,一般来说索引非常大,尤其是关系性数据库这种数据量大的索引能达到亿级别,所以为了减少内存的占用,索引也会被存储在磁盘上。
那么Mysql如何衡量查询效率呢?磁盘IO次数。B-树(B类树)的特点就是每层节点数目非常多,层数很少,目的就是为了就少磁盘IO次数,当查询数据的时候,最好的情况就是很快找到目标索引,然后读取数据,使用B+树就能很好的完成这个目的,但是B-树的每个节点都有data域(指针),这无疑增大了节点大小,说白了增加了磁盘IO次数(磁盘IO一次读出的数据量大小是固定的,单个数据变大,每次读出的就少,IO次数增多,一次IO多耗时啊!),而B+树除了叶子节点其它节点并不存储数据,节点小,磁盘IO次数就少。这是优点之一。
另一个优点是什么,B+树所有的Data域在叶子节点,一般来说都会进行一个优化,就是将所有的叶子节点用指针串起来。这样遍历叶子节点就能获得全部数据,这样就能进行区间访问啦。

(数据库索引采用B+树的主要原因是 B树在提高了磁盘IO性能的同时并没有解决元素遍历的效率低下的问题。正是为了解决这个问题,B+树应运而生。B+树只要遍历叶子节点就可以实现整棵树的遍历。而且在数据库中基于范围的查询是非常频繁的,而B树不支持这样的操作(或者说效率太低))

至于MongoDB为什么使用B-树而不是B+树,可以从它的设计角度来考虑,它并不是传统的关系性数据库,而是以Json格式作为存储的nosql,目的就是高性能,高可用,易扩展。首先它摆脱了关系模型,上面所述的优点2需求就没那么强烈了,其次Mysql由于使用B+树,数据都在叶节点上,每次查询都需要访问到叶节点,而MongoDB使用B-树,所有节点都有Data域,只要找到指定索引就可以进行访问,无疑单次查询平均快于Mysql(但侧面来看Mysql至少平均查询耗时差不多)。

总体来说,Mysql选用B+树和MongoDB选用B-树还是以自己的需求来选择的。

B树相对于红黑树的区别

在大规模数据存储的时候,红黑树往往出现由于树的深度过大而造成磁盘IO读写过于频繁,进而导致效率低下的情况。为什么会出现这样的情况,我们知道要获取磁盘上数据,必须先通过磁盘移动臂移动到数据所在的柱面,然后找到指定盘面,接着旋转盘面找到数据所在的磁道,最后对数据进行读写。磁盘IO代价主要花费在查找所需的柱面上,树的深度过大会造成磁盘IO频繁读写。根据磁盘查找存取的次数往往由树的高度所决定,所以,只要我们通过某种较好的树结构减少树的结构尽量减少树的高度,B树可以有多个子女,从几十到上千,可以降低树的高度。

©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 转 # https://www.cnblogs.com/easypass/archive/2010/12/ 08/...
    吕品㗊阅读 9,853评论 0 44
  • B树的定义 一棵m阶的B树满足下列条件: 树中每个结点至多有m个孩子。 除根结点和叶子结点外,其它每个结点至少有m...
    文档随手记阅读 13,415评论 0 25
  • 今天看到一位朋友写的mysql笔记总结,觉得写的很详细很用心,这里转载一下,供大家参考下,也希望大家能关注他原文地...
    信仰与初衷阅读 4,767评论 0 30
  • 今天是五月二十日,于我是发工资的日子。 二月十四日是情人节,三月十四日是白色情人节,阴历七月初七,是神话爱情牛郎织...
    可靠的小薇儿阅读 477评论 0 0
  • 不知道是谁说的每天叫醒我的不是闹钟,而是梦想。然而对于住寝室的宝宝们来说叫醒我们的是室友的脚步声、拉窗帘声、开关门...
    安若愚阅读 161评论 3 0