A method comprises: storing data for a plurality of objects in a plurality of physical blocks on a storage medium, using information about the objects to identify logical addresses for the physical blocks used to store the data, pre-fetching the data from particular ones of the physical blocks based on the identified logical addresses, and storing the pre-fetched data in a memory. Apparatus that performs the method is also included.