6.3.2 B+树基本概念

B+是应用数据库所需而出现的一种B树的变形树。

一棵B+树需满足下列条件: 1)每个分支结点最多有m棵子树(子结点)。

2)非叶根(不是叶子的根结点)结点至少有两棵子树,其他每个分支结点至少有【m/2】(向下取整)棵子树。(B树是要求至少2棵子树)

3)结点的子树个数与关键字个数相等。

4)所有叶结点包含全部关键字及指向相应记录的指针,而且叶结点中将关键字按大小顺序排列,并且相邻叶子结点按大小顺序相互链接起来。

5)所有分支结点(可看成是索引的索引)仅包含它的各个子节点(即下一级的索引块)中关键字的最大值及指向其子节点的指针。

m阶的B+与m阶的B树的主要差异在于:

1)在B+树中,具有n个关键字的结点只含有n棵子树,即每个关键字对应一棵子树;而在B树中,具有n个关键字的结点含有n+1棵子树。

2)在B+树中,每个结点(非根结点)关键字个数n的范围是【m/2】向下取整<=n<=m(根结点:1<=n<=m),在B树中,每个结点(非根结点)关键字个数n的范围是(【m/2】向下取整)-1<=n<=m-1(根结点1<=n<=m-1)。

3)在B树中,叶结点包含信息,所有非叶结点仅起到索引作用,非叶结点中的每个索引项只含有对应子树的最大关键字和指向该子树的指针,不含有该关键字所对应记录的存储地址。

4)在B+树中,叶结点包含全部关键字,即在非叶子结点中出现的关键字也会在叶结点中;而在B树中,叶结点包含的关键字和其他结点包含的关键字是不重复的。

通常在B+树中有两个头指针:一个指向根结点,另一个指向关键字最小的叶结点。因此,可以对B+树进行两种查找运算:一种是从最小关键字开始的顺序查找,另一种是从根结点开始,进行多路查找。

B+树的查找、插入和删除操作和B树基本类似。只是在查找过程中,如果非叶结点上的关键字值等于定值时并不终止,而是记录向下查找直到叶结点上的该关键字为止。所以B+树中,无论查找成功与否,每次查找都是一条从根结点到叶结点的路径。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏算法与数据结构

数据结构 单链表&顺序表

顺序表: 一般使用数组(C语言中的数组采用顺序存储方式。即连续地址存储)来描述。 优点:在于随机访问元素, 缺点:插入和和删除的时候,需要移动大量的元素。 链表...

42110
来自专栏刘君君

JDK8的ArrayList源码学习笔记

2716
来自专栏开发之途

Java集合框架源码解析之ArrayList

1694
来自专栏彭湖湾的编程世界

【算法】二叉查找树(BST)实现字典API

参考资料 《算法(java)》                           — — Robert Sedgewick, Kevin Wayne 《数据结...

4799
来自专栏微信公众号:Java团长

Java集合源码剖析——ArrayList源码剖析

ArrayList是基于数组实现的,是一个动态数组,其容量能自动增长,类似于C语言中的动态申请内存,动态增长内存。

1022
来自专栏java系列博客

Iterator在ArrayList中的源码实现

1642
来自专栏desperate633

LintCode 数组剔除元素后的乘积题目代码

定义B[i] = A[0] * ... * A[i-1] * A[i+1] * ... * A[n-1], 计算B的时候请不要使用除法。

881
来自专栏Java呓语

迭代器模式(控制访问集合中的元素)

现在我们需要思索,JDK是怎么做到这一切的?现在让我们先利用迭代器实现一个数组类型Array,这个类型需要支持添加、移除、遍历操作。

992
来自专栏余林丰

有关ArrayList常用方法的源码解析

jdk1.7.0_79   我相信几乎所有的同学在大大小小的笔试、面试过程中都会被问及ArrayList与LinkedList之间的异同点。稍有准备的人这些问...

2217
来自专栏专注 Java 基础分享

从源码解析TreeMap

     上篇文章我们介绍了HashMap集合,这是一个键值对集合,可以高效的按照键查找数值。但是它有一个缺陷:数据如果是无序的可以是很高效的,但是如果数据...

1998

扫码关注云+社区