Navigation Class Library  0.1.0
Navigation Class Library
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
Database Files

Database files are generally binary fines containing packed structures.
These files are directly mapped to memory by the handler classes, this guarantees the maximum speed at minimum cost - see the page Phisycal Mapping of Database Files for more details.


Directory Structure

The base directory path is returned by the function DB::GetDBRoot(), see more details there.
In this documentation, it is simply "Database".

Just for an example, let's see a slice of the dtabase directory structure:

db-dir-struct-003.png
db-dir-struct-001.png
Node Id and Node Position Files Name Files

See the details below.

Node Id Databse Files

These files are named NI??.db in the directory under Databse/Id directory, as you can see it in the example above.


Directory Structure


TODO


Node Position Databse Files

These files are named NP??.db in the directory under Databse/Id directory, as you can see it in the example above.


Directory Structure


TODO


Relation Databse Files


Directory Structure


TODO


Name Database Files

These files are named GN??????.db in the directory under Databse/Id directory, as you can see it in the example above.


TODO


Name Id Index File


Directory Structure


TODO


Database File Format

The Database Files are generated in two steps, see the OSM Parser Database File Conversion documentation for details.

The following binary file types are generated for the database:

See the details below.


Generic File Format

db-hdr-001.png
All database files begin with this generic header.
It can identify the database files, and have additional information about the file type and format version.
The header is represented by the struct DB::Header, see other details there.

It contains the following entries:

  • Magic Number:
    This is a 4 character ASCII identifier (without closing null character) with the following content:
    'D' 'n' 'D' 'b'
    This is the abbreviation of 'Ducktor Navi DataBase'.
    It is stored on 32 bits, which also can be identified as a binary value. Note that the byte order is fixed (this is really a string), so the binary value depends on endianness, however, it can be used for comparison. On little endian systems it is 0x62446e44.
  • File Type:
    This is a 16-bit unsigned integer, determining the file type.
    Its value is represented by the enum DB::FTYPE::fTypes, see more detailes there.
  • Version Number:
    This is a 16-bit unsigned integer: the version number of the file format (not the file content). It is just a number, starting from 1. It must be incremented every time when the database content has incompatible modification.
  • File Data:
    It is not really part of the header, and its content is determined by the file type.

The header length is 12 bytes, allowing the other content to be aligned on 32-bit boundary. However, the database uses unaligned content - see the details below.



Node Database File Format

These files contain information for Nodes, indexed by Node Id, Position Id, and Node Position.

  • Node Position Database Files:

    These files are indexed by Position Id and Node Position.

    db-003.png
    The Node Position Database Files contain Position Information indexed by Position and Position Id.
    See the file format details below.

    Node Position File Format details:

    Table Information (the first column on the picture):

    • Header:
      Struct DB::NODE::POS::Header contains generic information, see the details at its description.
    • Tile Map:
      This is a 32-bit sized bitmap: each bit represents a longitude range (5-bit information in the longitude).
      If a bit is set, it means that there is another bitmap for latitude is added (see the Tile Index below) and there is information stored for this position range.
      See detailed description at DB::NODE::POS::TileMap
      This map cannot be empty: if it is, the corresponding database file is not created.
    • Tile Index:
      This is an array of 32-bit sized bitmaps (DB::NODE::POS::TileMap). The size of this array is determined by the number of bits set in the Tile Map (see above).
      Each bit in these bitmaps represents a latitude range (5-bit information in the latitude).
      If a bit is set, it means that there is information stored for this position range in the Tile Table (see below).
      Enpty map is not stored here.
    • Tile Table:
      This is an array of the tiles stored in this file. Each bit set in the Tile Index (see above) represents an entry here, so the maximum size is 1024 (32x32).
      The storage order is determined by the bit access order of Tile Index (see above, and also see BitMapBase<BITS,ALLOC>::operator[](size_t) in the base library documentation for more details).
      The class DynamicContainer is used for this entry.

    Node Table (the second column on the picture):

    • First Id #:
      The first Node Id stored in this table.
    • Extra Size:
      The number of extra nodes to be displayed in this tile.
      Such nodes are stored on neihgbour tiles, but close enough to the border, so must be desplayed on this tile too.
      It can be zero, in this case no extra nodes are stored in the following array.
    • Extra Nodes:
      A simple array of Node Id's from the neihgbour tiles.
    • Node Data:
      This is the Node Data Table, storing information for each node.
      It is an array of the structure DB::NODE::POS::Binary. The elements are stored in incrementing Node Id order. The Node Id itself is not stored, it must be calculated from the starting Id and the position.
      The class DynamicContainer is used for this entry.

    One Node (the third column on the picture):

    • Node Entry:
      This entry holds information about one node.
      • longitude:
        The longitude position of the node. Note that only the lowest bits are stored here, the higher part can be calculated from the indices.
      • latitude:
        The latitude position of the node, also the lowest bits only.
      • Flags:
        This is a bitfield structure, with the following entries:
        • names:
          Hash value for the number of names associated to this node. See DB::NODE::POS::Binary::names for details.
        • type:
          Hash value for the type of this node. See DB::NODE::POS::Binary::type for details.
        • amenity:
          Hash value for the amenity of this node. See DB::NODE::POS::Binary::amenity for details.
      • Node Info:
        Optional entries of these values:
        • Number of Names:
          Optional entry, exists only if names (see above) shows it.
          8-bit unsigned value
        • Type:
          The type value, exists only if the type (see above) shows it.
          8-bit unsigned value
        • Amenity:
          The amenity value, exists only if amenity (see above) shows it.
          8-bit unsigned value
      • Name Id:
        This is the default Name Id. Optional value, exists only if it has at least one name.
      • Names:
        Table of national names associated to this node. Optional, exists only if this node has more than one name associated.

