Information storage medium used in the stream information recording, information recording method, information playback method, and information reproducing apparatus

Stream data has a recording data structure formed in units of stream blocks (or stream object units SOBU) which are segmented to have a predetermined data size. Data are recorded (or encoded) and partially erased (or temporarily erased) in units of the stream blocks (SOBUs).