B+ 树

B+树是 B-树的变体，也是一种多路搜索树。

B+的搜索与 B-树也基本相同，区别是 B+树只有达到叶子结点才命中（B-树可以在非叶子结点命中），其性能也等价于在关键字全集做一次二分查找；

B+的特性：

1. 所有关键字都出现在叶子结点的链表中（稠密索引），且链表中的关键字恰好是有序的
2. 不可能在非叶子结点命中
3. 非叶子结点相当于是叶子结点的索引（稀疏索引），叶子结点相当于是存储（关键字）数据的数据层 4.更适合文件索引系统

原因： 增删文件（节点）时，效率更高，因为 B+ 树的叶子节点包含所有关键字，并以有序的链表结构存储，这样可很好提高增删效率

使用场景：

文件系统和数据库系统中常用的 B/B+ 树，他通过对每个节点存储个数的扩展，使得对连续的数据能够进行较快的定位和访问，能够有效减少查找时间，提高存储的空间局部性从而减少 I/O 操作。他广泛用于文件系统及数据库中，如： Windows：HPFS 文件系统 Mac：HFS，HFS+ 文件系统 Linux：ResiserFS，XFS，Ext3FS，JFS 文件系统 数据库：ORACLE，MYSQL，SQLSERVER 等中

B 树：有序数组+平衡多叉树 B+树：有序数组链表+平衡多叉树

B+ 树的优点：

1. 层级更低，IO 次数更少
2. 每次都需要查询到叶子节点，查询性能稳定
3. 叶子节点形成有序链表，范围查询方便

B+数插入和平衡

B+ 树还有一个最大的好处，方便扫库，B 树必须用中序遍历的方法按序扫库，而 B+ 树直接从叶子结点挨个扫一遍就完了，B+ 树支持 range-query 非常方便，而 B 树不支持。这是数据库选用 B+树的最主要原因。

比如要查 5-10 之间的，B+ 树一把到 5 这个标记，再一把到 10，然后串起来就行了，B 树就非常麻烦。B 树的好处，就是成功查询特别有利，因为树的高度总体要比 B+ 树矮。不成功的情况下，B 树也比 B+ 树稍稍占一点点便宜。