B树
B 是 Balance（平衡）的缩写。它是一种多路的平衡搜索树。
它跟普通的平衡二叉树的不同是，B树的每个节点可以存储多个数据，而且每个节点不止有两个子节点，最多可以有上千个子节点。
B树中每个节点都存放着索引和数据，数据遍布整个树结构，搜索可能在非叶子节点结束，最好的情况是O(1)。
一般一棵 B 树的高度在 3 层左右，3 层就可满足 百万级别的数据量
B+树
叶子节点保存了完整的索引和数据，而非叶子节点只保存索引值，因此它的查询时间固定为 log(n).
叶子节点中有指向下一个叶子节点的指针，叶子节点类似于一个单链表
正因为叶子节点保存了完整的数据以及有指针作为连接，B+树可以增加了区间访问性，提高了范围查询，而B树的范围查询相对较差
B+树更适合外部存储。因为它的非叶子节点不存储数据，只保存索引。
b+树相比于b树的查询优势：
b+树的中间节点不保存数据，所以磁盘页能容纳更多节点元素，更“矮胖”；
b+树查询必须查找到叶子节点，b树只要匹配到即可不用管元素位置，因此b+树查找更稳定（并不慢）；
对于范围查找来说，b+树只需遍历叶子节点链表即可，b树却需要重复地中序遍历
为什么会出现B-树这类数据结构
传统用来搜索的平衡二叉树有很多，如 AVL 树，红黑树等。这些树在一般情况下查询性能非常好，但当数据非常大的时候它们就无能为力了。原因当数据量非常大时，内存不够用，大部分数据只能存放在磁盘上，只有需要的数据才加载到内存中。一般而言内存访问的时间约为 50 ns，而磁盘在 10 ms 左右。速度相差了近 5 个数量级，磁盘读取时间远远超过了数据在内存中比较的时间。这说明程序大部分时间会阻塞在磁盘 IO 上。那么我们如何提高程序性能？减少磁盘 IO 次数，像 AVL 树，红黑树这类平衡二叉树从设计上无法“迎合”磁盘。
