Fork me on GitHub

版权声明 本站原创文章 由 萌叔 发表
转载请注明 萌叔 | http://vearne.cc

引子

一直比较好奇如何在文件中建立索引
一个机缘巧合我们公司在使用IPIP的IP数据库, 这个公司对外提供的离线文件
为*.dat, IP的查询实际就是对这个离线文件的检索过程,我觉得这个文件的结构,很能够说明我的主题,如何在文件中建立索引

文件结构

首先IP库存在目的,是为了能够查询某个IP对应的以下信息

{
  "country": "中国",
  "region": "北京",
  "city": "北京",
  "isp": "阿里云/电信/联通/移动/铁通/教育网"
}

IP是以段来管理的,而不是单个IP

字段 类型 说明 备注
segment_start int IP段起始 由于ip是递增的,因此这个字段实际并不存在
segment_end int IP段结束 对于IPv4是4个字节
country string 国家
region string 省份
city string 城市
isp string 运营商

IP段的数量有限, 不超过2w

为了方便大家更好的理解文件结构,我画了一张图
示意图

说明

  1. 第1级索引直接使用IP的第1字节,因此最多256个,每个占4个字节
  2. 第2级索引,每个8个字节,其中前4个字节为segment_end,后4个字节中,前3个字节是是记录在文件中的偏移,最后一个字节,为记录的长度

检索

检索的过程,程序将整个文件加载并驻留到内存中,然后在内存中进行相应的操作

检索时间分析

由于IP段的数量有限(不超过2w),
在索引1区域的查找次数是1
在索引2区域的查找次数不超过20000/256(约为78)
由于在内存中操作,所以速度还是相当快的

参考资料

  1. ipip离线文件解析库

如果我的文章对你有帮助,你可以给我打赏以促使我拿出更多的时间和精力来分享我的经验和思考总结。

微信支付码

2 对 “在文件内建立索引(分析IPIP的*.dat文件)”的想法;

发表评论

电子邮件地址不会被公开。

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据