For what data structures is jump search practically useful?

Question

Jump search is a search algorithm for sorted lists which runs in $O(\sqrt n)$ time, but has the advantage of only making backwards steps at the end (and given the ability to make arbitrarily long backwards steps, guarantees only a single backwards step); thus, it may be preferable to binary search if reverse traversal is significantly more expensive than forward traversal.

Now, it's not hard to contrive situations in which that is the case--say, a skip-list which is doubly-linked at the lowest level (so that reverse traversal is possible) but singly-linked for every skip-link (so reverse traversal isn't fast). But what are contexts in which jump search actually makes sense as the most efficient method of searching data that was not specifically constructed to be ideal for jump searching?

Answer 1

But what are contexts in which jump search actually makes sense as the most efficient method of searching data that was not specifically constructed to be ideal for jump searching?

Any context in which data is stored on a physical medium that allows forward jumping quicker than backwards jumping is a candidate. Just think of an ordinary hard drive. Its disk spins in a specific direction, making a forward jump much quicker than a backwards jump. To jump one unit backwards you need the disk to complete (nearly) a full rotation whereas jumping one unit forwards is near-instantaneous. Tape is another example, though here it is mostly the change of direction that is costly rather than backwards jumping specifically. For data stored in RAM, a CPU architecture might be specifically optimized for forward search rather than backward search (in principle, caching and branch prediction might cause differences in the speed of forward and backwards jumping).