最近，我正在研究公司业务的存储架构。现有存储使用Redis和LevelDB通过自己编写的中间件来实现数据。以这种方式写作业务和数据恢复有点麻烦。如果您想优化，可以研究Redis和LevelDB的源代码。发现表跳转的数据结构非常有趣，性能很好，实现相对简单。我想使用GO来实现GO的跳线，并通过此表获得类似表的ZSET函数。我将尽可能地介绍所有细节。看本文，首先熟悉链接的相关知识列表，例如链接列表的插入和删除。最好是稍作介绍，而不是与关系。GO的语法非常简单。它与C有点相似。基本上，计算机基础可以理解GO的语法。
引入以下几点以介绍
跳台是可以快速搜索的有序链接列表。搜索，插入和删除操作的时间是O（logN）。Wikipedia Baike百科全书的详细定义Wikipedia百科全书是一种非常有用的数据结构，但是许多书籍有很多书，但是很多书都有很多书籍，但是很多书都有很多书。我没有写过这本书。我没有在大学的数据结构教科书中写下跳跃，这导致许多人不熟悉跳台。
跳台本质上是链接列表，因为链接列表的随机搜索性能太差了。它开着）。搜索元素只能从头部或末端节点穿越。
如图所示，您应该找到节点6，并且只能从稍微向右穿越。
我可以在链接列表中使用双点搜索吗？当然，有可能，即添加链接列表，即跳跃手表
上图是一个简单的跳跃表（图中将详细介绍图中的各种颜色和数字）。从图可以看出，跳台是根据两条路链接列表实现的。
作为一种快速的数据结构，跳台通常用于与红树和黑树进行比较。列出跳台和红色黑树的优点和缺点。
堂兄对Redis对思想特定代码的ZSET实现实现的真实代码的实现仅仅是GitHub表中有两种想法。一个是在跳跃表中无法重复的元素。REDIS中的跳跃表允许重复元素。这次我还可以实现重复的元素。
节点跳跃表节点的结构
在节点中，黑色1是值，黄块是级别的，而两个指针在图中的图中没有反映。只有一个向后的（向后指针），lactef数组的长度是，将有多少个向前。该值是计算跳跃表中此节点的排名下一个节点直到我编写插入和搜索节点。
头部和尾巴是指向跳桌的头部和尾巴的两个指针。大小是整个跳台中的节点的数量。高度不是固定的，而是插入和删除的动态更改。Maxlevel是跳台可以实现的最大高度。该值在开始时是固定的。
拍摄上面的图片并分析整个跳节点之间的组织关系
跳台上会有一个头节点，但是没有尾部节点。尾部只是一个指针，指向跳台的最后一个节点。这反映在初始化函数中
图中的向前指针，即橙色箭头，向后的指针，绿色箭头。forward指针处于级别，即每一层都有一个正向指针。向后仅存在于节点中，也就是说，每个节点只有一个向后指针。想想为什么您只需要一个向后的指针？互截面查看整个搜索过程，您可以理解为什么您只需要向后指针。
插入节点的基本知识几乎已经准备好，并开始输入跳台插入的逻辑。首先，使用图片显示逻辑
插入元素的第一步是首先找到元素。由于它是有序的链接列表，元素是按顺序排列的，并且该元素应处于应在元素上的位置。
在图中，分数到3的元素插入跳跃表中。带有序列号的箭头（指针）是搜索顺序。黑色箭头是实际路径。在搜索过程节点的跨度总和中。首先澄清我们要搜索哪个节点。我们需要找到最多的小于3的数量（在小数和链条列表中不超过3个情况），这反映在图中，也就是说，我们想找到元素2的位置。
在搜索之前确定当前跳跃的最高级别值。它也可以从最高级别开始，但没有任何意义。从0）。然后从头部节点的第3级开始。
首先设置一个临时指针t指向头节点。首先通过图中的1指针指向元素4，要插入的节点为3，显然大于3，因此不在排列。当未满足当前节点的下一个节点时，下一个节点不合格时，您需要开始搜索下一层。这是一个传输条件。这次，当前节点仍在头部，因此从Head's Level2到右侧。这次，节点的下一个节点少于1、1小于3，因此它符合条件，因此T指针应指向1个节点，然后记录头部的跨度值。
在此之后，在判断345个指针之后，我终于来到了节点2的级别。这时，Node2的下一个节点大于3，目前也是最后一层，所以节点2是最大值小于3，也是要查找的元素。
找到正确的位置，下一步是将节点3插入并调整跨度。
确定要插入的位置后，还必须确定Node3元素的级别高度。根据理想状态中间的节点，该高度是最高的。它类似于山区字符类型。此节点很高，但实际上，跳跃手表并不严格执行这种理想状态。节点的高度由随机数确定。您尚未正确阅读，您是由随机数确定的。这就是为什么跳跃相对简单地实现红树和黑树的原因。
这是一个随机函数
上述段落的功能函数是相同的，25％的概率允许节点的水平+1。
以下是整个节点的源代码
在搜索过程中，需要等级数组和更新数组的两个辅助结构。乘坐用于记录每一层的排名值，以稍后调整新节点级别。update用于记录从顶部传递的路径底部，即跳表中上一个节点中新节点的每一层。
以上是判断搜索过程中它是正确的还是将其调整到下一层的逻辑。不仅有必要在此处判断节点的社会，而且还考虑了两个节点分数的相同情况。当两个节点的SOCRE相同时，两个节点的大小由比较函数确定。
该代码是在确定新节点的高度后处理新层。因为在搜索时，我们现在没有将头放在更新中，现在将其放置在其中。
该代码是通过调整节点的前后指针并调整节点的跨度值，将新节点添加到跳台上。距离最后一个节点的距离，因为它是到下一个节点的距离，只需更改当前节点的跨度值即可。如果存储的内容是从最后一个节点到该节点的距离，则需要更改下一个节点的跨度，并且在更改它时会很麻烦。这可能有点尴尬，您可以自己体验它。
本段可能无法很好地理解。该代码的作用是，如果新节点的级别小于跳表中最大级别（新节点的级别为2，则跳表中最大的级别是5）时间，在2上方的所有节点中的跨度+1。
其余的，处理新节点的背包旅行（向后）并判断它是否是最后一个节点的情况，情况非常简单。
到目前为止，插入节点并不困难，这不是很难吗？实际上，跳台最复杂的是插入过程。其余的，更新和搜索是相似的逻辑。首先找到密钥节点，然后对其进行处理。
删除节点
同样，删除是首先搜索。通过黑色箭头的路径，找到要删除的先前的箭头，然后修改目标节点的先前节点指针，跳过目标节点，完成删除，最后调整目标节点的跨度。
首先搜索节点，然后记录到更新数组
插入时，此逻辑与搜索逻辑相同
以下是删除的逻辑
删除节点的代码要简单得多。这是一条从最大值传递到通过参数（即更新数组）的路径。
本段逻辑是删除节点。删除是让目标节点前面的节点的后指针指向目标节点后面的节点。其余的是处理节点背手，并判断它是否是最后一个节点。
更新节点以更新节点的分数。更新节点的前提是找到目标节点。原理和先前的插入。关于更新节点分数的逻辑的讲话，最简单的是删除节点然后插入。当然，可以优化此类逻辑，例如，存在情况。
如图所示，Node4的分数已更新为5。此时，修改节点的分数不会影响节点的位置，因此这种情况只需要修改节点的分数。
对于修改分数将改变的情况，首先需要节点，然后回复节点。
查找节点很容易找到节点，因为先前的插入，更新，删除要求正面查找节点。但是将搜索分为两种情况，一种是根据排名找到，另一个是基于得分。
首先看排名
首先排除不匹配的情况，然后根据上一个搜索逻辑逐步找到它。区别在于当前限制已排名。
根据分数看
根据分数找到更为复杂的一点，因为根据得分，将有两种情况：积极和无尽。在这次，只有两个简单的范围值不够，并且需要使用结构来描述范围。
在搜索之前确定它，给定范围是否在跳台的范围内，如果没有，则不需要找到它。
该逻辑是确定搜索的起始位置，即找到目标节点（根据范围找到最小的节点）。如果它从负面无尽的末尾开始，则不需要通过以前的方式确定起始节点。以下逻辑并不是什么特别的。找到目标后，稍后开始找到它，直到结束或不达到范围，它结束了。
好的，搜索也已完成。
跳台的基本功能现已完成。其余的是打包跳跃以在Redis中实现ZSET的功能。将不会发布特定代码，最后我将提供GitHub连接。
最后，让我们谈谈常见表的通用应用。REDIS的ZSET基于跳跃表。当然，我还通过阅读redis的源代码来学习跳台。谷歌开发的其他级别b也基于跳投实现。
最后放置所有源代码，github gitee
如果本文对您有所帮助，请记住给我一颗星星。谢谢。