什么是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 条评论
登录 后参与评论

相关文章

来自专栏数据结构与算法

cf444E. DZY Loves Planting(并查集)

然后cf正解居然是网络流??出给NOIP模拟赛T1???¥%……&((……%&((

14030
来自专栏小鹏的专栏

堆排序

堆排序排序是优秀的算法,但是在实际应用中,快速排序的性能一般会优于堆排序, 尽管如此,堆排序仍然有很多应用,例如:作为高效的优先队列,最大优先队列应用于共享计算...

21960
来自专栏我是攻城师

理解Java8并发工具类ConcurrentHashMap的实现

前面的文章已经分析过List和Queue相关的接口与并发实现类,本篇我们来分析一下非常Java里面非常重要的一个数据结构HashMap。(注意Set类型在这里我...

28420
来自专栏数据结构与算法

洛谷P3178 [HAOI2015]树上操作

题目描述 有一棵点数为 N 的树,以点 1 为根,且树点有边权。然后有 M 个操作,分为三种:操作 1 :把某个节点 x 的点权增加 a 。操作 2 :把某个节...

36480
来自专栏mySoul

java队列

队列为特殊的线性表,队列的特点先进先出(FIFO),队列插入为入队,队列删除为出对。

31300
来自专栏Golang语言社区

用Golang写一个搜索引擎

本篇较长较枯燥,请保持耐心看完。 前面两章介绍了一下倒排索引以及倒排索引字典的两种存储结构,分别是 跳跃表 和 哈希表 ,本篇我们介绍另一种数据结构,他也被大量...

48570
来自专栏李家的小酒馆

二叉树的层次遍历

二叉树的层次遍历 基本思想 借助队列来实现 首先初始化队列.然后将根结点压入队列 然后出队,输出出队元素的值, 如果存在左孩子.则左孩子入队 如果存在右孩子,则...

23300
来自专栏高性能服务器开发

什么是B+Tree

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

36180
来自专栏计算机视觉与深度学习基础

Leetcode 41 First Missing Positive 正解不是盛传的桶排序

Given an unsorted integer array, find the first missing positive integer. For ...

18880
来自专栏desperate633

LintCode 简化路径题目分析代码

思路比较简单,遇到..就回到上一级,遇到.或者空就不处理。 我们使用一个队列来处理,同时将三个需要特殊处理的字符存到一个set里面

7710

扫码关注云+社区

领取腾讯云代金券