大家好,欢迎收看猿话!
BTree意思是多路平衡查找树,它是一种数据结构。MySQL的InnoDB和MyISAM存储引擎,都是使用它来存储索引。BTree可细分为B-Tree和B+Tree,B+Tree是B-Tree的升级版。MySQL的InnoDB和MyISAM存储引擎使用的是B+Tree。
B-Tree
为了描述B-Tree,首先定义一条记录为一个二元组[key, data] ,key为记录的键值,对应表中的主键值,data为一行记录中除主键外的数据。对于不同的记录,key值互不相同。如下图中的紫色部分就是key,橙色部分就是一行数据,绿色部分就是指针。
一棵m阶的B-Tree有如下特性:
- 每个节点最多有m个子节点。 如上图所示是一个3阶的树,那最多有3个子节点。
- 除了根节点和叶子节点外,其它每个节点至少有ceil(m/2)个子节点。如上图所示是一个3阶的树,那每个节点至少有2个子节点。
- 所有叶子节点都在同一层,且不包含其它关键字信息
- 每个非终端节点包含n个关键字信息(P0,P1,…Pn, k1,…kn) ,关键字的个数n满足:ceil(m/2)-1 <= n <= m-1
- ki(i=1,…n)为关键字,且关键字升序排序。
- Pi(i=1,…n)为指向子树根节点的指针。P(i-1)指向的子树的所有节点关键字均小于ki,但都大于k(i-1)
- 指针存储的是子节点所在磁盘块的地址
假设以根节点为例,关键字为17和35,P1指针指向的子树的数据范围为小于17,P2指针指向的子树的数据范围为17~35,P3指针指向的子树的数据范围为大于35。
当我们要查找关键字29时:
- 根据根节点找到磁盘块1,读入内存。【磁盘I/O操作第1次】
- 比较关键字29在区间(17,35),找到磁盘块1的指针P2。
- 根据P2指针找到磁盘块3,读入内存。【磁盘I/O操作第2次】
- 比较关键字29在区间(26,30),找到磁盘块3的指针P2。
- 根据P2指针找到磁盘块8,读入内存。【磁盘I/O操作第3次】
- 在磁盘块8中的关键字列表中找到关键字29。
分析上面过程,发现需要3次磁盘I/O操作,和3次内存查找操作。由于内存中的关键字是一个有序表结构,可以利用二分法查找提高效率。而3次磁盘I/O操作是影响整个B-Tree查找效率的决定因素。B-Tree相对于AVLTree缩减了节点个数,使每次磁盘I/O取到内存的数据都发挥了作用,从而提高了查询效率。
B+Tree
从上一节中的B-Tree结构图中可以看到,每个节点中不仅包含数据的key值,还有data值。而每一个页的存储空间是有限的,一般为16K(也可以调整),如果data数据较大时将会导致每个节点(即一个页)能存储的key的数量很小。当存储的数据量很大时同样会导致B-Tree的深度较大,增大查询时的磁盘I/O次数,进而影响查询效率。
为解决这个问题,在B-Tree基础上就产生了一种新的数据结构B+Tree。
一棵m阶的B+Tree的特性和m阶的B-Tree基本相同,除了以下几点:
- 非叶子节点上只存储key值信息,而不存储data信息
- 非叶子节点的子树指针与关键字个数相同
- 非叶子节点的子树指针 P[i] , 指向关键字值属于 [K[i], K[i+1]) 的子树( B- 树是开区间)
- 所有关键字都会出现在叶子节点的链表中(稠密索引),且链表中的关键字恰好是有序的。如上图所示的升序。
虽然,MySQL的InnoDB和MyISAM存储引擎使用的都是B+Tree结构,但是它们也有不同之处:
- InnoDB的B+Tree索引分为聚簇索引和非聚簇索引,而MyISAM的B+Tree索引都是非聚簇索引。
- InnoDB的主键索引为聚簇索引,辅助索引为非聚簇索引。主键索引的叶子节点保存了完整的记录,辅助索引的叶子节点并不包含行记录的全部数据,它除了包含键值外,还包含了相应行数据的聚簇索引键。
- MyISAM的非聚簇索引结构都是一样的,它的叶子节点保存的都是磁盘地址,真正的数据存储在另外的地方。
声明:本站部分内容及图片来自互联网,转载是出于传递更多信息之目的,内容观点仅代表作者本人,如有任何标注错误或版权侵犯请与我们联系(Email:2595517585@qq.com),我们将及时更正、删除,谢谢。