CN1292371C - 倒排索引存储方法、倒排索引机制以及在线更新的方法 - Google Patents

Abstract

本发明提供了一种基于倒排文件的倒排索引存储方法，包括：创建一个倒排文件，该文件包括多个固定大小的索引块，每一索引块包括多个固定大小的索引单元，其中每一索引单元用于存储一条索引信息；以及，顺序将有关各个索引项的索引信息存储到已创建的文件中，其中，将有关同一索引项的索引信息存储在连续的索引块中，并且每一索引块中的多个索引单元只用于存储有关同一索引项的索引信息。由于每一索引块只用于存储有关同一索引项的索引信息，所以在对一个索引块中进行操作时，不会影响其他索引项，于是可以对任何索引块中的索引信息进行在线更新。

Description

倒排索引存储方法、 倒排索引机制以及在线更新的方法

技术领域

本发明一般涉及信息检索技术，具体地说，涉及全文检索中使用的倒排索引的存储方法、倒排索引机制以及对倒排索引进行在线更新的方法。

背景技术

据统计，目前因特网上有上亿的网页，信息十分丰富，而且处于不断变化之中。因特网给信息检索技术提供了一个广阔的舞台，各类搜索引擎在此大显身手。目前的搜索引擎一般使用两种技术来实现信息检索：一是使用网站分类技术，即把网站进行树状归类，登录的网站属于至少一个类别，对每个站点都有简略的描述。二是使用全文检索技术，全文检索技术处理的对象是文本，它能够对大量文档(例如因特网上的大量网页)建立由字(词)到文档的倒排索引，在此基础上，当用户使用关键词来对文档(网页)进行查询时，系统将给用户返回含有该关键词的文档(网页)。建立这种倒排索引的好处是不必为每个用户查询都检查一遍所有的文档(网页)。在提供这种全文检索服务的搜索引擎中，通常存在两种使用倒排索引的方式。一种方式是将整个倒排索引装入内存中。很明显，这种方式能够快速地处理用户的查询请求。然而，采用此方式的搜索引擎需要功能强大的硬件和复杂的并行处理软件。所以，大多数搜索引擎都选择使用第二种方式：将倒排索引以文件(称为倒排文件)形式存储在外部存储器(例如硬盘)上，通过文件读/写操作来访问倒排文件，以获得倒排索引信息。这将降低搜索引擎的硬件和软件成本。

图1示出了传统的基于倒排文件的倒排索引存储方法。

具体地说，首先对各文档进行分析以提取那些有可能成为用户查询对象的字(词)，并且将提取的字(词)连同对应的文档的标识(ID)一起存储在文件中，如图1A所示。

在对所有文档进行分析之后，对以上生成的文件按提取的字(词)的顺序进行排序、合并、统计出各字(词)在各文档中出现的频率，如图1B所示。

最后将以上文件分成两部分，其中一个称为映像文件，另一个称为倒排文件。在映像文件中存储了排好序的字(词)和指向倒排文件中某一记录的指针，而倒排文件中存储了各字(词)的索引信息，即：含有该字(词)的文档的ID。在这两个文件中还有可能包含其他信息，如图1C所示，在映像文件中还包含以下字段：文档数，用于表明一个字(词)在多少个文档中出现；总频率，用于表明一个字(词)在所有文档中出现的次数。在倒排文件中还包括字段：频率，用于表明一个字(词)在一文档中出现的次数。

通常各字(词)在各文档中出现的频率有很大的不同。例如，某些不常用的字(词)有可能仅在个别文档中出现几次，而某些流行的或者常用的字(词)有可能在多个文档中出现上百次，上千次，甚次更多次。于是，在倒排文件中，有的字(词)的索引信息仅占很少的存储空间，而有的字(词)的索引信息则有可能占有很多的存储空间。所以，在倒排文件中，通常采用变长记录来存储各字(词)的索引信息。这种方案的缺点是无法进行在线更新(插入/删除)操作。例如，一条新插入的索引信息将会引起倒排文件中在其之后的所有索引信息都要向后移动。这不但会加大磁盘I/O操作的成本，同时由于时间的因素，无法实时地进行索引信息的更新。在现有技术中，为了进行索引信息的更新，通常的做法是，使用两个倒排文件，一个是稳定的文件，该文件非常大，包含历史索引信息，另一个是工作文件，很小，只包含最近更新的索引信息。例如，如果用户想在倒排文件中插入一条新的索引信息，则只更新工作文件。因为该文件较小，更新操作的成本就不会太大。于是，在检索过程中要分别对这两个文件进行检索，并将检索结果组合起来提供给用户，而且在夜晚或非交互检索期间，通过离线处理将工作文件中的记录组合到稳定的倒排文件中去。以上这种方案的缺点是无法对倒排索引进行在线更新。

