⑶除根结点之外的所有非终端结点至少有,这些数据结构以某种方式引用(指向)数据

发布时间:2019-08-12  栏目:数据  评论:0 Comments

数据库索引的本性:

  • 防止举办数据库全表的扫描,大比比较多地方,只须求扫描相当少的索引页和数据页,而不是询问全体数据页。何况对于非集中索引,有的时候不供给拜见数据页就能够取得数码。
  • 聚焦索引能够免止数据插入操作,集中于表的最终三个数目页面。
  • 在有些意况下,索引能够制止排序操作。

数据库索引

原稿地址:http://blog.codinglabs.org/articles/theory-of-mysql-index.html

wiki:数据库索引,是数据库管理类别中一个排序的数据结构,以协助神速查询、更新数据库表中数据。

在数据之外,数据库系统还维护着满意特定查找算法的数据结构,那一个数据结构以某种方式引用(指向)数据,那样就能够在这么些数据结构上完结高档搜索算法。这种数据结构,正是索引。

图片 1

index.png

为了加速Col2的寻找,能够爱慕八个入手所示的二叉查找树,每一种节点分别包蕴索引键值和一个针对性对应数据记录物理地址的指针,那样就足以接纳二叉查找在O(log2n)的复杂度内取获得相应数据。
可是其实的数据库系统差不离未有运用二叉查找树或其发展品种红黑树(red-black
tree)实现的

目录的落到实处普通使用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<Ki+1,

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

           n  图片 2 为关键码的个数。
⑸全部的卡片结点都出现在平等等级次序上,并且不带音信(能够看成是外界结点或搜求未果的结点,实际上这个结点不设有,指向那些结点的指针为空)。

   即全数叶节点具备同样的吃水,等于树高度。

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

          图片 3

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                   
typedef struct Node{  
    int keynum;               
    struct Node *parent;       
    KeyType key[m+1];          
    struct Node *ptr[m+1];     
    Record *recptr[m+1];      
}NodeType;                    

typedef struct{  
    NodeType *pt;             
    int i;                    
    int tag;                  
}Result;                      

Result SearchBTree(NodeType *t,KeyType kx)  
{   



    p=t;q=NULL;found=FALSE;i=0;   
    while(p&&!found)  
    {   n=p->keynum;i=Search(p,kx);            
        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);                      
}  

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。有:

          图片 4

        相当于说在n个关键字的B树查找,从根节点到入眼字所在的节点所波及的节点数不超过:

      图片 5

3.B-树的插入

  B树的生成也是从空树起,每种插加入关贸总协定组织键字而得。但由于B树结点中的关键字个数必须≥ceil(m/2)-1,因而,每一回插入叁个重大字不是在树中增加二个叶子结点,而是首先在最低层的有些非终端结点中加多二个根本字,若该结点的要紧字个数不超越m-1,则插入达成,不然要发生结点的“分歧”,

如图(a)
为3阶的B树(图中略去F结点(即叶子结点)),假如需依次插加入关贸总协定组织键字30,26,85。

图片 6

1) 首先通过查找明确插入的职责。由根*a 起实行查找,分明30应插入的在*d
节点中。由于*d
中最主要字数目不超越2(即m-1),故第二个至关心爱抚要字插入达成:如(b)

图片 7

2) 一样,通过寻觅分明重视字26亦应插入 *d.
由于*d节点关键字数目超越2,此时须求将
*d不同成五个节点,关键字26及其前、后多少个指针仍保存在 *d
节点中,而首要字37 会同前、后多个指针存款和储蓄到新的产生的节点 *d`
中。同有的时候间将注重字30 和提醒节点 *d `的指针插入到其父母的节点中。由于
*b节点中的关键字数目未有超越2,则插入完成.如(c)(d)

图片 8图片 9

 

 

3) (e) -(g) 为插入85后;

图片 10图片 11图片 12

安插算法:

int InserBTree(NodeType **t,KeyType kx,NodeType *q,int i){   


    x=kx;ap=NULL;finished=FALSE;  
    while(q&&!finished)  
    {   
        Insert(q,i,x,ap);                 
        if(q->keynum<m) finished=TRUE;      
        else  
        {                                 
            s=m/2;split(q,ap);x=q->key[s];  

            q=q->parent;  
            if(q) i=Search(q,kx);   
        }  
    }  
    if(!finished)             
    NewRoot(t,q,x,ap);   
}  

