deque vs vector

Which is a key structural difference between std::deque and std::vector that affects their performance characteristics?