A randomly accessible storage medium stores unit data including a data body portion including data units, and a management information portion. New data is additionally recorded in the unit data from a predetermined position within the data body portion so that a beginning portion of the new data is additionally recorded in a leading additional recording area extending from the additional recording start position to an end position within a data unit including the additional recording start position. A subsequent portion of the new data is recorded in a physical storage area on the storage medium. The management information portion is updated according to the additionally recorded new data and recorded in the storage medium. The resulting unit data includes a new data body portion starting from the beginning of the previous data body portion and ending in the end of the new data, and the updated managing information portion.