计算机理论论文关系数据库CODB中XML全文检索的设计与实现.docVIP

关系数据库CoDB中XML全文检索的设计与实现 　　　　　　　　　　 5.1索引的存储 我们使用和数据库存储分离的方式来保存全文检索.我们使用文件系统将索引的结果按词作为文件名来存储,假设索引目录为%INDEX%.我们对于中英文的分词处理也不同.对于中文按字索引所以不需要字典,英文单词之间由于有空格分开可以很容易的分词.中文索引文件名为十6进制的编码.例如”大”字对应的索引文件为00F3B4H.英文单词的索引文件较简单,例如单词word对应的索引文件为%INDEX%/word.我们设置了最大词长度MAX_WORD_LENGTH,当词的实际长度超过此长度时,该词被忽略.自索引文件我们使用%INDEX%/word_idx作为文件名来存储. 文件中的每条记录的结构如下:TID ElementOffset OffsetToElement DeweyId 其中TID可以唯1的标记文档, ElementOffset为该词所在的XML节点的起始位置(按字节),OffsetToElement 为该词相对于该XML节点的偏移量(按字节).该词在文档中的实际出现位置(按字节)为ElementOffset + OffsetToElement.DeweyId为所在节点在XML文档中的DeweyId.DeweyId可以参看XML的编码1节. 为提高建立索引的速度,我们在写索引文件的时候使用Cache技术.建立索引时使用Cache和不使用Cache速度上可以差十倍之多.目前Cache块数为16k,每块大小为8k,每块Cache对应1个词. Xfti为Cache的结构体,整个过程中只使用1个,由CreateXftiIndex函数生成,由CloseXftiIndex函数释放.该结构体其中包含索引目录cDir,1个Cache结构体数组pCache和1个指向Cache数组的指针数组.该数组用于对Cache按词序排序,以便2分法查找.iCacheCount为使用中的Cache块个数(总是出现在前面).其中每个Cache块的结构体包括:Cache内容开始偏移量iStart(之前为该词)及结束偏移量 iEnd,以及块cBuf(前面存储词,后面是Cache内容,如cBuf=“secret\01 2 3 4 5 6 “, iStart=7, iEnd=19). 结构体find_data为parse出的结果信息.其中cWord为结果单词,pText指向当前文档iLength为该词长度,iOffset为当前单词在XML节点中的相对偏移量,iPositoin为词序,iPathLength为当前DeweyId的长度,数组iPath为当前DeweyId,数组iStartOffset为当前DeweyId上每个节点对应的开始偏移量,iStatus和iXmlStatus用于标示当前parse状态. 自索引文件的存储采用按块存储的方法,每个块存储1个内部节点,1个块不够存储时使用溢出块并连接起来. 主要函数的说明: InitFindData 对struct find_data的初始化,只被IndexFile调用 CheckXml 检查文档是否为Xml文档(只检查xml头)对非xml文档不使用DeweyId,但现在实际上已经放弃了,所有返回值均相同(在struct find_data中),即对所有文档均按xml处理. SeekToNextWord 定位到文档中下1词,其中包含比较复杂的parse过程,以及设置当前DeweyId等. CopyWord 将定位到的词复制到find_data结构体中. FindNextWord 查找下1词,结果放到find_data结构体中. CreateXftiIndex 创建Cache,用于建索引,必须的.须指定索引目录. FlushXftiCache 将Cache中的内容写回磁盘 LocateXftiCache 定位到指定的词对应的Cache,Cache使用替换最满的策略 WriteXftiCache 将1个整数写入定位到的Cache CloseXftiCache 写盘和并释放Cache内存 IndexFile 对指定字符串(pFile)建索引. 5.2利用索引进行检索 我们分开处理单个词和多个单词组合的情况.多个关键字调用单个词的检索函数并使用合并算法进行合并. 我们采用检索单个单词的结构体result: struct result { unsigned int dwBid; // 文档的TID中的块号 unsigned short wPid; // 文档的TID中的块内偏移号 unsigned int dwNextBid; // 为下次检索保留的块号 unsigned short wNextPid; // 为下次检索保留的