学习极客实践课程《检索技术核心20讲》https://time.geekbang.org/column/article/215243

课程分为基础篇、进阶篇、系统案例篇

检索技术它是更底层的通用技术它研究的是如何将我们所需的数据高效地取出来。

不管是在数据库和搜索引擎里还是在新闻推荐平台、电商平台、生活服务平台中如果我们把这些业务场景抽象出来它们的本质其实都是在海量的信息中快速筛选出我们需要的内容或服务而这都和检索技术紧密相关。

基础篇

数组和链表分别代表了连续空间和不连续空间的最基础的存储方式它们是线性表Linear

线性数据结构可以使用二分查找如数组、链表、队列等兼顾数组随机访问和链表增删方便的特点通过灵活改造将链表挂数组中可以一定程度改善

低效率寻址的缺点比如说我的链表就只有两个节点每个节点都存储了一个小的有序数组。

这样在检索的时候我可以用二分查找的思想。

思考1对于有序数组的高效检索为什莫使用二分查找而不是3-7、4-6分查找在缺乏分布信息的情况下”那么二分是效率最优的。

如果有了分布信息比如说数据是均匀分布的最小的数是1最大的数是1000那么当我们想查询5的时候我们第一次查询的位置就不是数组中间了而是在数组前5/1000的位置进行查找。

这种基于均匀分布假设的查找方式叫做“插值查找”。

呢方式1是可以采用两次二分查找分别在所有数据集查询x、y然后中间元素顺序访问确定区间方式2是首先一次二分查找x再从[x,TAIL]进行一次二分查找y中间元素顺序访问确定区间。

方式3首先查找y等。

方式1的实践复杂度为logN

树结构二分检索

基础的线性结构可以组合成树结构树结构实现方式可以是类似链表挂数组链表节点的数据节点可以是数组也可以是单值的结构如BST树BST树就类似一个书目录一个磁盘文件夹主要作用就是快速减少查询范围。

树结构可以巧妙的利用二分查找的特点。

前提是这棵树是BST二叉排序树

BST面对数据分布不均衡的时候容易退化为链表这样就无法达到快速减少

然后出现了AVL、红黑树这样的通过自旋等方式保证BST自平衡的结构。

像Redis中的linkedlist实现方式之一就有使用到跳表。

链表的特点不能随机访问因此不能很方便的快速到达所需要的位置区间。

跳表就是解决这个问题通过多层的一个链表组织结构上层的作为下层节点的目录底层的链表阶段存储数据。

上层的节点逐层递增理想的跳表每层基本数量维持在2的N0、1、2…次方。

在跳表的论文中有做实验提到在random

level的实际实现中将1/2改为1/4会有一定的检索效率提升。

而且空间利用率也会更好。

查找的时候从顶层开始逐渐在当层右移动、下层移动最终找到目标区间访问寻找到target。

2^n

个节点做一次链接的特性我们就需要重新修改许多节点的后续指针这会带来很大的开销。

因此在检索性能和修改性能做均衡保证是近似理想状态即可因此当新节点插入时我们不去修改已有的全部指针而是仅针对新加入的节点为它建立相应的各级别的跳表指针具体的过程

首先我们需要确认新加入的节点需要具有几层的指针。

我们通过随机函数来生成层数比如说我们可以写一个函数

(1/2)^n

层。

这样通过简单的随机生成指针层数的方式我们就可以保证指针的分布在大概率上是平衡的。

在确认了新节点的层数

以后接下来我们需要将新节点和前后的节点连接起来也就是为每一层的指针建立前后连接关系。

其实每一层的指针链接你都可以看作是一个独立的单链表的修改因此我们只需要用单链表插入节点的方式完成指针连接即可。

如插入节点先找到数据节点单链表也就是最后一层插入节点此时是最底层单链表的插入修改上一个节点的pre和插入节点的next指针即可下面是为生成level节点具体多少层就是randomLevel()函数决定的对于每个level需要从每层的head节点开始沿着next一直查找需要插入的位置因为有了数据节点可以很方便定位current.var

data.val

next.val主角这样就在current后面插入当前level的指针节点。

为了保证跳表的检索空间平衡跳表为每个节点随机生成层级这样的实现方式比

AVL

思考1什么时候使用红黑树而不是跳表跳表虽然实现比较简单理想结构查询效率为logN)但是跳表性能不太稳定检索性能最差是ON因为跳表是依赖于大量链接的随机分布来提高检索性能的但是随机分布的性能并不是最优的在极端情况下还可能退化到ON。

另外一个点就是内存占用率较高因为一个节点要带有多个指针这会带来更大的存储开销。

因此如果我们的应用场景要求检索性能稳定节省内存并且没有遍历需求插入频率也不高的话(红黑树频繁插入数据时加锁代价会比跳表大)那么使用红黑树更合适。

