什么是B+Tree

推荐阅读

微服务:

springboot系列教程学习

源码:Javaweb练手项目源码下载

调优:十五篇好文回顾

面试笔试:面试笔试整理系列

B+Tree的定义

B+Tree是B树的变种,有着比B树更高的查询性能,来看下m阶B+Tree特征:

有m个子树的节点包含有m个元素(B-Tree中是m-1)

根节点和分支节点中不保存数据,只用于索引,所有数据都保存在叶子节点中。

所有分支节点和根节点都同时存在于子节点中,在子节点元素中是最大或者最小的元素。

叶子节点会包含所有的关键字,以及指向数据记录的指针,并且叶子节点本身是根据关键字的大小从小到大顺序链接。

更直观的图

1、红点表示是指向卫星数据的指针,指针指向的是存放实际数据的磁盘页,卫星数据就是数据库中一条数据记录。

2、叶子节点中还有一个指向下一个叶子节点的next指针,所以叶子节点形成了一个有序的链表,方便遍历B+树。

B+树的优势1、更加高效的单元素查找

B+树的查找元素3的过程:

第一次磁盘IO

第二次磁盘IO

第三次磁盘IO

这个过程看下来,貌似与B树的查询过程没有什么区别。但实际上有两点不一样:

a、首先B+树的中间节点不存储卫星数据,所以同样大小的磁盘页可以容纳更多的节点元素,如此一来,相同数量的数据下,B+树就相对来说要更加矮胖些,磁盘IO的次数更少。

b、由于只有叶子节点才保存卫星数据,B+树每次查询都要到叶子节点;而B树每次查询则不一样,最好的情况是根节点,最坏的情况是叶子节点,没有B+树稳定。

2、叶子节点形成有顺链表,范围查找性能更优

B树范围查找3-8的过程

a、先查找3

b、再查找4、5、6、7、8,中间过程省略,直接到8的查找

这里查找的范围跨度越大,则磁盘IO的次数越多,性能越差。

B+树范围查找3-11的过程

先从上到下找到下限元素3,然后通过链表指针,依次遍历得到元素5/6/8/9/11;如此一来,就不用像B树那样一个个元素进行查找。

总结

单节点可以存储更多的元素,使得查询磁盘IO次数更少。

所有查询都要查找到叶子节点,查询性能稳定。

所有叶子节点形成有序链表,便于范围查询。

PS:在数据库的聚集索引(Clustered Index)中,叶子节点直接包含卫星数据。在非聚集索引(NonClustered Index)中,叶子节点带有指向卫星数据的指针。

本文来自企鹅号 - Java开发者媒体

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 基于关系型数据库的App Inventor网络应用(3)

    第三节 初识Node-RED 开发环境简介 如图8所示,整个浏览器窗口被划分为四个部分: (1) 顶部黑色通栏,左侧显示Node-RED的LOGO,右侧显著位置...

    企鹅号小编
  • 如何给Hadoop集群划分角色

    温馨提示:要看高清无码套图,请使用手机打开并单击图片放大查看。 Fayson的github:https://github.com/fayson/cdhproje...

    企鹅号小编
  • 高并发分布式——主节点选举

    1. 概述 本文主要分享 Elastic-Job-Lite 主节点选举。 涉及到主要类的类图如下: ? . 2. 为什么需要选举主节点 首先我们来看一段官方对 ...

    企鹅号小编
  • 什么是B+Tree

    B+Tree的定义 B+Tree是B树的变种,有着比B树更高的查询性能,来看下m阶B+Tree特征: 1、有m个子树的节点包含有m个元素(B-Tree中是m-1...

    范蠡
  • 跨越时空:找回 RNN 消失的梯度

    斯坦福 NLP 的第 9 课后半部分给出了答案:主要应对梯度消失的措施是隐含层中采用更复杂的隐含单元。读者朋友们,你们可以回想下 RNN 的网络结果,隐含层中,...

    double
  • 多图,一文了解 8 种常见的数据结构

    前几天和丙弟交流,他说我们写作的人都是在不停地燃烧自己,所以需要不停地补充燃料。对于他的观点,我不能再苟同了——所以我开始狂补计算机方面的基础知识,这其中就包括...

    沉默王二
  • 【算法】图文并茂,一文了解 8 种常见的数据结构

    百度百科对数据结构的定义是:相互之间存在一种或多种特定关系的数据元素的集合。定义很抽象,需要大声地朗读几遍,才有点感觉。怎么让这种感觉来得更强烈,更亲切一些呢?...

    黄博的机器学习圈子
  • 最接地气的负载均衡算法(含代码)

    实现比较简单,在请求量远超可用服务节点数量的情况下,各个服务节点被访问的概率基本相同,主要应用在各个服务节点的性能差异不大的情况下。

    用户7676729
  • 深度优先搜索(DFS)两点之间的可行路径

    假如我们的目标是求点1到点6的所有路径,可以采用深度优先搜索法: 先将节点1加入路径,然后从1的后置节点中选择一个节点,1有两个后置节点,分别是2和3; 这里先...

    带萝卜
  • 【深入学习MySQL】MySQL的索引结构为什么使用B+树?

    在MySQL中,无论是Innodb还是MyIsam,都使用了B+树作索引结构(这里不考虑hash等其他索引)。本文将从最普通的二叉查找树开始,逐步说明各种树解决...

    Java_老男孩

扫码关注云+社区

领取腾讯云代金券