倒排索引增量更新如何被实时检索? 怼烎@ 2023-03-13 13:49 13阅读 0赞 #### 正排索引与倒排索引 #### 索引的目的: 使根据 key 查询 value 的速度变快 正排索引:Forward Index ,以一个对象的唯一ID 为Key 的哈希索引结构 倒排索引:Inverted Index 根据具体内容,反过来查询文档 key ,根据内容(字典),查询对应的文档列表(记录列表) #### 倒排索引的创建: #### 1 文档唯一编号,排序,遍历文档 2 解析文档,生成, <关键字,文档ID,关键字Index> (查询多个关键字时,可以比较多个关键字的位置) 3 生成 关键字 对应的 (文档ID,关键字Index) 的 记录列表 这样查询某个关键字,就能得到所有包含关键字的文档ID的 记录列表 O(1) 当查询多个关键字时,就需要依次查询出 多个记录列表,然后进行归并排序 ,取出其中的交集,O(m+n+…) 可想而知,一个支持根据内容查询文档的检索引擎,需要很多庞大的倒排索引支持,无论有多少的历史数据,当倒排索引建立之后,查询速度都会变快,那么当一些新的数据加入的时候,如何立刻被检索到? #### 倒排索引的更新是如何设计的 ? #### 假设你设计一个倒排索引,将这个倒排索引存储在内存中,这会让检索系统的检索速度很快,假设这个索引规模不大,当有一个新的文档录入时,完全可以按照上面创建倒排索引的方法,增量的去将文档遍历,增加到对应的关键字 记录列表中 但这样存在一个问题,当我们更新文档,会给这个倒排索引加上锁,这样当用户访问这个索引时,就会引发错误和崩溃 #### 那么如何去增量的更新索引呢? #### 这里用到的思想是,双缓冲的概念 Double Buffer , 同时维护两个一样的索引,索引A和索引B,索引A只提供读取功能,索引B只提供写的功能,这里AB双缓冲的设计概念其实也是读写分离, 增量的索引更新到索引B中,写入由B负责,这样就不会有加锁产生的问题,当B更新完成之后,进行原子操作,将访问指针从A切换到B上面,完成读索引的切换 #### redis - rehash #### 这里其实和 redis 中的 rehash 是相似的设计 https://blog.csdn.net/qq\_28018283/article/details/103710590 ReHash 字典 章节 rehash的过程: 字典键值对存放在 ht\[0\] * 1 参照要执行的操作和字典中键值对的个数,为ht\[1\] 哈希表分配空间, * 2 将保存在 ht\[0\] 中的键值对重新计算哈希值和索引,然后存放到ht\[1\]中 * 3 当 ht\[0\] 中的数据全部迁移到 ht\[1\] 后,检查是否整个表迁移完成 rehash ht\[0\].used==0 已全部rehash到 ht\[1\] 之后,将 ht\[1\] 设为 ht\[0\] ,并将ht\[1\]新创建一个空白哈希表 -> 重复步骤1 当索引的规模很大的时候,一般不会存储在内存中,而是存储在磁盘中,这时候,用上面的双缓存切换的机制更新就不信了,此时常用的方案有全量结合增量索引 维护一个全量索引,为了搜索效率全量索引不加锁,新增加的文档,维护一个在内存中的倒排索引,也就是增量索引,当查询发生的时候,我们同时查询全量和增量索引,合并查询的结果。 全量结合增量的策略很实用,但是增量索引不可能一直在内存中增长,必然要将增量索引定期的合并到全量索引中,这里用到的是 滚动合并法: 具体就是把索引按照多层次分开,再进行归并排序 ,保证小索引合并到中索引再合并到大索引,避免的是 大索引产生大量的复制操作的问题
相关 倒排索引 倒排索引的核心组成:(包含两个部分) 单词词典(Term Dictionary):记录所有文档的单词,记录单词到倒排列表的关联关系 单词词 Myth丶恋晨/ 2023年07月03日 03:21/ 0 赞/ 25 阅读
相关 倒排索引增量更新如何被实时检索? 正排索引与倒排索引 索引的目的: 使根据 key 查询 value 的速度变快 正排索引:Forward Index ,以一个对象的唯一ID 为Key 的哈希索引结构 怼烎@/ 2023年03月13日 13:49/ 0 赞/ 14 阅读
相关 倒排索引 倒排索引是 es 中非常重要的索引结构,是从文档词项到文档 ID 的一个映射过程。 8.1 "正排索引" 我们在关系型数据库中见到的索引,就是“正排索引”。 8.2 灰太狼/ 2022年10月31日 14:59/ 0 赞/ 220 阅读
相关 倒排索引 1.什么是倒排索引 倒排索引源于实际应用中需要根据属性的值来查找记录。这种索引表中的每一项都包括一个属性值和具有该属性值的各记录的地址。由于不是由记录来确定属性值,而是 ╰半夏微凉°/ 2022年08月27日 11:42/ 0 赞/ 288 阅读
相关 倒排索引 倒排索引简单地就是:根据单词,返回它在哪个文件中出现过,而且频率是多少的结果。这就像百度里的搜索,你输入一个关键字,那么百度引擎就迅速的在它的服务器里找到有该关键字的文件,并根 我不是女神ヾ/ 2022年07月30日 13:25/ 0 赞/ 258 阅读
相关 Sphinx实时索引,用增量索引实现索引更新 我们前面知道,用./indexer --all 可以生成所有索引。当我们的数据很大,表的数据每天会逐渐添加,我们不可能再去重新生成下所有索引,这样性能方面会很差,那么,如何 本是古典 何须时尚/ 2022年07月14日 08:28/ 0 赞/ 262 阅读
相关 倒排索引 创建两个文件数据,并上传到hdfs data file edit file file view search data2 abc - 日理万妓/ 2022年06月06日 04:41/ 0 赞/ 346 阅读
相关 全文检索&倒排索引 全文检索&倒排索引 设计 ![951ueNT.png][] 全文检索 建立索引,快速定位搜索 倒叙索引 分词 根据分词来定位 梦里梦外;/ 2022年06月01日 12:54/ 0 赞/ 206 阅读
相关 倒排索引 1.单词——文档矩阵 单词-文档矩阵是表达两者之间所具有的一种包含关系的概念模型,图3-1展示了其含义。图3-1的每列代表一个文档,每行代表一个单词,打对勾 我不是女神ヾ/ 2022年05月22日 06:47/ 0 赞/ 318 阅读
相关 倒排索引 倒排索引(英语:Inverted index),也常被称为反向索引、置入档案或反向档案,是一种索引方法,被用来存储在全文搜索下某个单词在一个文档或者一组文档中的存储位置的... 小灰灰/ 2020年05月01日 19:45/ 0 赞/ 920 阅读
还没有评论,来说两句吧...