如何高效地根据 IP 获得城市?

请设计一个实现方式,可以给某个ip找到对应的省和市,要求效率尽可能的高。

240 2月之前 PHP Redis

答案

可以用 Redis 的有序集合(Sorted Set)实现,将 IP 保存为整形作为集合的score,再根据 score 范围查找。

/**
 * 时间复杂度: O(log(N)+M),N为有序集的基数,M为被结果集的基数。
 */
class Ip
{
    private $redis = null;
    private $key = 'ip';

    public function __construct()
    {
        $this->redis = new Redis();
        $this->redis->connect('127.0.0.1');
    }

    /**
     * 添加城市和最大最小IP,其中最小ip的城市名称前要加“#”作为前缀
     * @param $cityName
     * @param $ip
     */
    public function addIp($cityName, $ip)
    {
        $this->redis->zAdd($this->key, ip2long($ip), $cityName);
    }

    function getCity($ip)
    {
        // 从 score 为IP到正无穷之间获取一个值
        $city = $this->redis->zRangeByScore(
            $this->key,
            ip2long($ip),
            '+inf',
            array('limit' => array(0, 1))
        );

        if ($city) {
            if (strpos($city[0], "#") === 0) {
                return false;
            } else {
                return $city[0];
            }
        } else {
            return false;
        }
    }
}

答案解析

$ip = new Ip();
$ip->addIp('#bj', '1.1.1.0');
$ip->addIp('bj', '1.1.1.254');
$ip->addIp('#sh', '2.2.2.0');
$ip->addIp('sh', '2.2.2.254');

var_dump($ip->getCity('0.0.0.50')); // 内部 $city = ['#bj'], 返回 false
var_dump($ip->getCity('1.1.1.50')); // 内部 $city = ['bj'], 返回 true
var_dump($ip->getCity('2.2.2.50')); // 内部 $city = ['sh'], 返回 true
var_dump($ip->getCity('3.3.3.50')); // 内部 $city = false, 返回 false