最新一代文件结构 超高性能解析IP数据库 qqzeng-ip.dat

高性能IP数据库格式 qqzeng-ip.dat

编码：UTF8           字节序：Little-Endian

返回多个字段信息（如：亚洲|中国|香港|九龙|油尖旺|新世界电讯|810200|*|HK|114.17495|22.327115）

------------------------ 文件结构 ---------------------------

//文件头 16字节(4-4-4-4)
[索引区第一条流位置][索引区最后一条流位置][前缀区第一条的流位置][前缀区最后一条的流位置]

//内容区 长度无限制
[地区信息][地区信息]……唯一不重复

//索引区 12字节(4-4-3-1)
[起始IP][结束IP][地区流位置][流长度]

//前缀区 9字节(1-4-4)
[0-255][索引区start索引][索引区end索引]

------------------------ 文件结构 ---------------------------

优势：索引区分为[起始IP][结束IP][地区偏移][长度],减少多级偏移跳转步骤和长度的解析,提高效率;
根据ip第一位字节作为前缀,解析出以这个数字为前缀的第一个索引和最后一个索引,缩小查询区间,
然后在这区间再用二分查找快速查找到对应区间,效率提高几个等级

压缩：原版txt为15M,生成这种dat结构为2.45M

性能：每秒解析300多万         

对比：相比其他dat更简洁更高效

创建：qqzeng-ip 于 2015-08-01

代码：https://github.com/zengzhan/qqzeng-ip

public class IPSearch
{
    private Dictionary<uint, PrefixIndex> prefixDict;
    private byte[] indexBuffer;
    private byte[] data;
    long firstStartIpOffset;//索引区第一条流位置
    long lastStartIpOffset;//索引区最后一条流位置
    long prefixStartOffset;//前缀区第一条的流位置
    long prefixEndOffset;//前缀区最后一条的流位置
    long ipCount;       //ip段数量
    long prefixCount;  //前缀数量

    /// <summary>
    /// 初始化二进制dat数据
    /// </summary>
    /// <param name="dataPath"></param>
    public IPSearch(string dataPath)
    {
        using (FileStream fs = new FileStream(dataPath, FileMode.Open, FileAccess.Read, FileShare.Read))
        {
            data = new byte[fs.Length];
            fs.Read(data, , data.Length);
        }

        firstStartIpOffset = BytesToLong(data[], data[], data[], data[]);
        lastStartIpOffset = BytesToLong(data[], data[], data[], data[]);
        prefixStartOffset = BytesToLong(data[], data[], data[], data[]);
        prefixEndOffset = BytesToLong(data[], data[], data[], data[]);

        //prefixCount 不固定为256 方便以后*定制 国内版  国外版 全球版 或者某部分 都可以

        ipCount = (lastStartIpOffset - firstStartIpOffset) /  + ; //索引区块每组 12字节
        prefixCount = (prefixEndOffset - prefixStartOffset) /  + ; //前缀区块每组 9字节

        //初始化前缀对应索引区区间
        indexBuffer = new byte[prefixCount * ];
        Array.Copy(data, prefixStartOffset, indexBuffer, , prefixCount * );
        prefixDict = new Dictionary<uint, PrefixIndex>();
        for (var k = ; k < prefixCount; k++)
        {
            int i = k * ;
            uint prefix = (uint)indexBuffer[i];
            long start_index = BytesToLong(indexBuffer[i + ], indexBuffer[i + ], indexBuffer[i + ], indexBuffer[i + ]);
            long end_index = BytesToLong(indexBuffer[i + ], indexBuffer[i + ], indexBuffer[i + ], indexBuffer[i + ]);
            prefixDict.Add(prefix, new PrefixIndex() { prefix = prefix, start_index = start_index, end_index = end_index });
        }

    }

    public static uint IpToInt(string ip,out uint prefix)
    {
        byte[] bytes = IPAddress.Parse(ip).GetAddressBytes();
        prefix = (uint)bytes[];
        return (uint)bytes[] + (((uint)bytes[]) << ) + (((uint)bytes[]) << ) + (((uint)bytes[]) << );
    }

    public static string IntToIP(uint ip_Int)
    {
        return new IPAddress(ip_Int).ToString();
    }

