Navigation device and method of determining a height coordinate

A navigation device has a database which stores index data for respectively a tile (25) of a tiling. The index data includes for each one of plural cells of a grid which is superimposed on the tile respectively an identifier for each triangular face (26-39) of a triangulated irregular network which at least partially overlaps with the respective cell. The plural cells of the grid are defined so as to cover the respective tile (25). A processing device of the navigation device is configured to use the index data to determine a triangular face (26-39) on which a map feature having given lateral coordinates is located, in order to determine a height coordinate of the map feature. A method of determining height coordinates using the database and a method of generating the database are also described.