This invention provides a method of managing the navigation data for a rewritable recording medium which are referred to for control of recording, editing, and reproduction. It enables to access to each information table in the navigation data directly by referring to the start address, which is kept in the first information table in the navigation data. When data are recorded to the rewritable recording medium, the management data which are relevant to the data to be recorded are created and written to the relevant information tables, which are accessed directly based on the start addresses. When data on the recording medium are reproduced, the information tables which contain management data required for reproduction of the requested data are located directly by the start addresses. Then, the data are read out from the rewritable recording medium and reproduced in reference to the management data. Compared to the prior navigation data structure, where the information tables are accessed through calculation of the end addresses, the present invention allows to reduce the access time to each information table, contributing to the real-time operation for writing and reproduction.