从零实现LevelDB 2. 从一道leetcode开始

#C++##golang##项目##基础架构工程师##数据库##牛客创作赏金赛##软件开发2024笔面经#

在本节，我们将会了解：

1. 跳跃链表
2. 实现跳跃链表

在leetcode 1206中，要求实现一个数据结构，跳表，而这也是今天本文的主角。

跳表是leveldb中一个重要的数据结构，在本节，将以通过leetcode 1206为主线实现跳表,并在最后做一点小小的修改，以便运用于我们最终实现的leveldb。

本节完整代码可查看build_level_from_scratch——skiplist实现。

1.跳表介绍

相信每个人在刚开始《数据结构》时，都会学到链表跟数组的优缺点。

链表具有插入、删除方便的优点，但无法做到随机访问，因此对于有序链表无法使用二分查找等加速查找的方法；数组虽插入、删除效率低，但可以做到随机访问，对于有序数组可以使用二分查找等方法；

那么，一个问题不禁来到了人的心头，如何实现一个数据结构，既能插入、删除方便，又能够做到随机访问或近似随机访问呢？

这就引入我们今天的主角，跳表。

跳跃表(简称跳表)是1989年美国计算机科学家William Pugh在论文《Skip lists: a probabilistic alternative to balanced trees》发明的一种数据结构。

William Pugh通过对链表进行改造，以空间换时间，让其也具有近似随机访问的特点。

改造后的链表，称之为跳表。跳表既有插入、删除方便的优点，又具备近似随机访问优势。

下面将对跳表进行介绍。

1.1 跳表的思想

在传统的链表中，如图1所示，我们要查找任何元素,哪怕该链表是有序的，也只能从头到尾一个个查找，无法使用二分查找等方法加速查找，查找的时间复杂度为O(n)。

那么，如果我们加上辅助索引的话，如图2，每两个元素建立一个新的索引节点，组成一个2层的单向链表，这种结构能不能加速查找呢？

答案是可以的！

假如我们要查找25这个节点，如果是图1结构这种单层的链表，我们需要从第一个节点找到第九个节点才能找到，查找次数为9次。

而对于图2具有一层辅助索引的链表，我们可以现在第二层上进行查找，查找路径为6->9->17->21->26，发现26大于25，返回到21，并下沉到第一层，然后继续向右查找，找到25，返回结果，此时查找次数为6次。

以上便是跳表的基本思想，由于第2层的节点数量仅有第1层的一半，理论上查找的时间复杂度由O(N) 降低到了 O(N/2)，但由于第2层中的数据并不完备，因此当我们发现所寻找到目标值处在该层中某两个节点的间隙之内时，则需要顺延左边界往下退化到下一层，进一步完成目标值的搜索。

在实际跳表的实现中，我们一般会建立多层的辅助索引，以便更加的找到元素。如下图所示。

1.2 基于概率决定层数

在上图中，高一层的节点数总是相邻下一层节点数目的一半，且采取了每隔一个节点建立一个索引的策略，但在实际中，如果严格维持这种均匀间隔的索引建立策略，其维护代价十分昂贵。

以图1为例，假如我们要删除元素9，那么为了严格保证这种均匀间隔的索引的规定，那么几乎后续的所有节点都要重新维护。

因此在工程实现上，并不依据严格的间隔来建立索引，而是采用基于概率决定层级，以确保每个高层的节点个数是相邻下一层数量的一半。

在插入节点时，我们会对其层数进行随机取值，保证其建立第2层的概率为1/2，第3层的概率为1/4，第4层的概率为1/8，以此类推。这样，根据大数定律，在数据足够多的情况下，第2层的节点数目近似第1层的一半，第3层的节点数目近似于第2层的一半。

2 跳表的操作与实现

2.1 跳表的定义

跳表的由一系列节点，节点定义如下。

type Node struct {
	key   int
	next  []*Node
}

其中，key代表节点的值，next则是代表索引，以图三为例，节点3的key为3，next长度为1，其中next[0]指向节点6；节点6的key为6，next长度为2，其中next[0]指向节点7，next[1]指向节点9。

对于跳表而言，我们只需要定义其高度和头节点，通过头节点则可以找到后续的所有节点。

type Skiplist struct {
	maxHeight int
	head      *Node
}

1.2.1 查找

func (list *Skiplist) Search(key int) bool {
	x, _ := list.findGreaterOrEqual(key)
	if x != nil && x.key == key {
		return true
	}
	return false
}

Search的实现非常简单，通过findGreaterOrEqual找到第一个大于等于目标值的节点，如果该节点的值等于目标值，找到该值，返回true，否则，跳表中没有该目标值，返回false。其关键主要在于findGreaterOrEqual的实现，如下。

func (list *Skiplist) findGreaterOrEqual(key int) (*Node, [kMaxHeight]*Node) {
	var prev [kMaxHeight]*Node
	x := list.head
	level := list.maxHeight - 1
	for true {
		next := x.getNext(level)
		// key > next.key
		if list.keyIsAfterNode(key, next) {
			x = next
		} else {
			// key <= next.key
			// 即 next.key >= key
			prev[level] = x
			if level == 0 {
				return next, prev
			} else {
				// Switch to next list
				level--
			}
		}
	}
	return nil, prev
}

