之前一直不太懂,为什么跳表的平均时间复杂度为O(logN)
但是后来看了下
http://blog.xiaoheshang.info/?p=248 算是理解了一些,再结合自己的思考,记录一下
首先,需要理解刚才那篇文章中的 "如果每2^i个节点都指向前面2^i个节点,寻找一个节点的复杂度变成logn(类似于二分查找)", 这个应该没什么问题
那么问题来了,为什么随机的层数也能保证logN的复杂度?
原因就在于,这里说的随机,并不是完全的随机一个层数出来,而是通过随机的算法,算出一个并不随机的层数来
以redis中的随机层数的算法来看
int zslRandomLevel(void) {
int level = 1;
while ((random()&0xFFFF) < (ZSKIPLIST_P * 0xFFFF))
level += 1;
return (level<ZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL;
}
这里假设 ZSKIPLIST_P 为2 (实际为4,便于理解设置为2),这段代码我们可以理解为,落到层数为i + 1的概率为0.5^i
而反过来理解,每两个节点出现层数为2的期望就是1,每4个节点出现第三层的期望也为1,每8个节点出现第四层(0.5^3)的期望为1 (期望值 = 单个概率 * 数量)
正是基于此,如果我们的数据量越大,越是可以接近期望的值,所以,我们可以认为,我们实现了 "如果每2^i个节点都指向前面2^i个节点"的效果,也就是说,查找的平均复杂度为O(logN)
分享到:
相关推荐
摘要 面试时,交流有关mysql索引问题时,发现有些人能够涛涛不绝的说出B+... redis跳表是如何实现的 跳表和B+树,LSM树有和区别呢 解析 首先为什么要把mysql索引和redis跳表放在一起讨论呢,因为他们解决的都是同一种
java使用DelayQueue延迟队列和Redis缓存实现订单自动取消功能
【案例实战】SpringBoot整合Redis的GEO实现查找附近门店功能源码包
redis实现简单排行榜,和消息处理。
基于mq和redis实现的秒杀系统基于mq和redis实现的秒杀系统
redis之相关理解分析以及面试问题总结,以及更加深入的理解redis存储机制
基于Redis方式实现分布式锁
redis实现分布式锁(java/jedis),其中包含工具方法以及使用demo 本资源是利用java的jedis实现 redis实现分布式锁(java/jedis),其中包含工具方法以及使用demo 本资源是利用java的jedis实现
redis设计与实现 Redis(Remote Dictionary Server ),即远程字典服务,是一个开源的使用ANSI C语言编写、支持网络、可基于内存亦可持久化的日志型、Key-Value数据库,并提供多种语言的API。从2010年3月15日起,...
Redis主从实现读写分离,大家在工作中可能会遇到这样的需求,即Redis读写分离,目的是为了压力分散化。下面我将为大家介绍借助AWS的ELB实现读写分离,以写主读从为例。
今天用了一天来搞定了ssm+redis集成和nginx实现负载均衡,这里只有ssm+redis简单d集成demo,希望大家一起来讨论
tomcat-redis实现session共享
redis实现分布式锁,自旋式加锁,lua原子性解锁
Qt 使用 Redis实现 消息队列,点对点 生产者-消费者 模式
Spring boot基于Redis Hash数据结构实现附近的人Demo,框架由Spring-boot实现,压缩包含源码以及部署jar包。代码清晰,有注释,考虑性能优化
ssm+redis+nginx实现session共享和负载均衡,大家一起来研究吧
Spring Boot 使用 AOP 和 Redis 实现接口限流是一种高效且实用的方法,用于控制对特定接口的访问频率。以下是实现这个功能的基本步骤: 引入依赖:首先,在 Spring Boot 项目中引入 Redis 和 AOP 的相关依赖。这...
本篇文章主要介绍了基于 Redis 实现分布式应用限流的方法,小编觉得挺不错的,现在分享给大家,也给大家做个参考。一起跟随小编过来看看吧
Redis介绍与实现机制.PPT