（计算机应用技术专业论文）基于倒排索引的关系数据库全文检索查询效率研究.pdf

摘要 摘要 作为近年来的研究热点，全文检索领域取得了很多新成果和新突破。尤其以 文本数据库为代表的新技术，在各项性能上有了突飞猛进的发展，并能满足当今 大部分的文本检索需求。但是当面对全文检索和结构化数据检索的双重需求时， 许多功能比较单一的文本数据库就显得力不从心。另一方面，除一些费用昂贵的 商用关系数据库( o r a c l e ，d b 2 等) 外，以p o s t g r e s q l 为代表的开源关系数据 库，在全文检索性能表现上显得十分不足，不能很好的满足全文检索的需要。所 以寻找一种即能够满足全文检索和结构化数据检索的双重需求，且价格低廉的方 案就显得具有重要的现实意义。 为了满足以上需求，本论文研究了已有的全文检索研究成果，并根据倒排索 引模型的原理，对p o s t g r c s q l 关系数据库的全文检索方法进行了深入的分析， 发现其在查询性能上有很大提升空间。通过对p o s t g r e s q l 全文检索索引结构和 检索流程的学习和研究，本文找到了其全文检索性能不佳的原因，同时提出一套 基于倒排索引的p o s t g r e s q l 数据库全文检索改进方案。这套方案主要包括倒排 索引结构的改造、索引的扫描方法等内容。 最后，根据对比测试结果，改进后的p o s t g r c s q l 全文检索性能有了很大提 升，它满足了全文检索和结构化检索的双重需求，证明了从内部改进开源关系数 据库，以达到课题目标的可行性。 关键字：全文检索；倒排索引；p o s t g r e s q l 北京川k 人学i ：学硕十学何论文 a b s t r a c t t h e s ey e a r s ，a sah o t s p o tt h er e s e a r c ho ff u l l - t e x ts e a r c hg e tal o to fn e w a c h i e v e m e n t sa n db r e a k t h r o u g h s i np a r t i c u l a r ，p e r f o r m a n c eo ft e x td a t a b a s eh a sb e e n g r e a t l yi n p r o v e d ，a n di tm e e t st h em o s tr e q u i r e m e n to ft h et e x tr e t r i e v a l h o w e v e r ，i t i st o oh a r dt om e e tr e q u i r e m e n to ft h ej o i n ti n q u i r i e so ff u l l t e x ts e a r c ha n ds t r u c t u r e d a t ar e t r i e v a lf o rm a n yt e x td a t a b a s e sw h i c hh a ss i n g l ef u n c t i o n o nt h eo t h e rh a n d ， e x c e p ts o m ee x p e n s i v ec o m m e r c i a lr d b m s ( o r a c l e ，d b 2 ，e t c ) ，o p e ns o u r c e r d b m sr e p r e s e n t e db yp o s t g r e s q lm a k ep o o rp e r f o r m a n c eo nf u l l t e x ts e a r c h s o t h a ti th a sg r e a ts i g n i f i c a n c et of i n dal o w - c o s ta p p r o a c h et om e e tt h ed o u b l e r e q u i r e m e n t so ff u l l t e x ts e a r c ha n ds t r u c t u r ed a t ar e t r i e v a l i no r d e rt om e e tt h er e q u i r e m e n t sa b o v e m e n t i o n e d ，t h i sp a p e rh a ss t u d i e dt h e r e s e a r c ha c h i e v e m e n to ff u l l t e x ts e a r c h ，a n dt h e na n a l y z e sp o s t g r e s q lf u l l t e x t s e a r c hm e t h o dw h i c hi sb a s e do ni n v e r t e di n d e x a f t e rt h i sa n a l y s i s ，w ef o u n dt h e r ei s ag r e a tr o o mo fi t si n q u e r yp e r f o r m a n c ei m p r o v m e n t w i t ha b o v el e a r n i n ga n d r e s e a r c ho fi n d e xs t r u c t u r ea n dr e t r i e v a lp r o c e s s e so fp o s t g r e s q lf u l l t e x ts e a r c h ，w e f o u n ds e v e r a lr e a s o n sf o ri t sp o o rp e r f o r m a n c e ，a n db r i n gf o r w a r dap r o g r a mw h i c hi s b a s e do ni n v e r t e di n d e xt oi m p r o v et h ep e r f o r m a c eo fp o s t g r e s q lf u l l - t e x ts e a r c h t h i sp r o g r a mi n c l u d e st h es t r u c t u r eo fi n v e r t e di n d e xt r a n s f o r m a t i o n ，s c a nm e t h o d a n ds oo n f i n a l l y ，a ss h o w e di nc o m p a r i s o nt e s t ，t h ep e r f o r m a n c eo fp o s t g r e s q lf t s h a s b e e n g r e a t l yi m p r o v e d t h ei m p r o v e dp o s t g r e s q l f t sm e e t st h ed o u b l e r e q u i r e m e n t so ff u l l t e x ts e a r c ha n dr e t r i e v a lo fs t r u c t u r ed a t a i t sa l s op r o v e dt h e f e a s i b i l i t yo fi n s i d e l yi m p r o v i n go p e ns o u r c er e l a t i o n a ld a t a b a s et om e e tt h ed o u b l e r e q u i r e m e n t s k e y w o r d s ：f u l l t e x ts e a r c h ；i n v e r ti n d e x ；p o s t g r e s q l i i 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他 人已经发表或撰写过的研究成果，也不包含为获得北京工业大学或其它教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示了谢意。 签名：燃日期：星q q 皇生互目 关于论文使用授权的说明 本人完全了解北京工业大学有关保留、使用学位论文的规定，即：学校有权 保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部 分内容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 签名：导师签名：垄盔日期： 至q q 旦生墨旦 第1 章绪论 第1 章绪论 1 1 研究背景、现状与意义 随着计算机产业的发展，以计算机设备为载体存储的电子信息愈来愈多，这 些信息大致可分为两类：结构化信息和非结构化信息。据统计，非结构化数据占 整个信息量的8 0 以上。在这些非结构化信息中，文本信息是一个主要的表现形 式。如何快捷有效地管理和检索文本这种非结构化数据成为一项紧迫的研究任 务，全文检索技术由此应运而生。全文检索技术的出现，导致了信息检索领域的 一场革命。它不仅可以实现情报检索的绝大部分功能，而且还能直接根据数据资 料的内容进行检索，实现了多角度、多侧面地综合利用信息资源。 全文检索是指以文本为检索对象，允许用户以自然语言根据资料内容( 例如 文献中的任何一个词语) 而不仅是外在特征( 诸如标题、作者、摘要、附录等) 来实现信息检索的手段，以实现支持多角度、多侧面地综合利用信息资源。全面、 准确和快速是衡量全文检索系统的关键指标。最初的全文检索是通过在文本中逐 个字符扫描匹配完成的，比如l i k e 操作，不需要全文索引这样的辅助数据。随 着文本集越来越大，人们对全文检索的需求越来越多样，这种顺序比较效率低下 的弊端就凸显出来。人们受到书目索引的启发提出了全文索引的思想，而本文研 究的倒排索引则是目前应用得最广泛的全文索引模型之一。 衡量文本检索系统的度量是有效性和效率。有效性是度量结果集的准确性， 经常用两个指标来度量：查准率和查全率。查准率定义为与查询相关的文档在所 有获取的文档当中所占的比例；查全率定义为所找到的相关文档在所有文档集中 所占的比例。效率用来度量获得结果集合的时间和空间代价。这可以通过标准的 算法复杂度分析来得到。当然也可以通过一些经验性的统计方法例如响应时间， 磁盘i o 等数据来得到。 由于传统关系数据库擅长于结构化数据的管理，其索引是关键字索引，而文 本是典型的非结构化数据，文本检索要求针对全文建立索引，并且往往还要求具 有相关度排序，高亮显示等附加功能。两者之间的巨大差异使得全文检索系统的 实现手段以及全文索引的结构与传统关系数据库不尽相同，因此人们想到了建立 一种全新的文本数据库模型，以应对日益增加的全文检索需求。 作为一种特殊的数据库系统，文本数据库要完成的工作仍然是传统数据库的 两大功能：存储和检索，具体而言就是文本数据的存储和任意字符串的检索。数 据库系统的两大功能中，检索更具有核心的地位，可以认为文本数据库研究的重 点是全文检索。 ：l 匕京州k 人学l ：t ；f ；：硕十学位论文 1 2 国内外研究现状 目前图内外对全文索引的研究主要集中在以下几个方面：全文索引的模型、 全文索引的时空效率、索引的更新效率和语义能力等等。新一代的全文检索系统 除了全文检索功能外，还应该具备语义匹配、文本挖掘这类对语义理解要求较高 的功能，而这些功能的完成也有利于全文索引。 1 2 1 全文索引模型 目前，比较流行的全文检索模型主要有：倒排表模型( i n v e r t e df i l e s ) 【l 】、署 名文件( s i g n a t u r ef i l e s ) 、位图( b i t m a p ) 、p a t 树【2 】和p a t 数组【3 】。前三种索引模 型从实质上讲，是同一基本观念的变体，即把文档看成索引项的集合，因此具有 同样的弱点：索引数据必须具有文档索引项结构，且只能实现简单的查询。p a t 树和p a t 数组将索引数据看成一组半无限串的叠加，避免了这个弱点。 目前，国内对全文检索模型的研究方兴未艾，2 相邻矩阵模型4 j 和互关联 后继树模型( i s t r e e ) 【6 】都是针对中文提出的全文检索模型。这两种模型都能够利 用索引生成原文，因而可以完全抛弃原文，节约存储空间。互关联后继树比其他 模型有着更加广泛的应用，除了用于全文检索，还可以应用在时间序列查询【7 8 】， 关联规则挖掘【9 】等许多方面。下面将一一讲述主流的全文索引模型。 ( 1 ) 倒排索引( i n v e r t e df i l e s ) 倒排索引是从书的目录索引中得到启发而创造出来的，它也是目前应用得最 广泛的全文检索模型。在倒排索引模型中( 见图1 1 ) ，索引由两部分组成：词 表和词出现过的文档列表，词表包含单词和指向文档列表的指针；文档列表中记 录了：d o c j 词语出现的文档号，n u m i 词语在d o c i 中出现的总次数， p o s l ， p o s 2 ，卜一词语在d o c i 文档中出现的具体位置。 w o r d l d o c l ，n u m l ， p o s l ，p o s 2 ，】) ，n o e 2 ，n u m 2 ， p o s w o r d 2 d o e l ，n u m i ， p o s l ，p o s 2 ，】) ， d o e 2 ，n u m 2 ， p o s w o r d n d o c l ，n u m l ， p o s l ，p o s 2 ，】 ， d o e 2 ，n u m 2 ， p o s 图1 - 1 倒排表模型结构 f i g u r e1 - 1s t r u c t u r eo f i n v e r ti n d e xm o d u l e 通过使用倒排索引，可以很快得知一个单词在哪些文档的哪些位置出现。对 于英文文档而言，词表中要去除一些经常出现但是意义不大的词，例如：t h e ，a ， a n 等等，这些词语被称为停止词，另外要对单词进行抽取词干的处理，例如：s i n g ， 第l 章绪论 s i n g e r ，s i n g i n g ，s i n g s 这些词都被看成是s i n g 。中文文档的处理要相对复杂一些， 因为中文没有明显的分隔符，所以在建立中文文档的倒排索引时要进行分词处 理。中文的倒排索引有基于字和基于词两种不同的索引( 见图1 2 ) 。 倒排索引可以实现多种查询：布尔查询，邻近查询，前缀查询等等。下面以 基于字的倒排索引为例说明倒排索引的查找过程。检索时，设查询字符串为 a l a 2 a n ，首先通过字列表定位各字符的索引数据，然后对数据进行分析：若 a l a 2 a i l 的索引数据中均含有文档t 的索引记录，在n 个关于文档t 的索引记录 中又含有p o s l ，p o s 2 ，p o s n ( p o s 是属于字符a i 的索引数据) ，且p o s i 和 p o s i + l ( 1 分析p o s t g r e s q l 在对长文本表进行o r d e rb y 时性能下降原因，并提 出了解决方案。 1 5 本文安排 论文的主要内容包括以下几个方面： 第一章，绪论。 该章概要介绍了本论文研究的背景和现状分析，并说明了论文的组织结构与 主要内容。 第二章，p o s t g r e s q l 全文检索方法介绍及性能分析。 该章介绍了p o s t g r e s q l 中进行全文检索的方法，并分析了其性能及不足 第三章，基于倒排索引的p o s t g r e s q l 全文检方法改进方案的设计与实现。 该章提出了基于倒排索引的p o s t g r e s q l 全文检索方法的改进设计方案，并 给出了具体的实现方法 第四章，改进方案的性能测试及效果分析。 该章对改进后的p o s t g r e s q l 全文检索方法进行了测试。 最后部分，结论 结论部分总结了本文的现实意义与技术进步，并概述了研究中还存在的问题 与未来工作的开展方向。 第2 章p o s t g r e s q i ，伞文检索方法介绍及件能分析 第2 章p o s t g r e s o l 全文检索方法介绍及性能分析 p o s t g r e s q l 是一个开源的对象关系数据库，它具有良好的可扩展性、面向 对象性等优点。p o s t g r e s q l 还是一个严肃性很强的数据库，并且包含很多高级 特性，很多性能可以和o r a c l e 等相媲美。我们选择p o s t g r e s q l 为研究对象，主 要由于它严谨的实现了关系数据库的各项概念，是一个关系数据库的良好范例。 另外，p o s t g r e s q l 中已经实现了一个相对简单的全文检索子系统，而我们的课 题研究和性能改进将主要在这个子系统上进行。 2 1p o s t g r e s o l 全文检索概况 2 1 1p o s t g r e s o l 简介 p o s t g r e s q l 是由1 9 8 6 年美国加州大学伯克利分校( b e r k e l e y ) 开发的p o s t g r e s 软件包演变而来的，是一个面向公众的、开放源代码的对象关系数据库管理系统 ( o r d b m s ) 。p o s t g r e s q l 是最富特色的自由数据库管理系统，它的特性覆盖了 s q l 2 和s q l 3 。它具有如下特性【1 9 】： 支持丰富的数据类型：支持传统的数字、字符、日期等类型，并且还支持点、 线、多边形等几何类型和口类型，此外允许用户自定义数据类型。为了支 持存储超大文本和视频等数据，提供大对象类型( b l o b ，b i n a r yl a r g e o b j e c t ) 。 面向对象特性：支持类和多继承，不仅仅支持属性数据的继承，还支持函数 及过程的继承。如用户创建一个表时，只需要从一个已存在的表中继承一些 属性，然后加入一些新的属性。 强大的功能：支持事务、子查询、多版本并发控制等特性；支持触发器、缺 省( 值) 和约束等数据完整性检查特性；通过p h p 3 和p e r l 与w e b 紧密集成， 支持客户服务器应用；丰富的接口支持，如o d b c ，j d b c ，p y t h o n ，p e r l ， t c l ，c c + + ，e s q l 等；在数据规模比较大时仍能保持良好的性能。 2 1 。2p o s t g r e s o lf t s ( f ul i - t e x ts e a r c h ) 全文检索子系统 假设有下面的一个表：一组纯文本文档的内容驻留在d o c u m e n t 表的t e x t 列 中，同时该表中还包含t i t l e 、s i z e 和d o c a u t h o r 列。可能发出以下查询： 北京州k 人学i ：学硕十学位论文 s e l e c td o c u m e n t t 1 t l e ，d o c u m e n t s 1 z e ， d o c u m e n t d o c a u t h o r ，w r i t e r s c i 七i z e n s h i p f r o md o c u m e n t ，w r i t e r s w h e r et e x t p l a i n t o t s q u e r y ( q u e r yt e x t ) ； 发出此查询是为了获取所有满足下列条件的文档的名称、作者和大小：文档 中包含短语“q u e r y 和单词“t e x t ，而且二者在文档中的位置互邻。此信息同 w r i t e r s 表联接可获得作者的国籍。 在上述查询中，p o s t g r e s q l 数据库会调用它的全文检索模块p o s t g r e s q l f t s ，实现数据库管理系统和全文检索服务无缝连接，进行全文检索的操作。 p o s t g r e s q lf t s 由一个t s e a r c h ( 一个p o s t g r e s q l 的全文检索扩展) 发展而 来。t s e a r c h 2 是在p o s t g r e s q l 8 3 发布时，集成到了p o s t g r e s q l 中，形成了现在 的p o s t g r e s q lf t s 。它主要提供了以下全文检索功能： 提供了两种适合进行全文检索的索引，分别为g i s t 、g i n 。这两种基本能满 足大多数全文检索的索引需求； 提供了可扩展的分词字典； 提供了检索索引的一整套方案。l l 妻o - 定义了语义类型( t s v e c t o r ) 、搜索语 句类型( t s q u e r y ) 、搜索操作符( ) 等； 提供相关性排序功能，以及字段权重标注。 p o s t g r e s q lf t s 可以实现对t e x t 类型以及v a r c h a r 类型建立全文索引，满足 用户的简单需求，但是它离用户全文检索的需求相差甚远。下面将对p o s t g r e s q l f t s 的性能和缺陷作进一步的分析。 2 2p o s t g r e s o l 中的全文索引结构 2 2 1 常用倒排索引存储模型 文本集的动态性包含两个层次：文字的有序排列组成的文本，称为文字层次； 文本的无序集合构成的文本集，称为文本层次。因此文本集的动态调整可能在两 个层面上进行，但是由于文本内部文字的动态变化粒度太细，倒排索引要保持同 步调整的时间代价太大，而且，文字层次的动态调整可以转换成文本层次的动态 调整，用两次文本层次的调整代替文字调整，即对一个文本作文字改动视为删除 旧文本和增加新文本，因此一般只考虑文本层次的索引动态同步调整。文本层次 的变动也只考虑两个：增加和删除。 在关系数据库中，这两个操作被视为对称互逆操作，单位都是可以直接寻址 的单个元组，对b 树索引更新的处理原理也基本相同。与关系数据库不同，文 本集的增加和删除并非对称的，文本集增减的单位是文本，而一个文本包含的索 第2 章p o s t g r e s q l 全文榆索方法介绍 及性能分析 引数据无规律地分布在倒排索引中，因此删除一个文本时要扫描整个倒排索引并 逐个删除索引数据。为减少开销，往往对文本删除采取推迟更新、批量化调整索 引的策略。有鉴于此，目前有关动态算法的文章大多只讨论增加操作的处理。同 倒排索引的索引数据一样，构成倒排索引的单词表也必须允许扩充，因为新文本 可能包含全新的单词。对倒排索引动态性的研究与其说是算法的研究，不如说是 数据结构的研究，经典动态数据结构大多是基于树实现的，一般有二种：平衡二 叉树、b 树、键树。以这二种结构为基础，可以得到多种变种结构。此外，还有 基于散列函数的实现方法。 b 树堆存储模型 基于文件的b 树能够实现高效的插入、查找、删除等操作，所以这种数据 结构经常被用来实现大型的动态更新的倒排索引。 c u t t i n g 和p c d c r s c n 3 4 】根据z i p f sl a w t 3 5 】提出了若干种时空优化的方法来利 用b 一树和堆文件管理倒排文本索引。具体做法如下： 对于每一个索引的词汇，c u t t i n g 和p e d e r s c n 利用了一个b 树来存储较短的 文档列表。当列表较长的时候( 例如多于1 6 项) ，那么这个文档列表的一部分将 被分裂出来，在一个单独的堆文件( h e a pf i l e ) 中存储。堆是在列表过长的时候根 据需要而分配出来的一整块连续的内存空间所存储的二进制文件。当列表过长的 时候，每块独立分配的堆利用指针关联起来( 如图2 2 所示) 。b 树堆存储模型 需要相应的对堆进行管理的软件来分配、释放内存。 1 2 0 l x 8 0 卿6 0 磬4 0 2 0 o 一7 一 一 ? ， 一l l l f j 。一 1 01 0 01 0 0 01 0 0 0 01 0 0 0 0 01 o o e + 0 6 倒排列表( 记录) 的人小( 字节) 图2 1 某文档集中倒排列表的大小分布情况 f i g u r e2 - ld i s t r i b u t i o no ft h es i z eo fo n ei n v e r ti n d e x + 记录大小 文件大小 a 2 芝：昌囊竺= 置_ 卫聃t i n g s l i s t 小昌牡哂g s l i s f l 图2 - 2c u t t i n g 和p e d e r s e n 的b 树堆存储方案 f i g u r e2 - 2b - t r e e - h e a ps t o r em e t h o dd e s i g n e db yc u t t i n ga n dp e d e r s e n 该存储模型具有如下不足之处： 对于b 树的插入和删除，尤其是变长记录的插入和删除经常会是很复杂的 并且也难以调试。 每次查找倒排列表都需要从b 树的根结点遍历到叶子结点，因此增加了查 找的时间；并且该模型还需要相应的对堆进行管理的软件，实现起来很复 杂。 d u a l s t r u c t u r e 索引模型 t o m a s i c 和g a r c i a m o l i n a 等人【3 2 】提出了一种d u a l s t r u c t u r e 索引结构，它动 态地区分长、短倒排列表，并对长、短列表采用两种不同的存储结构及配套的检 索、更新策略。之所以区别对待长短列表也是基于z i p f sl a w 3 5 j 。 其一是针对短倒排列表的，某词通过静态散列函数映射到桶里，一个桶可以 装多个倒排列表，桶数是固定的，且每个桶都只有一个存储块。每个词的倒排列 表初始都是短倒排列表，当某个桶溢出时，将桶中最长的倒排列表晋升为长倒排 列表，在字典表中做上标记后，将它迁移到长倒排列表使用的存储结构中。这样 就动态地实现了长、短倒排列表的区分。另一种是将长倒排列表放在变长的连续 块中，且末尾预留一部分空闲空间，这些块不让其他词的倒排列表共享。对于给 定的词，可以通过查单词表来判定它是否对应一长倒排列表。 l u c e n e 的s e g m e n t s 模型 有关l u c e n e 的介绍在第一章已经提及，本小节将讲述l u c e n e 的索引文件存 储模式。在l u c e n e 中，索引并不是存储在一个大的索引文件中的，而是存放在 多个小的索引文件中( s e g m e n t s ) ( 图2 3 ) ，每一个s e g m e n t 中包含多个文档 的全文索引。这样的结构适合增量更新。每当有新的文档加入索引时，并不是把 新的文档加入到全文索引中，而是先在内存中生成内存索引，当内存索引中的文 档达到一定数量时，再将索引合并到磁盘中去。同时由于l u c e n e 支持内存索引的 检索，因此这样的结构适合动态文本集全文索引的存储。但是，该存储结构的查 询效率不高，因为每个查询要查找多个小的索引文件，然后对子结果集运算，才 1 4 第2 章p o s t g r e s q ! 伞文检索方法介纠及性能分析 能得到最终的结果。 7 l ! 竺b 、r i 一 f i e 刁l d 2 羹陋t e r m , i 墨；、匹t e r m 2 _ l d o c u m e n t i | e ；f i e l d l 图2 - 3l u c e n e 索引文件结构 f i g u r e 2 3i n v e r ti n d e xs t r u c t u r eo fl u c e n e 2 2 2p o s t g r e s o lf t s 中的索引结构 通用检索树g i s t g i s t ( g e n e r a l i z e ds e a r c ht r e 卜通用检索树) 是一种平衡的，树状结构的 访问方法，在系统中起一个基础的模版，然后可以使用它实现任意索引模式。 g i s t 的树结点是键p a i r ( p ，k e y ) 。如果树结点不是叶结点，则p 指向一个孩子结 点；如果是叶子结点，则p 有一指针指向数据库中对应的元组。其中的k e y 代表 能否从数据库中取到对应的元组。例如：在r t r e e s 中k e y 代表的是二维的矩形。 b + t r e e s ，r - t r e e s 和许多其它的索引模式都可以用g i s t 实现。g i s t 的一个优点 是它允许用户自定义的数据类型和合适的访问方法一起开发。g i s t 在许多模块 中都有着应用：c u b e 用于多维立方体的索引；i n t a r r a y 用于一维i n t 4 数组值的 r d t r e e ；l t r e e 用于树状结构的索引等等，这些都在p o s t g r e s q l 的c o n t r i b 文件 夹下。 随着社会的信息化，声音、图片、文本等无结构数据大量出现，虽然这类数 据主要存储在文件系统中，但是由于p o s t g r e s q l 具有丰富的数据类型，并且支 持大对象存储，很多p o s t g r e s q l 用户采取将它们存储在数据库中基于字符的列 ( 如v a r c h a r 和t e x t ) 中的管理方式。这意味着p o s t g r e s q l 数据库的用户需要一 种有效地从数据库中检索文本数据的机制。自从p o s t g r e s q l 7 4 版本开始， t s e a r c h 2 ( 一个p o s t g r e s q l 的全文检索扩展) 就被作为和数据库紧密集成的文 本检索引擎扩展，可以对数据库中的文本( t e x t ) 等类型建立索引。 g i s t 在t s e a r c h 2 中被扩展成s 一树( s i g n a t u r et r e e ) ，类似于署名文件。所以在 t s e a r c h 2 里使用的索引模式既不是基于b 树，也不是基于h a s h 结构的。s 树是 蓦尹 嚣手 北京l ：、i p 人学i ：学硕 等：化论文 平衡结构，所有的叶子结点在同一层。每个结点都有数个键( p a i r s ) ，每一个键包 含一个s i g n a t u r e 和指向孩子结点的指针。s 树包含两个整型的参数( k 和k ) 。 根结点可以容纳2 至k 个键，而其他结点至少容纳k 个，至多容纳k 个结点。 不像b 树中k = k 2 ，s 树里l = k = i ( 2 。对于n 个s i g n a t u r e s 的高度最多是h - l o g k n 1 。内部结点的s i g n a t u r e s 的生成是这样的：在它的孩子结点的s i g n a t u r e s 上s u p e r i m p o s i n g ( o r i n g ) i 而成的。这里s i g n a t u r e 是一个f 位的b i t s t r i n g ，f 是值 s i g n a t u r e 的长度。一个s i g n a t u r e 代表了集合早的一个元素，例如在t s e a r c h 2 里 的s i g n a t u r e 是由一个t s v e c t o r 散列而成的。设计h a s h 函数时要注意的是：在 1 f 的范围里，每一个位置都能平衡分布。图2 - 4 显示了一个s 一树的例子： 、1 0 0 0 00 0 ；1 0 0 0 00 1 0 0 00 0 0 0 l 1 0 0 0 00 1 0 0 00 0 0 1 0 1 0 0 0 00 1 0 0 00 1 0 0 0 图2 _ 4 一个s i g n a t u r et r e e 的具体例子，参数是k = 4 ，k = 2 f i g u r e2 - 4o l l ee x a m p l eo fs i g n a t u r et r e e ，k = 4 ，k = 2 在t s e a r c h 2 的树结构里，一个叶子结点直接代表一篇文档( 也就是一个经 过哈希函数散y 0 过后的t s v e c t o r 类型) ，父结点是某些文档的集合。并且 一个文档( t s v e c t o r 类型) 是经过哈希函数压缩后存放到树里的。 这种树结构的索引可以实现对t e x t 类型以及v a r c h a r 类型实现全文索引。在 t s e a r c h 被集成到p o s t g r e s q l 中后，f t s 继承了这种索引结构。它已经可以满足 用户的简单需求。但是在使用这种索引时，采用的文档压缩方式为有损压缩。比 如，两个词在被散列后值相同，那么他们会将同一位置为一，这将导致在查询时， 不能确定这两个词是否出现在文档中。所以这种索引的查询准确率，将随着数据 量的增长而降低。因此它并不适合作为大数据量的全文索引。 通用倒排索引g i n g i n ( g e n e r a l i z e di n v e r ti n d e x 通用倒排索7 1 ) 。如图2 5 所示，g i n 的结构 与b 树堆存储模型有些相似，它了建立了一棵平衡树( e n t r y 树) 来保存每个在 被索引的字段中出现过的词汇。但这棵平衡树并不是b + 树，它基本上是与g i s t 结构相似的一棵平衡树。 g i n 的树结点也是键p a i r ( p ，k e y ) 的数组。k e y 为被索引的词。当某个e n t r y 第2 章p o s t g r e s q l 全文检索冉法介智 及性能分析 树的结点不是叶结点时，p 指向一个孩子结点；如果是它叶子结点，则p 指向一 个p o s t i n g l i s t 。在这个p o s t i n g l i s t 中保存了包含所有包含词k e y 文档的元组i d 列表。当某词的p o s t i n gl i s t 较短时，它将以列表( l i s t ) 的形式存在。但是当 p o 时m gl i s t 的大小增长0 一定程度后系统会改用b + 树存储。如图2 - 5 中所示， a a a 的p o s t m g l i s t 为一颗树，这棵树是根据r i d ( 元组i d ) 建立的一颗b + 树，t i d 是一个指向存放文档元组位置的标识。它是每个元组标识自己的的唯一i d 。它 的结构定义如下： t y p e ds t r u c ti t e m p o i n t e r d a t a b l o c k i d d a t ai pb l k i d ； 块号 o f f s e t n u m b e ri p _ p o s i d ；项号一元组在块中的偏移盘 i t e m p o i n t e r d a t a ； 幽2 + 5 g 刑结构 h g u m 2 - 5s t u t c m r eo f g i n t i d 有两部分组成，块号和项号。块( b l o c k ) 为p o s t d e s q l 中i o 和存储的 基本单位。在图2 - 5 中，元组i d 以( 块号：项号) 的方式表示，如1 4 ：1 7 。 经实验证明，g i n 相对于g i s t 有着更好的查询效率和准确率。但是g i a 是 简单的布尔索引，索引结构中并没有保存词频、词位等计算相关性的信息只能 返回是否匹配。当全文检索查询需要对返刚结果进行相关性排序时，就必须对所 检索的文档进行扫描。这会极大的影响检索效率。2 3 将对基于g i n 的全文检索 北京f 、人学f 。学硕十学位论文 方法进行介绍。 2 3 基于g ln 的相关性排序性能及缺陷分析 如自仃文所述，g i s t 在建立的时候，将会对文档进行有损压缩，当数据量很 大的时候，全文检索的准确率不能令人满意。所以本文将g i n 作为分析和改造对 象。 在p o s t g r e s q l 中，当所查询的字段建有g i n 索引时，系统将进行全文检索。 根据官方测试结果，在只需要检索出包含检索词的文档的测试中，基于g i n 的全 文检索效率有了很大提高，相对没有建立索引的字段，使用g i n 的检索效率大约 提高了两个数量级。但是在全文检索的时，人们不仅只想通过检索系统得到包含 了检索词的文档集合，常常还希望结果集是有序的，并且排在结果集最前面的是 与检索词最相关的文档。这种信息检索系统返回结果的排序被称为“相关排序” ( r e l e v a n c er a n k i n g ) 。在全文检索中，人们也这么讲，但内涵其实是有了差别。 一方面，现代全文检索系统维护的内容十分繁杂且不规范，不像传统的图书、文 献等有很好的分类体系管理。另一方面，现代全文检索系统面对的用户背景广阔， 层次多样，不像传统的图书馆所面对的用户通常有相对比较整齐的用户群。因此， 现代全文检索系统要给出的不是一个狭义的相关序，而是某种反映多种因素的综 合统计优先序。检索质量评估的目标是对不同全文检索系统的检索质量评估其相 对优劣次序 给定某个文档集合d ，大小为m 设两篇文档d l ，d 2 任d ，个查询q 。用 什么样的标准来讲“d l 与d 2 相比，前者和q 更相关 ? 这方面最经典、最有影 响的工作是g e r a l ds a l t o n 等在3 0 多年前提出的“向量空间模型( v e c t o rs p a c e m o d e l ， v s m ) s a l t o n a n d l e s k ，1 9 6 8 ，s a l t o n ，1 9 7 1 】。该模型的基础是如下假 设：文档d 和查询q 的相关性可以由它们包含的共有词汇情况来刻画。 这样，文档d 和查询q 就都被简化成词汇的集合( 多重集) 。不失一般性，令 = 2 川 ( 2 - 1 ) 为一个词典，为词项，n 为它的规模，则： d = 妒，鬈2 ，扎，羚 ( 2 2 ) q = 1 8 一 ( 2 3 ) 第2 章p o s t g r e s o l 全文榆索方法介绍及性能分析 其中，吩，i = 1 ，2 ，n ，表示相应词项出现的次数，即词频t f ； 如果次数为零，则表示该词项在文档或查询中没有出现。在实际应用中，人们通 常去掉，直接用m i 和协，来表示d 和q 。 d 和q 相关程度的评价就以这样两个向量的某种“相近程度 为基础，这其 中，有一些细节的变化。 1 ) 上述表示中，词项在文档和查询中出现的次数( 词频) 是一个基本量，我们 称为“词频”模型。在实用中用规格化表示( 以一篇文档为例) 。 扛 w l ，帅吲，嵋= 最 一i(2-4) 查询q 也有同样的表达形式。这里，掉w 也称为词频，称这种方式为用词 频来表示项在文档或查询中的权重。 2 ) 在许多情况下，为了简便起见碍，只在集合 0 ，1 ) 中取值，表示词项 的出现与否，不关心其次数：此时的模型称为“二元模型”。 3 ) 假设一个词项，在某文档内部出现的频度很高，并且同时它在许多文档 中都有出现( 例如“我们 ，“大家”等) ，这样这个词项对于不同文档的区分能 力就不会很强，因此它的权重应该相对较小。将这种观念刻画出来，引入词项的 文档频率d f 的概念。用吃表示词项在文档集合d 中涉及的文档个数，m 是集 合d 的大小，则文档频率为 纱协 陋5 ， 我们需要的是和d f 成反比的一个量，称之为倒置文档频率i d f ，常用的一 种定义为 毗) - l 。g 协6 ， 这样结合词频，就有了经典的t f * i d f 词项权重 例嗍= 轰灿g 陪7 ， 给定某种权重的定量设计，求文档和查询的相关性就变成了求d 和q 向量的 某种距离，最常用的是余弦( c o s ) 距离 北京州k 人学l ：学硕十学位论艾 c o s 沪皆 p 8 ， 上述这些理论，源于传统信息检索领域，主要针对的是普通文本。这样一种 理论虽然从根本上看起来比较粗糙，但几十年来在大量真实语料评估的驱动下， 其不断完善的实现在实践中得到普遍认可。 p o s t g r e s q lf t s 也提供了相关性排序的功能。但是如果用户希望检索结果是 根据相关性进行排序的，那么需要遵循p o s t g r e s q l 的一些使用条件。首先，在 检索时需要使用o r d e rb y 在s q l 语句中明确注明需要排序字段；其次，只有 被声明为t s v e c t o r 类型的字段才能进行相关性排序。t s v e c t o r 是p o s t g r e s q l 为支 持全文检索而定义的数据类型。一个t s v e c t o r 的值是唯一分词的分类列表，它把 一句话格式化为不同的词条，在进行分词处理的时候t s v e c t o r 会自动去掉分词中 重复的词条，按照一定的顺序装入。经过处理后的t s v e c t o r 形式如下： 一s e l e c tt o t s v e c t o r ( e n g l i s h7，7a f a tc a ts a