Both. The hypothesis with Eytzinger is that you're doing vanilla binary search on a data structure where each hop is one operation. It doesn't, by itself, do anything to optimize around particular hot leaves, so assuming you aren't doing a weighted rebalance operation before construction it additionally assumes access patterns are somewhat uniform. That's the algorithm and input pattern whose cachability we're trying to optimize.

Imagine, e.g., doing a b-tree lookup on a binary Eytzinger layout. You would always grab more cache lines than optimal. Even more obviously, consider an inorder traversal. The properties of an algorithm and data structure depend properly on both components.

Locality is a property of how data is arranged, so it's a property of the data structure, no?