基于B+树的文本信息检索技术

张 华,顾红飞,刘 涛

（阜阳职业技术学院工程科技学院,安徽阜阳 236031）

基于B+树的文本信息检索技术

张 华,顾红飞,刘 涛

（阜阳职业技术学院工程科技学院,安徽阜阳 236031）

随着人类步入信息时代,网上庞大的数字化信息与人们获取所需信息能力之间的矛盾日益突出,怎样快速地检索相关信息已经成为研究热点。阐述了全文检索系统的原理,分析了基于字表结构的索引组织方法和索引库的建立。通过和B-树的对比,提出了基于B+树的索引存储方法及其算法思想,对提高索引的存储效率和查找速度具有一定意义。

B+树;全文索引;B-树;倒排索引

随着互联网的发展,如何充分利用网上的信息资源正在成为信息科学研究者所关注的热点。信息检索技术是根据互联网信息的特点而发展起来的一种检索方式。信息检索技术主要研究信息的表示、存储、组织和访问,即根据用户的查询要求,从信息数据库中检索出相关信息资料,其核心为文本信息的索引和检索,即全文检索技术。

1 全文检索系统

全文检索是指计算机索引程序通过扫描文章中的每一个词,对全文建立一个能精确定位每个字词的索引,当用户查询时,检索程序根据事先建立好的索引进行查找,并将查找的结果反馈给用户的检索方式。全文检索的核心技术是将源文档中所有的基本元素的出现信息记录到索引库中,在中文系统中,基本元素可以是单个汉字字符,也可以是词。因此存在两种基本的索引库结构,即基于字表的索引库和基于词表的索引库。字表法和词表法各有优缺点,文章主要讨论基于字表的检索方式。

全文检索系统是指按照全文检索技术理论建立起来的用于提供全文检索服务的软件系统。一般来说,全文检索系统需要具备建立索引和提供查询这两项基本功能。功能上,全文检索系统核心具有建立索引、增加索引、优化索引、处理查询返回结果集等功能。结构上,全文检索系统核心具有索引引擎、查询引擎、文本分析引擎、对外接口,加上各种外围应用系统等共同构成了全文检索系统。

图1 全文检索系统结构图

图1展示了全文检索系统的结构与功能。全文检索系统中最核心、最关键的部分是全文检索引擎部分,从功能模块上可以划分为文本分析模块、创建索引模块、查询索引模块。索引的准备工作和搜索的应用都是建立在这个引擎之上,因此提升全文检索引擎的效率即是我们提升全文检索应用效率的关键。

2 索引的数据结构

2.1 索引组织

中文索引策略中索引的组织方法有两种,即正向索引和倒排索引[1]（P24-26）。在信息检索系统中,会为每个文档分配一个唯一的ID号作为其标志,在索引数据库中以这个文档ID号表示该文档。索引建立的方法有正向索引和倒排索引（如图2所示）,正向索引是以文档的ID为关键字,表中记录文档中每个词出现的位置信息,进行检索时扫描表中每个文档中词的信息直到找出所有包含查询关键字的文档。这种方法的索引结构比较简单、维护方便,但是在查询的时候将会对所有的文档进行顺序扫描,因此使得检索时间大大延长,检索效率较低。所以这里采用倒排表（如图2所示）作为文档数据索引方式,倒排索引以索引单元作为关键字,每个关键字对应着该索引单元在所有文档中出现的位置信息、频率等。进行检索时可以一次得到该关键字对应的所有文档,因此检索时间短,检索效率较高。由于每个词对应的文档数量在动态变化,所以倒排表的建立和维护较为复杂,但是在检索的时候由于可以一次得到查询关键词对应的所有文档,所以效率远远高于正排表。

图2 正向索引和倒排索引

图3 字表图

图4 字表及字表段结构

2.2 建立索引库

建立一个全文检索系统,首先将源文档转换为能够进行文本查找的全文索引库,包括全文的分割处理以及规范格式等,这称为前处理工作,前处理完成后,即可开始建立索引,先过滤掉源文档中的排版符号、格式控制符等,再把源文档中每一个字的出现位置信息记录到索引库中。

前期处理工作主要将文档的内容全部提取出来,去除无用的信息,再转换成统一的格式类型。在文章检索系统的处理中,静态文件要去除文件内容中的大量标记,如htm l标记,动态文档则可直接抽取出数据库中的相应字段内容。处理完成后将所有内容转换成字符串类型的对象,最后根据一个词典,用一个“切词软件”,从处理完的字符串中切出所含的词,去掉诸如“的”,“在”等没有内容指示意义的词,这样文档就主要由一组词来近似代表了,如p={t1,t2,…tn…}。

