Efficient IP Geolocation Using In-Memory Red-Black Tree in Real-Time Risk Control

In real‑time risk control systems, many static data derivations such as IP, phone number, and bank‑card BIN lookups are required. Traditional relational‑database‑based IP lookup cannot handle high concurrency and low‑latency demands.

This article uses IP location as an example to show how Ctrip's risk control platform stores IP information in memory, converts it through several indexing steps into a red‑black tree, and thus achieves efficient IP location resolution under heavy load.

Figure 1: Data flow from database to in‑memory red‑black tree.

The process is as follows: IP address records are first loaded from a relational database into memory, each IP range is converted to a 32‑bit integer (long), and the resulting entries are inserted into a red‑black tree. When a query arrives, the IP is converted to a long integer and searched in the tree, yielding the corresponding location record.

Figure 2: IP address classification diagram (A‑E classes).

IP addresses consist of four bytes; each byte is shifted (first <<24, second <<16, third <<8) and summed to obtain a single integer. For example, 1.15.168.0 becomes 16777216 + 983040 + 43008 + 0 = 17803264.

Figure 3: IP to long conversion illustration.

The red‑black tree provides O(log n) search, insertion, and deletion, with the following properties:

Each node is red or black.

The root is black.

All leaves (NIL) are black.

Red nodes have black children (no two consecutive reds on any path).

Every path from a node to its descendant leaves contains the same number of black nodes.

IP location records are stored as JSON objects, for example:

{"region":"天津","start":"1.15.232.0","end":"1.15.232.255","city":"天津","country":"中国"}

{"region":"辽宁","start":"1.14.33.0","end":"1.14.33.255","city":"大连","country":"中国"}

{"region":"北京","start":"1.15.186.0","end":"1.15.186.255","city":"北京","country":"中国"}

These JSON entries are wrapped into Area objects, where type encodes country (1), region (2), and city (4) bits, and name holds the corresponding name. The Area collection is then transformed into a raw‑meta table that maps each type/name pair to an index.

Subsequent steps convert the raw‑meta and IP range data into formatted‑raw‑ip , then into segment‑regions‑ip , and finally into a compact ex‑ip‑segment representation. The final compact data is loaded into the in‑memory red‑black tree, where each node stores parent , left , right , color , from (start IP as long), end (end IP as long), and index (reference to ex‑ip‑segment ).

During a query, the target IP is converted to a long integer and traversed from the tree root: if the value is less than from , move left; if greater than end , move right; otherwise the node contains the location index. The index is used to retrieve country, region, and city from the Area collection.

This in‑memory approach reduces memory usage to about 20 MB for 719,296 IP records and scales well as the dataset grows. Adding new fields (e.g., latitude, ISP) or more IP ranges only requires updating the database and restarting the service, demonstrating good extensibility.

The same technique can be applied to other relatively static datasets that require fast, high‑concurrency lookups.