在移动互联网的应用中，经常需要根据用户的位置信息等做一些用户侧信息的统计分析。而要拿到用户的位置信息，一般有两个方法： GPS 定位的信息和用户 IP 地址。由于每个手机都不一定会打开 GPS，而且有时并不太需要太精确的位置（到城市这个级别即可），所以根据 IP 地址入手来分析用户位置是个不错的选择。 要做到这个功能得需要一个 IP 和地理位置的映射关系库，并依赖这个库启动一个 IP 转地理位置的服务。本文从需求入手，结合 Github 上拥有 8.4k 星的 ip2region 来分析映射关系库的设计以及 IP 如何快速转换成地理位置。

介绍

IP 定位服务很常见，而且很多公司都提供了类似的付费服务，比如阿里，高德，百度等，当然也有公开的免费服务，像 GeoIP，纯真IP等。这些服务要么通过 HTML 页面解析，要么通过接口请求，但不管怎样都离不开一次 http 请求，更不用说大部分服务都对 QPS 作了限制。下表枚举了一些常见的通过 IP 获取地址的方式。

ip2region 的 Github 仓库中提供了 ip2region.db 的生成过程，是用 JAVA 写的，其类图如下所示：

通过熟悉生成 ip2region.db 的源码，简述一下其生成过程如下：

1. 通过 RandomAccessFile 在文件中预留 8 bytes 的 super 块和 2048*8 bytes 的 header 索引区
2. 扫描 ip.merge.txt 文件，对每一条记录作如下处理：依据每一条记录的起始IP, 结束IP 和数据，生成一个索引块， 前四个字节存储起始IP, 中间四个字节存储结束IP, 后四个字节存储已经计算出的数据地址（通过 RandomAccessFile 写入，这里维护一个位置信息到文件位置的字典，保证同一个位置信息只写入一次。），并将索引块暂存在 indexPool 链表中。这一步会将数据区的所有位置信息确定。
3. 扫描完 ip.merge.txt 中所有的记录， 将 indexPool 中所有的索引块写到数据区后面。在此过程中将 int(1024*8/12-1)= 681 个索引块组成一个索引分区，并记录下每个索引分区第一个索引块的起始IP和地址信息（header块），并暂存在 headerPool 链表中。此外还会将索引区的起始位置和结束位置记录下来。
4. 调整 RandomAccessFile 指向文件开头，写入索引区的起始位置存储到 super 块的前四个字节，结束位置存储到 super 块的后四个字节。
5. 继续将 headerPool 中的 header 块写入到 header 区。
6. 调整 RandomAccessFile 指向文件结尾，写入时间戳和版权信息。

TIPS: ip2region 仓库中还使用了 global_region.csv 数据，该文件有5列（行号，，区域，，邮政编码），对应着区域的具体信息，可以往数据区每个位置信息中填充。

快速搜索

ip2region 提供三种查询算法，最差的查询耗时都是ms级别的。分别是内存二分搜索，b+tree搜索，二分查找。耗时依次增加。其搜索结构图如下：

二分搜索

通过 super 块可以拿到索引区的起始位置和结束位置，而且每个索引块都是 12 bytes，其中的 IP 地址都是递增的，所以可以使用二分搜索来快速获取位置信息。其步骤如下：

1. 把 IP 值通过 ip2long 方法转为整型
2. 读取 super 块获取索引区的起始位置和结束位置，二者相减 +1 可得索引块的总个数
3. 采用二分法直接求解，比较索引块中起始IP，结尾IP 和当前 IP 的大小，即可找到该 IP 对应的索引块，根据索引块后面四个字节得到数据地址和数据长度，从而拿到位置信息。

b+tree搜索

b+tree 搜索用到了 header 索引区，第一步先在 header 索引区中使用二分搜索，定位到某个索引分区后，再在对应的索引分区中使用二分搜索。相比较二分搜索而言，它的速度更快，原因是读磁盘的次数远低于二分搜索。其步骤如下：

1. 把 IP 值通过 ip2long 转为整型
2. 使用二分法在 header 索引区中搜索，比较得到对应的 header 索引块以及其对应的索引分区。
3. 读取对应索引分区，再通过二分法定位到对应的索引块，从而获得位置信息。

基于内存的二分搜索

该方法和二分搜索方法类似，区别就是前者将 ip2region.db 全部读进内存中，后者则是通过不断读取 ip2region.db 文件。

总结

ip2region 库只解决了一个非常常见的 IP 定位问题，但将这个服务做到了又小又快（当然还提供了多语言的客户端），从而在 Github 上获得了 8.4k 的 star。

占用内存小

1. 相邻 IP 的位置信息相同，通过 IP 段来解决相邻 IP 对应相同位置信息，避免位置信息被重复存储
2. IP 转换成 INT，像字符串 111.111.111.111 被转换成int（1869573999），从 15Byte 缩小到 4Byte
3. 不同的 IP 段也有相同的位置信息，通过指针来指向特定的位置信息，保证位置信息只保存一次（全量扫描存储进字典中）

搜索速度快

1. IP 有序，使用二分搜索将时间复杂度降到 O(logN)
2. 二级索引 header 索引区的使用，降低磁盘读写频率，先确定索引分区，再从索引分区确定索引位置，在确定位置信息数据。

多语言客户端支持

支持 java、C#、php、c、python、nodejs、php扩展(php5和php7)、golang、rust、lua、lua_c, nginx。

参考文献

1. ip2region 数据库文件结构及原理
2. ip2region源码
3. ipv4的维基百科
4. 各国IPv4地址分配列表
5. 高德地图api
6. 百度地图api