《检索技术核心 20 讲》笔记

发表于 2022-03-04 更新于 2024-01-27 分类于笔记，数据库本文字数： 8.1k 阅读时长 ≈ 7 分钟

《检索技术核心 20 讲》笔记

伸缩性架构是指不需要改变系统的软硬件设计，仅通过改变部署服务器数量就可以扩大或缩小系统的服务处理能力。

线性结构检索

检索的核心思想：合理组织数据，尽可能快速减少查询范围，可以提升检索效率。

数组和链表的比较

存储方式
- 数组用连续的内存空间来存储数据。
- 链表用 不连续 的内存空间来存储数据；并通过一个指针按顺序将这些空间串起来，形成一条链。
访问方式
- 数组支持随机访问。根据下标随机访问的时间复杂度为 O(1)
- 链表不支持随机访问，只能顺序访问。
空间大小
- 数组空间大小固定，扩容只能采用复制数组的方式。
- 链表空间大小不固定，扩容灵活。
效率比较
- 数组的查找效率高于链表。
- 链表的添加、删除效率高于数组。

非线性结构检索

对于无序数组，只能顺序查找，其时间复杂度为 O(n)。
对于有序数组，可以应用二分查找法，其时间复杂度为 O(log n)。

显然，二分查找法很高效，但是它有限制条件：数据有序。为了保证数据有序，添加、删除数组数据时，必须要进行数据调整，来保证其有序。

首先，对于数据频繁变化的应用场景，有序数组并不是最适合的解决方案。我们一般要考虑采用非连续存储的数据结构来灵活调整。同时，为了提高检索效率，我们还要采取合理的组织方式，让这些非连续存储的数据结构能够使用二分查找算法。

数据组织的方式有两种，一种是二叉检索树。一个平衡的二叉检索树使用二分查找的检索效率是 O(log n)，但如果我们不做额外的平衡控制的话，二叉检索树的检索性能最差会退化到 O(n)，也就和单链表一样了。所以，AVL 树和红黑树这样平衡性更强的二叉检索树，在实际工作中应用更多。

除了树结构以外，另一种数据组织方式是跳表。跳表也具备二分查找的能力，理想跳表的检索效率是 O(log n)。为了保证跳表的检索空间平衡，跳表为每个节点随机生成层级，这样的实现方式比 AVL 树和红黑树更简单。

无论是二叉检索树还是跳表，它们都是通过将数据进行合理组织，然后尽可能地平衡划分检索空间，使得我们能采用二分查找的思路快速地缩减查找范围，达到 O(log n) 的检索效率。

哈希检索

散列表的思路是：使用 Hash 函数将 Key 转换为数组下标。

哈希表的本质是一个数组，它通过 Hash 函数将查询的 Key 转为数组下标，利用数组的随机访问特性，使得我们能在 O(1) 的时间代价内完成检索。

尽管哈希检索没有使用二分查找，但无论是设计理想的哈希函数，还是保证哈希表有足够的空闲位置，包括解决冲突的“二次探查”和“双散列”方案，本质上都是希望数据插入哈希表的时候，分布能均衡，这样检索才能更高效。从这个角度来看，其实哈希检索提高检索效率的原理，和二叉检索树需要平衡左右子树深度的原理是一样的，也就是说，高效的检索需要均匀划分检索空间。

状态检索

在海量数据中，快速判断一个对象是否存在。相比于有序数组、二叉检索树和哈希表这三种方案，位图和布隆过滤器其实更适合解决这类状态检索的问题。这是因为，在不要求 100% 判断正确的情况下，使用位图和布隆过滤器可以达到 O(1) 时间代价的检索效率，同时空间使用率也非常高效。

为了判断一个很大的数据范围中，某数值是否存在，可以将这个范围的数据存为数组，其数组值为布尔型（true 或 false）。由于很多语言中，布尔类型需要 1 个字节，而二进制位（bit）的值 0 或 1 也可以表示 true 或 false，并且占用空间更小，所以更加合适。而这种基于位运算的哈希结构，即为位图。

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