4. B-树的去除

      反之,若在B树上删除二个首要字,则第一应找到该重大字所在结点,并从中删除之,若该结点为最下层的非终端结点,且当中的主要字数目非常的多于ceil(m/2),则删除实现,不然要拓展“合併”结点的操作。假使所删关键字为非终端结点中的Ki,则能够指针Ai所指子树中的最小关键字Y代替Ki,然后在对应的结点中删去Y。比如,在下图  图4.1(
a)的B树上删去45,能够*f结点中的50代表45,然后在*f结点中剔除50。

图片 13

                                图4.1( a)

所以,下边咱们能够只需座谈删除最下层非终端结点中的关键字的情形。有下列三种大概:

    (1)被删关键字所在结点中的关键字数目不低于ceil(m/2),则只需从该结点中去除该重大字Ki和相应指针Ai,树的其他一些不改变,比如,从图  图4.1(
a)所示B树中去除关键字12,删除后的B树如图  图4.2(
a)所示:

图片 14

                           图4.2( a)

   (2)被删关键字所在结点中的关键字数目等于ceil(m/2)-1,而与该结点相邻的右兄弟(或左兄弟)结点中的关键字数目大于ceil(m/2)-1,则需将其兄弟结点中的最小(或最大)的机要字上移至父母结点中,而将父母结点中型Mini于(或超过)且紧靠该提升关键字的重点字下移至被删关键字所在结点中。

[例如],从图图4.2(
a)中除去50,需将其右兄弟结点中的61上扬至*e结点中,而将*e结点中的53移至*f,从而使*f和*g中一言九鼎字数目均不低于ceil(m-1)-1,而双亲结点中的关键字数目不改变,如图图4.2(b)所示。

图片 15

 

                           图4.2(b)

       (3)被删关键字所在结点和其隔壁的小伙子结点中的关键字数目均等于ceil(m/2)-1。若是该结点有右兄弟,且其右兄弟结点地址由老人结点中的指针Ai所指,则在剔除关键字之后,它所在结点中剩下的严重性字和指针,加上老人结点中的关键字Ki一同,合并到
Ai所指兄弟结点中(若未有右兄弟,则统一至左兄弟结点中)。

[例如],从图4.2(b)所示
B树中去除53,则应除去*f结点,并将*f中的剩余消息(指针“空”)和父老妈*e结点中的
61一同统一到右兄弟结点*g中。删除后的树如图4.2(c)所示。

 图片 16

                     图 4.2(d)

 

B-树紧要行使在文件系统

为了将大型数据库文件存款和储蓄在硬盘上
以调整和裁减访谈硬盘次数为指标 在此提议了一种平衡多路寻找树——B-树结构
由其个性深入分析可见它的索求作用是一对一高的 为了提升 B-树品质’还可能有很三种B-树的变通,力图对B-树进行创新,如B+树。

 

B-树和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<Ki+1,

           Ai 为指向子树根结点的指针(i=0,1,…,n),且指针Ai-1
所指子树中具有结点的要害码均小于Ki (i=1,2,…,n),An
所指子树中全体结点的重大码均大于Kn.

           n
 图片 17
为关键码的个数。
⑸全部的卡片结点都现身在同等档次上,并且不带信息(能够当作是外表结点或搜求未果的结点,实际上那么些结点不设有,指向这一个结点的指针为空)。

   即全数叶节点具有一样的纵深,等于树中度。

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

       
  图片 18

B-树的索求类似二叉排序树的研究,所例外的是B-树每个结点上是多关键码的平稳表,在达到有些结点时,先在静止表中找出,若找到,则查找成功;不然,到遵照相应的指针消息指向的子树中去搜求,当到达叶子结点时,则说明树中没有对应的关键码。

在上海体育场面的B-树上探求关键字47的历程如下:

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

2)顺指针找到 *c节点,该节点有七个第一字(43和 78),而43 < 47 <
78,若存在比在指针A1所指的子树中。

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

2. 搜索算法

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

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。有:

        
图片 19

       
也正是说在n个关键字的B树查找,从根节点到紧要字所在的节点所波及的节点数不超越:

      图片 20

