ca888会员登录数据库索引浅析

2019-04-05 03:52栏目:程序人生

数据库索引的特点:

  • 避免进行数据库全表的扫描,大多数情况,只需要扫描较少的索引页和数据页,而不是查询所有数据页。而且对于非聚集索引,有时不需要访问数据页即可得到数据。
  • 聚集索引可以避免数据插入操作,集中于表的最后一个数据页面。
  • 在某些情况下,索引可以避免排序操作。

数据库索引

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

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

在数据之外,数据库系统还维护着满足特定查找算法的数据结构,这些数据结构以某种方式引用(指向)数据,这样就可以在这些数据结构上实现高级查找算法。这种数据结构,就是索引。

ca888会员登录 1

index.png

为了加快Col2的查找,可以维护一个右边所示的二叉查找树,每个节点分别包含索引键值和一个指向对应数据记录物理地址的指针,这样就可以运用二叉查找在O(log2n)的复杂度内获取到相应数据。
但是实际的数据库系统几乎没有使用二叉查找树或其进化品种红黑树(red-black tree)实现的
索引的实现通常使用B树及其变种B 树。

B 树

      B 树是应文件系统所需而产生的一种B-树的变形树。一棵m 阶的B 树和m 阶的B-
树的差异在于:
⑴有n 棵子树的结点中含有n 个关键码;
⑵所有的叶子结点中包含了全部关键码的信息,及指向含有这些关键码记录的指针,且
叶子结点本身依关键码的大小自小而大的顺序链接。
⑶所有的非终端结点可以看成是索引部分,结点中仅含有其子树根结点中最大(或最小)关键码。

 

 

 如图一棵3阶的B 树:

ca888会员登录 2

                                图4.2(c)

 如果因此使双亲结点中的关键字数目小于ceil(m/2)-1,则依次类推。

[例如],在 图4.2(c)的B-树中删去关键字37之后,双亲b结点中剩余信息(“指针c”)应和其双亲*a结点中关键字45一起合并至右兄弟结点*e中,删除后的B-树如图 4.2(d)所示。  
ca888会员登录 3 

 

B-树主要应用在文件系统

为了将大型数据库文件存储在硬盘上 以减少访问硬盘次数为目的 在此提出了一种平衡多路查找树——B-树结构 由其性能分析可知它的检索效率是相当高的 为了提高 B-树性能’还有很多种B-树的变型,力图对B-树进行改进,如B 树。

 

2. InnoDB索引实现

然InnoDB也使用B Tree作为索引结构,但具体实现方式却与MyISAM截然不同.

1)主键索引:

         MyISAM索引文件和数据文件是分离的,索引文件仅保存数据记录的地址。而在InnoDB 中,表数据文件本身就是按B Tree组织的一个索引结构,这棵树的叶节点data域保存了完整的数据记录。这个索引的key是数据表的主键,因此 InnoDB表数据文件本身就是主索引。

ca888会员登录 4

 

               (图inndb主键索引)

(图inndb主键索引)是InnoDB主索引(同时也是数据文件)的示意图,可以看到叶节点包含了完整的数据记录。这种索引叫做聚集索引。 因为InnoDB的数据文件本身要按主键聚集,所以InnoDB要求表必须有主键(MyISAM可以没有),如果没有显式指定,则MySQL系统会自动选 择一个可以唯一标识数据记录的列作为主键,如果不存在这种列,则MySQL自动为InnoDB表生成一个隐含字段作为主键,这个字段长度为6个字节,类型 为长整形。

2). InnoDB的辅助索引

       InnoDB的所有辅助索引都引用主键作为data域。例如,下图为定义在Col3上的一个辅助索引:

ca888会员登录 5

        InnoDB 表是基于聚簇索引建立的。因此InnoDB 的索引能提供一种非常快速的主键查找性能。不过,它的辅助索引(Secondary Index, 也就是非主键索引)也会包含主键列,所以,如果主键定义的比较大,其他索引也将很大。如果想在表上定义 、很多索引,则争取尽量把主键定义得小一些。InnoDB 不会压缩索引。

      文字符的ASCII码作为比较准则。聚集索引这种实现方式使得按主键的搜索十分高效,但是辅助索引搜索需要检索两遍索引:首先检索辅助索引获得主键,然后用主键到主索引中检索获得记录。

      不同存储引擎的索引实现方式对于正确使用和优化索引都非常有帮助,例如知道了InnoDB的索引实现后,就很容易明白为什么不建议使用过长的字段作为主 键,因为所有辅助索引都引用主索引,过长的主索引会令辅助索引变得过大。再例如,用非单调的字段作为主键在InnoDB中不是个好主意,因为InnoDB 数据文件本身是一颗B Tree,非单调的主键会造成在插入新记录时数据文件为了维持B Tree的特性而频繁的分裂调整,十分低效,而使用自增字段作为 主键则是一个很好的选择。

 InnoDB索引MyISAM索引的区别:

一是主索引的区别,InnoDB的数据文件本身就是索引文件。而MyISAM的索引和数据是分开的。

二是辅助索引的区别:InnoDB的辅助索引data域存储相应记录主键的值而不是地址。而MyISAM的辅助索引和主索引没有多大区别。

(转载出处:) B-树 1 .B-树定义 B-树是一种平衡的多...

两种类型的存储

在计算机系统中一般包含两种类型的存储,计算机主存(RAM)和外部存储器(如硬盘、CD、SSD等)。在设计索引算法和存储结构时,我们必须要考虑到这两种类型的存储特点。主存的读取速度快,相对于主存,外部磁盘的数据读取速率要比主从慢好几个数量级,具体它们之间的差别后面会详细介绍。 上面讲的所有查询算法都是假设数据存储在计算机主存中的,计算机主存一般比较小,实际数据库中数据都是存储到外部存储器的。

一般来说,索引本身也很大,不可能全部存储在内存中,因此索引往往以索引文件的形式存储的磁盘上。这样的话,索引查找过程中就要产生磁盘I/O消耗,相对于内存存取,I/O存取的消耗要高几个数量级,所以评价一个数据结构作为索引的优劣最重要的指标就是在查找过程中磁盘I/O操作次数的渐进复杂度。换句话说,索引的结构组织要尽量减少查找过程中磁盘I/O的存取次数。下面详细介绍内存和磁盘存取原理,然后再结合这些原理分析B-/ Tree作为索引的效率。

分类

唯一索引
唯一索引是不允许其中任何两行具有相同索引值的索引。
主键索引
数据库表经常有一列或列组合,其值唯一标识表中的每一行。该列称为表的主键。
在数据库关系图中为表定义主键将自动创建主键索引,主键索引是唯一索引的特定类型。该索引要求主键中的每个值都唯一。当在查询中使用主键索引时,它还允许对数据的快速访问。
聚集索引
在聚集索引中,表中行的物理顺序与键值的逻辑(索引)顺序相同。一个表只能包含一个聚集索引。

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  ca888会员登录 6 为关键码的个数。
⑸所有的叶子结点都出现在同一层次上,并且不带信息(可以看作是外部结点或查找失败的结点,实际上这些结点不存在,指向这些结点的指针为空)。

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

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

          ca888会员登录 7

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

          ca888会员登录 8

        也就是说在n个关键字的B树查找,从根节点到关键字所在的节点所涉及的节点数不超过:

      ca888会员登录 9

3.B-树的插入

  B-树的生成也是从空树起,逐个插入关键字而得。但由于B-树结点中的关键字个数必须≥ceil(m/2)-1,因此,每次插入一个关键字不是在树中添加一个叶子结点,而是首先在最低层的某个非终端结点中添加一个关键字,若该结点的关键字个数不超过m-1,则插入完成,否则要产生结点的“分裂”,

如图(a) 为3阶的B-树(图中略去F结点(即叶子结点)),假设需依次插入关键字30,26,85。

ca888会员登录 10

1) 首先通过查找确定插入的位置。由根*a 起进行查找,确定30应插入的在*d 节点中。由于*d 中关键字数目不超过2(即m-1),故第一个关键字插入完成:如(b)

ca888会员登录 11

2) 同样,通过查找确定关键字26亦应插入 *d. 由于*d节点关键字数目超过2,此时需要将 *d分裂成两个节点,关键字26及其前、后两个指针仍保留在 *d 节点中,而关键字37 及其前、后两个指针存储到新的产生的节点 *d` 中。同时将关键字30 和指示节点 *d `的指针插入到其双亲的节点中。由于 *b节点中的关键字数目没有超过2,则插入完成.如(c)(d)

ca888会员登录 12ca888会员登录 13

 

 

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

ca888会员登录 14ca888会员登录 15ca888会员登录 16

插入算法:

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。

ca888会员登录 17

                                图4.1( a)

因此,下面我们可以只需讨论删除最下层非终端结点中的关键字的情形。有下列三种可能:

    (1)被删关键字所在结点中的关键字数目不小于ceil(m/2),则只需从该结点中删去该关键字Ki和相应指针Ai,树的其它部分不变,例如,从图  图4.1( a)所示B-树中删去关键字12,删除后的B-树如图  图4.2( a)所示:

ca888会员登录 18

                           图4.2( a)

   (2)被删关键字所在结点中的关键字数目等于ceil(m/2)-1,而与该结点相邻的右兄弟(或左兄弟)结点中的关键字数目大于ceil(m/2)-1,则需将其兄弟结点中的最小(或最大)的关键字上移至双亲结点中,而将双亲结点中小于(或大于)且紧靠该上移关键字的关键字下移至被删关键字所在结点中。

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