布隆过滤器的误判有一个特点，那就是，它只会对存在的情况有误判。如果某个数字经过布隆过滤器判断不存在，那说明这个数字真的不存在，不会发生误判；如果某个数字经过布隆过滤器判断存在，这个时候才会有可能误判，有可能并不存在。不过，只要我们调整哈希函数的个数、位图大小跟要存储数字的个数之间的比例，那就可以将这种误判的概率降到非常低。

布隆过滤器过滤器适用于对误判有一定容忍度的场景。

倒排索引

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

尽管原理并不复杂，但是倒排索引是许多检索引擎的核心。比如说，数据库的全文索引功能、搜索引擎的索引、广告引擎和推荐引擎，都使用了倒排索引技术来实现检索功能。

B+ 树检索

内存是半导体元件。对于内存而言，只要给出了内存地址，我们就可以直接访问该地址取出数据。这个过程具有高效的随机访问特性，因此内存也叫随机访问存储器（Random Access Memory，即 RAM）。内存的访问速度很快，但是价格相对较昂贵，因此一般的计算机内存空间都相对较小。

而磁盘是机械器件。磁盘访问数据时，需要等磁盘盘片旋转到磁头下，才能读取相应的数据。尽管磁盘的旋转速度很快，但是和内存的随机访问相比，性能差距非常大。一般来说，如果是随机读写，会有 10 万到 100 万倍左右的差距。但如果是顺序访问大批量数据的话，磁盘的性能和内存就是一个数量级的。

磁盘的最小读写单位是扇区，较早期的磁盘一个扇区是 512 字节。随着磁盘技术的发展，目前常见的磁盘扇区是 4K 个字节。操作系统一次会读写多个扇区，所以操作系统的最小读写单位是块（Block），也叫作簇（Cluster）。当我们要从磁盘中读取一个数据时，操作系统会一次性将整个块都读出来。因此，对于大批量的顺序读写来说，磁盘的效率会比随机读写高许多。

假设有一个有序数组存储在硬盘中，如果它足够大，那么它会存储在多个块中。当我们要对这个数组使用二分查找时，需要先找到中间元素所在的块，将这个块从磁盘中读到内存里，然后在内存中进行二分查找。如果下一步要读的元素在其他块中，则需要再将相应块从磁盘中读入内存。直到查询结束，这个过程可能会多次访问磁盘。我们可以看到，这样的检索性能非常低。

由于磁盘相对于内存而言访问速度实在太慢，因此，对于磁盘上数据的高效检索，我们有一个极其重要的原则：对磁盘的访问次数要尽可能的少！

将索引和数据分离就是一种常见的设计思路。在数据频繁变化的场景中，有序数组并不是一个最好的选择，二叉检索树或者哈希表往往更有普适性。但是，哈希表由于缺乏范围检索的能力，在一些场合也不适用。因此，二叉检索树这种树形结构是许多常见检索系统的实施方案。

随着索引数据越来越大，直到无法完全加载到内存中，这是需要将索引数据也存入磁盘中。B+ 树给出了将树形索引的所有节点都存在磁盘上的高效检索方案。操作系统对磁盘数据的访问是以块为单位的。因此，如果我们想将树型索引的一个节点从磁盘中读出，即使该节点的数据量很小（比如说只有几个字节），但磁盘依然会将整个块的数据全部读出来，而不是只读这一小部分数据，这会让有效读取效率很低。B+ 树的一个关键设计，就是让一个节点的大小等于一个块的大小。节点内存储的数据，不是一个元素，而是一个可以装 m 个元素的有序数组。这样一来，我们就可以将磁盘一次读取的数据全部利用起来，使得读取效率最大化。

B+ 树还有另一个设计，就是将所有的节点分为内部节点和叶子节点。内部节点仅存储 key 和维持树形结构的指针，并不存储 key 对应的数据（无论是具体数据还是文件位置信息）。这样内部节点就能存储更多的索引数据，我们也就可以使用最少的内部节点，将所有数据组织起来了。而叶子节点仅存储 key 和对应数据，不存储维持树形结构的指针。通过这样的设计，B+ 树就能做到节点的空间利用率最大化。此外，B+ 树还将同一层的所有节点串成了有序的双向链表，这样一来，B+ 树就同时具备了良好的范围查询能力和灵活调整的能力了。

