A map updating system comprising: a map information storage means adapted to store therein map information a difference update information obtaining means adapted to obtain one or more pieces of difference update information used for updating a part of the map information stored in the map information storage means to a new piece of map information; a difference updating means adapted to update the map information based on the one or more pieces of difference update information obtained by the difference update information obtaining means; a total update information obtaining means adapted to obtain total update information used for updating an entirety of the map information stored in the map information storage means to a new piece of map information; a total updating means adapted to perform a total update on the map information based on the total update information obtained by the total update information obtaining means; a difference update information storage means adapted to store therein the one or more pieces of difference update information; a comparing means adapted to compare, after the total update performed by the total updating means, a version of the total update information used in the total update with each of versions of the one or more pieces of difference update information stored in the difference update information storage means; and an information extracting means adapted to extract, from the difference update information storage means, any of the one or more pieces of difference update information of which the version is judged to be newer than the version of the total update information by the comparing means; and a re-updating means adapted to update the map information on which the total update has been performed based on said any of the difference update information extracted by the information extracting means; and characterized by an information deleting means adapted to delete the one or more pieces of difference update information including said any of the difference update information extracted by the information extracting means from the difference update information storage means after the map information is updated by the re-updating means. a map information storage means adapted to store therein map information a difference update information obtaining means adapted to obtain one or more pieces of difference update information used for updating a part of the map information stored in the map information storage means to a new piece of map information; a difference updating means adapted to update the map information based on the one or more pieces of difference update information obtained by the difference update information obtaining means; a total update information obtaining means adapted to obtain total update information used for updating an entirety of the map information stored in the map information storage means to a new piece of map information; a total updating means adapted to perform a total update on the map information based on the total update information obtained by the total update information obtaining means; a difference update information storage means adapted to store therein the one or more pieces of difference update information; a comparing means adapted to compare, after the total update performed by the total updating means, a version of the total update information used in the total update with each of versions of the one or more pieces of difference update information stored in the difference update information storage means; and an information extracting means adapted to extract, from the difference update information storage means, any of the one or more pieces of difference update information of which the version is judged to be newer than the version of the total update information by the comparing means; and a re-updating means adapted to update the map information on which the total update has been performed based on said any of the difference update information extracted by the information extracting means; and characterized by an information deleting means adapted to delete the one or more pieces of difference update information including said any of the difference update information extracted by the information extracting means from the difference update information storage means after the map information is updated by the re-updating means.