Skip List

Posted on Jun 21, 2018

跳表是一种建立在普通链表基础上的概率数据结构，为什么说是概率呢，因为跳表会根据概率在原始链表上构建后续的链表层，每个额外的链表层包含的元素数量更少，但每个元素都是原始链表中已经拥有的，这使得跳表在搜索时不用像链表一样一个一个元素的寻找，而是跳过一些元素，这就是跳表名字的由来，正是因为略过了一些元素，所以大大增加了搜索的速度。

SkipList

利用跳表可以构建 kv 数据库的索引，例如 leveldb 中的索引就是利用跳表来构建的，跳表相对其他索引数据结构例如红黑树，b树等有实现相对简单，但查询效率高的特点，其空间复杂度为 O(n) ，时间复杂度为 O(logn) 。

跳表的组成元素

与链表类似，跳表也是由一系列节点组成，每个节点我们用 Element 结构体表示，每个节点会存储一个 kv 对，除了 kv 对之外，还包含一个 elementNode 结构体，该结构体其实就是一个指针数组，在单向链表中，指针有且只有一个，在跳表中，可以存在多个指向后续节点的指针，用于遍历时加速跳跃使用，这个指针数组是跳表的核心，使用 next []*Element 表示。

在表示完跳表的基本元素之后，我们还需要考虑一个完整跳表的数据结构，类与普通的链表类似，我们需要一个跳表头，这里用 elementNode 表示，由于跳表在构建时新元素的高度是不确定的，所以我们需要一个 rand.Source 帮助我们决定元素的高度，并限制高度小于最高高度 maxLevel ，这里整个跳表的质量与随机性有相当大的关系，构建得到的跳表随机性越强，搜索速度越快。

还有我们需要 prevNodesCache []*elementNode 来存储被查找节点的之前的节点，这个刚开始理解起来有一点复杂，因为被查找节点每一层的前一个元素都是不同的，每一个之前的元素可以用一个 *elementNode 来表示，由于每个节点可能存在多层指针，所以这里用一个数组来表示 []*elementNode 。

type elementNode struct {
    next []*Element
}

type Element struct {
    elementNode
    key   float64
    value interface{}
}

type SkipList struct {
    elementNode
    maxLevel       int
    Length         int
    randSource     rand.Source
    mutex          sync.RWMutex
    prevNodesCache []*elementNode
}

func New(maxLevel int) *SkipList {
    if maxLevel < 1 || maxLevel > 64 {
        panic("max level should be less than 64 and greater than 1")
    }
    return &SkipList{
        elementNode: elementNode{next: make([]*Element, maxLevel)},
        maxLevel: maxLevel,
        randSource: rand.New(rand.NewSource(time.Now().UnixNano())),
        prevNodesCache: make([]*elementNode, maxLevel),
    }
}

跳表的基本操作

在插入和删除特定节点时，我们需要获取该节点之前的所有元素节点， getPrevElementNodes 从跳表的头节点（ list.elementNode ）出发，并从最高层开始，确定 key 对应的元素在该层对应的前一个elementNode ，然后存储在 prevNodesCache 中（ prevs[i] = prev ），这样一直查找直到最底层。

func (list *SkipList) getPrevElementNodes(key float64) []*elementNode {
    var prev *elementNode = &list.elementNode
    var next *Element

    prevs := list.prevNodesCache

    for i := list.maxLevel - 1; i >=0; i-- {
        next = prev.next[i]
        for next != nil && key > next.key {
            prev = &next.elementNode
            next = next.next[i]
        }
        prevs[i] = prev
    }
    return prevs
}

func (list *SkipList) randLevel() (level int) {
    return list.randSource.Intn(list.maxLevel)
}

Get

Get 方法的本质就是一个走楼梯的过程，但是这里每个阶梯的高度和宽度并非确定，开始从楼梯的最高层出发（ i := list.maxLevel - 1 ），每次对前方同一层的阶梯（ next = prev.next[i] ）进行试探，如果前方阶梯不为空（ next != nil ），且符合特定要求（ key > next.key ）则继续在这一层走，否则直接进入下一层（ i-- ），直到找到为止，最后判断此阶梯不为空（ next != nil ）且该阶梯保存的值和要找的值相同时，返回该阶梯。

func (list *SkipList) Get(key float64) *Element {
    list.mutex.Lock()
    defer list.mutex.Unlock()

    var prev *elementNode = &list.elementNode
    var next *Element

    for i := list.maxLevel - 1; i >= 0; i-- {
        next = prev.next[i]

        for next != nil && key > next.key {
            prev = &next.elementNode
            next = next.next[i]
        }
    }

    if next != nil && next.key <= key {
        return next
    }

    return nil
}

Set

Set 方法需要使用之前的 getPrevElementNodes 来获取对应 key 之前的元素，如果该元素对应的 key 已经存在，则改变其 value 之后返回，如果不存在，则构建一个新的节点，然后将自己之前的节点的指针和自己之后节点的指针相连，使其前节点指向自己，使自己指向后面的节点。

func (list *SkipList) Set(key float64, value interface{}) *Element {
    list.mutex.Lock()
    defer list.mutex.Unlock()

    var element *Element
    prevs := list.getPrevElementNodes(key)
    if element = prevs[0].next[0]; element != nil && element.key <= key {
        element.value = value
        return
    }
    element = &Element {
        elementNode: elementNode{
            next: make([]*Element, list.randLevel()),
            key: key,
            value: value,
        }
    }
    for i := range element.next {
        element.next[i] = prevs[i].next[i]
        prevs[i].next[i] = element
    }
    list.Length++
    return element
}

Remove

Remove 方法也需要使用 getPrevElementNodes 方法，使自己前面的节点不指向该元素而是指向该元素后面的元素。

func (list *SkipList) Remove(key float64) *Element {
    list.mutex.Lock()
    defer list.mutex.Unlock()
    prevs := list.getPrevElementNodes(key)

    if element := prevs[0].next[0]; element != nil && element.key <= key {
        for k, v := range element.next {
            prevs[k].next[k] = v
        }
        list.Length--
        return element
    }
    return nil
}