数据库数据结构 B-树和B 树的选择:数据检索和数

作者:数据库

数据库索引的性情:

  • 防止举行数据库全表的围观,大相当多场地,只必要扫描很少的索引页和数据页,并不是询问全数数据页。何况对于非聚集索引,有的时候不须求拜会数据页就能够获得数码。
  • 聚集索引能够制止数据插入操作,聚集于表的末梢八个数额页面。
  • 在少数意况下,索引能够幸免排序操作。

数据库索引

原稿地址: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作为目录结构,这一节将构成Computer组成原理相关知识探讨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
树,不管查找成功与否,每趟搜寻都是走了一条从根到叶子结点的不二等秘书籍。

本文由ca88发布,转载请注明来源

关键词: ca88网址 MySQL 技术 数据结构 索引