31-B+树

作者: ducktobey | 来源:发表于2020-01-14 19:47 被阅读0次

B+树

B+树是B树的一种变体,常用语数据库和操作系统的问题件系统中

  • MySQL数据库的索引就是基于B+树实现的

下图为B+树的大概结构

B+树与前面研究的B树,B+树有以下特点:

  1. 分为内部节点(非叶子)与叶子节点两种节点
    叶子节点为最下面一层的节点,除了叶子节点以外的节点,都佳作内部节点,叶子节点与内部节点有以下特性

    • 内部节点只存储key,不存储具体数据
    • 叶子节点存储key和具体数据

    所以,可以理解为,B+树是用来存储key-value的,所以内部节点只存储key,叶子节点才用来存储key和数据

  2. 所有叶子节点,会形成一条有序链表
    从上图可以看出,叶子节点之间有箭头将节点串起来,并且节点的大小是有序的

当了解完B+树的特点以后,那么B+树到底有什么用呢?

由于B+树的非叶子节点,只用来存储key,所以当B+树节点与B树节点为同样大小的节点的话,B+树可以存储更多的key,因为一个key相对于一个节点具体数据来讲,占用的空间会更少,所以可以存储更多的key,这样,可以利用key快速找到对应的节点。

B树存储Key-Value的结构如下

所以,对比B树,B+树有以下一些优势

  1. 每个节点存储的key数量更多,树的高度更低
  2. 所有的具体数据都存储在叶子节点上,所以每次查询都要查到叶子节点,查询速度比较稳定
  3. 所有的叶子节点构成了一个链表,做区间查询时更方便

相关文章

  • 31-B+树

    B+树 B+树是B树的一种变体,常用语数据库和操作系统的问题件系统中 MySQL数据库的索引就是基于B+树实现的 ...

  • 水彩过程 | 树树树树

    练习了一下树的画法,用毛笔勾树干,扇形笔画树叶还是又快又方便的。因为不是写实风格,只要把树的意象画出来就可以,所以...

  • 树·树

    ​如果有来生,要做一棵树,站成永恒,没有悲欢姿势,一半在尘土里安详。一半在风里飞扬,一半洒落阴凉,一半沐浴阳光。 ...

  • 树,树……

    树,树…… ——洛尔迦 树,树, 枯了又绿。 脸蛋美丽的姑娘 在那里摘橄榄。 风,塔楼上的求爱者, 拦腰把她...

  • 橄榄树树树

    在建班级群的时候,我顺手打了三个树——橄榄树树树。是的,这是橄榄树第三次起航。 第一次,在北京,我说,我愿意在无人...

  • 树,与树

    (第一次学着简书里文友看图写诗,2020的图,各位讲究着看吧) 文/三少爷的糖 一颗树站在山头 遥望着远方,朦胧中...

  • 树,与树

    我不是一个很喜欢女生哭闹的人。 哭闹,意味着理智被情感摧毁。 理智没了,沟通渠道也就关闭了。 没有了沟通,剩下的就...

  • 树和树

    我的家门前有一棵柏树,不是什么稀罕的树,但它却挺直腰杆儿,坚定的伫立在我家门前,望着远方,似乎在等什么人又不像在等...

  • 树树秋声

    余秋雨说:生命,是一树花开,或安静或热烈,或寂寞或璀璨。日子,就在岁月的年轮中渐次厚重,那些天真的、跃动的、抑或沉...

  • 短篇‖树树

    这是一条幽静的古道,两旁尽是残垣断壁,竟也有一些台阶通向几栋还算有顶篷的石质的建筑物。我和我的伙伴着级上了一段...

网友评论

      本文标题:31-B+树

      本文链接:https://www.haomeiwen.com/subject/qwgaactx.html