2010年4月第26卷第2期皖西学院学报
Jo urnal o f West Anhui Unive rsity A pr . , 2010Vo l . 26 NO . 2
基于B +树的文本信息检索技术
张 华, 顾红飞, 刘 涛
(阜阳职业技术学院工程科技学院, 安徽阜阳236031)
摘 要:随着人类步入信息时代, 网上庞大的数字化信息与人们获取所需信息能力之间的矛盾日益突出, 怎样快速地检索相关信息已经成为研究热点。阐述了全文检索系统的原理, 分析了基于字表结构的索引组织方法和索引库的建立。通过和B -树的对比, 提出了基于B +树的索引存储方法及其算法思想, 对提高索引的存储效率和查找速度具有一定意义。
关键词:B +树; 全文索引; B -树; 倒排索引
中图分类号:T P391. 3 文献标识码:A 文章编号:1009-9735(2010) 02-0031-05
随着互联网的发展, 如何充分利用网上的信息资
源正在成为信息科学研究者所关注的热点。信息检索技术是根据互联网信息的特点而发展起来的一种检索方式。信息检索技术主要研究信息的表示、存储、组织和访问, 即根据用户的查询要求, 从信息数据库中检索出相关信息资料, 其核心为文本信息的索引和检索, 即全文检索技术。
1 全文检索系统
全文检索是指计算机索引程序通过扫描文章中的每一个词, 对全文建立一个能精确定位每个字词的索引, 当用户查询时, 检索程序根据事先建立好的索引进行查找, 并将查找的结果反馈给用户的检索方式。全文检索的核心技术是将源文档中所有的基本元素的出现信息记录到索引库中, 在中文系统中, 基本元素可以是单个汉字字符, 也可以是词。因此存在两种基本的索引库结构, 即基于字表的索引库和基于词表的索引库。字表法和词表法各有优缺点, 文章主要讨论基于字表的检索方式。
全文检索系统是指按照全文检索技术理论建立起来的用于提供全文检索服务的软件系统。一般来说, 全文检索系统需要具备建立索引和提供查询这两项基本功能。功能上, 全文检索系统核心具有建立索引、增加索引、优化索引、处理查询返回结果集等功能。结构上, 全文检索系统核心具有索引引擎、查询引擎、文本分析引擎、对外接口, 加上各种外围应用系统等共同构成了全文检索系统
。
图1 全文检索系统结构图
图1展示了全文检索系统的结构与功能。全文检索系统中最核心、最关键的部分是全文检索引擎部分, 从功能模块上可以划分为文本分析模块、创建索引模块、查询索引模块。索引的准备工作和搜索的应用都是建立在这个引擎之上, 因此提升全文检索引擎的效率即是我们提升全文检索应用效率的关键。2 索引的数据结构2. 1 索引组织
中文索引策略中索引的组织方法有两种, 即正向
P24-26)
索引和倒排索引[1](。在信息检索系统中, 会为每个文档分配一个唯一的ID 号作为其标志, 在索引
＊收稿日期:2009-11-18
基金项目:安徽省优秀青年人才基金资助项目(2009S QRZ216) 。作者简介:张华(1975-) , 女, 安徽六安人, 硕士, 讲师, 研究方向:基于数据压缩的文本信息检索。
数据库中以这个文档ID 号表示该文档。索引建立的方法有正向索引和倒排索引(如图2所示) , 正向索引是以文档的ID 为关键字, 表中记录文档中每个词出现的位置信息, 进行检索时扫描表中每个文档中词的信息直到找出所有包含查询关键字的文档。这种方法的索引结构比较简单、维护方便, 但是在查询的时候将会对所有的文档进行顺序扫描, 因此使得检索时间大大延长, 检索效率较低。所以这里采用倒排表
(如图2所示) 作为文档数据索引方式, 倒排索引以索引单元作为关键字, 每个关键字对应着该索引单元在所有文档中出现的位置信息、频率等。进行检索时可以一次得到该关键字对应的所有文档, 因此检索时间短, 检索效率较高。由于每个词对应的文档数量在动态变化, 所以倒排表的建立和维护较为复杂, 但是在检索的时候由于可以一次得到查询关键词对应的所有文档, 所以效率远远高于正排表
。
图2 正向索引和倒排索引 图3 字表图 图4 字表及字表段结构 2. 2 建立索引库2. 3 索引的存储结构及查找方式
建立一个全文检索系统, 首先将源文档转换为能全文索引[2](P9-10) 把正文看作一个长的字符串,
可以对每一个字符建立索引, 从而使查询不再限于关够进行文本查找的全文索引库, 包括全文的分割处理以及规范格式等, 这称为前处理工作, 前处理完成后,
即可开始建立索引, 先过滤掉源文档中的排版符号、格式控制符等, 再把源文档中每一个字的出现位置信息记录到索引库中。
前期处理工作主要将文档的内容全部提取出来, 去除无用的信息, 再转换成统一的格式类型。在文章检索系统的处理中, 静态文件要去除文件内容中的大量标记, 如html 标记, 动态文档则可直接抽取出数据库中的相应字段内容。处理完成后将所有内容转换成字符串类型的对象, 最后根据一个词典, 用一个“切词软件”, 从处理完的字符串中切出所含的词, 去掉诸如“的”, “在”等没有内容指示意义的词, 这样文档就主要由一组词来近似代表了, 如p ={t1, t2, …tn …}。索引库对每个不同的字符都保存一个字表, 字表法索引库的主要部分是每个字的字表信息, 字表结构如图3所示, 其中字符i 对应的字表值记录了该字符在源文档中所出现的位置P ix 。在这里, 位置采用字符相对于文档头的偏移字符数表示, 而不按通常情况采用相对于文档头的偏移字节数, 这样可减小位置的数值大小, 有利于进一步采用压缩技术。建立字表时, 需要扫描整个源文档, 对出现的每一个有效字符, 计算其在文档中出现的位置, 并将该位置的值加入到对应的字表中。字表是索引库中最主要的部分, 在每个汉字字符对应的字表中包含该字符出现在所有文档中的全部位置。为了区分每个位置值属于哪个文档, 每个字符的字表被分为多个字表段(图4) , 每段对应一个文档, 记录该字符在此文档中出现的位置。键词, 但也需要更大的空间, 因此索引库所需
的空间很大。因此选择合理的存储结构, 使其能够快速地得到关键字对应的文档id 集, 倒排存储结构有指针链表、H ash 表、B 树、二级索引等多种方法, 这里我们采用B +树存储结构。2. 3. 1 B -树[5]的结构与特点
B -树的结构如下:1、每个结点至多有m 个子结点; 2、除根结点和叶结点外, 其他每个结点至少有
个子结点; 3、根
节点至少有两个子结点, 唯一例外的是根结点是叶结点时没有子结点, 此时B -树只包含一个结点; 4、有λ+1个子结点的非根结点必有λ个关键码, 它包含如下信息:(P 0, K 1, P 1, K 2, P 2, K 3, …, P λ-1, K λ, P λ) ; 5、所有叶结点在同一层。
B 树上进行查找包含两种基本操作:(1) 在B 树中找结点; (2) 在结点中找关键字。由于B 树通常存储在磁盘上, 则前一查找操作是在磁盘上进行的, 而后一查找操作是在内存中进行的, 即在磁盘上找到指针P 所指结点后, 先将结点中的信息读入内存, 然后再利用顺序查找或折半查找查询等于K 的关键字。显然, 在磁盘上进行一次查找比在内存中进行一次查找耗费时间多得多, 因此, 在磁盘上进行查找的次数即待查找的次数, 也就等于待查关键字所在结点在B 树上的层次数, 是决定B 树查找效率的首要因素。
假设m 阶B -树包含N 个关键字, 由分析可知第k 层至少有2×
k -1
[4]
[3](P7-10)
个结点,
k -1
则N +1≥2×,
k ≤1+log
(N +1) /2
(1)
-1
第1层2个, 关键字数至少2×第2层至少2×……
第k 层至少2×
k
k -1
个;
2
对B -树进行插入, 会产生分裂。设L 是内部结点的个数, 除根外的所有内部结点都包括个关
键字时, B -树所包括的总关键字个数最少, 故
N 》1+L ×(
-1)
(2)
即L ≤(N -1) /(-1) 在最差的情况下每插入一个结点都经过分裂(除第一个) , 即L 都是分裂而来的, 则每插入一个关键码平均分裂结点个数为S =L /N ≤(N -1) /((
-1) ·N ) ≤1/(
-1)
(3)
个, 关键字数至少2×个;
结点, 关键字数至少2×
个。
k N /2
由于B +树的关键码都在叶子结点, 因此有N ≥2×即k ≤
log
(4) (5) +……+)
(6) -1)
2. 3. 2. 3 B +树的结点分裂次数
B +树的结点数P ≤1+2+2×2×
k -1
2. 3. 2 B +树的性能
2. 3. 2. 1 B +树的结构
B +树是B 树的变型, M 阶B +树的结构定义如下:1、每个节点至多有m 个子女; 2、每个节点(除根外) 至少有
个子女; 3、根节点至少有两个子女; 4、有λ个子女的节点必有λ个关键码, 它包含如下信息:(P 0, K 1, P 1, K 2, P 2, K 3, …,P λ-1, K λ) 。
在基本B 树中, 关键字分布在整个B 树中, 并且在内部结点中出现的关键字不再出现在叶结点中, 这样顺序链就不能将树中所有关键字接在一起。B +树在这一点上做了改动, 即把树中所有关键字都按递增次序从左到右插在叶结点上, 并用指针链接起来, 在B +树中数据指针只存储在树的叶结点中, 因此, 叶结点的结构与内部结点的结构是不同的。如果搜索字段是关键字, 叶结点对每个搜索字段的值有一个入口和一个指向记录的指针, 对于非关键搜索字段, 指针指向附加级中的一个块, 这个块中存放指向数据文件的记录指针。B +树的所有关键码都出现在叶子节点上, 上面各层节点中的关键码是下一层相应节点中最大关键码的复写。B +树的构造是由下而上的, m 限定了节点的大小, 自下而上地把每个节点的最大关键码复写到上一层节点中。(如图5
)
=1+2(1-
k
) /(1-
结合公式4) 推出P ≤1+(N -2) /(
(7)
即B +树的最大分裂次数由公式7) 和公式3) P -L =1+(N -2) /(1) /(-1)=1-1/(-1) 2. 3. 3 B +树和B -树的性能比较K B -≤1+log
(N +1) /2
-1)-(N -(8)
由公式(1) 知含N 个关键字的B -树的检索层次
, 大于1。由公式(5) 知含N 个
N /2
关键字的B +树的检索层次k B +≤
log , 小于1,
k B +小于K B -, 因此相同关键字数中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 +树, 设计的结点结构对应数据模型如下:
ty pedef struct BTNode {
图5 B +树
2. 3. 2. 2 B +树的检索效率
假设m 阶B +树中包含N 个关键字, 由B +树结构可知每层上最少关键字个数和结点数如下:
第0层结点数1个, 关键字数1个;
int keynum ; /结点的关键字个数/key type key [m ]; /＊存放关键字的向量＊/struct BTN ode ptr [m ]; /孩子指针向量/
＊
struct BTNode parent , ＊left , ＊rig ht ; /＊指向双亲结点, 左孩子和右孩子结点的指针
＊
＊
＊
＊
＊
＊＊
else {o . pt =p ; o . i =i ; o . tag =0; return o ; }
}(2) 在结点中查找关键字k 的位置
int search (BTree T , Key Type key ) {int n =T ->keynum , i =0; w hile (i key [i ]
re turn (i ) ; }
2. 4. 3 B +树的插入
B +树的生成是从空树开始逐个插入关键字, 由下而上生成。由B +树定义知道关键字必然插在叶结点, 因此插入分两个步骤:一、从根向下查找, 找到目标结点q ; 二、在目标结点中插入关键字k 。在树T 中结点q 中i 位置中插入关键字k 会产生如下几种情况:
(1) 当树为空时生成根结点
T =(BTree ) m alloc (sizeof (BTNode ) ) ; T ->key num =1; T ->pa rent =NU LL ; T ->left =NU LL ; T ->right =N ULL ;
T ->key [0]=k ; T ->ptr [0]=NU LL 。(2) 当q ->keynum
If (I
{inser t (q , I , k , ap ) ; ap =q ; q =q ->parent ; i =search (q , k ) ; }
(3) 当q ->keynum ==m , 首先插入关键字k , 再分裂为q 和q1两个结点, 再将两个结点中的最大关键字及q 和q1插入父结点中的相应位置。如果父结点中关键字个数大于等于m 则重复分裂, 向上生长, 直至满足条件为止。
While (q ->key num ==m )
{s =(q ->keynum ) /2; split (q , q1) ; if (i key [s -1]; ap =q ; q =q ->parent ; if (q1) {i =search (q , x ) ; inse rt (q , i , x , ap ) ; q ->ptr [q ->key num -1]=q1; }
}
/
}BTN ode , BT ree 。
所有内部结点仅含有其子树中的最大关键字, 则所有小于等于某一给定关键字值的关键字值将被存储在该给定关键字的子树中。B +树的叶子结点的关键字的个数, 具体关键字及每个关键字的地址, 关键字值按从小到大顺序排列。此算法的优势在于, 设置每个结点的双亲指针、左孩子和右孩子指针, 双亲指针使随机查找容易实现, 左孩子和右孩子指针使顺序查找得以实现, 提高B +树整体的检索效率。2. 4. 2 B +树的检索B +树的检索有两种途径, 一种从根开始进行随机查找, 第二种是从最小关键字的left 指针开始进行线性查找。这里我们采用第一种方式, 检索分两个步骤:一、查找目标结点; 二、在目标结点中查找关键字。B +树查找若在上层已找到待查关键码并不停止, 而是继续沿着相应子树查到叶结点层为止。如果在叶结点的q 找到k , 则说明找到关键字, 否则, 没有找到。为此我们定义了如下数据结构:
表示查找结果的类型Result :Ty pedef struct
{BTNode pt ; /目标结点指针/Int I ; /＊关键字在目标结点中的位置＊/Int tag ; /查找标志tag 为1表示找到, 0表示没有找到/}Result ; (1) 在树T 中查找关键字k 所在的目标结点Result Search BTree (BTree T , Key Ty pe k )
{BTree p , q ; Result o ; int found , i ;
p =T ; q =N ULL ; found =0; i =0; w hile (p ) {i =search (p , k ) ; if (i >0&&p ->key [i ]==k &&p ->ptr [i ]==NU LL ) fo und =1; else {q =p ; p =p ->ptr [i ]; }}if (fo und ) {o . pt =p ; o . i =i ; o . tag =1; return o ; }＊
＊＊
＊
＊
else {y =q1->key [q1->keynum -1]; ap =q ; q =q ->parent ;
if (q1) {i =search (q , y ) ; q ->key [i ]=y ; q ->ptr [i ]=q1;
x =ap ->key [s -1]; i =search (q , x ) ; insert (q , i , x , ap ) ; }
}}
(4) 当循环向上增长到根时, 如果根满则向上生长新的根new root =(BTree ) malloc (sizeof (BTNode ) ) ; new root ->keynum =2; new root ->parent =NULL ; new root ->left =NULL ; new root ->right =NULL ; new root ->key [0]=x ; new root ->ptr [0]=T ; new root ->key [1]=y ; new root ->ptr [1]=q1; T =new ro ot ; }
(5) 在树bp 中pos 的位置插入关键字key 和子树rp
void insert (BT ree bp , int po s , Key Ty pe key , BTree rp )
{int j ; fo r (j =bp ->keynum ; j >=po s +1; j --)
{bp ->key [j +1]=bp ->key [j ]; bp ->ptr [j +1]=bp ->ptr [j ]; }bp ->key [po s +1]=key ; bp ->ptr [pos +1]=rp ; bp ->key num ++;}(6) 将树oldp 分裂为oldp 和new p 两个子树void split (BTree oldp , BT ree new p ) {int s , n , i ; BTree u =oldp ->right , q1=NULL , q2=NULL ;
s =(oldp ->keynum ) /2; n =oldp ->keynum -s ;
new p =(BTree ) malloc (sizeof (BTNode ) ) ; new p ->keynum =n ;
new p ->parent =oldp ->parent ; oldp ->rig ht ->left =new p ;
new p ->righ t =oldp ->rig ht ; oldp ->rig ht =new p ; new p ->left =oldp ; fo r (i =0; i
{new p ->key [i ]=o ldp ->key [s +i ]; new p ->ptr [i ]=o ldp ->ptr [s +i ]; }o ldp ->keynum =s ; }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
ZH A NG H ua , G U H ong -fei , LIU Tao
(Institute o f Engineering and Technology , FuYang College of Vcational and T echnology , Fuy ang 236031, China )
A bstract :With human into the infor matio n ag e , the contradictio n betw een lar ge amo unt o f digital infor mation and the info rmatio n peo ple really need becomes mo re and mor e incisive , and how quickly retrieve relevant info rma tion has beco me a hotspot . T his arti -cle describes the principle of full tex t retrieval sy stem , analy sis of w ord -based index of the table str ucture methods and the estab -lishment o f the index database . By the compariso n between B -tree and B +tree , w e find that B +tree structure can be used as stor -ag e index tree to bo ost the speed o f stor e and sea rch g rea tly . Key words :B +T ree ; Full -tex t -Index ; B -T ree ; inver ted inde x
2010年4月第26卷第2期皖西学院学报
Jo urnal o f West Anhui Unive rsity A pr . , 2010Vo l . 26 NO . 2
基于B +树的文本信息检索技术
张 华, 顾红飞, 刘 涛
(阜阳职业技术学院工程科技学院, 安徽阜阳236031)
摘 要:随着人类步入信息时代, 网上庞大的数字化信息与人们获取所需信息能力之间的矛盾日益突出, 怎样快速地检索相关信息已经成为研究热点。阐述了全文检索系统的原理, 分析了基于字表结构的索引组织方法和索引库的建立。通过和B -树的对比, 提出了基于B +树的索引存储方法及其算法思想, 对提高索引的存储效率和查找速度具有一定意义。
关键词:B +树; 全文索引; B -树; 倒排索引
中图分类号:T P391. 3 文献标识码:A 文章编号:1009-9735(2010) 02-0031-05
随着互联网的发展, 如何充分利用网上的信息资
源正在成为信息科学研究者所关注的热点。信息检索技术是根据互联网信息的特点而发展起来的一种检索方式。信息检索技术主要研究信息的表示、存储、组织和访问, 即根据用户的查询要求, 从信息数据库中检索出相关信息资料, 其核心为文本信息的索引和检索, 即全文检索技术。
1 全文检索系统
全文检索是指计算机索引程序通过扫描文章中的每一个词, 对全文建立一个能精确定位每个字词的索引, 当用户查询时, 检索程序根据事先建立好的索引进行查找, 并将查找的结果反馈给用户的检索方式。全文检索的核心技术是将源文档中所有的基本元素的出现信息记录到索引库中, 在中文系统中, 基本元素可以是单个汉字字符, 也可以是词。因此存在两种基本的索引库结构, 即基于字表的索引库和基于词表的索引库。字表法和词表法各有优缺点, 文章主要讨论基于字表的检索方式。
全文检索系统是指按照全文检索技术理论建立起来的用于提供全文检索服务的软件系统。一般来说, 全文检索系统需要具备建立索引和提供查询这两项基本功能。功能上, 全文检索系统核心具有建立索引、增加索引、优化索引、处理查询返回结果集等功能。结构上, 全文检索系统核心具有索引引擎、查询引擎、文本分析引擎、对外接口, 加上各种外围应用系统等共同构成了全文检索系统
。
图1 全文检索系统结构图
图1展示了全文检索系统的结构与功能。全文检索系统中最核心、最关键的部分是全文检索引擎部分, 从功能模块上可以划分为文本分析模块、创建索引模块、查询索引模块。索引的准备工作和搜索的应用都是建立在这个引擎之上, 因此提升全文检索引擎的效率即是我们提升全文检索应用效率的关键。2 索引的数据结构2. 1 索引组织
中文索引策略中索引的组织方法有两种, 即正向
P24-26)
索引和倒排索引[1](。在信息检索系统中, 会为每个文档分配一个唯一的ID 号作为其标志, 在索引
＊收稿日期:2009-11-18
基金项目:安徽省优秀青年人才基金资助项目(2009S QRZ216) 。作者简介:张华(1975-) , 女, 安徽六安人, 硕士, 讲师, 研究方向:基于数据压缩的文本信息检索。
数据库中以这个文档ID 号表示该文档。索引建立的方法有正向索引和倒排索引(如图2所示) , 正向索引是以文档的ID 为关键字, 表中记录文档中每个词出现的位置信息, 进行检索时扫描表中每个文档中词的信息直到找出所有包含查询关键字的文档。这种方法的索引结构比较简单、维护方便, 但是在查询的时候将会对所有的文档进行顺序扫描, 因此使得检索时间大大延长, 检索效率较低。所以这里采用倒排表
(如图2所示) 作为文档数据索引方式, 倒排索引以索引单元作为关键字, 每个关键字对应着该索引单元在所有文档中出现的位置信息、频率等。进行检索时可以一次得到该关键字对应的所有文档, 因此检索时间短, 检索效率较高。由于每个词对应的文档数量在动态变化, 所以倒排表的建立和维护较为复杂, 但是在检索的时候由于可以一次得到查询关键词对应的所有文档, 所以效率远远高于正排表
。
图2 正向索引和倒排索引 图3 字表图 图4 字表及字表段结构 2. 2 建立索引库2. 3 索引的存储结构及查找方式
建立一个全文检索系统, 首先将源文档转换为能全文索引[2](P9-10) 把正文看作一个长的字符串,
可以对每一个字符建立索引, 从而使查询不再限于关够进行文本查找的全文索引库, 包括全文的分割处理以及规范格式等, 这称为前处理工作, 前处理完成后,
即可开始建立索引, 先过滤掉源文档中的排版符号、格式控制符等, 再把源文档中每一个字的出现位置信息记录到索引库中。
前期处理工作主要将文档的内容全部提取出来, 去除无用的信息, 再转换成统一的格式类型。在文章检索系统的处理中, 静态文件要去除文件内容中的大量标记, 如html 标记, 动态文档则可直接抽取出数据库中的相应字段内容。处理完成后将所有内容转换成字符串类型的对象, 最后根据一个词典, 用一个“切词软件”, 从处理完的字符串中切出所含的词, 去掉诸如“的”, “在”等没有内容指示意义的词, 这样文档就主要由一组词来近似代表了, 如p ={t1, t2, …tn …}。索引库对每个不同的字符都保存一个字表, 字表法索引库的主要部分是每个字的字表信息, 字表结构如图3所示, 其中字符i 对应的字表值记录了该字符在源文档中所出现的位置P ix 。在这里, 位置采用字符相对于文档头的偏移字符数表示, 而不按通常情况采用相对于文档头的偏移字节数, 这样可减小位置的数值大小, 有利于进一步采用压缩技术。建立字表时, 需要扫描整个源文档, 对出现的每一个有效字符, 计算其在文档中出现的位置, 并将该位置的值加入到对应的字表中。字表是索引库中最主要的部分, 在每个汉字字符对应的字表中包含该字符出现在所有文档中的全部位置。为了区分每个位置值属于哪个文档, 每个字符的字表被分为多个字表段(图4) , 每段对应一个文档, 记录该字符在此文档中出现的位置。键词, 但也需要更大的空间, 因此索引库所需
的空间很大。因此选择合理的存储结构, 使其能够快速地得到关键字对应的文档id 集, 倒排存储结构有指针链表、H ash 表、B 树、二级索引等多种方法, 这里我们采用B +树存储结构。2. 3. 1 B -树[5]的结构与特点
B -树的结构如下:1、每个结点至多有m 个子结点; 2、除根结点和叶结点外, 其他每个结点至少有
个子结点; 3、根
节点至少有两个子结点, 唯一例外的是根结点是叶结点时没有子结点, 此时B -树只包含一个结点; 4、有λ+1个子结点的非根结点必有λ个关键码, 它包含如下信息:(P 0, K 1, P 1, K 2, P 2, K 3, …, P λ-1, K λ, P λ) ; 5、所有叶结点在同一层。
B 树上进行查找包含两种基本操作:(1) 在B 树中找结点; (2) 在结点中找关键字。由于B 树通常存储在磁盘上, 则前一查找操作是在磁盘上进行的, 而后一查找操作是在内存中进行的, 即在磁盘上找到指针P 所指结点后, 先将结点中的信息读入内存, 然后再利用顺序查找或折半查找查询等于K 的关键字。显然, 在磁盘上进行一次查找比在内存中进行一次查找耗费时间多得多, 因此, 在磁盘上进行查找的次数即待查找的次数, 也就等于待查关键字所在结点在B 树上的层次数, 是决定B 树查找效率的首要因素。
假设m 阶B -树包含N 个关键字, 由分析可知第k 层至少有2×
k -1
[4]
[3](P7-10)
个结点,
k -1
则N +1≥2×,
k ≤1+log
(N +1) /2
(1)
-1
第1层2个, 关键字数至少2×第2层至少2×……
第k 层至少2×
k
k -1
个;
2
对B -树进行插入, 会产生分裂。设L 是内部结点的个数, 除根外的所有内部结点都包括个关
键字时, B -树所包括的总关键字个数最少, 故
N 》1+L ×(
-1)
(2)
即L ≤(N -1) /(-1) 在最差的情况下每插入一个结点都经过分裂(除第一个) , 即L 都是分裂而来的, 则每插入一个关键码平均分裂结点个数为S =L /N ≤(N -1) /((
-1) ·N ) ≤1/(
-1)
(3)
个, 关键字数至少2×个;
结点, 关键字数至少2×
个。
k N /2
由于B +树的关键码都在叶子结点, 因此有N ≥2×即k ≤
log
(4) (5) +……+)
(6) -1)
2. 3. 2. 3 B +树的结点分裂次数
B +树的结点数P ≤1+2+2×2×
k -1
2. 3. 2 B +树的性能
2. 3. 2. 1 B +树的结构
B +树是B 树的变型, M 阶B +树的结构定义如下:1、每个节点至多有m 个子女; 2、每个节点(除根外) 至少有
个子女; 3、根节点至少有两个子女; 4、有λ个子女的节点必有λ个关键码, 它包含如下信息:(P 0, K 1, P 1, K 2, P 2, K 3, …,P λ-1, K λ) 。
在基本B 树中, 关键字分布在整个B 树中, 并且在内部结点中出现的关键字不再出现在叶结点中, 这样顺序链就不能将树中所有关键字接在一起。B +树在这一点上做了改动, 即把树中所有关键字都按递增次序从左到右插在叶结点上, 并用指针链接起来, 在B +树中数据指针只存储在树的叶结点中, 因此, 叶结点的结构与内部结点的结构是不同的。如果搜索字段是关键字, 叶结点对每个搜索字段的值有一个入口和一个指向记录的指针, 对于非关键搜索字段, 指针指向附加级中的一个块, 这个块中存放指向数据文件的记录指针。B +树的所有关键码都出现在叶子节点上, 上面各层节点中的关键码是下一层相应节点中最大关键码的复写。B +树的构造是由下而上的, m 限定了节点的大小, 自下而上地把每个节点的最大关键码复写到上一层节点中。(如图5
)
=1+2(1-
k
) /(1-
结合公式4) 推出P ≤1+(N -2) /(
(7)
即B +树的最大分裂次数由公式7) 和公式3) P -L =1+(N -2) /(1) /(-1)=1-1/(-1) 2. 3. 3 B +树和B -树的性能比较K B -≤1+log
(N +1) /2
-1)-(N -(8)
由公式(1) 知含N 个关键字的B -树的检索层次
, 大于1。由公式(5) 知含N 个
N /2
关键字的B +树的检索层次k B +≤
log , 小于1,
k B +小于K B -, 因此相同关键字数中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 +树, 设计的结点结构对应数据模型如下:
ty pedef struct BTNode {
图5 B +树
2. 3. 2. 2 B +树的检索效率
假设m 阶B +树中包含N 个关键字, 由B +树结构可知每层上最少关键字个数和结点数如下:
第0层结点数1个, 关键字数1个;
int keynum ; /结点的关键字个数/key type key [m ]; /＊存放关键字的向量＊/struct BTN ode ptr [m ]; /孩子指针向量/
＊
struct BTNode parent , ＊left , ＊rig ht ; /＊指向双亲结点, 左孩子和右孩子结点的指针
＊
＊
＊
＊
＊
＊＊
else {o . pt =p ; o . i =i ; o . tag =0; return o ; }
}(2) 在结点中查找关键字k 的位置
int search (BTree T , Key Type key ) {int n =T ->keynum , i =0; w hile (i key [i ]
re turn (i ) ; }
2. 4. 3 B +树的插入
B +树的生成是从空树开始逐个插入关键字, 由下而上生成。由B +树定义知道关键字必然插在叶结点, 因此插入分两个步骤:一、从根向下查找, 找到目标结点q ; 二、在目标结点中插入关键字k 。在树T 中结点q 中i 位置中插入关键字k 会产生如下几种情况:
(1) 当树为空时生成根结点
T =(BTree ) m alloc (sizeof (BTNode ) ) ; T ->key num =1; T ->pa rent =NU LL ; T ->left =NU LL ; T ->right =N ULL ;
T ->key [0]=k ; T ->ptr [0]=NU LL 。(2) 当q ->keynum
If (I
{inser t (q , I , k , ap ) ; ap =q ; q =q ->parent ; i =search (q , k ) ; }
(3) 当q ->keynum ==m , 首先插入关键字k , 再分裂为q 和q1两个结点, 再将两个结点中的最大关键字及q 和q1插入父结点中的相应位置。如果父结点中关键字个数大于等于m 则重复分裂, 向上生长, 直至满足条件为止。
While (q ->key num ==m )
{s =(q ->keynum ) /2; split (q , q1) ; if (i key [s -1]; ap =q ; q =q ->parent ; if (q1) {i =search (q , x ) ; inse rt (q , i , x , ap ) ; q ->ptr [q ->key num -1]=q1; }
}
/
}BTN ode , BT ree 。
所有内部结点仅含有其子树中的最大关键字, 则所有小于等于某一给定关键字值的关键字值将被存储在该给定关键字的子树中。B +树的叶子结点的关键字的个数, 具体关键字及每个关键字的地址, 关键字值按从小到大顺序排列。此算法的优势在于, 设置每个结点的双亲指针、左孩子和右孩子指针, 双亲指针使随机查找容易实现, 左孩子和右孩子指针使顺序查找得以实现, 提高B +树整体的检索效率。2. 4. 2 B +树的检索B +树的检索有两种途径, 一种从根开始进行随机查找, 第二种是从最小关键字的left 指针开始进行线性查找。这里我们采用第一种方式, 检索分两个步骤:一、查找目标结点; 二、在目标结点中查找关键字。B +树查找若在上层已找到待查关键码并不停止, 而是继续沿着相应子树查到叶结点层为止。如果在叶结点的q 找到k , 则说明找到关键字, 否则, 没有找到。为此我们定义了如下数据结构:
表示查找结果的类型Result :Ty pedef struct
{BTNode pt ; /目标结点指针/Int I ; /＊关键字在目标结点中的位置＊/Int tag ; /查找标志tag 为1表示找到, 0表示没有找到/}Result ; (1) 在树T 中查找关键字k 所在的目标结点Result Search BTree (BTree T , Key Ty pe k )
{BTree p , q ; Result o ; int found , i ;
p =T ; q =N ULL ; found =0; i =0; w hile (p ) {i =search (p , k ) ; if (i >0&&p ->key [i ]==k &&p ->ptr [i ]==NU LL ) fo und =1; else {q =p ; p =p ->ptr [i ]; }}if (fo und ) {o . pt =p ; o . i =i ; o . tag =1; return o ; }＊
＊＊
＊
＊
else {y =q1->key [q1->keynum -1]; ap =q ; q =q ->parent ;
if (q1) {i =search (q , y ) ; q ->key [i ]=y ; q ->ptr [i ]=q1;
x =ap ->key [s -1]; i =search (q , x ) ; insert (q , i , x , ap ) ; }
}}
(4) 当循环向上增长到根时, 如果根满则向上生长新的根new root =(BTree ) malloc (sizeof (BTNode ) ) ; new root ->keynum =2; new root ->parent =NULL ; new root ->left =NULL ; new root ->right =NULL ; new root ->key [0]=x ; new root ->ptr [0]=T ; new root ->key [1]=y ; new root ->ptr [1]=q1; T =new ro ot ; }
(5) 在树bp 中pos 的位置插入关键字key 和子树rp
void insert (BT ree bp , int po s , Key Ty pe key , BTree rp )
{int j ; fo r (j =bp ->keynum ; j >=po s +1; j --)
{bp ->key [j +1]=bp ->key [j ]; bp ->ptr [j +1]=bp ->ptr [j ]; }bp ->key [po s +1]=key ; bp ->ptr [pos +1]=rp ; bp ->key num ++;}(6) 将树oldp 分裂为oldp 和new p 两个子树void split (BTree oldp , BT ree new p ) {int s , n , i ; BTree u =oldp ->right , q1=NULL , q2=NULL ;
s =(oldp ->keynum ) /2; n =oldp ->keynum -s ;
new p =(BTree ) malloc (sizeof (BTNode ) ) ; new p ->keynum =n ;
new p ->parent =oldp ->parent ; oldp ->rig ht ->left =new p ;
new p ->righ t =oldp ->rig ht ; oldp ->rig ht =new p ; new p ->left =oldp ; fo r (i =0; i
{new p ->key [i ]=o ldp ->key [s +i ]; new p ->ptr [i ]=o ldp ->ptr [s +i ]; }o ldp ->keynum =s ; }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
ZH A NG H ua , G U H ong -fei , LIU Tao
(Institute o f Engineering and Technology , FuYang College of Vcational and T echnology , Fuy ang 236031, China )
A bstract :With human into the infor matio n ag e , the contradictio n betw een lar ge amo unt o f digital infor mation and the info rmatio n peo ple really need becomes mo re and mor e incisive , and how quickly retrieve relevant info rma tion has beco me a hotspot . T his arti -cle describes the principle of full tex t retrieval sy stem , analy sis of w ord -based index of the table str ucture methods and the estab -lishment o f the index database . By the compariso n between B -tree and B +tree , w e find that B +tree structure can be used as stor -ag e index tree to bo ost the speed o f stor e and sea rch g rea tly . Key words :B +T ree ; Full -tex t -Index ; B -T ree ; inver ted inde x