Embodiments of the present invention provide mechanisms for improving storage consumption on a sequential access medium, such as a physical tape, by preferably storing one instance of a data block of a backup data set on the tape media. When another instance of a data block is received having the same pattern as the stored data block, rather than storing the data block itself, a reference to the data block is stored on the sequential access medium. When data are restored, data blocks are cached at a block store on a storage device(s) having a faster seek time than the tape. When a reference to a previously stored data block is read from the tape, rather than re-winding the tape to search for the data block on the tape (which might take a long time to locate), the referenced data block can be found on the storage device having a faster seek time than the tape media.