因此，B+ 树是一棵完全平衡的 m 阶多叉树。所谓的 m 阶，指的是每个节点最多有 m 个子节点，并且每个节点里都存了一个紧凑的可包含 m 个元素的数组。

即使是复杂的 B+ 树，我们将它拆解开来，其实也是由简单的数组、链表和树组成的，而且 B+ 树的检索过程其实也是二分查找。因此，如果 B+ 树完全加载在内存中的话，它的检索效率其实并不会比有序数组或者二叉检索树更
高，也还是二分查找的 log(n) 的效率。并且，它还比数组和二叉检索树更加复杂，还会带来额外的开销。

另外，这一节还有一个很重要的设计思想需要你掌握，那就是将索引和数据分离。通过这样的方式，我们能将索引的数组大小保持在一个较小的范围内，让它能加载在内存中。在许多大规模系统中，都是使用这个设计思想来精简索引的。而且，B+ 树的内部节点和叶子节点的区分，其实也是索引和数据分离的一次实践。

MySQL 中的 B+ 树实现其实有两种，一种是 MyISAM 引擎，另一种是 InnoDB 引擎。它们的核心区别就在于，数据和索引是否是分离的。

在 MyISAM 引擎中，B+ 树的叶子节点仅存储了数据的位置指针，这是一种索引和数据分离的设计方案，叫作非聚集索引。如果要保证 MyISAM 的数据一致性，那我们需要在表级别上进行加锁处理。

在 InnoDB 中，B+ 树的叶子节点直接存储了具体数据，这是一种索引和数据一体的方案。叫作聚集索引。由于数据直接就存在索引的叶子节点中，因此 InnoDB 不需要给全表加锁来保证一致性，它只需要支持行级的锁就可以了。

LSM 树检索

B+ 树的数据都存储在叶子节点中，而叶子节点一般都存储在磁盘中。因此，每次插入的新数据都需要随机写入磁盘，而随机写入的性能非常慢。如果是一个日志系统，每秒钟要写入上千条甚至上万条数据，这样的磁盘操作代价会使得系统性能急剧下降，甚至无法使用。

操作系统对磁盘的读写是以块为单位的，我们能否以块为单位写入，而不是每次插入一个数据都要随机写入磁盘呢？这样是不是就可以大幅度减少写入操作了呢？解决方案就是：LSM 树（Log Structured Merge Trees）。

LSM 树就是根据这个思路设计了这样一个机制：当数据写入时，延迟写磁盘，将数据先存放在内存中的树里，进行常规的存储和查询。当内存中的树持续变大达到阈值时，再批量地以块为单位写入磁盘的树中。因此，LSM 树至少需要由两棵树组成，一棵是存储在内存中较小的 C0 树，另一棵是存储在磁盘中较大的 C1 树。

LSM 树具有以下 3 个特点：

将索引分为内存和磁盘两部分，并在内存达到阈值时启动树合并（Merge Trees）；
用批量写入代替随机写入，并且用预写日志 WAL 技术（Write AheadLog，预写日志技术）保证内存数据，在系统崩溃后可以被恢复；
数据采取类似日志追加写的方式写入（Log Structured）磁盘，以顺序写的方式提高写
入效率。

LSM 树的这些特点，使得它相对于 B+ 树，在写入性能上有大幅提升。所以，许多 NoSQL 系统都使用 LSM 树作为检索引擎，而且还对 LSM 树进行了优化以提升检索性能。

索引构建

数据压缩：一个是尽可能地将数据加载到内存中，因为内存的检索效率大大高于磁盘。那为了将数据更多地加载到内存中，索引压缩是一个重要的研究方向。
分支处理：另一个是将大数据集合拆成多个小数据集合来处理。这其实就是分布式系统的核心思想。

索引更新

Double Buffer（双缓冲）机制

就是在内存中同时保存两份一样的索引，一个是索引 A，一个是索引 B。两个索引保持一个读、一个写，并且来回切换，最终完成高性能的索引更新。

优点：简单高效

缺点：达到一定数据量级后，会带来翻倍的内存开销，甚至有些索引存储在磁盘上的情况下，更是无法使用此机制。

