B树的定义

一棵m阶的B树满足下列条件：

树中每个结点至多有m个孩子。

除根结点和叶子结点外，其它每个结点至少有m/2个孩子。

根结点至少有2个孩子（如果B树只有一个结点除外）。

所有叶结点在同一层，B树的叶结点可以看成一种外部节点，不包含任何信息。

有k个关键字(关键字按递增次序排列)的非叶结点恰好有k+1个孩子。

看到上面的定义是不是感到十分熟悉，哈哈，是不是和B^- 树的定义是一样的？这个是必须的，因为所谓的B树就是我们熟知的B^- 树。对于这个有些资料已经作了详细说明，B树的英文名称叫做B-tree，咱们Chinese Man就翻译为B^- 树了。所以一提到B树，估计有好多人不知道，甚至以为它是一棵新的搜索树。

再次重申下B-tree树就是指的B树或者叫做B^- 树。

B树的存储结构

struct B_TNode{
    int numOfKey;//关键字个数
    B_TNode *parent;//指向父结点的指针
    B_TNode **childPtr;//指向子树的指针，childPtr[0]...childPtr[numOfKey]
    int *key;//指向关键字数组的指针
};

B树的查找

参照一个例子-文件的查找过程，文件的存储如下B树所示：

查找29号文件的过程如下：

1. 根据根结点指针找到文件目录的根磁盘块1，将其中的信息导入到内存。---进行了一次磁盘IO操作。
2. 此时内存中有两个文件名17、35和三个存储其他磁盘页面地址的数据。根据算法我们发现17<29<35，因此我们找到指针p2。
3. 根据p2指针，我们定位到磁盘块3，并将其中的信息导入内存。---进行了两次磁盘IO操作。  
4. 此时内存中有两个文件名26，30和三个存储其他磁盘页面地址的数据。根据算法我们发,26<29<30，因此我们找到指针p2。
5. 根据p2指针，我们定位到磁盘块8，并将其中的信息导入内存。---进行了三次磁盘IO操作。  
6. 此时内存中有两个文件名28，29。根据算法我们查找到文,29，并定位了该文件内存的磁盘地址。

关于B树的一些总结

原文：http://www.cnblogs.com/tgycoder/p/5077017.html