发明内容

为解决此问题，本发明提出了一种新的支持在线更新的倒排索引存储方法、倒排索引机制、及其对倒排索引进行在线更新的方法。

根据本发明的一个方面，提供了一种基于倒排文件的倒排索引存储方法，该方法包括：

在存储介质上创建一个用于存储倒排索引的倒排文件，该倒排文件包括多个固定大小的索引块，至少一个索引块包括多个固定大小的索引单元，其中每一索引单元用于存储一条索引信息；以及

顺序将有关各个索引项的索引信息存储到已创建的倒排文件中，其中，将有关同一索引项的索引信息存储在连续的索引块中，并且每一索引块中的多个索引单元只用于存储有关同一索引项的索引信息。

根据本发明另一方面，提供一种在以上产生的倒排文件中在线插入一条新的索引信息的方法，该方法包括以下步骤：

从将要插入的新的索引信息中提取对应的索引项，将与该索引项对应的索引块拷贝到内存中；

置位该索引项的在线更新标志；

判断在与该索引项对应的索引块中是否存在空的索引单元，如果存在，则将该索引信息写入已找到的空索引单元中，如果不存在，则在该倒排文件结尾处创建一个新的索引块，将该索引信息写入该新创建的索引块中，并且更新当前索引块的块首部中的信息；以及

复位该索引项的在线更新标志。

根据本发明又一方面，提供一种在以上产生的倒排文件中在线删除一条索引信息的方法，该方法包括以下步骤：

从将要删除的索引信息中提取对应的索引项，将与该索引项对应的所有索引块拷贝到内存中；

置位该索引项的在线更新标志；

在与该索引项对应的索引块中找到存储该索引信息的索引单元，置位该索引单元的标志位，以表明该索引单元是一空单元；以及

复位该索引项的在线更新标志。

根据本发明再一方面，提供一种对以上倒排文件进行在线整合的方法，该方法包括以下步骤：

在存储介质上创建一个与以上老的倒排文件具有相同格式的新的倒排文件；

顺序处理每个索引项：

从老的倒排文件中将与该索引项相关的所有索引块拷贝到内存中；

置位该索引项的在线整合标志；

顺序将有关该索引项的索引块写到新创建的倒排文件中；以及

复位该索引项的在线整合标志；以及

停止在老的倒排文件上的检索服务，开始在新的倒排文件上的检索服务。

根据本发明再一方面，提供一种支持在线更新的倒排索引设备，该倒排索引机制包括：

存储单元，用于存储倒排文件，该存储单元包括：多个固定大小的索引块，至少一个索引块包括多个固定大小的索引单元，每一索引单元用于存储一条索引信息，其中，有关同一索引项的索引信息是存储在连续的索引块中，并且每一索引块中的多个索引单元只用于存储有关同一索引项的索引信息；

检索单元，用于根据用户输入的关键字，借助倒排文件检出文档，进行文档与查询的相关度评价，对将要输出的结果进行排序，并将查询结果返回给用户；以及

在线更新单元，用于对倒排文件中的索引信息进行在线插入/删除。

在根据本发明的基于倒排文件的倒排索引存储方法中，由于将与同一索引项相关的所有索引信息存储在连续的索引块中，这样在读取任意一索引项的索引信息时，无需对文件的读指针重新定位，所以可以减少文件读取操作所需的时间。更值得注意的是，在根据本发明的基于倒排文件的倒排索引存储方法中，每一索引块只用于存储有关同一索引项的索引信息。这样在对一个索引块中的索引信息进行操作时，不会影响其他索引项，于是就可以通过简单的加锁-解锁方法，来对任何索引块中的索引信息进行在线更新，而不必停止检索服务。

