A road map data structure includes road network data Rn, representing roads by a connection relation of a plurality of links L, in a hierarchical structure of a plurality of levels, in which, as a link ID for each link L at a lowest level, consecutive serial IDs, according to a connection order of the links within a link line ML formed of a plurality of the consecutive links having a common attribute, are assigned to first links L1 which have a corresponding link existing at a higher level, and a permanent ID, irrelevant with the connection order of the links, is assigned to a second link L2 which does not have a corresponding link existing at a higher level.