B-tree B树学习介绍，B树建立
2013-07-16 18:03阅读：
平衡二叉排序树便于动态查找，因此用平衡二叉排序树来组织索引表是一种可行的选择。当用于大型数据库时，所有数据及索引都存储在外存，因此，涉及到内、外存之间频繁的数据交换，这种交换速度的快慢成为制约动态查找的瓶颈。若以二叉树的结点作为内、外存之间数据交换单位，则查找给定关键字时对磁盘平均进行㏒㏒次访问是不能容忍的，因此，必须选择一种能尽可能降低磁盘I/OI/O次数的索引组织方式。树结点的大小尽可能地接近页的大小。
B树主要用于文件系统中，在B树中，每个节点的大小为一个磁盘的页，节点中锁包含的关键字及其子节点的数目取决于页的大小。一个度为m的B树，称为m阶B树，定义如下：
（1）一个m阶B树，或者是空树，或者满足一下性质的m叉树；
（2）根节点或者是叶子，或者至少有两颗子树，至多是m棵子树；
（3）除根节点外，所有非终端节点至少是「m/2
（向上取整）棵子树，至多是m棵子树；
（4）所有叶子节点都在树的同一层上。
（5）
下图为B树的一个例子：
1，B树的数据结构，根据以上的信息，定义B树的数据结构如下：
//节点数据结构的定义
typedef struct BTNode
{
int keynum;
//节点信息的数量，不包含key[0]节点
struct BTNode *parent;
//父节点
int key[M+1];
//节点信息数组，第一个节点没用。
struct BTNode *ptr[M+1];//子节点信息
}BTNode;
2，B树的查找
查找的基本思想是：
（1）从树的根节点T开始，在节点中利用遍历或折半查找给定的值，如果找到，则返回节点指针和在节点中的位置；如果没有，则到（2）
（2）与节点中的Key进行比较，找到给定值左右Key中间的指针，去其子树中查找
（3）重复执行1,2两步，直到找到。如果直到叶子节点，仍未找到，则返回0，并返回最后搜索的叶子节点。（此节点是给定值需要插入的位置）
3，B树的插入
插入新节点的基本思想如下：
（1）在B树查找关键字，如果找到，则不插入；否则，执行（2）
（2）将给定值插入到叶子节点中，如果：
a，叶子的节点数
b，叶子的节点数=m-1：插入节点，并将节点分裂。分裂的方式是将该节点拆分成两个节点，然后，将中间节点插入到父节点当中，拆分后的两个节点，分别作为插入到父节点的中间节点的左右子。如果中间节点插入到父节点后，仍然需要分裂，则继续分裂，直到根节点。如果仍然需要分裂，则新建一个根节点，将分裂后的两个节点分别作为新根节点的两个子节点。
例如如下图：
代码如下：
#include
#include
#include
#include
using
namespace std;
//
定义B-tree 的阶数，一般是根据磁盘磁盘页的大小而定
#define M 5
//
节点数据结构的定义
typedef struct BTNode
{
int keynum;
//节点信息的数量，不包含
key[0] 节点
struct BTNode *parent;
// 父节点
int key[M+1];
//节点信息数组，第一个节点没用。
struct BTNode *ptr[M+1];//
子节点信息
}BTNode;
//B-tree 的搜索函数
//
参数T ： B-Tree的根节点，
K ：要查找的信息
//p
：如果找到 K，则
p 为所在的节点，如果没有找，则 p 为最后一次查找的节点
//p
传的是指针的引用
//
返回值为 0，为未找到；为其他值，为在节点中的位置
int
BT_search(BTNode *T,
int K, BTNode *&p)
{
BTNode
*q;
int i;
p=q=T;
while (q!=NULL)
{
p=q;
//
