Fork me on GitHub

版权声明 本站原创文章 由 萌叔 发表
转载请注明 萌叔 | https://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文件)”的想法;

回复 Java面试题 取消回复

您的电子邮箱地址不会被公开。 必填项已用*标注

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