B树 B+树等各种树的定义。
注：很多文章将B树误称为B-（减）树，这可能是对其英文名“B-Tree”的误解（更有甚者，将B树称为二叉树或二叉搜索树）。特别是与B+树一起讲的时候。想当然的认为有B+（加）树就有B-（减）树，实际上B+树的英文名是“B+-Tree”。
二叉搜索树（Binary Sort Tree）又称二叉查找树，亦称二叉排序树。定义为：一棵树要么是空树，要么是具有下列性质的二叉树：
1）若他的左子树不为空，则左子树上所有结点的值均小于他的根结点的值；
2）若他的右子树不为空，则右子树上所有结点的值均大于他的根结点的值；
3）他的左子树和右子树也分别是二叉排序树
平衡二叉树的定义为：一棵树要么是空树，要么是具有下列性质的二叉树：他的左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值不超过1。
AVL树（Adelson-Velskii和Landis)带有平衡条件的二叉查找树
红黑树，具有以下性质的二叉排序树：
1）所有节点都着色，且要么为红，要么为黑
2）红节点的儿子必须是黑节点
3）空节点认为是黑节点
4）根节点是黑节点
5）根节点到任意叶子节点的黑节点个数相同
B-树：是一种平衡的多路查找树。
一棵m阶B-树或为空树，或为满足下列特性的m叉树：
1）树中每个结点至多有m个子结点
2）若根结点非叶子结点的时候，至少有2个子结点
3）除根之外的所有非终端结点至少有m/2（向上取整）
4）二叉查询树和平衡二叉树特性
5）所有的叶子结点都出现在同一层次上，且不带任何信息（可以看作是外部结点或查找失败的结点，实际上这些结点不存在，指向这些结点的指针为空）
B+树：是应文件系统所需而出的一种B-树的变型树。
一棵m阶B+和m阶的B-树的差异在于：
1）有n棵子树的结点中含有n个关键字。
2）所有叶子结点中包含了全部关键字的信息，及指向含这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接。
3）所有的非终端结点可以看成是索引部分，结点中仅含有其子树（跟结点）中最大（或最小）的关键字。
带有顺序访问指针的B+Tree
一般在数据库系统或文件系统中使用的B+Tree结构都在经典B+Tree的基础上进行了优化，增加了顺序访问指针。
在B+Tree的每个叶子节点增加一个指向相邻叶子节点的指针，就形成了带有顺序访问指针的B+Tree。做这个优化的目的是为了提高区间访问的性能，例如图4中如果要查询key为从18到49的所有数据记录，当找到18后，只需顺着节点和指针顺序遍历就可以一次性访问到所有数据节点，极大提到了区间查询效率。