Way and Relation Database File Format

These files contain information for Ways and Relations, indexed by Relation Id.
Note that Ways are stored as a specific kind of Relation.

db-005.png
The Relation Database Files contain indexed Way and Relation entries.
TODO

Name Database File Format

These files contain all the Names stored by increasing Name Id value. The order is determined by the Unicode character values: the Name Id values are assigned by increasing Unicode order. If a national alphabetic order is necessary, it must be stored in a separated Index File (TODO).
To prevent storing the same name more times, all other parts of the database refer these names by Name Id values, and the entries in this database contain all Id values of other objects having the given name.
Note that the Name Id is generated here, it is not part of the original OpenStreetMap database.
As you can see in the example at the top, the files named XXXXXX.db are the Name Database Files.

db-001.png
The Name Database Files contain indexed Name entries, in UTF8 format with associated Id information. To save space, all other database tables use Name Ids to reference a name: this database gives very fast access by Name Id.
See Figure 5 at left about the binary file format. The block Name Db File is the main entry, the details are discussed below.

Name Database File Format:

  • Header:
    Name-specific header, see DB::NAME::Header for details.
  • #entries:
    This is the full number of Name Entries stored in this file.
    32-bit unsigned value.
  • Data:
    This is the dynamically indexed data.
    Such a data entry can be Index Table or Data Table on demand, but both begins with a common structure. The table kind can be determined by this common header. It depends on the content: if the name entries on this level needs more space than defined by DB::NAME::maxDataChunk then an Index Table is built instead of storing the data directly. This is done recursively within the Index Tables (see below). This method guarantees that all Data Tables have at most DB::NAME::maxDataChunk size which reduces the linear search necessary to find a given entry.
    Also see the class DB::NAME::Selector, it helps to select which kind of table is in use.

    • Common Header:
      This part of the header is common for both kind of tables.
      See DB::NAME::DataHeader for details.
      • mode:
        This flag makes difference between Index Table (with value 'I') and Data Table (with value 'D').
        One-byte ASCII character value.
      • Name Id:
        This is the Name Id of the first entry in tis table (Index or Data). The Id values are increased in storing order.
        32-bit unsigned value.
      • size:
        This is the number of entries in this table (Index or Data).
        In the case of Data Table, this is also the number of different Name Id's; that's why there is no separated entry for this information.
        16-bit unsigned value.

    The two possible table kinds:

    • Index Table:
      Such a table stores other Data blocks indexed by the first character.
      See DB::NAME::IndexTable for detailes.
      The Index Table specific members:
      • #entries:
        The number of Name Entries (with different Name Id's) in this table, including the recursive sub-tables stored under this index table.
        32-bit unsigned value.
      • The Indices (#1,#2,...):
        This is an array of DB::NAME::IndexEntry structures. The size of this array is determined by the value in #entries (see above).
        • chr:
          This is the character code (Unicode value) of the current position. Note that the next entries (Index or Data) contain only the remaining characters of the name.
        • offset:
          Points to the corresponding Data entry (relative to the section begin): these are stored after this index table, and also may contain index or data tables, as it is discussed above.
      • The Data:
        This is an array of Index Tables and/or Data Tables.
        The members have dynamic size, and are accessed by the DB::NAME::Index::offset member of the Indices table (see above).

    • Data Table:
      Such a table stores the names directly, in increasing alphabetical (Unicode value) order. However, the names are stored in UTF8 format.
      See DB::NAME::DataTable for details.
      The Data Table specific members:
      • The Indices (#1, #2, ...):
        These are simply the offsets of the Name Entries stored in this Data Table (see below).
        The offset is relative to the end of this index table (i.e. the beginning of the Name Entries, see Figure 2).
        16-bit unsigned integer value.
      • The Name Entries:
        This is an array of the DB::NAME::NameEntry structure:

        • Offset:
          It is the size of the Name and is necessary to calculate the table position stored after the Name. However, the name is null-terminated, but storing the size this way is faster than calling the function strlen() each time.
        • Name:
          This is the remaining part of the Name. Note that the first some characters are determined by the Index Tables, and only the remaining ones are stored here. Note that it is a null-terminated UTF8 string, while the Index Tables contain Unicode values.
        • flags:
          To save as much space as possible, this entry helps to determine the number of associated node and relation entries. See DB::NAME::NameFlag for more details.
        • Nodes:
          Optional table, exists only if nodes are associated at all. This is a simple array of Node Id's, prepended by a size entry if necessary. See DB::NAME::NameFlag::nodes for more details.
        • Relations:
          Optional table, exists only if relations are associated at all. This is a simple array of Relation Id's, prepended by a size entry if necessary. See DB::NAME::NameFlag::relations for more details.

        Common Nodes and Relations table format:
        These tables are simple arrays of Id values, having the following entries:

        • size:
          The number of Id's stored in the table.
          Note that this field is optional, see the details at DB::NAME::NameFlag
        • Id Entries:
          The table of Id values.



Main Name Index File

db-002.png
The Name Id file contains the list of Name Database Files sorted by increasing Id values. It also means sorting by raw character values (the UTF8 converted to Unicode), even though UTF8 strings are stored in the files.
This file can be used to reach the corresponding Name Database File as fast as possible.

Main Name Index File Format:

  • Header:
    Generic header, see Generic File Format for details. The file type is DB::FTYPE::FirstIndex here.
  • size:
    Number of entries stored in this file, i.e. the size of the following array.
  • Data Entries:
    Array of the following structure:
    • chr:
      The first character of the name, stored in Unicode.
      If the requested entry is found, this value gives the first directory name of the hierarchy.
    • Name Id:
      The first Name Id stored in the correcponding Name Database File for this character.
    • size:
      Number of Name Id's stored for this character (chr).