在文件内建立索引（分析IPIP的*.dat文件）

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

引子

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

文件结构

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

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

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

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离线文件解析库