乐趣区

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

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

退出移动版