检索技术核心-极客课程笔记-阿里云开发者社区

01 | 线性结构检索：从数组和链表的原理初窥检索本质

数组和链表分别代表了连续空间和不连续空间的最基础的存储方式，它们是线性表（Linear List）的典型代表。其他所有的数据结构，比如栈、队列、二叉树、B+ 树等，都不外乎是这两者的结合和变化。以栈为例，它本质就是一个限制了读写位置的数组，特点是只允许后进先出。

检索的核心思路，其实就是通过合理组织数据，尽可能地快速减少查询范围。

链表的检索能力偏弱，作为弥补，它在动态调整上会更容易。我们可以以 O(1) 的时间代价完成节点的插入和删除，这是“连续空间”的数组所难以做到的。毕竟如果我们要在有序的数组中插入一个元素，为了保证“数组有序”，我们就需要将数组中排在这个元素后面的元素，全部顺序后移一位，这其实是一个 O(n) 的时间代价了。

02 | 非线性结构检索：数据频繁变化的情况下，如何高效检索？

当链表想要访问中间的元素时，我们必须从链表头开始，沿着指针一步一步遍历，需要遍历一半的节点才能到达中间节点，时间代价是 O(n/2)。而有序数组由于可以“随机访问”，因此只需要 O(1) 的时间代价就可以访问到中间节点了。

尽管有序数组和二叉检索树，在数据结构形态上看起来差异很大，但是在提高检索效率上，它们的核心原理都是一致的。那么，它们是如何提高检索效率的呢？核心原理又一致在哪里呢？接下来，我们就从两个主要方面来看。将数据有序化，并且根据数据存储的特点进行不同的组织。对于连续存储空间的数组而言，由于它具有“随机访问”的特性，因此直接存储即可；对于非连续存储空间的有序链表而言，由于它不具备“随机访问”的特性，因此，需要将它改造为可以快速访问到中间节点的树状结构。在进行检索的时候，它们都是通过二分查找的思想从中间节点开始查起。如果不命中，会快速缩小一半的查询空间。这样不停迭代的查询方式，让检索的时间代价能达到 O(log n) 这个级别。

数据组织的方式有两种，一种是二叉检索树。一个平衡的二叉检索树使用二分查找的检索效率是 O(log n)，但如果我们不做额外的平衡控制的话，二叉检索树的检索性能最差会退化到 O(n)，也就和单链表一样了。所以，AVL 树和红黑树这样平衡性更强的二叉检索树，在实际工作中应用更多。除了树结构以外，另一种数据组织方式是跳表。跳表也具备二分查找的能力，理想跳表的检索效率是 O(log n)。为了保证跳表的检索空间平衡，跳表为每个节点随机生成层级，这样的实现方式比 AVL 树和红黑树更简单。无论是二叉检索树还是跳表，它们都是通过将数据进行合理组织，然后尽可能地平衡划分检索空间，使得我们能采用二分查找的思路快速地缩减查找范围，达到 O(log n) 的检索效率。

03 | 哈希检索：如何根据用户ID快速查询用户信息？

哈希表的本质是一个数组，它通过 Hash 函数将查询的 Key 转为数组下标，利用数组的随机访问特性，使得我们能在 O(1) 的时间代价内完成检索。尽管哈希检索没有使用二分查找，但无论是设计理想的哈希函数，还是保证哈希表有足够的空闲位置，包括解决冲突的“二次探查”和“双散列”方案，本质上都是希望数据插入哈希表的时候，分布能均衡，这样检索才能更高效。从这个角度来看，其实哈希检索提高检索效率的原理，和二叉检索树需要平衡左右子树深度的原理是一样的，也就是说，高效的检索需要均匀划分检索空间。

“线性探查”的插入逻辑很简单：在当前位置发现有冲突以后，就顺序去查看数组的下一个位置，看看是否空闲。如果有空闲，就插入；如果不是空闲，再顺序去看下一个位置，直到找到空闲位置插入为止。

二次探查就是将线性探查的步长从 i 改为 i^2：第一次探查，位置为 Hash(key) + 1^2；第二次探查，位置为 Hash(key) +2^2；第三次探查，位置为 Hash(key) + 3^2，依此类推。双散列就是使用多个 Hash 函数来求下标位置，当第一个 Hash 函数求出来的位置冲突时，启用第二个 Hash 函数，算出第二次探查的位置；如果还冲突，则启用第三个 Hash 函数，算出第三次探查的位置，依此类推。无论是二次探查还是双散列，核心思路其实都是在发生冲突的情况下，将下个位置尽可能地岔开，让数据尽可能地随机分散存储，来降低对不相干 Key 的干扰，从而提高整体的检索效率。

双散列就是使用多个 Hash 函数来求下标位置，当第一个 Hash 函数求出来的位置冲突时，启用第二个 Hash 函数，算出第二次探查的位置；如果还冲突，则启用第三个 Hash 函数，算出第三次探查的位置，依此类推。无论是二次探查还是双散列，核心思路其实都是在发生冲突的情况下，将下个位置尽可能地岔开，让数据尽可能地随机分散存储，来降低对不相干 Key 的干扰，从而提高整体的检索效率。

04 | 状态检索：如何快速判断一个用户是否存在？

