ElasticSearch学习篇12_《检索技术核心20讲》基础篇

背景

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

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

主要记录企业课程学习过程课程大纲关键点,以文档形式记录笔记。

内容

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

image.png

基础篇

顺序结构二分检索

数组的特点:随机访问,存储空间连续剧,增删性能较慢。
链表的特点:顺序访问,存储空间不连续,增删性能较快。

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

线性数据结构可以使用二分查找,如数组、链表、队列等,兼顾数组随机访问和链表增删方便的特点,通过灵活改造将链表挂数组中可以一定程度改善 "低效率寻址"的缺点,比如说,我的链表就只有两个节点,每个节点都存储了一个小的有序数组。这样在检索的时候,我可以用二分查找的思想。

一些高级结构都是基于数组、链表组合等方式设计实现的。

思考1:对于有序数组的高效检索,为什莫使用二分查找而不是3-7、4-6分查找?在缺乏分布信息的情况下”,那么二分是效率最优的。如果有了分布信息,比如说,数据是均匀分布的,最小的数是1,最大的数是1000,那么当我们想查询5的时候,我们第一次查询的位置就不是数组中间了,而是在数组前5/1000的位置进行查找。这种基于均匀分布假设的查找方式,叫做“插值查找”。

思考2:单值查询可以使用二分,对于有序区间查询[x,y] 呢?方式1是可以采用两次二分查找分别在所有数据集查询x、y,然后中间元素顺序访问确定区间,方式2是首先一次二分查找x,再从[x,TAIL]进行一次二分查找y,中间元素顺序访问确定区间。方式3首先查找y等。方式1的实践复杂度为log(N) + log(N),方式2的时间复杂度为log(x) + log(y-x)。

树结构二分检索

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

树结构可以巧妙的利用二分查找的特点。前提是这棵树是BST(二叉排序树)
image.png

BST面对数据分布不均衡的时候,容易退化为链表,这样就无法达到快速减少 查询范围的目标。
然后出现了AVL、红黑树这样的通过自旋等方式保证BST自平衡的结构。

跳表的二分检索

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

链表的特点不能随机访问,因此不能很方便的快速到达所需要的位置区间。跳表就是解决这个问题,通过多层的一个链表组织结构,上层的作为下层节点的目录,底层的链表阶段存储数据。上层的节点逐层递增,理想的跳表每层基本数量维持在2的N(0、1、2…)次方。在跳表的论文中,有做实验提到,在random level的实际实现中,将1/2改为1/4,会有一定的检索效率提升。而且空间利用率也会更好。

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

数据增删的时候,如果要保证理想链表的每隔 2^n 个节点做一次链接的特性,我们就需要重新修改许多节点的后续指针,这会带来很大的开销。因此在检索性能和修改性能做均衡,保证是近似理想状态即可,因此,当新节点插入时,我们不去修改已有的全部指针,而是仅针对新加入的节点为它建立相应的各级别的跳表指针,具体的过程:

  • 首先,我们需要确认新加入的节点需要具有几层的指针。我们通过随机函数来生成层数,比如说,我们可以写一个函数 RandomLevel(),以 (1/2)^n 的概率决定是否生成第 n 层。这样,通过简单的随机生成指针层数的方式,我们就可以保证指针的分布,在大概率上是平衡的。
  • 在确认了新节点的层数 n 以后,接下来,我们需要将新节点和前后的节点连接起来,也就是为每一层的指针建立前后连接关系。其实每一层的指针链接,你都可以看作是一个独立的单链表的修改,因此我们只需要用单链表插入节点的方式完成指针连接即可。

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

为了保证跳表的检索空间平衡,跳表为每个节点随机生成层级,这样的实现方式比 AVL 树和红黑树更简单。

思考1:什么时候使用红黑树而不是跳表?跳表虽然实现比较简单,理想结构查询效率为log(N),但是跳表性能不太稳定,检索性能最差是O(N),因为跳表是依赖于大量链接的随机分布来提高检索性能的,但是随机分布的性能并不是最优的,在极端情况下还可能退化到O(N)。另外一个点就是内存占用率较高,因为一个节点要带有多个指针,这会带来更大的存储开销。因此,如果我们的应用场景要求检索性能稳定,节省内存,并且没有遍历需求,插入频率也不高的话(红黑树频繁插入数据时,加锁代价会比跳表大),那么使用红黑树更合适。

