I've never applied it to rigorously prove the cost of some algorithm or data structure but I believe what you're looking for is the Idealized-cache model. The idea is to do Big O analysis where the cost is the number of cache block transfers instead of atomic machine instructions. E.g. Traversing an array under that model is
n is the number of elements and
B is the cache block size. (Technically
n is the number of bytes the array elements take up, but the difference between that and the number of elements is a constant factor, which Big O notation ignores.)
You might want to read the paper Cache Efficient Functional Algorithms, which applies this kind of analysis in the context of a purely functional language. I'm sure there's plenty of other papers as well; cache-efficient and cache-oblivious data structures and algorithms are an active research topic.
In a language with a generational garbage collector you make use of the heuristic that things that are allocated sequentially in time will generally end up adjacent in memory. The reason for this is that generational garbage collectors usually allocate sequentially in the youngest generation, and when a collection happens the live objects will be compacted and possibly moved to an older generation as well. When this happens the object graph will generally be traversed in depth-first or breadth-first order, but either way objects end up adjacent to other objects they point to.
If your language's garbage collector is non-generational and also non-moving/copying/compacting I don't know what you'd do, but then your performance is probably screwed either way since your memory is fragmented.
On the subject cache-efficient trees, you might want to read Improving RRB-Tree Performance through Transience which talks about a vector/list implementation using trees whose nodes have 31 or 32 children each.