数据库检索算法

摘 要：目前数据库的应用复杂多样,为了达到各种数据库的最优查询效率,不同的数据库肯定不能使用相同的数据库检索算法,本文对目前几种常用的数据库及这几种数据库常采用的数据库检索算法进行分析、总结,以达到对各数据库的检索算法进行更高效率的优化的目的.

关 键 词：数据库；检索；算法

中图分类号：TP391

数据库的检索效率在数据库管理系统中一直是需要不断优化的方向,而一个良好的数据库检索算法则对数据库的检索效率起着至关重要的作用.目前,对于各种类型的数据库有不同的检索算法.

其中,小型数据库有XML型数据库,由于XML数据库的嵌套结构均可以使用树型结构的数据模型来表示,对于这种XML检索树,目前广泛采用小枝模式对数据库进行检索；对于海量的数据库,由于其数据量较大,数据库检索时的读取、检索等使用一般的算法效率通常非常低,目前针对这种数据库的特点,结合目前比较热门的云计算技术,发展出一种针对大数据的基于云计算的数据库检索算法；对于分布式数据库的检索,对于整个分布式数据库系统的可用性、可扩展性以及提高分布式数据库的使用效率和可靠性的作用是不可估量的,对于分布式数据库,经常采用基于多关系半连接的检索算法；对于目前数据库技术和网格技术的一种结合,网格数据库也是一种新的数据库应用,为了对网络上的海量数据库资源进行高效的检索,通常采用的是基于启发函数的数据库检索算法.

1基于小枝模式的数据库检索算法

XML目前已成为互联网上的一种数据交互的标准,而对于XML文档的嵌套结构的特点,XML文档常用树型结构的数据模型表示,叫做XML文档树,也叫做XML检索树.XML文档使用文档树表示后,XML查询表达式可以使用查询树表示.将查询语言表达式转换为查询树的方法是将表达式的元素、属性和文本用节点表示.它们之间的父子关系用单斜线边（/）连接,祖先后代关系用双斜线边（//）连接.当查询树中有多个分支时,称为小技模式查询.

小枝模式检索最常用的方法是将XML检索树分解为多个二元结构的父/子或祖先/后代关系,然后在XML文档树中进行匹配,最后采用结构连接算法来对结果进行合并.使用这种方法的不足之处是在检索的过程中会产生大量的中间结果,而这些中间结果中的一部分对最终的小枝模式查询没有什么贡献.

针对小枝模式检索的特点,需要对小枝模式检索进行整体的考虑.在小枝模式检索的基础上衍生出两种优化的小枝模式检索算法：路径栈算法（PathStack算法）和小枝栈算法（TwigStack算法）.这两个算法先通过索引结构,将参与查询的每个元素按照其先序遍历的顺序进行存储.然后顺序扫描一次这些参与连接的元素列表,通过维护多个节点栈,实现小枝模式查询.PathStack算法需要将小枝模式分解为多个路径模式,然后对查询结果进行合并,查询过程中也会产生一些中间结果；TwigStack算法对小枝模式整体考虑,保证找到小枝模式的根节点后才进行入栈操作.

后来又在TwigStack算法的基础上,对小枝模式中含有“包含关系”的结构连接问题进行研究,提出了一般性的整体小枝连接算法（TSGeneric算法,TSGeneric算法可以通过索引,尽可能多地跳过不参与祖先/后代连接的元索,优化了小枝检索模式的效率.

2基于云计算的数据库检索算法

对于海量的数库的检索,单机查询效率往往不尽如人意.通常与目前比较热门的云计算技术结合,但是云计算由于其特点,数据库检索需要一个良好的检索调度算法.研究表明,将连续读取的特性应用到基于云计算的数据库检索调度算法中,即对数据库中要检索的数据可以重组出某些连续关系使之具有连续读取特性,然后将此连续的特性利用到数据存储器上,这种连续的存储方式可以大大提高云计算数据的随机读速率,缩短检索的执行时间,可以大幅度提高系统的性能.目前应用到云计算数据库检索调度的算法有两种：即批处理调度算法与基于计划的调度算法.批处理调度算法重复考虑到内存与I/O的有效运用,使相关的检索操作尽量以批量一次性执行完毕,这样可减少大量的不必要的I/O.但该调度对最大平行度与平衡负载的考虑不够周全,因此可能出现选取的查询仅仅局限于部分节点执行,而对另外部分资源闲置造成节点有不平衡负载的情况.另外一种调度算法是基于计划的调度算法,主要思想是是将现有空闲节点计划检索调度,在有足够可用检索节点的情况下可执行数据库检索,若多个查询同时拥有所需节点,则它们可同时执行.它发展出最大适应优先算法（Largest-Fit-First算法,简称LFF）和最先适应优先算法（First-Fit-First算法,简称FFF）两种算法.LFF将待执行检索的数据库按所需节点数目按照降序排列,使用节点较多的检索会优先处理；而FFF算法按照先进先出原则,对最先进入系统的检索优先处理.

