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

相关文章

来自专栏Bingo的深度学习杂货店

Q108 Convert Sorted Array to Binary Search Tree

Given an array where elements are sorted in ascending order, convert it to a hei...

3253
来自专栏LanceToBigData

Java集合源码分析(一)ArrayList

前言   在前面的学习集合中只是介绍了集合的相关用法,我们想要更深入的去了解集合那就要通过我们去分析它的源码来了解它。希望对集合有一个更进一步的理解!   既然...

2726
来自专栏书山有路勤为径

排序数组转换为二叉查找树

已知一个排序的数组,将该数组转换为一个高度平衡的二叉查找树。 平衡的定义: 二叉查找树中,任意节点的两颗子树高度差不超过1. LeetCode 108

903
来自专栏架构之路

Java 集合系列03之 ArrayList详细介绍(源码解析)和使用示例

概要 上一章,我们学习了Collection的架构。这一章开始,我们对Collection的具体实现类进行讲解;首先,讲解List,而List中ArrayLis...

2934
来自专栏余林丰

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

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

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

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

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

5209
来自专栏一枝花算不算浪漫

Java中常见数据结构List之ArrayList

38512
来自专栏Java呓语

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

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

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

从源码解析TreeMap

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

2108
来自专栏开发之途

Java集合框架源码解析之ArrayList

1874

扫码关注云+社区

领取腾讯云代金券