B-树是一种平衡的多路查找树，B是balance的意思，适用于组织文件的索引。
定义：一棵m（m>2)阶的B-树，或者为空树，或者为满足下列特性的m叉树：
- 如果根结点不是叶结点，则它至少有2棵子树，至多有m棵子树，关键字个数比子树个数少1；
- 除根结点外，每个分支结点至少有$$ \lceil{m/2}\rceil $$棵子树，至多有m棵子树，关键字个数比子树个数少1；
- 每个非叶节点中至少有$$ \lceil{m/2}\rceil-1
$$个关键字，至多有$$ m-1 $$个关键字； - 每个非叶结点包含以下信息：
$$ (n,P_0,K_1,P_1,K_2,P_2,...,K_n,P_n) $$，
其中：
- n为关键字个数，$$ \lceil{m/2}\rceil-1 \le n \le m-1 $$；
- $$ K_i
$$为关键字, 且$$ K_i<K_{i+1} (i=1,2,\ldots,n) $$； - $$ P_i (i=0,1,2,\ldots,n)
$$为指向子树根结点的指针，且指针$$ P_{i-1}$$所指子树中所有结点的关键字均小于$$ K_i (i=1,2,\ldots,n)$$，指针$$ P_i$$所指子树中所有结点的关键字均大于$$ K_i (i=1,2,\ldots, n) $$;
- 所有的叶结点都在最底层，并且不包含任何信息（实际上这些树叶并不存在，指向这些树叶的指针为空）；
- 含有n个关键字的B-树正好有n+1个树叶；
下图为一棵4阶的B-树，其深度为4：
注意：B-树的非叶结点中包含指向数据的指针，如下图所示：
也可是是复合索引，如下图所示：
B-树的特性：
- 关键字集合分布在整颗树中；
- 任何一个关键字出现且只出现在一个结点中；
- 搜索有可能在非叶子结点结束；
- 其搜索性能等价于在关键字全集内做一次二分查找；
B-树的搜索，从根结点开始，对结点内的关键字（有序）序列进行二分查找，如果命中则结束，否则进入查询关键字所属范围的子树；重复，直到所对应的子树指针为空，或已经是叶子结点。