3.B-树的插入

 
B树的扭转也是从空树起,每个插加入关贸总协定组织键字而得。但鉴于B树结点中的关键字个数必须≥ceil(m/2)-1,由此,每趟插入三个根本字不是在树中增加贰个卡片结点,而是首先在最低层的某部非终端结点中加多四个生死攸关字,若该结点的要害字个数不当先m-1,则插入完结,不然要发出结点的“分歧”,

如图(a)
为3阶的B树(图中略去F结点(即叶子结点)),倘若需依次插加入关贸总协定协会键字30,26,85。

图片 21

1) 首先通过寻找明确插入的地点。由根*a 起开始展览搜索,明确30应插入的在*d
节点中。由于*d
中关键字数目不超过2(即m-1),故第二个至关心爱戴要字插入完结:如(b)

图片 22

2) 同样,通过寻找分明主要字26亦应插入 *d.
由于*d节点关键字数目超过2,此时必要将
*d差异成八个节点,关键字26及其前、后四个指针仍保留在 *d
节点中,而关键字37 会同前、后四个指针存款和储蓄到新的发出的节点 *d`
中。同期将主要字30 和指三巳点 *d `的指针插入到其父母的节点中。由于
*b节点中的关键字数目未有超越2,则插入达成.如(c)(d)

图片 23图片 24

3) (e) -(g) 为插入85后;

图片 25图片 26图片 27

插入算法:

 1     int InserBTree(NodeType **t,KeyType kx,NodeType *q,int i){   
 2         /* 在m 阶B 树*t 上结点*q 的key[i],key[i+1]之间插入关键码kx*/   
 3         /*若引起结点过大,则沿双亲链进行必要的结点分裂调整,使*t仍为m 阶B 树*/  
 4         x=kx;ap=NULL;finished=FALSE;  
 5         while(q&&!finished)  
 6         {   
 7             Insert(q,i,x,ap);               /*将x 和ap 分别插入到q->key[i+1]和q->ptr[i+1]*/  
 8             if(q->keynum<m) finished=TRUE;    /*插入完成*/  
 9             else  
10             {                               /*分裂结点*p*/  
11                 s=m/2;split(q,ap);x=q->key[s];  
12                 /*将q->key[s+1…m],q->ptr[s…m]和q->recptr[s+1…m]移入新结点*ap*/  
13                 q=q->parent;  
14                 if(q) i=Search(q,kx); /*在双亲结点*q 中查找kx 的插入位置*/  
15             }  
16         }  
17         if(!finished)           /*(*t)是空树或根结点已分裂为*q*和ap*/  
18         NewRoot(t,q,x,ap); /*生成含信息(t,x,ap)的新的根结点*t,原*t 和ap 为子树指针*/  
19     }  

**4. B-树的删减
**

     
反之,若在B树上删除一个第一字,则第一应找到该重大字所在结点,并从中删除之,若该结点为最下层的非终端结点,且个中的要害字数目非常多于ceil(m/2),则删除完结,不然要实行“合併”结点的操作。要是所删关键字为非终端结点中的Ki,则能够指针Ai所指子树中的最小关键字Y替代Ki,然后在对应的结点中删去Y。比方,在下图 
图4.1(
a)的B树上删去45,能够*f结点中的50代替45,然后在*f结点中删除50。

图片 28

 

                                图4.1( a)

由此,上边我们能够只需商讨删除最下层非终端结点中的关键字的场合。有下列二种只怕:

    (1)被删关键字所在结点中的关键字数目不低于ceil(m/2),则只需从该结点中去除该重大字Ki和对应指针Ai,树的别的一些不改变,比方,从图 
图4.1( a)所示B树中去除关键字12,删除后的B树如图 
图4.2( a)所示:

图片 29

 

                           图4.2( a)

 
 (2)被删关键字所在结点中的关键字数目等于ceil(m/2)-1,而与该结点相邻的右兄弟(或左兄弟)结点中的关键字数目大于ceil(m/2)-1,则需将其兄弟结点中的最小(或最大)的根本字上移至父母结点中,而将老人结点中型Mini于(或高于)且紧靠该升高关键字的首要性字下移至被删关键字所在结点中。

