精华内容
下载资源
问答
  • Lucene倒排索引简述 之倒排表

    千次阅读 2018-10-09 20:31:55
    本篇博客将继续剖析Lucene关于倒排索引实现有另一个核心内容,倒排表(Postings)。我一直觉得Postings内容相对而言是比较简单,虽然内容很多,但是Lucene的官方文档讲得也非常详细了。如果对Lucene文档上的描述文件...

    一、前言

    上一篇《Lucene倒排索引简述 之索引表》,已经对整个倒索引的结构进行大体介绍,并且详细介绍了索引表(TermsDictionary)的内容。同时还详细介绍了Lucene关于索引表的实现,相关文件结构详解,以及对索引表采用的数据结构进行剖析解读。

    本篇博客将继续剖析Lucene关于倒排索引实现有另一个核心内容,倒排表(Postings)。我一直觉得Postings内容相对而言是比较简单,虽然内容很多,但是Lucene的官方文档讲得也非常详细了。如果对Lucene文档上的描述文件结构的表达方式不太熟悉的话,个人觉得可以参考前面的图自行画出文件结构示意图,或者直接在网络搜索相关的图,只要能整出索引文件的结构示意图,那么理解起来就应该不会太困难。

    二、Postings编码

    开始之前先介解Lucene在Postings采用了两个关键的编码格式,PackedBlock和VIntBlock。PackedBlock是在Lucene4.0引入,带来向量化优化。

    1. VIntBlock

    VIntBlock是能够存储复合数据类型的数据结构,主要通过变长整型(Variable Integer)编码达到压缩的目的。此外VIntBlock还能够存储byte[],比如.pay用VIntBlock存储了payloads数据等。

    值得一提的是,VIntBlock可以存储变长数据结构,如.doc用它存储DocID和TermFreq时,由于在特定条件下(TermFreq=1),Lucene会省略TermFreq以提高空间占用率。我知道Lucene用一个VInt来表示DocID,VInt则用每个Byte左边第一个Bit来表示是否需要读取顺续到下个Byte。也就是说一个VInt有效位是28bit,这就说明VInt头部是有特殊含义的,因此Lucene只能在VInt最右边的一个bit下功夫。让VInt的右边第一Bit来表示是否有下个数据。

    具体用法会在介绍.doc文件格式时介绍。

    2. PackedBlock

    PackedBlock只能存储单一结构,整数数组(Integer/Long)。这里主要是介绍PackedInts,即是将一个int[]打包成一个Block。PackedBlock只能能够存储固定长度的数组(Lucene规定其长度为128个元素),它压缩方式是将每个元素截断为预算的长度(length,单位是bit)压缩的。所以当长度length不是8的倍数时,会出现一个byte被多个元素占用。

    PackedBlock需要把整个int[]的所有条目指定长度编码,所以PackedBlock只能选择int[]最大的数还来计算长度,否则会让大数失真。反过来,PackedBlock都选择64位,则会浪费空间,不能达到压缩的目的。

    Lucene预先编译了64个PackedFormat编码器和解码器,即针对Long以内的每种长度都数据都有自己的解码和编码器,以提高编解码的性能。

    PackedPosDeltaBlock与PackedDocDeltaBlock和PackedFreqBlock一样采用PackedInts结构,它能存储的信息实际上是很有限的,只能存储Int的数组。所以在PackedPosDeltaBlock的时候,只能存储position信息,在VIntBlock则会存储更多必要的信息,减少搜索时的IO操作。

    这也是为什么需要将DocId和TermFreq拆分成PackedDocDeltaBlock和PackedFreqBlock两个Block存储的原因了。

    定长是指PackedBlock限定了一个Block仅允许存储长度128的整型数组,而不是限定Block用多少个Bytes来存储编码后的结果。另外Block存储占用的大小,是按数组中最大那个数的有效bits长度来计算整个Block需要占用多大的Bytes数组的。也就是Block的每个数据的长度都是一样,都按最长bits的来算。

    比如:(我们定义一个函数,bit(num)用来计算num占用多少个bits)

    1. 数组中最大的是1,那么PackedBlock的长度仅是16Bytes。bit(1) * 128 / 8 = 16
    2. 数组中最大的是128,PackedBlock长度则是144个Bytes。bit(128) * 128 / 8 = 144
    3. 数组中最大的是520,PackedBlock则需要160Bytes。bit(520) * 128 / 8 = 160

    小结,PackedBlock相当于是实现了向量化优化,Lucene通常会将整个PackedBlock加载到内在,既可以减少IO操作数,又能提高解码的性能。相对而言VIntBlock则能够更丰富数据类型,比较适合存储少量数据。

    三、Postings文件结构说明

    进入正题,我们知道整个Postings被拆成三个文件分别存储,实际上它们之间相对也是比较独立的。基本所有的查询都会用.doc,且一般的Query也仅需要用到.doc文件就足够了;近似查询则需要用.pox;.pay则是用于Payloads搜索(关于这个之前写一篇博客《Solr 迟到的Payloads》,介绍了Payloads用法和场景)。

    1. Frequencies And Skip Data(.doc文件)

    在Lucene倒排索引中,只有.doc是Postings必要文件,即是它是不能被省略。除此之外的两个文件都是通过配置,然后将其省略的。那么.doc到底是存储哪些不可告人的秘密呢?直接上图,开始剖析吧!

    这里画得不够清晰,每个Term都有成对的TermFreqs和SkipData的。换言之,SkipData是为TermFreqs构建的跳表结构,所以它们是成对出现的。

    1.1. TermFreqs – Frequencies

    TermFreqs存储了Postings最核心的内容,DocID和TermFreqs。分别表示文档号和对应的词频,它们是一一对应的,Term出现在文档上,就会有Term在文档中出现次数(TermFreqs)。

    Lucene早期的版本还没有PackedBlock结构,所以DocID与TermFreq是以一个二元组的方式存储的。这个结构非常好,是因为它好理解,之所以好理解是因为它贴近我们的心中的预想。但实际上这个结构并不太准确,只不过我们先简单这么理解也无伤大雅。既然是想深入剖析,还是有必要还原真相的。

    TermFreqs采用的是混合存储,由Packed Blocks和VInt Blocks两种结构组成。由于PackedBlock是定长的,当前Lucene默认是128个Integers。所以在不满128的时候,Lucene则采用VIntBlocks结构还存储。需要注意的是当用Packed Blocks结构时,DocID和TermFreq是分开存储的,各自将128个数据写入到一个Block。

    当用VIntBlocks结构时,还是沿用旧版本的存储方式,即上面描述的二元组的方式存储。所以说,将DocID和TermFreq当成一条数据的说法是不完全正确的。

    在Lucene4.0之前的版本,还没有引入PackedBlock时,DocID和TermFreq确定完全是成对出现,当时只有VIntBlock一种结构。

    Lucene尽可能优先采用PackedBlocks,剩余部分(不足128部分)则用VIntBlocks存储。引入PackedBlock之后,PackedDocDeltaBlock跟PackedFreqBlock是成对的,所以它的写出来的示意图应该是如下:

    每个PackedBlock由一个PackedDocDeltaBlock和一个PackedFreqBlock构成,它们都采用PackedInts格式。

    例如,在同一个Segment里,某一个Term A在259个文档同一个字段出现,那么Term A就需要把这259个文档的文档编号和Term A在每个文档出现的频率一同记下来存储在.doc。此时,Lucene需要用到2个PackedBlocks和3个VIntBlocks来存储它们。

    VIntBlock结构相对而言就高级很多了,它能够以一种巧妙的方式存储复杂的多元组结构。在.doc,用VIntBlock存储DocID和TermFreqs,是二元组。后面将介绍的Positions则用VIntBlock存储了Postition、Payload和Offset多元组,
    byte[]和VInt多种数据类型。

    这里每一个PackedBlock结构都包含了一个PackedDocDeltaBlock和一个PackedFreqBlock,如果没有省略Frequencies(TermFreq)的话;如果用户配置了不存储词频(TermFreq)的话,此时一个PackedBlock仅含有一个PackedDocDeltaBlock。PackedFreqBlock(TermFreq)的存储方式跟PackedDocDeltaBlock(DocID)完全一致,包括后面要讲的pos/pay也都一样的。也都是使用Packed Block这种编码方式。

    在VIntBlock上如何存储DocDelta和TermFreq的呢,当设置为不存储TermFreq时,Lucene将所有DocDelta以Variable Integer的编码方式直接写文件上。

    但当DocDelta和TermFreq两者都存储时,官方文档给出一个比较完整且复杂的计算说明。反正是我觉得有点复杂,所以没有用直接官方的上说明,我们来点简单的。

    首先需要换算的原因是,Lucene做一个小优化,即是当TermFreq=1时,TermFreq将不被存储。那么原本DocDelta(DocID的增量)后面紧跟一个Frequencies的情况变得不再确定,我压根就不知道我读的DocDelta后面有没有TermFreq的信息。

    那么问题就变成怎么标记存储还是没有存储TermFreq,Lucene先把数值向左移动一位,然后用最右的一个Bit的标记是否存储TermFreq。最后右边的一个bit1表示没有存储,0作为有存储TermFreq。实际上这已经是Lucene的惯用手段了。

    左移一位,实际上等同于X2,当最后一个bit是0,此时是一定是偶数,表示后面还存 储了TermFreq;
    左移一位再+1,相当于偶数+1,那就是奇数,此时最后一个bit是1,表示TermFreq=1,所以后面没有存储TermFreq。

    这基本上就是官方文档上的大体意思了。

    DocFreq=1时,Lucene做一个叫Singletion(仅出现在一个文档)的优化,当时就没有TermFreq和SkipData。因为TermFreq就等同于TotalTermFreq(上篇文章介绍过,存储在.tim的FieldMetadata上)。

    1.2. Multi-level SkipList – SkipData

    SkipData是.doc文件核心部件之一,Lucene采用的是多层次跳表结构,首先我们先预热一下了解SkipList的逻辑结构图,最后剖析Lucene存储SkipList的物理结构图。

    跳表的原理非常简单,跳表其实就是一种可以进行二分查找的有序链表。跳表在原有的有序链表上面增加了多级索引,通过索引来实现快速查找。首先在最高级索引上查找最后一个小于当前查找元素的位置,然后再跳到次高级索引继续查找,直到跳到最底层为止,这时候以及十分接近要查找的元素的位置了(如果查找元素存在的话)。由于根据索引可以一次跳过多个元素,所以跳查找的查找速度也就变快了。 ——— 来自百度百科

    将搜索时耗时转嫁给索引时,空间换时间是索引的基本思想。为此Lucene为Postings构建SkipList
    ,并把按层级将它系列化存储。第一个SkipLevel是最高,拥有最少的索引数。

    易知Lucene是在索引时构建了SkipList,在Segment中 每个Term都有自己唯一的Postings,每个Postings都有需要构建一个SkipList。这三者是一一对应的。所以画出来结构图如下:

    除了第0层之外所有SkipLevel的每个跳表数据块(SkipDatum)会存储了指向下一个SkipLevel的指针。图中SkipChildLevelFPg带?的原因是在Level 0时,SkipDatum没有下一级可以记录。如果Postings有存储positions、payloads和offsets的话,在跳表数据块中也会记录它们的Block所有文件指针。

    也就是说,通过SkipList可以找到DocID和TermFreq之外,还能找到Positions、Payloads和Offsets这三部分信息。所以在搜索时,通过SkipList的可以快速定位Postings的所有相关信息。

    关于Lucene如何构建SkipList的诸多细节,Lucene规定SkipList的层级不超过10层。

    1. 第0层,SkipList为每个Block增加索引,所以VIntBlock不在SkipList上。
    2. 第9层,SkipList的第一个节点是在第89 (227)Block。(这个数确实有点大)
    3. 第n层,SkipList的第m个节点的位置是第 8 n ∗ m 8^n * m 8nm个Block。

    跳表的第一层是最密的,越高层越稀疏。按层级从低到高依次系列化为写入.doc的SkipData部分。换言之,SkipDatum的个数越来越多,SkipLevelLength会越来越大。

    SkipLevelLength说明当前层次Skip系列化之后的长度,SkipLevel是包含该层的所有节点的数据SkipDatum。SkipDatum包含四部分信息,doc_id和term_freq、positions、payloads、以及下一层开始的位置(是第N层指向第N-1层的前一个索引)。

    SkipList主要是搜索时的优化,主要是减少集合间取交集时需要比较的次数,比如在Query被分词器分成多个关键词时,搜索结果需要同时满足这些关键词的。即是需要将每个Term对应的DocId集合进行析取操作,通过跳表能够有效有减少比较的次数。

    2. Postitions(.pos文件)

    .pos文件存储所有Terms出现文档中的位置信息。为更好的搜索性能,Lucene还在VIntBlock上存储了部分payloads和offsets的信息。实际上因为只有VIntBlock才有能力来存储复杂的数据结构,而PackedBlock是不具备这样的能力的。具体请参考下面的示意图:

    Lucene把同一个Term的所有position信息存储在同一个TermPositions上,并没有逻辑或者物理上的划分的。将在一个文档里出现的所有位置信息,按出现的先后顺序依次写入。
    关键在于,position与TermFreq并不是在一维度上,TermFreq的数值就是position的个数。也就是通过.pos文件,无法知道每个position的具体含义的,PostingsReader通过.doc文件的DocID和TermFreq信息才能算出Postition的是在哪个文档上的那个位置的。

    3. Payloads and Offsets(.pay文件)

    Payloads,可以理解为Term的附加信息,它实际上是跟Term成对出现的,类似于Map。在用法上也是如此,Payloads的信息需要用byte数组存储,所以在TermPayloads并不能用PackedBlock结构来存储。但是TermOffsets是由2个int来表示Offet的开始位置和长度的,即是能将它们拆成两个等size的int[],故可以用PackedBlock存储。故有如下图:

    四、总结

    开篇先学习了Lucene用于存储Postings的两种结构,或者说编码方式,PackedBlock和VIntBlock。PackedBlock是Lucene4.0引用的,它就是int[],给Postings向量化优化。除之外,还有一原著民VIntBlock,也是一种很巧妙且优雅的结构,能存储复杂的类型。

    而后,在介绍.doc文件格式的同时,又对上面的两大结构反复剖析。个人认为了解这两个结构之后,整个postings的理解应该不成问题。并且剖析了.doc文件上采用的SkipList数据结构,主要是搜索时集合间AND操作上的一个优化。所以在postings其它两个文件格式,仅用非常短的篇幅介绍。

    Lucene倒排索引部分内容到这里全部结束,其它很多优雅的设计和巧妙的结构,其中蕴含的Lucene之美,值得我们反复研读。

    展开全文
  • 倒排索引 倒排表

    2012-11-11 21:23:43
    什么我们要说倒排索引呢?   因为倒排索引是目前 搜索引擎公司最对搜索引擎最常用的存储方式.也是搜索引擎的核心内容!  在搜索引擎实际的引用之中,有时需要按照关键字的某些值查找记录,所以我们是按照关键字...

    http://www.cnblogs.com/fora/archive/2010/06/12/1756796.html

    为什么我们要说倒排索引呢? 
        因为倒排索引是目前 搜索引擎公司最对搜索引擎最常用的存储方式.也是搜索引擎的核心内容!
        在搜索引擎实际的引用之中,有时需要按照关键字的某些值查找记录,所以我们是按照关键字建立索引,这个索引我们就称之为: 倒排索引, 而带有倒排索引的文件我们又称作: 倒排索引文件 也可以叫它为: 倒排文件 来实现快速的检索与高速的效率!

    那我想问下 什么是倒排表呢?
         倒排文件中的 次关键字索引 我们称做: 倒排表
         其主要优点是: 在处理复杂的多关键字查询时,可在倒排表中先完成查询的交、并等逻辑运算,得到结果后再对记录进行存取。这样不必对每个记录随机存取,把对记录的查询转换为地址集合的运算,从而提高查找速度!



    下面就是整个倒排表的建立过程(组图):

      数据表

     
    索引表
     
    右项归并后的索引表
     

    那我最后问下 我们因该怎样建立倒排索引呢?
    关于建立倒排索引其实就象我们写一本小说一样 目录是章节标题对应的页码 对全文搜索来讲 倒排索引就是词对应文档编号!
    下面我们举个例子: 
    案例1:
     普通文档存在形式:(从文件到关键字的搜索)
          PPT (从头看起.....)==> keywords1,keywords2,keywords3,keywords4,keywords5,.............
    案例2:
      倒排索引翻转后的结果显示:(从关键字到文件的搜索)
          keywords1,keywords2,keywords3,keywords4,keywords5,............. (直接找关键字 然后在找内容页)==> PPT

     不知您看懂了没!  如果还不是很清楚 我在举个例子 最简单的:
           我们随便看什么书 我想 因该是分2种看法 一种是 从头到尾法! 而 另一种就是 先看目录 看那些 是我需要看的 那么 直接就翻到 该页面! 不然 和第一个人一样从头一直看 看到你想要看的 那不是 前面时间都浪费了??  目录就起了个 关键作用! 这下因该懂了把! 如果还不清楚 不要紧 看看 上面的 倒排表 你就因该懂了

    展开全文
  • 倒排索引 和 倒排表

    千次阅读 2015-06-09 14:45:18
    什么我们要说倒排索引呢?   因为倒排索引是目前 搜索引擎公司最对搜索引擎最常用的存储方式.也是搜索引擎的核心内容!  在搜索引擎实际的引用之中,有时需要按照关键字的某些值查找记录,所以我们是按照关键字...

    为什么我们要说倒排索引呢? 
        因为倒排索引是目前 搜索引擎公司最对搜索引擎最常用的存储方式.也是搜索引擎的核心内容!
        在搜索引擎实际的引用之中,有时需要按照关键字的某些值查找记录,所以我们是按照关键字建立索引,这个索引我们就称之为: 倒排索引, 而带有倒排索引的文件我们又称作: 倒排索引文件 也可以叫它为: 倒排文件 来实现快速的检索与高速的效率!

    那我想问下 什么是倒排表呢?
         倒排文件中的 次关键字索引 我们称做: 倒排表
         其主要优点是: 在处理复杂的多关键字查询时,可在倒排表中先完成查询的交、并等逻辑运算,得到结果后再对记录进行存取。这样不必对每个记录随机存取,把对记录的查询转换为地址集合的运算,从而提高查找速度!

    那我最后问下 我们因该怎样建立倒排索引呢?
    关于建立倒排索引其实就象我们写一本小说一样 目录是章节标题对应的页码 对全文搜索来讲 倒排索引就是词对应文档编号!
    下面我们举个例子:
    案例1:
     普通文档存在形式:(从文件到关键字的搜索)
          PPT (从头看起.....)==> keywords1,keywords2,keywords3,keywords4,keywords5,.............
    案例2:
      倒排索引翻转后的结果显示:(从关键字到文件的搜索)
          keywords1,keywords2,keywords3,keywords4,keywords5,............. (直接找关键字 然后在找内容页)==> PPT

     不知您看懂了没!  如果还不是很清楚 我在举个例子 最简单的:
           我们随便看什么书 我想 因该是分2种看法 一种是 从头到尾法! 而 另一种就是 先看目录 看那些 是我需要看的 那么 直接就翻到 该页面! 不然 和第一个人一样从头一直看 看到你想要看的 那不是 前面时间都浪费了??  目录就起了个 关键作用! 这下因该懂了把! 如果还不清楚 不要紧 看看 上面的 倒排表 你就应该懂了.
    展开全文
  • 查找8.3 索引顺序表和倒排表8.3.1 索引顺序表 8.3 索引顺序表和倒排表 当数据表中的数据元素个数n很大时,如果用顺序查找结构,则查找效率极低。如果采用有序表存储形式的折半查找,则为了维持数据表的有序性,时间...

    8.3 索引顺序表和倒排表

    当数据表中的数据元素个数n很大时,如果用顺序查找结构,则查找效率极低。如果采用有序表存储形式的折半查找,则为了维持数据表的有序性,时间开销很大;而且,当数据表很大时,计算机内存的容量可能不够。这时可采用索引方法来实现存储和查找。

    8.3.1 索引顺序表

    1. 索引顺序表一般由主表索引表两个部分组成,两者均采用顺序存储结构。
      主表中存放数据元素的全部信息索引表中存放数据元素的主键字和索引信息

    (1)完全索引

    1. 在图8-3所示的学生信息表的例子中,一个索引项对应数据表中一个数据元素,这时的索引结构叫作稠密索引也称完全索引。稠密索引结构适用于当数据元素在外存中按加入次序存放而不是按关键字有序存放的情形。
      在这里插入图片描述
    2. 完全索引表中关键字分块有序存放,即把所有n个索引项分为m个块 (子表),井且后一个子表中所有的关键字均大于前一个子表中所有的关键字,而在同一子表中所有关键字的次序任意。分块有序,索引按照关键字的大小建立,可知大于某个值或者小于某个值可以到哪个块里面去查找。经典的分块查找要求块间有序、块内也有序,如果块与块无序就无法建立索引。
    3. 分块查找的具体实现
      转载自:https://www.cnblogs.com/ciyeer/p/9067048.html
    #include <stdio.h>
    #include <stdlib.h>
    struct index {   //定义块的结构
      int key;
      int start;
    } newIndex[3];  //定义结构体数组
    int search(int key, int a[]);
    int cmp(const void *a,const void* b){
      return (*(struct index*)a).key>(*(struct index*)b).key?1:-1;
    }
    int main(){
      int i, j=-1, k, key;
      int a[] = {33,42,44,38,24,48, 22,12,13,8,9,20, 60,58,74,49,86,53};
      //确认模块的起始值和最大值
      for (i=0; i<3; i++)   {
        newIndex[i].start = j+1; //确定每个块范围的起始值
        j += 6;
        for (int k=newIndex[i].start; k<=j; k++)     {
          if (newIndex[i].key<a[k])       {
            newIndex[i].key = a[k];
          }
        }
      }
      //对结构体按照 key 值进行排序
      qsort(newIndex,3, sizeof(newIndex[0]), cmp);
      //输入要查询的数,并调用函数进行查找
      printf("请输入您想要查找的数:\n");
      scanf("%d", &key);
      k = search(key, a);
      //输出查找的结果
      if (k>0)   {
        printf("查找成功!您要找的数在数组中的位置是:%d\n",k+1);
      }  else  {
        printf("查找失败!您要找的数不在数组中。\n");
      }
      return 0;
    }
    int search(int key, int a[]){
      int i, startValue;
      i = 0;
      while (i<3 && key>newIndex[i].key)   {     // 确定在哪个块中,遍历每个块,确定key在哪个块中
        i++;
      }
      if (i>=3)   {     //大于分得的块数,则返回0
        return -1;
      }
      startValue = newIndex[i].start; //startValue等于块范围的起始值
      while (startValue <= startValue+5 && a[startValue]!=key)
      {
        startValue++;
      }
      if (startValue>startValue+5)   {     //如果大于块范围的结束值,则说明没有要查找的数
        return -1;
      }
      return startValue;
    }
    运行结果:
    
    请输入您想要查找的数:
    22
    查找成功!您要找的数在数组中的位置是:7
    
    1. 但是索引查找,块间有序,块内可以无序。查找过程是:
      首先根据索引查到块,然后如果块内有序就可以二分查找,如果无序就只能顺序查找。如下图,要查找38:
      在这里插入图片描述
      现在索引表看,38>22,而38<48,得到这个块的首地址6,直接找到6号位,(块内可以无序)并且从6号位开始顺序查找,直到9号位也是38,查找成功。

    (2)二级索引

    当完全索引表中关键字分块有序存放时,可以为完全索引表建立一个二级索引表,在二级索引表中一个索引项对应完全索引表中的一个子表,它记录了相应子表中最大关键字以及该子表在数据区中的起始位置,这种索引被称为二级索引,如图 8-4所示。
    在这里插入图片描述

    1. 对二级索引结构进行查找时,一般分为二次查找。其过程是:
      先在二级索引表中按给定值k进行查找,以确定待查子表的序号i,使得序号为i-1的子表中的最大关键字<k<=序号为i的子表中的最大关键字。然后再在第i个子表中给定值查找关健字等于k的索引项。如果找到关键字等于k的索引项,则可以根据索引项内的地址直接从外存中读取相应的数据元素;否则表示查找失败。
    2. 二级索引表是按关键字有序的,且长度一般不太大,可以用折半查找,也可以顺序查找。
    3. 二级索引查找平均查找长度:
      (1)查找成功
      ASL(IndexSeq)=ASL(Index)+ASL(SubList)
      其中,ASL(Index)是在二级索引表中查找成功的平均查找长度,ASL(SubList)是在子表内查找成功的平均查找长度。
      设完全索引表的长度为n,分成均等的m个子表,每个子表中有k个对象,则m=⌈n/k⌉(向上取整)。
      在等概率的情况下,每个子表的查找概率为1/m,子表内各对象的查找概率为1/k。
      ①若二级索引表和子表都用顺序查找,则二级索引查找成功时的平均查找长度为:
      ASL(IndexSeq)=(n+k2)/(2k)+1
      由此可见,二级索引查找的平均查找长度不仅与完全表索引表的长度n有关,而且与每个子表中所含的索引项个数k有关。那么,在给定n的情况下,当k=n1/2时,ASL(IndexSeq)取极小值n1/2+1
      ②若对二级索引表采用折半查找、对子表用顺序查找,则二级索引查找成功时的平均查找长度为:
      ASL(IndexSeq)=ASL(Index)+ASL(SubList)~log2(1+n/k)+k/2

    结论

    查找方法比较

    n个元素顺序查找折半查找分块查找
    ASL最大最小两者之间;顺序查找+顺序查找ASL=(n+k2)/(2k)+1;折半查找+顺序查找ASL~log2(1+n/k)+k/2
    表结构有序表、无序表有序表分块有序表
    存储结构顺序存储结构、线性链表顺序存储结构顺序存储结构、线性链表(块可以链式存储,但是要知道块的首地址)

    8.3.2 倒排表

    1. 对包含有大量数据元素的数据表或文件进行查找时,最常用的方法是针对数据元素的主关键字建立索引表,用主关键字建立的索引叫作主索引,主索引表的每个索引项给出数据元素的关键字及其在数据表或文件中的存放地址。但在实际应用中有时需要针对其他属性进行查找。
      因此,除主关健字外,可以把一些在查找时经常用到的属性设定为次关键字,并以每一个属性作为次关键字建立次索引表,称之为倒排索引表
    2. 倒排索引表有链式单元式两种结构。

    (1)链式倒排索引表

    1. 在链式倒排索引表中,列出了作为次关键字属性的所有取值,并对每一个取值建立有序链表把所有具有相同属性值的主关键字按其递增的顺序或按其在主索引表中的存储地址巡增的顺序链接在一起
      因此,链式倒排索引表包拓三个部分:次关键字、链表长度和有序链表
      在这里插入图片描述
    2. 由于主关键宁技大小依次有序存放上表的长度确定,因此在静态链表中可省去指针域。
    3. 在链式倒排索引表中各个属性链表的长度大小不一,管理起来比较困难。

    (2)单元倒排索引表

    1. 为此引入单元式倒排索引表,在单元式倒排表中,索引项中不存放对象的存储地址,存放该对象所在硬件区域的标识。硬件区域可以是磁盘柱面、磁道或一个页块,以一次I/O操作能存取的存储空间作为硬件区域为最好。为使索引空间最小,在索引中标识这个硬件区域时可以使用一个能转换成地址的二进制数,整个次索引形成一个(二进制数的)位矩阵。
      因此,在单元式例排索引表的各个索引项中存放表示各外存区域是否存有相应数据元素的标识(以0或1表示)。于是,整个单元式倒排索引表将形成一个(二进制数的)位矩阵。
      在这里插入图片描述
    2. 查找时,将相关索引项的二进制位串行进行按位“与”运算,求得所查数据元素在外存区域的区号。
      例如,求计算机系的上海籍男生:
      在这里插入图片描述

    特点

    倒排的优缺点和正排的优缺点整好相反。
    所有正排的【优点】易维护;【缺点】搜索的耗时太长。
    倒排【缺点】在构建索引的时候较为耗时且维护成本较高;【优点】搜索耗时短(在处理复杂的多关键字查询时,可在倒排表中先完成查询的交、并等逻辑运算,得到结果后再对记录进行存取。这样不必对每个记录随机存取,把对记录的查询转换为地址集合的运算,从而提高查找速度)。

    展开全文
  • 一文了解倒排表

    千次阅读 2020-09-15 08:43:49
    倒排表 到排表是搜索引擎的核心架构 假设我们爬取了4个文档,里面的内容如下 基于4个文档,写出我们的词库 [我们,今天,运动,昨天,上,课,什么] 统计词库中的每个单词出现在哪些文档中,显然 我们 出现在[doc1,...
  • 【简单理解】搜索引擎检索-倒排表(倒排索引) 简单介绍倒排索引 倒排索引(Inverted index),也常被称为反向索引、置入档案或反向档案,是一种索引方法,被用来存储在全文搜索下某个单词在一个文档或者一组文档...
  • 关于建立倒排表搜索的一点心得

    千次阅读 2015-05-03 14:36:53
    这几天刚刚用C写了一个关于倒排表搜索词条的程序,程序的效果还是可以,但是当词条数量增加后,算法的效率会大大降低。这里将对算法进行简述,并总结得失。一, 数据结构 将有两个文件作为索引的可持久化被保存。第...
  • 针对当前在最频繁项集挖掘方面的不足, 将集合论引入倒排表以对其进行改进, 然后以此为基础提出了几个命题和推论, 并结合最小支持度阈值动态调整策略, 提出了一个基于改进的倒排表和集合理论的最频繁项集挖掘算法, ...
  • 2.3 建立倒排表文件(引用刘鹏hadoop实战)  在分析完分词,Rank值得计算等问题的解决方案之后,就可以设计相应的MapReduce算法,来建立倒排表,计算,保存Rank和Position等附属信息。  首先定义倒排表存储...
  • 倒排表交集的计算

    千次阅读 2009-05-16 23:43:00
    1. 对倒排表进行排序2. 对排序后的倒排表进行求交集的时间复杂度是o(n + m)3. 两两合并和多路同时合并的效果差不多4.可以采用跳表来加速合并过程,所谓跳表即是 因此在查询时可以根据快表进行跳转,但快表的长度...
  • Lucene 合并倒排表算法之并集

    千次阅读 2010-09-25 13:39:00
    本文继续对倒排表求并集的算法:lucene处理交集时采用的数据结构是一个倒排表的数组,数组的元素是一个个的迭代器来表现每个倒排表.而在求并集的时候则是采用了队列数据结构.在DisjunctionSumScorer类的构造函数中对...
  • Lucene倒排表原理

    千次阅读 2010-08-14 10:53:00
    Lucene倒排索引原理  Lucene是一个高性能的java全文检索工具包,它使用的是倒排文件索引结构。该结构及相应的生成算法如下: <br /> 0)设有两篇文章1和2  文章1的内容为:Tom lives in ...
  • Frame Of Reference压缩算法对于倒排表来说效果很好,但对于需要存储在内存中的Filter缓存等不太合适,两者之间有很多不同之处:倒排表存储在磁盘,针对每个词都需要进行编码,而Filter等内存缓存只会存储那些经常...
  • 倒排索引是什么

    千次阅读 2019-03-04 00:11:34
    倒排索引是什么 倒排索引(英语:Inverted index),也常被称为反向索引、置入档案或反向档案,是一种索引方法,被用来存储在全文搜索下某个单词在一个文档或者一组文档中的存储位置的映射。它是文档检索系统中最...
  • 倒排索引

    2016-02-09 01:07:59
    倒排索引的实现。 一个文件含有几个文件的名字,打开这个文件之后读其他文件的内容,将内容出现的文件号输出。
  • 基于改进倒排表和集合论的TOP-N最频繁项集挖掘算法
  • Lucene 合并倒排表算法之交集

    千次阅读 2010-09-25 10:16:00
    lucene在搜索时,需要对多个倒排表进行merge操作:计算两者间的交集 并集和差集.
  • 针对当前在最频繁项集挖掘方面的不足,将集合论引入倒排表以对其进行改进,然后以此为基础提出了几个命题和推论,并结合最小支持度阈值动态调整策略,提出了一个基于改进的倒排表和集合理论的最频繁项集挖掘算法,...
  • 所有索引项的集合构成该文件的索引。保存在磁盘上的索引又称索引文件。索引技术是组织大型数据库以及磁盘文件的一种重要技术。索引按照结构可以分为线性索引,树形索引和多级索引。所谓线性索引就是将索引项集合...
  • 给出了一个基于音节混淆网络的语音文档内容检索系统,提出了一种基于两阶段解码的查询自动扩展方法,首先通过Viterbi解码算法在混淆音节网格上计算混淆音节的似然得分,然后利用A*解码算法从音节格上产生易混淆的...
  • Lucene倒排索引简述 之索引

    千次阅读 2018-09-27 09:57:42
    Lucene倒排索引的核心内容,索引,你对这部分真的熟悉了吗?那你知道FST用什么地方吗?FST又存储了什么内容呢?有什么功能呢?关于Burst-Trie,你知道Lucene是如何采用它的思想来加速Lucene搜索性能的吗?
  • 信息检索,倒排记录的合并算法实现,用户通过提示输入两个倒排记录,系统自动实现倒排记录的合并,并将合并结果输出。
  • 数据结构链表倒排方法解析及代码,多种方法:创建新链表实现倒排,不创建新链表实现倒排
  • Elasticsearch的倒排索引是什么? 1、倒排索引是搜索引擎的核心。搜索引擎的主要目标是在查找发生搜索条件的文档时提供快速搜索。倒排索引是一种像数据结构一样的散列图,可将用户从单词导向文档或网页。它是搜索...
  • 那么什么是倒排索引呢?在知乎上看到一个讲解elasticsearch的倒排索引的帖子。 链接是:https://zhuanlan.zhihu.com/p/33671444 为什么说elasticsearch的倒排索引的检索速度是比关系型数据库的索引查新更快...
  • 数据结构 c++语言描述 链表倒排。通过建立指针等方法对链表进行倒排
  • java实现读取多个文件构成hashmap创建倒排索引,然后实现布尔查询. 代码比较丑陋,初学者写的。多多包涵!
  • 什么是倒排索引?

    万次阅读 多人点赞 2019-02-17 11:09:08
    什么是倒排索引?    不多说,直接上干货!        见其名知其意,有倒排索引,对应肯定,有正向索引。  正向索引(forward index),反向索引(inverted index)更熟悉的名字是倒排索引。    在...
  • lucene倒排索引搜索原理

    千次阅读 2018-01-12 11:54:27
    什么是倒排索引?搜索的过程是什么样的?会用到哪些算法与数据结构? 前面的内容太宏观,为了照顾大部分没有做过搜索引擎的同学,数据结构与算法部分从正排索引、倒排索引一点点开始。提问:什么是正排索引...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 50,918
精华内容 20,367
关键字:

倒排表是什么