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

对于一个保存了 ip 起止地址的巨型文本数据库,怎么优化才能既方便查找又节约空间?

  •  
  •   xuboying · 2016-01-12 15:16:54 +08:00 · 3602 次点击
    这是一个创建于 1375 天前的主题,其中的信息可能已经有所发展或是发生改变。
    数据格式如下
    0.0.0.0,1.1.1.0, 信息 0
    1.1.1.1,2.2.2.2, 信息 1
    2.2.2.3,2.5.5.5, 信息 3
    2.5.5.6,...
    文本数据量非常大,不方便一次全读入内存,如果 grep 一个 ip 地址也可能落在区间找不到
    有什么方法可以既压缩数据,又方便查找么
    sqlite 可以么,能否支持查询 ip 区间
    (程序语言希望用 python 实现)
    第 1 条附言  ·  2016-01-14 23:32:13 +08:00
    24 回复  |  直到 2016-01-14 23:31:29 +08:00
        1
    sunchen   2016-01-12 15:23:46 +08:00
    ip 地址转化成 32 位数字, 然后经典的 bitmap 查找
        2
    popu111   2016-01-12 15:32:35 +08:00 via Android
    跑一遍存到 MySQL 里面去,然后就好多啦⊙▽⊙
        3
    luban   2016-01-12 15:34:41 +08:00
    @popu111 存到 mysql 也是不小的
    推荐看这个, ip 数据有 txt 和作者自己封装的格式,比较准确,多种语言客户端都有代码
    http://git.oschina.net/lionsoul/ip2region
        4
    paw   2016-01-12 15:35:36 +08:00
    参考 纯真 IP 库 的实现,。,
    https://github.com/gwind/ylinux/tree/master/tools/IP/QQWry
    一个 py 实现
        5
    picasso250   2016-01-12 15:42:15 +08:00
    新建一个 table ipt
    有 3 列,如下:
    ip_start int
    ip_end int
    info varchar

    在 ip_start 和 ip_end 上各建一个索引

    将这个 txt 跑一遍,存下来

    select * from ipt where ip_start <= ? and ip_end >= ?
        6
    0987363   2016-01-12 15:43:59 +08:00
    转 32 位然后筛选吧
        7
    xuboying   2016-01-12 15:49:44 +08:00
    @0987363 @luban @paw @picasso250 @popu111 @sunchen
    感谢建议,我大概有思路了,可以造一个小的索引文件,类似 startdict 的格式
    数据库我不是很熟悉,可能最终做不出我要的效果
        8
    congeec   2016-01-12 16:00:51 +08:00 via iPhone
    转 32bit 数字然后存到数据库
    实在要文本的话用 btree 建立索引吧
    最后别忘了加缓存
        9
    congeec   2016-01-12 16:03:06 +08:00 via iPhone
    文本只读不写的话可以分段多进程搜索,毕竟没有数据竞争,安全
        10
    lululau   2016-01-12 16:10:27 +08:00
    我怎么记得一个国内的 IP 库也就几十 MB
        11
    xuboying   2016-01-12 16:20:23 +08:00
        12
    Livid   V2EX Moderator   2016-01-12 16:26:40 +08:00
    用 Redis 的 Sorted Sets :

    http://redis.io/commands#sorted_set
        13
    TaMud   2016-01-12 16:28:13 +08:00
    ip 数据库都能卖钱〜〜〜〜〜
        14
    ryd994   2016-01-12 20:14:01 +08:00
    用 CIDR ,查询的时候按 prefix 长度顺序查
        15
    mlhadoop   2016-01-12 21:21:00 +08:00
    字典树可以吗?
        16
    wbsdty331   2016-01-12 21:49:09 +08:00
    纯真 IP 看 i
        17
    skydiver   2016-01-12 21:52:56 +08:00
    有多巨型?
        18
    raysonx   2016-01-12 22:05:16 +08:00 via Android
    IP 地址轉為 32 位二進制存儲,建立索引使用二分查找
        19
    h4x3rotab   2016-01-12 22:13:32 +08:00 via iPhone   ♥ 1
    数据和 key 分离是必须的,你肯定要一个索引。

    首先 ipv4 地址就是一个 int32 ,所以 key 很好处理。其次要看你的区间会不会重叠,没有交集自然随便搞,是排序之后二分查找,还是丢进什么可以查找的树结构都没问题。但是如果区间会重合,上面大多数人的答案都是错的。

    对于重合的区间查找,要用区间树或者线段树才能有效保证查询效率,其他所有的做法都不靠谱, bitmap 只适用于分布均匀的小量数据,只支持一个 key 的各种容器或者数据库就更不用考虑了,最坏情况要遍历大半个索引。
        20
    strwei   2016-01-12 22:45:57 +08:00
    碎片化
        21
    Orzzzz   2016-01-12 23:20:19 +08:00
    zgrep
        22
    KentY   2016-01-13 05:02:35 +08:00
    先说说有多大
        23
    caocheng   2016-01-13 14:15:36 +08:00
    比如 postgres 数据库有 inet 类型
        24
    xuboying   2016-01-14 23:31:29 +08:00
    @0987363 @KentY @Livid @Orzzzz @TaMud @caocheng @congeec @h4x3rotab @luban @strwei @raysonx
    感谢各位帮忙献计献策,我最终用了 stardict 的格式的解决方案,为 csv 数据建立索引,再用二分查找法搜索,数据库不熟悉,没有采用,具体见 https://code.csdn.net/snippets/1556752
    关于   ·   FAQ   ·   API   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   1908 人在线   最高记录 5043   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.3 · 23ms · UTC 16:16 · PVG 00:16 · LAX 09:16 · JFK 12:16
    ♥ Do have faith in what you're doing.