索引库对每个不同的字符都保存一个字表,字表法索引库的主要部分是每个字的字表信息,字表结构如图3所示,其中字符i对应的字表值记录了该字符在源文档中所出现的位置 Pix。在这里,位置采用字符相对于文档头的偏移字符数表示,而不按通常情况采用相对于文档头的偏移字节数,这样可减小位置的数值大小,有利于进一步采用压缩技术。建立字表时,需要扫描整个源文档,对出现的每一个有效字符,计算其在文档中出现的位置,并将该位置的值加入到对应的字表中。字表是索引库中最主要的部分,在每个汉字字符对应的字表中包含该字符出现在所有文档中的全部位置。为了区分每个位置值属于哪个文档,每个字符的字表被分为多个字表段（图4）,每段对应一个文档,记录该字符在此文档中出现的位置。

2.3 索引的存储结构及查找方式

全文索引[2]（P9-10）把正文看作一个长的字符串,可以对每一个字符建立索引,从而使查询不再限于关键词,但也需要更大的空间,因此索引库[3]（P7-10）所需的空间很大。因此选择合理的存储结构,使其能够快速地得到关键字对应的文档id集,倒排存储结构有指针链表、Hash表、B树、二级索引等多种方法,这里我们采用B+[4]树存储结构。

2.3.1 B-树[5]的结构与特点

B-树的结构如下:

1、每个结点至多有m个子结点;2、除根结点和叶结点外,其他每个结点至少有个子结点;3、根节点至少有两个子结点,唯一例外的是根结点是叶结点时没有子结点,此时B-树只包含一个结点;4、有λ+1个子结点的非根结点必有λ个关键码,它包含如下信息:（P0,K1,P1,K2,P2,K3,…,Pλ-1,Kλ,Pλ）;5、所有叶结点在同一层。

B树上进行查找包含两种基本操作:（1）在B树中找结点;（2）在结点中找关键字。由于B树通常存储在磁盘上,则前一查找操作是在磁盘上进行的,而后一查找操作是在内存中进行的,即在磁盘上找到指针P所指结点后,先将结点中的信息读入内存,然后再利用顺序查找或折半查找查询等于K的关键字。显然,在磁盘上进行一次查找比在内存中进行一次查找耗费时间多得多,因此,在磁盘上进行查找的次数即待查找的次数,也就等于待查关键字所在结点在B树上的层次数,是决定B树查找效率的首要因素。

假设m阶B-树包含N个关键字,由分析可知第k层至少有2×k-1个结点,

对B-树进行插入,会产生分裂。设L是内部结点的个数,除根外的所有内部结点都包括-1个关键字时,B-树所包括的总关键字个数最少,故

2.3.2 B+树的性能

2.3.2.1 B+树的结构

B+树是B树的变型,M阶B+树的结构定义如下:1、每个节点至多有m个子女;2、每个节点（除根外）至少有个子女;3、根节点至少有两个子女; 4、有λ个子女的节点必有λ个关键码,它包含如下信息:（P0,K1,P1,K2,P2,K3,…,Pλ-1,Kλ）。

在基本B树中,关键字分布在整个B树中,并且在内部结点中出现的关键字不再出现在叶结点中,这样顺序链就不能将树中所有关键字接在一起。B+树在这一点上做了改动,即把树中所有关键字都按递增次序从左到右插在叶结点上,并用指针链接起来,在B+树中数据指针只存储在树的叶结点中,因此,叶结点的结构与内部结点的结构是不同的。如果搜索字段是关键字,叶结点对每个搜索字段的值有一个入口和一个指向记录的指针,对于非关键搜索字段,指针指向附加级中的一个块,这个块中存放指向数据文件的记录指针。B+树的所有关键码都出现在叶子节点上,上面各层节点中的关键码是下一层相应节点中最大关键码的复写。B+树的构造是由下而上的,m限定了节点的大小,自下而上地把每个节点的最大关键码复写到上一层节点中。（如图5）

2.3.2.2B+树的检索效率

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

第0层结点数1个,关键字数1个;

2.3.2.3B+树的结点分裂次数

图5 B+树

2.3.3B+树和B-树的性能比较

由公式（1）知含N个关键字的B-树的检索层次KB-≤1+log（N+1）/2,大于1。由公式（5）知含N个关键字的B+树的检索层次kB+≤logN/2,小于1,kB+小于KB-,因此相同关键字数中B+数的检索层次小,检索效率更高。由图5可知B+树上有两个指针,一个指向根结点,另一个指向关键字最小的叶子结点。B +树的关键字存储在叶子结点,同组关键字是顺序排列,进行顺序查找比B-树容易实现,优点是加快了顺序访问的速度,删除过程简化,被删除的关键字只需要从叶子结点移出,相关指针进行移动,其他内部结点保持不变。B+树的第二种查找方式是从根结点开始进行随机查找,由于B+树的检索层次比B-树小,对磁盘的存取次数少,速度更快。

