Fh's Blog

山随平野尽,江入大荒流。

HyperLogLog算法核心原理 写在前面... 阅读Redis的源码你会发现,里面有个略微奇怪的结构,叫做HyperLogLog。大多数人第一反应这个可能是个日志相关的东西?实际上是Redis里相对复杂的一个非传统算法,其可被用于海量数据的统计。 上...

发布 0 条评论

Redis跳表中每个节点的span实际上是个非常巧妙的设计,但是关于span的部分阅读起来不是很容易,因为这种在数据结构上做的创新行为往往不能第一眼就理解。在跳表的插入删除操作,可以看到有很多部分都在对span进行调整,span是一个重要...

发布 0 条评论

下面进入跳表的具体实现,以下代码位于z_set.c 先忽略插入与删除中对span相关的调整操作,下一篇会专门对span进行解释后再继续跳表的后续剖析 以下是两个基本的创建函数 创建一个跳表节点,不多说 创建整个跳表。设置跳表的初始最...

发布 0 条评论

从跳表(SkipList)开始,离Redis用户层面就比较近了,Redis用户层面的五个基本数据类型中有序集合zset的实现主要基于三个部分:跳表、dict、ziplist。三者搭配的很完美,其中dict我们已经研究过,至于ziplist则是压缩列表,关于zipli...

发布 0 条评论

排序永远是数据结构里永恒的话题,快排、归并排序这样基于分治思想排序的提出,极大的优化了插入排序、冒泡排序这样的O(N^2)排序算法。对于这样基于分治思想的排序,都可以写成多线程算法,但在C/C++下,很少有人把快排写成多线程,因...

发布 2 条评论