思考2:跳表能否替代数组? 每个结构都有各自的优缺点,需要针对具体的数据场景合理选择结构,需要不仅仅考虑内存空间效率,数组的确比跳表更加稳定。不过内存碎片化问题,这个会有内存碎片处理来解决。其实,还有两点是很关键的,一个是考虑实际情况,内存有局部性原理,对连续空间的处理会更高效;另一个是考虑范围查找,数组将查询结果成片复制出来效率会更高(内存拷贝技术+内存局部性原理)

哈希检索

在实际应用中,我们经常会面临需要根据键(Key)来查询数据的问题。比如说,给你一个用户 ID,要求你查出该用户的具体信息,如何实现呢?

首先想到的就是将所有key排序,使用数组顺序存储key、val,这样就能实现二分查找。比如用户的 ID 是一个数字,并且范围有限,这样才能申请固定长度的数组空间。
或者使用BST、跳表等实现。这样的平均时间复杂度就是logN。

假如ID是字符串呢?可以采用Hash的方式,将字母映射为数字。一种O(1)的方案就是将key利用Hash函数转为数组下标,利用数组随机访问的特点,

假如ID范围很大,无法申请这莫大空间的数组呢?可以对Hash数值进行特殊计算操作,比如对最大数组长度取余数。这种情况会导致Hash冲突。

线性探测解决哈希冲突:解决Hash冲突的方式有开放寻址法-线性探测,逻辑就是发生冲突之后,就是向前 or 向后 查询可以插入的位置,另外还有指数探测等。查询的逻辑就是找到key对应的数组位置,判断元素是否为空 or 是否和当前key一样,不一样的话就按照约定的如开放寻址法继续寻找,直到找到或者找不到为止。

其他方法解决哈希冲突:哈希冲突会影响哈希表的整体性能,插入和查询的时候都会沿着哈希表进行逐个遍历,复杂度为O(N)。为了解决这个问题,可以采用二次探测、双散列的方式优化。

  • 二次探查就是将线性探查的步长从 i 改为 i^2:第一次探查,位置为 Hash(key) + 1^2;第二次探查,位置为 Hash(key) +2^2;第三次探查,位置为 Hash(key) + 3^2,依此类推。
  • 双散列就是使用多个 Hash 函数来求下标位置,当第一个 Hash 函数求出来的位置冲突时,启用第二个 Hash 函数,算出第二次探查的位置;如果还冲突,则启用第三个 Hash 函数,算出第三次探查的位置,依此类推。

对于开放寻址法来说,无论使用什么优化方案,随着插入的元素越多、哈希表越满,插入和检索的性能也就下降得越厉害。在极端情况下,当哈希表被写满的时候,为了保证能插入新元素,我们只能重新生成一个更大的哈希表,将旧哈希表中的所有数据重新 Hash 一次写入新的哈希表,也就是 Re-Hash,这样会造成非常大的额外开销。因此,在数据动态变化的场景下,使用开放寻址法并不是最合适的方案。

链表法解决哈希冲突:将冲突的元素使用链表存储起来。
image.png

思考1:使用开放寻址法解决哈希冲突的哈希表能直接删除某元素吗?不能直接简单的删除,可以增加一个删除flag。哈希表在查找元素的时候,不是只看下标的,还要对比下标位置的元素值,相同才算找到。这也是为什么会有线性探查等方法。不能直接删除的问题在于,直接删除会把探查序列中断。举个例子:有三个元素a,b,c的hash值是冲突的,那么探查序列会把他们放在三个位置上,比如1,2,3(探查序列是123),如果我们把b删了,那么2这个位置就空了。这时候,要查询c,探查序列就会在2的位置中断,查不到c。

二值状态检索

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

使用普通数组的话,我们直接将用户 ID 的值作为数组下标,将该位置的值从 0 设为 1 就可以了。数量很少并且固定比较适合,当数量很大占用空间会比较大,最直观的一个想法就是,使用最少字节的类型来定义数组,比如说,使用 1 个字节的 char 类型数组,或者使用 bool 类型的数组(在许多系统中,一个 bool 类型的元素也是 1 个字节)。它们和 4 个字节的 int 32 数组相比,空间使用效率提升了 4 倍,这已经算是不错的改善了。但是让然很浪费空间,因为表示 0 或者 1,理论上只需要一个 bit。所以,如果我们能以 bit 为单位来构建这个数组,那使用空间就是 int 32 数组的 1/32,从而大幅减少了存储使用的内存空间。

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

