检索技术核心20讲总结-part1
本文为极客时间《检索技术核心20讲》课程第二章的总结笔记, 第二章围绕检索技术展开，深入剖析了多种数据结构和算法在检索场景中的应用、性能特点以及优化策略。
一、线性结构检索
（一）数组和链表的存储特点
- 数组：使用一块连续的内存空间存储数据，这种存储方式使得数组具有可随机访问的特性，即可以在O(1)的时间复杂度内直接访问数组中的任意元素。例如，对于数组
a[n]，可以直接通过索引i访问元素a[i]。 - 链表：链表能够申请不连续的内存空间，通过指针将这些空间按顺序串起来形成一条链，通常所说的链表指单链表。链表的每个节点包含数据和指向下一个节点的指针。与数组相比，链表的优点是插入和删除操作不需要移动大量元素，时间复杂度为O(1)；缺点是无法随机访问，访问链表中间的元素时，需要从链表头开始，沿着指针一步一步遍历，时间复杂度为O(n)。
（二）数组检索效率的提升
- 无序数组的检索：当数据无序存储时，无论是数组还是链表，要查找一个指定元素是否存在，在缺乏数据分布信息的情况下，都只能从头到尾遍历一遍，检索效率为O(n)。如果数据集规模较小，直接遍历的方式尚可接受；但对于大规模数据集，这种方式效率较低。
- 有序数组与二分查找：对于规模较大的数据集，通常先将其通过排序算法转为有序数据集，然后使用二分查找算法来提高检索效率。二分查找也叫折半查找，其思路是将有序数组二分为左右两个部分，通过与中间元素比较，只在半边进行查找。具体实现步骤如下：
- 首先从中间元素查起，若中间元素的值等于要查询的值，则直接返回。
- 若中间元素的值小于要查询的值，由于数组有序，所以要查询的值只可能存在于右半边数组中，继续对右半边数组使用二分查找。
- 若中间元素的值大于要查询的值，则只在左边数组元素中查找。
- 不断重复上述过程，每次检索空间都能减少一半，整体平均查询效率为O(log n)，远低于遍历整个数组的O(n)代价 。
（三）链表在检索和动态调整上的特点
- 检索效率分析：链表在数据无序存储时检索效率很低。即使数据有序，由于其不具备“随机访问”的特点，访问中间元素仍需从链表头开始遍历，时间代价为O(n/2)，检索能力较弱。
- 动态调整优势：链表在动态调整方面具有优势，能够以O(1)的时间代价完成节点的插入和删除操作。例如，在有序数组中插入一个元素，为保证数组有序，需要将插入位置之后的元素全部顺序后移一位，时间代价为O(n)；而链表只需调整前后节点的链接即可。
- 链表的改造与优化：为提升链表的检索效率，可以对链表进行改造。比如让链表每个节点不再只是存储一个元素，而是存储一个小的数组，这样能大幅减少节点数量，减少依次遍历节点带来的“低寻址效率”。在检索时，可以用二分查找的思想，先查询第一个节点存储的小数组的末尾元素，再决定在哪个小数组中继续二分查找，时间代价可达到O(log n)。
二、非线性结构检索
（一）树结构的二分查找
- 链表与二分查找的矛盾：上一讲提到，链表不具备“随机访问”特点，导致二分查找无法生效。当链表想要访问中间元素时，需要遍历一半的节点，时间代价是O(n/2)；而有序数组可“随机访问”，访问中间节点时间代价为O(1)。
- 二叉检索树的构建：为使链表能使用二分查找，可对其进行改造。将链表的中间节点单独记录，若要查找的元素与中间节点相等，则返回结果；若大于或小于中间节点，则分别到右边或左边部分继续查找。对于左右子链表，同样记录中间节点，并将中间节点改造为带有两个指针，分别指向左右子链表的中间节点，这样就形成了二叉检索树。
- 二叉检索树的特性与检索效率：二叉检索树是有序的，其左子树的所有节点的值都小于根节点，右子树所有节点的值都大于等于根节点。这种有序结构使得它能使用二分查找算法，快速过滤掉一半的数据，检索时间代价理论上能达到O(log n)。但如果二叉检索树结构不平衡，可能退化成单链表，检索效率会退化到O(n)。为解决这个问题，出现了AVL树（平衡二叉树）和红黑树等，它们通过特殊处理保证左右子树差距不大，确保检索效率，在实际工作中应用广泛，如C++中的Set和Map等数据结构，底层就是用红黑树实现的。
（二）跳表的二分查找
- 跳表的设计思路：链表访问中间节点效率低是因为每个节点只存储下一个节点的指针。跳表的设计思路是在节点上增加指针，指向更远的节点，提供不同步长的遍历能力。例如，让节点的指针一次跳过2个、4个甚至一半的节点，这样就能更快速地访问到中间节点。
- 跳表的结构与检索过程：一个理想的跳表，从链表头开始，用多个不同的步长，每隔2^n个节点做一次直接链接（n取值为0,1,2……） 。跳表中的每个节点都拥有多个不同步长的指针，通过这些指针可以在O(log n)的时间复杂度内完成检索。例如，检索元素k时，从第一个节点开始，用最大步长的指针遍历，若下一个节点大于k，则在当前节点和下一个节点之间，用小一个级别步长继续查询，以此类推，直到找到目标元素。
- 跳表的实际实现与平衡方案：在实际情况下，为保证检索性能和修改指针代价之间的平衡，当新节点插入时，通过随机函数来生成层数，以(1/2)^n的概率决定是否生成第n层 。这样可以保证指针分布在大概率上是平衡的。相比于复杂的平衡二叉检索树，跳表用更简单的方式实现了检索空间的平衡，并且保持了链表顺序遍历的能力，在需要遍历功能的场景中使用更方便，因此在Redis这样的系统中经常被用来代替红黑树作为底层的数据结构。
三、哈希检索
（一）Hash函数与哈希表的基本原理
- 利用数组随机访问特性的设想：在实际应用中，常需要根据键（Key）查询数据。数组具有随机访问特性，若能将查询的Key转换为数组下标，就能利用数组的这一特性实现高效检索。例如，当用户ID是从1开始的整数且范围有限（不大于10万）时，可以申请一个长度为10万的数组，将用户ID作为数组下标，实现O(1)级别的查询能力。
- Hash函数的作用：当用户ID数字范围很大或为字符串时，无法直接作为数组下标。此时可以使用Hash函数，将对象（如字符串ID）转为有限范围的正整数，这个正整数作为数组下标，将对应元素存放在数组中，该数组即为哈希表。例如，对于字符串ID“tom”，可以通过特定算法（如将字母在字母表中的位置顺序作为数值，将字符串看作26进制数字进行计算）将其转换为一个数值，再通过取余等操作得到数组下标。
- 哈希冲突及解决方案：任何Hash函数都可能造成对象不同但Hash值相同的冲突。对于哈希冲突，有两类解决方案：
- 构造理想的Hash函数：使得Hash以后得到的数值尽可能平均分布，减少冲突发生的概率。
- 提供冲突解决方案：常用的冲突解决方案是“开放寻址法”和“链表法”。
（二）开放寻址法解决Hash冲突
- 线性探查：开放寻址法是在冲突发生后，新元素寻找新空闲的数组位置完成插入。线性探查是其中一种简单的方案，其插入逻辑是在当前位置发现冲突后，顺序查看数组的下一个位置是否空闲，若空闲则插入，否则继续往后查找，直到找到空闲位置插入为止。查询逻辑与插入逻辑相似，先根据Hash值查找相应数组下标的元素，若该位置不为空但存储元素的Key和查询的Key不一致，则顺序到数组下一个位置检索，直到找到匹配的Key或遍历到空闲处。
- 优化方案：线性探查可能导致元素聚集，影响哈希表的整体性能。为解决这个问题，可以使用“二次探查”和“双散列”进行优化。二次探查将线性探查的步长从i改为i^2；双散列则使用多个Hash函数来求下标位置，当第一个Hash函数求出来的位置冲突时，启用第二个Hash函数，依此类推。这些方法的核心思路都是在发生冲突时，将下个位置尽可能岔开，让数据随机分散存储，降低对不相干Key的干扰，提高整体检索效率。
- 开放寻址法的局限性：对于开放寻址法，随着插入元素增多、哈希表变满，插入和检索的性能会下降。在极端情况下，当哈希表被写满时，为插入新元素，只能重新生成一个更大的哈希表，将旧哈希表中的所有数据重新Hash一次写入新表，即Re - Hash，这会造成很大的额外开销。因此，在数据动态变化的场景下，开放寻址法不是最合适的方案。
（三）链表法解决Hash冲突
- 链表法的原理：链表法是在数组中不存储具体元素，而是存储一个链表头。当一个Key经过Hash函数计算得到对应的数组下标后，将其加入该位置所存链表的尾部。这种方法既利用了数组的随机访问特性，又利用了链表的动态修改特性，提供了快速查询和动态修改的能力。
- 链表法的优化：在链表法中，如果链表很长，遍历代价会很高。为提高检索效率，在JDK1.8之后，Java中HashMap的实现是当链表达到一定长度时，将其转为红黑树；当红黑树中的节点低于一定阈值时，再将其退化为链表。这样在冲突元素不多时，能有效提高检索效率。
- 哈希表的缺点：哈希表虽然具有接近O(1)的检索效率，能支持动态数据场景，但也存在缺点：
- 空间需求大：为保证检索效率，需要预估数据量，提前生成足够大的哈希表，通常要预留一半以上的空闲位置，这使得哈希表比有序数组、二叉检索树需要更多的存储空间。
- 不支持有序遍历和范围查询：哈希表使用Hash值直接进行下标访问，失去了“有序存储”的特点。在需要遍历数据或进行范围查询的场景中，哈希表本身没有加速办法，性能不佳。
四、状态检索
（一）利用数组随机访问特性提高查询效率
- 使用数组判断对象是否存在：在判断一个对象是否存在的场景（如注册新用户时判断用户ID是否被注册）中，使用有序数组、二叉检索树或哈希表都可实现。其中，哈希表平均检索时间代价为O(1) ，是相对合适的选择。若查询对象ID为正整数且范围有上限，可申请一个足够大的数组，以ID为数组下标，将存在的对象对应位置的值设为1，查询时直接访问数组下标，若值为1则表示对象存在，这种方式利用数组随机访问特性，查询效率最高。
- 数组方案的问题与优化方向：直接使用ID作为数组下标存在两个问题：一是ID范围广时，数组长度需很大，占用空间大；二是若使用int 32类型数组存储0和1，会造成空间浪费。为优化空间，可以考虑使用占用字节更少的数组类型，如char类型或bool类型数组，进一步还可以使用位图（Bitmap）。
（二）位图与布隆过滤器减少存储空间
- 位图的原理与实现：位图以bit为单位构建数组，理论上表示0或1只需要一个bit，相比int 32数组，使用空间可缩小至1/32 。在许多系统中没有以bit为单位的数据类型，常需要对其他类型数组进行转换设计来实现位图。例如，以char类型数组为例，通过计算bit位在数组中的位置，再利用位运算来访问和判断指定bit位的值，可在O(1)时间内完成判断，大幅减少存储使用的内存空间。
- 布隆过滤器的设计思想：为进一步优化存储空间，可限制数组长度并使用哈希函数将大于数组长度的ID转换为小于数组长度的数值作为下标。但数组压缩会增加哈希冲突的可能性，布隆过滤器借鉴“双散列”思想，对一个对象使用多个哈希函数，得到k个哈希值，将数组中对应下标位置的值都置为1 。与位图不同，布隆过滤器用k位来表示一个对象，降低了两个对象哈希值冲突的概率。
- 布隆过滤器的查询特点与错误率：布隆过滤器的查询结果可能出现错误，即即使查询对象的k个位置的值都是1，查询结果为存在，该结果也可能是错误的，这被称为布隆过滤器的错误率。例如，当布隆过滤器中存储了x和y两个对象，它们对应的bit位被置为1，若一个不存在的对象z的k个哈希值对应位置的值正好都是1，z就会被错误地认定为存在。在系统不要求结果100%准确的情况下（如判断用户ID是否注册），可以直接当作对象存在，从而使用布隆过滤器快速完成“是否存在”的检索。同时，需要控制布隆过滤器中哈希函数的个数，可通过公式计算最优个数，以平衡错误率和查询性能。
五、倒排索引
（一）倒排索引的概念
- 正排索引与倒排索引的对比：正排索引是以对象的唯一ID为key，把相关内容作为值存储的哈希索引结构，如给出诗的题目查询内容，可通过正排索引在O(1)时间内完成检索。而倒排索引则是根据具体内容或属性反过来索引文档标题的结构，将每个关键字当作key，把包含该关键字的诗的列表当作存储内容。例如，要查询包含特定字的诗，正排索引需要遍历所有诗，时间代价高；倒排索引则可在O(1)时间内得到包含该关键字的文档列表。
- 倒排索引的构成：在倒排索引中，key的集合叫作字典（Dictionary），一个key后面对应的记录集合叫作记录列表（Posting List） 。这种结构能高效地实现根据关键字查找文档的功能，是许多检索引擎的核心技术。
（二）倒排索引的创建
- 创建步骤：创建倒排索引的过程如下：
- 给每个文档编号，作为其唯一标识并排序，然后遍历文档。
- 解析当前文档中的每个关键字，生成<关键字，文档ID，关键字位置>这样的数据。记录关键字位置信息，是因为在许多检索场景中，需要显示关键字前后内容或判断多个关键字之间的距离。
- 将关键字作为key插入哈希表。若哈希表中已有该key，则在对应的posting list后面追加节点，记录该文档ID和关键字位置；若哈希表中没有该key，则直接插入该key，并创建posting list和对应节点。
- 重复上述步骤，处理完所有文档，完成倒排索引的创建。
（三）倒排索引的查询
- 单个关键字查询：查询包含单个关键字的文档时，直接以查询的关键字作为key去倒排索引表中检索，得到的posting list就是结果。
- 多个关键字联合查询：查询同时包含多个关键字（如“极”和“客”）的文档时，先分别用这些关键字去倒排索引中检索，得到多个posting list。若要查找这些posting list的公共元素，当posting list为无序链表时，需将每个元素分别比对，时间代价为O(m * n)；当posting list为有序链表时，可使用归并排序的方法遍历，时间代价降为O(m + n) ，其中m和n分别为两个链表的长度。联合查询还包括查询包含“极”或“客”字（对应集合的并集）、包含“极”且不包含“客”（对应集合的差集）等场景，实现方法与交集查询类似，都是通过遍历链表对比完成。对于多个关键字（如“极”“客”“时”“间”）的联合查询，可利用多路归并的方法，同时遍历这些关键词对应的posting list。