新一代搜索引擎项目 ZeroSearch 设计探索( 十 ) 本文作者：kaelhua

短链长链与超长链其中超长链的定义相对简单一些，设定一个阈值 X ，当且仅当：倒排链长度 / max（倒排链的 pageid) >= X 则倒排链使用 bitmap 进行存储。 X 的考虑主要是 bitmap 收益与顺序迭代访问损耗的一个折中，这一点需要通过业务数据来实际验证后才能明确。
那么短链和长链又该如何定义。短链与长链的区别对待体现在近邻查找时的 Block 数量上，在这里我们需要先简单分析一下步长增长查找方式与二分查找在性能上的差异。
条件：假设倒排链总长度为 n ，块长为 T ，块数为 N 。二分查找的时间复杂度为：
logN + logT = logn需要注意的是由于倒排查找过程中要找的是第一个大于等于求教基准 N 值的位置，因此每一次二分查找，其查找次数不多不少，都是 logn（n 为还未查找过的文档数量）。如果以倒排链长度为 X 轴，时间复杂度为 Y 轴，那么二分查找的时间复杂度就是一条直线。
当使用步长增长查找方式时，假设第 X 次确定了目标位置，那么其时间复杂度为
X + log2^(X-1) * T = 2X + logT - 1 ，其中1 <= X <= log(N+1)其最小值约等于 logT ，最大值约等于 logN + logn ，如果以倒排链长度为 X 轴，时间复杂度为 Y 轴，那么很明显，步长增长查找方式的时间复杂度为一条曲线。
从步长增长查找的复杂度公式里的最小值和最大值可以知道，越在前面找到下一个求交基准的位置，那么步长增长查找带来的提升就越大，再往后，其性能就开始落后于二分查找了。现在可以开始考虑短链与长链了。假设存在阈值 K ， Block 数目大于 K 的就是长链，小于 K 的就是短链，我们希望的最理想的效果是使用步长增长查找时的平均复杂度小于等于使用二分查找的平均时间复杂度。
由于二分查找的时间复杂度固定为 logn ，因此其平均复杂度也就是 logn 了。而步长增长查找的平均时间复杂度的计算要麻烦许多，假定求交基准落在每一个 Block 的概率是相等的话，那么其平均时间复杂度为：
文章插图
乍一看好像挺复杂的，完全误会了，本人数学底子非常渣。这里其实就是对于每一个 X ，都乘了一下[当前 X 所覆盖的 Block 数量 / 总 Block 数量]的比例值，得到的平均时间复杂度的公式。
总之，由于本人的数学底子非常渣的原因，我这里就直接给出我们这边计划尝试的 K 值了， K=15 。怎么得出来的呢？通过计算 k=3 ， 7 ， 15 ， 31 ， 63 等等情况下的两者的平均时间复杂度，发现 k 值越大，步长增长查找的平均时间复杂度就越高(但其实算法实现的时候会发现，当我们限定了只查找多少个 Block 时，步长增长查找方式的逻辑会轻很多，尽管查找次数上并不占优) 。最后因为如下 2 点原因选择了 15:
1 越靠近的Block ，命中下一个求交基准的概率就越高(仅仅是猜想，还未有实际业务验证) ，虽然k=15时平均复杂度已经比二分高了，但如果越靠前的Block命中概率越高的话，靠前的Block区域加权因子变大，靠后的Block区域加权因子变小，那么其平均复杂度可能并不会比二分高。 2 XMM寄存器一次可比较4个32bit的整数，与步长增长查找15个Block刚好对应。如果XMM的使用确实带来了优化，那么我们后续也会对YMM进行测试。这一点才是主要考虑的原因，为后续指令集优化埋下伏笔。即在我们的引擎里， Block 数量大于等于 15 的则为长链，小于 15 的则为短链。对于长链，在近邻搜索时最多查找 15 个 Blcok（含当前 Block），对于短链，我们只与当前 Block 的最大值进行比较一次。
需要再次说明的是以上的讨论都是建立在猜想：越靠近的 Block ，命中下一个求交基准的概率就越高。原因在于文档在索引分片分库时已经被打散(稀疏)过一次，同时一个 Block 内保存的是多个 pageid ，被稀疏过后的文档又紧密存储(聚集)在一起。
如果猜想不成立呢？
计划用质量标准系统统计一下长链在求交过程中命中下一个求交基准的 Block 与上一个位置所处的 Block 的距离。例如如果有 90%以上是落在 X 个 Block 内的话，那么依然还是有价值先对这 X 个 Block 进行查找的。
另外当我们确定要对 X 个 Block 进行查找时，是有多种查找方式可以使用的，例如从前往后查，或者从后往前查，恒定步长的查找方式，步长增长的查找方式等等。具体如何使用还是需要视数据分布特征而定。