针对此种场景,可以使用位图来减少存储空间,但许多系统中并没有以 bit 为单位的数据类型。因此,我们往往需要对其他类型的数组进行一些转换设计,使其能对相应的 bit 位的位置进行访问,从而实现位图。

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

布隆过滤器:就是对一个对象使用多个哈希函数。如果我们使用了 k 个哈希函数,就会得到 k 个哈希值,也就是 k 个下标,我们会把数组中对应下标位置的值都置为 1。布隆过滤器和位图最大的区别就在于,我们不再使用一位来表示一个对象,而是使用 k 位来表示一个对象。这样两个对象的 k 位都相同的概率就会大大降低,从而能够解决哈希冲突的问题了。

image.png
布隆过滤器的错误率:存在一定程度地误判,只能判断一个元素一定不存在,不能判断一个元素一定存在。针对场景我们希望用更小的代价快速判断 ID 是否已经被注册了比较合适。

思考1:布隆过滤器中一个元素能否直接删除?不能直接删除,因为某个位置的状态可能是多个hash函数的即多个元素的映射位置,删了可能会影响其他元素是否存在的判断。有些改进的布隆过滤器采用计数值方式替换0、1,可以解决这个问题,代价就是需要额外额bit来存储计数值。

倒排检索

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

倒排索引的核心其实并不复杂,它的具体实现其实是哈希表,只是它不是将文档 ID 或者题目作为 key,而是反过来,通过将内容或者属性作为 key 来存储对应的文档列表,使得我们能在 O(1) 的时间代价内完成查询。

创建倒排索引的步骤

  • 给文档编号,作为唯一标识,排序,遍历文档。
  • 解析出文档关键字,生成<关键字,文档ID,关键字位置>信息。
  • 关键字作为key插入哈希表中,如果已经存在就在哈希表的postinglist后面追加节点,记录上面的信息。
  • 重复2-3直至处理所有文档。

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

思考1:如果有个需求是根据文档作者查询文档,怎么设计呢?第一个方案可以对文档的作者设置一个作者标签,为作者标签这些内容创建倒排索引,不再一个内容倒排索引文档中实现,是怕文档内容包含 作者名字 会发生干扰。另一个方案是可以在posting list中加域,标明是作者还是内容,这样就使用一个倒排索引结构就可以了,posting list分域,就是一个元素里加上域标识。举个例子,一篇文章有标题,作者,内容三个域,而“李白”这两个字,可能出现在这三个位置。因此,key和posting list可以这么写: key =“李白” -> [id1,标题域:0,作者域:1,内容域:0],[id2,标题域:1,作者域:0,内容域:1]

思考2:邮件敏感词过滤检测适不适合使用倒排索引?邮件只需要检测一次,因此对邮件做倒排索引并不适用。而且倒排索引也解决不了近义词问题。
邮件敏感词检测一般是这样的思路:

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

这里的核心问题是如何提取关键词和如何在敏感词字典中查询。一种方式是用哈希表存敏感词字典,然后用分词工具从邮件中提取关键字,然后去字典中查。另一种方式是trie树来实现敏感词字典,然后逐字扫描邮件,用当前字符在trie树中查找。

不过,这两种方式都无法解决近义词,或者各种刻意替换字符的场景。要想解决这种问题,要么提供近义词字典,要么得使用大量数据进行训练和学习,用机器学习进行打分,将可疑的高分词找出来。其实这种近义词处理方案,和搜索引擎解决近义词和查询纠错的过程很像。

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

链表归并的过程总结成了 3 个步骤,就是一个双指针的概念

  • 第 1 步,使用指针 p1 和 p2 分别指向有序链表 A 和 B 的第一个元素。
  • 第 2 步,对比 p1 和 p2 指向的节点是否相同,这时会出现 3 种情况: 两者的 id 相同,说明该节点为公共元素,直接将该节点加入归并结果。然后,p1 和 p2 要同时后移,指向下一个元素; p1 元素的 id 小于 p2 元素的 id,p1 后移,指向 A 链表中下一个元素; p1 元素的 id 大于 p2 元素的 id,p2 后移,指向 B 链表中下一个元素。
  • 第 3 步,重复第 2 步,直到 p1 或 p2 移动到链表尾为止。