附图说明

通过以下结合附图对本发明优选实施例的描述，本发明的这些和其他优点、目的和特征将变得更加清楚，其中：

图1示出了现有技术中基于倒排文件的倒排索引存储方法；

图2示出了根据本发明一优选实施例的基于倒排文件的倒排索引存储方法；

图3示出了与访问和更新倒排文件操作有关的四个映像文件；

图4是一个流程图，描述了根据本发明一个优选实施例对倒排文件进行访问的过程；

图5是一个流程图，描述了根据本发明一个优选实施例对倒排文件进行在线插入的过程；

图6是一个流程图，描述了根据本发明一个优选实施例对倒排文件进行在线删除的过程；

图7是一个流程图，描述了根据本发明一个优选实施例对倒排文件进行整合的过程；以及

图8示出了根据本发明一优选实施例的倒排索引机制的组成。

具体实施方式

图2示出了根据本发明一优选实施例的基于倒排文件的倒排索引存储方法。如图2A所示，在根据本发明一优选实施例的基于倒排文件的倒排索引存储方法中，首先要在存储介质上创建一个用于存储倒排索引的倒排文件，其格式如图2B所示。所述存储介质可以是磁盘、光盘等可直接访问的非易失性存储介质。该倒排文件由多个固定大小的索引块组成，而每个索引块又包括数目相等的固定大小的索引单元。每一索引单元用来存储一条索引信息。在创建了如图2B所示的倒排文件之后，对于任意一个索引项K计算出该索引项所需的索引块个数B＝((N_K+m-1)/m)取整，然后顺序将有关该索引项的索引信息存储到从L开始的B个索引块中，其中：m：每个索引块中包含的索引单元的个数；N_K：有关索引项K的索引信息的条数；L：是一指针，指向倒排文件中的一个索引块，从该索引块开始的B个连续的索引块将用于存储有关该索引项K的索引信息，其初始值为1。由此可以看出，在根据本发明的基于倒排文件的倒排索引存储方法中，将有关同一索引项的索引信息存储在连续的索引块中，并且每一索引块中的多个索引单元只用于存储有关同一索引项的索引信息。

在前边我们曾讨论过，在基于文本的检索中，各个字(词)(又称索引项)的流行性、常用性决定了其在文档中出现的频率有很大的不同。一个不常用字(词)，有可能只在个别文档中出现过几次，而目前流行的常用字(词)可能在多个文档中出现过几百次甚至几千次(或更多次)。于是，不同的索引项需要的索引块数是不同的。正如以上所述，对于任意一个索引项K来说，如果其在各文档中出现过N_K次，则需((N_K+m-1)/m)取整个索引块来存储有关该索引项的索引信息。在根据本发明的基于倒排文件的倒排索引存储方法中，将与同一索引项相关的所有索引信息存储在倒排文件的连续索引块中，这样在读取任意一索引项的索引信息时，无需对文件的读指针重新定位，所以可以减少文件读取操作所需的时间。此外，在根据本发明的基于倒排文件的倒排索引存储方法中，倒排文件中的每一索引块只用于存储有关同一索引项的索引信息。这样在对一个索引块中的索引信息进行操作期间，不会影响到其他索引项，于是就可以通过简单的加锁-解锁方法，来对任何索引块中的索引信息进行在线更新，而不必停止检索服务。

在确定一个索引块中包含索引单元的个数时，主要从磁盘存储消耗方面进行考虑：

如果索引块中包含单元个数很少，那么造成每个索引项对应的索引块的个数增多，同时由于每个索引块都会有一个固定长度的块首部，因此一方面会在块首部上浪费很多的存储空间，另一方面，因为索引块过小，会使倒排文件在以下将要介绍的在线更新过程中产生碎片的概率增大，因此，在实际应用中会影响系统的检索效率。

