一种由B+树实现的倒排索引
开篇：润墨网以专业的文秘视角，为您筛选了一篇一种由B+树实现的倒排索引范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！
摘要：索引作为整个数据检索系统的重要组成部分，一直是人们研究的热点。倒排索引结构以其快的查询速度、高的查询效率得到青睐。而B+树作为一种成熟的数据结构，是创建索引的首选。该文提出了一种由b+树实现的倒排索引结构，结合了B+树与倒排索引的优点，查询速度快、效率高，在数据挖掘以及数据查询等方面应用广泛。
关键词：倒排索引；正向索引；B+树；数据查询
中图分类号：TP391文献标识码：A文章编号：1009-3044(2011)08-1720-03
An Algorithm Based on N-gram String Segmentation
LI Wen, HONG Qin, TENG Zhong-jian, SHI Zhao-ying
(School of Physics and Optoelectronics Technology of Fujian Normal University Campus Cangshan, Fuzhou 350007, China)
Abstract: Index, as an important part of data query system, has been one of the hot spots. Inverted index structure is popular for its fast speed and high efficiency. The B+ tree isa mature structure, which is often used on establishing indexes. In our paper, we present an algorithm to achieve inverted index by B+ tree structure. It combines the advantages of inverted index and the B+ tree, and has high query speed and efficiency. It will be widely used in data cloning and data query.
Key words: inverted index; forward index; B+ tree; data query
索引在整个数据检索系统中是很重要的组成部分，是实现信息检索的主要渠道[1]。数据的查询是使用最频繁的一种数据操作，当数据库中的数据比较庞大的时候，数据查询的效率就会成为用户最关心的问题[2]。因此，所创建索引的效率将直接影响整个搜索的快慢，因此，选择一种合适的、高效的索引是实现高速搜索的关键。
1 倒排索引
目前，对于索引这一研究领域来说，索引策略中索引的组织方法有两类：即正向索引和倒排索引，在信息检索系统中，每个文件被分配在索引数据库中的文档ID号会作为该文档标志的唯一号码，通过该ID号来区分不同的文档。如图1所示，为倒排索引的结构图。
倒排索引是以词或字符串作为关键字，对每种关键字都设立一个索引，每个关键字对应一个索引项，将具有相同关键字值的记录ID都保存在与之对应的索引项中。在进行信息检索时，通过主关键字或次关键字都可以找到文件中的各个记录。因此，使用倒排表作索引的好处在于检索记录较快， 它对于任何复杂的布尔询问，均只需访问一次满足询问的记录，就能获得肯定或否定的回答[3]。
如图2所示，为一个小的数据集的2-grams倒排列表。
2 B+树的索引实现
B+树是数据库中常用的索引机制，是一种一维数据索引结构设计[4]。由于这种数据结构高效、易变、平衡和独立于硬件结构的优点而在数据库系统中得到广泛的应用，成为应用较为广泛的索引结构。
2.1 B+树的定义
B+树的定义[5]：一棵m阶的B+的叶子节点与根节点都必须满足一定的条件，保证树的平衡。如图3所示，为m=3的一棵由上述分割的字符串片段构成的B+树。
2.2 基于B+树实现的倒排索引
2.2.1 B+树倒排索引的查询
B+树是一种平衡树，因此，查询效率较高。通常，B+树的查询有两种方法：一种是从上至下即从根节点至叶子节点的随机查询方法，另一种是顺序查询方法[6]。在本文中，我们采用的是第一种方法。查询过程的代码描述如下所示：
BTree_SearchNode( )
{
memcpy(); 申请索引需要的空间；
SearchUserInfo.FileIndex = -1; //定义找不到为－1
if 头指针为空 printf 查找失败 ;
else
{
case 当前B+树结点小于索引的字符串:
if当前B+树结点没有向后结点return 则返回找不到;
else当前B+树结点有向后结点，则向后查找;
case 当前B+树结点等于索引的字符串:
if 当前B+树结点没有向下结点
则返回该结点就是我们要查找的结点
else当前B+树结点有向下结点，则向下查找；
case 当前B+树结点大于索引的字符串:
当前B+树结点没有向下结点，则返回没有找到；
}
}
2.2.2 B+树倒排索引的插入
B+树是著名的B树的变体，其各个叶节点之间相互联系，以增强搜索的性能[7]。根据B+树的定义中，我们可以得知，B+树的非根节点的关键字个数必须不能小于m/2。插入操作按照以下规律进行：先在B+树最底层的非叶子节点添加一个关键字，如果该节点所包含的关键字个数不超过m，插入成功；反之，则需要对该节点进行分裂。分裂后的两个新的节点所包含的关键字个数应满足左节点不小于(m+1)/2(向下取整),右节点不小于(m+1)/2(向上取整)。若该节点的双亲节点有足够的空间，则该双亲节点应包含这两个子节点的最大关键字。否则，则对父节点进行分裂，并在父节点的上一层加入新的关键字，依次向高层推进，直至产生新的根节点，使得B+树的层次增加一层。下面为本文中所提出的B+树索引插入操作的算法实现描述：
BTree_AddNode //添加一个新的索引项
{
case 当前的B+树枝干结点的字符串小于索引字符串:
ifB+树没有向后节点
if B+树没有向下结点 search();
elseB+树有向下结点 add_node();
elsesearch();
case当前的B+树枝干结点的字符串等于索引字符串:
if 当前B+树结点没有向下结点return TRUE;
else search();
case当前的B+树枝干结点的字符串大于索引字符串:
if当前B+树结点没有向后结点
{ If 当前B+树结点没有向下结点 return TRUE;
elseadd_node(pCurIndexInfo); }
else search();
}
2.2.3 B+树倒排索引的删除
从B+树中删除，不单只是删除一个关键字，还要删除该关键字所对应键-指针对[8]。要删除B+树索引中的一个关键字，首先通过搜索找到它，然后执行删除操作。当然，由于B+树的节点个数有一定的限制，如果删除了该节点之后导致节点个数无法满足条件，则需要对节点进行合并操作。从图3所示的B+树中删除ic这个键值的结果如图4所示。
本文所实现的删除函数的伪代码如下：
BTree_DelNode( )
{
case 当前的B+树结点小于索引的字符串:
if (当前B+树结点没有向后结点) return;
elsesearch();
case 当前的B+树结点等于索引的字符串:
if (当前B+树结点没有向下结点) delete();
else search();
case 当前B+树结点大于索引的字符串:
return;
}
3 实验结果与分析
在一般的B+树结果中，结点中往往是仅包含其子树中最大的关键字，而在本文的研究方法中，将子树中的最小关键字作为保存在上一级节点中。通过这种方法，可以减少索引结构的更新。使索引更加高效。
在主函数main中，实现一个计算时间的函数time(void (*process)(void))；用该函数粗略记录的程序的执行时间。该实验运行的环境为Pentium(R) 4，CPU 3.00GHZ，1G内存的Windows XP系统。最终将生成好的索引文件存放入btree_index.txt中，记录中包含约30,000个关键字。初始化索引大约需要8s左右的时间，将所有节点遍历一遍则需要大约1.5s的时间。如图5所示为生成索引结构的图形化显示。
4 展望与总结
如今，网络信息的高速膨胀，给我们的信息检索系统的准确性、高效性都带来了很大的压力，而倒排索引作为信息检索系统的核心部分，组织方式与存储结构对信息检索的性能的影响不容小觑。因此，怎样找出一种高效的倒排索引结构一直是人们关注的话题[9]。
参考文献：
[1] 王冬,左万利,赫枫龄,等.一种增量倒排索引结构的设计与实现[J].吉林大学学报,2007(6).
[2] 王英强,石永生.B+树在数据库索引中的应用[J].长江大学学报,2008(1).
[3] 张华,顾红飞,刘涛.基于B+树的文本信息检索技术[J].皖西学院学报,2010(2).
[4] JES_US R,CAMPA~NA,JUAN M,et,al.Indexing fuzzy numerical data with a B+ tree for fast retrieval using necessity-measured flexible conditions[J].World Scientic,2009,17(Suppl 1):1-23.
[5] 严蔚敏,吴伟民.数据结构[M].北京:清华大学出版社,1997.
[6] 刘筝.嵌入式数据库B#树索引机制的实现[J].信息与电脑,2009(8).
[7] Roh Hongchan,Kim Woo-Cheol,Kim Seungwoo,et,al.A B-Tree index extension to enhance response time and the life cycle of flash memory[J].Information Sciences,2009,(179):3136-3161.
[8] Mohan C,Levine F.ARIES/IM: an efficient and high concurrency index management method using write-ahead logging[C].Proceedings of ACM SIGMOD,1992:371-380.
[9] 邓攀,刘功申.一种高效的倒排索引存储结构[J].计算机工程与应用,2008,44(31).