在倒排索引的检索过程中,两个 posting list 求交集是一个最重要、最耗时的操作,postinglist合并的时候除了使用归并排序,还有跳表、哈希表、位图等结构思想优化效率的方法。

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

假如归并法遇到下面的情况,那么B的指针需要等待A指针移动(500-2)次才找到交集500。显然数据量大的时候很耗时。
image.png因此可以使用跳表实现postinglist,只需要查找log(500-2)次,后面元素同理,假如A链表比B链表元素稀疏,那就反过来,拿着A的元素去B中二分查找,即互相二分查找。
image.png
在实际的系统中,如果 posting list 可以都存储在内存中,并且变化不太频繁的话,那我们还可以利用可变长数组来代替链表。可变长数组的数组的长度可以随着数据的增加而增加。一种简单的可变长数组实现方案就是当数组被写满时,我们直接重新申请一个 2 倍于原数组的新数组,将原数组数据直接导入新数组中。这样,我们就可以应对数据动态增长的场景。

那对于两个 posting list 求交集,我们同样可以先使用可变长数组,再利用相互二分查找进行归并。而且,由于数组的数据在内存的物理空间中是紧凑的,因此 CPU 还可以利用内存的局部性原理来提高检索效率。

哈希表法加速倒排索引取交集

哈希表加速的思路其实很简单,就是当两个集合要求交集时,如果一个集合特别大,另一个集合相对比较小,那我们就可以用哈希表来存储大集合。这样,我们就可以拿着小集合中的每一个元素去哈希表中对比:如果查找为存在,那查找的元素就是公共元素;否则,就放弃。

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

但是,使用哈希表法加速倒排索引有一个前提

  • 就是我们要在查询发生之前,就把 posting list 转为哈希表。这就需要我们提前分析好,哪些 posting list 经常会被拿来求交集,针对这一批 posting list,我们将它们提前存入哈希表。
  • 原始的postinglist也需要保留,哈希表遍历不太方便,后续可能要进行posting list合并。因此倒排字典的key需要指向posting list、哈希表两个结构。

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

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

查询过程如果需要取交集,直接两个bitmap与运算即可,由于位图的长度是固定的,因此两个位图的合并运算时间代价也是固定的。并且由于 CPU 执行位运算的效率非常快,因此,在位图总长度不是特别长的情况下,位图法的检索效率还是非常高的。

局限性

  • 仅适合存储ID的简单的postinglist,复杂对象不适合。
  • 仅适合元素稠密的场景,如果是稀疏bitmap位运算和存储的开销反而会比使用链表更大。
  • 会占用大量空间,每个bitmap必须固定长度,比如ID是int32,那一个bitmap大小就约为512M (2 ^ 16 / 8 / 1024 / 1024 ),如果我们有 1 万个 key,每个 key 都存一个这样的位图,那就需要 5120G 的空间了。

一种升级版位图Roaring Bitmap 可以解决占用空间太多问题Roaring Bimap,设计思想缩短bitmap的bit长度,在前面分层加一个prefix bit 基数数组,比如将一个32bit分为两部分,高16位可表示2^16个桶,低16位表示一个子位图。
image.png

这样的话,查询的时候进行两次查询

  • 第一步是以高 16 位在有序数组中二分查找,看对应的桶是否存在。如果存在
  • 第二步就是将桶中的位图取出,拿着低 16 位在位图中查找,判断相应位置是否为 1。

第一步查找由于是数组二分查找,因此时间代价是 O(log n);第二步是位图查找,因此时间代价是 O(1)。

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

  • 在高16位部分,使用一个数组,数组每个元素称为一个桶,桶的空间为 16bit,可以使用可变长数组更节省空间。
  • 在低 16 位部分,因为位图长度是固定的,每个都是 2^16 个 bit = 2 ^ 13 byte,那所占空间就是 8K 个字节

相比512M大大节省空间。但是仅限于这种极端情况,假如高16位都不一样,那么高16位有2^16个桶,每个桶对应2 ^ 16 个bitmap。

2 ^ 16 个桶以及对应的2 ^ 16 个低位bitmap空间:2 ^ 16 * 16 bit + 2 ^ 16 * 8 K byte = 2 ^ 19 K byte = 128 K byte + 512M byte = 512M

