go skip list跳表实现之Redis为啥这么快之一的原因

😯skip list是一个基于List数据结构的概率平衡有序List。因其良好的查找和插入特性被很多开源组件选择作为数据存储结构，其中不乏知名项目，例如Redis。

🚗🚗🚗🚗本篇博客致力于讲清楚SkipList的结构，以及数据查找和数据插入的伪代码流程。

目录

一、SkipList的诞生

二、🍻SkipList的概念介绍

2.1🍺🍺🍺 SkipList的概念

2.1 🍭🍭🍭SkipList的数据的查找和插入

三、🍻SkipList的Go语言实现

3.1 节点定义

三、🍏🍏🍏总结

---

---

一、SkipList的诞生

SkipList在1989年由William Pugh发明，作者时年29岁。SkipList发明的初衷是为了克服平衡树的一些缺点，比如平衡树在节点插入时，需要额外的进行的树的转枝，剪枝操作，才能够达到树的平衡。而SkipList借助于其独特的设计，在数据插入过程中，不需要额外的数据排序过程，只需要找到其需要插入位置的前置节点，即可插入，插入之后，依然保持数据结构的数据平衡。

二、🍻SkipList的概念介绍

SkipList的设计主要是基于单链表，在单链表的技术上加多层链表数据索引，实现对链表数据的二分查找。

2.1🍺🍺🍺 SkipList的概念

        SkipList的主要构建是在基础数据的基础进行数据的多层索引，数据会有几次索引，是通过概率函数保证，基本上是1/2的概率是0,1、1/4的概率是3,4层（详细过程：实验中提及）。

        下面这张图片较为详细的介绍了SkipList的构造过程！下图有a,b,c,d,e5个链表，从a-e都在原有的上一层链表加了一层索引。

        这里面有2个关键点就是：

        1、加了层数，但是数据并没有增加！比如值为9的节点，在b中，它的nextNode增加了值为17的节点、在C中增加了nextNode为21的节点。

        2、一个节点有几层索引是独立的，和前后节点均没有关联。也就是有可能出现前置节点的层数小于后置节点。

2.1 🍭🍭🍭SkipList的数据的查找和插入动图展示

来自于维基百科的动图展示。

2.2 SkipList的查找逻辑描述

SkipList是一个多层的链表，其设计的初衷是在链表中查询数据可以达到logN，也就是接近于二分查找。那么在SkipList中是如何实现的？如何实现SkipList的分层查找。

看这种相对来说比较复杂的数据结构行为，拆分来看，效果会更好一些。

查找的过程中，有两个主要行为：

1、单层查找，每一层都遍历查找，直至层级下移查找的条件或者找到查询节点，结束查找。

2、层级下级下移查找，直至最底层

层级下移查找的条件：当前层级中，遍历至最后一个元素，没有找到节点。这里有一个小小优化就是在当前层级中找到元素所在的区间，也可以层级下移。

2.3 SkipList的插入逻辑描述

万变不离其宗，考虑SkipList的插入时，也要在SkipList是一个多层有序链表的前提下考虑。

SkipList的插入逻辑综合起来也是多层链表的一个实现。一般的实现逻辑是先找到层数对应的每一层都需要插入的前置节点。

找到所有的前置节点后，再使用随机函数，确定一个该节点插入的层级。插入层级确认完毕以后，执行0层到插入层级的逐级插入。

三、🍻SkipList的Go语言实现

3.1 节点定义

        SkipList的数据结构基本上是升级的List数据结构，与普通的List节点相比，其next是一个数组，而不是单个一个指针。

三、🍏🍏🍏总结

        今天主要是抛转引玉，添加了一些参考价值比较高的资料和图片💪🏻⛽️~

🧧🧧🧧感谢诸位大佬的阅读，点个关注，收藏一下呗~