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

1 非稠密区域与非稠密区域的查找，与短链与短链的查找特点相似2 非稠密区域与稠密区域的查找，与短链与长链的查找特点相似3 稠密区域与稠密区域的查找，与长链与长链的查找特点相似尽管问题又得到了回归，但是数据分布均匀与否依然有着显著的差异，即数据分布均匀的情况下，它的求交特点是稳定的，而数据分布不均匀时，求交特点是变化的，可能上一次查找属于非稠密区域与非稠密区域的查找，下一次查找时就落入了稠密区域与稠密区域的查找了，甚至随着求交过程，长链与短链的相对关系也在变化。
关于如何去评判一条倒排链的数据分布情况，计划采用的方式是通过计算间距的平均值和方差来进行评判，因此实际上当前我们对于这一点也还属于还未开工的探索阶段，暂且无法得到数据分布特征的一些数据。
不管怎样，问题总算是得到了回归，至少我们可以得到以下两点结论和一个猜想：1 多条倒排链求交时，其耗时主要由短链的长度决定,原因是求交基准的数目上限由短链决定。
2 多条长链求交时，长链每次查找范围过大，因此查找消耗较大。
3 猜想:不论是对于长链还是短链，下一个求交基准大概率落在近邻 Block 内
以这 3 点为基础，可以给我们的查找算法带来一些新的思路。下面介绍求交优化的做法。
1 倒排链查找优化根据猜想：下一个求交基准大概率落在近邻 Block 内。我们将先使用步长增长查找的方式对近邻 Block 进行查找，未找到再二分查找剩余 Block ， Block 内依然使用二分查找。
步长增长查找：每次向后查找的 Block 数量为 2^(n-1) ，确定目标位置后，再在该 2^(n-1)个 Block 内进行二分查找。
了解到这种查找方式其实有个专有名词叫：Galloping Search ，其实是很轻松就能想到的方式。
需要注意的是，在这里我们需要对长链和短链区分处理，简单来说就是短链查找的近邻 Block 较少，长链查找的近邻 Block 较多。具体下文会分析。
2 bitmap对于超长链，其倒排结构使用 bitmap 进行存储， bitmap 具备快速求交、快速求并、快速查找等特性，然而 bitmap 在 bit 位稀疏时的顺序迭代访问性能较差，而求交基准在选取时是需要获取每个节点当前指向的 pageid 的，对于 bitmap 来说，需要通过顺序迭代访问来找到第一个非零 bit 位。因此超长链的定义将主要由 bitmap 带来的收益和迭代性能来决定，仅从空间使用率上来看，未压缩的情况下其实一条倒排链只需要满足长度大于等于索引库文档总数/32（pageid 采用 4 字节存储）即可，当然这个标准在性能上肯定是不行的。
3 语法树查询优化
3.1 短链优先查找由于短链节点查找消耗更低，单次查找更快，因此短链节点优先查找，用于快速更新求交基准，减少后续倒排链的查找次数，同时 pageid 值的间距更大的可能性较高，利于快速增长求交基准 N 。
需要注意的是，随着求交过程的不断执行，长链，短链的相对关系可能会发生变化，这里的短链优先查找是在求交开始之前就对查询节点的查询顺序进行调整，后续不会再进行调整。
3.2 同义词子树置后查找与短链节点优先查找对应，由于同义词子树一次查找需要对多个 Term 节点进行倒排查找，因此在评估单次查找消耗时，需要以整颗子树进行考虑，其查找消耗是该子树下所有 Term 节点之和。最终的效果会导致同义词子树被置后查找。同样的，这里的调整是在求交开始之前就完成，后续不会再进行调整。
3.3 bitmap 合并bitmap 语法节点合并，对于有多个 bitmap 子节点的父节点，可对其新增一个虚拟语法节点，对 or 节点下的 bitmap 节点进行求并，对 and 节点下的 bitmap 节点进行求交。
3.4 重复词节点合并对于语法树中的每个 Term 节点，我们只会创建一个倒排访问对象，简称游标(Cursor) 。在逻辑后验算法里，所有倒排链都在往求交基准 N 查找，因此对于相同的 Term 节点，它们可以共享同一个游标。
4 指令集优化经组内同事 sen 指点，在求交过程中可以利用 SSE 指令集(需要硬件支持)中的 XMM(128bit)、YMM(256bit)等大长度寄存器，使用单指令多数据流的方法一次比较多个整形元素，来达到求交加速的效果。这类寄存器的使用跟步长增长查找的方式恰好十分匹配，这一点属于我们后续打算尝试的一个方向。
那么遗留下来的问题就是如何定义短链，长链，以及超长链了。