9512.net
甜梦文库
当前位置:首页 >> 计算机软件及应用 >>

B树


B-树和 B+树的应用:数据搜索和数据库索引
分类: 数据结构与算法 c/c++Mysql2012-07-29 11:272008 人阅读评论(0)收藏举报

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

为关键码的个数。

⑸所有的叶子结点都出现在同一层次上,并且不带信息(可以看作是外部结点或查找失败的结点,实 际上这些结点不存在,指向这些结点的指针为空)。 如一棵四阶 B-树,其深度为 4.

B-树的查找类似二叉排序树的查找,所不同的是 B-树每个结点上是多关键码的有序表,在到达某个 结点时,先在有序表中查找,若找到,则查找成功;否则,到按照对应的指针信息指向的子树中去查 找,当到达叶子结点时,则说明树中没有对应的关键码。 在上图的 B-树上查找关键字 47 的过程如下: 1)首先从更开始,根据根节点指针找到 *节点,因为 *a 节点中只有一个关键字,且给定值 47 > 关 键字 35,则若存在必在指针 A1 所指的子树内。 2)顺指针找到 *c 节点,该节点有两个关键字(43 和 78),而 43 < 47 < 78,若存在比在指针 A1 所 指的子树中。 3)同样,顺指针找到 *g 节点,在该节点找到关键字 47,查找成功。

2. 查找算法
[cpp] view plaincopyprint?

1. 2. 3. 4. 5. 6. 7. 8. 9. 10.

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 树结点类型*/

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. }

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 后;

插入算法:

[cpp] view plaincopyprint?

1. 2. 3. 4. 5. 6. 7. 8. 9.

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

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。

图 4.1( a) 因此,下面我们可以只需讨论删除最下层非终端结点中的关键字的情形。有下列三种可能: (1)被删关键字所在结点中的关键字数目不小于 ceil(m/2),则只需从该结点中删去该关键字 Ki 和相应 指针 Ai, 树的其它部分不变, 例如, 从图 图 4.1( a)所示 B-树中删去关键字 12, 删除后的 B-树如图 图 4.2( a)所示:

图 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)所示。

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

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

图 4.2(c) 如果因此使双亲结点中的关键字数目小于 ceil(m/2)-1,则依次类推。 [例如],在 图 4.2(c)的 B-树中删去关键字 37 之后,双亲 b 结点中剩余信息(“指针 c”)应和其双亲*a 结点中关键字 45 一起合并至右兄弟结点*e 中,删除后的 B-树如图 4.2(d)所示。

图 4.2(d)

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

B+树
B+树是应文件系统所需而产生的一种 B-树的变形树。一棵 m 阶的 B+树和 m 阶的 B树的差异在于: ⑴有 n 棵子树的结点中含有 n 个关键码; ⑵所有的叶子结点中包含了全部关键码的信息,及指向含有这些关键码记录的指针,且

叶子结点本身依关键码的大小自小而大的顺序链接。 ⑶所有的非终端结点可以看成是索引部分,结点中仅含有其子树根结点中最大(或最小)关键码。 如图一棵 3 阶的 B+树:

通常在 B+树上有两个头指针,一个指向根节点,另一个指向关键字最小的叶子节点。因此可以对 B+ 树进行两种查找运算:一种是从最小关键字起顺序查找,另一种是从根节点开始,进行随机查找。 在 B+树上进行随机查找、插入和删除的过程基本上与 B-树类似。只是在查找时,若非终端结点上的 关键码等于给定值,并不终止,而是继续向下直到叶子结点。因此,在 B+ 树,不管查找成功与否,每次查找都是走了一条从根到叶子结点的路径。

B+树在数据库中的应用
1. 索引在数据库中的作用 在数据库系统的使用过程当中, 数据的查询是使用最频繁的一种数据操作。 当数据库中数据非常多 的 时候 ,数据查询的效率就是数据库系统用户最关心的问题。要提高数据查询的效率 ,最简单、有效 的 方法就是在数据表相应的列上建立索引。 索引是对数据库表 中一个或多个列的值进行排序的结 构。与在表 中搜索所有的行相比,索引用指针 指向存储在表中指定列的数据值,然后根据指定的次 序排列这些指针,有助于更快地获取信息。通常情 况下 ,只有当经常查询索引列中的数据时 ,才 需要在表上创建索引。索引将占用磁盘空间,并且影响数 据更新的速度。但是在多数情况下 ,索引 所带来的数据检索速度优势大大超过它的不足之处。 2. B+树在数据库索引中的应用 1)在数据库索引的应用 在数据库索引的应用中,B+树按照下列方式进行组织 :

