跳表(skiplist)是一种有序数据结构,它通过在每个节点中维持多个指向其他节点的指针,从而达到快速访问节点的目的。 跳表是Redis有序集合的底层实现之一。
从跳表开始入手写,是想学习实现跳表这个数据结构。跳表的实现实际写下来还是蛮简单的,参考跳表论文"Skip Lists: A Probabilistic Alternative to Balanced Trees",看看前面的实现部分就可以了。
- 首先得了解跳表的基础算法,看论文,顺便可以刷一下leetcode 1206
- 了解跳表在redis中的,跳表的api,看《redis设计与实现》5.1节
- 对着redis的源码,翻译到go语言。
具体翻译到go的时候,比想象中难多了。其实也不难,只要不实现redis那些追求极致性能的语法就可以了。go语言的语法和c语言还挺像的。
进度太慢,先对着c源码照着撸go代码,把节奏搞起来,才有信心往下接着下。
对着代码翻译,了解了redis中的dict 字典
数据结构定义,shared 共享内存字符串
,string2ll
的实现
完成了zscore
命令的功能性测试。
实现过程中,想在go语言中实现redis的embedded string object
,这个对象主要的功能是,把robj
和string
所需要的内存,一起向操作系统申请,一来减少多次申请内存的时间开销,二来靠在一起的内存读写更快,也减少了产生内存碎片的概率。
在了解了一通操作系统的内存知识,go内存管理后,实现不了,除非引入CGO
。
go是基于tcmalloc
算法,完全自己管理内存,而且管理的方法和在学操作系统(C语言)的方法差异很大。go管理内存的思想是抽象内存空间为几种规格的空间,便可以流水线化的统一管理了。