XDB-查询过程描述 - Ip2Region社区

在阅读本章节之前我假设您已经阅读了XDB-数据结构的描述并且对XDB的数据结构有了一个基础的认识。搜索过程的深入也自然会让你对整个xdb文件的结构有更清晰的认识，整个搜索过程分为如下四个核心步骤。

第一步、将IP转为字节数组

每个查询binding都有一个类似的parseIP的函数，用于把字符串IP转换为大端字节序的字节数组，IPv4会解析得到一个4字节的数组，IPv6会解析得到一个16字节的数组，例如：

// 把 IPv4 转换为 ip_bytes
var ip_bytes = parseIP("58.251.27.201")
// [58,251,27,201]
// 把 IPv6 转换为 ip_bytes
var ip_bytes = parseIP("240e:3b7:3272:d8d0:db09:c067:8d59:539e")
// [36,14,3.,83,50,114,216,208,219,9,192,103,141,89,83,158]

// 备注：后续代码演示中都将直接使用 ip_bytes 全局变量

第二步、从vector索引中获取二分索引段

第一步确保我们收到的ip_bytes参数是一个字节数组，4或者16字节，二分索引短获取的检索的逻辑很简单，具体如下：

// 常量定义
// 每个 vector 索引项的字节数
var VectorIndexSize = 8
// vector 索引的列数
var VectorIndexCols = 256
// vector 索引段整个的字节数
var VectorIndexLength = 512KiB

// 假设 vectorIndex 为加载的向量索引
// loadVectorIndex api 返回的数据，本质上是一维的 byte 数组。
var vectorIndex = byte[VectorIndexLength]

// 第一个字节的整数 (& 0xFF，确保取值在 0 ~ 255)
var il0 = ip_bytes[0] & 0xFF
// 第二个字节的整数 (& 0xFF，确保取值在 0 ~ 255)
var il1 = ip_bytes[1] & 0xFF

// 计算得到 vector 索引项的开始地址。
// 这里可以对比上述的 vector table 结构进行理解
var idx = il0 * VectorIndexCols * VectorIndexSize + il1 * VectorIndexSize

// 区域二分索引的开始地址
// idx 开始读取 4 个字节，用小端字节序解码得到一个无符号的整数
var sPtr = le_getUint32(vectorIndex, idx)

// 二分区域索引的结束地址
// idx + 4 处读取 4 个字节，用小端字节序解码得到一个无符号的整数
var ePtr = le_getUint32(vectorIndex, idx + 4)

每个 searcher binding 都有加载vectorIndex的 api，本质上是一个一维的byte数组，然后利用IP地址的前两个字节到vectorIndex中快速的得到这个分区的二分索引的开始和结束地址，这也是向量索引的核心，利用一次检索将二分索引分成256 × 256个分区，急剧减少后续二分搜索的扫描范围，从而减少运行时的IO操作数，加速查询过程。

第三步、在二分索引中进行拆半查找

第二步得到了区域二分索引的开始和结束地址之后，就可以在这个区域索引之间使用拆半搜索去得到具体的可以定位地域数据的信息了，该检索过程需要区分 IP 版本，IP 版本的class和对应的实例配置描述如下：

class Version {
    var id;              // 版本序号
    var name;            // 版本序号
    var bytes;           // IP 字节数
    var indexSize;       // 二分索引字节数
    func ipSubCompare;   // IP 比较函数，IPv4 和 IPv6 不一样
}

// IPv4 版本实例
var IPv4 = new Version(4, "IPv4", 4, 14, func(ip1, buff, offset){
    // 为了兼容 2.0 旧版本，待查询 ip1 是大端字节序，buff[offset:ip1.length] 目标 ip 是小端字节序。
    // 具体查询代码请参考你熟悉的语言的 binding 实现。
});
// IPv6 版本实例
var IPv6 = new Version(6, "IPv6", 16, 38, func(ip1, buff, offset){
    // ip1 和 buffer[offset:ip1.length] 都是大端字节序。
    // 具体查询代码请参考你熟悉的语言的 binding 实现。
});

将版本定义为version 参数，具体的拆半搜过过程如下：

// 查询的 IP 版本描述实例，v4 = IPv4，v6 = IPv6
var version

// 二分搜索低位
var l = 0

// 二分搜索高位
// 上第一步得到的结束索引位置减去开始索引位置
// 再除以每个索引的字节大小就是这次搜索要扫描的索引的个数了。
var h = (ePtr - sPtr) / version.indexSize

// 数据长度 / 数据地址
var dataLen = 0, dataPtr = 0

// ip_bytes 字节数 / ip_bytes 字节数的两倍
var bytes = ip_bytes.length, dBytes = ip_bytes.length << 1;

// 开始拆半搜索得到地域数据长度和位置信息
var buff[version.indexSize]
for l < h {
  // 得到中间的索引项
  var m = (l + h) >> 1
  
  // 计算中间索引项的指针地址
  // 在起始地址 sPtr 上加上 m 的相对地址即可
  var p = sPtr + m * version.indexSize
  
  // 从 p 位置开始读取 buff.length 个字节到 buff
  // 得到一个完整的上述描述的二分索引项，不过为了减少不必要的操作，我们是按需要解码
  read(p, buff)
  
  // 比较待查询的 ip_bytes 和 当前二分索引段的开始IP
  if version.ipSubCompare(ip_bytes, buff, 0) < 0 {
      // ip_bytes 比 sip 小，也就是在 p 位置的左边
      h = m - 1
  } else if version.ipSubCompare(ip_bytes, buff, bytes) > 0 {
      // ip_bytes 比 eip 大，也就是在 p 位置的右边
      l = m + 1
  } else {
      // 搜索命中
      // 目标 ip 正好在 sip 和 eip 之间
      // 也就是找到目标 ip 了
      
      // 小端字节序解码 2 字节得到一个无符号的整数即为 地域数据的长度
      dataLen = le_getUint16(buff, dBytes)
      // 小端字节序解码 4 字节得到一个无符号的整数即为 地域数据的地址
      dataPtr = le_getUint32(buff, dBytes + 2)
  }
}

经过上面的搜索过程之后，我们会得到地域数据的长度dataLen和地址dataPtr。

第四步：获取地域信息并完成搜索

通过第三步得到的dataLen和dataPtr我们就可以轻松的得到地域数据了，从dataPtr位置读取dataLen个字节就是地域数据，具体代码如下：

// 将文件指针移动到 dataPtr
handle.seek(dataPtr)

// 当前位置读取 dataLen 个字节
var buff[dataLen]
handle.read(buff)

// 把 buff 解码成 utf-8 字符串返回
return string(buff, "utf-8")

到此整个xdb查询过程就讲解完成了，一开始看XDB-数据结构的时候不一定会完全理解，再结合上述的查询逻辑就可以比较清晰的明白整个xdb的结构了。