动态查找树主要有二叉查找树（binary search tree），平衡二叉查找树（balanced binary search tree）， 红黑树 (red-black tree )，
都是典型的二叉查找树结构，查找的时间复杂度 o(log2-n) 与树的深度相关，降低树的深度会提高查找效率，于是有了多路的b-tree/b+-tree/ b*-tree (b~tree)。
关于这b树以及b树的两种变体，其实很好区分，
相比b树，b+树不维护关键字具体信息，不考虑value的存储，所有的我们需要的信息都在叶子节点上，
b*树在b+树的基础上增加了非叶子节点兄弟间的指针，在某些场景效率更高，
主要掌握b树的操作，也就掌握了这两种变体树的操作。
注意b树也就是b-树，b树的英文是b-tree，很多地方直译成了b-树，其实b-树和b树是同一种树。
b树是为了磁盘或其它存储设备而设计的一种多叉平衡查找树。
（1）b-tree的接点结构
b-tree中，每个结点包含：
本结点所含关键字的个数；
指向父结点的指针；
关键字；
指向子结点的指针数组；
1
2
3
4
5
6
7
8
9
10
<code>#define max l000 //结点中关键字的最大数目：max=m-1，m是b-树的阶</code>
<code>#define min 500 //非根结点中关键字的最小数目：min=m/2-1</code>
<code>typedef</code> <code>int</code> <code>keytype； </code><code>//keytype关键字类型由用户定义</code>
<code>typedef</code> <code>struct</code> <code>node{ </code><code>//结点定义中省略了指向关键字代表的记录的指针</code>
<code> </code><code> </code><code>int</code> <code>keynum； </code><code>//结点中当前拥有的关键字的个数，keynum<<max</code>
<code> </code><code> keytype key[max+1]； </code><code>//关键字向量为key[1..keynum]，key[0]不用。</code>
<code> </code><code> </code><code>struct</code> <code>node *parent； </code><code>//指向双亲结点</code>
<code> </code><code> </code><code>struct</code> <code>node *son[max+1]；</code><code>//指向孩子结点的指针数组，孩子指针向量为son[0..keynum]</code>
<code> </code><code>}btreenode；</code>
<code>typedef</code> <code>btreenode *btree；</code>
（2）b-tree的特点
b-tree是一种多路搜索树（并不是二叉的），对于一棵m阶树：
定义任意非叶子结点最多只有m个孩子；且m>2；
根结点的孩子数为[2, m]，除非根结点为叶子节点；
除根结点以外的非叶子结点的儿子数为[m/2, m]；
非叶子结点的关键字个数=指向儿子的指针个数-1；
每个非叶子结点存放至少m/2-1（取上整）和至多m-1个关键字；
非叶子结点的关键字：k[1], k[2], …, k[m-1]；且k[i] < k[i+1]；
非叶子结点的指针：p[1], p[2], …, p[m]；其中p[1]指向关键字小于k[1]的子树，p[m]指向关键字大于k[m-1]的子树，其它p[i]指向关键字属于(k[i-1], k[i])的子树；
所有叶子结点位于同一层；
以m=3的一棵3阶b树为例：
一棵包含了24个英文字母的5阶b树的结构：
（3）b-tree高度与复杂度
b树的高度是
，而不是其它几种树的h=log2n，其中t为度数（每个节点包含的元素个数），即所谓的阶数，n为总元素个数或总关键字数。
b树查找的时间复杂度为o(log2-n)，下面是参考推导过程：
其中m为设定的非叶子结点最多子树个数，n为关键字总数；所以b-树的性能总是等价于二分查找（与m值无关），也就没有avl树平衡的问题。
（1）查找操作
在b-树中查找给定关键字的方法类似于二叉排序树上的查找。不同的是在每个结点上确定向下查找的路径不一定是二路而是keynum+1路的。
对结点内的存放有序关键字序列的向量key[l..keynum] 用顺序查找或折半查找方法查找。若在某结点内找到待查的关键字k，则返回该结点的地址及k在key[1..keynum]中的位置；否则，确定k在某个key[i]和key[i+1]之间结点后，从磁盘中读son[i]所指的结点继续查找。直到在某结点中查找成功；或直至找到叶结点且叶结点中的查找仍不成功时，查找过程失败。
11
12
13
14
15
16
17
<code>btreenode *searchbtree(btree t，keytype k，</code><code>int</code> <code>*pos)</code>
<code> </code><code>{ </code><code>//在b-树t中查找关键字k，成功时返回找到的结点的地址及k在其中的位置*pos</code>
<code>//失败则返回null，且*pos无定义</code>
<code> </code><code>int</code> <code>i；</code>
<code> </code><code>t→key[0]=k; </code><code>//设哨兵．下面用顺序查找key[1..keynum]</code>
<code> </code><code>for</code><code>(i=t->keynum；k<t->key[i];i--)； </code><code>//从后向前找第1个小于等于k的关键字</code>
<code> </code><code>if</code><code>(i>0 && t->key[i]==1){ </code><code>//查找成功，返回t及i</code>
<code> </code><code>*pos=i；</code>
<code> </code><code>return</code> <code>t；</code>
<code> </code><code>} </code><code>//结点内查找失败，但t->key[i]<k<t->key[i+1]，下一个查找的结点应为</code>
<code> </code><code>//son[i]</code>
<code> </code><code>if</code><code>(!t->son[i]) </code><code>//*t为叶子，在叶子中仍未找到k，则整个查找过程失败</code>
<code> </code><code>return</code> <code>null；</code>
<code> </code><code>//查找插入关键字的位置，则应令*pos=i，并返回t，见后面的插入操作</code>
<code> </code><code>diskread(t->son[i])； </code><code>//在磁盘上读人下一查找的树结点到内存中</code>
<code> </code><code>return</code> <code>searchbtree(t->son[i]，k，pos)； </code><code>//递归地继续查找于树t->son[i]</code>
<code> </code><code>}</code>
（2）查找操作的时间开销
b-树上的查找有两个基本步骤：
1.在b-树中查找结点，该查找涉及读盘diskread操作，属外查找；
2.在结点内查找，该查找属内查找。
查找操作的时间为：
1.外查找的读盘次数不超过树高h，故其时间是o(h)；
2.内查找中，每个结点内的关键字数目keynum<m(m是b-树的阶数)，故其时间为o(nh)。
注意：
1.实际上外查找时间可能远远大于内查找时间。
2.b-树作为数据库文件时，打开文件之后就必须将根结点读人内存，而直至文件关闭之前，此根一直驻留在内存中，故查找时可以不计读入根结点的时间。
（3）插入操作
插入一个元素时，首先在b树中是否存在，如果不存在，即在叶子结点处结束，然后在叶子结点中插入该新的元素，注意：如果叶子结点空间足够，这里需要向右移动该叶子结点中大于新插入关键字的元素，如果空间满了以致没有足够的空间去添加新的元素，则将该结点进行“分裂”，将一半数量的关键字元素分裂到新的其相邻右结点中，中间关键字元素上移到父结点中（当然，如果父结点空间满了，也同样需要“分裂”操作），而且当结点中关键元素向右移动了，相关的指针也需要向右移。如果在根结点插入新元素，空间满了，则进行分裂操作，这样原来的根结点中的中间关键字元素向上移动到新的根结点中，因此导致树的高度增加一层。
（4）删除操作
首先查找b树中需删除的元素,如果该元素在b树中存在，则将该元素在其结点中进行删除，如果删除该元素后，首先判断该元素是否有左右孩子结点，如果有，则上移孩子结点中的某相近元素到父节点中，然后是移动之后的情况；如果没有，直接删除后，移动之后的情况。
b+-tree是应文件系统所需而产生的一种b-tree的变形树。
（1）b树和b+树的对比
一棵m阶的b+树和m阶的b树的异同点在于：
1.有n棵子树的结点中含有n-1 个关键字；
2.所有的叶子结点中包含了全部关键字的信息，及指向含有这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大的顺序链接。 (而b 树的叶子节点并没有包括全部需要查找的信息)
3.所有的非终端结点可以看成是索引部分，结点中仅含有其子树根结点中最大（或最小）关键字。 (而b 树的非终节点也包含需要查找的有效信息)
（2）为什么说b+-tree比b 树更适合实际应用中操作系统的文件索引和数据库索引？
b+-tree的磁盘读写代价更低
b+-tree的内部结点并没有指向关键字具体信息的指针。因此其内部结点相对b 树更小。
如果把所有同一内部结点的关键字存放在同一盘块中，那么盘块所能容纳的关键字数量也越多。
一次性读入内存中的需要查找的关键字也就越多。相对来说io读写次数也就降低了。
举个例子，假设磁盘中的一个盘块容纳16bytes，而一个关键字2bytes，一个关键字具体信息指针2bytes。
一棵9阶b-tree(一个结点最多8个关键字)的内部结点需要2个盘快。而b+ 树内部结点只需要1个盘快。当需要把内部结点读入内存中的时候，b 树就比b+ 树多一次盘块查找时间(在磁盘中就是盘片旋转的时间)。
b+-tree的查询效率更加稳定
由于非终结点并不是最终指向文件内容的结点，而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同，导致每一个数据的查询效率相当。
b*-tree是b+-tree的变体，在b+树的基础上(所有的叶子结点中包含了全部关键字的信息，及指向含有这些关键字记录的指针)，
b*树中非根和非叶子结点再增加指向兄弟的指针；
b*树定义了非叶子结点关键字个数至少为(2/3)*m，即块的最低使用率为2/3（代替b+树的1/2）。
下图是一棵典型的b*树：