精华内容
下载资源
问答
  • 我在这里使用Java实现了反向索引。 它支持来自文件的输入和简单的查询搜索。 用法: 1)将要索引的文档重命名为filex.txt,其中x为No。 文件。 确保从0开始。 2)将文件复制到.java文件所在的目录中。 否则,请确保...
  • 索引器演示 用于处理反向索引的 Java 代码。
  • 了解关系型数据库的童靴都了解它底层结构采用b+tree的实现,而Lucene则是基于反向索引实现,并将它发挥到了极致。如果不了解Lucene是什么,可以参阅《系列一之全文检索》 目录 1. 什么是反向索引 2. 如何设计反向...

    了解关系型数据库的童靴都了解它底层结构采用b+tree的实现,而Lucene则是基于反向索引实现,并将它发挥到了极致。如果不了解Lucene是什么,可以参阅《系列一之全文检索

    目录

    1. 什么是反向索引

    2. 如何设计反向索引

    2.1 如何快速查询与苍老师有关的新闻?

    2.2 有标题列索引和内容列索引会有什么问题

    2.3 反向索引的记录数【英文/中文】会不会很大

    2.4 开源中文分词器有哪些

    2.5. 你、我、他、my、she、it、标点符号怎么办

    2.6. 当出现了新词了该怎么办

    2.7. 如何进行搜索

    2.8. 反向索引是存储在内存中还是磁盘

    2.9. 反向索引更新问题

    小结

    3. 索引内部原理

    3.1 FST

    3.2 FST-性能测试

    3.3 索引结构

    3.4 倒排表结构

    3.5 正向文件

    3.6 列式存储DocValues


    1. 什么是反向索引

    反向索引英文名叫做 Inverted index,顾名思义,是通常意义下索引的倒置,它相当于一篇文章包含了哪些词,它从词出发,记载了这个词在哪些文档中出现过,由两部分组成——词典和倒排表。这就是:反向索引(Inverted index)。举个例子:

    1I love you
    2I love you too
    4I dislike you

    如果要用单词作为索引,而句子的位置作为被索引的元素,那么索引就发生了倒置:

    I : {1,2,3}
    love : {1,2}
    you : {1,2,3}
    dislike : {3}

    如果要检索I dislike you这句话,那么就可以这么计算 : {1,2,3} ^ {3} ^ {1,2,3} (^是交集)

    2. 如何设计反向索引

    2.1 如何快速查询与苍老师有关的新闻?

    分析:输入的是苍老师,想要得到标题或内容中包含“苍老师”的新闻列表。

    标题列索引:

    内容列索引:

    那如果是这样的文章呢?

    id标题新闻内容
    1Tony 与苍老师一起吃火锅2018年4月1日,Tony 在四川成都出席某活动时,碰巧主办方也邀请了苍老师来提高人气,在主办方的邀请下和苍老师一起吃了个火锅,很爽!

    如果是英文文章(It’s one thing to find the 10 best documents to match your query)好不好分?英文好分(有空格)

    中文则不好分,一定分的话,就必须写一套专门的程序来做这个事情:分词器(有个词的字典,对语句前后字进行组合,与字典匹配,歧义分析)。

    2.2 有标题列索引和内容列索引会有什么问题

    两个索引需要合并,好处是:可以减少访问数据库的次数

    2.3 反向索引的记录数【英文/中文】会不会很大

    英语单词的大致数量是10万个
    汉字汉字的总数已经超过了8万,而常用的只有3500字,《现代汉语规范词典》比《现代汉语词典》收录的字和词数量更多。 前者是13000多字,72000多词,后者是11000多字,69000多词

    结论:量不会很大,30万以内;通过这个索引找文章会很快

    2.4 开源中文分词器有哪些

    准确率、分词效率、中英文混合分词支持,常用中文分词器有:IKAnalyzermmseg4j

    2.5. 你、我、他、my、she、it、标点符号怎么办

    这些词称为:停用词。分词器支持指定/添加停用词,不需要为其创建索引

    2.6. 当出现了新词了该怎么办

    撩妹 老司机、软妹子、直男、腿玩年、苍老师...

    分词器应支持为其词典添加新词

    2.7. 如何进行搜索

    搜索与 “tony OR 苍老师” 相关的新闻,怎么做?

    Step 1: 对搜索输入进行分词,得到:tony 、苍老师

    Step 2:在反向索引中找出包含tony、苍老师的文章列表

    Step3:合并两个列表,排序输出

    2.8. 反向索引是存储在内存中还是磁盘

    大的放磁盘,小的放内存,同时需要做持久化。应该说都有使用,下面会详细讲解

    2.9. 反向索引更新问题

    问1:新增时,需要怎么更新?
    问2:删除时,需要怎么更新?
    问3:修改时,需要怎么更新?

    带着疑问继续向下看

    小结

    我们创建反向索引,大概如下所示:

    3. 索引内部原理

    之前讲过绝大多数全文检索都基于倒排索引来实现,主要用到词典和倒排表。特别是词典结构尤为重要,有很多种词典类数据结构,各有各的优缺点

    数据结构

    优缺点

    排序列表

    实现简单,但性能差

    Hash表

    性能高,内存消耗大

    跳跃表

    占用内存小且可调,但模糊查询支持不好

    B树

    磁盘索引,更新方便,但检索速度慢,数据库应用比较多

    字典树

    查询效率只跟字符串长度有关,但只适合英文词典

    双数组字典树

    可做中文词典,内存占用小,分词工具应用比较多

    Finit state Transducers(FST)

    中文有穷状态转换器,

    		<p style="margin-left:0cm;">优点:内存占用率低,压缩率一般在3倍~20倍之间、模糊查询支持好、查询快<br>
    		缺点:结构复杂、输入要求有序、更新不易</p>
    		</td>
    	</tr></tbody></table></div><p>lucene里面就引入了<strong>term dictonary</strong>的概念,也就是term的字典。在term很多,内存放不下的时候,效率还是需要进一步提升。</p>
    

    Lucene3.0之前使用的也是跳跃表结构,后(Lucene4.0,为了方便实现rangequery或者前缀,后缀等复杂的查询语句)换成了FST,但跳跃表在Lucene其他地方还有应用如倒排表合并和文档号索引。

    3.1 FST

    它功能类似于字典的功能,但其查找是O(1)的,仅仅等于所查找的key长度。FST可以用HashMap代替。但是相比HashMap,FST有以下优点:

    1. 紧凑的结构,通过对词典中单词前缀和后缀的重复利用,压缩了存储空间。
    2. O(len(str))的查询时间复杂度。

    如果不考虑FST的输出,FST本质上是一个最小的,有向无环DFA算法摘自

    对aaaa,bbaa,ccbaa,ddcbaa这4个单词构建FST(注意:单词插入前必须先进行排序,否则就无法生成最小FST)

    如果感兴趣的话,可以从源码org.apache.lucene.util.fst.Builder的add()方法作为切入口一步步去分析

    3.2 FST-性能测试

    对HashMap、TreeMap、FST进行100万数据性能测试

    
     
    1. String inputs={ "abc", "abd", "acf", "acg"}; //keys
    2. long outputs={ 1, 3, 5, 7}; //values
    3. FST<Long> fst= new FST<>();
    4. for( int i= 0;i<inputs.length;i++) {
    5. fst. add(inputs[i],outputs[i])
    6. }
    7. //get
    8. Long value=fst. get( "abd"); //得到3
    9. //迭代
    10. BytesRefFSTEnum<Long> iterator= new BytesRefFSTEnum<>(fst);
    11. while(iterator.next!= null){...}
    数据结构HashMapTreeMapFST
    构建时间(ms)1855001512
    查询所有key(ms)106218890

    从上面结果可以看出,FST性能基本跟HaspMap差距不大,但FST有个不可比拟的优势就是占用内存小,只有HashMap10分之一左右,这对大数据规模检索是至关重要的,毕竟速度再快放不进内存也是没用的。因此一个合格的词典结构要求有:

    • 查询速度。
    • 内存占用。
    • 内存+磁盘结合。

    3.3 索引结构

    存储文件

    在介绍索引结构之前,先看一下lucene的存储文件,

    说明一下:属于一个段的所有文件具有相同的名称和不同的扩展名。当使用复合索引文件,这些文件(除了段信息文件、锁文件和已删除的文档文件)将压缩成单个.cfs文件。当任何索引文件被保存到目录时,它被赋予一个从未被使用过的文件名字。

    名称文件扩展名简短描述
    Segments Filesegments_N保存了一个提交点(a commit point)的信息
    Lock Filewrite.lock防止多个IndexWriter同时写到一份索引文件中
    Segment Info.si保存了索引段的元数据信息
    Compound File.cfs,.cfe一个可选的虚拟文件,把所有索引信息都存储到复合索引文件中
    Fields.fnm保存fields的相关信息
    Field Index.fdx保存指向field data的指针
    Field Data.fdt文档存储的字段的值
    Term Dictionary.timterm词典,存储term信息
    Term Index.tip到Term Dictionary的索引
    Frequencies.doc由包含每个term以及频率的docs列表组成
    Positions.pos存储出现在索引中的term的位置信息
    Payloads.pay存储额外的per-position元数据信息,例如字符偏移和用户payloads
    Norms.nvd,.nvm.nvm文件保存索引字段加权因子的元数据,.nvd文件保存索引字段加权数据
    Per-Document Values.dvd,.dvm.dvm文件保存索引文档评分因子的元数据,.dvd文件保存索引文档评分数据
    Term Vector Index.tvx将偏移存储到文档数据文件中
    Term Vector Documents.tvd包含有term vectors的每个文档信息
    Term Vector Fields.tvf字段级别有关term vectors的信息
    Live Documents.liv哪些是有效文件的信息
    Point values.dii,.dim保留索引点,如果有的话

    索引文件结构

    Lucene经多年演进优化,现在的一个索引文件结构如图所示,基本可以分为三个部分:词典、倒排表、正向文件、列式存储DocValues。索引结构中,不仅仅保存了反向信息,还保存了正向信息。

    正向信息

    (1)按层次保存了从索引,一直到词的包含关系:索引(Index)-->段(segment)->文档(Document)->域(Field)->词(Term)
    (2)也即此索引包含了那些段,每个段包含了那些文档,每个文档包含了那些域,每个域包含了那些词。segments_N保存了此索引包含多少个段,每个段包含多少篇文档。

    XXX.fnm保存此段包含的所有文档,每篇文档包含了多少域,每个域保存了那些信息。
    XXX.fdx,XXX.fdt保存了此段包含的所有文档,每篇文档包含了多少域,每个域保存了那些信息。

    反向信息

    (1)保存了词典到倒排表的映射:词(Term) --> 文档(Document)
    (2)含反向信息的文件有:
          #XXX.tis,XXX.tii保存了词典(Term Dictionary),也即此段包含的所有的词按字典顺序的排序
          #XXX.frq保存了倒排表,也即包含每个词的文档ID列表。
          #XXX.prx保存了倒排表中每个词在包含此词的文档中的位置。

    它的特点就是:

    1. 词查找复杂度为O(len(str))
    2. 共享前缀、节省空间
    3. 内存存放前缀索引、磁盘存放后缀词块

    我们往索引库里插入四个单词abd、abe、acf、acg,看看它的索引文件内容。

    • tip部分,每列一个FST索引,所以会有多个FST,每个FST存放前缀和后缀块指针,这里前缀就为a、ab、ac
    • tim里面存放后缀块和词的其他信息如倒排表指针、TFDF等
    • doc文件里就为每个单词的倒排表

    它的检索过程分为三个步骤:

    1. 内存加载tip文件,通过FST匹配前缀找到后缀词块位置。
    2. 根据词块位置,读取磁盘中tim文件中后缀块并找到后缀和相应的倒排表位置信息。
    3. 根据倒排表位置去doc文件中加载倒排表。

    这里就会有两个问题,第一就是前缀如何计算,第二就是后缀如何写磁盘并通过FST定位,下面将描述下Lucene构建FST过程:已知FST要求输入有序,所以Lucene会将解析出来的文档单词预先排序,然后构建FST,我们假设输入为abd,abd,acf,acg,

    1. 插入abd时,没有输出。
    2. 插入abe时,计算出前缀ab,但此时不知道后续还不会有其他以ab为前缀的词,所以此时无输出。
    3. 插入acf时,因为是有序的,知道不会再有ab前缀的词了,这时就可以写tip和tim了,tim中写入后缀词块d、e和它们的倒排表位置ip_d,ip_e,tip中写入a,b和以ab为前缀的后缀词块位置(真实情况下会写入更多信息如词频等)。
    4. 插入acg时,计算出和acf共享前缀ac,这时输入已经结束,所有数据写入磁盘。tim中写入后缀词块f、g和相对应的倒排表位置,tip中写入c和以ac为前缀的后缀词块位置。

    以上是一个简化过程,Lucene的FST实现的主要优化策略有:

    1. 最小后缀数。Lucene对写入tip的前缀有个最小后缀数要求,默认25,这时为了进一步减少内存使用。如果按照25的后缀数,那么就不存在ab、ac前缀,将只有一个跟节点,abd、abe、acf、acg将都作为后缀存在tim文件中。我们的10g的一个索引库,索引内存消耗只占20M左右。
    2. 前缀计算基于byte,而不是char,这样可以减少后缀数,防止后缀数太多,影响性能。如对宇(e9 b8 a2)、守(e9 b8 a3)、安(e9 b8 a4)这三个汉字,FST构建出来,不是只有根节点,三个汉字为后缀,而是从unicode码出发,以e9、b8为前缀,a2、a3、a4为后缀,如下图:

    3.4 倒排表结构

    倒排表就是文档号集合,但怎么存,怎么取也有很多讲究,Lucene现使用的倒排表结构叫Frame of reference,它主要有两个特点:

    1. 数据压缩,可以看上图怎么将6个数字从原先的24bytes压缩到7bytes
    2. 跳跃表加速合并,因为布尔查询时,and 和or 操作都需要合并倒排表,这时就需要快速定位相同文档号,所以利用跳跃表来进行相同文档号查找。可以参考官方

    3.5 正向文件

    正向文件指的就是原始文档,Lucene对原始文档也提供了存储功能,它存储特点就是分块+压缩,fdt文件就是存放原始文档的文件,它占了索引库90%的磁盘空间,fdx文件为索引文件,通过文档号(自增数字)快速得到文档位置,它们的文件结构如下:

    • fnm中为元信息存放了各列类型、列名、存储方式等信息。
    • fdt为文档值,里面一个chunk就是一个块,Lucene索引文档时,先缓存文档,缓存大于16KB时,就会把文档压缩存储。一个chunk包含了该chunk起始文档、多少个文档、压缩后的文档内容。
    • fdx为文档号索引,倒排表存放的时文档号,通过fdx才能快速定位到文档位置即chunk位置,它的索引结构比较简单,就是跳跃表结构,首先它会把1024个chunk归为一个block,每个block记载了起始文档值,block就相当于一级跳表。

    查找文档,就分为三步:

    第一步二分查找block,定位属于哪个block。
    第二步就是根据从block里根据每个chunk的起始文档号,找到属于哪个chunk和chunk位置。
    第三步就是去加载fdt的chunk,找到文档。这里还有一个细节就是存放chunk起始文档值和chunk位置不是简单的数组,而是采用了平均值压缩法。所以第N个chunk的起始文档值由 DocBase + AvgChunkDocs * n + DocBaseDeltas[n]恢复而来,而第N个chunk再fdt中的位置由 StartPointerBase + AvgChunkSize * n + StartPointerDeltas[n]恢复而来。

    总结lucene对原始文件的存放是行是存储,并且为了提高空间利用率,是多文档一起压缩,因此取文档时需要读入和解压额外文档,因此取文档过程非常依赖随机IO,以及lucene虽然提供了取特定列,但从存储结构可以看出,并不会减少取文档时间。

    3.6 列式存储DocValues

    我们知道倒排索引能够解决从词到文档的快速映射,但当我们需要对检索结果进行分类、排序、数学计算等聚合操作时需要文档号到值的快速映射,而原先不管是倒排索引还是行式存储的文档都无法满足要求。原先4.0版本之前,Lucene实现这种需求是通过FieldCache,它的原理是通过按列逆转倒排表将(field value ->doc)映射变成(doc -> field value)映射,但这种实现方法有着两大显著问题:

    1.  构建时间长。
    2.  内存占用大,易OutOfMemory,且影响垃圾回收

    因此4.0版本后Lucene推出了DocValues来解决这一问题,它和FieldCache一样,都为列式存储,但它有如下优点:

    1. 预先构建,写入文件。
    2. 基于映射文件来做,脱离JVM堆内存,系统调度缺页。

    DocValues这种实现方法只比内存FieldCache慢大概10~25%,但稳定性却得到了极大提升。

    Lucene目前有五种类型的DocValues:NUMERIC、BINARY、SORTED、SORTED_SET、SORTED_NUMERIC,针对每种类型Lucene都有特定的压缩方法。如对NUMERIC类型即数字类型,数字类型压缩方法很多,如:增量、表压缩、最大公约数,根据数据特征选取不同压缩方法。SORTED类型即字符串类型,压缩方法就是表压缩:预先对字符串字典排序分配数字ID,存储时只需存储字符串映射表,和数字数组即可,而这数字数组又可以采用NUMERIC压缩方法再压缩,图示如下:

    这样就将原先的字符串数组变成数字数组,一是减少了空间,文件映射更有效率,二是原先变成访问方式变成固长访问。对DocValues的应用,ElasticSearch功能实现地更系统、更完整,即ElasticSearch的Aggregations——聚合功能,它的聚合功能分为三类:

    1. Metric -> 统计
        典型功能:sum、min、max、avg、cardinality、percent等
    2. Bucket ->分组
        典型功能:日期直方图,分组,地理位置分区
    3. Pipline -> 基于聚合再聚合
        典型功能:基于各分组的平均值求最大值。

    基于这些聚合功能,ElasticSearch不再局限与检索,而能够回答如下SQL的问题
    select gender,count(*),avg(age) from employee where dept='sales' group by gender //销售部门男女人数、平均年龄是多少

    我们看下ElasticSearch如何基于倒排索引和DocValues实现上述SQL的

    1. 从倒排索引中找出销售部门的倒排表。
    2. 根据倒排表去性别的DocValues里取出每个人对应的性别,并分组到Female和Male里。
    3. 根据分组情况和年龄DocValues,计算各分组人数和平均年龄
    4. 因为ElasticSearch是分区的,所以对每个分区的返回结果进行合并就是最终的结果。

    上面就是ElasticSearch进行聚合的整体流程,也可以看出ElasticSearch做聚合的一个瓶颈就是最后一步的聚合只能单机聚合,也因此一些统计会有误差,比如count(*) group by producet limit 5,最终总数不是精确的。因为单点内存聚合,所以每个分区不可能返回所有分组统计信息,只能返回部分,汇总时就会导致最终结果不正确,具体如下:

    Shard 1    

    Shard 2      

    Shard 3

    Product A (25)

    Product A (30)

    Product A (45)

    Product B (18)

    Product B (25)

    Product C (44)

    Product C (6)

    Product F (17)

    Product Z (36)

    Product D (3)

    Product Z (16)

    Product G (30)

    Product E (2)

    Product G (15)

    Product E (29)

    Product F (2)

    Product H (14)

    Product H (28)

    Product G (2)

    Product I (10)

    Product Q (2)

    Product H (2)

    Product Q (6)

    Product D (1)

    Product I (1)

    Product J (8)

     

    Product J (1)

    Product C (4)

     

    count(*) group by producet limit 5,每个节点返回的数据如下:

    Shard 1

    Shard 2

    Shard 3

    Product A (25)

     Product A (30)     

    Product A (45)

    Product B (18)

    Product B (25)     

    Product C (44)

    Product C (6)

    Product F (17)

    Product Z (36)

    Product D (3)

    Product Z (16)  

     Product G (30)

    Product E (2)

    Product G (15)

    Product E (29)

    合并后:

    Merged

    Product A (100)

    Product Z (52)

    Product C (50)

    Product G (45)

    Product B (43)

    商品A的总数是对的,因为每个节点都返回了,但商品C在节点2因为排不到前5所以没有返回,因此总数是错的。

    展开全文
  • 目录 正向索引:从文档到单词。 反向索引:从词到文档。...在谈论搜索引擎的索引时,会涉及到两个概念正向索引(forward index)和反向索引(inverted index)。&amp;lt;/p&amp;gt; 听上去,它们...
    
    

    在谈论搜索引擎的索引时,会涉及到两个概念正向索引(forward index)和反向索引(inverted index)。

    听上去,它们像是一种全新数据结构。让我们看看维基百科的解释。

    正向索引:从文档到单词。

    假如有三个 txt 文档,

    • Document_1: The cow says moo.
    • Document_2: The cat and the hat.
    • Document_3: The dish ran away with the spoon.

    解析每个文档出现的单词,然后建立从文档 (document) 到词组 (words) 的映射关系,这就是正向索引。

    DocumentWords
    Document_1the,cow,says,moo
    Document_2the,cat,and,the,hat
    Document_3the,dish,ran,away,with,the,spoon

    反向索引:从词到文档。

    反向索引方向则是正向索引的逆向,建立从单词 (word) 到文档(document lsit) 的映射关系。

    WordDocuments
    theDocument_1, Document_3, Document_4, Document_5, Document_7
    cowDocument_2, Document_3, Document_4
    saysDocument_5
    mooDocument_6

    怎么看这都不是什么全新的数据结构啊?

    现实世界中的索引

    使用 index 快速检索信息并不是21世纪新的发明。

    1876年,杜威发明图书分类法(Dewey Decimal Classification)。我们通过这个方法,给图书建立索引,按书架快速查找(get)和摆放(set)书籍。

    分类图书
    哲学与心理学《苏菲的世界》,《理想国》
    宗教《圣经》,《古兰经》
    社会科学《宏观经济学》,《微观经济学》
    ......

    通常书籍最后的章节会罗列所有涉及到的行业术语,你可以通过这个列表查看哪一页交代了这些术语,并快速跳转到定义的地方,这也是一种索引 word -> page

    问题

    index 从来都不是一个新发明,从19世纪的图书分类法,到21世纪的数据库索引,我们一直在用。而且当大家提起索引这个术语时,脑海中都是按 word -> document 方向来建立。

    反向索引,其实就是普通的索引嘛。

    为什么有人仍然坚持创建出一个新的术语 inverted index ?

    此外 forward index 在现实世界中根本毫无用处,压根不能称之为索引,为什么要造这个词?

    无论是 Stack Overflow 还是 ElasticSearch 的官方文档也只是一而再,再而三的强调「是什么」,并没有回答「为什么」[1]。

    最终 Stack Overflow 一个不起眼的回答道出了玄机。[2]

    索引(index) 是个很老的概念。但是搜索引擎横空出世之后,却把这个概念包装了一下,称之为「反向索引」。并不是有什么本质性的区别,乃是因为搜索引擎在创建会先解析文档的关键词,创建一个正向索引,然后再基于正向索引,把方向逆转过来,创建反向索引,仅此而已。

    This should be the accepted answer as it answers the question why we call an index "inverted" even if it is just what everybody thinks of a "normal index". A SQL b-tree index stores for each word a pointer to all rows ("documents") containing it. There we call it "index". But in search engines we suddenly call this exact same procedure "inverted index". Not because it's fundamentally different, but because we first created a "forward index" (split text) and then "inverse" it. So, all in all, the name "inverse" comes from the process of creating it, not from the final structure of the index.

    搜索引擎如何创建索引?

    如果要进一步理解正向索引,需要了结搜索引擎 analyzer 的基本工作步骤。所有的文档在建立索引之前都要经过一个 pipeline。

    1. character filter,过滤一些词,比如 html 标签。
    2. tokenization。分词,转换时态,转换单复数等。
    3. token filter。过滤一些token,比如 the,a,an,this,these 等停用词。

    最终 pipeline 的输出就是一个单词列表。我猜测这个单词列表就用来创建正向索引。

    结论

    说到底,反向索引就是生活中处处可见的普通索引。

    反向索引之所以在搜索引擎中中被冠以新词,是因为在它之前要先创建正向索引。

    Reference

    1. Elasticsearch: Inverted Index

    2. Stack Overflow 的这个回答 没有被选为最佳答案,真是可惜。

    原文链接

    http://mednoter.com/inverted-index.html

    展开全文
  • 本作业探讨通过trie和反向索引的实现来检索信息。 提供了骨架代码。 目的 该作业提供对trie和反向索引数据结构以及信息检索领域的洞察力。 背景 对于此作业,您应该 了解特里数据结构及其相关操作 了解倒排索引数据...
  • 反向索引 1.1 反向索引的定义 反向索引作为B-tree索引的一个分支,主要是在创建索引时,针对索引列的索引键值进行字节反转,进而实现分散存放到不同叶子节点块的目的。 1.2 反向索引针对的问题 使用...
    • 一 反向索引

      1.1 反向索引的定义

      • 反向索引作为B-tree索引的一个分支,主要是在创建索引时,针对索引列的索引键值进行字节反转,进而实现分散存放到不同叶子节点块的目的。

       

      1.2 反向索引针对的问题

      • 使用传统的B-tree索引,当索引的列是按顺序产生时,相应的索引键值会基本分布在同一个叶块中。当用户对该列进行操作时,难免会发生索引块的争用。
      • 使用反向索引,将索引列的键值进行反转,实现顺序的键值分散到不同的叶块中,从而减少索引块的争用。
      • 例如:键值1001、1002、1003,反转后1001、2001、3001,进而分散到不用的叶子节点块中。

       

      1.3 反向索引应用场景

      • 索引块成为热点块
      • rac环境
        • rac环境下中多节点访问访问数据呈现密集且集中的特点,索引热块的产生较高。
        • 在范围检索不高的rac环境中使用反向索引可有效提高性能。

       

      1.4 反向索引的优点与缺点

      • 优点:降低索引叶子块的争用问题,提升系统性能。
      • 缺点:对于范围检索,例如:between,>,<时,反向索引无法引用,进而导致全表扫面的产生,降低系统性能。

       

      1.5 反向索引示例说明

    • -- 创建两张相同结构的表,内部结构及数据均引用scott用户下的emp表SQL> select count(*) from test01;
      
        COUNT(*)
      ----------
      
      SQL> select count(*) from test02;
      
        COUNT(*)
      ----------
      
      
      
      --针对表TEST01的empno列,添加B-tree索引 
      SQL> create index PK_TEST01 on TEST01(EMPNO);
      Index created.
      
      --针对表TEST02的empno列,添加反向索引
      SQL> create index PK_REV_TEST02 on TEST02(EMPNO) REVERSE;
      Index created.
      
      
      --验证上面的索引,NORMAL/REV表明为反向索引
      SQL> select TABLE_NAME,INDEX_NAME,INDEX_TYPE from user_indexes where INDEX_NAME like '%TEST%';
      
      TABLE_NAME           INDEX_NAME           INDEX_TYPE
      -------------------- -------------------- --------------------
      TEST01               PK_TEST01            NORMAL
      TEST02               PK_REV_TEST02        NORMAL/REV
      
      
      --打开会话追踪
      SQL> set autotrace traceonly
      
      
      --相同条件查询,观察两表的执行计划
      SQL> select * from TEST01 where empno=7369;
      Execution Plan
      ----------------------------------------------------------
      Plan hash value: 515586510
      
      -----------------------------------------------------------------------------------------
      | Id  | Operation                   | Name      | Rows  | Bytes | Cost (%CPU)| Time     |
      -----------------------------------------------------------------------------------------
      |   0 | SELECT STATEMENT            |           |     1 |    87 |     2   (0)| 00:00:01 |
      |   1 |  TABLE ACCESS BY INDEX ROWID| TEST01    |     1 |    87 |     2   (0)| 00:00:01 |
      |*  2 |   INDEX RANGE SCAN          | PK_TEST01 |     1 |       |     1   (0)| 00:00:01 |
      -----------------------------------------------------------------------------------------
      
      Predicate Information (identified by operation id):
      ---------------------------------------------------
      - access("EMPNO"=7369)
      
      Note
      -----
         - dynamic sampling used for this statement (level=2)
      
      
      Statistics
      ----------------------------------------------------------
       recursive calls
       db block gets
       consistent gets
       physical reads
       redo size
       bytes sent via SQL*Net to client
       bytes received via SQL*Net from client
       SQL*Net roundtrips to/from client
       sorts (memory)
       sorts (disk)
       rows processed
      
      
      
      
      SQL> select * from TEST02 where empno=7369;
      
      Execution Plan
      ----------------------------------------------------------
      Plan hash value: 1053012716
      
      ---------------------------------------------------------------------------------------------
      | Id  | Operation                   | Name          | Rows  | Bytes | Cost (%CPU)| Time     |
      ---------------------------------------------------------------------------------------------
      |   0 | SELECT STATEMENT            |               |     1 |    87 |     2   (0)| 00:00:01 |
      |   1 |  TABLE ACCESS BY INDEX ROWID| TEST02        |     1 |    87 |     2   (0)| 00:00:01 |
      |*  2 |   INDEX RANGE SCAN          | PK_REV_TEST02 |     1 |       |     1   (0)| 00:00:01 |
      ---------------------------------------------------------------------------------------------
      
      Predicate Information (identified by operation id):
      ---------------------------------------------------
      - access("EMPNO"=7369)
      
      Note
      -----
         - dynamic sampling used for this statement (level=2)
      
      
      Statistics
      ----------------------------------------------------------
       recursive calls
       db block gets
       consistent gets
       physical reads
       redo size
       bytes sent via SQL*Net to client
       bytes received via SQL*Net from client
       SQL*Net roundtrips to/from client
       sorts (memory)
       sorts (disk)
       rows processed
      
      
      
      
      -- 相同范围条件查询,观察两表的执行计划
      SQL> select * from TEST01 where empno between 7350 and 7500;
      
      Execution Plan
      ----------------------------------------------------------
      Plan hash value: 515586510
      
      -----------------------------------------------------------------------------------------
      | Id  | Operation                   | Name      | Rows  | Bytes | Cost (%CPU)| Time     |
      -----------------------------------------------------------------------------------------
      |   0 | SELECT STATEMENT            |           |     2 |   174 |     2   (0)| 00:00:01 |
      |   1 |  TABLE ACCESS BY INDEX ROWID| TEST01    |     2 |   174 |     2   (0)| 00:00:01 |
      |*  2 |   INDEX RANGE SCAN          | PK_TEST01 |     2 |       |     1   (0)| 00:00:01 |
      -----------------------------------------------------------------------------------------
      
      Predicate Information (identified by operation id):
      ---------------------------------------------------
      - access("EMPNO">=7350 AND "EMPNO"<=7500)
      
      Note
      -----
         - dynamic sampling used for this statement (level=2)
      
      
      Statistics
      ----------------------------------------------------------
       recursive calls
       db block gets
       consistent gets
       physical reads
       redo size
       bytes sent via SQL*Net to client
       bytes received via SQL*Net from client
       SQL*Net roundtrips to/from client
       sorts (memory)
       sorts (disk)
       rows processed
      
      
      
      
      
      SQL> select * from TEST02 where empno between 7350 and 7500;
      
      Execution Plan
      ----------------------------------------------------------
      Plan hash value: 3294238222
      
      ----------------------------------------------------------------------------
      | Id  | Operation         | Name   | Rows  | Bytes | Cost (%CPU)| Time     |
      ----------------------------------------------------------------------------
      |   0 | SELECT STATEMENT  |        |     2 |   174 |     3   (0)| 00:00:01 |
      |*  1 |  TABLE ACCESS FULL| TEST02 |     2 |   174 |     3   (0)| 00:00:01 |
      ----------------------------------------------------------------------------
      
      Predicate Information (identified by operation id):
      ---------------------------------------------------
      - filter("EMPNO">=7350 AND "EMPNO"<=7500)
      
      Note
      -----
         - dynamic sampling used for this statement (level=2)
      
      
      Statistics
      ----------------------------------------------------------
       recursive calls
       db block gets
       consistent gets0  redo size
       bytes sent via SQL*Net to client
       bytes received via SQL*Net from client
       SQL*Net roundtrips to/from client
       sorts (memory)
       sorts (disk)
       rows processed

      通过上面的示例可以看到,当使用between条件进行范围查询时,采用反向索引的表,并没有使用索引,而是采用了全表扫面的方式进行检索。

    转载于:https://www.cnblogs.com/lucifa/p/10165940.html

    展开全文
  • 1.正向索引 正向索引(正排索引):正排表是以文档的ID为关键字,表中记录文档中每个字的位置信息,查找时扫描表中每个文档中字的信息直到找出所有包含查询关键字的文档。 “文档1”的ID > 单词1:出现次数,出现...

    1.正向索引

    正向索引(正排索引):正排表是以文档的ID为关键字,表中记录文档中每个字的位置信息,查找时扫描表中每个文档中字的信息直到找出所有包含查询关键字的文档。

    “文档1”的ID > 单词1:出现次数,出现位置列表;单词2:出现次数,出现位置列表;…………。
    “文档2”的ID > 此文档出现的关键词列表。
    在这里插入图片描述

    正排表结构如图1所示,这种组织方法在建立索引的时候结构比较简单,建立比较方便且易于维护;因为索引是基于文档建立的,若是有新的文档加入,直接为该文档建立一个新的索引块,挂接在原来索引文件的后面。若是有文档删除,则直接找到该文档号文档对应的索引信息,将其直接删除。但是在查询的时候需对所有的文档进行扫描以确保没有遗漏,这样就使得检索时间大大延长,检索效率低下。

    尽管正排表的工作原理非常的简单,但是由于其检索效率太低,除非在特定情况下,否则实用性价值不大。

    反向索引

    反向索引(倒排索引):倒排表以字或词为关键字进行索引,表中关键字所对应的记录表项记录了出现这个字或词的所有文档,一个表项就是一个字表段,它记录该文档的ID和字符在该文档中出现的位置情况。

    由于每个字或词对应的文档数量在动态变化,所以倒排表的建立和维护都较为复杂,但是在查询的时候由于可以一次得到查询关键字所对应的所有文档,所以效率高于正排表。在全文检索中,检索的快速响应是一个最为关键的性能,而索引建立由于在后台进行,尽管效率相对低一些,但不会影响整个搜索引擎的效率。

    倒排索引的结构如下:
    “关键词1”:“文档1”的ID,“文档2”的ID,…………。
    “关键词2”:带有此关键词的文档ID列表。
    在这里插入图片描述

    3.倒排索引介绍

    3.1.单词——文档矩阵

    单词-文档矩阵是表达两者之间所具有的一种包含关系的概念模型,图1展示了其含义。下图的每列代表一个文档,每行代表一个单词,打对勾的位置代表包含关系。
    在这里插入图片描述

    从纵向即文档这个维度来看,每列代表文档包含了哪些单词,比如文档1包含了词汇1和词汇4,而不包含其它单词。从横向即单词这个维度来看,每行代表了哪些文档包含了某个单词。比如对于词汇1来说,文档1和文档4中出现过单词1,而其它文档不包含词汇1。矩阵中其它的行列也可作此种解读。

    搜索引擎的索引其实就是实现“单词-文档矩阵”的具体数据结构。可以有不同的方式来实现上述概念模型,比如“倒排索引”、“签名文件”、“后缀树”等方式。但是各项实验数据表明,“倒排索引”是实现单词到文档映射关系的最佳实现方式,所以本文主要介绍“倒排索引”的技术细节。

    3.2.倒排索引基本概念

    • 文档(Document):一般搜索引擎的处理对象是互联网网页,而文档这个概念要更宽泛些,代表以文本形式存在的存储对象,相比网页来说,涵盖更多种形式,比如Word,PDF,html,XML等不同格式的文件都可以称之为文档。再比如一封邮件,一条短信,一条微博也可以称之为文档。在本书后续内容,很多情况下会使用文档来表征文本信息。

    • 文档集合(Document Collection):由若干文档构成的集合称之为文档集合。比如海量的互联网网页或者说大量的电子邮件都是文档集合的具体例子。

    • 文档编号(Document ID):在搜索引擎内部,会将文档集合内每个文档赋予一个唯一的内部编号,以此编号来作为这个文档的唯一标识,这样方便内部处理,每个文档的内部编号即称之为“文档编号”,后文有时会用DocID来便捷地代表文档编号。

    • 单词编号(Word ID):与文档编号类似,搜索引擎内部以唯一的编号来表征某个单词,单词编号可以作为某个单词的唯一表征。

    • 倒排索引(Inverted Index):倒排索引是实现“单词-文档矩阵”的一种具体存储形式,通过倒排索引,可以根据单词快速获取包含这个单词的文档列表。倒排索引主要由两个部分组成:“单词词典”和“倒排文件”。

    • 单词词典(Lexicon):搜索引擎的通常索引单位是单词,单词词典是由文档集合中出现过的所有单词构成的字符串集合,单词词典内每条索引项记载单词本身的一些信息以及指向“倒排列表”的指针。

    • 倒排列表(PostingList):倒排列表记载了出现过某个单词的所有文档的文档列表及单词在该文档中出现的位置信息,每条记录称为一个倒排项(Posting)。根据倒排列表,即可获知哪些文档包含某个单词。

    • 倒排文件(Inverted File):所有单词的倒排列表往往顺序地存储在磁盘的某个文件里,这个文件即被称之为倒排文件,倒排文件是存储倒排索引的物理文件。

      关于这些概念之间的关系,通过下图可以比较清晰的看出来。
      在这里插入图片描述

    3.3.倒排索引简单实例

    倒排索引从逻辑结构和基本思路上来讲非常简单。下面我们通过具体实例来进行说明,使得读者能够对倒排索引有一个宏观而直接的感受。

    假设文档集合包含五个文档,每个文档内容下图所示,在图中最左端一栏是每个文档对应的文档编号。我们的任务就是对这个文档集合建立倒排索引。 
    在这里插入图片描述
                 文档集合

    中文和英文等语言不同,单词之间没有明确分隔符号,所以首先要用分词系统将文档自动切分成单词序列。这样每个文档就转换为由单词序列构成的数据流,为了系统后续处理方便,需要对每个不同的单词赋予唯一的单词编号,同时记录下哪些文档包含这个单词,在如此处理结束后,我们可以得到最简单的倒排索引(参考图3-4)。在图4中,“单词ID”一栏记录了每个单词的单词编号,第二栏是对应的单词,第三栏即每个单词对应的倒排列表。比如单词“谷歌”,其单词编号为1,倒排列表为{1,2,3,4,5},说明文档集合中每个文档都包含了这个单词。
                  (参考图3-4)图4

    之所以说图4所示倒排索引是最简单的,是因为这个索引系统只记载了哪些文档包含某个单词,而事实上,索引系统还可以记录除此之外的更多信息。图5是一个相对复杂些的倒排索引,与图4的基本索引系统比,在单词对应的倒排列表中不仅记录了文档编号,还记载了单词频率信息(TF),即这个单词在某个文档中的出现次数,之所以要记录这个信息,是因为词频信息在搜索结果排序时,计算查询和文档相似度是很重要的一个计算因子,所以将其记录在倒排列表中,以方便后续排序时进行分值计算。在图5的例子里,单词“创始人”的单词编号为7,对应的倒排列表内容为:(3:1),其中的3代表文档编号为3的文档包含这个单词,数字1代表词频信息,即这个单词在3号文档中只出现过1次,其它单词对应的倒排列表所代表含义与此相同。     
    在这里插入图片描述
                  图 5 带有单词频率信息的倒排索引

    实用的倒排索引还可以记载更多的信息,图6所示索引系统除了记录文档编号和单词频率信息外,额外记载了两类信息,即每个单词对应的“文档频率信息”(对应图6的第三栏)以及在倒排列表中记录单词在某个文档出现的位置信息。

    在这里插入图片描述
                 图6 带有单词频率、文档频率和出现位置信息的倒排索引

    “文档频率信息”代表了在文档集合中有多少个文档包含某个单词,之所以要记录这个信息,其原因与单词频率信息一样,这个信息在搜索结果排序计算中是非常重要的一个因子。而单词在某个文档中出现的位置信息并非索引系统一定要记录的,在实际的索引系统里可以包含,也可以选择不包含这个信息,之所以如此,因为这个信息对于搜索系统来说并非必需的,位置信息只有在支持“短语查询”的时候才能够派上用场。

    以单词“拉斯”为例,其单词编号为8,文档频率为2,代表整个文档集合中有两个文档包含这个单词,对应的倒排列表为:{(3;1;<4>),(5;1;<4>)},其含义为在文档3和文档5出现过这个单词,单词频率都为1,单词“拉斯”在两个文档中的出现位置都是4,即文档中第四个单词是“拉斯”。

    图6所示倒排索引已经是一个非常完备的索引系统,实际搜索系统的索引结构基本如此,区别无非是采取哪些具体的数据结构来实现上述逻辑结构。

    有了这个索引系统,搜索引擎可以很方便地响应用户的查询,比如用户输入查询词“Facebook”,搜索系统查找倒排索引,从中可以读出包含这个单词的文档,这些文档就是提供给用户的搜索结果,而利用单词频率信息、文档频率信息即可以对这些候选搜索结果进行排序,计算文档和查询的相似性,按照相似性得分由高到低排序输出,此即为搜索系统的部分内部流程,具体实现方案本书第五章会做详细描述。

    3.4. 单词词典

    单词词典是倒排索引中非常重要的组成部分,它用来维护文档集合中出现过的所有单词的相关信息,同时用来记载某个单词对应的倒排列表在倒排文件中的位置信息。在支持搜索时,根据用户的查询词,去单词词典里查询,就能够获得相应的倒排列表,并以此作为后续排序的基础。
    对于一个规模很大的文档集合来说,可能包含几十万甚至上百万的不同单词,能否快速定位某个单词,这直接影响搜索时的响应速度,所以需要高效的数据结构来对单词词典进行构建和查找,常用的数据结构包括哈希加链表结构和树形词典结构。

    3.4.1 哈希加链表

       图7是这种词典结构的示意图。这种词典结构主要由两个部分构成:
    

    主体部分是哈希表,每个哈希表项保存一个指针,指针指向冲突链表,在冲突链表里,相同哈希值的单词形成链表结构。之所以会有冲突链表,是因为两个不同单词获得相同的哈希值,如果是这样,在哈希方法里被称做是一次冲突,可以将相同哈希值的单词存储在链表里,以供后续查找。
    在这里插入图片描述

    在建立索引的过程中,词典结构也会相应地被构建出来。比如在解析一个新文档的时候,对于某个在文档中出现的单词T,首先利用哈希函数获得其哈希值,之后根据哈希值对应的哈希表项读取其中保存的指针,就找到了对应的冲突链表。如果冲突链表里已经存在这个单词,说明单词在之前解析的文档里已经出现过。如果在冲突链表里没有发现这个单词,说明该单词是首次碰到,则将其加入冲突链表里。通过这种方式,当文档集合内所有文档解析完毕时,相应的词典结构也就建立起来了。

    在响应用户查询请求时,其过程与建立词典类似,不同点在于即使词典里没出现过某个单词,也不会添加到词典内。以图7为例,假设用户输入的查询请求为单词3,对这个单词进行哈希,定位到哈希表内的2号槽,从其保留的指针可以获得冲突链表,依次将单词3和冲突链表内的单词比较,发现单词3在冲突链表内,于是找到这个单词,之后可以读出这个单词对应的倒排列表来进行后续的工作,如果没有找到这个单词,说明文档集合内没有任何文档包含单词,则搜索结果为空。

    3.4.2 树形结构

    B树(或者B+树)是另外一种高效查找结构,图8是一个 B树结构示意图。B树与哈希方式查找不同,需要字典项能够按照大小排序(数字或者字符序),而哈希方式则无须数据满足此项要求。

    B树形成了层级查找结构,中间节点用于指出一定顺序范围的词典项目存储在哪个子树中,起到根据词典项比较大小进行导航的作用,最底层的叶子节点存储单词的地址信息,根据这个地址就可以提取出单词字符串。

    在这里插入图片描述
    图8 B树查找结构

    3.4 总结

    单词ID:记录每个单词的单词编号;
    单词:对应的单词;
    文档频率:代表文档集合中有多少个文档包含某个单词
    倒排列表:包含单词ID及其他必要信息
    DocId:单词出现的文档id
    TF:单词在某个文档中出现的次数
    POS:单词在文档中出现的位置

    以单词“加盟”为例,其单词编号为6,文档频率为3,代表整个文档集合中有三个文档包含这个单词,对应的倒排列表为{(2;1;<4>),(3;1;<7>),(5;1;<5>)},含义是在文档2,3,5出现过这个单词,在每个文档的出现过1次,单词“加盟”在第一个文档的POS是4,即文档的第四个单词是“加盟”,其他的类似。

    这个倒排索引已经是一个非常完备的索引系统,实际搜索系统的索引结构基本如此。

    参考文档:https://blog.csdn.net/starzhou/article/details/87519973#comments,并对有些图的位置做了相应调整。

    展开全文
  • 什么是反向索引

    千次阅读 2018-11-04 15:38:12
    反向索引英文名叫做Inverted index, 顾名思义, 是通常意义下索引的倒置。 举个例子:我们用不同的数字索引不同的句子(比如以下三句在文本中是按照0,1,2的顺序排列的) 0 : “I love you” 1 :“I love you ...
  • 反向索引

    2018-09-10 15:02:00
    反向索引英文名叫做 Inverted index,顾名思义,是通常意义下索引的倒置。 举个例子: 我们用不同的数字索引不同的句子(比如以下三句在文本中是按照0,1,2的顺序排列的) 0 : "I love you" 1 : &...
  • 各位读者中午好! 这里对之前发表的查找类型算法的应用做个...文章目录一、字典查找二、索引、反向索引查找三、文件索引四、Git源码 因为实例代码需要一些.csv格式的data,不过书本官网找不到( https://algs4.cs.p...
  • 关键词:索引、倒排索引(反向索引) (1)为什么要用索引 索引的建立,能使查找更加快速 (2)索引的数据结构 数组: 方便查找,但是数据更新太慢 链表:方便更新,但是查找太慢(从头到尾,或者从尾到头)...
  • 反键索引又叫反向索引,不是用来加速数据访问的,而是为了均衡IO,解决热块而设计的比如数据这样: 1000001 1000002 1000005 1000006 在普通索引中会出现在一个叶子上,如果部门数据需求极大,也就是热块,多个需求之间...
  • 在本文中,我们提出了一种有效的私有关键字搜索(EPKS)方案,该方案支持binary.search并将其扩展到基于反向索引的加密数据的动态设置(DEPKS)。 首先,我们描述了构建支持二进制搜索的可搜索对称加密(SSE)方案...
  • 关于正向索引与反向索引

    千次阅读 2017-02-27 16:23:26
    前面我们说过索引包含正向索引和反向索引两部分,首先我们看看正向索引的结构。 正向索引用来存储文档的各种属性,从逻辑上讲,正向索引其实就是一个大数组,数组中每个元素就是一个文档的属性集合。 ...
  • 正向索引(forward index)和反向索引(inverted index)一句话总结通过A搜索B是正向索引,那么反过来通过B去搜索A就是反向索引。是不是很简单。实例说明先看个例子吧。 我们搜索正向索引,这4个字会被拆分为“正向索引...
  • 正向索引与反向索引(solr)

    千次阅读 2019-03-20 21:22:00
    正向索引(正排索引):正排表是以文档的ID为关键字,表中记录文档中每个字的位置信息,查找时扫描表中每个文档中字的信息直到找出所有包含查询关键字的文档。 正排表结构如图1所示,这种组织方法在建立索引的时候...
  • 反键索引/反向索引

    2017-02-27 16:24:25
    反键索引又叫反向索引,不是用来加速数据访问的,而是为了均衡IO,解决热块而设计的  比如数据这样:  1000001 1000002 1000005 1000006  在普通索引中会出现在一个叶子上,如果部门数据需求极大,也就是热块,多...
  • 反向索引是一种索引结构,它存储了单词与单词自身在一个或多个文档中所在位置之间的映射。反向索引通常利用关联数组实现。它拥有两种表现形式: inverted file index,其表现形式为 {单词,单词所在文档的ID} ...
  • -- 测试创建反向索引及表分区和索引分区,并把索引指定在不同的表空间上 -- 用户有了unlimited TABLESPACE权限,就可以在任何表空间可以创建对象 -- 创建主键上的反向索引,要注意先创建索引,在设主键 -- 可以把...
  • 在Hadoop上使用MapReduce构建反向索引器 脚步 在Makefile中更改netid(默认为jguo7) $cd src 字数 $cd wordCount $make init: build up the directories in the HDFS, pre-process the input file and put it into...
  • 1、直接根据条件进行索引,isin()接受一个列表,判断该列中元素是否在列表中 import numpy as np import pandas as pd df=pd.DataFrame(np.random.randn(4,4),columns=['A','B','C','D']) df Out[189]: A B ...
  • 使用Mapreduce可以并行的创建反向索引。假如你输入的是文本文件,输出是元组列表,每个元组由一个数据和包含该数据的文件列表组成。常规处理办法需要将这些数据连接在一起,而且是在内存中执行连接操作。但是有大量...
  • 基于MySQL和Lucene的反向索引系统的实时性能比较研究,刘一洲,徐鹏,搜索引擎是当今互联网使用最频繁的应用之一。为用户提供及时的,甚至是实时的信息索引是当今搜索引擎所要面对的首要挑战。倒排索
  • mysql什么时候支持反向索引

    千次阅读 2017-06-12 17:10:59
    这会导致越往后翻页查询越慢,看了一眼其他数据库,可以在创建索引的时候创建倒序索引 这样使用这个索引的时候普通查询即可把最新更新的数据很快列出来 不知道mysql什么时候支持这类先置索引而不是在查询时倒序使用...
  • 动态数组 使用负索引进行反向索引的向量(学校的 C++ 项目) 任务描述

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 105,425
精华内容 42,170
关键字:

反向索引