检测postgresql数据库中子网重叠的最佳方法

Question

我有一个postgres数据库,有近200'000个网络地址类型.我想检测一些子网是否重叠,例如检测123.0.0.0/16,123.2.0.0/24和123.3.4.128/30并报告它们.

我已经使用了很多python脚本和netaddr库.

考虑到条目数量,检测重叠的最佳方法/算法是什么？

我很确定比将每个条目与整个数据库进行比较有更好的方法.

Answer 1

我认为以下应该是一种相当有效的方法:

import netaddr
import bisect

def subnets_overlap(subnets):
    # ranges will be a sorted list of alternating start and end addresses
    ranges = []
    for subnet in subnets:
        # find indices to insert start and end addresses
        first = bisect.bisect_left(ranges, subnet.first)
        last = bisect.bisect_right(ranges, subnet.last)
        # check the overlap conditions and return if one is met
        if first != last or first % 2 == 1:
            return True
        ranges[first:first] = [subnet.first, subnet.last]
    return False

例子:

>>> subnets_overlap([netaddr.IPNetwork('1.0.0.0/24'), netaddr.IPNetwork('1.0.0.252/30')])
True
>>> subnets_overlap([netaddr.IPNetwork('1.0.0.0/24'), netaddr.IPNetwork('1.0.1.0/24')])
False