思考2跳表能否替代数组

每个结构都有各自的优缺点需要针对具体的数据场景合理选择结构需要不仅仅考虑内存空间效率数组的确比跳表更加稳定。

不过内存碎片化问题这个会有内存碎片处理来解决。

其实还有两点是很关键的一个是考虑实际情况内存有局部性原理对连续空间的处理会更高效另一个是考虑范围查找数组将查询结果成片复制出来效率会更高内存拷贝技术内存局部性原理

哈希检索

在实际应用中我们经常会面临需要根据键Key来查询数据的问题。

比如说给你一个用户

首先想到的就是将所有key排序使用数组顺序存储key、val这样就能实现二分查找。

比如用户的

或者使用BST、跳表等实现。

这样的平均时间复杂度就是logN。

假如ID是字符串呢可以采用Hash的方式将字母映射为数字。

一种O1的方案就是将key利用Hash函数转为数组下标利用数组随机访问的特点

假如ID范围很大无法申请这莫大空间的数组呢可以对Hash数值进行特殊计算操作比如对最大数组长度取余数。

这种情况会导致Hash冲突。

线性探测解决哈希冲突解决Hash冲突的方式有开放寻址法-线性探测逻辑就是发生冲突之后就是向前

查询可以插入的位置另外还有指数探测等。

查询的逻辑就是找到key对应的数组位置判断元素是否为空

是否和当前key一样不一样的话就按照约定的如开放寻址法继续寻找直到找到或者找不到为止。

其他方法解决哈希冲突哈希冲突会影响哈希表的整体性能插入和查询的时候都会沿着哈希表进行逐个遍历复杂度为ON。

为了解决这个问题可以采用二次探测、双散列的方式优化。

i^2第一次探查位置为

对于开放寻址法来说无论使用什么优化方案随着插入的元素越多、哈希表越满插入和检索的性能也就下降得越厉害。

在极端情况下当哈希表被写满的时候为了保证能插入新元素我们只能重新生成一个更大的哈希表将旧哈希表中的所有数据重新

Hash

Re-Hash这样会造成非常大的额外开销。

因此在数据动态变化的场景下使用开放寻址法并不是最合适的方案。

思考1使用开放寻址法解决哈希冲突的哈希表能直接删除某元素吗不能直接简单的删除可以增加一个删除flag。

哈希表在查找元素的时候不是只看下标的还要对比下标位置的元素值相同才算找到。

这也是为什么会有线性探查等方法。

不能直接删除的问题在于直接删除会把探查序列中断。

举个例子:有三个元素abc的hash值是冲突的那么探查序列会把他们放在三个位置上比如123探查序列是123如果我们把b删了那么2这个位置就空了。

这时候要查询c探查序列就会在2的位置中断查不到c。

二值状态检索

比如判断一个对象是否存在查询某个二值状态结果可以使用数组、跳表等二分查找也可使用哈希表O(1)查找。

是否还有优化方案呢

就可以了。

数量很少并且固定比较适合当数量很大占用空间会比较大最直观的一个想法就是使用最少字节的类型来定义数组比如说使用

char

使用哈希表的话key存储IDval存储0、1支持key为字符串数量很少比较适合为了解决空间占用大需要压缩哈希表数组的长度当数量很大而且不固定范围可能要面临rehash等比较占空间和耗时。

bit

为单位的数据类型。

因此我们往往需要对其他类型的数组进行一些转换设计使其能对相应的

bit

压缩哈希表长度但是又不能使用线性探测方法解决hash冲突因为数量足够大哈希冲突又比较多这时可以采用线性探测-双散列的思想解决哈希冲突这就是布隆过滤波器的i思想。

个哈希函数就会得到

1。

布隆过滤器和位图最大的区别就在于我们不再使用一位来表示一个对象而是使用

布隆过滤器的错误率存在一定程度地误判只能判断一个元素一定不存在不能判断一个元素一定存在。

针对场景我们希望用更小的代价快速判断

思考1布隆过滤器中一个元素能否直接删除不能直接删除因为某个位置的状态可能是多个hash函数的即多个元素的映射位置删了可能会影响其他元素是否存在的判断。

有些改进的布隆过滤器采用计数值方式替换0、1可以解决这个问题代价就是需要额外额bit来存储计数值。

倒排检索

假如一篇文章包含题目、内容需要根据关键字查找题目和根据关键字查找内容两个需求关键字查找题目这个就比较适合正排索引结构如哈希表第二个根据关键字查找内容使用哈希表就比较费力了因为需要遍历每个key获取val在判断有么有包含指定内容时间复杂度OK*

倒排索引的核心其实并不复杂它的具体实现其实是哈希表只是它不是将文档

