其他
目前市面上充斥着大量关于跳跃表结构与Redis的源码解析,但是经过长期观察后发现大都只是在停留在代码的表面,而没有系统性地介绍跳跃表的由来以及各种常量的由来。作为一种概率数据结构,理解各种常量的由来可以更好地进行变化并应用到高性能功能开发中。本文没有重复地以对现有优秀实现进行代码分析,而是通过对跳跃表进行了系统性地介绍与形式化分析,并给出了在特定场景下的跳跃表扩展方式,方便读者更好地理解跳跃表数据结构。跳跃表[1,2,3]是一种用于在大多数应用程序中取代平衡树的概率数据结构。跳跃表拥有与平衡树相同的期望时间上界,并且更简单、更快、是用更少的空间。在查找与列表的线性操作上,比平衡树更快,并且更简单。概率平衡也可以被用在基于树的数据结构[4]上,例如树堆(Treap)。与平衡二叉树相同,跳跃表也实现了以下两种操作通过搜索引用[5],可以保证从任意元素开始,搜索到在列表中间隔为的元素的任意期望时间是实现线性表的常规操作(例如将元素插入到列表第k个元素后面)这几种操作在平衡树中也可以实现,但是在跳跃表中实现起来更简单而且非常的快,并且通常情况下很难在平衡树中直接实现(树的线索化可以实现与链表相同的效果,但是这使得实现变得更加复杂[6])一、预览最简单的支持查找的数据结构可能就是链表。Figure.1是一个简单的链表。在链表中执行一次查找的时间正比于必须考查的节点个数,这个个数最多是。Figure.1