    /// <summary>
    /// 根据ip查询多维字段信息
    /// </summary>
    /// <param name="ip">ip地址（123.4.5.6）</param>
    /// <returns>亚洲|中国|香港|九龙|油尖旺|新世界电讯|810200|*|HK|114.17495|22.327115</returns>
    public string Query(string ip)
    {
        uint ip_prefix_value;
        uint intIP = IpToInt(ip,out ip_prefix_value);
        uint high = ;
        uint low = ;
        uint startIp = ;
        uint endIp = ;
        uint local_offset = ;
        uint local_length = ;

        if (prefixDict.ContainsKey(ip_prefix_value))
        {
            low = (uint)prefixDict[ip_prefix_value].start_index;
            high = (uint)prefixDict[ip_prefix_value].end_index;
        }
        else
        {
            return "";
        }

        uint my_index = low == high? low : BinarySearch(low, high, intIP);          

        GetIndex(my_index, out startIp, out endIp, out local_offset, out local_length);

        if ((startIp <= intIP) && (endIp >= intIP))
        {
            return GetLocal(local_offset, local_length);
        }
        else
        {
            return "";
        }

    }
    /// <summary>
    /// 二分逼近算法
    /// </summary>
    public uint BinarySearch(uint low, uint high, uint k)
    {
        uint M = ;
        while (low <= high )
        {
            uint mid = (low + high) / ;

            uint endipNum = GetEndIp(mid);
            if (endipNum >= k)
            {

                M = mid;
                if (mid == )
                {
                    break;   //防止溢出
                }
                high = mid - ;
            }
            else
                low = mid + ;
        }
        return M;
    }
    /// <summary>
    /// 在索引区解析
    /// </summary>
    /// <param name="left">ip第left个索引</param>
    /// <param name="startip">返回开始ip的数值</param>
    /// <param name="endip">返回结束ip的数值</param>
    /// <param name="local_offset">返回地址信息的流位置</param>
    /// <param name="local_length">返回地址信息的流长度</param>
    private void GetIndex(uint left, out uint startip, out uint endip, out uint local_offset, out uint local_length)
    {
        long left_offset = firstStartIpOffset + (left * );
        startip = BytesToLong(data[left_offset], data[ + left_offset], data[ + left_offset],data[ + left_offset]);
        endip = BytesToLong(data[+left_offset], data[ + left_offset], data[ + left_offset], data[ + left_offset]);
        local_offset = (uint)data[ + left_offset] + (((uint)data[ + left_offset]) << ) + (((uint)data[ + left_offset]) << );
        local_length = (uint)data[ + left_offset];
    }
    /// <summary>
    /// 只获取结束ip的数值
    /// </summary>
    /// <param name="left">索引区第left个索引</param>
    /// <returns>返回结束ip的数值</returns>
    private uint GetEndIp(uint left)
    {
        long left_offset = firstStartIpOffset + (left * );
        return BytesToLong(data[ + left_offset], data[ + left_offset], data[ + left_offset], data[ + left_offset]);

    }

    /// <summary>
    /// 返回地址信息
    /// </summary>
    /// <param name="local_offset">地址信息的流位置</param>
    /// <param name="local_length">地址信息的流长度</param>
    /// <returns></returns>
    private string GetLocal(uint local_offset, uint local_length)
    {
        byte[] buf = new byte[local_length];
        Array.Copy(data, local_offset, buf, , local_length);
        return Encoding.UTF8.GetString(buf, , (int)local_length);

    }

    /// <summary>
    /// 字节转整形 小节序
    /// </summary>
    /// <param name="a"></param>
    /// <param name="b"></param>
    /// <param name="c"></param>
    /// <param name="d"></param>
    /// <returns></returns>
    private uint BytesToLong(byte a, byte b, byte c, byte d)
    {
        return ((uint)a << ) | ((uint)b << ) | ((uint)c << ) | ((uint)d << );
    }
}

/*
（调用例子）：
IPSearch finder = new IPSearch("qqzeng-ip.dat");
string result = finder.Query("1.2.3.4");
--> result="亚洲|中国|香港|九龙|油尖旺|新世界电讯|810200|*|HK|114.17495|22.327115"
*/

public class PrefixIndex
{
    public uint prefix { get; set; }
    public long start_index { get; set; }
    public long end_index { get; set; }
}