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; and 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; the map updating system characterized by: 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; an information extracting means adapted to extract, out of 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 the any of the difference update information extracted by the information extracting 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; and 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 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; an information extracting means adapted to extract, out of 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 the any of the difference update information extracted by the information extracting means.