如果索引块中包含单元个数很多，也会带来问题。因为通常大多数索引项在文档中出现的次数都很少，例如，根据在随机抽取的2550篇新浪新闻网页进行的统计，通过分词处理，一共找到了30444个不同的索引词，而其中就有20657个词的出现的次数不大于5次。因此，如果索引块中包含索引单元个数过多，因为大量的低频词会导致巨大的存储浪费，这也会影响系统的检索效率。

因此，需要对二者进行一种折中，根据用户语料库的具体情况，通过空闲存储的百分比来决定索引块中索引单元的个数。

另外，索引块中包含的索引单元的个数也可以考虑根据文件系统的设定进行优化。索引块中包含单元个数越多，那么其大小s也就越大。考虑到磁盘中文件块的大小M，如果s和M可以互相整除(s可以整除M或者M可以整除s)，那么在建立倒排文件时候，我们就可以将索引块和文件块进行对齐，进而在读取索引块时会减少读取文件块的个数，从而达到了优化的目的。

在图2B所示的倒排文件中，每个索引块包括一个块首部和10个索引单元。对于本领域技术人员来说，很明显该优选实施例只是为了说明本发明，而不应该构成对本发明的限制。在各种具体应用中，可以根据用户语料库的具体情况来确定索引块中包含的索引单元的个数。

在图2B所示的倒排文件中，在块首部中包括以下字段：单元数，用于表明该索引块中非空索引单元个数；下一块信息，其中：“0”，表明该索引块是用于存储该索引项的索引信息的最后一个索引块；“1”，表明紧邻该索引块的下一索引块仍是用于存储该索引项的索引信息；其他值，是一偏移地址，例如从文件开始处的偏移块数，表明在其他不连续的索引块中还存储了该索引项的索引信息，可由该偏移地址得出该不连续的索引块的具体地址。在以下将会讨论，由于在线更新操作，会使部分索引信息存储在不连续的索引块中，即会产生碎片。但可以通过整合操作来消除这些碎片。

此外，在图2B所示的倒排文件中，每个索引单元包括以下字段：单元标志，“1”表明该单元中存储了索引信息，“0”表明该单元为空单元；以及索引信息，用于存储文档的ID、该索引项(字、词)在该文档中出现的频率等。

由以上可以看出，在根据本发明的基于倒排文件的倒排索引存储方法中，由于将有关同一索引项的所有索引信息存储在倒排文件的连续索引块中，所以在检索过程中，可以提高访问速度。此外，由于在倒排文件中，每个索引块只存储与同一索引项相关的索引信息，所以对任意一索引块的更新操作，不会影响到其他索引项，因此可以在不停止检索服务的情况下更新倒排文件，于是根据本发明的基于倒排文件的倒排索引存储方法支持在线更新操作。

以下就结合附图详细地描述一下对以上产生的倒排文件进行访问以及进行在线更新的操作。

图3示出了与访问和更新倒排文件操作有关的四个映像文件。其中：

映像文件1实现了从索引项(字、词)到索引项ID的映射。索引项，也就是通常所说的关键字(词)都有一个唯一的数字，即索引项ID与之一一对应，这样在存储和检索过程中就可以使用数字来表示该关键字(词)，从而减少存储空间同时加快检索速度。例如，通过使用索引项ID，可以将在图1C中的映像文件存储的索引项替换为其ID。

映像文件2实现了从索引项ID到倒排文件偏移地址的映射。对于索引项ID到倒排文件中偏移地址的映像表，它给出了在倒排文件中包含该索引项的第一个索引块的偏移地址。这样就将索引项和倒排文件中相对应的索引块建立了对应关系。如果该偏移地址N＞＝0，则表明该索引项的索引信息位于从倒排文件开始的N*(索引块大小)处；如果该偏移地址N＜0，则表明正在对该索引项的索引信息进行更新，原始索引信息已拷贝到内存中。

映像文件3、4给出了文档ID同其具体路径的一一映射。这样在索引中，就可以利用其文档ID来表示具体存储在某个位置的该文档地址，同样知道文档ID就可以通过其映射的文档路径来找到该文档的具体内容。实现了从文档ID到文档名/文档路径的映射。

