A method of constructing a database in an on-vehicle device includes the steps of connecting a mobile terminal storing a plurality of pieces of music and music information associated with each of the plurality of pieces of music, acquiring the music information of each piece of music from the mobile terminal, when the acquired music information is stored in a storage space, determining whether free capacity of the storage space is insufficient, and when it is determined that the free capacity of the storage space is insufficient, removing at least one piece of music information of each piece of music from the storage space, and constructing a database for searching music on the basis of the music information stored in the storage space.