倒排索引增量更新如何被实时检索？

怼烎@ 2023-03-13 13:49 7阅读 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

当索引的规模很大的时候，一般不会存储在内存中，而是存储在磁盘中，这时候，用上面的双缓存切换的机制更新就不信了，此时常用的方案有全量结合增量索引  
维护一个全量索引，为了搜索效率全量索引不加锁，新增加的文档，维护一个在内存中的倒排索引，也就是增量索引，当查询发生的时候，我们同时查询全量和增量索引，合并查询的结果。

全量结合增量的策略很实用，但是增量索引不可能一直在内存中增长，必然要将增量索引定期的合并到全量索引中，这里用到的是 滚动合并法：

具体就是把索引按照多层次分开，再进行归并排序 ，保证小索引合并到中索引再合并到大索引，避免的是 大索引产生大量的复制操作的问题