文件系统的灵魂数据结构 B树 什么是B-树、B树、B+树、B*树？
正如标题所言，本文介绍经常使我们混淆的B-树、B树、B+树和B*树。
首先，B-tree树即B树。B即Balanced平衡，因为B树的原英文名称为B-tree，而国内很多人喜欢把B-tree译作B-树，这是个非常不好的直译，很容易让人产生误解，人们可能会以为B-树和B树是两种树。
1、B树
1.1、B树产生的背景
不管是二叉树、二叉查找树还是平衡二叉树，它们都有诸多限制，比如：
每个结点只能存储一个元素。
结点的度至多为2，即使是平衡二叉树，在存储百万、千万级别的数据量时，也会导致树的深度特别大，而深度大就会影响查找效率。
这里提一下平衡二叉树的缺点：
由于平衡二叉树需要左旋和右旋来调整树的结构，因此在频繁插入和删除的场景下，每插入或删除一个结点，都极有可能导致树的不平衡，性能也会大打折扣。红黑树（后面会介绍）就是来解决这个问题的。
前面讲的几种数据结构，都是纯内存操作，但是当数据量特别大（如数据库中千万级别的数据表、磁盘中的上万个文件等），内存都存不下了怎么办？在这种情况下，需要用外存（硬盘）来存储，而对数据的处理则需要不断地从硬盘调入调出。
此时，时间复杂度的计算就会发生变化，因为还要额外考虑对硬盘的访问次数和单次访问时间等。
为了降低对硬盘的访问次数，需要设计新的数据结构。前面讲的几种树，结点都只能存一个元素，因此，当元素非常多的时候，要么结点的度非常大，要么树的深度非常大，这两种情况都会导致对硬盘的访问次数偏大。如果每个结点能存多个元素，那么树的总结点数就会大大减少，对磁盘的访问次数也会相应的大大减少。
由于有如上限制，为此引入了多路查找树的概念。
多路查找树：结点的度可以大于2，并且每一个结点可以存储多个元素。由于是查找树，所以结点之间存在某种特定的排序关系。
1.2、B树的基本概念
B树是一种平衡的多路查找树。
其实B树和多路查找树是一个意思，网上很多资料也是这样认为的，但是也可以认为多路查找树和B树不是一个意思，因为多路查找树不一定是平衡的。
B树的阶：所有结点中的最大孩子数。其实跟树的度一个意思。
一个m阶B树的属性：
如果根结点不是叶子结点，则其至少有两颗子树。
[m/2]<=k<=m，[m/2]为向上取整，比如9阶B树，5<=k<=9。每一个非根分支结点都有k个孩子和k-1个元素；叶子结点有k-1个元素。
所有叶子结点在同一层（平衡）。
所有分支结点有下列信息数据：(n,A0,K1,A1,K2,A2,...,Kn,An)，n是结点存储的元素个数，Ai表示子树，Ki表示元素，而从A0到An的值是从小到大排序的，这跟二叉查找树的性质一样。
下面来演示一下如何在B树上查找元素，如下图，是一颗B树。
如果要查找元素7，首先从硬盘上读取根节点（第一次读磁盘）
即读到了3,5,8三个元素，发现7并不在其中，但由于5<7<8，因此找到了A2，然后根据A2再读取一次硬盘（第二次读磁盘）
此时读到了2,6,7三个元素，找到了元素7
两次磁盘读取就查找了我们想要的元素，非常高效，B树就是这样一种为内外存数据交互为设计的数据结构。
2、B+树
尽管B树有很多好处，但是它还是有缺点的：
当进行范围查找时，存在回旋查找的问题
排序的时候，需要进行一次中序遍历（order by）
其实这也是数据库索引不使用B树，而使用B+树的原因。
因为B树是存储在磁盘中的，如下图的B树，假设每个结点都存储在磁盘的不同页中（一般在设计的时候，会将B树的阶与磁盘页的大小相匹配，目的是为了减少跨页访问）。
那么进行一次中序遍历的访问流程是：
页面2->页面1->页面3->页面1->页面4->页面1->页面5
页面1被访问了多次，这就是回旋访问问题。如果一个文件系统使用B树来做存储结构的话，那性能肯定还是不高的。B+树正是应文件系统所需而出的一种B树的升级版。
一颗B+树的样子如下图所示。
图1
一颗m阶的B+树与m阶的B树差异如下：
非叶子结点的元素个数=孩子个数
B+树只有达到叶子结点才命中（B-树可以在非叶子结点命中）
所有的非叶子结点相当于叶子结点的索引，而所有的叶子结点才是存储关键字的数据层
所有叶子结点根据关键字从小到大排序，且通过指针顺序连接
所有非叶子结点中的元素，都同时存在于子节点中(因此元素个数与孩子数要相同，相同与将k个元素分配给k个孩子)，在子节点中是最小（或最大）元素。
对于差异5，,什么时候表现为最小元素，什么时候表现为最大元素呢？
如图1所示，根结点中元素与孩子指针按从小到大排序应该是
5<P1<28<P2<65<P3
然后分别将5分配给P1、28分配给P2、65分配给P3，自然而然就表现为了最小元素，二层的分支结点以此类推。
若要表现为最大元素，则需要将指针放在最前面，即类似于这样的排序
P1<5<P2<28<P3<65
如果要在B+树上查询关键字，即使在分支结点上找到了该关键字，它也只是用来做索引的，最终还是要定位到包含该关键字的叶子结点中。
大家有没有注意到图1还有一个data指针，它指向了最小叶子结点。如果我们要遍历整颗B+树的话，直接从data指针开始搜索即可，而不需要从根结点开始查找。
3、B*树
B*树是B+树的变体，在B+树的非根分支结点再增加指向兄弟的指针，将结点的最低利用率从1/2提高到2/3。
一颗B*树如下图所示。
本文就介绍到这里，感谢大家阅读！