为何数组二分查找比二叉搜索树略快？缓存效应是原因吗？

嗨，这个问题问到点子上了——缓存效应确实是大数据量下数组二分查找反超的核心原因，咱们来仔细唠唠：

数组的内存连续性是关键：

• 数组在内存里是一块连续的存储空间，CPU在访问某个元素时，会遵循「空间局部性」原理，把这个元素附近的一整块内存都加载到高速缓存里。这样后续二分查找时，下一个要访问的array[mid]很大概率已经在缓存里了，不用频繁去速度慢很多的主存取数据。
• 当数据规模极大时，主存和缓存的速度差距会被无限放大，这种缓存友好性带来的优势就会非常明显。

普通的链式二叉搜索树完全没有内存连续性的特性：

• 链式BST的每个节点都是动态分配的，在内存里是零散分布的，左右子节点可能在完全不相邻的内存区域。每次访问子节点都可能触发一次主存访问，缓存命中率极低。
• 只有一些特殊实现的二叉搜索树（比如用数组模拟的平衡BST、或者B-树/B+树这类多路搜索树）才会有一定的缓存友好性——比如B+树的叶子节点是连续存储的，这也是数据库索引偏爱B+树的原因之一，但这已经不是咱们通常说的普通链式BST了。

当数据量较小时，不管是数组还是BST，访问数据的开销主要集中在算法本身的O(logn)逻辑上，主存和缓存的速度差异还没凸显出来，所以两者的实际执行速度看起来差不多。但数据量上去后，缓存命中率的差异导致的常数项开销被放大，数组二分的优势就显现了。

附上你提供的数组二分查找代码（补全了未写完的分支逻辑）：

int binary_array_search(int array[], int length, int query){
    // the array has been sorted
    int left=0, right=length-1;
    int mid;
    while(left <= right){
        mid = (left+right)/2;
        if(query == array[mid]){
            return 1;
        } else if(query < array[mid]){
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return 0; // 未找到目标时返回0
}

内容的提问来源于stack exchange，提问作者CSDUG