B树和B+树在数据结构上的区别

B-tree最早是由德国计算机科学家鲁道夫·拜尔等人在1972的论文《大型有序索引的组织与维护》中提出的，但是我看了一下原文，发现作者并没有解释为什么叫B-trees，所以我把B-tree的B，简单的解释为平衡或者二进制并不是特别严谨。可能作者是以拜耳的首字母命名的...

二、B树长什么样？

直接看图更清晰。如图所示，B树实际上是一棵平衡的多分支搜索树，也就是说，在M >时，可以打开M个分支(M >；=2)，我们称之为M阶B树。为了体现这个博客的良心，不像其他地方可以看到2阶B树，这里我们特意画了一棵5阶B树。

一般来说，M阶B树满足以下条件:

每个节点最多可以有m个子树。

根节点至少有两个节点(或者极端情况下一棵树有一个根节点，单细胞生物是根、叶、树)。

非根非叶节点至少有Ceil(m/2)个子树(Ceil代表上舍入，图中每个节点至少有3个子树，即至少有3个叉)。

非叶节点中的信息包括[n，A0，K1，A1，K2，A2，…，KN，An]，其中N表示节点中保存的关键字数，K为关键字，Ki

每一条从根到叶的路径长度都是一样的，也就是说叶节点在同一层，这些节点没有信息。实际上，这些节点意味着无法找到指定的值，即指向这些节点的指针为空。

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+树中，无论搜索成功与否，每次搜索都是走一条从根到叶节点的路径。