当前位置:网站首页>搜索 正排索引 和 倒排索引 区别
搜索 正排索引 和 倒排索引 区别
2022-07-05 15:48:00 【软件工程小施同学】
一、什么是正排索引(forward index)?
简言之,由key查询实体的过程,使用正排索引。
例如,用户表:
t_user(uid, name, passwd, age, sex)
由uid查询整行的过程,就是正排索引查询。
画外音:时间复杂度可以认为是O(1)。
二、什么是倒排索引(inverted index)?
与正排索引相反,由item查询key的过程,使用倒排索引。
对于网页搜索,倒排索引可以理解为:
Map<item, list<url>>
能够由查询词快速找到包含这个查询词的网页的数据结构。
画外音:时间复杂度也是O(1)。
举个例子,假设有3个网页:
url1 -> “我爱北京”
url2 -> “我爱到家”
url3 -> “到家美好”
这是一个正排索引:
Map<url, page_content>。
分词之后:
url1 -> {我,爱,北京}
url2 -> {我,爱,到家}
url3 -> {到家,美好}
这是一个分词后的正排索引:
Map<url, list<item>>。
分词后倒排索引:
我 -> {url1, url2}
爱 -> {url1, url2}
北京 -> {url1}
到家 -> {url2, url3}
美好 -> {url3}
由检索词item快速找到包含这个查询词的网页Map<item, list<url>>就是倒排索引。
画外音:明白了吧,词到url的过程,是倒排索引。
正排索引和倒排索引是spider和build_index系统提前建立好的数据结构,为什么要使用这两种数据结构,是因为它能够快速的实现“用户网页检索”需求。
画外音,业务需求决定架构实现,查询起来都很快。
边栏推荐
- 抽象类和接口的区别
- ES6 drill down - Async functions and symbol types
- Enterprise backup software Veritas NetBackup (NBU) 8.1.1 installation and deployment of server
- 16. [stm32] starting from the principle, I will show you the DS18B20 temperature sensor - four digit digital tube displays the temperature
- Clock switching with multiple relationship
- Using graylog alarm function to realize the regular work reminder of nail group robots
- 漫画:什么是分布式事务?
- 一些認知的思考
- 项目sql中批量update的时候参数类型设置错误
- 利用GrayLog告警功能实现钉钉群机器人定时工作提醒
猜你喜欢
Convert obj set to entity set
PSPNet | 语义分割及场景分析
英特尔第13代Raptor Lake处理器信息曝光:更多核心 更大缓存
vant tabbar遮挡内容的解决方式
Defining strict standards, Intel Evo 3.0 is accelerating the upgrading of the PC industry
Intelligent metal detector based on openharmony
DeSci:去中心化科学是Web3.0的新趋势?
CISP-PTE之PHP伪协议总结
Clock switching with multiple relationship
抽象类中子类与父类
随机推荐
移动办公时如何使用frp内网穿透+teamviewer方式快速连入家中内网主机
Background system sending verification code function
List de duplication and count the number
OneForAll安装使用
Intel 13th generation Raptor Lake processor information exposure: more cores, larger cache
Intelligent metal detector based on openharmony
[vulnerability warning] cve-2022-26134 conflict Remote Code Execution Vulnerability POC verification and repair process
17.[STM32]仅用三根线带你驱动LCD1602液晶
异常com.alibaba.fastjson.JSONException: not match : - =
Cartoon: what is distributed transaction?
英特尔第13代Raptor Lake处理器信息曝光:更多核心 更大缓存
[graduation season] as a sophomore majoring in planning, I have something to say
新春限定丨“牛年忘烦”礼包等你来领~
obj解析为集合
ES6深入—ES6 Generator 函数
对象和类的关系
助力数字经济发展,夯实数字人才底座—数字人才大赛在昆成功举办
Cs231n notes (medium) -- applicable to 0 Foundation
Five common negotiation strategies of consulting companies and how to safeguard their own interests
定义严苛标准,英特尔Evo 3.0正在加速PC产业升级