A recording medium cartridge includes a memory circuit for storing information concerning signals recorded on the recording medium within the cartridge. The information is stored in the memory circuit in the form of a hierarchic data structure which includes a plurality of data packets having a predetermined form and length. Each data packet includes a code indicative of a level in the data structure to which the data packet belongs. At least some of the data packets include data indicative of starting and ending positions on the recording medium of recorded signals which the data packet represents. The hierarchic (or “tree”) data structure facilitates rapid retrieval and reproduction of the signals recorded on the recording medium, particularly when the recording medium is a magnetic tape. The tree structure also facilitates storage of information in connection with recording of additional signals on the recording medium.