消除盲区，本文记录的是我对 B树和B+树（B Tree/B+ Tree） 的探索与理解。
B树/B+树在现实中具有非常多的应用，例如在文件系统IO、数据库索引。B树是为数据存储而设计的一种平衡的多路搜索树。而 B+树是B树的一种变形，它把所有的卫星数据都存储在叶节点中，内部节点只存放关键字和孩子指针，因此最大化了内部节点的分支因子，所以B+树的遍历也更加高效(B树需要以中序的方式遍历节点，而B+树只需把所有叶子节点串成链表就可以从头到尾遍历)。
前言
维基百科对B树的定义为“在计算机科学中，B树（B-tree）是一种树状数据结构，它能够存储数据、对其进行排序并允许以O(log n)的时间复杂度运行进行查找、顺序读取、插入和删除的数据结构。B树，概括来说是一个节点可以拥有多于2个子节点的二叉查找树。与自平衡二叉查找树不同，B树为系统最优化大块数据的读和写操作。B-tree算法减少定位记录时所经历的中间过程，从而加快存取速度。普遍运用在数据库和文件系统。
B树定义：
B树可以看作是对2-3查找树的一种扩展，即他允许每个节点有M-1个子节点。
-
根节点至少有两个子节点
-
每个节点有M-1个key，并且以升序排列
-
位于M-1和M key的子节点的值位于M-1 和M key对应的Value之间
-
其它节点至少有M/2个子节点
下图是一个M=4 阶的B树:
可以看到B树跟2-3树非常类似，可以看成是2-3树的一种扩展吧，他允许一个节点有多于2个的元素。B树的插入及平衡化操作也和2-3树很相似，这里就不介绍了。
B+树定义：
B+树是对B树的一种变形树，它与B树的差异在于：
-
有k个子结点的结点必然有k个关键码；
-
非叶结点仅具有索引作用，跟记录有关的信息均存放在叶结点中。
-
树的所有叶结点构成一个有序链表，可以按照关键码排序的次序遍历全部记录。
如下图，是一个B+树:
总结分析：
B和B+树的区别在于，B+树的非叶子结点只包含导航信息，不包含实际的值（卫星数据），所有的叶子结点和相连的节点使用链表相连，便于区间查找和遍历。
B+树优势：
-
由于B+树在内部节点上都没有存卫星数据，因此在一个磁盘页可以存更多的节点。 数据存放的更加紧密，具有更好的空间局部性。因此访问叶子几点上关联的数据也具有更好的缓存命中率。
-
B+树的叶子结点都是相链的，因此对整棵树的便利只需要一次线性遍历叶子结点即可。而且由于数据顺序排列并且相连，所以便于区间查找和搜索，即查到头元素之后，直接链表向后找，就能准确定位。而B树则需要进行每一层的递归遍历。相邻的元素可能在内存中不相邻，所以缓存命中性没有B+树好。
B树/B+树通过动态改变每个节点的关键码跟儿子节点个数以保持最大的平衡，即以最少的层数保存数据，令关键码的查找逼近二分查找（O（log2n）时间复杂度）
也正正因为B+树的这种特性，因此这种数据结构常用于文件系统跟数据库索引中。它通过对每个节点存储个数的扩展，使得对连续的数据能够进行较快的定位和访问，能够有效减少查找时间，提高存储的空间局部性从而减少IO操作。