相比于位图法,这种设计方案就是通过,将不存在的桶的位图空间全部省去这样的方式,来节省存储空间的。而代价就是将高 16 位的查找,从位图的 O(1) 的查找转为有序数组的 log(n) 查找。

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

image.png

RoaringBitmap取交集的过程

  • 第 1 步,比较高 16 位的所有桶,也就是对这两个有序数组求交集,所有相同的桶会被留下来。
  • 第 2 步,对相同的桶里面的元素求交集。这个时候会出现 3 种情况,分别是位图和位图求交集、数组和数组求交集、位图和数组求交集。其中,位图和位图求交集,我们可以直接使用位运算;数组和数组求交集,我们可以使用相互二分查找(类似跳表法);位图和数组求交集,我们可以通过遍历数组,在位图中查找数组中的每个元素是否存在(类似哈希表法)。

思考1:在 Roaring Bitmap 的求交集过程中,有位图和位图求交集、数组和数组求交集、位图和数组求交集这 3 种场景。那它们求交集以后的结果,我们是应该用位图来存储,还是用数组来存储呢?考虑到交集元素的数量数组和数组求交集、位图和数组求交集 这两种情况可以很容易的想到是使用数组.

但是位图和位图的交集,需要根据情况而定,可以使用预判方法,假设A有a个值,B有b个值,按照平均可以算下间隔,比如位图支持总个数为216,那么A的平均值间隔为216 / a,B的平均值间隔2^16 / b,二者相乘为交集的间隔,那么交集的个数大致为 a * b / (2 ^16 ),最后在和4096比较即可。

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

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

假如在一个系统的倒排索引中,有4个不同的key对应四类标签的用户,现在需要进行组合key联合查询。
比如在“北京”或在“上海”,并且使用“安卓”的用户集合。抽象成联合查询表达式就是,(“北京”∪“上海”)∩“安卓”;

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

调整次序法
  • 连续集合(有包含关系)求交集,通过分析key对应集合的数量,先排序,按照从小到大的集合互取交集,这样时间复杂度更低。
  • 连续并集合然会与另外集合取交集,对于并集合中子集合和需要取交集的集合元素数量、值相差比较大的时候,可以根据分配率,逐个与另外集合取交集,最后在合并。

总是就是利用集合的各种公式定律如交交换率(A∩B)∩C = A∩(B∩C)、分配率A∩(B∪C)=(A∩B)∪(A∩C)等根据集合元素特性选择合适的计算顺序。

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

快速多路归并法

在对多个 posting list 求交集的过程中,我们可以利用跳表的性质,快速跳过多个元素,加快多路归并的效率。这种方法,我叫它"快速多路归并法"。

快速多路归并法的思路和实现都非常简单,就是将 n 个链表的当前元素看作一个有序循环数组list[n]。并且,对有序循环数组从小到大依次处理,当有序循环数组中的最小值等于最大值,也就是所有元素都相等时,就说明我们找到了公共元素。

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

  • 第一步,四个指针指向4个链表的第一个元素,更新最大值max
  • 第二步,各个链表当前指针值和max对比
    • 如果都像等,max为公共元素,记录此值,每个链表后移指针。
    • 如果某个链表当前值 < max,利用跳表法快速调整指针到 >= max 的位置,如果如果新位置元素的值大于 max,则更新 max 的值。继续其他链表。

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

image.png
快速多路归并法适用在要归并的key较多且posting list较长的情况下。否则频繁的排序调整也是一个额外开销。

预先组合法

就是将常出现的查询结果缓存起来,假设,key1、key2 和 key3 分别的查询结果是 A、B、C 三个集合。如果我们经常会计算 A∩B∩C,那我们就可以将 key1+key2+key3 这个查询定义为一个新的组合 key,然后对应的 posting list 就是提前计算好的结果。之后,当我们要计算 A∩B∩C 时,直接去查询这个组合 key,取出对应的 posting list 就可以了。

缓存法加速

预先组合法适合一些常出现的查询,对于某些搜索引擎以及一些具有热搜功能的平台中,经常会出现一些最新的查询组合。这些查询组合请求量也很大,但是由于之前没有出现过,因此我们无法使用预先组合的方案来优化。这个时候,我们会使用缓存技术来优化。

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

  • 双链表:一个合适的实现方案是使用双向链表:当一个元素被访问时,将它提到链表头。
  • 哈希表:优化链表元素访问速度,O(1)获取元素,将元素作为key,元素所在链表节点的地址作为value

