java - 如何使范围树实现线程安全

我实现了一个范围树，它支持以递增或递减特定值计数的形式进行更新它还可以查询小于或等于所提供值的值的数目。
范围树已经过测试，可以在单线程环境中工作，但是我想知道如何修改实现，以便可以同时更新和查询它。
我知道一个简单的解决方案是同步访问此树的方法，但我想知道是否有方法可以使rangetree线程本身安全，对性能的影响最小。

public class RangeTree {

    public static final int ROOT_NODE = 0;

    private int[] count;
    private int[] min;
    private int[] max;

    private int levels;
    private int lastLevelSize;

    public RangeTree(int maxValue) {

        levels = 1;
        lastLevelSize = 1;
        while (lastLevelSize <= maxValue) {
            levels++;
            lastLevelSize = lastLevelSize << 1;
        }

        int alloc = lastLevelSize * 2;
        count = new int[alloc];
        min = new int[alloc];
        max = new int[alloc];

        int step = lastLevelSize;
        int pointer = ROOT_NODE;
        for (int i = 0; i < levels; i++) {
            int current = 0;
            while (current < lastLevelSize) {
                min[pointer] = current;
                max[pointer] = current + step - 1;
                current += step;
                pointer++;
            }
            step = step >> 1;
        }
    }

    public void register(int value) {
        int index = lastLevelSize - 1 + value;
        count[index]++;

        walkAndRefresh(index);
    }

    public void unregister(int value) {
        int index = lastLevelSize - 1 + value;
        count[index]--;

        walkAndRefresh(index);
    }

    private void walkAndRefresh(int node) {
        int currentNode = node;
        while (currentNode != ROOT_NODE) {
            currentNode = (currentNode - 1) >> 1;
            count[currentNode] = count[currentNode * 2 + 1] + count[currentNode * 2 + 2];
        }
    }

    public int countLesserOrEq(int value) {
        return countLesserOrEq0(value, ROOT_NODE);
    }

    private int countLesserOrEq0(int value, int node) {
        if (max[node] <= value) {
            return count[node];
        } else if (min[node] > value) {
            return 0;
        }
        return countLesserOrEq0(value, node * 2 + 1) + countLesserOrEq0(value, node * 2 + 2);
    }
}

最佳答案

路易斯·瓦瑟曼是对的，这是个难题。但可能有简单的解决办法。
根据您的更新/读取比率和数据争用情况，使用ReadWriteLock而不是synchronized可能会很有用。
在某些情况下（取决于您的工作负载），另一个可能有效的解决方案是在更新之前复制整个RangeTree对象，然后将引用切换到“实际的”RangeTree。就像在CopyOnWriteArrayList中一样。但这也违反了原子一致性协议，并导致我们最终的一致性。