直接使用 ID 作为数组下标会有一个问题：如果 ID 的范围比较广，比如说在 10 万之内，那我们就需要保证数组的长度大于 10 万。所以，这种方案的占用空间会很大。而且，如果这个数组是一个 int 32 类型的整型数组，那么每个元素就会占据 4 个字节，用 4 个字节来存储 0 和 1 会是一个巨大的空间浪费。

如何使用位图来减少存储空间？

如果我们能以 bit 为单位来构建这个数组，那使用空间就是 int 32 数组的 1/32，从而大幅减少了存储使用的内存空间。这种以 bit 为单位构建数组的方案，就叫作 Bitmap，翻译为位图。

数组是以 char 类型的元素为一个单位的，因此，我们的第一步，就是要找到第 11 个 bit 在数组的第几个元素里。具体的计算过程：一个元素占 8 个 bit，我们用 11 除以 8，得到的结果是 1，余数是 3。这就代表着，第 11 个 bit 存在于第 2 个元素里，并且在第 2 个元素里的位置是第 3 个。

一个数组所占的空间其实就是“数组元素个数 * 每个元素大小”我们已经将每个元素大小压缩到了最小单位 1 个 bit，如果还要进行优化，那么自然会想到优化“数组元素个数”。压缩数组长度，并使用哈希函数，就是一个更加通用的解决方案。

哈希表解决哈希冲突的两种常用方法：开放寻址法和链表法。

布隆过滤器（Bloom Filter）的设计思想：在位图的场景下使用多个哈希函数来降低冲突概率

使用 k 位来表示一个对象。这样两个对象的 k 位都相同的概率就会大大降低，从而能够解决哈希冲突的问题了。布隆过滤器的查询特点：即使任何两个元素的哈希值不冲突，而且我们查询对象的 k 个位置的值都是 1，查询结果为存在，这个结果也可能是错误的。这就叫作布隆过滤器的错误率。

Bloom filter 错误率示例

哈希函数个数 k = (m/n) * ln(2)。其中 m 为 bit 数组长度，n 为要存入的对象的个数。实际上，如果哈希函数个数为 1，且数组长度足够，布隆过滤器就可以退化成一个位图。所以，我们可以认为“位图是只有一个特殊的哈希函数，且没有被压缩长度的布隆过滤器”。

这种快速预判断的思想，也是提高应用整体检索性能的一种常见设计思路。

bitmap 是一个集合，每个元素在集合中有一个唯一不冲突的编号(用户自己保证，在数据库中这个编号可以是行号)，是双射关系。而布隆过滤器是一个不准确的集合，而且是一对多的关系，会发生冲突，也就是说布隆过滤器的为1的位可能代表多个元素，自然不能因为一个元素删除就把它干掉。

在不要求精准，但是要求快速和省空间的场景下，布隆过滤器是不错的选择。

节省哈希函数的耗时，是位图固有的优势，而是否节省空间，则只有分析过数据的实际场景，才能决策出合适的数据存储方案，使检索达到空间和时间的最佳。

在数据不是连续紧凑出现的前提下，bloomfilter和roaring bitmap才能发挥它们的优势，反之，如果是连续紧凑的元素存储，直接使用bitmap更合适

1.bitmap和bloomfilter都是为了判断状态存在的。

2.bitmap只有一个位置用来判断状态

3.bloomfilter有多个位置用来判断状态

4.针对bloomfilter来说若果不所在一定不存在，存在不一定存在(因为hash冲突，可能是另外的元素状态)

5.如何根据用户数量来确定bitmap或者bloomfilter的bit数组的大小呢？如果是原始位图，假设id是int 32，如果你不清楚数值分布范围，那么只能覆盖所有int 32的取值区间。这时候的位图大小是512m。

如果是布隆过滤器，你需要预估你的用户数量，

此外，还要设置一个你能接受的错误率p，使用这个公式:m =－n ln p / （ln 2）^2 ，可以算出来bit 位数组m的大小。

05 | 倒排索引：如何从海量数据中查询同时带有“极”和“客”的唐诗？

一个以对象的唯一 ID 为 key 的哈希索引结构，叫作正排索引（Forward Index）.

随着数据量的变化选择合适的容器来存储数据，比较节省内存，倒排索引+压缩位图是一个非常强的组合，搜索性能非常高，合适的场景下甚至可以替换ES，提升几十倍搜索性能。快手、华为千亿级用户标签检索系统中也有类似的应用

近义词处理方案,邮件敏感词检测一般是这样的思路:

1.准备一个敏感词字典。

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

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

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

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

不过，这两种方式都无法解决近义词，或者各种刻意替换字符的场景。要想解决这种问题，要么提供近义词字典，要么得使用大量数据进行训练和学习，用机器学习进行打分，将可疑的高分词找出来。

将每个关键字当作 key，将包含了这个关键字的诗的列表当作存储的内容。这样，我们就建立了一个哈希表，根据关键字来查询这个哈希表，在 O(1) 的时间内，我们就能得到包含该关键字的文档列表。这种根据具体内容或属性反过来索引文档标题的结构，我们就叫它倒排索引（Inverted Index）。在倒排索引中，key 的集合叫作字典（Dictionary），一个 key 后面对应的记录集合叫作记录列表（Posting List）。

将一个文档解析并加入倒排索引