redis中跳表源码（redis中的跳表）

本文目录一览：

• 1、windows怎么调试redis源码
• 2、数据结构 - 跳表skiplist
• 3、跳跃表(SkipList)
• 4、Redis的五种数据结构及其底层实现原理
• 5、为啥redis 使用跳表而不是使用 red-black

windows怎么调试redis源码

Redis对于Linux是官方支持redis中跳表源码的,安装和使用没有什么好说的,普通使用按照官方指导，5分钟以内就能搞定。详情请参考:

但有时候又想在windows下折腾下Redis,可以从redis下载页面看到如下提示(在页面中搜索 "windows")redis中跳表源码：

[plain] view plain copy

Win64 Unofficial The Redis project does not directly support Windows,

however the Microsoft Open Tech group develops and maintains

an Windows port targeting Win64.

大意就是 Redis官方是不支持windows的，只是 Microsoft Open Tech group 在 GitHub上开发redis中跳表源码了一个Win64的版本,项目地址是：

打开以后，可以直接使用浏览器下载，或者Git克隆。

可以在项目主页右边找到 zip包下载地址:

(注意: dist文件改变了下载地址: )

数据结构 - 跳表skiplist

更多数据结构内容redis中跳表源码，请参考： 数据结构 - 概要

跳表产生redis中跳表源码的背景

任何技术，都是为了解决特定问题而出现的。

跳表要解决的就是list这种数据结构查询速度过慢的问题。

与list常做对比的数据结构是数组。数组中元素的查找可以使用二分查找，可以使查找降低到O(logN)的时间复杂度度

但是对于list来讲，查找只能从头或尾部一个个遍历，时间复杂度是O(n)的。

二分查找的效率高，是因为每次对比后，都能排除一半的数据，使要搜索的元素集合大大减少。这类似于一种索引技术，而数组下标就是索引。

对于list来讲，可以通过额外存储一些数据，当做list的索引：即在原来list的基础上，再存储些数据，这些数据也都是用list存储的。通过逐层对比这些数据，实现缩小搜索范围的目的。这个在 Redis 为什么用跳表而不用平衡树？ 中讲的比较清楚。

但是跳表并没有实现严格的二分。要实现严格的二分要调整已经存储的数据，会增加工作量。

跳表选择了一种变通做法，通过随机函数，决定新插入元素的层高。这种实现虽然不能保证查询效率是严格的O(logN)，但是平均值和绝大多数情况下，都能达到O(logN)的效率。

这是一种折中，但折中折中在没有降低太多查询性能的情况下，大大提升了插入效率。这个想法跟红黑树的实现有相似之处。 数据结构 - 红黑树

跳表与平衡树的比较

跳表会经常被用来跟平衡树，尤其是红黑树来比较。

这是因为跳表和红黑树能做的事几乎相同。

像redis中sorted set数据结构是用跳表来实现的。而JDK中的TreeMap使用红黑树来实现的。

只能说跳表和红黑树各有千秋。个人在选择其中一个实现时，需要结合自己的实际情况，如能力、时间和需求等。

为啥 redis 使用跳表(skiplist)而不是使用 red-black？ 文中讨论了redis为何使用的是跳表而非红黑树。里面一个共识就是，跳表实现起来比红黑树简单太多了(redis作者也把这个列为了一个因素)，又能满足需求。

跳跃表(SkipList)

跳跃表是一种基于有序链表的拓展redis中跳表源码，简称跳表。

下面正式开始了哦，跟着思路来，非常简单理解:

给定一个有序链表：

1-2-3-5-6-7-8

跳表的思想就是利用了类似索引的思想，提取出链表中的部分关键节点，然后再用二分查找。

上面的有序链表，把奇数作为关键节点提取出来：

上面只是介绍了基本思想，其实还可以继续优化，看到这别担心，难度不会增加，也非常好理解:

既然上面提取了一层节点作为索引，那是不是也可以进一步提取redis中跳表源码？

有了2级索引后，插入的节点可以先和2级索引比较，确定大体范围;然后再和1级索引比较;最后再回到原链表，找到并插入对应的位置。

