基于B-树和B+树的使用：数据搜索和数据库索引的详细分析
发布时间：2021-11-27 15:18:55 所属栏目：PHP教程 来源：互联网
导读：B-树 1 .B-树定义 B-树是一种平衡的多路查找树，它在文件系统中很有用。 定义：一棵m 阶的B-树，或者为空树，或为满足下列特性的m 叉树： ⑴树中每个结点至多有m 棵子树； ⑵若根结点不是叶子结点，则至少有两棵子树； ⑶除根结点之外的所有非终端结点至少有
|
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 的插入位置信息*/ } B- 树查找算法分析 从查找算法中可以看出， 在B- 树中进行查找包含两种基本操作: ( 1) 在B- 树中查找结点； ( 2) 在结点中查找关键字。 由于B- 树通常存储在磁盘上， 则前一查找操作是在磁盘上进行的， 而后一查找操作是在内存中进行的， 即在磁盘上找到指针p 所指结点后， 先将结点中的信息读入内存， 然后再利用顺序查找或折半查找查询等于K 的关键字。显然， 在磁盘上进行一次查找比在内存中进行一次查找的时间消耗多得多. 因此， 在磁盘上进行查找的次数、即待查找关键字所在结点在B- 树上的层次树， 是决定B树查找效率的首要因素 那么，对含有n 个关键码的m 阶B-树，最坏情况下达到多深呢？可按二叉平衡树进行类似分析。首先，讨论m 阶B-数各层上的最少结点数。 由B树定义：B树包含n个关键字。因此有n+1个树叶都在第J+1 层。 1）第一层为根，至少一个结点，根至少有两个孩子，因此在第二层至少有两个结点。 2）除根和树叶外，其它结点至少有[m/2]个孩子,因此第三层至少有2*[m/2]个结点,在第四层至少有2*[m/2]2 个结点… 3）那么在第J+1层至少有2*[m/2]J-1个结点,而J+1层的结点为叶子结点,于是叶子结点的个数n+1。有： 也就是说在n个关键字的B树查找，从根节点到关键字所在的节点所涉及的节点数不超过： 3.B-树的插入 B-树的生成也是从空树起，逐个插入关键字而得。但由于B-树结点中的关键字个数必须≥ceil(m／2)-1，因此，每次插入一个关键字不是在树中添加一个叶子结点，而是首先在最低层的某个非终端结点中添加一个关键字，若该结点的关键字个数不超过m-1，则插入完成，否则要产生结点的“分裂”， 如图（a） 为3阶的B-树(图中略去F结点(即叶子结点))，假设需依次插入关键字30，26，85。 1) 首先通过查找确定插入的位置。由根*a 起进行查找，确定30应插入的在*d 节点中。由于*d 中关键字数目不超过2（即m-1），故第一个关键字插入完成：如（b） 2) 同样，通过查找确定关键字26亦应插入 *d. 由于*d节点关键字数目超过2，此时需要将 *d分裂成两个节点，关键字26及其前、后两个指针仍保留在 *d 节点中，而关键字37 及其前、后两个指针存储到新的产生的节点 *d` 中。同时将关键字30 和指示节点 *d `的指针插入到其双亲的节点中。由于 *b节点中的关键字数目没有超过2，则插入完成.如（c）(d) 3) (e) -(g) 为插入85后;  （编辑：应用网_丽江站长网） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
浙公网安备 33038102330468号