01正向索引、倒排索引

  • 1.什么是索引

1)索引就好比一本书的目录,它能让你更快的找到自己想要的内容。
2)让获取的数据更有目的性,从而提高数据库检索数据的性能。
官方:
索引是为了加速对表中数据行的检索而创建的一种分散的存储结构。索引是针对表而建立的,它是由数据页面以外的索引页面组成的,每个索引页面中的行都会含有逻辑指针,以便加速检索物理数据。

  • 2.正向索引(forward index)
以文档id为关键字,表中记录文档中每个字的位置信息;查找时扫描表中每个文档中字的信息直到找到所有包含查询关键字的文档。

这种组织方法在建立索引的时候结构较为简单,建立比较方便且易于维护。
新增文档加入: 直接为该文档建立一个新的索引块,挂接在原来索引文件的后面;
文档删除: 直接找到该文档号文档对应的索引信息,将其删除。

优缺点:
检索效率低,只能运用于简单场景。

id关键字
01操作系统、linux、Windows、shell
02SSH、linux、shell
  • 3.反向索引(inverted index)

反向索引也叫倒排索引

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

优缺点:
查询时由于可以一次查到关键字所对应的所有文档,所以查询效率高于正排索引;
由于每个字或词对应的文档数量在动态变化,所以倒排索引的建立和维护难度较为复杂。

关键字id
操作系统01
linux01、02
SSH02
......

随意搜索任意一个单词,Elasticsearch只要遍历一下这个表,就可以知道哪些文档被匹配到。
反向索引里面不止记录了单词与文档的对应关系,它还维护了很多其他有用的数据。如:每个文档一共包含了多少个单词,单词在不同文档中的出现频率,每个文档的长度,所有文档的总长度等等。这些数据用来给搜索结果进行打分,如搜索linux时,那么出现linux这个单词次数最多的文档会被优先返回,因为它匹配的次数最多,和我们的搜索条件关联性最大,因此得分也最多。
反向索引是不可更改的,一旦它被建立了,里面的数据就不会再进行更改。这样做就带来了以下几个好处:
1.没有必要给反向索引加锁,因为不允许被更改,只有读操作,所以就不用考虑多线程导致互斥等问题。
2.索引一旦被加载到了缓存中,大部分访问操作都是对内存的读操作,省去了访问磁盘带来的io开销。
3.因为反向索引的不可变性,所有基于该索引而产生的缓存也不需要更改,因为没有数据变更。
4.使用反向索引可以压缩数据,减少磁盘io及对内存的消耗。

02倒排索引的组成

倒排索引主要由单词词典(Term Dictionary)倒排列表(Posting List) 组成
倒排索引的重要组成,记录所有文档的单词,一般都比较大,记录单词到倒排列表的关联信息,
单词词典一般用B+Trees来实现,存储在内存中。

Last modification:June 3, 2022
如果觉得我的文章对你有用,请随意赞赏