或者题目作为

给文档编号作为唯一标识排序遍历文档。

解析出文档关键字生成关键字文档ID关键字位置信息。

关键字作为key插入哈希表中如果已经存在就在哈希表的postinglist后面追加节点记录上面的信息。

重复2-3直至处理所有文档。

为什么需要存储关键字位置信息因为在许多检索场景中都需要显示关键字前后的内容比如在组合查询时我们要判断多个关键字之间是否足够近。

所以我们需要记录位置信息以方便提取相应关键字的位置。

思考1如果有个需求是根据文档作者查询文档怎么设计呢第一个方案可以对文档的作者设置一个作者标签为作者标签这些内容创建倒排索引不再一个内容倒排索引文档中实现是怕文档内容包含

作者名字

list中加域标明是作者还是内容这样就使用一个倒排索引结构就可以了posting

list分域就是一个元素里加上域标识。

举个例子一篇文章有标题作者内容三个域而“李白”这两个字可能出现在这三个位置。

因此key和posting

key

[id1标题域:0作者域:1内容域:0][id2标题域:1作者域:0内容域:1]

思考2:邮件敏感词过滤检测适不适合使用倒排索引邮件只需要检测一次因此对邮件做倒排索引并不适用。

而且倒排索引也解决不了近义词问题。

准备一个敏感词字典。

遍历邮件提取关键词去敏感词字典中查找找到了就说明邮件有敏感词。

这里的核心问题是如何提取关键词和如何在敏感词字典中查询。

一种方式是用哈希表存敏感词字典然后用分词工具从邮件中提取关键字然后去字典中查。

另一种方式是trie树来实现敏感词字典然后逐字扫描邮件用当前字符在trie树中查找。

不过这两种方式都无法解决近义词或者各种刻意替换字符的场景。

要想解决这种问题要么提供近义词字典要么得使用大量数据进行训练和学习用机器学习进行打分将可疑的高分词找出来。

其实这种近义词处理方案和搜索引擎解决近义词和查询纠错的过程很像。

**为什么需要排序**查询一个关键字的时候可以直接获取该关键字下的所有文档信息文档ID、关键字位置等如果查询多个关键字就需要对两条postinglist上的文档信息取交集如果是无序的那么时间复杂度为OM*N如果是排序的就能使用如归并排序快速排序时间代价就会将为OM

步使用指针

求交集是一个最重要、最耗时的操作postinglist合并的时候除了使用归并排序还有跳表、哈希表、位图等结构思想优化效率的方法。

跳表法相互二分加速取交集

假如归并法遇到下面的情况那么B的指针需要等待A指针移动500-2次才找到交集500。

显然数据量大的时候很耗时。

因此可以使用跳表实现postinglist只需要查找log500-2次后面元素同理假如A链表比B链表元素稀疏那就反过来拿着A的元素去B中二分查找即互相二分查找。

posting

可以都存储在内存中并且变化不太频繁的话那我们还可以利用可变长数组来代替链表。

可变长数组的数组的长度可以随着数据的增加而增加。

一种简单的可变长数组实现方案就是当数组被写满时我们直接重新申请一个

倍于原数组的新数组将原数组数据直接导入新数组中。

这样我们就可以应对数据动态增长的场景。

那对于两个

求交集我们同样可以先使用可变长数组再利用相互二分查找进行归并。

而且由于数组的数据在内存的物理空间中是紧凑的因此

CPU

哈希表加速的思路其实很简单就是当两个集合要求交集时如果一个集合特别大另一个集合相对比较小那我们就可以用哈希表来存储大集合。

这样我们就可以拿着小集合中的每一个元素去哈希表中对比如果查找为存在那查找的元素就是公共元素否则就放弃。

查询代价是OM如果M的值很大那么它的性能不一定比跳表法更好了。

posting

list我们将它们提前存入哈希表。

原始的postinglist也需要保留哈希表遍历不太方便后续可能要进行posting

位图法加速倒排索引取交集

list可以使用位运算进行检索加速具体就是为每个倒排字典的key创建长度大小相等的bitmap如果一个文档信息出现在postinglist中就将位图中该元素可以是ID对应的位置值设置为1。

查询过程如果需要取交集直接两个bitmap与运算即可由于位图的长度是固定的因此两个位图的合并运算时间代价也是固定的。

并且由于

CPU

执行位运算的效率非常快因此在位图总长度不是特别长的情况下位图法的检索效率还是非常高的。

局限性

仅适合存储ID的简单的postinglist复杂对象不适合。

仅适合元素稠密的场景如果是稀疏bitmap位运算和存储的开销反而会比使用链表更大。

会占用大量空间每个bitmap必须固定长度比如ID是int32那一个bitmap大小就约为512M

1024

