精华内容
下载资源
问答
  • MongoDB支持2维地理信息索引。它被设计用来进行脑海中基于位置的查询,诸如“查找距离我的位置最近的N个场所”。它还可以高效的处理额外的查询条件,比如“查找距离我的位置最近的N个博物馆”。 为了可以使用这种...

    v1.4+

    MongoDB支持2维地理信息索引。它被设计用来进行脑海中基于位置的查询,诸如“查找距离我的位置最近的N个场所”。它还可以高效的处理额外的查询条件,比如“查找距离我的位置最近的N个博物馆”。

    为了可以使用这种索引,你需要在你的对象中设置一个字段,该字段可以是一个子对象或者前两个元素为x,y坐标的数组(或者y,x-只要一致就行;为了确保一致性,推荐在你的客户端代码中使用保持排序的词典/hashes。)。

    一些例子:

    { loc : [ 50 , 30 ] } //SUGGESTED OPTION
    { loc : { x : 50 , y : 30 } }
    { loc : { foo : 50 , y : 30 } }
    { loc : { lon : 40.739037, lat: 73.992964 } }

    创建该索引

    db.places.ensureIndex( { loc : "2d" } )

    默认情况下,该索引假定你在索引经度/维度,并且这些值的范围是[-180,180].

    如果你在索引其他东西,你可以指定一些选项:

    db.places.ensureIndex( { loc : "2d" } , { min : -500 , max : 500 } )

    这会对索引扩容来存储-500到500范围的值。地理信息边界搜索目前是限制在长方形和圆形之内不含边界以外。你不能插入边界[min,max)之外的值。例如,

    使用上面的代码,点(-500,500)不能被插入并且会触发一个错误(但是,点(-500,499)是可以的)。

    db.places.ensureIndex( { loc : "2d" } , { bits : 26 } )

    bits参数设定了2D geo-hash值的精度,存储位置的最小记录。默认情况下,精度设置为26位,这大体等同于(经度,纬度)定位的1步长,默认的边界为(-180,180)。要对拥有更大边界的空间建立索引,可以将位数增大到最大值32.

    当前,你仅能为每一个集合创建一个地理信息索引。

    模糊大小数组语法仅能使用在不低于V1.9的版本,在“foo.bak”中的“2d”可以引用的内嵌字段类似于:

    { foo : [ { bar : [ ... ] } ] }

    这个限制即使在并不是每个文档都有多个位置时依然存在并且数组大小为1.在老版本中,你需要将内嵌位置嵌入到非数组中:

    { foo : { bar : [ ... ] } }

    查询

    该索引可以用来进行精确查询:

    db.places.find( { loc : [50,50] } )

    当然,这并不是很有趣。更重要的是查询某个点附近的点,并且不需要精确匹配:

    db.places.find( { loc : { $near : [50,50] } } )

    上面的查询寻找离(50,50)最近的点并且按距离排序后返回(这里不需要增加排序参数)。使用limit()指定最大返回个数(默认返回100个):

    db.places.find( { loc : { $near : [50,50] } } ).limit(20)

    你还可以对$near增加一个最大距离的参数:

    db.places.find( { loc : { $near : [50,50] , $maxDistance : 5 } } ).limit(20)

    所有地理空间查询中的距离同文档坐标系统中的单位一样(除了接下来讨论的球面查询)。例如,如果你索引的区域大小为[300,300),表示一个300*300平米地段,并且你有两个(10,20)和(10,30)的文档(代表在(x,y)的点),你可以这样查询 $near:[10,20],$maxDistance:10.距离单位和你的坐标系统一样,因此这个查询查找距离该点10米以内的目标点。

    联合索引

    MongoDB地理信息索引支持可选的从键。如果你经常对地址和其他属性同时查询,可以增加其他属性到该索引。其他属性作为索引的注解,可以让过滤执行的更快。例如:

    db.places.ensureIndex( { location : "2d" , category : 1 } );
    db.places.find( { location : { $near : [50,50] }, category : 'coffee' } );

    geoNear命令

    尽管find()函数是通常的首先,MongoDB还是提供了一个执行类似功能的geoNear命令。geoNear命令可以在查询结果中返回每个点距离查询点的距离,也有一些故障诊断信息。

    合法的选项有:“near”,"num","maxDistance","distanceMultiplier"和“query”。

    > db.runCommand( { geoNear : "places" , near : [50,50], num : 10 } );
    > db.runCommand({geoNear:"asdf", near:[50,50]})
    {
    "ns" : "test.places",
    "near" : "1100110000001111110000001111110000001111110000001111",
    "results" : [
    {
    "dis" : 69.29646421910687,
    "obj" : {
    "_id" : ObjectId("4b8bd6b93b83c574d8760280"),
    "y" : [
    1,
    1
    ],
    "category" : "Coffee"
    }
    },
    {
    "dis" : 69.29646421910687,
    "obj" : {
    "_id" : ObjectId("4b8bd6b03b83c574d876027f"),
    "y" : [
    1,
    1
    ]
    }
    }
    ],
    "stats" : {
    "time" : 0,
    "btreelocs" : 1,
    "btreelocs" : 1,
    "nscanned" : 2,
    "nscanned" : 2,
    "objectsLoaded" : 2,
    "objectsLoaded" : 2,
    "avgDistance" : 69.29646421910687
    },
    "ok" : 1
    }

    上面的命令返回距离(50,50)最近的10个点。(在该集合上面检查2d索引时会自动确定loc字段)

    如果你需要增加过滤器,可以这样做:

    > db.runCommand( { geoNear : "places" , near : [ 50 , 50 ], num : 10,
    ... query : { type : "museum" } } );

    query可以是任意常规的mongo query。
    边界查询

    可以使用$within代替$near在某个图形内部进行查询。返回的结果并不是按距离进行排序的,在这种无排序的情况下查询会更快一些。支持的图形类型有$box(矩形),$center(圆形),和$polygon(凹和凸的多边形)。所有的边界查询默认包含了图形的边,尽管在浮点类型情形下这一点不能严格依赖。

    查询矩形内所有点,你必须指定左下角和右上角的坐标:

    > box = [[40.73083, -73.99756], [40.741404, -73.988135]]
    > db.places.find({"loc" : {"$within" : {"$box" : box}}})

    通过中心点坐标和半径来指定一个圆形:

    > center = [50, 50]
    > radius = 10
    > db.places.find({"loc" : {"$within" : {"$center" : [center, radius]}}})

    通过一个数组或者对象来指定多边形。多边形最后一个点默认会和第一个点相连。

    > polygonA = [ [ 10, 20 ], [ 10, 40 ], [ 30, 40 ], [ 30, 20 ] ]
    > polygonB = { a : { x : 10, y : 20 }, b : { x : 15, y : 25 }, c : { x : 20, y : 20 } }
    > db.places.find({ "loc" : { "$within" : { "$polygon" : polygonA } } })
    > db.places.find({ "loc" : { "$within" : { "$polygon" : polygonB } } })

    多边形查询严格限定在多边形内部,目前文档内的多边形不能被Mongodb建立索引。

    多位置文档

    Mongodb还支持对多位置文档建立索引。这些位置可以通过子对象中的数组来指定,例如:

    > db.places.insert({ addresses : [ { name : "Home", loc : [55.5, 42.3] }, { name : "Work", loc :
    [32.3, 44.2] } ] })
    > db.places.ensureIndex({ "addresses.loc" : "2d" })

    多位置也可以在单独的字段指定:

    > db.places.insert({ lastSeenAt : [ { x : 45.3, y : 32.2 }, [54.2, 32.3], { lon : 44.2, lat : 38.2 } ]
    })
    > db.places.ensureIndex({ "lastSeenAt" : "2d" })

    默认情况下,当在包含多位置文档的集合上执行geoNear或者 $near类型的查询时,相同的文档可能会返回多次。使用$within操作符的查询默认不会返回重复文档。

    在V2.0,可以通过对geoNear和$within查询使用$uniqueDocs参数来覆盖默认参数,类似于:

    > db.runCommand( { geoNear : "places" , near : [50,50], num : 10, uniqueDocs : false } )
    > db.places.find( { loc : { $within : { $center : [[0.5, 0.5], 20], $uniqueDocs : true } } } )

    目前不能对$near指定$uniqueDocs参数。

    另外,当使用geoNear查询和多位置文档时,在返回距离的同时也返回生成距离的位置信息是很有用的。在v2.0,对geoNear查询指定includeLocs:true
    就可以返回位置信息了。返回的位置是文档的位置信息的一份拷贝-如果位置是一个数组,这个对象会有“0”,“1”字段。

    > db.runCommand({ geoNear : "places", near : [ 0, 0 ], maxDistance : 20, includeLocs : true })
    {
    "ns" : "test.places",
    "near" : "1100000000000000000000000000000000000000000000000000",
    "results" : [
    {
    "dis" : 5.830951894845301,
    "loc" : {
    "x" : 3,
    "y" : 5
    },
    "obj" : {
    "_id" : ObjectId("4e52672c15f59224bdb2544d"),
    "name" : "Final Place",
    "loc" : {
    "x" : 3,
    "y" : 5
    }
    }
    },
    {
    "dis" : 14.142135623730951,
    "loc" : {
    "0" : 10,
    "1" : 10
    },
    "obj" : {
    "_id" : ObjectId("4e5266a915f59224bdb2544b"),
    "name" : "Some Place",
    "loc" : [
    [
    10,
    10
    ],
    [
    50,
    50
    ]
    ]
    }
    },
    {
    "dis" : 14.142135623730951,
    "loc" : {
    "0" : -10,
    "1" : -10
    },
    "obj" : {
    "_id" : ObjectId("4e5266ba15f59224bdb2544c"),
    "name" : "Another Place",
    "loc" : [
    [
    -10,
    -10
    ],
    [
    -50,
    -50
    ]
    ]
    }
    }
    ],
    "stats" : {
    "time" : 0,
    "btreelocs" : 0,
    "nscanned" : 5,
    "objectsLoaded" : 3,
    "avgDistance" : 11.371741047435734,
    "maxDistance" : 14.142157540259815
    },
    "ok" : 1
    }

    分片环境

    Mongodb支持在分片环境下使用地理信息索引。


    展开全文
  • lucene索引结构(二)--域(Field)信息索引

    千次阅读 2012-07-22 19:46:56
    1. 域(Field)的元数据信息(.fnm)文件分析 1.1 作用  我们在为文档建立索引的时候,会为文档添加不同的域(字段)来进行索引,使得索引结构能满足更多的查询语法。例如一个文档集被索引了author,modifydate字段,...
    1. 域(Field)的元数据信息(.fnm)文件分析
    1.1 作用
         我们在为文档建立索引的时候,会为文档添加不同的域(字段)来进行索引,使得索引结构能满足更多的查询语法。例如一个文档集被索引了author,modifydate字段,那么就能支持 'author:wangzhengnb AND modifydate>20120722' 这种Query语法。
         更真实的例子就是搜索引擎普遍支持的site语法,也就是对网页索引时添加了site域,这样用户输入'意甲 site:sports.sina.com.cn' 时,搜索后端就能根据网页的site field来判断这个网页是不是新浪体育的,从而实现针对新浪体育频道域下的搜索。如下图,

           而.fnm文件就是索引了这些域的元信息。比如一共有多少个域,某个域是否被存储、是否保存位置信息、是否保存偏移等等。

    1.2 .fnm的物理结构分析
         .fnm的物理结构如下图,

         .fnm文件分为FNMVersion,FieldsCount, <FieldName, FieldBits>FieldsCount 
          
         FNMVersion, FieldsCount --> VInt

         FieldName --> String

         FieldBits --> Byte

         FNMVersion对应版本号,对应Lucene-3.0.2为-2。

         FieldsCount表示这个段中Field的总数。

         <FieldName, FieldBits>元组是一个Field的信息,它一共重复FieldsCount次;其中的FieldName是Field名称,FieldBits表示这个域的属性,具体如下表。

    1) 最低位如果为0,表示这个域不被索引(Field.Index.NO);为1,表示被索引(Field.Index.ANALYZED不仅索引而且分词,Field.Index.NOT_ANALYZED仅索引不分词),加入倒排表。
    2) 次低位为0,表示不保存词向量(TermVector)(Field.TermVector.NO),为1表示保存词向量(Field.TermVector.YES)
    3) 倒数第三位如果为1表示在词向量中保存位置信息(Field.TermVector.WITH_POSITIONS)
    4) 倒数第四位如果为1表示在词向量中保存偏移量信息(Field.TermVector.WITH_OFFSETS)
    5) 倒数第五位如果为1表示不保存偏移量因子(Field.Index.NOT_ANALYZED_NO_NORMS)
    6) 倒数第六位如果为1表示保存Payload信息。

    Notes:
         1) 索引域(Indexed)和存储域(Stored)的区别
     一个域为什么会被存储(store)而不被索引(Index)呢?在一个文档中的所有信息中,有这样一部分信息,可能不想被索引从而可以搜索到,但是当这个文档由于其他的信息被搜索到时,可以同其他信息一同返回。

    ◦ 举个例子,读研究生时,您好不容易写了一篇论文交给您的导师,您的导师却要他所第一作者而您做第二作者,然而您导师不想别人在论文系统中搜索您的名字时找到这篇论文,于是在论文系统中,把第二作者这个Field的Indexed设为false,这样别人搜索您的名字,永远不知道您写过这篇论文,只有在别人搜索您导师的名字从而找到您的文章时,在一个角落表述着第二作者是您
    分信息,可能不想被索引从而可以搜索到,但是当这个文档于其他的信息被搜索到时,可以同其他信息一同返回。

         2) payload的使用
    ◦ 我们知道,索引是以倒排表形式存储的,对于每一个词,都保存了包含这个词的一个链表,当然为了加快查询速度,此链表多用跳跃表进行存储。

    ◦ Payload信息就是存储在倒排表中的,同文档号一起存放,多用于存储与每篇文档相关的一些信息。当然这部分信息也可以存储域里(stored Field),两者从功能上基本是一样的,然而当要存储的信息很多的时候,存放在倒排表里,利用跳跃表,有利于大大提高搜索速度。

     利用Payload,我们可以为文档附加上一些自定义的信息。比如为文档增加一个自定义的Term "$$$_Internal_ID"以及声明特殊的Field "$$$_Internal_ID",用以为文档保存一份不同于Lucene生成的ID。这样在倒排里就可以有一个"$$$_Internal_ID"的词项指向有这些域的文档的倒排,从而查找这些文档的自定义的ID。

    1.3 深入分析.fnm文件
         用UE打开_0.fnm文件,下图是我用不同颜色标注的各个字段的信息。



         1) FNMVersion, VInt FEFFFFFF0F, decode出来就是4294967294(126 + 127*128 + 127*128^2 + 127*128^3 + 15*128^4), 也就是-2了。

             这和官方文档上叙述的"FNMVersion (added in 2.9) is always -2."是一致的。

             不过让我略觉蛋疼的是官方文档上也清楚的写着"VInt - A variable-length format for positive integers ",尼玛这不是正数吗。靠int32溢出来转成-2。。。而且不就           是一个版本号么,搞个定长的int32数就完了呗,反正也就存一次,能耗多少空间嘛。。真是的,蛋疼。。

         2) FieldsCount, 也是Vint, 0x03, 解码后就是3,和建索引的代码是一致的。一共加入了'path','modified'和'contents'三个域。
           doc.add(new Field( "path", f.getPath(), Field.Store.YES, Field.Index.NOT_ANALYZED ));
           doc.add(new Field("modified",DateTools. timeToString(f.lastModified(), DateTools.Resolution.MINUTE ),Field.Store. YES,Field.Index. NOT_ANALYZED));
           BufferedReader br = new BufferedReader(read);
           doc.add(new Field("contents", br));
    

    后面跟着的就是FieldsCount个域。

         3) 这里只展示第一个域。首先是FieldName,String类型,String也就是一个VInt表示长度len,后面跟着len个Byte。

             这里的长度是04,解码也就是4。后面读出的4个Byte就是这个域的名字,也就是'path'了,从右侧也可以看到。

             这之后跟着的就是下一个域,长度为08(也就是8),名字是'modified'。然后又是下一个。。


    2. 域数据文件(.fdx和.fdt)分析
    2.1 作用

         前面提到的域元数据文件,是从一个整体上来对段中的域进行描述。

         然而当你想查找某篇文档都有哪些Field,这篇文档的这些个Field都取些什么值,都有啥属性,那就得依靠域数据文件了。
         
         PS:从上句话也可以看出来,这个域数据索引,也是一个典型的正向索引(文档ID--->文档域信息)。

         域数据文件分成域数据索引(Field data index, .fdx)和域数据(Field data, .fdt)两部分,下面将对它们介绍。

    2.2 域数据索引及域数据的物理结构分析

         .fdx和.fdt文件的物理结构如下图所示:


         坑爹的地方来了。这幅图原来在网上找到的时候是没有前面粉红色的Format Version字段的,连和代码一起下下来的官方文档里都没提这俩字段。

         尼玛啊,这索引文件可是二进制的啊,用UE打开全是00 01 FF的这种有木有,怎么看都怎么不对,遂上网搜以及跟代码看。终于发现是Lucene2.9之后再.fdx和.fdt最前面加入了一个format version字段。。。可参见http://blog.csdn.net/a276202460/article/details/5650026

         上述索引和数据的关系大体如下:
         段内检索了多少个文档,在.fdx中就有多少个FieldValuePosition,这是一个UInt64的定长数据,指向的是.fdt的一个绝对偏移地址。这个地址上保存的就是这篇文档的域信息。

         显而易见,.fdx因为是一个由定长数据组成的记录,所以docID=n的文档的域数据地址,就被保存在索引文件.fdx的4+n*8的位置上,然后读出绝对偏移后,就可以读取.fdt的这个偏移上的数据,就是docID=n文档的域信息了。

         一篇文档的域信息包括文档域的个数,域编号(文档内的编号,从0开始),域属性,域的值。

         详细的解释如下:
         
         域数据索引:
         1) Format Version: Int32数据,Lucene-3.0.2的这个值对应的是2。
         2) 之后就跟的是SegSize个(段的大小,也即文档总数,在segment索引可找到它的身影,见http://blog.csdn.net/wangzhengnb/article/details/7771448) FieldValuesPosition,都是UInt64数据。表示.fdt文件中的绝对偏移。

         域数据:
         1) Format Version: Int32数据,Lucene-3.0.2的这个值对应的是2。

         2) 之后跟着SegSize个DocFieldData。DocFieldData可不是定长数据,因为每个文档对应的某个域的取值都是不同的,文档也不都一定有相同数量的域等等。

         3) DocField由FieldCount开头,是个Vint变长数据,标志这个文档一共有多少个域。
             接下来就是1个Bits段,占1字节,解释见下表。
              
    最低位为1表示这个域是分词的(tokenized)
    次低位为1表示这个域是二进制数据,否则是文本,也即字符串数据
    倒数第三位为1表示这个域采用了压缩算法(ZLib)
              
         最后跟着的是Value段,Value可根据域的取值是二进制还是文本,或为BinaryValue类型或为String类型。
         这里只讨论String类型的。同样String还是由VInt和Char bytes组成。

    2.3 深入分析.fdx和.fdt文件

         UE打开它俩,截图如下,因为文件很长,也没必要全部截完图,所以只截了开头的一部分。并把它俩贴到一副图里,方便叙述。



          嗯哈?有点乱?不要怕,接下来一步步看,很简单。    
         首先看看.fdx文件:
         1)由一个Format Version开头,占Int32空间,取值为0x02,也即2。

         2) 紧跟着的是99个文档的域信息在.fdt中的绝对偏移。这里框取了前3个,它们的偏移分别是0x04,0x3F,0x7C。
              看看下方的.fdt文件,3个红色的圈圈圈住的地方,就是这三个文档的域信息的开头的地方。

         在看看.fdt文件:
         1) 同样由一个Format Version开头,占Int32空间,取值为0x02,也即2。

         2)接下来的是文档的域总数FieldCount,为2。等等!不是建立了path,modified和contents三个域嘛?!怎么只有俩!别着急,原来是contents只索引,不保存。如果每篇文档都保存全部的正文部分,那空间开销好大哦。

         3) 接着的是这个域在文档中的编号,第一个绿圈里的数是00,第二个绿圈对应的是01,也即0号域和1号域。注意,这个编号是文档内的。到了下一篇文档,域编号又会从0开始啦。

         4) 接下来是Bits了,取0。也即这个域不分词、为字符串类型、不压缩,这个和实际的索引建立程序是吻合的。

         5) 之后是Value了,这里我把String类型拆成了Vint(紫色)和char bytes(棕色)来画,方便看些:)

             可看到文档0的域0的value长度为0x28,也就是40。所以从接下来的0x08到0x2F就是文档0的域0的值,可以从右侧看到是它的路径,E:\lucene\....什么的。
              
             如是分析文档0的域1的信息,都能和实际吻合。当域1的value在0x3E结束后,又开始了文档1的域信息,这印证了.fdx中文档1的偏移地址是0x3F的正确性。

    3 Reference
    [1] Apache Lucene - Index File Formats
    http://lucene.apache.org/core/old_versioned_docs/versions/2_9_0/fileformats.html#File Naming

    [2] forfuture1978的专栏
    http://blog.csdn.net/forfuture1978

    [3] a276202460的专栏--边学边记(七) lucene索引结构四(_N.fdx,_N.fdt)

    展开全文
  • 信息检索 信息检索(Information Retrieval,简称IR):从大规模非结构化数据(通常是文本)的集合(通常保存在计算机上)中找出满足用户信息需求的资料(通常是文档)的...倒排索引 顺序扫描:这种线性扫描就是一种

    信息检索

    信息检索(Information Retrieval,简称IR):从大规模非结构化数据(通常是文本)的集合(通常保存在计算机上)中找出满足用户信息需求的资料(通常是文档)的过程

    信息检索按照规模分类:
    • 以web搜索为代表的大规模级别
    • 小规模级别,典型示例为个人信息检索
    • 中等规模级别,面向企业、机构和特定领域的搜索

    倒排索引

    顺序扫描:这种线性扫描就是一种最简单的计算机文档检索方式。这个过程通常称为grepping,它来自于Unix下的一个文本扫描命令grep。

    顺序扫描无法满足的几种情况:
    1. 大规模文档集条件下的快速查找。
    2. 更灵活的匹配方式。比如grep命令下不能支持诸如Romans NEAR countrymen之类的查询
    3. 需要对结果进行排序
    词项-文档的关联矩阵



    词项-文档的关联矩阵,其中每一行代表一个词,每列表示一个剧本。当词t在剧本d中存在时,矩阵元素(t, d)的值为1,否则为0

    为想要查询 Brutus AND Caesar AND NOT Calpurnia,我们分别取出 Brutus,Caesar及Calpurnia对应的行向量,并对Calpurnia对应的向量求反,然后进行基于位的与操作,得到:
    110100 AND 110111 AND 101111 = 100100

    词项-文档(term-doc)的关联矩阵具有高度稀疏性,仅仅保存非零的位置明显更好

    倒排索引的构建
    • 对每个词项t,记录所有包含t的文档,建立词条序列<词条,docID>二元组
    • 对词项、文档排序。按词项排序,然后每个词项按docID排序
    • 合并词项,并记录词项的文档频率df(对每个词项t,记录所有包含t的文档数目)



    布尔查询处理

    and查询处理

    比如说,我们要寻找既包含字符串“Brutus”又包含字符串“Calpurnia”的文档,我们可以采用归并的方法(类似于归并排序中的merge操作),进行如下几步:
    1. 取出包含字符串“Brutus”的倒排记录表
    2. 取出包含字符串“Calpurnia”的倒排记录表
    3. 通过合并两个倒排记录表,找出既包含“Brutus”又包含“Calpurnia”的文档



    利用归并的算法,可以在O(n)的时间复杂度求出交集,书上用链表,我为了方便,直接用数组了

    #include <stdio.h>
    
    int main(void)
    {
    	int arr1[7] = {1, 2, 4, 11, 31, 45, 173}; /*Brutus文档集合*/
    	int arr2[4] = {2, 31, 54, 101}; /*Calpurnia文档集合*/
    	int result[7] = {0}; /*交集集合*/
    	int i, j, k, len1, len2;
    
    	/*变量初始化*/
    	len1 = sizeof(arr1) / sizeof(int);
    	len2 = sizeof(arr2) / sizeof(int);
    
    	/*归并算法*/
    	for (i = j = k = 0; i < len1 && j < len2;) {
    		if (arr1[i] == arr2[j]) {
    			result[k] = arr1[i];
    			i ++;
    			j ++;
    			k ++;
    		} else if (arr1[i] < arr2[j]) {
    			i ++;
    		} else if(arr1[i] > arr2[j]) {
    			j ++;
    		}
    	}
    
    	/*打印输出*/
    	for (i = 0; i < k; i ++) {
    		printf("%d ", result[i]);
    	}
    	printf("\n");
    
    	return 0;
    }
    

    通用的查询优化策略(词典中保存文档频率df的一个充分理由)

    (madding OR crowd) AND (ignoble OR strife) AND (killed OR slain)

    • 每个布尔表达式都能转换成上述形式(合取范式)
    • 获得每个词项的df
    • 通过将词项的df相加,估计每个OR表达式对应的倒排记录表的大小
    • 按照上述估计从小到大依次处理每个OR表达式

    布尔逻辑转换(数学理论)

    可以参考我之前写的一篇博客:http://blog.csdn.net/zinss26914/article/details/9056049

    这种变换基于关于逻辑等价的规则:
    • 双重否定律
    • 德×摩根定律:非(P 且 Q) = (非P)  |  (非Q) 非(P 或 Q) = (非 P) 且 (非 Q)
    • 分配律

    参考链接

    展开全文
  • Lucene源代码之信息索引

    千次阅读 2008-11-26 20:18:00
    索引是什么?索引是一种数据存储和组织结构。 逆常人之思维,lucene索引采用倒排文件索引构造索引系统。具体实现原理举例说明: 假设有3篇文章,file1,file2,file3,文件内容如下:  file1 (单词1,单词2,单词3...

     索引是什么?索引是一种数据存储和组织结构。

    逆常人之思维,lucene索引采用倒排文件索引构造索引系统。具体实现原理举例说明:

    假设有3篇文章,file1,file2,file3,文件内容如下: 

    file1 (单词1,单词2,单词3,单词4....)

    file2 (单词a,单词b,单词c,单词d....)

    file3 (单词1,单词a,单词3,单词d....)

    建立的倒排索引就是这个样子:

    单词1 (file1,file3)

    单词2 (file1)

    单词3 (file1,file3)

    单词a (file2, file3)

    ....

    这就是倒排索引,很简单吧。

     

    补充:

    “倒排”是与“正排”相对的概念,“正排”如同我们通常的阅读过程:先看到文档后看到单词,而倒排则像我们翻看《辞源》的过程:从单词找到文档。所以正排与倒排可以从文档与单词的指向关系上做区分:正排是文档指向单词,倒排是单词指向文档。目前几乎所有的商业搜索引擎都采用倒排索引方式,开源Lucene也不例外,如图3.1所示。

     

    注:一般情况下,一个文件要建立索引,就先把它变成纯文本的格式。

     

    索引文件的逻辑视图

    在lucene 中有索引块的概念,每个索引块包含了一定数目的文档。我们能够对单独的索引块进行检索。图 2 显示了 lucene 索引结构的逻辑视图。索引块的个数由索引的文档的总数以及每个索引块所能包含的最大文档数来决定。


    图2:索引文件的逻辑视图 
     

    lucene 中的关键索引文件

    下面的部分将会分析lucene中的主要的索引文件,可能分析有些索引文件的时候没有包含文件的所有的字段,但不会影响到对索引文件的理解。

    1.索引块文件

    这个文件包含了索引中的索引块信息,这个文件包含了每个索引块的名字以及大小等信息。表 2 显示了这个文件的结构信息。


    表2:索引块文件结构 

    2.域信息文件

    我们知道,索引中的文档由一个或者多个域组成,这个文件包含了每个索引块中的域的信息。表 3 显示了这个文件的结构。


    表3:域信息文件结构 

    3.索引项信息文件

    这是索引文件里面最核心的一个文件,它存储了所有的索引项的值以及相关信息,并且以索引项来排序。表 4 显示了这个文件的结构。


    表4:索引项信息文件结构 

    4.频率文件

    这个文件包含了包含索引项的文档的列表,以及索引项在每个文档中出现的频率信息。如果lucene在索引项信息文件中发现有索引项和搜索词相匹配。那么 lucene 就会在频率文件中找有哪些文件包含了该索引项。表5显示了这个文件的一个大致的结构,并没有包含这个文件的所有字段。


    表5:频率文件的结构 

    5.位置文件

    这个文件包含了索引项在每个文档中出现的位置信息,你可以利用这些信息来参与对索引结果的排序。表 6 显示了这个文件的结构


    表6:位置文件的结构 

    从上所述:

    索引结构可以分为索引、段索引、文档索引、域索引、项索引几个层次。lucene每个索引的结构有一个或多个段组成(索引在内存和磁盘上具有相同的逻辑结构);每个段包含一个或多个文档(索引段相当于子索引);每个文档管理一个或多个域;每个域有一个或多个项组成;每个索引项是一个索引数据(索引项是索引管理的最小的单位)。

    在Lucene中采用段索引的生成方式,如图3.2所示。合并阈值(mergeFactor)影响着内存与硬盘中索引文件的个数,每添加一个document将生成单一段索引(single segment index)被内存持有,当单一段索引的个数超过合并阈值时,就会通过merge(合并)的过程将单一段索引合并为段索引(segment index)。段索引的个数超过合并阈值时也会触发合并过程,合并为一个索引。单一段索引,段索引,索引文件格式(file format)是相同的,三者只是规模不同。

    图3.2 增量索引过程


    下面来看一下IndexWriter()是如何实现的了。

    IndexWriter()的实例化过程(包含初始化);

    1. private void init(Directory d, Analyzer a, final boolean create, boolean closeDir)
    2.     throws IOException {
    3.     this.closeDir = closeDir;
    4.     directory = d;
    5.     analyzer = a;
    6.     if (create) {
    7.       //清理遗留下来的写入锁:
    8.       directory.clearLock(IndexWriter.WRITE_LOCK_NAME);//IndexWriter.WRITE_LOCK_NAME="write.lock".
    9.     }
    10.     Lock writeLock = directory.makeLock(IndexWriter.WRITE_LOCK_NAME);
    11.     if (!writeLock.obtain(writeLockTimeout)) // obtain write lock
    12.       throw new IOException("Index locked for write: " + writeLock);
    13.     this.writeLock = writeLock;                   // save it
    14.     try {
    15.       if (create) {
    16.       try {
    17.           segmentInfos.read(directory);                                    @1
    18.           segmentInfos.clear();
    19.         } catch (IOException e) {
    20.         }
    21.         segmentInfos.write(directory);                                     @2
    22.       } else {
    23.         segmentInfos.read(directory);
    24.       }
    25.       /**
    26.        * 创建一个删除器用以记录哪些文件可以被删除。
    27.        */
    28.       deleter = new IndexFileDeleter(segmentInfos, directory);
    29.       deleter.setInfoStream(infoStream);
    30.       deleter.findDeletableFiles();
    31.       deleter.deleteFiles();
    32.     } catch (IOException e) {
    33.       this.writeLock.release();
    34.       this.writeLock = null;
    35.       throw e;
    36.     }
    37.   }

    @1:表示从索引目录中读取旧段号,然后把后来创建的段号与旧段号连接起来;

    @2:在索引目录中写入segment段信息文件。

     

    注:下一篇将介绍SegmentInfos的实现。

     

    IndexWriter中几个重要的属性:

      public final static int DEFAULT_MERGE_FACTOR = 10;//对内存和磁盘中的索引都有作用。

      public final static int DEFAULT_MAX_BUFFERED_DOCS = 10;//minMergeDocs默认值为10,控制内存中索引,不影响磁盘

      public final static int DEFAULT_MAX_MERGE_DOCS = Integer.MAX_VALUE;//maxMergeDocs默认值2147483647,合并后的document数目如果超出此值就会保持不变。

     以上三个全部都是合并阀值,只是作用区域不同。

      public final static int DEFAULT_MAX_BUFFERED_DELETE_TERMS = 1000;

      public final static int DEFAULT_MAX_FIELD_LENGTH = 10000;

    maxFieldLength指一个可以为多少个Field建立索引,在Lucene中指定的默认的值为10000

      public final static int DEFAULT_TERM_INDEX_INTERVAL = 128;

    termIndexInterval是词条索引区间,与在内存中处理词条相关。如果该值设置的越大,则导致IndexReader使用的内存空间就越小,也就减慢了词条Term的随机存储速度。该参数决定了每次查询要求计算词条Term的数量。在Lucene中的默认值为128。

      private Similarity similarity = Similarity.getDefault(); // how to normalize

    DefaultSimilarity类继承自Similarity抽象类,该类是用来处理有关“相似性”的,与检索密切相关,其实就是对一些数据在运算过程中可能涉及到数据位数的舍入与进位。具体地,Similarity类的定义可查看org.apache.lucene.search.Similarity。

     

    【小知识】上面的minMergeDocs与maxMergeDocs同mergeFactor都是合并阈值,只是作用区域不同,minMergeDocs控制内存中的索引段数,超过该阈值时就会合并,但不影响磁盘上的索引段。maxMergeDocs的数值决定合并后段中包含的document数目,如果要超过该值,就不会合并而维持原有段不变。mergeFactor对内存与磁盘中的段都起作用,内存与磁盘中段索引个数总和超过该阈值就合并索引。

     

    写入索引时,无论是IndexWriter、DocumentWriter、FieldWriter、TermInfosWriter,都含有addDocument()方法。IndexWriter写入时,通常每一个document添加时都作为单一段索引添加到内存中,达到合并阈值时才会合并索引并保存到磁盘中,代码如下:

    1.  public void addDocument(Document doc, Analyzer analyzer) throws IOException {
    2.     /**写入内存*/
    3.     SegmentInfo newSegmentInfo = buildSingleDocSegment(doc, analyzer);              @1
    4.     synchronized (this) {
    5.       ramSegmentInfos.addElement(newSegmentInfo);  //向SegmentInfos中添加一个SegmentInfo
    6.       maybeFlushRamSegments();    /**将内存中的索引合并后保存到硬盘*/         @2
    7.     }
    8.   }

    其实,在执行@1前,首先首先调用了ensureOpen()方法,该方法根据一个closed标识来保证当前实例化的IndexWriter是否处于打开状态。关于closed的标识的设置,当一个IndexWriter索引器实例化的时候,该值就已经初始化为false了,表示索引器writer已经处于打开状态。如果想要关闭writer,直接调用IndexWriter类的close()方法,可以设置closed的标识为true,表示索引器被关闭了,不能进行有关建立索引的操作了。

    @1    添加一个document产生一个singleDocSegmentIndex的过程,该索引只写入到内存中。

    @2    将内存中的索引合并后保存到硬盘。该方法在IndexWriter类中定义用来监测当前缓冲区,及时将缓冲区中的数据flush到索引目录中。其中可能存在索引段合并的问题。

    @1,@2涉及了在内存中建立索引和合并到磁盘两块重量级的知识,在后续篇慢慢研读。……
    展开全文
  • 收集统计信息导致索引被监控

    千次阅读 2013-03-26 17:33:34
    对于索引的调整,我们可以通过Oracle提供的索引监控特性来跟踪索引是否被使用。尽管该特性并未提供索引使用的频度,但仍不失为我们参考的... 1、基于Oracle 10g 收集统计信息索引被监控情形scott@CNMMBO> select * fro
  • 索引

    2010-06-21 17:37:00
    在这个信息爆炸的年代, 信息索引的重要性不言而喻。现在主要的索引结构就是倒排索引,又称为记录文件(posting file),词汇索引(concordance)。 其他的还有签名文件(signature file), 和 位图(bitmap)。 ...
  • 索引信息

    千次阅读 2011-07-05 15:53:12
    /* ================================================================================= ...2011-07-05  在日常的使用中,数据库管理员将会经常性的针对索引进行监控及相应的处理.  针对此应用,现将常
  • 生成索引信息索引创建脚本

    千次阅读 2014-09-25 17:28:22
    create proc p_helpindex...--生成索引信息索引创建脚本 --@tbname 表名,空返回所有表索引 --@type 是否显示聚集索引,1显示聚集索引,2不显示聚集索引 --调用:p_helpindex 'dbo.customers','1' with t as ( select r
  • 1,查询索引状态 1.1 查询user_indexes表 select status,T.* from user_indexes T where table_name='表名' 状态列STATUS说明: valid:当前索引有效 N/A :分区索引 有效 unusable:索引失效 1.2 查询分区索引-...
  • MySQL 索引

    千次阅读 2018-10-29 14:22:17
    索引统计信息 索引碎片处理   索引介绍 在MySQL中,索引是高效获取数据的最重要的数据结构,通常在表数据越来越多情况下获取数据的效率开始下降,而索引或者叫做键可以有效提升效率。理解索引工作的方式最好的...
  • 查看索引信息

    千次阅读 2013-08-11 10:45:15
    1. 查看特定表上的索引信息。 SELECT * FROM user_indexes WHERE table_name='USERS'; 2. 查看特定列上的索引信息。 SELECT * FROM user_ind_columns WHERE table_name='USER';
  • MySQL索引统计信息

    2019-06-25 15:17:22
    MySQL索引统计信息2背景在performance_schema中查看统计信息指标分类:举例在sys举例 背景 上一篇文章中提到了在MySQL的社区版本中,都提供了对于索引统计信息的表,但是,在官方的MySQL版本中,是怎么维护索引...
  • Oracle之查询索引索引列等信息

    千次阅读 2017-04-17 14:43:16
    user_indexes: 系统视图存放是索引的名称以及该索引是否是唯一索引信息。 user_ind_column: 系统视图存放的是索引名称,对应的表和列等。 完整性约束  DBA_CONSTRAINTS、ALL_CONSTRAINTS和USER_...
  • Trafodion将所有的对象(表、索引、字段等)元数据信息保存到”MD“这个Schema下,每个对象都需要唯一的对象ID(OBJECT_ID),通过OBJECT_ID,可以在不同的元数据表中查询需要的信息。 下面这条SQL语句可以帮助我们...
  • 位置信息索引是在倒排索引的基础上实现的,
  • 索引的基本信息`

    2020-09-04 16:47:49
    mysql性能下降,执行时间长,等待时间长 ...mysql索引分类: 单值索引, 复合索引,唯一索引 唯一索引 索引列的值必须唯一,但允许有空值 create unique index index_student_name on student(name); 单值索引
  • 索引是对数据库表中一列或多列的值进行排序的一种结构,使用索引可快速访问数据库表中的特定信息索引的一个主要目的就是加快检索表中数据,亦即能协助信息搜索者尽快的找到符合限制条件的记录ID的辅助数据结构。 ...
  • Oracle收集索引统计信息

    千次阅读 2013-12-11 22:44:01
    相信大家对索引结构非常熟悉了,它是由根、支、叶...下面分析索引统计信息的相关内容。 一、如何查询索引统计信息  查询索引统计信息需要用到user_ind_statistics,下面是典型的查询语句。 SELECT INDEX_NAME AS N
  •   索引是对数据库表中一列或多列的值进行排序的一种结构,使用索引可快速访问数据库表中的特定信息。但是查询速度的提高是以插入,更新,删除的速度为代价的,所以索引的作用在于提高一个海量数据的检...
  • elasticsearch查询某个索引分片信息

    千次阅读 2019-10-30 14:19:53
    elasticsearch6.8 ...通过下面的路径可以查询elasticsearch某个索引分片信息 http://xx.xx.xx.xx:9200/索引名称/_search_shards { "nodes": { "Q6i1duFYQLmJFIu812DQjQ": { "name": "node1", "ephemera...
  • PostgreSQL - 查询表结构和索引信息

    万次阅读 2018-11-19 23:38:45
    PostgreSQL的表一般都是建立在public这个schema下的,假如现在有个数据表t_student,可以用以下几种方式来查询表结构和索引信息。 使用\d元命令查看表字段信息索引信息 在cmd界面使用psql连接db后,输入\d加上表名...
  • 索引3:Hash索引与BitMap索引

    千次阅读 2020-02-11 13:41:49
    hash索引是将索引键通过hash运算后,将运算结果的hash值和对应的行指针信息存储Bucket。 引用:‘’哈希索引(hash index)基于哈希表实现,只有精确匹配索引所有列的查询才有效。对于每一行数据,存储引擎都会对...
  • 索引

    2008-06-25 11:07:00
    使用索引可快速访问数据库表中的特定信息索引是对数据库表中一列或多列的值进行排序的一种结构,例如 employee 表的姓(lname)列。如果要按姓查找特定职员,与必须搜索表中的所有行相比,索引会帮助您更快地获得...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 27,994
精华内容 11,197
关键字:

信息索引