MySQL索引改进的B+树的研究

林荣杭 刘小英

摘要：MySQL数据库采用了B+树作为索引的数据结构，传统的B+树的叶子节点是一个单向的指针，这使得在范围搜索数据时，只能单方面查找一个方向的数据，极大地增加了数据查找的时间。为了增加MySQL数据库中索引的搜索效率，提出一种改进的B+树，通过对B+树的叶子节点增加一个双向的指针，提出双向查找数据的B+树算法，通过与原生B+樹的搜索进行对比发现，改进的B+树在范围搜索方面可以极大地减少搜索时间和I/O次数。

关键词：数据库;B+树;数据结构;MySQL

中图分类号：TP301        文献标识码：A

文章编号：1009-3044（2022）16-0012-02

数据库作为目前最有效地管理数据的方式被广泛应用于各类应用系统中[1-2]。在大量的数据库选型中，MySQL数据库因为自身开源，轻便，速度快的优势成了最为频繁使用的数据库之一[3-5]。在MySQL数据库的底层，为了方便对数据的查找、插入、删除、修改以及维护，MySQL数据库在众多的数据结构中选择了B+树这一数据结构来实现索引、实现底层的数据信息管理。B+树是多路查找树B树的一个变种[6]，同时B+树的树结构是多路搜索的平衡树，数据仅存储在叶子节点中，非叶子结点引导搜索，同时为了有效检索所有的叶子页面，叶子节点间通过指针相互链接[7]。本文在研究了传统B+树搜索的原理后，对B+树的叶子结点进行了优化，有效地提高了搜索效率。

1 传统B+树

1.1 B+树的特征

B+ tree 是一种多叉树，每个节点可以拥有大量子节点，同一个树中允许不同的节点可以拥有不同数量的子节点[8]。一棵B+ tree由一个根节点、若干个内部节点和若干个叶节点组成。B+树中数据以键值对（Key - value）的形式存储在树中，非叶子节点只存储键（Key），而在叶子节点中存储键和值（Key - value）。通过观察图1，一个3阶的B+树，可以发现B+树一个节点可以存放多个值。一颗阶为P的B+树，它的Root（根）节点至少应该有两个子节点，同时Root节点最多只能拥有P个孩子节点。同时这个B+树的每个非叶子节点最多也只有P个孩子节点，最少应该存在两个节点，这个特性和Root节点一样。而每个叶子节点中最多存在P-1个元素，最少存在?P/2?个元素。

1.2 B+树对数据的操作

B+树对数据的操作主要包括查找、插入和删除。对数据进行插入和删除的时候，B+树会判断每个节点的子节点是否满足最多存在P-1个元素，最少存在?P/2?个元素的规则，不满足则实现上溢或者下溢操作，调整树的平衡，在自我平衡后B+树每个叶子节点到Root节点的深度也是一样的。在进行数据插入操作时，B+树会对插入数据进行排序，实现自身数据结构的有序性。在对数据进行有序排序后，B+树在叶子节点会利用一个单向链表形式的数据结构将叶子节点的所有节点有序的串联在一起。在进行查找操作时，B+树会通过非叶子节点来逐个定位到一个需要查找的范围，然后在这个范围的叶子节点进行搜索，搜索的方式则是通过叶子节点的单向链表来查找数据。

2 改进的B+树

2.1改进思路

通过观察B+树的查找方式不难发现，B+树在查找一个数据时首先定位某个非叶节点是否存在该数据，不存在则在一个范围内的叶子节点中通过单向链表查找，但是当叶子节点过多时就会发生链表长度过长，此时采用单向链表查找模式就会出现极大的时间浪费，同时也不利于MySQL数据库对数据的精确范围查找，因为单向链表只有一个方向，无法满足在使用MySQL数据库时出现的双向查找，所以需要让B+树的叶子节点不只是单向的链接，而是可以双向循环的链接，让数据查找时可以随意沿着某个方向去查找，如图2所示。

2.2改进后的B+树算法

MySQL数据库在进行数据操作时常会使用范围的查找，例如使用select * from * where x（字段）

以下是改进后的B+树搜索算法

输入：第一个满足小于搜索值（Key）的位置

输出：获取到所有满足小于搜索值（Key）的值

