导读:1建站知识本篇文章介绍了，基于B-树和B+树的使用：数据搜索和数据库索引的详细分析。需要的朋友参考下网站建设哪家好网站建设多少钱。

B-树

1 .B-树定义

B-树是一种平衡的多路查找树，它在文件系统中很有用。

定义：一棵m 阶的B营销型网站建设-树，或者为空树，或为满足下列特性的m 叉树： ⑴树中每个结点至多有m 棵子树； ⑵若根结点不是叶子结点，则至少有两棵子树；

⑶除根结点之外的所有非终端结点至少有[m/2] 棵子树； ⑷所有的非终端结点中包含以下信息数据：

（n，A0，K1，A1，K2，…，Kn，An） 其中：Ki（i=1,2,…,n）为关键码，且Ki

Ai 为指向子树根结点的指针(i=0,1,…,n)，且指针Ai-1 所指子树中所有结点的关键码均小于Ki (i=1,2,…,n)，An 所指子树中所有结点的关键码均大于Kn.

n 为关键码的个数。 ⑸所有的叶子结点都出现在同一层次上，并且不带信息（可以看作是外部结点或查找失败的结点，实际上这些结点不存在，指向这些结点的指针为空）。

即所有叶节点具有相同的深度，等于树高度。

如一棵四阶B-树，其深度为4.

B-树的查找类似二叉排序树的查找，所不同的是B-树每个结点上是多关键码的有序表，在到达某个结点时，先在有序表中查找，若找到，则查找成功；否则，到按照对应的指针信息指向的子树中去查找，当到达叶子结点时，则说明树中没有对应的关键码。

在上图的B-树上查找关键字47的过程如下：

1）首先从更开始，根据根节点指针找到 *节点，因为 *a 节点中只有一个关键字，且给定值47 > 关键字35，则若存在必在指针A1所指的子树内。

2）顺指针找到 *c节点，该节点有两个关键字（43和 78），而43 < 47 < 78,若存在比在指针A1所指的子树中。

3）同样，顺指针找到 *g节点，在该节点找到关键字47,查找成功。

2. 查找算法

复制代码 代码如下:

typedef int KeyType ; #define m 5 /*B 树的阶，暂设为5*/ typedef struct Node{ int keynum; /* 结点中关键码的个数，即结点的大小*/ struct Node *parent; /*指向双亲结点*/ KeyType key[m+1]; /*关键码向量，0 号单元未用*/ struct Node *ptr[m+1]; /*子树指针向量*/ Record *recptr[m+1]; /*记录指针向量*/ }NodeType; /*B 树结点类型*/ typedef struct{ NodeType *pt; /*指向找到的结点*/ int i; /*在结点中的关键码序号，结点序号区间[1…m]*/ int tag; /* 1:查找成功，0:查找失败*/ }Result; /*B 树的查找结果类型*/ Result SearchBTree(NodeType *t,KeyType kx) { /*在m 阶B 树t 上查找关键码kx，反回(pt,i,tag)。若查找成功，则特征值tag=1，*/ /*指针pt 所指结点中第i 个关键码等于kx；否则，特征值tag=0,等于kx 的关键码记录*/ /*应插入在指针pt 所指结点中第i 个和第i+1 个关键码之间*/ p=t;q=NULL;found=FALSE;i=0; /*初始化，p 指向待查结点，q 指向p 的双亲*/ while(p&&!found) { n=p->keynum;i=Search(p,kx); /*在p-->key[1…keynum]中查找*/ if(i>0&&p->key[i]= =kx) found=TRUE; /*找到*/ else {q=p;p=p->ptr[i];} } if(found) return (p,i,1); /*查找成功*/ else return (q,i,0); /*查找不成功，反回kx 的插入位置信息*/ }

关键词标签: 搜索 索引 详细介绍