所有节点组成树结构。

　　每个指针要么为null，要么指向另外一个节点。

　　如果某个指针在节点node最左边且不为null，则其指向节点的所有key小于v（key1），其中v（key1）为node的第一个key的值。

　　如果某个指针在节点node最右边且不为null，则其指向节点的所有key大于v（keym），其中v（keym）为node的最后一个key的值。

　　如果某个指针在节点node的左右相邻key分别是keyi和keyi+1且不为null，则其指向节点的所有key小于v（keyi+1）且大于v（keyi）。

　　图2是一个d=2的B-Tree示意图。

图2

　　由于B-Tree的特性，在B-Tree中按key检索数据的算法非常直观：首先从根节点进行二分查找，如果找到则返回对应节点的data，否则对相应区间的指针指向的节点递归进行查找，直到找到节点或找到null指针，前者查找成功，后者查找失败。B-Tree上查找算法的伪代码如下：

　　关于B-Tree有一系列有趣的性质，例如一个度为d的B-Tree，设其索引N个key，则其树高h的上限为logd((N+1)/2)，检索一个key，其查找节点个数的渐进复杂度为O(logdN)。从这点可以看出，B-Tree是一个非常有效率的索引数据结构。

　　另外，由于插入删除新的数据记录会破坏B-Tree的性质，因此在插入删除时，需要对树进行一个分裂、合并、转移等操作以保持B-Tree性质，本文不打算完整讨论B-Tree这些内容，因为已经有许多资料详细说明了B-Tree的数学性质及插入删除算法，有兴趣的朋友可以在本文末的参考文献一栏找到相应的资料进行阅读。

　　B+Tree

　　B-Tree有许多变种，其中最常见的是B+Tree，例如MySQL就普遍使用B+Tree实现其索引结构。

　　与B-Tree相比，B+Tree有以下不同点：

　　每个节点的指针上限为2d而不是2d+1。

　　内节点不存储data，只存储key；叶子节点不存储指针。

　　图3是一个简单的B+Tree示意。

图3