Golang跳表

跳表简介

相信大家都知道排行榜，在很多场景里都需要用到排行榜功能，尤其是游戏中！之前在了解排行榜实现机制的时候，在网上看得最多的答复便是使用redis的有序集合实现。于是深入了解了一下redis中的有序集合。

redis中的有序结合(sorted set)是一种线性结构，底层是用有序链表实现的，但是对链表增加的“索引”，并且对索引进行了分层，跳表每层散落的节点数不同，查找过程中通过索引向下层跳转，最终落到最下层的数据链中，这样做的目的是通过空间换时间来获取更高的效率，故称之为跳跃表（跳表）。

网上有很多关于跳表图文并茂的原理解析，这里便不再展开。

通过阅读redis中sorted set部分的源码，自己用golang实现了一部分功能，核心代码翻译自redis源码。

代码在这里

Usage Example

package main

import (
	"fmt"
	"github.com/pyihe/go-skipList"
)

func main() {
	ss := go_skipList.NewSkipList()
	ss.InsertByEle("k1", 10, nil)
	ss.InsertByEleArray("k2", 10.1, "this is k2", "k3", 1.1, nil)
	nodes, err := ss.GetElementByRank(1)
	if err != nil {
		//handle err
	}

	//output: mem: k2, score: 10.1, data: this is k2
	fmt.Printf("mem: %s, score: %v, data: %v\n", nodes[0].Name(), nodes[0].Score(), nodes[0].Data())
}

Thanks!