由公式（3）知道B-树每插入一个关键码的平均分裂次数为小于等于1/（-1）,随着m的增大,分裂次数逐渐减少。由公式（8）知道B+树的最大分裂次数为p=1-1/（-1）比B-树的略大,但是随着m的增长分裂次数p的值总小于1,因此B+树需要进行“分裂”处理的概率不大,因为B+树具有良好的查找速度,插入操作比较简单等优势,因此采用B+树存储结构。

2.4 B+树的算法

2.4.1 结点结构

对于m阶B+树,设计的结点结构对应数据模型如下:

所有内部结点仅含有其子树中的最大关键字,则所有小于等于某一给定关键字值的关键字值将被存储在该给定关键字的子树中。B+树的叶子结点的关键字的个数,具体关键字及每个关键字的地址,关键字值按从小到大顺序排列。此算法的优势在于,设置每个结点的双亲指针、左孩子和右孩子指针,双亲指针使随机查找容易实现,左孩子和右孩子指针使顺序查找得以实现,提高B+树整体的检索效率。

2.4.2 B+树的检索

B+树的检索有两种途径,一种从根开始进行随机查找,第二种是从最小关键字的left指针开始进行线性查找。这里我们采用第一种方式,检索分两个步骤:一、查找目标结点;二、在目标结点中查找关键字。B+树查找若在上层已找到待查关键码并不停止,而是继续沿着相应子树查到叶结点层为止。如果在叶结点的q找到k,则说明找到关键字,否则,没有找到。为此我们定义了如下数据结构:

表示查找结果的类型Result:

2.4.3B+树的插入

B+树的生成是从空树开始逐个插入关键字,由下而上生成。由B+树定义知道关键字必然插在叶结点,因此插入分两个步骤:一、从根向下查找,找到目标结点q;二、在目标结点中插入关键字k。在树T中结点q中i位置中插入关键字k会产生如下几种情况:

（1）当树为空时生成根结点

（2）当q-＞keynum＜m,则直接插入关键字k,如果k是q中的最大关键字,则调整父结点中的相应关键字,继续查看k是否为父结点中的最大关键字,如果是继续向上调整父结点中的关键字,如此循环直至不需调整为止。

（3）当q-＞keynum==m,首先插入关键字k,再分裂为q和q1两个结点,再将两个结点中的最大关键字及q和q1插入父结点中的相应位置。如果父结点中关键字个数大于等于m则重复分裂,向上生长,直至满足条件为止。

3 结束语

全文检索系统对人们从互联网中快速获得有用信息具有积极的意义。随着互联网信息的高速增长,搜索效率降低,耗费时间长的问题越来越严重。文中阐述了全文检索系统的原理,分析了基于字表结构的索引组织方法和索引库的建立。通过和B-树的对比,提出B+树的索引存储方法及其算法思想,对提高索引的存储效率和查找速度具有一定意义。

[1]韩中元.中文索引策略的研究[D].哈尔滨:哈尔滨工程大学（硕士学位论文）,2007.

[2]于波.中文全文检索技术研究[D].武汉:华中师范大学（硕士学位论文）,2004.

[3]陈洪猛.全文检索技术的研究与实现[D].北京:北京工业大学（硕士学位论文）,2008.

[4]古辉,叶会华,赖松风.一种基于B+树的程序信息库设计[J].浙江工业大学学报,2008,36（1）:67-71.

[5]关新民.动态B-树分析与应用[J].吉林化工学院学报, 1999,16（4）:52-56.

Information Retrieval Technique of Text Database Based on B+Tree

ZHANG Hua,GU Hong-fei,LIU Tao

（Institute of Engineering and Technology,FuYang College of Vcational and Technology,Fuyang236031,China）

With human into the information age,the contradiction between large amount of digital information and the information people really need becomes more and more incisive,and how quickly retrieve relevant information has become a hotspot.This article describes the principle of full text retrieval system,analysis of word-based index of the table structure methods and the establishment of the index database.By the comparison between B-tree and B+tree,we find that B+tree structure can be used as storage index tree to boost the speed of store and search greatly.

B+Tree;Full-text-Index;B-Tree;inverted index

TP391.3

A

1009-9735（2010）02-0031-05

2009-11-18

安徽省优秀青年人才基金资助项目（2009SQRZ216）。

张华（1975-）,女,安徽六安人,硕士,讲师,研究方向:基于数据压缩的文本信息检索。