以下就结合图4描述一下对倒排文件的访问过程。如图4所示，首先通过映像文件1获得索引项的ID(步骤401)。然后再使用映像文件2获得该索引项ID对应的倒排文件偏移地址(步骤403)。如果该偏移地址小于零，则表明正在对该索引项的索引信息进行更新，由于已将与该索引项相关的所有索引块拷贝到内存中，所以可以直接访问内存中的各索引块(步骤404，406)。如果偏移地址大于或等于零，则按该偏移地址来访问倒排文件中与该索引项相关的索引块(步骤404，405)。在此之后，判断当前索引块的块首部中下一块信息是否大于零(步骤407)。如果大于零，则表明还存在与该索引项相关的其他索引信息，则继续按下一块信息来访问倒排文件(返回到步骤402)。如果下一块信息不大于零，则表明这是与该索引项相关的最后一个索引块，于是结束访问操作(步骤408)。

由以上可以看出，如果与一个索引项相关的所有索引信息都存储在连续的索引块中(没有碎片)，则访问某一索引项的索引信息的操作是访问倒排文件中的连续的索引块，于是不必移动文件读指针，所以访问速度非常快。

以下结合图5和图6详细地描述一下对以上倒排文件进行的在线更新操作，其中图5示出了在线插入操作，图6示出了在线删除操作。

如图5所示，为了在倒排文件中插入一条新的索引信息，首先通过映像文件2获得该索引项的索引信息所在第一索引块的地址，即相对于倒排文件开始处的偏移地址(步骤501)。然后，按该偏移地址找到用于存储该索引项的索引信息的第一个索引块，并且按各索引块的块首部中的下一块信息找到用于存储该索引项的索引信息的所有其他索引块，并且将它们拷贝到内存中(步骤502)。并且，将该索引项的偏移地址设置成负值，以表明正在对该索引项进行在线更新操作(步骤503)。在此之后，按偏移地址和各索引块的块首部中的下一块信息访问倒排文件，以找到一个空单元，将该索引信息写到空的索引单元中，并且将当前数据的块首部中的单元数加1(步骤505，506，507)。如果在与该索引项相关的索引块中没有找到空的索引单元，则在倒排文件结尾处创建一新的索引块，将该索引信息写到新创建的索引块的第一个索引单元中，并且更新当前索引块的标题中的下一块信息(步骤508)。最后将偏移地址复位(步骤509)，结束在线插入操作(步骤510)。由以上可以看出，由于在对倒排文件执行在线插入过程中，如果在与该索引项相关的索引块中没有找到空的索引单元，则将要插入的索引信息写入在倒排文件结尾处新创建的索引块中，于是造成与同一索引项相关的索引块不再是连续的，即产生了碎片，但是可以通过以下将要介绍的整合操作来消除这些碎片。

图6示出了对倒排文件进行的在线删除操作。如图6所示，首先通过映像文件2获得该索引项的索引信息所在第一索引块的地址，即相对于倒排文件开始处的偏移地址(步骤601)。按该偏移地址找到用于存储该索引项的索引信息的第一个索引块，并且按各索引块的块首部中的下一块信息找到用于存储该索引项的索引信息的所有其他索引块，并且将它们拷贝到内存中(步骤602)。然后将该索引项的偏移地址设置成负值，以表明正在对该索引项进行在线更新操作(步骤603)。在倒排文件中按偏移地址和各索引块的块首部中的下一块信息逐块查找该索引信息所在的索引单元，找到后将该索引单元的标志置为零，表明该单元是一空索引单元，并且将当前索引块首部中的单元数减1(步骤604，605，606，607)。最后复位偏移地址(步骤608)，结束删除操作(步骤609)。

由以上可以看出，无论在线插入操作还是在线删除操作都有可能导致有关同一索引项的索引信息不再存储在连续的索引块中，这会降低倒排文件的访问速度，于是需要对其定期进行整合。图7示出了这种整合操作。这种整合操作也可以是在线操作，无需停止检索服务。

