3分钟干货之正排索引与倒排索引

智数清韵
• 阅读 9365

△什么是正排索引(forward index)?
简言之,由key查询实体的过程,使用正排索引。

例如,用户表:
t_user(uid, name, passwd, age, sex)
由uid查询整行的过程,就时正排索引查询。

又例如,网页库:
t_web_page(url, page_content)
由url查询整个网页的过程,也是正排索引查询。

网页内容分词后,page_content会对应一个分词后的集合list。
简易的,正排索引可以理解为:
Map>
能够由网页url快速找到内容的一个数据结构。
画外音:时间复杂度可以认为是O(1)。

△什么是倒排索引(inverted index)?
与正排索引相反,由item查询key的过程,使用倒排索引。

对于网页搜索,倒排索引可以理解为:
Map>
能够由查询词快速找到包含这个查询词的网页的数据结构。
画外音:时间复杂度也是O(1)。

举个例子,假设有3个网页:
url1 -> “我爱北京”
url2 -> “我爱到家”
url3 -> “到家美好”
这是一个正排索引:
Map。

分词之后:
url1 -> {我,爱,北京}
url2 -> {我,爱,到家}
url3 -> {到家,美好}
这是一个分词后的正排索引:
Map>。

分词后倒排索引:
我 -> {url1, url2}
爱 -> {url1, url2}
北京 -> {url1}
到家 -> {url2, url3}
美好 -> {url3}
由检索词item快速找到包含这个查询词的网页Map>就是倒排索引。
画外音:明白了吧,词到url的过程,是倒排索引。

正排索引和倒排索引是spider和build_index系统提前建立好的数据结构,为什么要使用这两种数据结构,是因为它能够快速的实现“用户网页检索”需求。
画外音,业务需求决定架构实现,查询起来都很快。

点赞
收藏
评论区
推荐文章
美凌格栋栋酱 美凌格栋栋酱
6个月前
Oracle 分组与拼接字符串同时使用
SELECTT.,ROWNUMIDFROM(SELECTT.EMPLID,T.NAME,T.BU,T.REALDEPART,T.FORMATDATE,SUM(T.S0)S0,MAX(UPDATETIME)CREATETIME,LISTAGG(TOCHAR(
Wesley13 Wesley13
3年前
SQL
当数据库中数据量特别大的时候,查询的速度就比较慢,这时候需要添加索引,来提高查询速度。索引的优点1通过创建唯一索引,可以保证数据库表中每行数据的唯一性。2加快数据查询速度3在使用分组和排序进行数据查询时,可以显著的减少查询中分组和排序的时间索引的缺点1维护索引需要消耗数据库资源2索引需要占用磁盘空间,索引文件可能会比数据
Wesley13 Wesley13
3年前
MySQL千万级别优化·中
MySQL千万级别的查询优化手段·中单列索引(假设在v\_record表中存在id列的索引)1、WHERE条件使用​EXPLAINSELECT\FROMv\_recordWHEREid2​结论:利用索引进行回表查询2、SELECT字段使用
Wesley13 Wesley13
3年前
MySQL索引的索引长度问题
MySQL的每个单表中所创建的索引长度是有限制的,且对不同存储引擎下的表有不同的限制。在MyISAM表中,创建组合索引时,创建的索引长度不能超过1000,注意这里索引的长度的计算是根据表字段设定的长度来标量的,例如:createtabletest(idint,name1varchar(300),name2varchar(300),nam
Wesley13 Wesley13
3年前
mysql中的回表查询与索引覆盖
了解一下MySQL中的回表查询与索引覆盖。回表查询要说回表查询,先要从InnoDB的索引实现说起。InnoDB有两大类索引,一类是聚集索引(ClusteredIndex),一类是普通索引(SecondaryIndex)。InnoDB的聚集索引InnoDB聚集索引的叶子节点存储行记录,因此InnoDB必须要有且只有一个聚集索引。
Wesley13 Wesley13
3年前
560字带你彻底搞懂:MySQL的索引优化分析
正文一、SQL分析性能下降、SQL慢、执行时间长、等待时间长查询语句写得差索引失效关联查询太多join(设计缺陷)单值索引:在user表中给name属性创建索引,createindexidx\_nameonu
Wesley13 Wesley13
3年前
mysql5.6 分页查询优化
mysql5.6分页查询优化场景:表结构:主键(非自增)contentCode(varchar),过滤条件列为updateTime(timeStamp),已经为timestamp建立索引。搜索sql为:SELECTFROMmy_hello_tableWHEREupdat
Wesley13 Wesley13
3年前
mysql之索引
一.索引:索引是表的目录,在查找内容之前可以先在目录中查找索引位置,以此快速定位查询数据。对于索引,会保存在额外的文件中1.1.创建一个索引:mysqlcreateindexix_classontb3(class_id);QueryOK,0rowsaffected(0.02sec)
Wesley13 Wesley13
3年前
mysql中的分区表
分区表的意义:当数据量非常大时(表的容量到达GB或者是TB),如果仍然采用索引的方式来优化查询,由于索引本生的消耗以及大量的索引碎片的产生,查询的过程会导致大量的随机I/O的产生,在这种场景下除非可以很好的利用覆盖索引,否则由于在查询的过程中需要根据索引回数据表查询,会导致性能受到很大的影响,这时可以考虑通过分区表的策略来提高查询的性能。
Wesley13 Wesley13
3年前
mysql——索引——概念
一、索引索引由数据库表中一列或者多列组合而成,其作用是提高对表中数据的查询速度。索引是创建在表上面的,是对数据表中一列或者多列的值进行排序的一种结构。通过索引,查询数据时可以不必读完记录的所有信息,而只是查询索引列。索引优点:提高检
Stella981 Stella981
3年前
ELK学习笔记之ElasticSearch的索引详解
0x00ElasticSearch的索引和MySQL的索引方式对比Elasticsearch是通过Lucene的倒排索引技术实现比关系型数据库更快的过滤。特别是它对多条件的过滤支持非常好,比如年龄在18和30之间,性别为女性这样的组合查询。倒排索引很多地方都有介绍,但是其比关系型