比普通二分查找快4倍的结构

比普通二分查找快4倍的结构

1、朴素二分查找介绍
 二分查找是查询有序数组的有效结构，对于规模为N的有序数组来说，二分查找算法的时间复杂度为O(logN)。二分查找的步骤如下：

 即每次选择数组范围的中间数据和查询数据比较，如果不等于查询数据则选择一半的范围继续查询。

2、二分查询的缺点
 算法每次选择一段范围的中间节点，每次都相当于一个随机位置比较，对cache和磁盘等非随机结构很不友好。
 
3、改进
 为了提高二分法的速度，我们可以通过重新排列有序数组的位置，减少连续2次访问数据的位置距离。在上面查找11的过程中，最好的设计是把7、11、9连续放在一起，这样3次随机访问变成3次顺序访问（对于cache和磁盘来说，顺序访问和一次随机访问时间一样）。
 如果用树来表示二分查找过程，其图如下：
 

 这个图其实是一个二叉树，中序遍历有序，每个节点包含一个数据。我们知道，1个节点包含多个数据可以提高数据访问的有序性。我们根据这种思想设计了一种树结构，用图表示如下： 
 

 这是一棵后序遍历的有序多叉树（图中为2叉）。利用这棵树，我们最多需要访问3次节点，即可找到想要的数据。
 树虽然访问节点的次数少，但它结构复杂，占用额外空间多，不适合大规模数据（如几kw）。我们可以把树存储为一个数组，即从上到下，存储每层的数据。举例来说： 
  

  
 在查询的时候，我们仍然把数组看成一个逻辑树，所以仍然是查询树的策略。唯一比较复杂的地方是如何快速的把有序数组变成最下面的数组树结构。

4、计算公式
1）设层数N，每个节点包含S个数据，数据总量为ArrayLen个，则满足公式：(S^N-S)/(S-1) >= ArrayLen > (S^(N-1)-S)/(S-1);
2）查询
int bsearch(data,key){
    k1=k2=0;
    for(m=-1;m<N-1;m++){
        p=(S^(m+2)-S)/(S-1)+k1*S;
        if(find(key in data[p->p+S], &k2))
            return convert(m,k1*S+k2);
        k1=k2;
    }
    return -1;
}
3）find函数：遍历即可
4）convert(a,b)
  a、(b+1)(S^(N-1-a)+...+2)+b+([b/S]+[b/S^2]+...)
  b、即下层排前节点个数+本层排前节点个数+上层排前节点个数
  c、如不是完全树，则第一项(b+1)*(S^(N-1-a))的值最大等于最后一层节点数
5）效率：在int数组，64字节cache line，速度提高log(64/4)=4倍