Redis设计与实现之基本数据结构（三）
跳跃表使用场景跳跃表在大多数时间内可以与平衡树媲美，而且跳跃表的设计要比平衡树简单，所以采用跳跃表。
在Redis中，使用跳跃表作为有序集合的底层实现。如果一个有序集合的元素数量比较多，或者有序集合的成员是比较长的字符串时，Redis会采用跳跃表来作为有序集合的底层实现。
具体设计123456789101112131415161718192021222324252627282930313233// 跳跃表结构体如下typedef struct zskiplist { // 跳跃表的头节点以及尾节点 struct skiplistNode *head, *tail; // 跳跃表节点数量 unsigned long length; // 跳跃表中节点最深节点的深度 int level; } zskiplist;// 跳跃表中每一个节点typedef struct skiplistNode { // 层 struct skiplistLevel { // 前进指针 ...
Redis设计与实现之基本数据结构（二）
字典具体结构字典又称符号表、关联数组或映射，是一种用于保存键值对的抽象数据结构。
Redis字典使用哈希表作为底层实现，一个哈希表可以有多个哈希表节点，每一个哈希表节点保存了字典中的一个键值对。
12345678910111213141516171819202122232425262728293031C// 哈希表结构typedef struct dictht { // 哈希表数组 dictEntry **table; // 哈希表大小 unsigned long size; // 哈希表大小掩码，用于计算索引值，总是等于size - 1 unsigned long sizemask; // 该哈希表已有的节点数量 unsigned long used;} dictht;// 哈希表节点typedef struct dictEntry { // 键 void *key; // 值 union { void *val; ...
Redis设计之基本数据结构（一）
简单动态字符串SDS作用1、保存数据库中字符串的值
2、AOF中的缓冲区以及客户端状态中的缓冲区
具体结构代码1234567891011struct sdshdr { // 记录buf数组中已经使用字节的数量 // 等于SDS所保存字符串的长度 int len; // 记录buf数组中未使用字节的数量 int free; // 字节数组，用于保存字符串 char buf[];}
因为C语言的字符串在每次赋值前都需要申请空间，而且获取长度需要遍历整个字符串，所以Redis采用上述设计。
SDS的好处1、可以在O(1)的时间复杂度之内获取到字符串的长度。
2、杜绝缓冲区的溢出。
SDS的API每次操作SDS时，会先检查SDS空间是否满足，如果不满足会将空间扩展至足够的大小，然后才执行实际的修改。
3、减少修改字符串时带来的内存分配的次数。在C语言中，每一次修改字符串都需要重新分配内存空间，而SDS采用空间预分配和惰性删除来减少分配次数
1）空间预分配：如果需要对SDS进行扩容，如果扩容后SDS的长度小于1mb ...