V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
d5
V2EX  ›  程序员

关于 ip 地址匹配 ip 地址区间的小问题

  •  
  •   d5 · 2020-01-13 13:15:14 +08:00 · 2255 次点击
    这是一个创建于 1537 天前的主题,其中的信息可能已经有所发展或是发生改变。

    需求:用户输入一个 IP 地址,需要匹配出地址对应的小区间

    有上万个这种小区间: 10.238.73.1-10.238.73.30

    个人能想到的只有把 ip 地址段转换为数字(例如上文的小区间是 183388417-183388446),然后通过二分法,找到最近的区间,最后判断用户输入的 ip 地址对应的数字是否在区间内。

    请问大佬们还有没有更简单、更科学的方法?现成的 go&python 库也行。

    8 条回复    2020-01-13 15:21:47 +08:00
    Livid
        1
    Livid  
    MOD
       2020-01-13 13:21:48 +08:00   ❤️ 1
    midasfree
        2
    midasfree  
       2020-01-13 13:26:20 +08:00   ❤️ 1
    转换成 cidr 进行比较
    xkeyideal
        3
    xkeyideal  
       2020-01-13 13:33:24 +08:00   ❤️ 1
    两年前写过这种需求,第一个将 ip 区间排序,无需转换成数字,go 语言有 IP 类型,排序后做区间合并,多个连续的区间合并成一个,查找 IP 是否存在的时候用二分搜索即可
    hankai17
        4
    hankai17  
       2020-01-13 13:37:57 +08:00   ❤️ 1
    github.com/hankai17/ipdb 做了一个 好久没维护了
    xenme
        5
    xenme  
       2020-01-13 13:51:40 +08:00   ❤️ 1
    ipv4 本身就是 32bit 的数据,直接转成二进制(也就是你的数字),然后排序比较就行了啊
    xyjincan
        6
    xyjincan  
       2020-01-13 13:55:07 +08:00   ❤️ 1
    PostgreSQL 数据库, 原生支持这种数据结构,可以直接基于 IP 地址查询匹配 IP 段
    no1xsyzy
        7
    no1xsyzy  
       2020-01-13 15:05:13 +08:00   ❤️ 1
    单次查还是多次查有区别。
    单次的话,问题都不大,线性搜索都没什么问题,应该不是指这个。
    多次就是 bitmap set 时间效率最高,但空间效率一般,直接占用 512 MB 并且需要一次性清零。可以用初始化标记法空间换时间。

    但想了想,话说这个是不是 B-tree 的一般涉猎范畴?
    每个节点是区间下界和上界和下方最上界和上方最下界的值。
    shuax
        8
    shuax  
       2020-01-13 15:21:47 +08:00   ❤️ 1
    二分足够快了
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   5340 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 37ms · UTC 08:24 · PVG 16:24 · LAX 01:24 · JFK 04:24
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.