A recording apparatus for recording compressed video data has compressed video data generator for generating a compressed video data having a plurality of intra frames each of which has no cross-reference to any other frames, and bidirectional interpolated frames and predictive frames each of which has cross-reference to other frame. In the first cycle operation, address detector detects addresses of the intra frames and stores the detected addresses in a memory. A scan information generator generates, with reference to the stored addresses in the memory, scan information for an independent frame including one or two addresses of advanced intra frames and one or two addresses of previous intra frames. The scan information is inserted to each frame and then recorded on a disk. During the reproduce of the disk, the scan information is detected to have a quick access to the intra frame located near by.