思考1:为什么最好使用双链表而不是单链表?因为查询节点k之后,需要节点k移动到链表的头部,假如查询的时候位置在整个LRU的中间,如果链表是单链表的话,那么如何把k节点从链表中摘取出来,然后链表还不能被打断,这就成了一个问题了。因此,我们用双向链表,就可以快速地找到k节点的前序节点,这样就能完成节点k的摘取操作。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/335822.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

芝加哥大学最新研究:GPT-4与财务预测,重塑财务分析的未来

最近&#xff0c;芝加哥大学的研究团队发表了一篇突破性的研究&#xff0c;展示了大型语言模型&#xff08;LLM&#xff09;&#xff0c;特别是 OpenAI 开发的 GPT-4&#xff0c;如何在财务报表分析领域取得了与专业分析师相匹配甚至超越的表现。这项研究不仅凸显了人工智能在高…

鸿蒙开发接口图形图像:【WebGL】

WebGL WebGL提供图形绘制的能力&#xff0c;包括对当前绘制图形的位置、颜色等进行处理。 WebGL标准图形API&#xff0c;对应OpenGL ES 2.0特性集。 说明&#xff1a; 开发前请熟悉鸿蒙开发指导文档&#xff1a; gitee.com/li-shizhen-skin/harmony-os/blob/master/README.md…

dp秒杀优惠券

1、全局id生成器 当用户抢购时&#xff0c;就会生成订单并保存到tb_voucher_order这张表中&#xff0c;而订单表如果使用数据库自增ID就存在一些问题&#xff1a; id的规律性太明显受单表数据量的限制 场景分析&#xff1a;如果我们的id具有太明显的规则&#xff0c;用户或者…

如何使用 .htaccess 删除文件扩展名

本周有一个客户&#xff0c;购买Hostease的虚拟主机&#xff0c;询问我们的在线客服&#xff0c;如何使用 .htaccess 删除文件扩展名&#xff1f;我们为用户提供相关教程&#xff0c;用户很快解决了遇到的问题。在此&#xff0c;我们分享这个操作教程&#xff0c;希望可以对您有…

每日复盘-20240529

20240529 六日涨幅最大: ------1--------300956--------- 英力股份 五日涨幅最大: ------1--------301361--------- 众智科技 四日涨幅最大: ------1--------301361--------- 众智科技 三日涨幅最大: ------1--------300637--------- 扬帆新材 二日涨幅最大: ------1--------30…

HDR视频相关标准-HDR vivid(二)

上文介绍了HDRvivid的一些技术。今天从全局角度来看看HDR视频的处理流程&#xff0c;HDR视频系统&#xff0c;即建立一个比SDR视频更大的色彩/亮度坐标体系&#xff0c;并改变系统的传输函数&#xff0c;以再现更大的色域(WCG)和更高的亮度动态范围。 菁彩 HDR技术的专业术语 …

jmeter多用户并发登录教程

有时候为了模拟更真实的场景&#xff0c;在项目中需要多用户登录操作&#xff0c;大致参考如下 jmx脚本&#xff1a;百度网盘链接 提取码&#xff1a;0000 一&#xff1a; 单用户登录 先使用1个用户登录&#xff08;先把1个请求调试通过&#xff09; 发送一个登录请求&…

19 - grace数据处理 - 补充 - 地下水储量计算过程分解 - 冰后回弹(GIA)改正

19 - grace数据处理 - 补充 - 地下水储量计算过程分解 - 冰后回弹(GIA)改正 0 引言1 gia数据处理过程0 引言 由水量平衡方程可以将地下水储量的计算过程分解为3个部分,第一部分计算陆地水储量变化、第二部分计算地表水储量变化、第三部分计算冰后回弹改正、第四部分计算地下…

【busybox记录】【shell指令】rmdir

目录 内容来源&#xff1a; 【GUN】【rmdir】指令介绍 【busybox】【rmdir】指令介绍 【linux】【rmdir】指令介绍 使用示例&#xff1a; 删除空目录 - 默认 删除dirname下的所有空目录&#xff0c;包括因删除其他目录而变为空的目录 常用组合指令&#xff1a; 指令不…

【busybox记录】【shell指令】mkfifo

