利用线段树替代redis的有序集合实现排名

存在的问题

在现有的业务中使用了redis的有序集合对象作为排行榜，但是由于数据本身没有落地，而且用户数据太多，将近一千五百万的数据，导致redis占用内存特别大，需要进行优化。

优化的思路

因为排行榜只需要展示前100名用户数据，所以redis中只需要保存前100的数据，其他数据可以落地到mysql中。单个用户的分数查询，可以利用到mysql的索引，查询效率虽然比redis低，但是也可以接受。但是每个用户的排名，如果使用mysql，那么需要遍历索引树，查询效率必定很低，所以需要使用更高效的方法。

由于分数区间有限，大部分用户都出现在某个区间中，所以这里可以利用哈希表+红黑树，记录每个分数出现的次数，查询用户排名时，只需要将比这个用户分数高的分数对应的次数累加，即可将得出用户的分数排名。该方法对查询的时间复杂度为O(N)，插入的时间复杂度为O（log1），时间复杂度与redis相同，而空间复杂度为reids的千分之一。

优化的方案

对于排名而言，查询的次数远远多于插入的次数，所以必须优化查询方案，最好能接近redis的查询复杂度O(logN)。这里可以考虑线段树，线段树是一种区间查询与更新的数据结构，整棵树类似于二叉树，详细情况不在这里讲解。

普通的线段树，存在两个问题。一使用的是二叉树，如果区间非常大，则树的深度会比较大，递归层次多。二是使用了数组实现，同理如果区间非常大，需要的数组也会占用很大的空间。在业务中，虽然分数基本集中在某个区间，但是分数的最大值将近3亿，所以不能使用普通的线段树实现。在这里我们使用的是多叉树实现，且用指针代替数组，不存在的区间不会占用不会额外占用空间。go版本的实现方法如下。

package utils

import (
    "math"
)

type SegmentTree struct {
    root *stNode
}

type stNode struct {
    value     []int
    count     []int
    childNode []*stNode
}

func NewSegmentTree(maxValue int) *SegmentTree {
    var st = SegmentTree{}
    st.root = st.createNode(0, maxValue)
    return &st
}

func (st *SegmentTree) createNode(left int, right int) *stNode {
    var node = stNode{}
    var size = 128
    if right-left < 127 {
        size = right - left + 1
    }
    node.value = make([]int, size)
    node.count = make([]int, size)
    node.childNode = make([]*stNode, size)

    var skip = int(math.Ceil(float64(right-left) / 127))
    for i := 0; i < size; i++ {
        node.value[i] = skip*i + left
    }
    return &node
}

func (st *SegmentTree) BatchInsert(score int, count int) {
    if st.root == nil {
        return
    }
    var root = st.root
    var size = len(root.value)
    if score > root.value[size-1] { //分数超过最大值，直接返回，超过最大值的排序不再准确，需要重新构建线段树
        root.count[size-1] += count
        return
    }

    var cur = root
    for cur != nil {
        size = len(cur.value)
        for i := size - 2; i >= 0; i-- {
            if score >= cur.value[i] {
                cur.count[i] += count
                if cur.value[i]+1 < cur.value[i+1] && cur.childNode[i] == nil {
                    cur.childNode[i] = st.createNode(cur.value[i], cur.value[i+1])
                }
                cur = cur.childNode[i]
                break
            }
        }
    }
}

func (st *SegmentTree) Insert(score int) {
    st.BatchInsert(score, 1)
}

func (st *SegmentTree) Delete(score int) {
    if st.root == nil {
        return
    }
    var root = st.root
    var size = len(root.value)
    if score > root.value[size-1] { //分数超过最大值，直接返回，超过最大值的排序不再准确，需要重新构建线段树
        root.count[size-1]--
        return
    }

    var cur = root
    for cur != nil {
        size = len(cur.value)
        for i := size - 2; i >= 0; i-- {
            if score >= cur.value[i] {
                cur.count[i]--
                cur = cur.childNode[i]
                break
            }
        }
    }
}

func (st *SegmentTree) Query(score int) int {
    if st.root == nil {
        return -1
    }
    var root = st.root
    var size = len(root.value)
    if score > root.value[size-1] { //分数超过最大值，直接返回，超过最大值的排序不再准确，需要重新构建线段树
        return root.count[size-1]
    }

    var rank = root.count[size-1]
    var cur = root
    for cur != nil {
        size = len(cur.value)
        for i := size - 2; i >= 0; i-- {
            if score >= cur.value[i] {
                cur = cur.childNode[i]
                break
            } else {
                rank += cur.count[i]
            }
        }
    }

    return rank
}

结论

如果在业务中需要用到排名，且分数重复比较多，集中在某个范围，也不需要用户的具体分数，只需要用户的排名，那么可以使用线段树进行优化，减少内存的占用。