B+树、B*树及MySQL的两种引擎

2017-06-18 15:03 阅读 821 次 评论 0 条

本篇博客继承前面B-树,对B-树的变种B+/B*树展开分析,是一场没有代码的战争,以及MySQL数据库的两个引擎MyISAMInnoDB作以阐述,文中引入了部分网上资料。

B+Tree的定义与特性

B+树作为B-树的一个变种,也是一种多路搜索树。其定义基本与B-树没有区别,除了以下几点:

1)非叶子结点的子树指针域关键字个数相同。

2)非叶子结点的子树指针P[i],指向关键字属于([K[i],K[i+1]])的子树(B-树是开区间)。

3)它为所有叶子结点增加了一个链指针。

4)所有的关键字都在叶子结点出现。

下图是一个M=3阶的B+树(此图引自网上):

B+树的搜索与B-树也基本相同,区别在于B+树只有到达叶子结点才能被命中,而B-树可以在非叶子结点被命中,其性能也等价于在关键字全集做了一次二分查找

B+树的特性如下(承接上述与B-树的区别的一种解释罢了):

① 所有关键字都出现在叶子结点的链表中(稠密索引),且链表中的关键字恰好是有序的。

② 不可能在非叶子结点命中。

③ 非叶子结点相当于是叶子结点的索引(稀疏索引),叶子结点相当于是存储(关键字)数据的数据层。

④ B+树更适合做文件系统。

在B+树上进行随机查找、插入和删除基本与B-树类似,不同之处在于:

B+树在查找时:若非终端结点上的关键字等于给定值,并不终止,而是继续向下直到叶子结点。因此,在B+树中查找无论成功与否,都会走到叶子节点。

B+树在插入时:仅在叶子结点上进行,当结点中的关键字个数大于M时要分裂成两个节点,它们所包含的关键字个数分别为[(M+1)/2]和[(M+1)/2],并且它们的双亲结点中应包含这两个节点中的最小/大关键字。

B+树在删除时:仅在叶子结点上进行,当叶子结点中的最小/大关键字被删除时,并在非终端结点中的值可以作为一个分界关键字存在。若因删除而使节点中关键字小于[M/2]时,其和兄弟节点的合并过程与B-树类似。

B*Tree的定义与特性

B*树是B-树的二次变种,即在B+树的非根和非叶子结点增加了指向兄弟的指针。它的图示如下:

B*树定义了非叶子结点关键字个数至少为(2/3)*M,即块的最低使用率为2/3(代替B+树的1/2)。

对上面的解释为:B*树插入时,当一个节点满时,如果它的下一个兄弟节点未满,那么将一部分数据移到兄弟节点中,再在原节点插入关键字,最后修改父节点中兄弟节点的关键字(因为兄弟节点的关键字范围改变了)。如果兄弟节点满了,则在原节点与兄弟节点之间增加新节点,并各复制1/3的数据到新节点,最后在父节点增加新节点的指针。

B-Tree及变种的总结

B- 树:多路搜索树,每个节点存储M/2到M个关键字,非叶子节点存储指向关键字范围的子节点。

B+树:在B-树的基础上为叶子结点增加了链表指针,所有关键字都在叶子结点出现,非叶子节点作为叶子结点的索引,且只能在叶子结点才能够被命中。

B* 树:在B+树的基础上,为非根非叶子结点增加链表指针,将节点的最低利用率从1/2提高到2/3。

MySQL的两种引擎

目前大多数的数据库系统及文件系统都采用B-Tree及其变种B+Tree作为索引结构,虽然RB-Tree也可以用来实现索引,但是依据计算机的局部性原理,采用B-/+Tree可以减少查找过程中磁盘I/O的存取次数,从而提高效率。

▶MyISAM索引实现(非聚集)

MyISAM引擎使用B+Tree作为索引结构,叶节点的data域存放的是数据记录的地址(B+Tree中,key是表主键,value是数据在磁盘中的地址)。下图是MyIASM的原理图:

上述表中共有三列,假设Col1为主键,可以看出MyISAM的索引文件仅仅保存数据记录的地址,在MyISAM中,主索引与辅助索引在结构上没有任何区别,只是主索引要求key唯一,而辅助索引可以重复。

MyISAM索引检查的算法为首先按照B+Tree搜索算法搜索索引,如果key存在,则去除其data域的值,然后以data域的值为地址,读取相应的数据记录。

▶InnoDB索引实现(聚集)

虽然InnoDB也使用B+Tree作为索引结构,但具体实现方式却与MyISAM截然不同。原理图如下:

InnoDB与MyISAM的主要区别在于:

1)事务处理方面:MyISAM强调的是性能,查询的速度比InnoDB更快,但是不提供事务支持。

2)外键方面:MyISAM不支持外键,但InnoDB支持外键。

3)锁机制方面:MyISAM只支持表级锁,InnoDB支持行级锁和表级锁,默认为行级锁。

4)全文索引方面:MyISAM支持全文索引,InnoDB不支持全文索引。InnoDB从MySQL5.6版本开始提供全文索引。

5)表主键方面:MyISAM允许没有主键的表存在。InnoDB如果没有设定主键,就会自动生成一个6字节的主键(用户不可见)。

6)表的具体行数:MyISAM只要简单的读出保存好的行数,因为它内置了一个计数器,count(*)时它直接从计数器中读。InnoDB不保存表的具体行数,需要扫描一遍整个表来计算有多少行。

① InnoDB的数据文件本身就是索引文件,而MyISAM索引文件和数据文件是分离的,索引文件仅保存数据记录的地址。而InnoDB的叶节点保存了完整的数据记录。

② InnoDB的辅助索引data域存储相应记录主键的值而不是地址,即InnoDB的索引辅助索引都引用主键作为data域。

聚集索引这种实现方式使得按主键的搜索十分高效,但是辅助索引搜索需要检索两遍索引:首先检索辅助索引获得主键,然后用主键到主索引中检索获得记录。
版权声明:本文著作权归原作者所有,欢迎分享本文,谢谢支持!
转载请注明:B+树、B*树及MySQL的两种引擎 | 术与道的分享
分类:编程素养 标签:, ,
1024do.com导航_术与道导航平台

发表评论


表情