节点多的时候还可以进一步提取，保证每一层是上一层节点的一半。提取的极限是同一层只有两个节点的时候，因为一个节点比较没有意义。

到这里，多层链表结构就提取完了，这就是跳跃表。

当大量新节点通过逐层比较插入到链表中后，上层节点就会显得不够用，这就需要从新节点中“提拔”一部分节点到上一层，问题就是“提拔”谁呢(如何选择索引)？

跳表设计者采用了“抛硬币”的方法，随机决定新节点是否提拔。因为跳表的添加和删除的节点是不可预测的，很难用算法保证跳表的索引分布始终均匀。虽然抛硬币的方式不能保证绝对均匀，但大体上是趋于均匀的。

比如说，9插入到链表后，开始分析：

跳跃表插入操作的时间复杂度是O（logN），而这种数据结构所占空间是2N，既空间复杂度是 O（N）。

删除的时候只要在索引层找到要删除的节点，然后删除每一层相同的节点即可。如果某一层删到只剩下一个，那么整层都可以删掉。比如删除5:

跳跃表删除操作的时间复杂度是O（logN）。

跳表维持结构平衡的成本较低，完全靠随机。二叉查找树在多次插入和删除后需要重新保持自平衡。

Redis的五种数据类型之一Sorted-set(zset)这种有序集合，正是对于跳跃表的改进和应用。

还有Java中的ConcurrentSkipListMap和ConcurrentSkipListSet内部都是用跳表的数据结构。

Redis的五种数据结构及其底层实现原理

redis的字符串类型是由一种叫做简单动态字符串(SDS)的数据类型来实现

SDC和C语言字符串的区别：

1：SDS保存了字符串的长度，而C语言不保存，只能遍历找到第一个\0的结束符才能确定字符串的长度

2：修改SDS，会检查空间是否足够，不足会先扩展空间，防止缓冲区溢出，C字符串不会检查

3：SDS的预分配空间机制，可以减少为字符串重新分配空间的次数

备注：重新分配空间方式，小于1M的数据 翻倍+1，例如：13K+13K+1，如果大于1M，每次多分配1M，例如：10M+1M+1,如果字符串变短，并不会立即缩短，而是采用惰性空间释放，有专门的API可以释放多余空间

hash结构里其实是一个字典，有许多的键值对

redis的哈希表是一个dictht结构体：

哈希表节点的结构体如下：

hash算法：

当要将一个新的键值对添加到字典里面时， 程序需要先根据键值对的键计算出哈希值和索引值， 然后再根据索引值， 将包含新键值对的哈希表节点放到哈希表数组的指定索引上面。

hash冲突解决方式：链表法，后入的放到最前面

rehash：

键值数据量变动时，时为了让哈希表的负载因子（load factor）维持在一个合理的范围之内， 当哈希表保存的键值对数量太多或者太少时， 程序需要对哈希表的大小进行相应的扩展或者收缩。

如果是扩充，新数组的空间大小为 大于2*used的2的n次方，比如：used=5,则去大于10的第一个2的n次方，为16

如果是缩小，新数组的空间大小为第一个不大于used的2的n次方，比如：used=5,则新大小为4

redis的list列表是使用双向链表来实现的

···

typedef struct listNode {

struct listNode * pre; //前置节点

struct listNode * next; //后置节点

void * value; //节点的值

}

typedef struct list {

listNode *head; //表头节点

listNode tail; //表尾节点

unsigned long len; //链表所包含的节点数量

void ( dup) (void ptr); //节点值赋值函数 这里有问题

void ( free) (void ptr); //节点值释放函数

int ( match) (void *ptr, void *key) //节点值对比函数

}

···

1：有序集合的底层实现之一是跳表， 除此之外跳表它在 Redis 中没有其他应用。

2：整数集合（intset）是集合键的底层实现之一： 当一个集合只包含整数值元素， 并且这个集合的元素数量不多时， Redis 就会使用整数集合作为集合键的底层实现。

3：数据少是，使用ziplist(压缩列表)，占用连续内存，每项元素都是(数据+score)的方式连续存储，按照score从小到大排序。ziplist为了节省内存，每个元素占用的空间可以不同，对于大数据(long long),就多用一些字节存储，而对于小的数据(short)，就少用一些字节来存储。因此查找的时候需要按顺序遍历。ziplist省内存但是查找效率低。

