背景

接触过ip库查询的人，可能都听说过ip2region这个开源的方案，其通过查询一些外部数据源形成自己的ip段信息，再通过生成索引库，从而提供ip信息的查账，可惜的是作者一直未提供Ipv6的查询方案，在ipv6越加重要的现在，着实有些可惜。所以今天来说下在Ip2region的基础上实现支持ipv6的实现方案。

ip2region的原理

ip2region分三个部分：

源数据转变成ip2region db 文件的过程
ip2region 的结构
搜索方法

此处跳过db文件生成的过程，只讲讲结构和搜索方案

ip2region.db 结构

生成的ip2region.db文件包含以下四个部分：

1, SUPER BLOCK

2, HEADER INDEX

3, DATA

4, INDEX

ip2region结构

生成 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 的后面四个字节，分别得到数据长度和数据地址
从数据地址读取拿到的所得长度的字节，即是搜索结果

ip2region支持ipv6

如何支持Ipv6

ip文本生成long

实现ipv4检索的时候，最主要的一个步骤就是将ip转成long, 通过该值进行二分查找或b-tree搜索。

ipv6也是可以转为long值的，但是因为long值的范围问题，无法全用正数表示，所以生成的long值带有符号，所以在long值的比较时会有一些不同。

ip to long 我使用了
sun.net.util.IPAddressUtil

private byte[] getIpBytes(String ip) throws IpFormatException {
    byte[] ipBytes;
    if (dbType == DbType.IPV4) {
        ipBytes = IPAddressUtil.textToNumericFormatV4(ip);
    } else {
        ipBytes = IPAddressUtil.textToNumericFormatV6(ip);
    }
    if (ipBytes == null) {
        throw new IpFormatException(String.format("ip [%s] format error for %s", ip, dbType));
    }
    return ipBytes;
}

ipv4的 byte 数组长度为4，ipv6的数组长度为16, 在初始化库时，可以根据提供的参数对长度参数进行初始化。

ipBytesLength = dbType == DbType.IPV4 ? 4 : 16;

long值的比较

因为带有符号位，所以在比较时，需要分类处理。

/**
 * @param bytes1
 * @param bytes2
 * @param length 检查前多少位的byte
 * @return
 */
private static int compareBytes(byte[] bytes1, byte[] bytes2, int length) {
    for (int i = 0; i < bytes1.length && i < bytes2.length && i < length; i++) {
        if (bytes1[i] * bytes2[i] > 0) {
            if (bytes1[i] < bytes2[i]) {
                return -1;
            } else if (bytes1[i] > bytes2[i]) {
                return 1;
            }
        } else if (bytes1[i] * bytes2[i] < 0) {
            // 异号时，负数的大
            if (bytes1[i] > 0) {
                return -1;
            } else {
                return 1;
            }
        } else if (bytes1[i] * bytes2[i] == 0 && bytes1[i] + bytes2[i] != 0) {
            // 0 最小
            if (bytes1[i] == 0) {
                return -1;
            } else {
                return 1;
            }
        }
    }
    if (bytes1.length >= length && bytes2.length >= length) {
        return 0;
    } else {
        if (bytes1.length > bytes2.length) {
            return 1;
        } else if (bytes1.length == bytes2.length) {
            return 0;
        } else {
            return -1;
        }
    }
}

缺点改进

在使用过程中，遇到的最大的问题就是需要生成DB时自己指定Index区域的大小，而该区域的大小适合数据文件大小息息相关的，也就是说，如果文件很小但是你的index给的过大，就会导致空间浪费；如果文件很大，但是你给的index区域过小，会导致index数据会覆盖data区（ps: 生成过程中，是先根据预先设定的index区域大小预留空间，写完data后会再写index, 由于index的区域是在data前面的，所以如果index给的小了，会导致index的尾部数据会覆盖data区域），引起的现象就是查询结果乱码。

为了避免该现象的产生，做了如下改进：

加载数据时先计算data区域的大小。
根据data区域的大小，计算需要的index空间

代码

当前代码已经公开，详情可见：

https://github.com/amazingWu/ip2region-v6

使用

生成库文件

确保你安装好了java环境（不玩Java的童鞋就自己谷歌找找拉，临时用一用，几分钟的事情）
cd到${ip2region_root}/maker/java，然后运行如下命令：

java -jar ip2region-maker-{version}-with-dependencies.jar -s 文本数据文件 -f 生成的ip2region.db文件名称或完整目录+名称 -t ipv6|ipv4

获取生成的ip2region.db文件覆盖原来的ip2region.db文件即可
默认的ip2region.db文件生成命令:

cd ${ip2region_root}/java/
java -jar ../../ip2region-maker-1.0-SNAPSHOT-with-dependencies.jar -s ipv6_merge.txt -f ipv6_netease.db -t ipv6
# 会看到一大片的输出

使用库文件

提供了如下两种构造方法进行初始化：

/**
 * construct class
 *
 * @param dbFile
 * @throws FileNotFoundException
 */
public DbSearcher(String dbFile, QueryType queryType) throws IOException {
    this.queryType = queryType;
    raf = new RandomAccessFile(dbFile, "r");
    switch (queryType) {
        case MEMORY:
            dbBinStr = new byte[(int) raf.length()];
            raf.seek(0L);
            raf.readFully(dbBinStr, 0, dbBinStr.length);
            raf.close();
            //initialize the global vars
            initMemoryOrBinaryModeParam(dbBinStr, dbBinStr.length);
            break;
        case BTREE:
            initBtreeModeParam(raf);
            break;
        case BINARY:
            raf.seek(0L);
            byte[] superBytes = new byte[DbConstant.SUPER_PART_LENGTH];
            raf.readFully(superBytes, 0, superBytes.length);
            //initialize the global vars
            initMemoryOrBinaryModeParam(superBytes, raf.length());
            break;
        default:
            break;
    }
}

/**
 * you can only use memory query when using this constructor
 * Thanks to the issue from Wendal at https://gitee.com/lionsoul/ip2region/issues/IILFL
 *
 * @param bytes
 */
public DbSearcher(byte[] bytes) {
    this.dbBinStr = bytes;
    this.dbBinStr = bytes;
    this.queryType = QueryType.MEMORY;
    initMemoryOrBinaryModeParam(bytes, bytes.length);
}

检索：

/**
 * get the region through the ip address with memory or binary or btree search algorithm
 *
 * @param ip
 * @return DataBlock
 * @throws IOException       using binary search or btree search may occurs IOException
 * @throws IpFormatException throw IpFormatException when ip format is not right
 */
public String search(String ip) throws IpFormatException, IOException {
    byte[] ipBytes = getIpBytes(ip);
    DataBlock dataBlock = null;
    switch (queryType) {
        case MEMORY:
            dataBlock = memorySearch(ipBytes);
            break;
        case BINARY:
            dataBlock = binarySearch(ipBytes);
            break;
        case BTREE:
            dataBlock = bTreeSearch(ipBytes);
            break;
        default:
            break;
    }
    if (dataBlock == null) {
        return null;
    } else {
        return dataBlock.getRegion();
    }

}

原文链接：https://blog.csdn.net/u013668852/article/details/111468891

背景