ca888会员登录 19

 

                           图4.2(b)

       (3)被删关键字所在结点和其相邻的兄弟结点中的关键字数目均等于ceil(m/2)-1。假设该结点有右兄弟,且其右兄弟结点地址由双亲结点中的指针Ai所指,则在删去关键字之后,它所在结点中剩余的关键字和指针,加上双亲结点中的关键字Ki一起,合并到 Ai所指兄弟结点中(若没有右兄弟,则合并至左兄弟结点中)。

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

 ca888会员登录 20

                     图 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  ca888会员登录 21 为关键码的个数。
⑸所有的叶子结点都出现在同一层次上,并且不带信息(可以看作是外部结点或查找失败的结点,实际上这些结点不存在,指向这些结点的指针为空)。

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

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

          ca888会员登录 22

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

         ca888会员登录 23

        也就是说在n个关键字的B树查找,从根节点到关键字所在的节点所涉及的节点数不超过:

      ca888会员登录 24

3.B-树的插入

  B-树的生成也是从空树起,逐个插入关键字而得。但由于B-树结点中的关键字个数必须≥ceil(m/2)-1,因此,每次插入一个关键字不是在树中添加一个叶子结点,而是首先在最低层的某个非终端结点中添加一个关键字,若该结点的关键字个数不超过m-1,则插入完成,否则要产生结点的“分裂”,

如图(a) 为3阶的B-树(图中略去F结点(即叶子结点)),假设需依次插入关键字30,26,85。

ca888会员登录 25

1) 首先通过查找确定插入的位置。由根*a 起进行查找,确定30应插入的在*d 节点中。由于*d 中关键字数目不超过2(即m-1),故第一个关键字插入完成:如(b)

ca888会员登录 26

2) 同样,通过查找确定关键字26亦应插入 *d. 由于*d节点关键字数目超过2,此时需要将 *d分裂成两个节点,关键字26及其前、后两个指针仍保留在 *d 节点中,而关键字37 及其前、后两个指针存储到新的产生的节点 *d` 中。同时将关键字30 和指示节点 *d `的指针插入到其双亲的节点中。由于 *b节点中的关键字数目没有超过2,则插入完成.如(c)(d)

ca888会员登录 27ca888会员登录 28

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

ca888会员登录 29ca888会员登录 30ca888会员登录 31

插入算法:

 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。

ca888会员登录 32

 

                                图4.1( a)

因此,下面我们可以只需讨论删除最下层非终端结点中的关键字的情形。有下列三种可能:

    (1)被删关键字所在结点中的关键字数目不小于ceil(m/2),则只需从该结点中删去该关键字Ki和相应指针Ai,树的其它部分不变,例如,从图  图4.1( a)所示B-树中删去关键字12,删除后的B-树如图  图4.2( a)所示:

ca888会员登录 33

 

                           图4.2( a)

   (2)被删关键字所在结点中的关键字数目等于ceil(m/2)-1,而与该结点相邻的右兄弟(或左兄弟)结点中的关键字数目大于ceil(m/2)-1,则需将其兄弟结点中的最小(或最大)的关键字上移至双亲结点中,而将双亲结点中小于(或大于)且紧靠该上移关键字的关键字下移至被删关键字所在结点中。

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

ca888会员登录 34

 

                               图4.2(b)

       (3)被删关键字所在结点和其相邻的兄弟结点中的关键字数目均等于ceil(m/2)-1。假设该结点有右兄弟,且其右兄弟结点地址由双亲结点中的指针Ai所指,则在删去关键字之后,它所在结点中剩余的关键字和指针,加上双亲结点中的关键字Ki一起,合并到 Ai所指兄弟结点中(若没有右兄弟,则合并至左兄弟结点中)。

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

 ca888会员登录 35

 

                                图4.2(c)

 如果因此使双亲结点中的关键字数目小于ceil(m/2)-1,则依次类推。

[例如],在 图4.2(c)的B-树中删去关键字37之后,双亲b结点中剩余信息(“指针c”)应和其双亲*a结点中关键字45一起合并至右兄弟结点*e中,删除后的B-树如图 4.2(d)所示。  
ca888会员登录 36

 

                         图 4.2(d)

B-树主要应用在文件系统

为了将大型数据库文件存储在硬盘上 以减少访问硬盘次数为目的 在此提出了一种平衡多路查找树——B-树结构 由其性能分析可知它的检索效率是相当高的 为了提高 B-树性能’还有很多种B-树的变型,力图对B-树进行改进

版权声明:本文由ca888发布于程序人生,转载请注明出处:ca888会员登录数据库索引浅析