数据库教程:MySQL B-tree与B+tree索引数据结构剖析

一、产生的背景

二叉查找树的查找时间复杂度是o(logn)，整体的查询效率已经足够高了，那么为什么还会有b树和b+树的进化演进呢? 主要的原因是：二叉树可能会退化成一个线性树，造成磁盘io次数增高的问题，当有大量的数据存储的时候，二叉查找树查询不能将所有的数据加载到内存中，只能逐一加载磁盘页，每个磁盘对应树的节点，造成大量的磁盘io操作（最坏的情况io次数为树的高度），平衡二叉树由于树深度过大而造成磁盘io读写过于频繁，进而导致效率低下。所以，为了减少磁的io的次数，必须降低树的深度，将瘦高的树变得矮胖。

1.1 进化要求

• 每个结点能存储多个元素
• 摒弃二叉树结构，采用多叉树

二、b-tree

b-tree是一种多叉的平衡搜索树（并不一定是二叉的），以一个三阶b-tree为例子来分析，每个储存块都包含：关键字和指向孩子结点的指针，最多有m个孩子，m的大小主要取决于每个存储块的容量和数据库的配置，m表示m阶数的意思。

2.1 b-tree特性

• 根节点至少包括两个孩子，范围是[2,m]；
• 树中每个节点最多包含m阶数个孩子（m是阶数，3阶，即：每个节点最多包含3个孩子）；
• 除了根节点和叶子结点以外，其他每个节点至少有ceil(m/2)个孩子节点，ceil是取上限函数（m是阶数，3阶，即：每个节点至少有2个孩子）；
• 所有的叶子结点都位于同一层。

假设每个非叶子节点包含n个关键字信息，其中：

• ki(i=1,2..,n)为关键字，且关键字按顺序升序排序k(i-1)< ki；
• 关键字的个数n必须满足：[ceil(m/2)-1]<=n<=m-1（非叶子结点的关键字 = 指向孩子的指针个数-1）；
• 非叶子结点的指针：p[1],p[2],…,p[m]；其中p[1]指向关键字小于k[1]的子树（即：3和5均小于8），p[m]指向关键字大于k[m-1]的子树（即：13和15均大于12），其他p[i]指向关键字属于(k[i-1],k[i])的子树，是开区间（即：9和10都处于8-12区间）；

假设需要查询数据15，查询步骤：

• 首先从根部开始找，15<17，往左边p1找，p1指向的子树关键字为8和12；
• 由于15比8和12都大，因此会找到p3；
• p3指向了13和15，13<15，最终找到15；
• 查找的时间复杂度为o(logn)。

三、b+tree

3.1 b+tree特性

b+树是b树的变体，其定义基本上与b树相同，除了：

• 非叶子结点的子树指针与关键字的个数相同；
• 非叶子结点的子树指针p[i]，指向关键字值 [k[i],k[i+1])的子树，左闭右开区间；
• 非叶子结点仅用于索引，数据都保存在叶子结点中；
• 所有的叶子结点均有一个链指针指向下一个叶子结点；
• b+树非叶子结点仅用来存放索引，能存储更多的关键字，使得b+树相对于b树来说更矮壮，能存储更多数据。
• 所有的数据都存储在叶子结点。

四、结论

b+tree相比b-tree更适合用来存储索引，原因如下：

• b+树的磁盘读写代价更低，b+树内部节点不存放数据，只存放索引信息，因此其内部节点相对b-tree会更小，所以同一个盘快就能存储更多的关键字，一次性读入内存中需要查找的关键字也就越多，因此io次数也就越低。
• b+树的查询效率更加稳定，由于b+树内部节点并不是指向文件内容的节点，而只是叶子节点关键字的索引，索引任何一个数据的查询都必须是：任何关键字查询都是从根节点到叶子节点的查询路线，因此每个数据的查询效率都是稳定一致的。
• b+树跟有利于对数据的扫描，b-tree在解决磁盘io性能同时并没有解决元素遍历效率低下问题，而b+树只需要遍历叶子节点就可以实现对所有关键字的扫描，所有对数据库频繁的范围查询是有着更高的查询性能。

到此这篇关于mysql b-tree与b+tree索引数据结构剖析的文章就介绍到这了,更多相关mysql b-tree与b+tree内容请搜索<计算机技术网(www.ctvol.com)!!>以前的文章或继续浏览下面的相关文章希望大家以后多多支持<计算机技术网(www.ctvol.com)!!>！

需要了解更多数据库技术:MySQL B-tree与B+tree索引数据结构剖析，都可以关注数据库技术分享栏目—计算机技术网(www.ctvol.com)!