正排索引和倒排索引

一、简介

正排索引：一个未经处理的数据库中，一般是以文档ID作为索引，以文档内容作为记录。
倒排索引：Inverted index，指的是将单词或记录作为索引，将文档ID作为记录，这样便可以方便地通过单词或记录查找到其所在的文档。

二、倒排索引

创建倒排索引，分为以下几步。

2.1 形成文档列表

lucene首先对原始文档数据进行编号（DocID），形成列表，就是一个文档列表

2.2 创建倒排索引列表

对文档中数据进行分词，得到词条。对词条进行编号，以词条创建索引。保存包含这些词条的文档的编号信息。

例如 谷歌之父–> 谷歌、之父

2.3 搜索的过程

1. 当用户输入任意的词条时，首先对用户输入的数据进行分词，得到用户要搜索的所有词条；
2. 拿着这些词条去倒排索引列表中进行匹配；
3. 找到这些词条就能找到包含这些词条的所有文档的编号；
4. 根据这些编号去文档列表中找到文档。

2.4 使用场景

solr和elastic search

三、正排索引

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

因为索引是基于文档建立的，若是有新的文档加入，直接为该文档建立一个新的索引块，挂接在原来索引文件的后面。

若是有文档删除，则直接找到该文档号文档对应的索引信息，将其直接删除。但是在查询的时候需对所有的文档进行扫描以确保没有遗漏，这样就使得检索时间大大延长，检索效率低下。

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

文档编号（id）	文档内容
1	我喜欢数学
2	我喜欢编程
3	我考试数学成绩很好

使用场景

mysql和postgresql

优化

在我们关系型库中索引为了兼顾插入和查询的性能，都采用了排序树例如：B-Tree/B+Tree这样的数据结构来存储索引。

四、正向和倒排对比

概念区别

• 正向索引是最传统的，根据id索引的方式。但根据词条查询时，必须先逐条获取每个文档，然后判断文档中是否包含所需要的词条，是根据文档找词条的过程。

• 而倒排索引则相反，是先找到用户要搜索的词条，根据词条得到保护词条的文档的id，然后根据id获取文档。是根据词条找文档的过程。

优缺点

正向索引：

• 优点：
  • 可以给多个字段创建索引
  • 根据索引字段搜索、排序速度非常快
• 缺点：
  • 根据非索引字段，或者索引字段中的部分词条查找时，只能全表扫描。

倒排索引：

• 优点：
  • 根据词条搜索、模糊搜索时，速度非常快
• 缺点：
  • 只能给词条创建索引，而不是字段
  • 无法根据字段做排序