请推荐优化的 IP 查找算法和数据结构

Question

我建立了一个包含大约 8,000,000 个 IP 段的 geoip 数据库。为了将其加载到内存中以便快速查找，我尝试使用 std：：map 作为间隔树。每个随机IPv4地址的查找速度约为20-40us，但远远超出了项目要求(每个<10us(。我很感激有人可以就此提出更好的选择，谢谢。

// the geoip info attach to each ip segment
struct geoip_info {
geoip_info(const geoip_info& info);
uint32_t country;
uint32_t subdiv;
uint32_t city;
float    latitude;
float    longitude;
};
// the ip segment definition used as the std::map key
struct ip_segment_key {
uint32_t from;
uint32_t to;
ip_segment_key(uint32_t from, uint32_t to);
ip_segment_key(const ip_segment_key& key);
bool operator==(const ip_segment_key & data) const;
bool operator!=(const ip_segment_key & data) const;
bool operator>(const ip_segment_key & data) const;
bool operator<(const ip_segment_key & data) const;
};
struct lookup_table {
// use std::map as a interval tree here
typedef std::map<ip_segment_key , geoip_info> ip_range_map;
ip_range_map table;
void load(uint32_t ip_range_from, uin32_t ip_range_to, geoip_info &info) {
table.insert(make_pair(ip_segment_key(from, to), value));    
}
// lookuping ip means passing a key with same 'from' and 'to' as the ip argument
bool lookup(uint32_t ip, geoip_info &info) {
auto it = table.find(ip_segment(ip, ip);
if (it != table.end()) {
info = it->second;
return true;
}
return false;
} 
}

Answer 1

我会说这是可用内存的问题......

如果您碰巧为此有 4 个 RAM 演出，那么最终很容易成为 O(1( 查找......

如果您根据可以轻松识别要搜索的树的方法将段划分为多个树，则可以获得包含不超过 2,000,000 个元素的树，这些元素应该在您正在寻找的范围内......n位前缀可能是这样的方法...具体取决于数据集的形状

Answer 2

对于您的 8M IP 子网，您可以创建 128mb 哈希表，包含 16M 的uint64_t值。每个值为：

• 字节 0-3 - 段的 IP 前缀
• 字节 4 - 网络掩码 (0-32(
• 字节 5-7 - 地理位置的 24 位数据值

搜索/插入到因此表中可以通过键执行，包含 5 个最低字节，即通过 IP+网络掩码。

对于给定的地址，只需从 0 迭代掩码到 31，然后每次查找您的哈希表。我认为，所有 31 个搜索总共消耗不到 5 美元。我自己的双哈希实现执行每次搜索 ~120ns，所以在最坏的情况下，你只会花费 4us。 实际上，您将更快地获得结果，因此我估计的实际平均查找时间为1-2us。