[例如],从图图4.2(
a)中除去50,需将其右兄弟结点中的61向上至*e结点中,而将*e结点中的53移至*f,从而使*f和*g中重大字数目均不低于ceil(m-1)-1,而老人结点中的关键字数目不改变,如图图4.2(b)所示。

图片 30

 

                               图4.2(b)

     
 (3)被删关键字所在结点和其左近的小伙子结点中的关键字数目均等于ceil(m/2)-1。假使该结点有右兄弟,且其右兄弟结点地址由父母结点中的指针Ai所指,则在剔除关键字之后,它所在结点中剩下的要紧字和指针,加上海大学人结点中的关键字Ki一同,合併到
Ai所指兄弟结点中(若未有右兄弟,则统一至左兄弟结点中)。

[例如],从图4.2(b)所示
B树中去除53,则应除去*f结点,并将*f中的剩余音讯(指针“空”)和父母*e结点中的
61一齐统一到右兄弟结点*g中。删除后的树如图4.2(c)所示。

 图片 31

 

                                图4.2(c)

 要是就此使家长结点中的关键字数目小于ceil(m/2)-1,则相继类推。

[例如],在 图4.2(c)的B-树中去除关键字37现在,双亲b结点中剩余新闻(“指针c”)应和其家长*a结点中关键字45一齐统一至右兄弟结点*e中,删除后的B树如图 4.2(d)所示。
 
图片 32

 

                         图 4.2(d)

B-树首要行使在文件系统

为了将重型数据库文件存款和储蓄在硬盘上 以减掉访谈硬盘次数为指标在此提议了一种平衡多路搜索树——B-树结构
由其质量分析可见它的查找效用是相当高的
为了提升 B-树品质’还应该有很二种B-树的变动,力图对B-树进行改良

数据库索引与数据结构

上文说过,二叉树、红黑树等数据结构也能够用来落到实处索引,但是文件系统及数据库系统广大运用B-/+Tree作为目录结构,这一节将整合计算机组成原理相关知识斟酌B-/+Tree作为目录的商议基础。

B-Tree

先是定义一条数据记录为二个二元组[key,
data],key为记录的键值,对于区别数量记录,key是互不一致样的;data为数量记录除key外的数目。那么B-Tree是满意下列条件的数据结构:

  • d为超越1的贰个正整数,称为B-Tree的度。
  • h为三个正整数,称为B-Tree的可观。
  • 各样非叶子节点由n-1个key和n个指针组成,个中d<=n<=2d。
  • 每一个叶子节点最少富含四个key和五个指针,最多含有2d-1个key和2d个指针,
  • 叶节点的指针均为null 。
  • key和指针相互间隔,节点两端是指针。
  • 二个节点中的key从左到右非递减少排放列。
  • 假若有些指针在节点node最侧边且不为null,则其指向节点的兼具key小于v(key1),其中v(key1)为node的首先个key的值。
    倘使有些指针在节点node最右侧且不为null,则其指向节点的富有key大于v(keym),在那之中v(keym)为node的末段多少个key的值。
    万一有个别指针在节点node的左右邻座key分别是keyi和keyi+1且不为null,则其指向节点的具有key小于v(keyi+1)且高于v(keyi)。
    也正是:每一种非终端结点中带有有n个首要字音讯:
    (n,P0,K1,P1,K2,P2,……,Kn,Pn)。当中:
    a) Ki (i=1…n)为重大字,且首要字按梯次升序排序K(i-1)< Ki。
    b)
    Pi为指向子树根的接点,且指针P(i-1)指向子树种全部结点的最首要字均低于Ki,但都大于K(i-1)。
    c) 关键字的个数n必须满意: [ceil(m / 2)-1]<= n <= m-1。

一个d=2的B-Tree示意图:

图片 33

BTree_Search(node, key) {
   if(node == null) return null;
   foreach(node.key)
   {
     if(node.key[i] == key) return node.data[i];
     if(node.key[i] > key) return BTree_Search(point[i]->node);
   }
   return BTree_Search(point[i+1]->node);
}
data = BTree_Search(root, my_key);

其搜索节点个数的渐进复杂度为O(logd N)。

B+树

      B+树是应文件系统所需而发出的一种B-树的变形树。一棵m 阶的B+树和m
