个人技术分享

跳跃表

  跳跃表是一种有序的数据结构，它通过在每个节点维护多个指向其它结点的指针，从而达到快速访问结点的目的。在链表的基础上增加多级索引。跳跃表是以空间换时间提升查询速度，平均时间复杂度O(logN)，最坏O(N)。大多数情况下是和平衡树查找效率一样的。
  例如：我们想查找链表上的数字5，需要遍历查找到第5个节点，而跳跃表是在链表基础上抽取一些元素组成一个链表，就可以缩短我们遍历查找的节点个数，像下图我们使用第二个链表就可以遍历查找到第3个元素查找到5。当然这仅仅是个帮助我们理解的小例子。

应用

• Redis有序集合：包含元素较多时或者元素有比较长的字符串时
• 集群节点中用作内部数据结构

实现

  每次当创建新的跳跃表节点的时候，程序根据幂次定律随机生成1~32之间的数值作为level数组的大小，也就是高度，程序会尽量保证上一层元素的个数是下一层元素个数的1/2。

zskiplistNode

typedef struct zskiplistNode{
	//后退指针：指向当前节点前一个节点，从表尾向表头遍历使用
	struct zskiplistNode *backward;
	//分值score：按照分值从小到大排列
	double score;
	//成员对象：指向一个字符串对象，字符串对象保存的是一个SDS字符串
	robj *obj;
	//层:level数组下每个元素里包含一个指向其它节点的指针，程序通过层来加快访问其它节点的速度
	struct zskiplistLevel{
		//前进指针，用于从表头向表尾访问节点
		struct zskiplistNode *forward;
		//跨度：记录两个节点之间的距离，用于计算1排位
		unsigned int span;
	}level[];
}

zskiplist结构

用于保存跳跃表节点的相关信息

typedef struct zskiplist{
	//表头和表尾节点的指针
	struct skiplistNode *header,*tail;
	//表中节点的数量，可以直接返回跳跃表长度
	unsigned long length;
	//表中层数最大的节点的层数（表头节点的层高并不计算在内）
	int level;
}

为什么使用跳跃表

redis使用跳跃表而没有使用其它有序的数据结构，例如红黑树。主要有以下几个方面考虑

• 实现简单：跳跃表相比较于红黑树的实现更简单，容易理解
• 避免复杂的旋转操作：在查找、插入和删除等操作中，跳跃表不需要旋转操作
• 空间利用率高：跳跃表通过引入多级索引来实现查找并且索引占用空间小