Yes. I have read that big skip lists have poor data locality because the skips jump at unpredictable (probabilistic) times to memory that is probably on a different page.