开源 IP 地址定位库-ip2region
2017-10-21 10:13:00 
阿炯
ip2region是准确率99.9%的ip地址定位库，0.0x毫秒级查询，数据库文件大小只有2.7M，提供了java、php、c、nodejs、golang查询绑定和Binary、B树、内存三种查询算法。采用ApacheV2协议授权。
ip2region 的ip数据来自纯真和淘宝的ip数据库，每次抓取完成之后会生成 ip.merge.txt， 再通过程序根据这个源文件生成ip2region.db 文件。
ip.merge.txt 中每一行对应一条完整记录，每一条记录由ip段和数据组成，格式如下：
0.0.0.0|0.255.255.255|未分配或者内网IP|0|0|0|0
1.0.0.0|1.0.0.255|澳大利亚|0|0|0|0
1.0.1.0|1.0.3.255|中国|华东|福建省|福州市|电信
从左到右分别表示： 起始ip,结束ip,国家，区域，省份，市，运营商。无数据区域默认为0。
ip2region.db 结构
生成的ip2region.db文件包含以下四个部分：
1, SUPER BLOCK
2, HEADER INDEX
3, DATA
4, INDEX
生成 ip2region.db 的时候，首先会在首部预留 8 bytes 的SUPER BLOCK 和 8k 的 HEADER INDEX。
再根据ip.merge.txt，依据每一条记录的起始ip, 结束ip和数据，生成一个index block， 前四个字节存储起始ip, 中间四个字节存储结束ip, 后四个字节存储已经计算出的数据地址，并暂存到INDEX区。
当 INDEX 索引区和 DATA 数据区确定下来之后，再把 INDEX 的起始位置存储到 SUPER BLOCK 的前四个字节，结束位置存储到 SUPER BLOCK 的后四个字节。
再把 INDEX 分成大小为 4K 的索引分区，把每个分区起始位置的索引的起始ip和该索引的位置存入一个 header index block, 组成 HEADER INDEX 区域, 最后写入ip2region.db。
具体功能：
INDEX
索引区域，索引元素为 index block (12 字节)， 分成三个部分，起始ip, 结束ip, 数据信息, 每一条 index block 对应 ip.merge.txt 中的一条记录。
数据信息： 前三个字节保存数据地址（DATA中），后一个字节保存数据长度。
每个index block 表示一个ip段的索引。当指定ip 在某个 index block 的起始ip和结束ip中间，即表示命中索引。
再通过 index block 中的数据地址和数据长度，就能从ip2region.db读取对应的地址。
SUPER BLOCK
用来保存 INDEX 的起始地址和结束地址，first index ptr 指向INDEX起始位置的index block， last index ptr 指向最后一个index block的地址。这样查询的时候直接读取superblock 8个字节，就能快速获取 INDEX 索引区域的地址。
HEADER INDEX
HEADER INDEX 区是对 INDEX 区的二级索引， INDEX总长度除以 4K 就是 HEADER INDEX 的实际索引数。
该区域长度为8k, 由 8 bytes 的 header index block 组成。
header index block 前四个字节存储每个4K分区起始位置的index block 的起始ip值，后四个字节指向该index block的地址。
把HEADER INDEX 区定义为8k，可以通过一次磁盘读取读取整个HEADER INDEX 区，然后在内存中进行查询，查询的结果可以确定该ip在INDEX区的某个4k分区内，然后再根据地址一次读取4k index 到内存，再在内存中查询，从而减少磁盘读取的次数。
DATA
保存的数据，数据格式如下：
2163|中国|华南|广东省|深圳市|鹏博士
分别表示 城市ip,国家，区域，省份，城市，运营商
搜索方法
binary搜索
二分法就不多介绍了，步骤：
把ip值通过ip2long方法转为长整型
通过 SUPER BLOCK 拿到INDEX的起始位置和结束位置
相减+1得出index block 总数
采用二分法直接求解，比较 index block 和当前ip的大小，即可找到该ip属于的 index block
拿到该 index block 的后面四个字节， 分别得到数据长度和数据地址
从数据地址读取拿到的所得长度的字节，即是搜索结果
b-tree 搜索
b-tree 搜索用到了 HEADER INDEX，第一步先在 HEADER INDEX 中搜索，再定位到 INDEX 中的某个 4k index分区搜索。步骤：
把ip值通过ip2long 转为长整型
使用二分法在 HEADER INDEX 中搜索，比较得到对应的 header index block
header index block 指向 INDEX 中的一个 4K 分区，所以直接把搜索范围降低到 4K
采用二分法在获取到的 4K 分区搜索，得到对应的 index block
拿到该 index block 的后面四个字节， 分别得到数据长度和数据地址
从数据地址读取拿到的所得长度的字节，即是搜索结果
最新的ip.merge.txt 有122474条记录，并且根据开始ip地址升序排列。
最新版本：1.3
更新如下：
1，数据升级到2017/10/09版本
2，部分国外地址增加了详细定位数据，例如：
4.16.152.0|4.16.159.255|美国|西部|华盛顿州|0|Level3
4.16.160.0|4.16.167.255|美国|东部|马萨诸塞州|波士顿|Level3
4.16.168.0|4.16.175.255|美国|西部|华盛顿州|西雅图|Level3
4.16.176.0|4.16.183.255|美国|东部|佛罗里达州|迈阿密|Level3
4.16.184.0|4.16.191.255|美国|东部|乔治亚州|亚特兰大|Level3
4.16.192.0|4.16.199.255|美国|西部|加利福尼亚州|旧金山|Level3
3，这次升级的数据原因，ip2region.db长大到了2.7M，这个得说明下，原来是1.7M，使用memorySearch的用户得考虑下。
最新版本：2.0
数据升级至2019/10/27版本。增加Nginx的查询插件，README中增加前言：Ip2region重点在于对ip数据存储的设计和各种语言查询客户端的实现的研究和学习，数据完全来源于第三方，所以本项目不保证数据的及时更新，没有也不会有商业版本，用户可以用自己的数据导入到ip2region，利用其查询性能和多语言查询客户端的便利。
项目主页：https://github.com/lionsoul2014/ip2region
ip2region 的ip数据来自纯真和淘宝的ip数据库，每次抓取完成之后会生成 ip.merge.txt， 再通过程序根据这个源文件生成ip2region.db 文件。
ip.merge.txt 中每一行对应一条完整记录，每一条记录由ip段和数据组成，格式如下：
0.0.0.0|0.255.255.255|未分配或者内网IP|0|0|0|0
1.0.0.0|1.0.0.255|澳大利亚|0|0|0|0
1.0.1.0|1.0.3.255|中国|华东|福建省|福州市|电信
从左到右分别表示： 起始ip,结束ip,国家，区域，省份，市，运营商。无数据区域默认为0。
ip2region.db 结构
生成的ip2region.db文件包含以下四个部分：
1, SUPER BLOCK
2, HEADER INDEX
3, DATA
4, INDEX
生成 ip2region.db 的时候，首先会在首部预留 8 bytes 的SUPER BLOCK 和 8k 的 HEADER INDEX。
再根据ip.merge.txt，依据每一条记录的起始ip, 结束ip和数据，生成一个index block， 前四个字节存储起始ip, 中间四个字节存储结束ip, 后四个字节存储已经计算出的数据地址，并暂存到INDEX区。
当 INDEX 索引区和 DATA 数据区确定下来之后，再把 INDEX 的起始位置存储到 SUPER BLOCK 的前四个字节，结束位置存储到 SUPER BLOCK 的后四个字节。
再把 INDEX 分成大小为 4K 的索引分区，把每个分区起始位置的索引的起始ip和该索引的位置存入一个 header index block, 组成 HEADER INDEX 区域, 最后写入ip2region.db。
具体功能：
INDEX
索引区域，索引元素为 index block (12 字节)， 分成三个部分，起始ip, 结束ip, 数据信息, 每一条 index block 对应 ip.merge.txt 中的一条记录。
数据信息： 前三个字节保存数据地址（DATA中），后一个字节保存数据长度。
每个index block 表示一个ip段的索引。当指定ip 在某个 index block 的起始ip和结束ip中间，即表示命中索引。
再通过 index block 中的数据地址和数据长度，就能从ip2region.db读取对应的地址。
SUPER BLOCK
用来保存 INDEX 的起始地址和结束地址，first index ptr 指向INDEX起始位置的index block， last index ptr 指向最后一个index block的地址。这样查询的时候直接读取superblock 8个字节，就能快速获取 INDEX 索引区域的地址。
HEADER INDEX
HEADER INDEX 区是对 INDEX 区的二级索引， INDEX总长度除以 4K 就是 HEADER INDEX 的实际索引数。
该区域长度为8k, 由 8 bytes 的 header index block 组成。
header index block 前四个字节存储每个4K分区起始位置的index block 的起始ip值，后四个字节指向该index block的地址。
把HEADER INDEX 区定义为8k，可以通过一次磁盘读取读取整个HEADER INDEX 区，然后在内存中进行查询，查询的结果可以确定该ip在INDEX区的某个4k分区内，然后再根据地址一次读取4k index 到内存，再在内存中查询，从而减少磁盘读取的次数。
DATA
保存的数据，数据格式如下：
2163|中国|华南|广东省|深圳市|鹏博士
分别表示 城市ip,国家，区域，省份，城市，运营商
搜索方法
binary搜索
二分法就不多介绍了，步骤：
把ip值通过ip2long方法转为长整型
通过 SUPER BLOCK 拿到INDEX的起始位置和结束位置
相减+1得出index block 总数
采用二分法直接求解，比较 index block 和当前ip的大小，即可找到该ip属于的 index block
拿到该 index block 的后面四个字节， 分别得到数据长度和数据地址
从数据地址读取拿到的所得长度的字节，即是搜索结果
b-tree 搜索
b-tree 搜索用到了 HEADER INDEX，第一步先在 HEADER INDEX 中搜索，再定位到 INDEX 中的某个 4k index分区搜索。步骤：
把ip值通过ip2long 转为长整型
使用二分法在 HEADER INDEX 中搜索，比较得到对应的 header index block
header index block 指向 INDEX 中的一个 4K 分区，所以直接把搜索范围降低到 4K
采用二分法在获取到的 4K 分区搜索，得到对应的 index block
拿到该 index block 的后面四个字节， 分别得到数据长度和数据地址
从数据地址读取拿到的所得长度的字节，即是搜索结果
最新的ip.merge.txt 有122474条记录，并且根据开始ip地址升序排列。
最新版本：1.3
更新如下：
1，数据升级到2017/10/09版本
2，部分国外地址增加了详细定位数据，例如：
4.16.152.0|4.16.159.255|美国|西部|华盛顿州|0|Level3
4.16.160.0|4.16.167.255|美国|东部|马萨诸塞州|波士顿|Level3
4.16.168.0|4.16.175.255|美国|西部|华盛顿州|西雅图|Level3
4.16.176.0|4.16.183.255|美国|东部|佛罗里达州|迈阿密|Level3
4.16.184.0|4.16.191.255|美国|东部|乔治亚州|亚特兰大|Level3
4.16.192.0|4.16.199.255|美国|西部|加利福尼亚州|旧金山|Level3
3，这次升级的数据原因，ip2region.db长大到了2.7M，这个得说明下，原来是1.7M，使用memorySearch的用户得考虑下。
最新版本：2.0
数据升级至2019/10/27版本。增加Nginx的查询插件，README中增加前言：Ip2region重点在于对ip数据存储的设计和各种语言查询客户端的实现的研究和学习，数据完全来源于第三方，所以本项目不保证数据的及时更新，没有也不会有商业版本，用户可以用自己的数据导入到ip2region，利用其查询性能和多语言查询客户端的便利。
项目主页：https://github.com/lionsoul2014/ip2region