阶的B-
树的歧异在于:
⑴有n 棵子树的结点中蕴藏n 个关键码;
⑵全数的卡牌结点中包含了全套关键码的音讯,及指向含有那个关键码记录的指针,且
叶子结点自身依关键码的深浅自小而大的顺序链接。
⑶全数的非终端结点能够用作是索引部分,结点中仅含有其子树根结点中最大(或一点都不大)关键码。

 

 

 如图一棵3阶的B+树:

图片 34

                                图4.2(c)

 假若因而使老人结点中的关键字数目小于ceil(m/2)-1,则相继类推。

[例如],在 图4.2(c)的B-树中去除关键字37随后,双亲b结点中剩余音信(“指针c”)应和其家长*a结点中关键字45一同统一至右兄弟结点*e中,删除后的B树如图 4.2(d)所示。
 
图片 35 

 

B-树首要接纳在文件系统

为了将大型数据库文件存款和储蓄在硬盘上
以压缩访问硬盘次数为目标 在此提议了一种平衡多路搜索树——B-树结构
由其品质解析可见它的找出效能是一对一高的 为了提升 B-树品质’还会有很各类B-树的改造,力图对B-树实行改良,如B+树。

 

B+树

      B+树是应文件系统所需而发出的一种B-树的变形树。一棵m
阶的B+树和m 阶的B-
树的差距在于:
⑴有n 棵子树的结点中包涵n 个关键码;
⑵全数的卡牌结点中带有了整个关键码的音信,及指向含有那几个关键码记录的指针,且
叶子结点本人依关键码的大小自小而大的一一链接。
⑶全数的非终端结点可以当做是索引部分,结点中仅含有其子树根结点中最大(或纤维)关键码。

 如图一棵3阶的B+树:
图片 36
常备在B+树上有四个头指针,三个对准根节点,另一个对准关键字一点都不大的卡片节点。因而能够对B+树举办三种检索运算:一种是从最小关键字起各个查找,另一种是从根节点起先,实行随机查找。 
在B+树上进行随机查找、插入和删除的经过基本上与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<Ki+1,

           Ai
为指向子树根结点的指针(i=0,1,…,n),且指针Ai-1
所指子树中保有结点的第一码均小于Ki (i=1,2,…,n),An
所指子树中具有结点的要害码均大于Kn.

           n
 图片 37 为关键码的个数。
⑸全部的叶子结点都出现在同一档案的次序上,並且不带信息(能够看做是表面结点或查究未果的结点,实际上那么些结点官样文章,指向这么些结点的指针为空)。

   即全体叶节点具有同等的深浅,等于树高度。

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

          图片 38

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。有:

          图片 39

       
也等于说在n个关键字的B树查找,从根节点到根本字所在的节点所提到的节点数不超越:

      图片 40

3.B-树的插入

 
B树的改动也是从空树起,每一个插加入关贸总协定组织键字而得。但鉴于B树结点中的关键字个数必须≥ceil(m/2)-1,因而,每趟插入一个生死攸关字不是在树中增多二个叶子结点,而是首先在最低层的有个别非终端结点中增添一个最重要字,若该结点的主要字个数不超越m-1,则插入实现,否则要发生结点的“分歧”,

如图(a)
为3阶的B树(图中略去F结点(即叶子结点)),假诺需依次插加入关贸总协定组织键字30,26,85。

图片 41

1) 首先通过搜索显明插入的地方。由根*a 起开展搜索,鲜明30应插入的在*d
节点中。由于*d
中重大字数目不当先2(即m-1),故第八个主要字插入落成:如(b)

图片 42

2) 一样,通过搜索鲜明重要字26亦应插入 *d.
由于*d节点关键字数目超过2,此时急需将
*d区别成八个节点,关键字26及其前、后五个指针仍保留在 *d
节点中,而重要字37 会同前、后七个指针存款和储蓄到新的发出的节点 *d`
中。同期将重大字30 和指重三点 *d `的指针插入到其父母的节点中。由于
*b节点中的关键字数目未有超过2,则插入完结.如(c)(d)

图片 43图片 44

3) (e) -(g) 为插入85后;

图片 45图片 46图片 47

插入算法:

