赞
踩
跳跃表(skiplist)是一种有序且随机化的数据结构,它通过在每个节点中维持多个指向其他节点的指针,从而达到快速访问节点的目的。
有序集合(zset)的底层可以采用数组、链表、平衡树等结果来实现, 但是他们都有各自的缺点,数组方便查询,但不便于插入和删除;链表方便插入和删除,但是不利于查找;平衡树/红黑树效率高但是实现起来很复杂。
为什么 Redis 不使用这样一些结构呢?
所以Redis自己实现了跳跃表来来当做有序集合(zset)的底层实现, 他的查询复杂度平均O(logN), 最坏O(N), 堪比红黑树,但实现起来远比红黑树简单。
先分析一下链表,链表的优势是插入、删除快,查询很慢。对于链表来讲,即便链表中存储的数据是有序的,如果我们要向在其中查找某个数据,它只能从头到尾遍历链表。这样查找效率就会很低,时间复杂度会很高,达到了O(n)。
若要查找值为5的元素,需要从第一个元素依次向后查询,共需比较5次才可以。
假设要查找值为5的元素,可以先在索引层遍历,当遍历到索引层中值为5的元素时就返回。在原单链表中查找值为5的元素,需要遍历比较5次才可以。而现在有了一级索引后,只需要遍历3次就可以找到对应的元素。
从上个例子中,每加来一层索引后,查找元素需要遍历的次数就会减少,查询效率也得到提升,同理在一级索引的基础上,在加二级索引。
假设要查找值为6的元素,可以先在索引层遍历,当遍历到索引层中值为7的元素时,则会下降到下层链表层继续查找值为6的元素。
从图中我们可以看出,查找效率又有了提升,因为在这里例子中我们的数据量很少,当有大量的数据时,我们可以增加多级索引,在查询时,效率可以得到明显的提升。像这种链表增加多种索引的结构,就是 跳跃表。
B+树存储就是一个平衡搜索树,如果要插入一个节点那么就检索到这个节点插入,插入的时候要维护子树的规则(平衡搜索树)还有就是 B+树 在 mysql 当中还要在一定的情况下扩容和缩容。这就要消耗一定的资源算力,而跳表这里用随机层数来解决这个问题,这样就解决了插入的消耗问题,比平衡术更加优秀。
由此可见跳表的本质是解决查找问题。
如果理解上面所说的跳跃表的原理,那么很容易理清楚插入节点时发生的几个动作 (几乎跟链表类似):
插入操作在实现起来是最麻烦的,需要的考虑的东西最多。插入需要考虑是否插入索引,插入几层等问题。其流程为:
删除操作比起查询稍微复杂一丢丢,但是比插入简单。删除需要改变链表结构,需要先找到元素,然后对于每个层的相关节点重排前向后向指针,所以需要处理好节点之间的联系,同时还要更新层数。
对于删除操作你需要谨记以下几点:
暂时没做研究
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。