B树和B加树的区别，再理解Oracle的B-Tree Index

一、B树的起源

B树，最早是由德国计算机科学家Rudolf Bayer等人于1972年在论文 《Organization and Maintenance of Large Ordered Indexes》提出的，不过我去看了看原文，发现作者也没有解释为什么就叫B-trees了，所以把B树的B，简单地解释为Balanced或者Binary都不是特别严谨，也许作者就是取其名字Bayer的首字母命名的也说不定啊……

二、B树长啥样

还是直接看图比较清楚，图中所示，B树事实上是一种平衡的多叉查找树，也就是说最多可以开m个叉（m>=2），我们称之为m阶b树，为了体现本博客的良心之处，不同于其他地方都能看到2阶B树，这里特意画了一棵5阶B树 。

总的来说，m阶B树满足以下条件：

每个节点至多可以拥有m棵子树

根节点，只有至少有2个节点（要么极端情况，就是一棵树就一个根节点，单细胞生物，即是根，也是叶，也是树)

非根非叶的节点至少有的Ceil(m/2)个子树(Ceil表示向上取整，图中5阶B树，每个节点至少有3个子树，也就是至少有3个叉)

非叶节点中的信息包括[n,A0,K1,A1,K2,A2,…,Kn,An]，，其中n表示该节点中保存的关键字个数，K为关键字且Ki<Ki+1，A为指向子树根节点的指针

从根到叶子的每一条路径都有相同的长度，也就是说，叶子节在相同的层，并且这些节点不带信息，实际上这些节点就表示找不到指定的值，也就是指向这些节点的指针为空

B树的查询过程和二叉排序树比较类似，从根节点依次比较每个结点，因为每个节点中的关键字和左右子树都是有序的，所以只要比较节点中的关键字，或者沿着指针就能很快地找到指定的关键字，如果查找失败，则会返回叶子节点，即空指针

例如查询图中字母表中的K

从根节点P开始，K的位置在P之前，进入左侧指针

左子树中，依次比较C、F、J、M，发现K在J和M之间

沿着J和M之间的指针，继续访问子树，并依次进行比较，发现第一个关键字K即为指定查找的值

三、Plus版——B+树

作为B树的加强版，B+树与B树的差异在于：

有n棵子树的节点含有n个关键字（也有认为是n-1个关键字）

所有的叶子节点包含了全部的关键字，及指向含这些关键字记录的指针，且叶子节点本身根据关键字自小而大顺序连接

非叶子节点可以看成索引部分，节点中仅含有其子树（根节点）中的最大（或最小）关键字

请点击输入图片描述

B+树的查找过程，与B树类似，只不过查找时，如果在非叶子节点上的关键字等于给定值，并不终止，而是继续沿着指针直到叶子节点位置。因此在B+树，不管查找成功与否，每次查找都是走了一条从根到叶子节点的路径

首先，b树和b-树是一种东西，不存在什么“b减树”。

“B-tree，B即Balanced，平衡的意思。因为B树的原英文名称为B-tree，而国内很多人喜欢把B-tree译作B-树，其实，这是个非常不好的直译，很容易让人产生误解，可能会以为B-树是一种树，而B树又是另一种树。而事实上是， B-tree就是指的B树 。特此说明。”

概述 ：

b-树是一种多叉平衡查找树，一个结点可以存放多个关键字（从小到大排序），每个关键字有左右两个指针分别指向子节点，左子树中的所有关键字小于它，右子树中的所有关键字大于它。

对于一个m阶b树需要满足以下条件 ：

下图中的左右白色长方形，就分别代表左右指针，叶子节点的指针为空

b树的构建，其实是一个不断插入结点并根据以上条件调整结构的过程。具体过程此处不再赘述，可以简略看一下这一篇文章， The Difference Between B-trees and B+trees 。

b树的查找。简要来说，搜索当前结点的所有Key，找到第一个 大于等于 target的key，如果key==target就可以返回value，否则说明要去查找子节点。如果当前结点是叶子结点，没有子节点，则查找失败，返回null。否则递归查找第i个子节点。

注意，下面的图中，再单个结点的搜索用的是线性查找，可以使用二分查找进一步提高效率。

时间复杂度

B树查找的时间复杂度为O(Log2-N)，N为关键字总数。具体可以参考 Best case and worst case heights 与 二叉树学习笔记之B树、B+树、B*树 。

思路是：

B-树上的查找有两个基本步骤：

1.在B-树中查找结点，该查找涉及读盘DiskRead *** 作，属外查找；

2.在结点内查找，该查找属内查找。

查找 *** 作的时间为：

1.外查找的读盘次数不超过树高h，故其时间是O(h)；

2.内查找中，每个结点内的关键字数目keynum<= m - 1(m是B-树的阶数)，如果算二分查找，时间是O(log2 m)

b+树是b树最著名的版本。具有两个b树不具备的特征：

b+树的插入、查找、删除等 *** 作，具体可以看 B+-trees 。这里简要提一下它的查找 *** 作，由于b+树的具体数据都储存在叶子结点，它的查找过程必须从根节点一直查到叶子。具体算法过程为：

https://www.baeldung.com/cs/b-trees-vs-btrees

https://www.cnblogs.com/myseries/p/12532919.html

https://blog.csdn.net/weixin_42462202/article/details/104335419

定义： B树，又称多路平衡查找树，B树中所有结点的孩子个数的最大值称为B树的阶，通常用m表示。一颗m阶B树或为空树，或为满足如下特性的m叉树。

m阶B树的核心特性：

B树的高度:

问题:含n个关键字的m阶B树，最小高度，最大高度是多少?

5阶B树——结点关键字个数 ┌ (m/2) ┐ - 1 ≤ n ≤ m-1，即：2 ≤ n ≤ 4（此处省略失败结点）

核心要求：

一颗m阶的B+树需满足下列条件：

1.m阶B+树

2.m阶B树

---