int InserBTree(NodeType **t,KeyType kx,NodeType *q,int i){ 
    /* 在m 阶B 树*t 上结点*q 的key[i],key[i+1]之间插入关键码kx*/ 
    /*若引起结点过大,则沿双亲链进行必要的结点分裂调整,使*t仍为m 阶B 树*/
    x=kx;ap=NULL;finished=FALSE;
    while(q&&!finished)
    { 
        Insert(q,i,x,ap);               /*将x 和ap 分别插入到q->key[i+1]和q->ptr[i+1]*/
        if(q->keynum<m) finished=TRUE;    /*插入完成*/
        else
        {                               /*分裂结点*p*/
            s=m/2;split(q,ap);x=q->key[s];
            /*将q->key[s+1…m],q->ptr[s…m]和q->recptr[s+1…m]移入新结点*ap*/
            q=q->parent;
            if(q) i=Search(q,kx); /*在双亲结点*q 中查找kx 的插入位置*/
        }
    }
    if(!finished)           /*(*t)是空树或根结点已分裂为*q*和ap*/
    NewRoot(t,q,x,ap); /*生成含信息(t,x,ap)的新的根结点*t,原*t 和ap 为子树指针*/
}

4. B-树的删除

     
反之,若在B树上删除二个重大字,则率先应找到该重大字所在结点,并从中删除之,若该结点为最下层的非终端结点,且在那之中的要害字数目非常的多于ceil(m/2),则删除完结,不然要实行“合併”结点的操作。借使所删关键字为非终端结点中的Ki,则足以指针Ai所指子树中的最小关键字Y代替Ki,然后在相应的结点中删去Y。比如,在下图 
图4.1(
a)的B树上删去45,能够*f结点中的50代表45,然后在*f结点中除去50。

图片 48

                                图4.1( a)

所以,上面大家能够只需钻探删除最下层非终端结点中的关键字的景观。有下列二种恐怕:

    (1)被删关键字所在结点中的关键字数目异常的大于ceil(m/2),则只需从该结点中删除该重大字Ki和对应指针Ai,树的别样一些不改变,比方,从图 
图4.1( a)所示B树中删除关键字12,删除后的B树如图 
图4.2( a)所示:

图片 49

                           图4.2( a)

   (2)被删关键字所在结点中的关键字数目等于ceil(m/2)-1,而与该结点相邻的右兄弟(或左兄弟)结点中的关键字数目大于ceil(m/2)-1,则需将其兄弟结点中的最小(或最大)的根本字上移至老人结点中,而将养父母结点中型Mini于(或高于)且紧靠该提升关键字的首要性字下移至被删关键字所在结点中。

[例如],从图图4.2(
a)中剔除50,需将其右兄弟结点中的61上扬至*e结点中,而将*e结点中的53移至*f,从而使*f和*g中重要字数目均极大于ceil(m-1)-1,而家长结点中的关键字数目不改变,如图图4.2(b)所示。

图片 50

                               图4.2(b)

       (3)被删关键字所在结点和其相邻的兄弟结点中的关键字数目均等于ceil(m/2)-1。假使该结点有右兄弟,且其右兄弟结点地址由大人结点中的指针Ai所指,则在剔除关键字之后,它所在结点中多余的要紧字和指针,加上海大学人结点中的关键字Ki一齐,合併到
Ai所指兄弟结点中(若未有右兄弟,则统一至左兄弟结点中)。

[例如],从图4.2(b)所示
B树中删除53,则应除去*f结点,并将*f中的剩余新闻(指针“空”)和老人家*e结点中的
61一齐统一到右兄弟结点*g中。删除后的树如图4.2(c)所示。

 图片 51

                                图4.2(c)

 假设因而使父母结点中的关键字数目小于ceil(m/2)-1,则相继类推。

[例如],在 图4.2(c)的B-树中剔除关键字37事后,双亲b结点中剩余信息(“指针c”)应和其父母*a结点中关键字45一同统一至右兄弟结点*e中,删除后的B树如图 4.2(d)所示。
 
图片 52

                         图 4.2(d)

B-树首要选拔在文件系统

为了将大型数据库文件存款和储蓄在硬盘上
以减小访问硬盘次数为目标 在此提议了一种平衡多路寻觅树——B-树结构
由其性质深入分析可见它的追寻功用是一定高的
为了升高 B-树品质’还或然有很三种B-树的转变,力图对B-树举办立异

相关文章

留下评论

网站地图xml地图