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

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

这是一个创建于 3225 天前的主题，其中的信息可能已经有所发展或是发生改变。

数据格式如下
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

ip 数据来源为： https://db-ip.com/db/

解决方案见
https://code.csdn.net/snippets/1556752

文本

2.5.5.6

2.5.5.5

1.1.1.0

24 条回复 • 2016-01-14 23:31:29 +08:00

sunchen

2016-01-12 15:23:46 +08:00

ip 地址转化成 32 位数字，然后经典的 bitmap 查找

popu111

2016-01-12 15:32:35 +08:00 via Android

跑一遍存到 MySQL 里面去，然后就好多啦⊙▽⊙

luban

2016-01-12 15:34:41 +08:00

@popu111 存到 mysql 也是不小的
推荐看这个， ip 数据有 txt 和作者自己封装的格式，比较准确，多种语言客户端都有代码
http://git.oschina.net/lionsoul/ip2region

paw

2016-01-12 15:35:36 +08:00

参考纯真 IP 库的实现，。，
https://github.com/gwind/ylinux/tree/master/tools/IP/QQWry
一个 py 实现

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 >= ?

0987363

2016-01-12 15:43:59 +08:00

转 32 位然后筛选吧

xuboying

2016-01-12 15:49:44 +08:00

@0987363 @luban @paw @picasso250 @popu111 @sunchen
感谢建议，我大概有思路了，可以造一个小的索引文件，类似 startdict 的格式
数据库我不是很熟悉，可能最终做不出我要的效果

congeec

2016-01-12 16:00:51 +08:00 via iPhone

转 32bit 数字然后存到数据库
实在要文本的话用 btree 建立索引吧
最后别忘了加缓存

congeec

2016-01-12 16:03:06 +08:00 via iPhone

文本只读不写的话可以分段多进程搜索，毕竟没有数据竞争，安全

lululau

2016-01-12 16:10:27 +08:00

我怎么记得一个国内的 IP 库也就几十 MB

xuboying

2016-01-12 16:20:23 +08:00

@lululau https://db-ip.com/db/

Livid

MOD

2016-01-12 16:26:40 +08:00

用 Redis 的 Sorted Sets ：

http://redis.io/commands#sorted_set

TaMud

2016-01-12 16:28:13 +08:00

ip 数据库都能卖钱〜〜〜〜〜

ryd994

2016-01-12 20:14:01 +08:00

用 CIDR ，查询的时候按 prefix 长度顺序查

mlhadoop

2016-01-12 21:21:00 +08:00

字典树可以吗？

wbsdty331

2016-01-12 21:49:09 +08:00

纯真 IP 看 i

skydiver

2016-01-12 21:52:56 +08:00

有多巨型？

raysonx

2016-01-12 22:05:16 +08:00 via Android

IP 地址轉為 32 位二進制存儲，建立索引使用二分查找

h4x3rotab

2016-01-12 22:13:32 +08:00 via iPhone

数据和 key 分离是必须的，你肯定要一个索引。

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

对于重合的区间查找，要用区间树或者线段树才能有效保证查询效率，其他所有的做法都不靠谱， bitmap 只适用于分布均匀的小量数据，只支持一个 key 的各种容器或者数据库就更不用考虑了，最坏情况要遍历大半个索引。

strwei

2016-01-12 22:45:57 +08:00

碎片化

Orzzzz

2016-01-12 23:20:19 +08:00

zgrep

KentY

2016-01-13 05:02:35 +08:00

先说说有多大

caocheng

2016-01-13 14:15:36 +08:00

比如 postgres 数据库有 inet 类型

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