如图7所示，基本工作过程是通过遍历映像文件2来处理所有索引项以及与之相对应的倒排文件中的索引块，保证每一个索引项相对应的所有索引块在新的索引文件中物理上是连续分布的，从而实现消除‘碎片’的功能。

701，702，703，706是遍历映像文件2的过程，这样就逐个遍历了所有索引项。对于每个索引项，通过映像文件2中对应该索引项ID的偏移地址以及在每个索引块中的下一块信息，就可以访问老的倒排文件中对应该索引项ID的所有索引块(704)。然后将除最后一块的索引块中下一块信息改为‘1’，并将新块按顺序写入新的倒排文件(705)。当所有过程完成，就可以停止在老倒排文件上的检索服务，将服务转入新文件上(707)。

由于在根据本发明的基于倒排文件的倒排索引存储方法中，使倒排文件中的任一索引块只与一索引项相关，即只用来存储同一索引项的索引信息，所以对倒排文件中的任意一索引块的操作不会影响其他索引项，所以不必停止检索服务。因此这种整合操作可以是在线操作。如果在线地进行这种整合操作，需要在对每一索引项进行处理之前或之后，置位或复位在线整合标志。

以上结合附图详细地描述了根据本发明优选实施例的基于倒排文件的倒排索引存储方法以及对倒排索引进行在线更新的方法和整合方法，对于本领域技术人员来说，很明显，基于以上内容，很容易得出一种支持在线更新的倒排索引机制。

所谓索引机制是指一个能够为信息资源建立索引，然后为用户查询提供服务的计算机系统。于是，所谓的倒排索引机制就是指一个能够为文本信息建立倒排索引，然后为用户查询提供全文检索服务的计算机系统。通常，倒排索引机制的工作包括如下三个过程：1.搜索文本信息；2.对文本信息进行提取，建立倒排文件；3.根据用户输入的关键字，借助倒排文件检出文档，进行文档与查询的相关度评价，对将要输出的结果进行排序，并将查询结果返回给用户。此外，通常索引机制的工作还应包括一个对倒排文件进行索引信息的更新(插入/删除)的过程。然而，如前所述，由于现有倒排文件结构上的限制，这种维护操作只能离线地进行。为此，根据本发明另一个方面，提供一种支持在线更新的倒排索引机制。

如图8所示，根据本发明一个优选实施例的倒排索引机制包括：用户接口801、检索单元802、在线更新单元803、整合单元804、文件读/写处理单元805以及倒排文件806。其中，用户接口801用于接收各种用户输入或输出各种查询结果。检索单元802包括倒排文件访问单元、相关度评价单元和查询结果排序单元，用于根据用户输入的关键字，借助倒排文件检出文档，进行文档与查询的相关度评价，对将要输出的结果进行排序，并将查询结果返回给用户。在线更新单元803包括在线插入单元和在线删除单元，用于对倒排文件中的索引信息进行在线插入/删除，其具体操作过程如图5和图6所示。整合单元804包括在线整合单元和离线整合单元，用于在线或离线地消除倒排文件中的碎片(不连续的索引块)，其具体操作过程如图7所示。文件读/写处理单元805用于通过I/O通道或网络等来读取或改写以上倒排文件，其中，该文件读/写处理单元可以在一次文件读取操作中读取倒排文件中与一个索引项相关的多个连续的索引块。倒排文件806是通过如图2所示的根据本发明一个优选实施例的基于倒排文件的倒排索引存储方法产生的，该倒排文件可以存储在各种存储介质上，例如磁盘、光盘等可直接访问的非易失性存储介质上。

对于本领域技术人员来说，很明显，根据本发明优选实施例的支持在线更新的倒排索引机制既可以作为一个计算机系统来实现，也可以是记录在任何计算机可读存储介质上的程序。此外，倒排文件和各个处理单元可以在同一计算机上，也可以分布在不同的计算机上，各个计算机之间可以通过网络相连接。

虽然以上结合附图对本发明优选实施例进行了详细地描述，但这些实施例不是限制性的，本领域技术人员可以在不背离本发明的精神实质情况下作出各种修改和变型。因此，本发明不限于这些实施例，本发明的保护范围由所附权利要求书来限定。