List findless（V key，List list） {

if（this.number <=0）  //判断当前叶子节点是否存在值

return null;

Integer left = 0;   //叶子节点内部是个数组

Integer right = this.number;

Integer i = 0;

while（true） {

if（key.compareTo（i） <= 0） { //获取所有小于Key的值

list.add（this.values[i++]）;

}else {  //表示已经遍历完当前叶子节点中所有小于Key的值

if（this.prev.title.equals（"end"））{

break; //判断指针是否已经移动到最右边的叶子节点

}

this.key = prev.key; //将当前的key数组指向叶子节点左边的叶子节点的key数组

this.values = prev.values;//同上操作，让values数组指向左边的values数组

}

}

return list;}

在改进了B+树的搜索算法后，B+树的搜索小于某个值的流程为：

1）调用搜索算法先定位到第一个小于或等于搜索值的临界值;

2）对临界值的叶子节点进行遍历，因为是数组，其遍历的时间复杂度为O（1）;

3）遇到第一个大于搜索值的数据时，将Key和Values数组移动到前一个叶子节点中;

4）遍历前一个叶子节点数据;

5）遍历完后检查前一个叶子节点是否为右边最后一个节点，如果是则结束遍历操作，并返回值，不是继续移动指针并遍历。

3 实验分析

3.1实验对比

为了验证改进后的B+树在MySQL中搜索效率的提升，本文选择Java为编程语言，在Eclipse上分别对改进前后的B+树进行了构建，并通过两者的I/O次数和查找用时来探讨改进后的B+树在数据查找方面的优势。在实验中采取了控制变量法用于提高实验的可信性，实验中的B+树为512阶，并且搜索5条数据（搜索结果只有5条数据，格式为大于x和小于y），得到结果如表1、表2所示。

3.2实验数据分析

由表1可以得出，随着数据量的增加，虽然搜索的数据一直都只有5条数据，但是由于搜索的5条数据是双向的，而初始的B+树当中叶子节点是一个单向链表，无法满足对数据的双向搜索，所以会产生更多的I/O次数，当数据达到105级别时会出现I/O次数骤升的情况。改进后的B+树，因为叶子节点是双向循环的，所以每次搜索的I/O次数都十分平均，没有出现骤升的情况。由表2可以得出，原B+树在数据量为105由于I/O次数的增加，其搜索时间也突然增加，但是改进后的B+树并不会出现这种现象，这也增加了搜索的稳定性，不会出现突然间的时间增大。在数据逐渐增大的过程中MySQL使用改进后的B+树时所带来的时间消耗并不会出现突然性的增加，而是一个平缓的过程，这证明了在将B+树改进后，B+树的搜索优化效果较好。

4 结论

通过分析原生B+树的基本特点，提出了一种MySQL索引改进的B+树，通过将B+树叶子节点的单向链表变为双向链表来提升B+树在对范围数据进行查找的效率。改进后的B+树在对范围数据进行查找时带来了极高的效率，无论是从I/O次数还是时间消耗上来看都得到了极大的提升，这些提升对于数据存储量极大的MySQL数据库而言有现实意义。

参考文献：

[1] 侯金彪.一种基于Jsp和MySQL的外卖系统的设计与实现[J].安顺学院学报，2021，23（3）：129-136.

[2] 朱宝善，陈光浦，李鹏程，等.基于B/S模式和MySQL的人力资源管理系统设计[J].现代电子技术，2021，44（14）：65-69.

[3] 宋永鹏.基于MySQL的数据库查询性能优化[J].电子设计工程，2021，29（12）：43-47.

[4] 豆利.基于MySQL的查询优化技术[J].电脑知识与技术，2021，17（15）：35-36.

[5] 石怡.基于MySQL数据库的查询性能优化研究[J].四川职业技术学院学报，2021，31（1）：164-168.

[6] 王澜.内存数据库中B+树和CSB+树的性能比較[J].通讯世界，2015（12）：277.

[7] 施恩，顾大权，冯径，等.B+树索引机制的研究及优化[J].计算机应用研究，2017，34（6）：1766-1769.

[8] 时亚南.B+树算法的Java实现方法研究[J].计算机技术与发展，2015，25（1）：111-114.

【通联编辑：王力】