Bimap设计思想缩短bitmap的bit长度在前面分层加一个prefix

bit

基数数组比如将一个32bit分为两部分高16位可表示2^16个桶低16位表示一个子位图。

位在有序数组中二分查找看对应的桶是否存在。

如果存在第二步就是将桶中的位图取出拿着低

Olog

对于空间占用假如根据数据分布因为高16位会存在值一样的情况而且一般比较稀疏这样可以数组假如所有元素高16位都是相同的

2^16

相比512M大大节省空间。

但是仅限于这种极端情况假如高16位都不一样那么高16位有2^16个桶每个桶对应2

个低位bitmap空间2

相比于位图法这种设计方案就是通过将不存在的桶的位图空间全部省去这样的方式来节省存储空间的。

而代价就是将高

O(1)

每个桶对应子bitmap空间优化当位图元素太稀疏的时候还不如直接使用数组因为一个位图也要占用16bit当元素格式少于4096时候使用初始默认4长度的数组随着数量增对大于4094就动态的使用位图容器。

步比较高

位的所有桶也就是对这两个有序数组求交集所有相同的桶会被留下来。

第

种情况分别是位图和位图求交集、数组和数组求交集、位图和数组求交集。

其中位图和位图求交集我们可以直接使用位运算数组和数组求交集我们可以使用相互二分查找类似跳表法位图和数组求交集我们可以通过遍历数组在位图中查找数组中的每个元素是否存在类似哈希表法。

思考1:在

的求交集过程中有位图和位图求交集、数组和数组求交集、位图和数组求交集这

种场景。

那它们求交集以后的结果我们是应该用位图来存储还是用数组来存储呢考虑到交集元素的数量数组和数组求交集、位图和数组求交集

但是位图和位图的交集需要根据情况而定可以使用预判方法假设A有a个值B有b个值按照平均可以算下间隔比如位图支持总个数为216那么A的平均值间隔为216

^16

百万并发场景中倒排索引与位图计算的实践_倒排索引_京东科技开发者_InfoQ写作社区

联合查询中加速取交集方法

假如在一个系统的倒排索引中有4个不同的key对应四类标签的用户现在需要进行组合key联合查询。

比如在“北京”或在“上海”并且使用“安卓”的用户集合。

抽象成联合查询表达式就是“北京”∪“上海”∩“安卓”

对于联合查询在工业界中有许多加速检索的研究和方法比如调整次序法、快速多路归并法、预先组合法和缓存法。

调整次序法

连续集合有包含关系求交集通过分析key对应集合的数量先排序按照从小到大的集合互取交集这样时间复杂度更低。

连续并集合然会与另外集合取交集对于并集合中子集合和需要取交集的集合元素数量、值相差比较大的时候可以根据分配率逐个与另外集合取交集最后在合并。

A∩B∩C、分配率A∩B∪CA∩B∪A∩C等根据集合元素特性选择合适的计算顺序。

但是调整次序法有一个前提就是集合的大小要有一定的差异这样的调整效果才会更明显。

快速多路归并法

求交集的过程中我们可以利用跳表的性质快速跳过多个元素加快多路归并的效率。

这种方法我叫它快速多路归并法。

个链表的当前元素看作一个有序循环数组list[n]。

并且对有序循环数组从小到大依次处理当有序循环数组中的最小值等于最大值也就是所有元素都相等时就说明我们找到了公共元素。

如四个链表A、B、C、D求交集

第一步四个指针指向4个链表的第一个元素更新最大值max第二步各个链表当前指针值和max对比

如果都像等max为公共元素记录此值每个链表后移指针。

如果某个链表当前值

max利用跳表法快速调整指针到

处理完第四个链表后循环回到第一个链表用循环数组实现直到链表全部遍历完。

预先组合法

预先组合法适合一些常出现的查询对于某些搜索引擎以及一些具有热搜功能的平台中经常会出现一些最新的查询组合。

这些查询组合请求量也很大但是由于之前没有出现过因此我们无法使用预先组合的方案来优化。

这个时候我们会使用缓存技术来优化。

比如使用LRU缓存实现将某次联合查询的结果保存起来一般是双链表加哈希表实现LRU机制方案。

双链表一个合适的实现方案是使用双向链表当一个元素被访问时将它提到链表头。

哈希表优化链表元素访问速度O1获取元素将元素作为key元素所在链表节点的地址作为value

思考1:为什么最好使用双链表而不是单链表因为查询节点k之后需要节点k移动到链表的头部假如查询的时候位置在整个LRU的中间如果链表是单链表的话那么如何把k节点从链表中摘取出来然后链表还不能被打断这就成了一个问题了。

因此我们用双向链表就可以快速地找到k节点的前序节点这样就能完成节点k的摘取操作。