检索技术核心20讲总结-part2
本文为极客时间《检索技术核心20讲》课程第三章的总结笔记，第三章围绕检索技术在多场景下的应用展开，详细介绍多种检索数据结构、算法及优化方案等
数据库检索：B+树索引
- 磁盘与内存读写特性差异：内存由半导体元件构成，具有随机访问特性，只要给出内存地址就能快速访问数据，访问速度快，但其价格昂贵，导致计算机内存空间相对较小。磁盘属于机械器件，访问数据时需等待盘片旋转到磁头下方，随机读写性能比内存慢10万到100万倍。不过，磁盘的顺序读写性能与内存处于同一数量级。磁盘的最小读写单位是扇区，早期扇区大小为512字节，现在常见的是4K字节。操作系统以块（簇）为最小读写单位，当从磁盘读取数据时，会一次性读取整个块，这使得大批量顺序读写时磁盘效率较高。
- B+树数据结构剖析：B+树是一种m阶多叉树，其设计与磁盘特性紧密结合。B+树的节点大小被设计为与磁盘块大小一致，这样可以充分利用磁盘一次读取的数据，提高读取效率。内部节点仅存储key和用于维持树形结构的指针，不存储key对应的数据，这种设计使得内部节点能够存储更多的索引数据，进而使用最少的内部节点将所有数据组织起来。叶子节点则存储key和对应数据，且同一层的所有叶子节点通过双向链表串连起来，这一结构赋予了B+树良好的范围查询能力和灵活调整能力。
- B+树检索流程详解：B+树的检索从根节点开始。在检索时，通过一次磁盘访问将根节点数据块读出，然后在根节点的有序数组中执行二分查找。具体查找过程为，确认要寻找的查询值位于数组中哪两个相邻元素中间，接着读出第一个元素对应的指针，从而获得下一个block的位置。之后，读出下一个block的节点数据并重复上述操作，B+树会逐层访问内部节点，直至读出叶子节点。在叶子节点的数组中，再次使用二分查找算法判断查找的元素是否存在。若存在，就能获取该查询值对应的存储数据。若数据是详细信息的位置指针，则还需再访问磁盘一次，以读出详细信息。由于B+树是完全平衡的，一个只有2 - 4层的B+树就能索引数量级非常大的数据，并且可以通过将上面几层的内部节点全部读入内存的方式，进一步降低磁盘读取次数。
- B+树动态调整机制：在插入数据时，由于具体数据存储在叶子节点，所以插入操作从叶子节点开始。以一个节点能存储3个元素的B+树为例，若插入的节点ID对应的元素所在叶子节点未满，直接将该元素插入数组即可；若叶子节点已满，则需要将该叶子节点分裂，生成一个新节点并将数据在两个节点中平分，同时，上一层的内部节点也需要相应修改。若父节点也满了，同样需要分裂，最后可能还需要调整根节点。在删除数据时，如果节点数组较满，直接删除；若删除后数组有一半以上的空间为空，为提高节点空间利用率，该节点会尝试将左右两边兄弟节点的元素转移过来，但转移的条件是元素转移后该节点及其兄弟节点的空间都能维持在半满以上。若无法满足这个条件，说明兄弟节点也足够空闲，此时直接将该节点的元素并入兄弟节点，然后删除该节点。
NoSQL检索：LSM树
- LSM树设计思路与优势：在日志系统、监控系统等写操作频繁的应用场景中，B+树由于每次插入新数据都需随机写入磁盘，性能会急剧下降，而LSM树则更适合这类场景。LSM树的设计思路是延迟写磁盘，数据先存放在内存中的C0树进行常规的存储和查询。当C0树达到阈值时，再批量地以块为单位写入磁盘中的C1树。这样以批量写入代替了多次随机写入，大大提升了写入性能。
- 数据恢复机制：WAL技术：为了确保内存中的数据在系统崩溃后能够恢复，工业界采用WAL技术（Write Ahead Log，预写日志技术）。具体步骤为，内存中的程序在处理数据时，先将对数据的修改作为一条记录顺序写入磁盘的log文件进行备份，由于磁盘文件的顺序追加写入效率很高，所以这种备份方式在许多应用场景中是可行的。在数据写入log文件后，备份成功，数据可以继续驻留在内存中，并且会生成对应的检查点记录在磁盘中，之后可以删除被处理完的数据，避免log文件无限增长。当系统崩溃重启时，只需要从磁盘中读取检查点，就能知道最后一次成功处理的数据在log文件中的位置，然后将该位置之后未被处理的数据重新加载到内存中。
- 内存与磁盘数据合并过程：当C0树满后，需要将其数据转换到C1树上，这涉及滚动合并（Rolling Merge）的过程。滚动合并时，系统会将C0树和C1树的所有叶子节点中存储的数据看作两个有序链表，参考两个有序链表归并排序的过程进行合并。具体步骤为，第一步，以多页块为单位，将C1树的当前叶子节点从前往后读入内存，读入内存的多页块称为清空块；第二步，将C0树的叶子节点和清空块中的数据进行归并排序，把归并的结果写入内存的一个新块中，这个新块叫作填充块；第三步，如果填充块写满了，将其作为新的叶节点集合顺序写入磁盘，若C0树的叶子节点和清空块都没有遍历完，则继续遍历归并并将数据写入新的填充块，若清空块遍历完了，就去C1树中顺序读取新的多页块加载到清空块中；第四步，重复第三步，直到遍历完C0树和C1树的所有叶子节点，并将所有的归并结果写入到磁盘，同时删除C0树和C1树中被处理过的叶子节点。在这个过程中，几乎所有的读写操作都是以多页块为单位，对多个叶子节点进行顺序读写，充分利用了磁盘顺序读写性能高的特性，使得LSM树的性能得到大幅提升。
- LSM树检索方式与细节：LSM树在检索时，会先到C0树中查询。因为C0树存储的是最新的一批数据，所以如果在C0树中查询到了所需数据，则直接返回，无需再去查询C1树。若在C0树中未查询到，则去磁盘中的C1树查询。但在C1树中查到数据后，不能直接返回，因为可能存在数据已被删除但仍在C1树中的情况。对于被删除的数据，会将其key插入到C0树中，并存入删除标志。如果C0树中已经存有这些数据，则将C0树中这些数据对应的key都加上删除标志。这样，当在C0树中查询时，若查到带删除标志的key，直接返回查询失败，无需再查询C1树。在滚动归并的时候，会查看数据在C0树中是否带有删除标志，若有，则在滚动归并时将其放弃，从而实现C1树的批量“数据删除”动作。
索引构建与更新
- 大规模倒排索引生成步骤：在搜索引擎等超大规模数据应用场景中，需要对万亿级别的网站进行索引，生成的倒排索引非常庞大，无法全部存储在内存中。对于大规模文档集合生成倒排索引，首先将其均匀划分为多个小的文档集合，然后为每个小文档集合在内存中生成倒排索引。生成内存倒排索引的步骤为，给每个文档编号并排序，顺序扫描每个文档，将文档中的所有内容生成<关键字，文档ID，关键字位置>数据对，并以关键字为key存入倒排表（位置信息可省略）。接着，将内存中的倒排索引存入磁盘，生成临时倒排文件，在存入磁盘时，先将内存中的文档列表按照关键词的字符串大小进行排序，然后将关键词以及对应的文档列表作为一条记录写入临时倒排文件。处理完所有文档集合后，会得到多个临时文件，此时使用多路归并技术，根据关键词合并这些临时文件。在合并过程中，为每个关键词赋上全局唯一的编号，最终得到完整的倒排文件。这种将大任务分解为多个小任务，根据key归并的思路，与分布式计算MapReduce的思路相似，并且该方案可迁移到MapReduce框架上，在多台机器上同时运行。
- 索引更新方法及适用场景：索引更新方法主要有完全重建法、再合并法和滚动合并法。完全重建法适用于增量索引增长速度不算很快，或者全量索引重建代价不大的情况。在增量索引写满内存空间之前，完全重建一次全量索引，然后将系统查询切换到新的全量索引上，同时释放旧的增量索引空间。再合并法适用于较大规模的检索系统，其思路是将全量索引看作已合并好的大索引，增量索引看作新增的小索引，直接归并全量索引和增量索引生成新的全量索引，避免了从头处理所有文档的重复开销。滚动合并法是通过逐层滚动合并增量索引和全量索引，每次合并时不会进行大量的无谓数据复制，从而减少开销。
分布式检索：索引拆分
- 索引拆分方式及特点：分布式技术在大规模检索系统中用于加速检索，其中索引拆分是重要手段。索引拆分方式主要有基于关键词拆分和基于文档拆分。基于关键词拆分索引时，查询词少且合理分片的情况下，能大幅降低请求复制的代价，但存在诸多问题，如查询词多且未划分到同一分片时，请求会多次复制；高频词对应的文档列表长，检索性能会急剧下降；还有新增文档的索引修改、系统热点查询负载均衡等问题。基于文档拆分索引，虽然每个索引分片的词典可能完整，但posting list不完整，不过这种方式系统的扩展性和可运维性更好。
- 分布式检索优势体现：利用分布式技术进行索引拆分有两大优势。一方面，能将更多的索引数据加载到内存中，减少磁盘访问次数，从而大幅度提升检索效率；另一方面，基于文档的拆分方式，可以将一个查询请求复制成多份，由多台索引服务器并行完成，进而缩短单次检索的时间。这种方式在搜索引擎、广告引擎、推荐引擎等大规模数据检索引擎中都有应用，只是根据处理对象不同，拆分方式的命名有所不同。
检索结果打分排序
- 打分方法原理与比较：常见的打分方法有TF - IDF、BM25算法和机器学习打分。TF - IDF中，TF代表词项在文档中的权重，IDF体现词项的区分度，它是许多更复杂打分算法的基础。BM25算法是概率模型中成功的相关性打分算法，它认为TF对相关性的影响有上限，除了考虑IDF、文档长度、文档中的词频，还考虑了查询词中的词频，并给出了3个可人工调整的参数，使得打分效果更好，应用更广泛。机器学习打分则可以大规模引入更多的打分因子，并且能够自动学习出各个打分因子的权重，因此成为目前大规模检索引擎的标配。
- Top K检索优化策略：为了提高检索效率，通常采用非精准Top K检索结合精准Top K检索的方案。非精准Top K检索实现加速的方法主要有三种：一是根据静态质量得分排序截断，在离线阶段为文档打分，在线检索时根据得分排序截断；二是使用胜者表，利用词频进行相关性判断并截断；三是使用分层索引，对一次查询请求进行两层检索，先在高质量索引中查询，若结果不足再去低质量索引中查询。这些方法的核心思路是将计算从在线环节转移到离线环节，减少在线倒排检索时的计算量，快速截断Top K个结果，提升检索引擎的检索效率。同时，还可以在倒排检索结束后、精准打分排序前插入“非精准打分”环节，进一步减少参与“精准打分”的检索结果数量，降低性能开销。在工业界，完整的Top K检索由非精准Top K检索和精准Top K检索共同完成，通过这种方式用更小的代价快速减少检索排序范围，提升整体在线检索效率。
空间检索
- “查找附近的人”功能实现方案：在实现“查找附近的人”功能时，简单计算所有人与自己的距离并排序的方案在大规模系统中不可行。非精准检索思路可用于优化该功能，即通过限定“附近”的范围来减少检索空间，例如先查询所在城市的人，再优先检索同一区的用户。为提高检索效率，将所有检索空间划分为多个区域并编号，以区域编号为key建立索引。在查询时，根据自己的坐标计算所属区域编码，查询该区域的用户并计算距离。这种非精准检索方案会带来一定误差，对于精准查询需求，可扩大候选集合，纳入邻接区域用户，或更细粒度划分区域。Geohash编码是一种常用的地理位置编码方式，它将经纬度坐标转换为字符串编码，通过对经纬度进行多次二分，交叉组合编码并转换为base32编码，方便存储和查询，并且不同长度的Geohash编码代表不同大小的覆盖区域，可根据应用需要选择合适长度。
- 动态调整查询范围检索技术：以查找最近的加油站为例，直接多次查询效率较低。利用四叉树可以快速划分查询空间，递归扩大查询范围。四叉树的每个节点有四个子节点，通过对节点编号，从根节点遍历到叶子节点得到区域编码。在检索时，以目标区域编码为Key查询，若结果不足则递归返回上一层父节点继续检索。满四叉树在数据稀疏时会造成空间浪费，因此实际应用中常使用非满四叉树，为每个叶子节点规定容纳上限，当节点数据超出上限时进行分裂。前缀树也可用于GeoHash编码的检索，其检索思路与四叉树相似，通过匹配字符串路径检索数据，并且前缀树常用于字典检索，适用于匹配字符串的场合。
相似文章检索
- 向量空间模型与相似性计算基础：在相似文章检索中，使用向量空间模型将文章表示为高维空间中的点。具体做法是提取所有文档中出现的关键词，每个关键词作为一个维度，组成n维向量空间。一篇文章根据其中关键词的权重在相应维度上取值，一般以关键词的TF - IDF值作为权重，若文章不包含某个关键词，则该维度值为0。这样，每篇文章都可以用一个n维向量表示。计算两篇文章的相似性就转化为计算两个向量的相似度，常用余弦距离来度量，距离越小，文章越相似。在搜索引擎和推荐引擎中，查询相似文章的问题就变成在n维空间中查询离一个点距离最近的k个点的问题。
- 局部敏感哈希技术应用：对于高维空间的近邻检索问题，由于使用k - d树在维度增加时检索效率急剧下降，因此采用近似最近邻检索，借助非精准检索思路，使用局部敏感哈希（LSH）。LSH通过将高维空间中的点映射成低维空间中的一维编码，使相似的数据哈希值相近。构造LSH的方法有随机超平面划分和SimHash。随机超平面划分是随机生成n个超平面，每个超平面将高维空间划分为两部分，根据点与超平面的位置关系生成n位的哈希值。SimHash则是Google提出的一种局部敏感哈希函数，它使用一个普通哈希函数代替n次随机超平面划分，作用于文档中的每个关键词，保留关键词权重，简化了函数生成过程。在检索相似文章时，以海明距离定义相似度，通过抽屉原理进行分段划分，建立倒排索引，提高检索效率。例如，Google利用SimHash函数和分段检索，能在百亿级别的网页中快速过滤相似网页。