基于B+树的优化树查找技术

0引言

在数据库系统的使用过程当中,数据的查询是使用最频繁的一种数据操作。最基本也是最简单的查询算法是顺序查找,即遍历整个数据库中的表,然后逐行匹配行值是否等于待查找的关键字,其时间复杂度为O(n)。如果数据库中的数据量非常庞大,则这种算法对于时间来说,牺牲是比较大的。在数据库中引入了B+树的查询方式。对于重复性查询的用户来说,B+树的查询方式有其弊端,所以我们基于B+树的模式,优化了传统B+树的查询方式。

1 B+树查询数据

1.1 B+树简介

B+树分为两大部分,一部分是非叶子结点,非叶子结点存储着大量的关键码,这些相当于索引表,并且存储在外存中;另外一部分是叶子结点,叶子结点中存储的是关键字的数据层(有可能是主键,也有可能是数据库中的记录),这些结点通过链表链接,并且有序存储在内存中。简单地说,B+树是平衡多叉树和有序数组链表的组合。

1.2 B+树的特性

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

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

如图1是B+树的树形结构图。

1.3 B+树查询搜索具体算法

2 B+树与查询重复性的结合优化

2.1用户个体查询重复率分析

分析大规模中文搜索日志中的查询重复性,通过用户个体查询重复率等数据的统计发现:查询频率较低的用户,其平均查询重复率也较低;用户查询频率越高,其查询重复率也越高,最终稳定在一个特定的水平。如在30天中,查询次数为10次的用户平均查询重复率约为13%;查询次数为40次的用户平均查询重复率约为28%;当用户查询次数增加到100次左右,其查询重复率接近于35%;当用户查询次数高于100次,其行为特殊,查询重复率统计波动较大,但基本在35%上下浮动。图2给出了用户查找频率与查询重复率的关系。这个数据说明了针对于个人用户的查找习惯,其重复率是比较高的,结合这个特性,对B+树进行优化,可以对查找重复率较高的用户所需的时间进行改良。

2.2 B+树中运用重复查询优先比进行优化

数据库中,只要查询到该有序数组链表中的任意一项,优先比就+1,将查找的优先比最高的前n个提取出来,在新的内存空间中开辟一块内存来存储这些优先比和关键码,一段时间内,并对优先比从大到小排序,排好序的关键码和优先比放进已经开辟的内存中。下一次用户若要是再对这些重复率出现较高的关键码进行查找时,先在新开辟的内存空间中查找,若找到该关键码,则将关键码的信息返回给用户;若没有在该内存找到想要的关键码,则重新在B+树中进行随机查找或者顺序查找。基于B+树的优化树结构为:平衡多叉树+有序数组链表+重复查询优先比。这种基于B+树的优化树的树形图结构如图3所示,图中的A表示优先比。

以下是基于B+树优化树的查找部分关键伪代码。

3查询算法效率分析比较

3.1 B+树的检索效率

假设m阶B+树中包含N个关键字,由B+树结构可知每层上最少关键字个数和结点数如下:第0层结点数1个,关键字数1个;

3.2基于B+树的优化树检索效率

对于用户重复查询率的分析,对于重复查询的关键码,其概率基本在35%上下浮动;

非重复查询关键码概率为1-35%=65%;

对于新加入的搜索优先比A,占用一层孩子结点,加上数据层的孩子结点,其深度为2;

所以B+树的优化查询深度 。

所以,最终比较结果为:

当关键码N趋于无穷时,K′远小于K,即基于B+树的优化树检索效率高于B+树的检索效率。

4结束语

本文通过对个体用户的查询重复率的分析,在查找性能方面进行研究,对B+树的数据库查找技术进行优化改进,使对于一些个体用户查询重复率较高的现象,提高了其时间性能,对于重新在内存中开辟新的空间是否会影响其空间复杂度,还需进一步分析与实现。

摘要：目前,国内大多数据库都采用B+树数据结构来实现索引和查找,这些数据库包括Mysql、SQL Sever等数据库。对于个人用户来说,在多次查找过程中,每次查找的关键码总是位于一个特定的范围或者一部分特定的值中,每次进行查找时,这些查找频率较高的关键码都要重新进行搜索,重新进行定位,如果数据库中存在大量的数据元素,效率就会低下。本文基于B+树的结构思想,增加重复查询优先比(这里的优先比记为A),在内存中开辟一个新的空间,这个空间用来存储这些重复查询优先比。用户再次查找关键码或者数据元素时,先在新开辟的空间中查找优先比A,可实现快速查找,减少因重复查找而耽搁的查找时间。

关键词：B+树,数据库,优化,重复性

参考文献

[1] 窦志成,袁晓洁,何松柏.大规模中文搜索日志中查询重复性分析[J].计算机工程,2008,21(34):40-44.

[2] 张华,顾红飞,刘涛.基于B+树的文本信息检索技术[J].皖西学院学报,2010,26(2):31-35.

[3] 长孙妮妮,张毅坤,华灯鑫,邹子夏,陈浩.一种基于B+树的混合索引结构[J].计算机工程,2012,14(38):37-40.

[4] 耿庆田,狄婧,常亮,赵宏伟.基于B+树的数据索引存储[J].吉林大学学报:理学版,2013,51(6):1134-1135.

[5] 胡廷波,钟俊.基于分簇的B+树数据库索引优化算法[J].计算机应用,2013,33(9):2474-2476.