A rule of thumb in computing is that a program will spend 90% of its execution time in 10% of the code. One impact this has is the use of caching to contain those instructions which have been used recently, have been used often, and are near the current instruction 'physicially'.
Two types of locality have been noted: temporal locality and spatial locality. A data structure which uses locality of reference to achieve better long-term performace is the splay tree (a binary search tree with extra rules).