sortlist

README

介绍

1. 使用skiplist 封装成 sortedlist(MemberScore), 支持并发场景,Range操作O(log(n)+m)
2. 对container/list进行修改，加入score([]byte,可以改成Comparable接口来支持不同类型排序)，支持并发场景，Range操作O(n+m)

使用场景

两者可用于从 redis zset 通过 ZRANGE ** start stop WITHSCORES (O(log(n)+m))或 ZRANGEBYSCORE ** min max WITHSCORES(O(log(n)+m)) 获取的数据放入本地进程SortedList结构中使用，减少网络io，并发请求大时，缓解出现热key的情况；

本地缓存可以选用LRU来进行淘汰；

tips: 写入redis zset的数据是时序append加入到有序集合中的，不能出现更新历史数据的情况，以防顺序变化，导致本地缓存不一致

references

1. wiki: Skip list
2. Skip Lists：A Probabilistic Alternative to Balanced Trees

Documentation

Index

• Constants
• type MemberScore
• type SortedList
  • func NewSortedList() *SortedList
  • func (sl *SortedList) AddBatchForStringScoreMembers(values [][]byte) error
  • func (sl *SortedList) Back() *skiplist.Element
  • func (sl *SortedList) CreateTime() int64
  • func (sl *SortedList) Front() *skiplist.Element
  • func (sl *SortedList) Init() *SortedList
  • func (sl *SortedList) Len() int
  • func (sl *SortedList) Range(start int, stop int) []*skiplist.Element
  • func (sl *SortedList) RangeByScoreAsc(min string, max string) []*skiplist.Element

Examples

• SortedList.RangeByScoreAsc

Constants

const (
	N_INF = "-inf"
	P_INF = "+inf"
)

Types

type MemberScore

type MemberScore struct {
	// contains filtered or unexported fields
}

type SortedList

type SortedList struct {
	// contains filtered or unexported fields
}

func NewSortedList

func NewSortedList() *SortedList

func (*SortedList) AddBatchForStringScoreMembers

func (sl *SortedList) AddBatchForStringScoreMembers(values [][]byte) error

eg: from redis zset zrange get [][]byte

func (*SortedList) Back

func (sl *SortedList) Back() *skiplist.Element

Back returns the last element of list l or nil if the list is empty.

func (*SortedList) CreateTime

func (sl *SortedList) CreateTime() int64

返回链表创建时间

func (*SortedList) Front

func (sl *SortedList) Front() *skiplist.Element

Front returns the first element of list l or nil if the list is empty.

func (*SortedList) Init

func (sl *SortedList) Init() *SortedList

func (*SortedList) Len

func (sl *SortedList) Len() int

func (*SortedList) Range

func (sl *SortedList) Range(start int, stop int) []*skiplist.Element

func (*SortedList) RangeByScoreAsc

func (sl *SortedList) RangeByScoreAsc(min string, max string) []*skiplist.Element

Example

sl := NewSortedList()
memberScore := [][]byte{
	[]byte(`111`), []byte(`1.1`),
	[]byte(`4`), []byte(`1.4`),
	[]byte(`4`), []byte(`1.4`),
	[]byte(`4`), []byte(`1.4`),
	[]byte(`4`), []byte(`1.4`),
	[]byte(`4`), []byte(`1.4`),
	[]byte(`2`), []byte(`1.2`),
	[]byte(`3`), []byte(`1.3`),
	[]byte(`1`), []byte(`1.1`),
}
n := len(memberScore)
err := sl.AddBatchForStringScoreMembers(memberScore)
m := sl.Len()
println(n, m)

if err != nil {
	return
}

res := sl.RangeByScoreAsc("1.0", "1.2")
for _, e := range res {
	fmt.Println(string(e.Value.([]byte)))
}

Output:

1.1
1.1
1.2