全量索引和增量索引

将新接收到的数据单独建立一个可以存在内存中的倒排索引，也就是增量索引。当查询发生的时候，我们会同时查询全量索引和增量索引，将合并的结果作为总的结果输出。

因为增量索引相对全量索引而言会小很多，内存资源消耗在可承受范围，所以我们可以使用 Double Buffer 机制
对增量索引进行索引更新。这样一来，增量索引就可以做到无锁访问。而全量索引本身就是只读的，也不需要加锁。因此，整个检索过程都可以做到无锁访问，也就提高了系统的检索效率。

如何处理增量索引空间的持续增长

完全重建法

如果增量索引的增长速度不算很快，或者全量索引重建的代价不大，那么我们完全可以在增量索引写满内存空间之前，完全重建一次全量索引，然后将系统查询切换到新的全量索引上。

再合并法

直接归并全量索引和增量索引，生成一个新的全量索引，这也就避免了从头处理所有文档的重复开销。

滚动合并法

先生成多个不同层级的索引，然后逐层合并。

比如说，一个检索系统在磁盘中保存了全量索引、周级索引和天级索引。所谓周级索引，就
是根据本周的新数据生成的一份索引，那天级索引就是根据每天的新数据生成的一份索引。
在滚动合并法中，当内存中的增量索引增长到一定体量时，我们会用再合并法将它合并到磁
盘上当天的天级索引文件中。

索引拆分

水平拆分和垂直拆分

TOP K 检索

TF-IDF 算法

TF-IDF 算法的公式是：相关性 = TF*IDF。其中，TF 是词频（Term Frequency），IDF 是逆文档频率（Inverse Document Frequency）。

词频定义的就是一个词项在文档中出现的次数。换一句话说就是，如果一个词项出现了越多次，那这个词在文档中就越重要。
文档频率（Document Frequency），指的是这个词项出现在了多少个文档中。你也可以理解为，如果一个词出现在越多的文档中，那这个词就越普遍，越没有区分度。一个极端的例子，比如“的”字，它基本上在每个文档中都会出现，所以它的区分度就非常低。
逆文档频率是对文档频率取倒数，它的值越大，这个词的的区分度就越大。

BM25 算法

BM25 算法的一个重要的设计思想是，它认为词频和相关性的关系并不是线性的。也就是说，随着词频的增加，相关性的增加会越来越不明显，并且还会有一个阈值上限。当词频达到阈值以后，那相关性就不会再增长了。

总结来说，BM25 算法就是一个对查询词和文档的相关性进行打分的概率模型算法。BM25 算法考虑了四个因子，分别为 IDF、文档长度、文档中的词频以及查询词中的词频。并且，公式中还加入了 3 个可以人工调整大小的参数，分别是：k1、k2 和 b。

机器学习打分

机器学习可以更大规模地引入更多的打分因子，并且可以自动学习出各个打分因子的权重。所以，利用机器学习进行相关性打分，已经成了目前大规模检索引擎的标配。

根据打分结果快速 TOP K 检索

完成打分阶段之后，排序阶段我们要重视排序的效率。对于精准 Top K 检索，我们可以使用堆排序来代替全排序，只返回我们认为最重要的 k 个结果。这样，时间代价就是 O(n) + O(k log n) ，在数据量级非常大的情况下，它比 O(n log n) 的检索性能会高得多。

非精准 TOP K 检索

高质量的检索结果并不一定要非常精准，我们只需要保证质量足够高的结果，被包含在最终的 Top K 个结果中就够了。这就是非精准 Top K 检索的思路。

空间检索

通过将二维空间在水平和垂直方向上不停二分，可以生成一维的区域编码，然后我们可以使用一维空间的检索技术对区域编码做好索引。

在需要动态调整查询范围的场景下，对于二进制编码的二维空间的最近邻检索问题，我们可以通过四叉树来完成。四叉树可以很好地快速划分查询空间，并通过递归的方式高效地扩大查询范围。但是满四叉树经常会造成无谓的空间浪费，为了避免这个问题，在实际应用的时候，我们会选择使用非满四叉树来存储和索引编码。对于 GeoHash 编码的二维空间最近邻检索问题，我们也能通过类似的前缀树来提高检索效率。

