首先，我们需要确认新加入的节点需要具有几层的指针 。我们通过随机函数来生成层数，比如说，我们可以写一个函数 RandomLevel()，以 (1/2)^n 的概率决定是否生成第 n 层 。这样，通过简单的随机生成指针层数的方式，我们就可以保证指针的分布，在大概率上是平衡的 。
在确认了新节点的层数 n 以后，接下来，我们需要将新节点和前后的节点连接起来，也就是为每一层的指针建立前后连接关系 。其实每一层的指针链接，你都可以看作是一个独立的单链表的修改，因此我们只需要用单链表插入节点的方式完成指针连接即可 。
这么说，可能你理解起来不是很直观，接下来，我通过一个具体的例子进一步给你解释一下 。
我们要在一个最高有 3 层指针的跳表中插入一个新元素 k，这个跳表的结构如下图所示 。
文章插图
假设我们通过跳表的检索已经确认了，k 应该插入到 a6和 a7两个节点之间 。那接下来，我们要先为新节点随机生成一个层数 。假设生成的层数为 2，那我们就要修改第 0 层和第 1层的指针关系 。对于第 0 层的链表，k 需要插入到 a6和 a7之间，我们只需要修改 a6和 a7的第 0 层指针；对于第 1 层的链表，k 需要插入到 a5和 a7之间，我们只需要修改 a5和 a7的第 1 层指针 。这样，我们就完成了将 k 插入到跳表中的动作 。
通过这样一种方式，我们可以大大减少修改指针的代价 。当然，由于新加入节点的层数是随机生成的，因此在节点数目较少的情况下，如果指针分布的不合理，检索性能依然可能不高 。但是当节点数较多的时候，指针会趋向均匀分布，查找空间会比较平衡，检索性能会趋向于理想跳表的检索效率，接近 O(log n) 。
因此，相比于复杂的平衡二叉检索树，如红黑树，跳表用一种更简单的方式实现了检索空间的平衡 。并且，由于跳表保持了链表顺序遍历的能力，在需要遍历功能的场景中，跳表会比红黑树用起来更方便 。这也就是为什么，在 redis 这样的系统中，我们经常会利用跳表来代替红黑树作为底层的数据结构 。
五、总结首先，对于数据频繁变化的应用场景，有序数组并不是最适合的解决方案 。我们一般要考虑采用非连续存储的数据结构来灵活调整 。同时，为了提高检索效率，我们还要采取合理的组织方式，让这些非连续存储的数据结构能够使用二分查找算法 。
数据组织的方式有两种，一种是二叉检索树 。一个平衡的二叉检索树使用二分查找的检索效率是 O(log n)，但如果我们不做额外的平衡控制的话，二叉检索树的检索性能最差会退化到 O(n)，也就和单链表一样了 。所以，AVL 树和红黑树这样平衡性更强的二叉检索树，在实际工作中应用更多 。
除了树结构以外，另一种数据组织方式是跳表 。跳表也具备二分查找的能力，理想跳表的检索效率是 O(log n) 。为了保证跳表的检索空间平衡，跳表为每个节点随机生成层级，这样的实现方式比 AVL 树和红黑树更简单 。
无论是二叉检索树还是跳表，它们都是通过将数据进行合理组织，然后尽可能地平衡划分检索空间，使得我们能采用二分查找的思路快速地缩减查找范围，达到 O(log n) 的检索效率 。
除此之外，我们还能发现，当我们从实际问题出发，去思考每个数据结构的特点以及解决方案时，我们就会更好地理解一些高级数据结构和算法的来龙去脉，从而达到更深入地理解和吸收知识的目的 。并且，这种思考方式，会在不知不觉中提升你的设计能力以及解决问题的能力 。
【数据频繁变化的情况下，如何高效检索？】
推荐阅读
- 是地球上生物多样性丰富和生产力较高的生态系统 为适应环境变化而进化的生物
- 建立数据中转服务器的详细方法
- 未来已来！分布式数据库的“星辰大海”绝不仅限于替换
- SpringBoot配置文件数据加密自定义开发详解
- 星空越黑暗,星光越明亮 星空一天之中的变化
- CentOS7下yum方式安装MySQL5.7数据库
- Redis宕机或者出现意外删库导致数据丢失--解决方案
- Springboot +Mybatis实现多数据源配置，你会吗？
- 什么是数据库的“缓存池”？
- Apache四个大型开源数据和数据湖系统