Ref:
GPL协议在我心中,一直是一块丰碑,简直让人敬而畏之。
但真正读过GPL的人,少之又少,甚至绝大多数程序员,都没有见过GPL的真身。
原因很简单,一是不关心,二是懒得看,三是觉得看了也看不懂。
其实没有那么难的,看完这篇人话版,你就克服这个心理障碍了。
我们早该读GPL的。
我们早该理解GPL的。
Ref:
GPL协议在我心中,一直是一块丰碑,简直让人敬而畏之。
但真正读过GPL的人,少之又少,甚至绝大多数程序员,都没有见过GPL的真身。
原因很简单,一是不关心,二是懒得看,三是觉得看了也看不懂。
其实没有那么难的,看完这篇人话版,你就克服这个心理障碍了。
我们早该读GPL的。
我们早该理解GPL的。
在我阅读 Redis 底层实现中跳表的部分的时候,不由得想起 b+ 树系列。它们有类似性,比如都是通过多层结构实现快速跳转查找。但是跳表中的层数完全随机,即便是在统计意义上的平均时间复杂度也是和 b+ 树相近。好像跳表从各个方面都不太比得上 b+ 树,那为什么 Redis 的作者却更偏向使用跳表来实现呢? (3.0版本之后的 Redis 更喜欢将 sdlist 与 skiplist 一起使用,并称之为 quicklist
)
如下即是一个典型的跳表[1]:
关于跳表的细节可以参考 WilliamPugh 关于跳表的论文 《Skip Lists: A Probabilistic Alternative to Balanced Trees》
[0]
Include: 跳表的粗浅理解, Redis 作者给出的理由