处理海量IP网络数据：List+Set与Dict的存储效率对比及优化

我有数百万条IPv4（及IPv6）网络数据，格式如下：

sample = [
    [16777216, 33554431, None, 'AU', False, False, False, False],
    [16777216, 16777471, 13335, 'AU', False, True, False, False],
    [16777472, 16777727, None, 'CN', False, False, False, False],
    [16777728, 16778239, None, 'CN', False, False, False, False],
    [16778240, 16779263, 38803, 'AU', False, False, False, False],
    [16778496, 16778751, 38803, 'AU', False, False, False, False],
    [16779264, 16781311, None, 'CN', False, False, False, False],
    [16781312, 16785407, None, 'JP', False, False, False, False],
    [16781312, 16781567, 2519, 'JP', False, False, False, False],
    [16785408, 16793599, None, 'CN', False, False, False, False],
    [16785408, 16785663, 141748, 'CN', False, False, False, False],
    [16793600, 16809983, 18144, 'JP', False, False, False, False],
    [16809984, 16842751, 23969, 'TH', False, False, False, False],
    [16809984, 16826367, 23969, 'TH', False, False, False, False],
    [16809984, 16818175, 23969, 'TH', False, False, False, False],
    [16809984, 16810239, 23969, 'TH', False, False, False, False],
    [16810240, 16810495, 23969, 'TH', False, False, False, False],
    [16810496, 16811007, 23969, 'TH', False, False, False, False],
    [16811008, 16811263, 23969, 'TH', False, False, False, False],
    [16811264, 16811519, 23969, 'TH', False, False, False, False],
    [16812032, 16812287, 23969, 'TH', False, False, False, False],
    [16812288, 16812543, 23969, 'TH', False, False, False, False],
    [16812544, 16812799, 23969, 'TH', False, False, False, False],
    [16812800, 16813055, 23969, 'TH', False, False, False, False],
    [16813312, 16813567, 23969, 'TH', False, False, False, False],
    [16814080, 16818175, 23969, 'TH', False, False, False, False],
    [16818176, 16826367, 23969, 'TH', False, False, False, False],
    [16818176, 16819199, 23969, 'TH', False, False, False, False],
    [16819200, 16819455, 23969, 'TH', False, False, False, False],
    [16819456, 16819711, 23969, 'TH', False, False, False, False],
    [16819712, 16819967, 23969, 'TH', False, False, False, False],
    [16819968, 16820223, 23969, 'TH', False, False, False, False]
]

这些数据需要转换为sqlite3数据库并支持每日更新。观察数据可知，仅起始与结束IP段唯一，其余6个字段存在大量重复，直接存储会造成极大空间浪费，因此计划将重复字段组存储为唯一集合，用索引引用替代原字段以压缩数据。

初始压缩方案的缺陷 #

最初尝试用List按出现顺序存储唯一字段组，但List的存在性检查是O(n)线性搜索，效率极低。改用Set做O(1)存在性检查的方案如下：

groups = []
unique_groups = set()
compressed = []
for row in sample:
    data = tuple(row[2:])
    if data in unique_groups:
        compressed.append([*row[:2], groups.index(data)])
    else:
        unique_groups.add(data)
        compressed.append([*row[:2], len(groups)])
        groups.append(data)

该方案的问题在于List.index仍为线性搜索，且每个唯一字段组需存储两份（List和Set各一份），空间占用翻倍。

更优的Dict方案 #

改用Dict实现的方案性能更优：

groups = {}
compressed = []
for row in sample:
    data = tuple(row[2:])
    compressed.append([*row[:2], groups.setdefault(data, len(groups))])

此方案借助Dict的O(1)查找特性，避免了线性搜索，且无需重复存储字段组。但Python Dict本身空间开销较大，不确定在海量数据下的空间复杂度表现。

IP段预处理逻辑 #

在压缩前，需要先对数据进行预处理：拆分重叠的IP段（以更短段的数据为准）、合并相邻且属性相同的IP段，消除歧义并最小化数据量。示例数据处理后的结果为：

[(16777216, 16777471, 1),
 (16777472, 16778239, 2),
 (16778240, 16779263, 3),
 (16779264, 16781311, 2),
 (16781312, 16781567, 5),
 (16781568, 16785407, 4),
 (16785408, 16785663, 6),
 (16785664, 16793599, 2),
 (16793600, 16809983, 7),
 (16809984, 16842751, 8),
 (16842752, 33554431, 0)]

内存加载与快速查询 #

处理后的数据存入sqlite3的两张表仅用于持久化（磁盘查询IO延迟过高），程序启动时加载为Python List，通过二分查找实现快速IP归属查询：

from bisect import bisect

ASN = [
    (None, 'AU', False, False, False, False),
    (13335, 'AU', False, True, False, False),
    (None, 'CN', False, False, False, False),
    (38803, 'AU', False, False, False, False),
    (None, 'JP', False, False, False, False),
    (2519, 'JP', False, False, False, False),
    (141748, 'CN', False, False, False, False),
    (18144, 'JP', False, False, False, False),
    (23969, 'TH', False, False, False, False)
]

NETWORKS = [
    (16777216, 16777471, 1),
    (16777472, 16778239, 2),
    (16778240, 16779263, 3),
    (16779264, 16781311, 2),
    (16781312, 16781567, 5),
    (16781568, 16785407, 4),
    (16785408, 16785663, 6),
    (16785664, 16793599, 2),
    (16793600, 16809983, 7),
    (16809984, 16842751, 8),
    (16842752, 33554431, 0)
]

STARTS, ENDS, ASNS = zip(*NETWORKS)

def get_network(ip):
    index = bisect(STARTS, ip) - 1
    if ip <= (end := ENDS[index]):
        return [STARTS[index], end, *ASN[index]]
    return None

经基准测试，Dict方案的时空效率均优于List+Set方案，但仍希望探索更优的实现方式。

内容的提问来源于stack exchange，提问作者Ξένη Γήινος