存在的问题

在现有的业务中使用了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
}

结论

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