本発明は、特に、コンテンツデータの所望のシーンをユーザにより容易に検索することができるようにした、再生装置、および、再生方法、記録装置、および、記録方法、記録媒体、プログラム格納媒体、並びに、プログラムに関する。検索に利用する情報を、コンテンツデータとともに光ディスクに記録する。光ディスクに記録されるデータには、少なくとも、コンテンツデータ本体と、再生装置において所定のメニュー画面を外部の表示装置に表示させるためのシーン付加情報とが含まれる。そのシーンのＩＮ点とＯＵＴ点を示す情報、および、検索のキーと値のペアが複数定義されているシーン毎の情報が、シーンの数だけ含まれているデータ構造のシーン付加情報が、コンテンツデータとともに、光ディスクに記録される。本発明は、記録装置、再生装置、光ディスクなどの記録媒体に適用できる。