A method and apparatus for creating and recording management information for digital data streams by grouping transport stream units of a received transport stream into stream object units so that the maximum search time required for locating a specific position within a stream object unit is uniform among a plurality of stream object units. An example embodying the present invention varies the time length of each stream object unit depending upon the bit rate of the received transport stream and keeps the size of each stream object unit constant irrespective of the transfer rate of the data stream, thereby guaranteeing the maximum search time required for locating a transport stream packet within a stream object unit to be uniform.