A search data update system includes a navigation apparatus in which search data are used and a data provider center that provides the navigation apparatus with update data to be used to update the search data. The update data provided by the data provider center only include new search tree data and update entity data. The new search tree data assume a structure that enables specification of the update entity data and specification of the entity data in the original search data except for the entity data corresponding to the update entity data.