二叉树实现快速查找数字所在区间

背景

通过IP地址查询ip地址所属省市，存在这样的数据

3748137472,3748137727,223.104.10.0,223.104.10.255,中国,江西,,,移动,330000,,城域网
3748137728,3748137983,223.104.11.0,223.104.11.255,中国,陕西,,,移动,710000,,移动网络
3748137984,3748138239,223.104.12.0,223.104.12.255,中国,云南,,,移动,650000,,移动网络
3748138240,3748138495,223.104.13.0,223.104.13.255,中国,河北,,,移动,050000,,移动网络
3748138496,3748138751,223.104.14.0,223.104.14.255,中国,山西,,,移动,030000,,移动网络
3748138752,3748138815,223.104.15.0,223.104.15.63,中国,内蒙古,,,移动,010000,,移动网络
3748138816,3748138847,223.104.15.64,223.104.15.95,中国,内蒙古,,,移动,020000,,移动网络

通过将IP地址翻译成数字比较数字所属区间找到对应的省市信息，单个或多个查询都没问题，如果批量查询上万个，对oracle的性能是很大的考验，于是想到了缓存，但是普通的map结构似乎不能满足，于是想到了二叉树，基本逻辑是用二分法将数据排序，取中间的为根节点，向左向右取中间节点为左右子节点构建大树，然后按照二叉树逻辑检索，测试了一下性能还可以，记录一下。

package org.example.util;
 
import java.util.ArrayList;
import java.util.Date;
import java.util.List;
import java.util.Random;
 
public class CacheRange {
 
    public static void main(String[] args) {
        Date begin = new Date();
        long max = 4294967296l;
        long min =0;
        Random random = new Random();
        List nodes = new ArrayList<>();
 
        while(min < max){
            int increment = random.nextInt(1000);
 
            Node node = new Node(min,min+increment);
            nodes.add(node);
            min = min+increment;
        }
        Date now = new Date();
        System.out.println(nodes.size()+" cost "+(now.getTime()-begin.getTime()));
        int maxSize = nodes.size()-1;
        int minSize = 0;
        int curSize = (maxSize-minSize)/2;
        Node root = nodes.get(curSize);
        root.setLeft(getMidNode(nodes,curSize,minSize,true));
        root.setRight(getMidNode(nodes,maxSize,curSize,false));
 
        System.out.println(root);
        now = new Date();
        System.out.println("setMidNode cost "+(now.getTime()-begin.getTime()));
 
        long idx = 29496729l;
        for(int i=0;i<100;i++){
            Node node = root.indexNode(idx);
            System.out.println(idx+"@node is "+node);
            idx = idx + random.nextInt(1000);
        }
        now = new Date();
        System.out.println(nodes.size()+" cost "+(now.getTime()-begin.getTime()));
    }
 
    public static Node getMidNode(List nodes, int maxSize, int minSize,boolean isleft){
        int curSize = (maxSize-minSize)/2+minSize;
        Node root;
        if(maxSize-minSize <= 1){//这里考虑2个元素、1个元素情况
            if(isleft){
                root = nodes.get(minSize);
            }else{
                root = nodes.get(maxSize);
            }
            if(root.isExist){
                return null;
            }
            return root;
        }else{
            root = nodes.get(curSize);
            if(null == root || root.isExist){
                return null;
            }
            root.setLeft(getMidNode(nodes,curSize,minSize,true));
            root.setRight(getMidNode(nodes,maxSize,curSize,false));
            return root;
        }
    }
 
    static class Node{
        long begin = 0;
        long end = 0;
        Node left;
        Node right;
        boolean isExist =false;
        public Node(long begin,long end){
            this.begin=begin;
            this.end = end;
        }
 
        public void setLeft(Node left){
            this.left=left;
        }
        public Node getLeft(){
            return this.left;
        }
        public void setRight(Node right){
            this.right=right;
        }
        public Node getRight(){
            return this.right;
        }
 
        public void setIsExist(){
            this.isExist = true;
        }
 
        public Node indexNode(long index){
            if(this.begin <= index && this.end >= index){
                return this;
            }
            if(this.begin > index){
                return this.left.indexNode(index);
            }
            if(this.end < index){
                return this.right.indexNode(index);
            }
 
            return null;
        }
 
        @Override
        public String toString(){
            return this.begin+" - "+this.end;
        }
    }
}

测试的结果如下：

8597917 cost 2347
2146951032 - 2146951635
setMidNode cost 2461
29496729@node is 29496411 - 29497393
29497062@node is 29496411 - 29497393
29497953@node is 29497466 - 29498096

......
29544412@node is 29544398 - 29544647
29545207@node is 29544647 - 29545591
8597917 cost 2462

Process finished with exit code 0

树结构