Main data records are recorded in a first area of a non-rewritable optical disk and index records used for retrieving the main data records are recorded in a second area. Each index record includes a code data to be used as an index, and a provisional order which is an order of the code data to be registered, occupying in the code data already registered in the second area. Prior to the data retrieval, the index records are sequentially read out of the second area of the optical disk, the latest index record first, and a sorted index table is prepared in parallel with the readout of the index records by referencing the provisional orders. The data record is retrieved by searching the designated index code data on the index table, reading out a pointer stored in the table in paired relation with the index code and reading out the main data record from the first area of the optical disk.