目录 内容来源&#xff1a; 【GUN】【mkfifo】指令介绍 【busybox】【mkfifo】指令介绍 【linux】【mkfifo】指令介绍 使用示例&#xff1a; 创建管道文件 - 创建的时候同时指定文件权限 常用组合指令&#xff1a; 指令不常用/组合用法还需继续挖掘&#xff1a; 内容来…

决策树模型-预测用户是否购买某母婴产品

1&#xff0c;场景描述 假设我们是京东的数据分析师&#xff0c;负责分析母婴产品的购买行为。我们想预测用户是否会购买一款新上线的母婴产品。为了进行预测&#xff0c;我们将利用用户的历史购买数据、浏览行为和其他特征&#xff0c;通过决策树模型进行分析&#xff0c;并提…

AVB协议分析(一) FQTSS协议介绍

FQTSS协议介绍 一、AVB整体架构二、概述三、协议作用及作用对象四、协议的实现五、参考文献&#xff1a; 一、AVB整体架构 可见FQTSS位于MAC层的上面&#xff0c;代码看不懂&#xff0c;咱们就从最底层开始&#xff0c;逐层分析协议&#xff0c;逐个击破&#xff0c;慢就是快。…

Unity学习日志

目录 获取相机可视范围的世界坐标(2D) 视口转世界坐标和屏幕转世界坐标的区别: 屏幕转世界坐标 视口转屏幕坐标 视口转屏幕结合3D数学实现可视范围的怪物生成 transform.up游戏对象的方向问题 其实还有一种不用Translate的写法: 修改 transform.up 的行为和影响 C#抽象…

如何评价GPT-4o?

GPT-4o&#xff1a;开启全新理解与生成语言的篇章 在近年来的AI发展中&#xff0c;GPT模型赫然矗立&#xff0c;在自然语言处理任务中刷新了人们的认知&#xff0c;一路从GPT-1演进到如今的GPT-4o。 从GPT-1到GPT-4&#xff0c;我们可以看到模型的层数和参数量在持续增长&…

HTTP Basic Access Authentication Schema

HTTP Basic Access Authentication Schema 背景介绍流程安全缺陷参考 背景 本文内容大多基于网上其他参考文章及资料整理后所得&#xff0c;并非原创&#xff0c;目的是为了需要时方便查看。 介绍 HTTP Basic Access Authentication Schema&#xff0c;HTTP 基本访问认证模式…

【SpringBoot】整合百度文字识别

流程图 一、前期准备 1.1 打开百度智能云官网找到管理中心创建应用 全选文字识别 1.2 保存好AppId、API Key和Secret Key 1.3 找到通用场景文字识别&#xff0c;立即使用 1.4 根据自己需要&#xff0c;选择要开通的项目 二、代码编写 以通用文字识别&#xff08;高精度版&am…

这些项目,我当初但凡参与一个,现在也不至于还是个程序员

10年前&#xff0c;我刚开始干开发不久&#xff0c;我觉得这真是一个有前景的职业&#xff0c;我觉得我的未来会无限广阔&#xff0c;我觉得再过几年&#xff0c;我一定工资不菲。于是我开始像很多大佬说的那样&#xff0c;开始制定职业规划&#xff0c;并且坚决执行。但过去这…

深入分析 Android Activity (一)

文章目录 深入分析 Android Activity (一)1. Activity 的窗口管理2. Activity 的生命周期管理onCreateonStartonResumeonPauseonStoponDestroyonRestart 3. Activity 与 Fragment 的交互添加 FragmentFragment 的生命周期 4. Activity 的任务和返回栈5. 配置变化处理 总结 深入…

断开自定义模块与自定义库的链接

断开自定义模块与自定义库的链接 1、断开模块与库的链接 1、断开模块与库的链接 如果摸个库文件添加到模型中&#xff0c;无法“Disable Link”时&#xff0c;可以使用save_system命令进行断开到模型中用户定义的库模块的链接&#xff1b; 参考链接&#xff1a; 传送门 save…

小短片创作-理论知识(三)

1、抗锯齿 1.相机移动的时候出现锯齿 2.当1个像素在三角形边缘的时候&#xff0c;可能取值为白色&#xff0c;也可能取值为黑色&#xff0c;表现出来就是闪烁&#xff0c;或锯齿 3.如果我们通过超采样将1个像素变成4个像素进行计算&#xff0c;得到的结果就会更准确&#x…