树形分区设计

均匀分区查询算法的失败是由于积分分布的非均匀性，那么我们自然就会想，能不能按二八定律，把score_range表设计为非均匀区间呢？比如，把低分区划密集一点，10分一个区间，然后逐渐变成100分，1000分，10000分 … 当然，这不失为一种方法，不过这种分法有一定的随意性，不容易把握好，而且整个系统的积分分布会随着使用而逐渐发生变化，最初的较好的分区方法可能会变得不适应未来的情况了。我们希望找到一种分区方法，既可以适应积分非均匀性，又可以适应系统积分分布的变化，这就是树形分区。

我们可以把[0, 1,000,000)作为一级区间；再把一级区间分为两个2级区间[0, 500,000), [500,000, 1,000,000)，然后把二级区间二分为4个3级区间[0, 250,000), [250,000, 500,000), [500,000, 750,000), [750,000, 1,000,000)，依此类推，最终我们会得到1,000,000个21级区间[0,1), [1,2) … [999,999, 1,000,000)。这实际上是把区间组织成了一种平衡二叉树结构，根结点代表一级区间，每个非叶子结点有两个子结点，左子结点代表低分区间，右子结点代表高分区间。树形分区结构需要在更新时保持一种不变量(Invariant)：非叶子结点的count值总是等于其左右子结点的count值之和。

range_tree

以后，每次用户积分有变化所需要更新的区间数量和积分变化量有关系，积分变化越小更新的区间层次越低。总体上，每次所需要更新的区间数量是用户积分变量的log(n)级别的，也就是说如果用户积分一次变化在百万级，更新区间的数量在二十这个级别。在这种树形分区积分表的辅助下查询积分为s的用户排名，实际上是一个在区间树上由上至下、由粗到细一步步明确s所在位置的过程。比如，对于积分499,000，我们用一个初值为0的排名变量来做累加；首先，它属于1级区间的左子树[0, 500,000)，那么该用户排名应该在右子树[500,000, 1,000,000)的用户数count之后，我们把该count值累加到该用户排名变量，进入下一级区间；其次，它属于3级区间的[250,000, 500,000)，这是2级区间的右子树，所以不用累加count到排名变量，直接进入下一级区间；再次，它属于4级区间的…；直到最后我们把用户积分精确定位在21级区间[499,000, 499,001)，整个累加过程完成，得出排名！

虽然，本算法的更新和查询都涉及到若干个操作，但如果我们为区间的from_score和to_score建立索引，这些操作都是基于键的查询和更新，不会产生表扫描，因此效率更高。另外，本算法并不依赖于关系数据模型和SQL运算，可以轻易地改造为NoSQL等其他存储方式，而基于键的操作也很容易引入缓存机制进一步优化性能。进一步，我们可以估算一下树形区间的数目大约为2,000,000，考虑每个结点的大小，整个结构只占用几十M空间。所以，我们完全可以在内存建立区间树结构，并通过user_score表在O(n)的时间内初始化区间树，然后排名的查询和更新操作都可以在内存进行。一般来讲，同样的算法，从数据库到内存算法的性能提升常常可以达到10^5以上；因此，本算法可以达到非常高的性能。

算法特点

优点：结构稳定，不受积分分布影响；每次查询或更新的复杂度为积分最大值的O(log(n))级别，且与用户规模无关，可以应对海量规模；不依赖于SQL，容易改造为NoSQL或内存数据结构。

缺点：算法相对更复杂。

代码：

class TreeNode() {
    var fromScore: Int = _
    var toScore: Int = _
    var count: Int = _
    var right: TreeNode = _
    var left: TreeNode = _

    def this(from: Int, to: Int, c: Int = 0){
        this
        fromScore = from
        toScore = to
        count = c
    }
}

object TreePar {

    def createTreeNode(from: Int, to: Int): TreeNode = {
        if (from > to) return null
        val root = new TreeNode(from, to)
        if (from == to) return root
        val mid = (from & to) + ((from ^ to) >> 1)
        root.left = createTreeNode(from, mid)
        root.right = createTreeNode(mid + 1, to)
        root
    }

    def insertNewScore(root: TreeNode, score: Int): Unit = {
        if (root == null) return
        if (score >= root.fromScore && score <= root.toScore) root.count += 1
        val mid = (root.fromScore & root.toScore) + ((root.fromScore ^ root.toScore) >> 1)
        if (score <= mid) insertNewScore(root.left, score)
        else insertNewScore(root.right, score)
    }

    def deleteOldScore(root: TreeNode, score: Int): Unit = {
        if (root == null) return
        if (score >= root.fromScore && score <= root.toScore) root.count -= 1
        val mid = (root.fromScore & root.toScore) + ((root.fromScore ^ root.toScore) >> 1)
        if (score <= mid) deleteOldScore(root.left, score)
        else deleteOldScore(root.right, score)
    }

    def changScore(root: TreeNode, oldScore: Int, newScore: Int): Unit = {
        deleteOldScore(root, oldScore)
        insertNewScore(root, newScore)
    }

    def getRank(root: TreeNode, score: Int): Int = {
        if (root == null) return -1
        val mid = (root.fromScore & root.toScore) + ((root.fromScore ^ root.toScore) >> 1)
        if (score > mid) return getRank(root.right, score)
        else if (root.right != null) return root.right.count + getRank(root.left, score)
        1
    }

    def printTree(root: TreeNode): Unit = {
        if (root != null) {
            printTree(root.left)
            println(s"(${root.fromScore},${root.toScore})=${root.count}")
            printTree(root.right)
        }
    }

    def main(args: Array[String]): Unit = {
        val root = createTreeNode(1, 10)
        val scores = List(1, 3, 5, 6, 2, 4, 3, 1, 7, 7)
        for (i <- scores.indices) insertNewScore(root, scores(i))
        println("Rank is as follows:")
        printTree(root)
        println("Rank of score=5")
        println(getRank(root, 5))
        println("Alter the score")
        changScore(root, 2, 4)
        printTree(root)
        println(getRank(root, 3))
    }

}