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

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

第一步、将IP转为整数

计算机里面任何数据都可以转换为数字，这是一句废话？整个数字电路就是基于二进制的，每个查询binding都有一个类似的ip2long的函数，用于把字符串IP转换为整数IP，IPv4本身就是一个4字节的整数，IP的字符串输出形式就是四个字节转换成整数然后用点串接起来：

var ip = "120.24.78.129"
// 把字符串 ip 按照 . 拆分，此处略过错误检测
var ps = ip.split(".")
// 把切分得到四个数字转换成整数，然后进行位运行就好。
var ip_int = (toInt(ps[0]) << 24) | (toInt(ps[1]) << 16) | (toInt(ps[2]) << 8) | toInt(ps[3]))

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

第一步确保我们收到的参数是一个整数，至少是4字节，例如java这类没有无符号概念的语言需要使用8字节的长整，不然会出现溢出的情况。vector索引检索的逻辑很简单，具体如下：

// 常量定义
// 每个 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_int >> 24) & 0xFF
// 第二个字节的整数 (&0xFF，确保取值在 0 ~ 255)
var il1 = (ip_int >> 16) & 0xFF

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

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

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

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

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

第二步得到了区域二分索引的开始和结束地址之后，就可以在这个区域索引之间使用拆半搜索去得到具体的可以定位地域数据的信息了，具体的拆半搜过过程如下：

// 常量定义
// 二分索引项的字节数
var SegmentIndexSize = 14

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

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

// 开始拆半搜索得到地域数据长度和位置信息
var buff[SegmentIndexSize]
for l < h {
  // 得到中间的索引项
  var m = (l + h) >> 1
  
  // 计算中间索引项的指针地址
  // 在起始地址 sPtr 上加上 m 的相对地址即可
  var p = sPtr + m * SegmentIndexSize
  
  // 从 p 位置开始读取 SegmentIndexSize = 14 个字节到 buff
  // 得到一个完整的上述描述的二分索引项，不过为了减少不必要的操作
  // 我们是按需要解码，此处 buff 为 p 开始的 14 个 byte 的数据
  read(p, buff)
  
  // 前面 4 个字节是起始 IP
  var sip = getInt(buff, 0) 
  if ip_int < sip {
      // 目标比 sip 小，也就是在 p 位置的左边
      h = m - 1
  } else {
      // 4 ~ 7 之间的 4 个字节是结束 IP 地址
      var eip = getInt(buff, 4)
      if ip_int > eip {
          // 目标 ip 比 eip 大，也就是在 p 位置的右边
          l = m + 1
      } else {
          // 搜索命中
          // 目标 ip 正好在 sip 和 eip 之间
          // 也就是找到目标 ip 了
          
          // 8 ~ 10 两个字节是地域数据的长度
          dataLen = getShort(buff, 8)
          // 10 ~ 13 的 4 个字节是地域数据的地址
          dataPtr = getInt(buff, 10)
      }
  }
}

经过上面的搜索过程之后，我们会得到地域数据的长度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-V4数据结构的时候不一定会完全理解，再结合上述的查询逻辑就可以比较清晰的明白整个xdbV4 的结构了。