《数据库中基于多索引段的全文索引研究》由会员分享，可在线阅读，更多相关《数据库中基于多索引段的全文索引研究（52页珍藏版）》请在金锄头文库上搜索。
1、华中科技大学 硕士学位论文 数据库中基于多索引段的全文索引研究 姓名：漆团 申请学位级别：硕士 专业：计算机软件与理论 指导教师：王元珍 2011-01-19 I 摘摘 要要 随着电子图书馆，企业办公自动化，互联网的发展，数据库管理系统DBMS中已 积累大量的非结构化数据。采用在DBMS的外部建立索引的方法很难保证DBMS中的 数据与索引的一致性，不适合对性能或者灵活性要求较高的应用。将全文索引与 DBMS有机的结合起来是数据库信息检索整合（DB-IR Integration, DB-IR）领域 目前讨论的一种主流方法。 为了能够快速地检索海量的非结构化数据，需要用到信息检索（Informat
2、ion Retrieval, IR）领域的全文索引技术。尽管有多种数据结构可以用于实现全文索引，但 是目前的主流是使用倒排索引。已有的讨论有机结合方式的论文，使用的是基于单倒 排索引段的索引，存在性能低下的问题。针对这一不足，提出在DBMS中使用基于多 倒排索引段的全文索引，来提高建立索引和查询索引的性能。根据数据库自身环境的 特性改进索引段结构。将数据源表的关键字和关键字的大小序号，直接存储在倒排索 引单词的倒排表中，并使用位图存储删除信息。索引段结构的改进可以进一步提高全 文索引上的查询和删除操作的性能。通过实验验证，相对于已有的DBMS中的全文索 引，DBMS中的基于多倒排索引段的全文索
3、引，在建立和查询索引方面具有性能上的 优势。 并讨论如何使用B+-Tree这一DBMS中常用的数据结构来实现基于多倒排索引段 的全文索引。最后，设计出一套并发控制和日志恢复机制，来解决如何保证索引相关 事务ACID特性的问题。 关键词：关键词：数据库信息检索整合，全文索引，倒排索引，事务特性 II Abstract With the development of the electronic library, business office automation and Internet, a large amount of unstructured data has been accumul
4、ated in DBMS(Data Base Management System). Its very difficult to ensure the consistency of the data and its full-text index, if the index is outside DBMS. So index built outside DBMS isnt suitable for those applications that are sensitive to performance or flexibility. To combine the data and its in
5、dex organicly is discussed in Database-Information Retrieval Integration (DB-IR Integration) field in a mainstream way. In order to retrieve vast amounts of unstructured data quickly, we need to use the full-text index technology from Information Retrieval (IR) domain. Although many data structures
6、can be used to implement full-text index, now the mainstream is to use the inverted index. The performance of index based on single-segment index, used in existing articles on organic combination, is not very well. Full-text index implemented by multi-segments index(one or more inverted indexes) is
7、proposed by this article to improve the performance of building, updating and querying. Improvements on index segment structure, key of source table and the sequence number of key stored in word list of index segment and deleting information stored in bit vector, are also introduced to enhance the p
8、erformance of querying and deleting on index. A performance advantage, in both indexing and querying, of the full-text index proposed by this article, over the existing DBMS in the full-text index, has been verified by an experiment. And how to implement the multi-segments index by B+-Tree, a widely
9、 used data structure in DBMS, is also discussed. In the end of this article, a concurrency control and recovery mechanism is designed to ensure the ACID properties of muti-segments index related transations. Key words: DB-IR, full-text index, inverted index, ACID 独创性声明独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的
10、研究工作及取得的 研究成果。尽我所知，除文中已经标明引用的内容外，本论文不包含任何其他个人 或集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体，均已 在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。 学位论文作者签名： 日期： 年 月 日 学位论文版权使用授权书学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校有权 保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借 阅。本人授权华中科技大学可以将本学位论文的全部或部分内容编入有关数据库进 行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。
11、保密 ，在_年解密后适用本授权书。 本论文属于 不保密。 （请在以上方框内打“” ） 学位论文作者签名： 指导教师签名： 日期： 年 月 日 日期： 年 月 日 1 华 中 科 技 大 学 硕 士 学 位 论 文 1 绪论绪论 1.1 课题背景 1.1 课题背景 数据库管理系统DBMS对数据的管理提供了很好的共享性，独立性，安全性。 用户可以利用DBMS的基于事务的并发处理机制来统一管理这些数据。 随着数字图书馆，企业电子化办公，互联网的发展，这些领域用户的DBMS 中积累了海量的半结构，无结构类型的数据。但是通过使用传统DBMS中的基于 精确匹配的方式，对这些数据进行查询，很难获得理想的效果
12、。 为了处理海量无结构和半结构化的数据，信息检索领域发展出了一系列的技 术和理论，包括各种文本压缩，全文索引和基于概率统计模型的查询结果排序。 因此，希望可以利用，从信息检索领域发展出来的理论和技术，来处理DBMS中 的无结构和半结构类型数据。 在利用信息检索领域(Information Retrieval, IR)中的理论和技术处理数据的同 时，又可以利用DBMS管理数据的需求，促使了数据库信息检索整合（DB-IR Integration, DB-IR）研究领域的产生。也促使了众多商业数据库厂商在自己的 DBMS产品中加入全文检索技术。 全文检索技术通过对数据库中大量的非结构化数据建立全文索
13、引，使得基于 关键字的查询可以迅速完成。本文提出的基于多索引段的全文索引，采用从内部 与DBMS结合的方式（1.2.2小节介绍的第四种方式） ，可以保证全文索引相关事务 的ACID特性。在保证ACID特性的提前下，本文提出的全文索引采用划分多索引 段的方法，来建立和更新索引。另外，根据数据库自身的特点，本文提出的全文 索引，在倒排索引的结构上也有所改进。相对于已有的DBMS中的全文索引，本 文提出的全文索引，在建立索引、更新索引和查询索引方面，在性能上有了较大 提升。 本课题来源于国家“核高基”重大专项，基础软件产品方向，课题5-1：大型 通用数据库管理系统与套件研发及产业化，对达梦数据库管理
14、系统6.0中的全文索 引性能的改进需求。改进的目的是解决，全文索引功能存在建立索引的速度慢， 无法真正增量更新，以及无法保证全文索引相关事务ACID特性的问题。 2 华 中 科 技 大 学 硕 士 学 位 论 文 1.2 国内外研究概况 1.2 国内外研究概况 IR 领域的研究成果是 DB-IR 的重要理论基础。 并且本文提出的 DBMS 中的全 文索引在性能上的改进，也是以 IR 中的全文索引理论为基础。1.2.1 小节将详细 介绍 IR 研究领域中，全文索引的建立和更新方面的研究概况。 本文提出 DBMS 中的全文索引是在 DBMS 内部实现的，可以与 DBMS 有机 地结合。1.2.2
15、小节将对 DBMS 与全文索引结合的几种方式进行介绍。 1.2.3 小节将介绍已有的 DBMS 中的全文索引。 1.2.1 全文索引研究概况全文索引研究概况 全文索引的实现主要有三种数据结构：签名文件1、位图2和倒排索引3,4。 目前一般使用倒排索引来实现全文索引，完成全文检索功能。因此本文后面提到 的全文索引都是基于倒排索引的。 本小节先介绍建立全文索引的方法，再讨介绍更新全文索引的方法。 全文索引的建立，主要包括三种方法：基于内存的倒排5,6、基于排序的倒排 4,6和基于合并的倒排7。文献8中对这几种建立索引的方法进行了比较。基于内 存的倒排和基于排序的倒排，在建立索引的过程中需要维护内存
16、中的字典。所以 这两种方法所能处理的文档集的规模，受限于内存的大小。基于合并的倒排，在 建立索引的过程中，将较小的索引段合并成较大的索引段。此方法建立索引的过 程，实际上是合并索引段的过程。但是此方法不需要在内存中，维护一个字典。 因此，此方法所能处理的文档集规模，不会受到内存大小的限制。 全文索引的更新，主要包括：重建索引、合并更新、原地增量更新和基于划 分多索引段的更新9四种。重建索引的代价较大，适合文档集合规模较小的情况。 合并更新需要扫描整个索引，每次更新的代价较大。在原地增量更新的过程中， 磁头需要随机移动。并且此种方法所建立索引的空间不够连续。基于划分多索引 段的更新会选择多个索引段的一部分进行合并，适合在线更新的情