Claims (7)

1.一种基于倒排文件的倒排索引存储方法，该方法包括：

在存储介质上创建一个用于存储倒排索引的倒排文件，该倒排文件包括多个固定大小的索引块，每一索引块包括多个固定大小的索引单元，其中每一索引单元用于存储一条索引信息；以及

顺序将有关各个索引项的索引信息存储到已创建的倒排文件中，其中，将有关同一索引项的索引信息存储在连续的索引块中，并且每一索引块中的多个索引单元只用于存储有关同一索引项的索引信息。

2.根据权利要求1的基于倒排文件的倒排索引存储方法，其中每一索引块还包括一个块首部，该块首部包括以下字段：单元数，用于表明该索引块中非空索引单元个数；以及，下一块信息，用于表明与当前索引项相关的下一索引块的位置。

3.一种在倒排文件中在线插入一条新的索引信息的方法，其中所述倒排文件包括：多个固定大小的索引块，每一索引块包括多个固定大小的索引单元，每一索引单元用于存储一条索引信息，其中，有关同一索引项的索引信息是存储在连续的索引块中的，并且每一索引块中的多个索引单元只用于存储有关同一索引项的索引信息，该方法包括以下步骤：

从将要插入的新的索引信息中提取对应的索引项，将与该索引项对应的索引块拷贝到内存中；

置位该索引项的在线更新标志；

判断在与该索引项对应的索引块中是否存在空的索引单元，如果存在，则将该索引信息写入已找到的空索引单元中，如果不存在，则在该倒排文件结尾处创建一个新的索引块，将该索引信息写入该新创建的索引块中，并且更新当前索引块的块首部中的信息；以及

复位该索引项的在线更新标志。

4.一种在倒排文件中在线删除一条索引信息的方法，其中所述倒排文件包括：多个固定大小的索引块，每一索引块包括多个固定大小的索引单元，每一索引单元用于存储一条索引信息，其中，有关同一索引项的索引信息是存储在连续的索引块中的，并且每一索引块中的多个索引单元只用于存储有关同一索引项的索引信息，该方法包括以下步骤：

从将要删除的索引信息中提取对应的索引项，将与该索引项对应的所有索引块拷贝到内存中；

置位该索引项的在线更新标志；

在与该索引项对应的索引块中找到存储该索引信息的索引单元，置位该索引单元的标志位，以表明该索引单元是一空单元；以及

复位该索引项的在线更新标志。

5.一种对倒排文件进行在线整合的方法，其中所述倒排文件包括：多个固定大小的索引块，每一索引块包括多个固定大小的索引单元，每一索引单元用于存储一条索引信息，其中，有关同一索引项的索引信息是存储在连续的索引块中的，并且每一索引块中的多个索引单元只用于存储有关同一索引项的索引信息，该方法包括以下步骤：

在存储介质上创建一个与以上老的倒排文件具有相同格式的新的倒排文件；

顺序处理每个索引项：

从老的倒排文件中将与该索引项相关的所有索引块拷贝到内存中；

置位该索引项的在线整合标志；

顺序将有关该索引项的索引块写到新创建的倒排文件中；以及

复位该索引项的在线整合标志；以及

停止在老的倒排文件上的检索服务，开始在新的倒排文件上的检索服务。

6.一种支持在线更新的倒排索引设备，包括：

存储单元，用于存储倒排文件，该存储单元包括：多个固定大小的索引块，每一索引块包括多个固定大小的索引单元，每一索引单元用于存储一条索引信息，其中，有关同一索引项的索引信息是存储在连续的索引块中的，并且每一索引块中的多个索引单元只用于存储有关同一索引项的索引信息；

检索单元，用于根据用户输入的关键字，借助倒排文件检出文档，进行文档与查询的相关度评价，对将要输出的结果进行排序，并将查询结果返回给用户；以及

在线更新单元，用于对倒排文件中的索引信息进行在线插入/删除。

7.根据权利要求6的支持在线更新的倒排索引设备，其中还包括一个整合单元，用于在线或离线地消除倒排文件中的碎片。

Images