B Tree 和 B+Tree

数据结构学习地址：
https://www.cs.usfca.edu/~galles/visualization/Algorithms.html

什么是B树？

B树，全名是平衡多路查找树，是对二叉查找树的改进，它的设计思想是，将相关数据尽量集中在一起，以便一次读取多个数据，减少硬盘操作次数，B树大量应用在数据库和文件系统当中。

为什么出现B树？而不是红黑树？

1、红黑树是二叉树，二B树是多叉的
2、根据计算机的局部性原理，B树将很多相近甚至连续的值存放在一个节点上，这样在获取数据时，B树可以一次获取更多的相关信息，二红黑树一次只能获取一个数据信息。
3、B树由于是多路的，相同数据量，就证实其高度要显著低于红黑树，在效率上也显著高于红黑树。

B Tree的结构

对于一棵m阶B tree：
1、每个结点至多可以拥有m个子结点。
2、根结点至少有2个子结点，除非根结点为叶子节点，根结点中关键字的个数为1~m-1。
3、非根结点至少有[m/2]（[]，向上取整）个子结点，相应的，关键字个数为[m/2]-1~m-1

B树节点信息

1、本结点所含关键字的个数；
2、指向父结点的指针；
3、关键字；
4、指向子结点的指针；

什么是B+树？

B+树是B树的一个更新版，相对于B树来说B+树更充分的利用了节点的空间，让查询速度更加稳固，其速度完全接近于二分法查找。

B+树与B树的不同

1、在B+树种，非叶子节点值存数据的key和子节点指针信息，不存储数据的具体值data的指针，这使得B+树可以存储更多的key。B+树的所有数据data存储在叶子节点上。
2、在叶子节点上，每个叶子结点添加顺序指针，形成链表结构，便于区间查找和遍历，非叶子结点作为索引。（非叶子节点也有横向指针的叫做B*树）