测一测 | 高性能检索系统的实战知识，你掌握了多少？

这是一道开放的设计题，并没有标准答案，但是，我会给你一个参考的解答思路。你可以和你自己的方案进行对比，看看有哪些相同或者不同的地方，这些地方是否合理。下面是具体的解答思路。 对于第一个问题，其实是有着两个检索维度，一个维度是地理位置，另一个维度是兴趣标签。因此，我们可以将这两个维度进行解耦，分别建立两个索引。 对于基于地理位置，查询附近的人，我们可以使用区域编码，或者Geohash，将区域进行划分。由于允许检索结果为空，因此，我们可以根据应用的需求，选择合适的区域大小。然后对于所有的区域进行索引构建。我们可以使用跳表，也可以使用倒排索引。在构建好索引以后，针对要查询的区域，进行一次查询即可。如果希望更精准一些，那么可以查询周边的区域。这样，我们就可以得到“附近的人”的列表。 而对于基于兴趣标签，查找具有相同兴趣的人，我们可以通过以标签为Key，来构建倒排索引。这样，通过查询兴趣标签，我们就能找到“具有相同兴趣”的人的列表。如果一个人身上有多个兴趣标签，那么我们会查询倒排索引多次，得到每个标签对应的posting list，并将它们求并集即可。 那么，对于“附近的具有相同兴趣的人”，我们将这两个候选集求交集，就可以得到我们期望的结果。 如果不考虑该应用是否还有其他的和兴趣检索有关的需求，那么为了提高检索效率，我们其实还能将这两个维度的索引层次组合起来。我们可以根据“地理位置”将所有的人进行分片，对于同一个区域里的所有人，我们再根据兴趣标签来为每个区域的人建立倒排索引。这种组合索引结构，你会发现和层次聚类，或者倒排乘积量化的结构有点相似。它们都是通过将不同的索引进行层次组合，使得我们能快速减少减少空间。 那第二个问题，关于索引更新，在内存都可以加载的情况下，我们可以使用double buffer机制来实现。 当一个用户的位置发生变化时，如果他的位置区域没变，那么基于地理位置的索引就不用改变；而如果所属区域变化了，那么我们就将这个用户从原有区域列表中删除，然后加入到新的区域列表中。 而当一个用户的兴趣发生变化时，我们也用同样的操作，去修改兴趣标签的倒排索引。 第三个问题，要对所有符合条件的人进行打分排序，我们可以考虑一下有哪些重要的因子。在这个应用中，兴趣相似度和距离关系是最重要的因子。 关于计算两个人的兴趣相似度，其实这个和计算两个文档的相似度非常像。我们可以将每个人看作是一个文档，将每个兴趣标签看作是一个关键词。因此，我们可以使用TF-IDF的思想，或者BM25算法来进行打分。 而地理位置的距离关系，其实也是很重要的一个指标，我们可以把它当作一个独立的因子，赋予你认为合适的权重，和相关性打分进行累加即可。 当然，你也可以使用机器学习模型，将所有的因子都考虑进去，用机器学习来学习权重和进行打分。 好了，这就是全部的解题思路啦。快把你想到的答案放到留言区吧！期待与你的交流！

谈谈我的想法，采用两种数据结构保存数据： 1. 按照用户地理位置geoHash，建立倒排索引，posting list为用户ID。 [geoHash | userId] 2. 以用户标签建立倒排索引，posting list为用户ID。[tag | userId] 查找用户A 附近相同标签用户的时候，首先按照A的地理位置，在地理位置索引里找到附近的用户列表B，B = [b1, b2, b3...]. 其次，再按照用户A的标签，假设有两种标签[t1, t2, t3]，在标签索引找到相同标签的用户列表集合C，C = [c1, c2, c3...] 最后，取 B和C的交集，即是相同标签的用户。这个过程中可以采用优化算法，比如跳表，位图，加快交集的计算。 如果匹配到的用户过多的话，可以按照匹配标签的数目来对用户排序，也就是用户之前相同标签的数量。 例如，按照标签t1，匹配到用户列表C1 = [c1, c2, c3]. 按照标签t2，匹配到用户列表C2 = [c2, c3, c4]. 按照标签t3，匹配到用户列表C3 = [c3, c4, c6]. (前面提到的C是C1 C2 C3的并集) 那么对于用户出现次数排序为 CC = [c3, c2, c4...]。对于标签数量一样的用户，可以增加标签权重的因子。

“关于计算两个人的兴趣相似度，其实这个和计算两个文档的相似度非常像。我们可以将每个人看作是一个文档，将每个兴趣标签看作是一个关键词。因此，我们可以使用TF-IDF的思想，或者BM25算法来进行打分。” 陈老师，这里用相似度来打分，比如A用户的标签是“a,b”，B用户的标签是“a,b,c,d,e,f,g,h”，这样的话我理解他们俩的相似度打分应该不高。 对于有相同兴趣标签的用户，如果按照“相同兴趣标签个数越多，排序越靠前”，这样是否更好呢？标签是个大类，总量不会很大，使用位图来改造posting list，这样就判断两个用户的位图与后，bit为1的个数，越多打分越高；或者直接使用数组来查找。这个思路可行吗？

进阶实战篇到了后面，我一直有种每篇文章我知道讲什么，但没有一条主线能把它们串起来，最关键的是冥冥之中我感觉它们是有联系的┭┮﹏┭┮。花了一上午重温，得出结论： 倒排索引更泛化得讲，是一个一个的索引值key 到 完整数据集合的子集set的一个映射关系。而本专栏的8-16章就可以理解为从这个映射的各个方面进行的阐述，来，强制解释一波： 8，9，10 很明显讲的是映射关系的构建，维护，分片。 11，12 讲的是用户输入key的一个组合，返回最匹配的前k个数据，这说明映射的集合set与它对应的key之间是有匹配度的，而且set是可以按这个匹配度进行组织的。（这里有点牵强，毕竟核心思想还在于如何通过线下打分，在线上操作的时候就排除一大批数据，使得线上查询需要精确打分的很少） 13，14，在我看来讲的是映射关系中key怎么进行编码，以及当key不在是单维度信息下，怎么用前缀树，kd-tree这样的结构维护key之间的关系，使得从一个key能够找到其他相似key. 15，16 就是对key编码的升级版，通过simhash，聚类把key的空间减小，同时保留key之间的相似性。 最大感受： 虽然只是key-> set的映射，但怎么根据查询种类去设计key，以及采用什么样的数据结构组织key，set存储结构附加信息，整个映射的构建，更新，分片都是值得深思的问题。

65分