B+树
B+树简介
B+ 树是 B 树的一个升级版，相对于 B 树来说 B+ 树更充分的利用了节点的空间，让查询速度更加稳定，其速度完全接近于二分法查找。
B+树的特征
有 k 个子树的中间节点包含有 k 个元素（ B 树中是 k - 1 个元素），每个元素不保存数据，只用来索引，所有数据都保存在叶子节点。
所有的叶子结点中包含了全部元素的信息，及指向含这些元素记录的指针，且叶子结点本身按照关键字的大小自小而大顺序链接。
所有的中间节点元素都同时存在于子节点，在子节点元素中是最大（或最小）元素。
B+树的优势
单一节点存储更多的元素，使得查询的 IO 次数更少。
所有查询都要查找到叶子节点，查询性能稳定。
所有叶子节点形成有序链表，便于范围查询。
为什么说B+ tree比B 树更适合实际应用中操作系统的文件索引和数据库索引？
B+ tree的磁盘读写代价更低
B+ tree的内部结点并没有指向关键字具体信息的指针。因此其内部结点相对B 树更小。如果把所有同一内部结点的关键字存放在同一盘块中，那么盘块所能容纳的关键字数量也越多。一次性读入内存中的需要查找的关键字也就越多。相对来说IO读写次数也就降低了。
举个例子，假设磁盘中的一个盘块容纳16bytes，而一个关键字2bytes，一个关键字具体信息指针2bytes。一棵9阶B-tree(一个结点最多8个关键字)的内部结点需要2个盘快。而B+ 树内部结点只需要1个盘快。当需要把内部结点读入内存中的时候，B 树就比B+ 树多一次盘块查找时间(在磁盘中就是盘片旋转的时间)。
B+ tree的查询效率更加稳定
由于非终结点并不是最终指向文件内容的结点，而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同，导致每一个数据的查询效率相当。