Method of generating a database, navigation device and method of determining height information

In a method of generating a database (10) for use in a navigation device, entries (13-18) in a first data structure (11) are generated which are respectively associated with one tile of a tiling. Based on a comparison of a three-dimensional terrain on the respective tile with at least one pre-defined tile pattern, either an identifier (19) for a pre-defined tile pattern or data describing the terrain on the respective tile are stored in the entry. A method of determining height coordinates using the database (10) and a navigation device including the database (10) are also provided.