无序集合可以用整数集合(intset)或者字典实现

Redis的5.0版本中，放出一个新的数据结构Stream。其实也是一个队列，没一个不同的key对应的是不同的队列，没个队列的元素，也就是消息，都有一个msgid，并且需要保证msgid是严格递增的。在Stream当中，消息是默认持久化的，即便是Redis重启，也能够读取到信息。

Stream的多播，与其它队列系统相似，对不同的消费者，也有消费者Group这样的概念，不同的消费组，可以消费通一个消息，对于不同的消费组，都维护一个Idx下标，表示这一个消费群组费到了哪里，每次进行消费，都会更新一下这个下标，往后面一位进行偏移。

跳跃表是一种有序数据结构，它通过在每个节点中维持多个指向其它节点的指针，从而大道快速访问节点的目的，具有以下性质：

1：有很多层结构组成

2：每一层都是一个有序的链表，排列顺序为由高到低，都至少包含两个链表节点，分别是前面的head节点和后面的nil节点

3：最底层的链表包含了所有的元素

4：如果一个元素出现在某一层的链表中，那么在该层之下的链表也全部都会出现

5：链表中的每个节点都包含两个指针，一个指向同一层的下一个链表节点，另一个指向下一层的通一个链表节点

多个跳跃表节点构成一个跳跃表

1：搜索，从最高层的链表节点开始，如果比当前节点要大和比当前层的下一个节点要小，那么则往下找，也及时和当前层的下一层的节点下一个节点

2：插入，首先确定插入的层数，有一种方法是抛一个硬币，如果是正面就累加，直到遇到反面为止，最后记录正面的次数作为插入的层数，当确定插入的层数K后，则需要将新元素插入从底层到K层

3：删除，在各个层中找到包含指定值得节点，然后将节点从链表中删除即可，如果删除以后只剩下头尾两个节点，则删除这一层。

整数集合是Redis用于保存整数值集合的抽象数据类型，它可以保存int16_t、int32_t、int64_t的整数值，并且保证集合中不会出现重复元素。

整数集合的每个元素都是contents数组的一个数据项，他们按照从小到大的顺序排列，并且不包含任何重复项。

length属性记录了contents数组的大小。

需要注意的是虽然contents数组声明为int8_t类型，但是实际上contents数组并不保存任何int8_t类型的值，其真正类型由encoding来决定。

压缩列表(ziplist)是Redis为了节省内存而开发的，是由一系列特殊编码的连续内存块组成的顺序型数据结构，一个压缩列表可以包含任意多个节点(entry)，每个节点可以保存一个字节数组或一个整数值。

压缩列表的原理：压缩列表并不是对数据利用某种算法进行压缩的，而是将数据按照一定规则编码在一块连续的内存区域，目的是节省内存。

压缩列表的每个节点构成如下：

为啥redis 使用跳表而不是使用 red-black

redis使用跳表(ziplist)?

首先redis中跳表源码，跳表是skiplist？不是ziplist。ziplist在redis中是一个非常省内存redis中跳表源码的链表（代价是性能略低），所以在hash元素的个数很少（比如只有几十个），那么用这个结构来存储则可以在性能损失很小的情况下节约很多内存（redis是内存数据库啊，能省还是要省的）。好这个问题清楚redis中跳表源码了。

至于这个问题：请问，有人用C实现过红黑树么？实在看不懂。

不过提问者所引出的另一个问题倒是值得讨论一下，就是在server端，对并发和性能有要求的情况下，如何选择合适的数据结构（这里是跳跃表和红黑树）。

如果单纯比较性能，跳跃表和红黑树可以说相差不大，但是加上并发的环境就不一样redis中跳表源码了，如果要更新数据，跳跃表需要更新的部分就比较少，锁的东西也就比较少，所以不同线程争锁的代价就相对少了，而红黑树有个平衡的过程，牵涉到大量的节点，争锁的代价也就相对较高了。性能也就不如前者了。

不过这些对redis这个单进程单线程server来说都是浮云。