The CPU will load less cache data with linear searches. This is because you will have less cache misses. Less cache misses == less loading from memory. With pointer-heavy data structures, you load more from memory, and most of the stuff you do load is useless.
A binary tree might require you to visit only O(log2(N)) of your data, while a linear array on average requires you to visit one half. How does that correspond to less loading from memory?
Linear arrays are often faster, not because they require fewer memory loads, but because the cache has intelligence built in (the prefetcher) that loads some memory in advance even before the code requests it. That intelligence works way better with linear array scans than with pointer chasing. (I'm not sure if these loads will count as cache misses or not).
You need to look at the coefficients. Memory queries pull in 64 bytes of contiguous memory at a time (actually more with speculative prefetching). That extra data is used in a linear scan, but is mostly wasted when doing random access. You also have other bottlenecks with binary search, e.g. branch misprediction.
Yes, for large enough N, a BST easily beats linear search.
> That extra data is used in a linear scan, but is mostly wasted when doing random access
You are shifting goalposts. What the parent poster said is that a linear scan will read more memory than a binary search, therefore it will cause more churn in the cache (assuming same cache policies, which I don't know is a safe assumption), therefore linear scan may actually be less cache friendly - given that you're not interested in the data in any other way besides for the scan - by way of putting other parts of the program whose data was pushed out of the cache at a disadvantage.
Implied was also that linear scan might actually result in a slower program, even if the scan itself might be faster than a binary search.
What you replied is "The CPU will load less cache data with linear searches", which I assume to be false, although I will be happy to learn that it's actually the case (for example because the CPU has a clever cache eviction policy, executing linear scans by streaming in memory into a small part of the cache instead of thrashing the whole cache).
Let's say we have an array of 200 4-byte ints. Let's do a linear array scan and on average will touch 100 of them (or about 7 cache lines). Now let's say we have each integer in its own linked node in a BST in a totally random memory location. We can expect to need about 7 steps as well (2^8 = 256 > 200), which is 7 cache lines. So about 200 is already a lower bound where BST is more efficient in terms of visited cache lines, even for a pessimistic inefficient data structure like this 4-byte integer example.
