1. A computer program product comprising a computer readable storage medium having a computer readable program stored therein, wherein the computer readable program, when executed on a computing device, causes the computing device to: determine frequently accessed non-sequential cache records in a cache subsystem; collect trailing record statistics for the frequently accessed non-sequential cache records; determine a caching strategy, wherein the caching strategy comprises prefetching a set of trailing records responsive to a read of a given frequently accessed non-sequential cache record; and apply the caching strategy to the cache subsystem.