倒排索引 订阅
倒排索引源于实际应用中需要根据属性的值来查找记录。这种索引表中的每一项都包括一个属性值和具有该属性值的各记录的地址。由于不是由记录来确定属性值,而是由属性值来确定记录的位置,因而称为倒排索引(inverted index)。带有倒排索引的文件我们称为倒排索引文件,简称倒排文件(inverted file)。 展开全文
倒排索引源于实际应用中需要根据属性的值来查找记录。这种索引表中的每一项都包括一个属性值和具有该属性值的各记录的地址。由于不是由记录来确定属性值,而是由属性值来确定记录的位置,因而称为倒排索引(inverted index)。带有倒排索引的文件我们称为倒排索引文件,简称倒排文件(inverted file)。
信息
特殊要求
海量数据
构建方法
使用hash去重单词term
中文名
倒排索引
外文名
inverted index
倒排索引概述
在关系数据库系统里,索引是检索数据最有效率的方式,。但对于搜索引擎,它并不能满足其特殊要求:1)海量数据:搜索引擎面对的是海量数据,像Google,百度这样大型的商业搜索引擎索引都是亿级甚至百亿级的网页数量 ,面对如此海量数据 ,使得数据库系统很难有效的管理。2)数据操作简单:搜索引擎使用的数据操作简单 ,一般而言 ,只需要增、 删、 改、 查几个功能 ,而且数据都有特定的格式 ,可以针对这些应用设计出简单高效的应用程序。而一般的数据库系统则支持大而全的功能 ,同时损失了速度和空间。最后 ,搜索引擎面临大量的用户检索需求 ,这要求搜索引擎在检索程序的设计上要分秒必争 ,尽可能的将大运算量的工作在索引建立时完成 ,使检索运算尽量的少。一般的数据库系统很难承受如此大量的用户请求 ,而且在检索响应时间和检索并发度上都不及我们专门设计的索引系统。 [1] 
收起全文
精华内容
下载资源
问答
  • 倒排索引

    2021-03-10 11:35:53
    CRDB中支持的倒排索引解析 关于倒排索引 倒排索引列类型 示例 通用倒排索引解析 倒排索引相关概念 示例 CRDB中支持的倒排索引解析 https://www.cockroachlabs.com/docs/v20.2/inverted-indexes.html 关于...

    目录

    CRDB中支持的倒排索引解析

    关于倒排索引

    倒排索引列类型

    SQL示例1

    倒排索引查询

    SQL示例2

    SQL示例3

    SQL示例4

    通用倒排索引解析

    倒排索引与正向索引的区别

    倒排索引相关概念

    示例


    CRDB中支持的倒排索引解析

    https://www.cockroachlabs.com/docs/v20.2/inverted-indexes.html

    关于倒排索引

    倒排索引存储从容器列(例如JSONB文档)中的值到保留该值的行的映射,用于加速搜索,例如,“输出表中包含键值对{"location":"NYC"}的JSON列的所有行。倒排索引通常用于文档检索系统。

    标准索引适合基于对排序数据的前缀进行搜索,但是数据类型JSONB或者arrays只有在全表扫描的情况下完成查询,因为他们不遵循普通的值前缀比较运算。相对于标准索引,JSONB尤其需要建立索引的方式更加关注细节,这就是倒排索引有优势的地方。

    倒排索引列类型

    • JSONB
    • ARRAYS
    • Spatial data(GEOMETRY and GEOGRAPHY types)

    JSONB数据类型建立在2个结构体上,

    • Objects - 键值对的集合
    • Arrays - 数组中的每个值都是按顺序排列的

    SQL示例1

    创建倒排索引

    输入,

    CREATE TABLE users (
        user_profile JSONB
      );
    
    INSERT INTO users (user_profile) VALUES
        ('{"first_name": "Lola", "last_name": "Dog", "location": "NYC", "online" : true, "friends" : 547}'),
        ('{"first_name": "Ernie", "status": "Looking for treats", "location" : "Brooklyn"}'),
        ('{"first_name": "Carl", "last_name": "Kimball", "location": "NYC", "breed": "Boston Terrier"}'
      );
      
    CREATE INVERTED INDEX ON users (user_profile);
    
    SELECT *, jsonb_pretty(user_profile) FROM users;

    输出,

    倒排索引查询

    倒排索引支持直接使用以下运算符进行查询,仅支持基于JSONB类型的列的JSONB格式内容查询

    1. 被包含:<@ ----JSONB, ARRAYS支持

    SQL示例2

    输入,

    select * from users where user_profile <@ '{"first_name": "Ernie", "location": "Brooklyn", "status": "Looking for treats", "sta":"ok"}';
    

    输出,

    2. 包含:@> ----JSONB, ARRAYS支持

    SQL示例3

    输入,

    select * from users where user_profile @> '{"location":"NYC"}';

    输出,

    3. 相等:----JSONB支持

    写法不同,结果同上

    SQL示例4

    输入,

    select * from users where user_profile -> 'location' = '"NYC"';
    

    输出,

     

    通用倒排索引解析

    https://www.cnblogs.com/zlslch/p/6440114.html

    倒排索引与正向索引的区别

    • 正向索引(forward index)结构如下

           “文档1”的ID > “单词1”的ID,出现次数,出现位置列表;“单词2”的ID,出现次数,出现位置列表;…………

           “文档2”的ID > 此文档出现的“单词ID”列表

    • 反向索引(inverted index)结构如下

           “单词1”的ID > “文档1”的ID,出现次数,出现位置列表;“文档2”的ID,出现次数,出现位置列表;…………

           “单词2”的ID > 带有此单词的“文档ID”列表

    倒排索引相关概念

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

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

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

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

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

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

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

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

    示例

    1. 简单的倒排索引示例

    单词ID 单词 倒排列表(DocID)
    1 中文 1, 2
    2 1, 2, 3, 4, 5
    3 英文 3, 4
    4 1, 2, 3, 4, 5
    5 不同 5

    2. 带有单词频率信息的倒排索引

    单词ID

    单词

    倒排列表(DocID)

    1

    中文

    1, 2

    2

    1, 2, 3, 4, 5

    3

    英文

    3, 4

    4

    1, 2, 3, 4, 5

    5

    不同

    5

    3. 带有单词频率、文档频率和出现位置信息的倒排索引

    *位置信息非必须

    单词ID

    单词

    文档频率

    倒排列表(DocID;TF

    1

    中文

    2

    (1;1;<1>), (2;1;<1>)

    2

    5

    (1;1;<2>), (2;1;<2>), (3;1;<2>), (4;1;<2>), (5;1;<2>)

    3

    英文

    2

    (3;1;<3>), (4;1;<5>)

    4

    5

    (1;1;<6>), (2;1;<8>), (3;1;<6>), (4;1;<8>), (5;1;<6>)

    5

    不同

    1

    (5;1;<9>)

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

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 6,693
精华内容 2,677
关键字:

倒排索引