XDB data structure

The XDB storage and management format is stable and has tested extremely well: it not only supports IP segments at the scale of hundreds of millions, it also shortens query time to the 10 microsecond level. For the code and usage documentation, see Github or Gitee; this page focuses on the structure of the xdb data format.

From the smallest file pointer to the largest, the entire structure is divided into the following four layers:

1. Layer 1: the Header segment

The header segment mainly records some header information. It occupies a fixed 256 bytes, of which only 16 bytes are actually used today; everything that remains is 0x00 reserved space for future expansion needs. The current usage of the space is as follows:

A tangent worth pondering: what possible space expansion needs might there be? For example:

1. If you want to verify the integrity of the xdb data, you can store the MD5 hash of everything outside the header segment in the remaining unoccupied bytes, making it easy to confirm whether the file was damaged during network transfer or project packaging.

2. Adding other information that accelerates queries, and so on.

2. Layer 2: the vector index segment

The vector index segment is the second-level index of the binary search index. It is essentially a 256 × 256 two-dimensional array, equivalent to splitting all IP segments into 256 × 256 partitions by the first two bytes of the IP. This way, a single fixed IO operation can greatly reduce the number of IO operations in the subsequent binary search — the more data rows there are, the more noticeable the speedup this index provides. For the repository's default data, I once measured that most IP queries complete the entire lookup with just two IO operations. The space table structure of the vector index is as follows:

As shown in the table, it is essentially a 256 × 256 two-dimensional array. The structure of each vector index entry — that is, of each of the 256 × 256 cells above — is as follows:

The start position points to the start of the region's binary search index, and the end position points to its end; in other words, the vector index divides the entire binary search index into 256 × 256 partitions, which quickly narrows the search range of the binary search index and thereby speeds up queries. The space of each cell is fixed, so the entire vector index segment occupies 256 × 256 × 8 = 524288 Bytes = 512 KiB; this space is fixed and independent of the number of source IP data rows.

3. Layer 3: the region data segment

The standard format of the source data is start IP|end IP|region info, and this layer stores the region info from the source data. With the xdb format you can completely replace it with your own region info — whatever the source file contains is what gets stored in the xdb; for example, you can use a JSON format to store region info in different languages.

1. For example, the following three consecutive IPv4 segments:

0.0.0.0|0.255.255.255|0|0|内网IP|内网IP
1.0.0.0|1.0.0.255|澳大利亚|0|0|0
1.0.1.0|1.0.3.255|中国|福建省|福州市|电信

are written in turn as the following three consecutive region info entries:

0|0|内网IP|内网IP
澳大利亚|0|0|0
中国|福建省|福州市|电信

2. For example, the following three consecutive IPv6 segments:

2401:b180:2800::|2401:b180:28ff:ffff:ffff:ffff:ffff:ffff|中国|上海|上海市|阿里云
2401:b180:2900::|2401:b180:2fff:ffff:ffff:ffff:ffff:ffff|中国|北京|北京市|阿里云
2401:b180:3000::|2401:b180:30ff:ffff:ffff:ffff:ffff:ffff|中国|广东省|深圳市|阿里云

are written in turn as the following three consecutive region info entries:

中国|上海|上海市|阿里云
中国|北京|北京市|阿里云
中国|广东省|深圳市|阿里云

Whatever the region info in the source file contains is what gets written. Strings use utf-8 encoding, and the maker deduplicates automatically: the same region info is written only once. Before writing, it records the file pointer at that moment and stores it in the data pointer space of the binary search index below. So the space occupied by this layer cannot be determined in advance — it takes up exactly as much space as the data finally written.

4. Layer 4: the binary search index segment

The binary search index layer is the core of a query; the heart of the search process is the binary search within this index. The space table structure of the binary search index is as follows:

Each binary search index entry occupies a fixed $fixed = 14 bytes for IPv4 and a fixed $fixed = 38 bytes for IPv6. The detailed fields and space distribution are as follows:

1. The space structure of an IPv4 binary search index entry, i.e. 14 = 4 + 4 + 2 + 4:

2. The space structure of an IPv6 binary search index entry, i.e. 38 = 16 + 16 + 2 + 4:

So the space occupied by the binary search index cannot be determined in advance either, but it can be computed from the number of source IP segment rows. For example, the default data/ipv4_source.txt source data has 683591 rows, so the binary search index occupies 683591 × 14 = 9570274 Bytes = 9.12 MiB, which takes up the vast majority of the entire 11MiB data/ip2region_v4.xdb. This binary search index space could still be compressed further; my current principle is query speed first, and space compression is not yet necessary at this point. Interested friends are welcome to try compressing it themselves.

Ideas for attempts at compression are as follows:

1. Tail-head merging of index entries: if the continuity of the binary search index entries can be guaranteed, the start IP of the next entry can be derived from the end IP of the previous one, so each entry can drop a fixed IP address worth of space, which would greatly reduce the space usage of the xdb file.

2. Elastic pointers: the pointers inside xdb currently use a fixed 4 bytes; for small files, pointers with a smaller number of bytes could be used to reduce the space usage of the file.

5. XDB layer relationships

The spatial structure of the entire xdb file and the approximate relationships between its layers are illustrated in the figure below: