前言
动态查找树主要有：二叉查找树（Binary Search Tree），平衡二叉查找树（Balanced Binary Search Tree），红黑树(Red-Black Tree )，B-tree/B+-tree/ B*-tree
(B~Tree)。前三者是典型的二叉查找树结构，其查找的时间复杂度O(log2N)与树的深度相关，那么降低树的深度自然会提高查找效率。
1.B树
具体讲解之前，有一点，再次强调下：有的文章里面出现的B-树，即为B树。因为B树的原英文名称为B-tree，而国内很多人喜欢把 B-tree 译作B-树，其实，这是个非常不好的直译，很容易让人产生误解。如人们可能会以为 B-树是一种树，而B树又是一种一种树。而事实上是，B-tree就是指的B树。特此说明。
定义
一颗m阶的B树定义如下：
1）每个结点最多有m-1个关键字。
2）根结点最少可以只有1个关键字。
3）非根结点至少有Math.ceil(m/2)-1个关键字。
4）每个结点中的关键字都按照从小到大的顺序排列，每个关键字的左子树中的所有关键字都小于它，而右子树中的所有关键字都大于它。
5）所有叶子结点都位于同一层，或者说根结点到每个叶子结点的长度都相同。
2.B+树
特点:
- 有k个子树的中间节点包含有k个元素（B树中是k-1个元素），每个元素不保存数据，只用来索引，所有数据都保存在叶子节点。
- 所有的叶子结点中包含了全部元素的信息，及指向含这些元素记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接。
- 所有的中间节点元素都同时存在于子节点，在子节点元素中是最大（或最小）元素。
B-和B+树对比
B+树的中间节点没有卫星数据，所以同样大小的磁盘可以容纳更多的节点元素；
在数据量相同的情况下，B+树的结构比B-树更加“矮胖”，因此查询的IO次数也更少；B+树的查询必须最终查找到叶子节点，而B-树只要查找匹配的元素即可，无论匹配的元素处于中间节点还是叶子节点。
- B-树的查找性能并不稳定（最好情况只查询根节点，最坏情况是查找叶子节点）。而B+树的每一次查找都是稳定的。
B+树比B-树的优势三个：
1. 单一节点存储更多的元素，使得查询的IO次数更少。
2. 所有查询都要查找到叶子节点，查询性能稳定。
3. 所有叶子节点形成有序链表，便于范围查询。
3.B*树
定义
是B+树的变体，在B+树的非根和非叶子结点再增加指向兄弟的指针；B树定义了非叶子结点关键字个数至少为(2/3)M，即块的最低使用率为2/3（代替B+树的1/2）。
特点
B的查询、插入和删除操作和B+树差不多，只不过会遵循非叶子结点元素个数至少为(2/3)M的特点。比如，对于3阶B*树，当元素个数大于1的时候，每个非叶子节点的元素个数，至少为两个