findGreaterOrEqual的返回值有两个，第一个返回值是第一个大于等于key的节点，第二个是如果key节点在跳表中的所有前置元素，如果key存在于跳表的话。

以图四为例，如果我们要查找21这个节点，那么返回值将会是节点21，以及{nil,9,17,19}，即节点21的所有前置元素。

下面我们看其具体实现，我们会从最高层往下寻找，首先获取下一个节点，如果下一个节点的值大于等于目标值key，即找到目标节点(第一个大于等于目标值key的节点)，记录当前节点为目标节点的前置元素，如果此时已是最下面一层，直接返回目标节点和记录的前置元素即可，否则，跳到下一层。

下图是论文《Skip lists: a probabilistic alternative to balanced trees》中关于查找的伪代码，读者也可以对照一下。

1.2.2 插入

对于插入而言，比如我们要插入节点17，首先我们要找到节点19(即跳表中第一个大于等于17的节点)的所有前置元素，即findGreaterOrEqual(key)返回的第二返回值，通过随机值确定新插入节点的高度，由于我们已经具有前置元素，所以插入时只要将前置节点的后续节点设置为新插入节点，新插入节点设置为之前节点的后续元素即可，代码如下。

func (list *Skiplist) Add(key int) {
	_, prev := list.findGreaterOrEqual(key)
	height := list.randomHeight()
	if height > list.maxHeight {
		for i := list.maxHeight; i < height; i++ {
			prev[i] = list.head
		}
		list.maxHeight = height
	}
	x := newNode(key,  height)
	for i := 0; i < height; i++ {
		// 设置新插入节点的后续节点
		x.setNext(i, prev[i].getNext(i))
		// 将前置节点的后续节点设置为新插入节点
		prev[i].setNext(i, x)
	}
}

需要注意的是randomHeight()的实现，这里使用了rand.Intn(kBranching)来生成一个[0, kBranching-1]范围内的随机整数,如果结果为0，即1/kBranching的概率高度加一层，同时kBranching也决定了每几个节点建立一个索引的间隔。

func (list *Skiplist) randomHeight() int {
	height := 1
	for height < kMaxHeight && (rand.Intn(kBranching) == 0) {
		height++
	}
	return height
}

下图是关于插入的伪代码。

1.2.3 删除

删除的实现较为简单，我们首先寻找目标值key的节点，如果不存在，直接返回false，否则，将目标值key所在节点的前置节点设置为下一个节点即可，代码如下。

func (list *Skiplist) Erase(key int) bool {
	node, prev := list.findGreaterOrEqual(key)
	if node == nil || node == list.head || node.key != key {
		return false
	}
	height := len(node.next)
	for i, n := range prev[:height] {
		n.setNext(i, n.getNext(i).getNext(i))
	}
    return true
}

1.2.4 总结

在上面，我们介绍了跳表的思路和实现，完整的代码可以查看leetcode_1206_solutions，读者可在Leetcode中测试代码正确性。

需要注意的是，如果想要运用于LevelDB，还需要进行一些简单的修改，这部分修改不多，请读者在独立完成leetcode 1206后查看build_level_from_scratch——skiplist实现。

1.3 跳表的复杂度

1.3.1 时间复杂度

关于跳表的时间复杂度，在此给出直觉上的证明，关于详细的证明可以查看论文。

以每两个节点建立一个索引为例，我们发现每次查找时，上层数据量都是下一层的一半，每次查找数据减半，因此我们可以把它看作一个二分查找树，所以时间复杂度为O(logn)。

同理，如果是每三个节点建立一个索引为例，我们可以把它看作一个三分查找树，时间复杂度仍然为O(logn)。

所以，不管每几个节点建立索引，其时间复杂度都为O(logn)。

1.3.2 空间复杂度

以每两个节点建立一个索引为例，假设原始链表包含 n 个元素，则索引节点的总数是：一级索引元素个数+二级索引元素个数+三级索引元素个数+...=(n/2)+(n/4)+(n/8)+...+8+4+2=n-2，空间复杂度是 O(n)。

在上文我们提到可以通过kBranching来控制每隔几个节点建立索引，所以实际实现中，可以通过增大kBranching的值，减少每一层的索引节点来降低空间复杂度，但系统设计的精髓在于权衡(tradeoff)，如果减少了索引，相应的，查找效率也会有一定下降，在现实中我们要根据应用场景来控制这个阈值。

参考文献

[1]. William Pugh. 1990. Skip lists: a probabilistic alternative to balanced trees. Commun. ACM 33, 6 (June 1990), 668–676. https://doi.org/10.1145/78973.78977

[2]. fanru_bigdata. 2019. 一文彻底搞懂跳表的各种时间复杂度、适用场景以及实现原理. https://blog.csdn.net/qq_34412579/article/details/101731935