在文件内建立索引（分析IPIP的*.dat文件）
版权声明 本站原创文章 由 萌叔 发表 转载请注明 萌叔 | 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级索引直接使用IP的第1字节，因此最多256个，每个占4个字节 第2级索引，每个8个字节，其中前4个字节为segment_end，后4个字节中，前3个字节是是记录在文件中的偏移，最后一个字节，为记录的长度 检索 检索的过程，程序将整个文件加载并驻留到内存中，然后在内存中进行相应的操作 检索时间分析 由于IP段的数量有限（不超过2w）， 在第1级索引的查找次数是1 在第2级索引的是顺序遍历的 平均需要遍历的索引条目条数为 20000/256 ≈ 80 索引条目是固定长度（8bytes），且文件已经提前加载到了内存中，因此速度还是很快的。 ...