A map data storage device, a map data updating method, and a computer program that can shorten the time required for a map data updating process. In the case where map data stored in a navigation-side local DB of a navigation apparatus are to be updated, the navigation apparatus updates the map data stored in the navigation-side local DB on the basis of map updating data received from a map distribution center, and prepares a data reference index that associates a PID (universal identification information) included in the map data with a record number (internal identification information) included in the map data on the basis of the updated map data. After that, in the case where an application is executed by the navigation apparatus, the prepared data reference index is referenced to access the map data stored in the navigation-side local DB.