①叶结点的组织方式 。 B+树的查找键 是数据文件的主键 , 且索引是稠密的。 也就是说 , 叶结点 中 为数据文件的第一个记录设有一个键、 指针对 , 该数据文件可以按主键排序, 也可以不按主键排序 ; 数据文件按主键排序,且 B +树是稀疏索引 , 在叶结点中为数据文件的每一个块设有一个键、指针 对 ;数据文件不按键属性排序 ,且该属性是 B +树 的查找键 , 叶结点中为数据文件里出现的每 个属性 K 设有一个键 、 指针对 , 其中指针执行排序键值为 K 的 记录中的第一个。 ②非叶结点 的组织方式。B+树 中的非叶结点形成 了叶结点上的一个多级稀疏索引。 每个非叶结 点中至少有 ceil( m/2 ) 个指针 , 至多有 m 个指针 。 2)B+树索引的插入和删除 ①在向数据库中插入新的数据时,同时也需要向数据库索引中插入相应的索引键值 ,则需要向 B+ 树 中插入新的键值。即上面我们提到的 B-树插入算法。 ②当从数据库中删除数据时,同时也需要从数据库索引中删除相应的索引键值 ,则需要从 B+树 中 删 除该键值 。即 B-树删除算法

MySQL 的 B-Tree 索引(技术上说 B+Tree)
在 MySQL 中,主要有四种类型的索引,分别为: B-Tree 索引, Hash 索引, Fulltext 索引和 R-Tree 索引。我们主要分析 B-Tree 索引。 B-Tree 索引是 MySQL 数据库中使用最为频繁的索引类型,除了 Archive 存储引擎之外的其他所 有的存储引擎都支持 B-Tree 索引。Archive 引擎直到 MySQL 5.1 才支持索引,而且只支持索引单 个 AUTO_INCREMENT 列。 不仅仅在 MySQL 中是如此, 实际上在其他的很多数据库管理系统中 B-Tree 索引也同样是作为最主 要的索引类型,这主要是因为 B-Tree 索引的存储结构在数据库的数据检索中有非常优异的表现。 一般来说, MySQL 中的 B-Tree 索引的物理文件大多都是以 Balance Tree 的结构来存储的,也 就是所有实际需要的数据都存放于 Tree 的 Leaf Node(叶子节点) ,而且到任何一个 Leaf Node 的 最短路径的长度都是完全相同的,所以我们大家都称之为 B-Tree 索引。当然,可能各种数据库(或 MySQL 的各种存储引擎) 在存放自己的 B-Tree 索引的时候会对存储结构稍作改造。 如 Innodb 存 储引擎的 B-Tree 索引实际使用的存储结构实际上是 B+Tree,也就是在 B-Tree 数据结构的基础 上做了很小的改造,在每一个 Leaf Node 上面出了存放索引键的相关信息之外,还存储了指向与该 Leaf Node 相邻的后一个 LeafNode 的指针信息(增加了顺序访问指针),这主要是为了加快检索 多个相邻 Leaf Node 的效率考虑。

下面主要讨论 MyISAM 和 InnoDB 两个存储引擎的索引实现方式:

1. MyISAM 索引实现:
1)主键索引: MyISAM 引擎使用 B+Tree 作为索引结构, 叶节点的 data 域存放的是数据记录的地址。 下图是 MyISAM 主键索引的原理图:

(图 myisam1) 这里设表一共有三列,假设我们以 Col1 为主键,图 myisam1 是一个 MyISAM 表的主索引(Primary key)示意。可以看出 MyISAM 的索引文件仅仅保存数据记录的地址。 2)辅助索引(Secondary key)

在 MyISAM 中,主索引和辅助索引(Secondary key)在结构上没有任何区别,只是主索引要求 key 是唯一的,而辅助索引的 key 可以重复。如果我们在 Col2 上建立一个辅助索引,则此索引的结构如 下图所示:

同样也是一颗 B+Tree,data 域保存数据记录的地址。因此,MyISAM 中索引检索的算法为首先按照 B+Tree 搜索算法搜索索引,如果指定的 Key 存在,则取出其 data 域的值,然后以 data 域的值为 地址,读取相应数据记录。 MyISAM 的索引方式也叫做“非聚集”的,之所以这么称呼是为了与 InnoDB 的聚集索引区分。

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

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

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