存储系统

LevelDB 是由 Google 开源的存储系统。

LevelDB 是基于 LSM 树优化而来的存储系统。LSM 树会将索引分为内存和磁盘两部分，并在内存达到阈值时启动树合并。但是，这里面存在着大量的细节问题。

数据在内存中如何高效检索？

首先，对内存中索引的高效检索，我们可以用很多检索技术，如红黑树、跳表等，这些数据结构会比 B+ 树更高效。LevelDB 对于 LSM 树的第一个改进，就是使用跳表代替 B+ 树来实现内存中的 C0 树。

数据是如何高效地从内存转移到磁盘的？

LevelDB 做了读写分离的设计。它将内存中的数据分为两块，一块叫作 MemTable，它是可读可写的。另一块叫作 Immutable MemTable，它是只读的。这两块数据的数据结构完全一样，都是跳表。

当 MemTable 的存储数据达到上限时，我们直接将它切换为只读的 Immutable MemTable，然后重新生成一个新的 MemTable，来支持新数据的写入和查询。这时，将内存索引存储到磁盘的问题，就变成了将 Immutable MemTable 写入磁盘的问题。而且，由于 Immutable MemTable 是只读的，因此，它不需要加锁就可以高效
地写入磁盘中。

数据如何合并

在原始 LSM 树的设计中，内存索引写入磁盘时是直接和磁盘中的 C1 树进行归并的。但如果工程中也这么
实现的话，会有两个很严重的问题：

合并代价很高，因为 C1 树很大，而 C0 树很小，这会导致它们在合并时产生大量的磁盘 IO；
合并频率会很频繁，由于 C0 树很小，很容易被写满，因此系统会频繁进行 C0 树和 C1 树的合并，这样频繁合并会带来的大量磁盘 IO，这更是系统无法承受的。

LevelDB 采用了延迟合并的设计来优化。具体来说就是，先将 Immutable MemTable 顺序快速写入磁盘，直接变成一个个 SSTable（Sorted String Table）文件，之后再对这些 SSTable 文件进行合并。这样就避免了 C0 树和 C1 树昂贵的合并代价。

而在管理多个 SSTable 文件的环节，LevelDB 使用分层和滚动合并的设计来组织多个 SSTable 文件，避免了 C0 树和 C1 树的合并带来的大量数据被复制的问题。

数据如何检索

先在 MemTable 中查找，如果查找不到再去 Immutable MemTable 中查找。如果 Immutable MemTable 也查询不到，才会到磁盘中去查找。

在磁盘中检索数据的环节，因为 SSTable 文件是有序的，所以我们通过多层二分查找的方式，就能快速定位到需要查询的 SSTable 文件。接着，在 SSTable 文件内查找元素时，LevelDB 先是使用索引与数据分离的设计，减少磁盘 IO，又使用 BloomFilter 和二分查找来完成检索加速。加速检索的过程中，LevelDB 又使用缓存技术，将会被反复读取的数据缓存在内存中，从而避免了磁盘开销。

搜索系统

搜索流程：

先对查询内容分词，搜索引擎还会纠错和相似推荐，得到检索词
根据检索词在倒排索引中进行短语检索。然后，根据相关性打分，将得分高的结果保留。

广告系统

广告引擎处理一个广告请求的过程，本质上就是根据用户的广告请求信息，找出标签匹配的广告设置，并将广告进行排序返回的过程。

在标签检索引擎中，我们通过合理地将标签使用在树形检索 + 倒排索引 + 结果过滤这三个环节，来提高检索效率。
在向量检索引擎中，我们可以使用聚类 + 倒排索引 + 乘积量化的技术来加速检索。
在打分排序环节，增加一个非精准打分环节，这样我们就可以大幅降低使用深度学习模型带来的开销。
在索引构建环节，我们还可以将一些过滤条件前置，仅将当前有效的广告设置加入索引，然后通过全量索引 + 增量索引的更新方式，来保证过滤逻辑的有效。

参考资料

检索技术核心 20 讲