3多关系半连接数据库检索算法

分布式数据库管理系统的性能最关键的决定因素取决于分布式数据库检索算法,因此对于分布式数据库检索处理和优化对整个使用分布式数据库的应用系统数据的可用性、可扩展性、提高分布式数据库的使用效率和可靠性起着不可估量的作用.分布式数据库检索通常采用的是基于多关系半连接的数据库检索算法.由于半连接操作可以充分减小数据库连接时的关系元组,因而可以有效地减少分布式数据库站点间数据的传输量.但是半连接也有可能导致通信次数的大量增加与本地处理时间的延长等不良影响.并且半连接操作会经过两次关系的传递,每次传递到不同的节点后又会执行连接操作,这使得本地的处理时间又延长了.因此可以得到普通半连接检索算法的特点：是按照关系间的连接顺序来执行半连接的,具有处理简单、速度快的优点,但是由于没有考虑对子查询的半连接优化,造成网络通信代价较高.基于上述半连接算法的不足,发展出一种基于多关系的半连接数据库检索算法,该算法解决了执行子查询的中间结果的数据通信造成网络资源的消耗的问题,还定义了确定多关系半连接检索算法的优化函数.实验表明在分布式数据库检索算法中,与普通的半连接算法相比,多关系半连接数据库检索算法的效率更高.使用基于多关系半连接的检索优化算法,使得中间结果数据量和网络通信总代价大大地降低.通过实验表明,在分布式数据库的检索优化中,基于多关系的半连接检索算法比普通的半连接检索算法具有更高的检索效率.

4网格数据库检索算法

网格数据库,是将网格技术与数据库技术相结合的新兴产物.其主要用于有效地对网络上大量的数据资源进行管理,目的是为用户提供一个可以统一化访问的接口.网格数据库系统最重要的应用是用来接收用户的数据检索,并且对检索数据进行优化,并将优化后的检索数据发送到各个网格节点上并行执行,将最终结果返回给用户.网格数据库检索主要用到了数据库副本技术,数据库副本技术主要包含副本创建与迁移、副本的一致性维护以及基于副本的查询处理技术.目前网格数据库检索算法主要有启发函数检索算法,是一种基于缓存的查询处理的检索模型,在此模型上设计一个启发函数,并充分考虑到网格节点负载能力.网格数据库检索的处理框架自上到下由用户接口层、中间协调层与网格执行层三部分组成.用户接口层用于响应用户提交的检索请求,将检索请求交给中间协调层来处理,中间协调层在接收到用户接口层提交的检索请求后,会调用自身的编译解释权对检索信息进行解析和优化,转化为内部统一检索形式,由中间协调层按照一定算法将检索任务分解为多个子任务,并分发到每个网格执行层的网格节点去执行检索.最后对对每个子任务的检索结果进行合并处理,并返回给用户接口层.

5总结

综上看来,各种数据库都各自有不同的数据库检索算法,目前各种数据库检索算法较多,选择合适的数据库及对应的算法对提高检索速度,优化检索结果有非常重要的意义.

[2]李建中.基于多重加权树的并行数据库查询优化方法[J].计算机学报,1998,21（5）.

[3]金胜华.基于启发函数的网格数据库查询算法[J].四川理工学院学报（自然科学版）,2011,24（6）.

[3]杨一展.一种基于数据库查询的改进的决策树算法[J].计算机工程与应用,2008,44（15）.

作者简介：王文宜,女,山东青岛人,实验师,硕士,研究方向：数据库.

作者单位：山东财经大学,济南250014