InnoDB 表是基于聚簇索引建立的。 因此 InnoDB 的索引能提供一种非常快速的主键查找性能。 不过, 它的辅助索引(Secondary Index, 也就是非主键索引)也会包含主键列,所以,如果主键定义的比

较大, 其他索引也将很大。 如果想在表上定义 、 很多索引, 则争取尽量把主键定义得小一些。 InnoDB 不会压缩索引。 文字符的 ASCII 码作为比较准则。聚集索引这种实现方式使得按主键的搜索十分高效,但是辅助索 引搜索需要检索两遍索引:首先检索辅助索引获得主键,然后用主键到主索引中检索获得记录。 不同存储引擎的索引实现方式对于正确使用和优化索引都非常有帮助,例如知道了 InnoDB 的索引实 现后,就很容易明白为什么不建议使用过长的字段作为主键,因为所有辅助索引都引用主索引,过长 的主索引会令辅助索引变得过大。再例如,用非单调的字段作为主键在 InnoDB 中不是个好主意,因 为 InnoDB 数据文件本身是一颗 B+Tree,非单调的主键会造成在插入新记录时数据文件为了维持 B+Tree 的特性而频繁的分裂调整,十分低效,而使用自增字段作为主键则是一个很好的选择。 InnoDB 索引和 MyISAM 索引的区别: 一是主索引的区别,InnoDB 的数据文件本身就是索引文件。而 MyISAM 的索引和数据是分开的。 二是辅助索引的区别:InnoDB 的辅助索引 data 域存储相应记录主键的值而不是地址。而 MyISAM 的辅助索引和主索引没有多大区别。

分享到: ? 上一篇:gzip 压缩算法


赞助商链接

更多相关文章:
下列叙述正确的是( )。 A.B树既适应于随机检索,又适于...
下列叙述正确的是( )。 A.B树既适应于随机检索,又适于顺序检索B.B树把所有的关键码都存在叶结点上C.二叉排序树适合外存储器中的索引结构D.B树和B+树用于组织...
以下关于B树运算的叙述中,哪一条是正确的 A.若插入过程...
以下关于B树运算的叙述中,哪一条是正确的 A.若插入过程中根结点发生分裂,则B树的高度加1B.每当进行插入运算,就在B树的最下面一层增加一个新结点C.若要删除的...
已知一棵5阶B树有53个关键字,并且每个节点的关键字都达...
根据B-树定义,m阶B树除根之外所有的非终端节点至少有「m/2」个节点,即3个,而根节点最少有2个节点,当每个节点的关键字是最少状态时,5层的满树节点的关键字...
下面关于B树和B+树的叙述中,不正确的是___。 A) B树和B...
下面关于B树和B+树的叙述中,不正确的是___。 A) B树和B+树都是平衡的多分树B) 都能有效地支持顺序检索C) 都可以用于文件的索引结构D) ...
M阶B树中的M是指()。 A.每个结点至少具有M棵子树 B.每...
C.分支结点中包含的关键字的个数 D.M阶B树的深度 正确答案及相关解析 正确答案 B 解析 [解析] M阶B-树中的M是指B-树中每个结点至多具有M棵子树。最新...
(13)至(14)题基于以下的5阶B树结构,该B树现在的层数为2。
(13)至(14)题基于以下的5阶B树结构,该B树现在的层数为2。往该B树中插入关键码72后,该B树的第2层的结点数为正确答案及相关解析 正确答案 C 解析 [解析]...
在一棵高度为2的5阶B树中,所含关键字的个数最少是 A.5B...
正确答案及相关解析 正确答案 A 解析 一棵高度为2的5阶B树,根结点只有到达5个关键字的时候才能产生分裂,成为高度为2的B树。最新上传套卷...
B树做的图书管理系统
B树做的图书管理系统 - #include<stdio.h> #include<stdlib.h> #include<string.h> #include<conio.h> #include<...
5阶的B树中,每个结点最多有( )个关键码。 _答案_百度高考
正确答案及相关解析 正确答案 B 解析 [分析] 在最坏情况下,对含有n个关键字的m阶B树,其深度L满足如下条件:n+1≥2*({m/2 ...
往该B树中插入关键码72后,该B树的第2层的结点数为[*] A...
往该B树中插入关键码72后,该B树的第2层的结点数为[*] A.6B.7C.8D.9_答案解析_2016年_一模/二模/三模/联考_图文_百度高考
更多相关标签:

All rights reserved Powered by 甜梦文库 9512.net

copyright ©right 2010-2021。
甜梦文库内容来自网络,如有侵犯请联系客服。zhit325@126.com|网站地图