自己做网站出口,电子商务服务网站,河南怎么样做网站,wordpress链接的index.php文章目录一.引言二.redis的特点三.Redis的数据结构a.字符串b.hashc.listd.sete.zset(有序集合)一.引言
redis是一个开源的使用C语言编写、支持网络、可基于内存亦可持久化的日志型、key-value的NoSQL数据库。
通常使用redis作为缓存中间件来降低数据库的压力#xff0c;除此…
文章目录一.引言二.redis的特点三.Redis的数据结构a.字符串b.hashc.listd.sete.zset(有序集合)一.引言
redis是一个开源的使用C语言编写、支持网络、可基于内存亦可持久化的日志型、key-value的NoSQL数据库。
通常使用redis作为缓存中间件来降低数据库的压力除此之外redis还有很多使用场景比如分布式锁、计数、队列等等。
二.redis的特点
读写速度快。每秒10w次左右。原因 数据存储在内存中访问速度快采用单线程的架构避免上下文的切换和多线程带来的竞争不存在加锁和释放锁的操作减少了CPU的消耗采用了非阻塞IO多路复用机制 数据结构丰富。redis不仅仅支持简单的key-value类型的数据同时还提供list、set、zset、hash等数据结构支持持久化。RDB和AOF两种持久化策略支持高可用。可以使用主从复制并且提供哨兵机制保证服务器的高可用客户端语言多。涵盖了所有主流编程语言
三.Redis的数据结构
常见的五种数据类型string、list、set、zset、hash
redis的这些数据结构在底层都是使用redisObject来进行表示的。redisObject有三个重要的属性分别是type、encoding、ptr。
type代表保存的value的类型。通常有以下五种
字符串REDIS_STRING列表 REDIS_LIST集合 REDIS_SET有序集合 REDIS_ZSET字典 REDIS_HASH
encoding表示保存的value的编码通常有以下几种
字符串REDIS_ENCODING_RAW整数REDIS_ENCODING_INT哈希表REDIS_ENCODING_HTzipmapREDIS_ENCODING_ZIPMAP双端链表REDIS_ENCODING_LINKEDLIST压缩列表REDIS_ENCODING_ZIPLIST整数集合REDIS_ENCODING_INTSET跳跃表REDIS_ENCODING_SKIPLIST
ptr是一个指针指向实际保存的value的数据结构
数据类型和编码方式是有一定关系的所以数据类型和编码方式是可以确定底层采用什么数据结构的。 a.字符串
字符串对象的encoding有三种分别是int、raw、embstr
常用命令有set、get、decr、incr、mget
底层不是使用c语言的字符串动态类型而是自己开发了一种数据类型SDSSimple Dynamic String动态字符串进行存储
struct sdshdr{int len;/*字符串长度*/int free;/*未使用的字节长度*/char buf[];/*保存字符串的字节数组*/
}SDS与C语言的字符串有什么区别
C语言获取字符串长度是从头到尾遍历时间复杂度是O(n)而SDS有len属性记录字符串长度时间复杂度尾O(1)避免缓冲区溢出。SDS在需要修改时会先检查空间是否满足大小如果不满足则先拓展至所需大小再进行修改操作。空间预分配。当SDS需要进行扩展时redis会为SDS分配好内存并且根据特定的算法分配多余的free空间避免连续执行字符串带来的内存分配的消耗惰性释放。如果需要缩短字符串不会立即回收多余的内存空间而是用free近路剩余的空间以便下次扩展时使用避免了再次分配内存的操作二进制安全。c语言存储字符串是采用N1的字符串数据末尾使用‘\0’标识字符串的结束如过我们存储的字符串中出现‘\0’那么就会出现识别出错而SDS因为记录了字符串的长度len则没有这个问题。
redis规定了字符串的长度不得超过512M
b.hash
哈希对象的编码方式有两种ziplist和hashtable
当哈希对象保存的键值对数量小于512并且所有键值对的长度都小于64自己饿时使用ziplist存储否则使用hashtable存储。
redis中的hashtable跟java中的hashMap类似都是通过数组链表的实现方式解决部分的哈希冲突。
typedf struct dict{dictType *type;//类型特定函数包括一些自定义函数这些函数使得key和value能够存储void *private;//私有数据dictht ht[2];//两张hash表 int rehashidx;//rehash索引字典没有进行rehash时此值为-1unsigned long iterators; //正在迭代的迭代器数量
}dict;typedef struct dictht{//哈希表数组dictEntry **table;//哈希表大小unsigned long size;//哈希表大小掩码用于计算索引值//总是等于 size-1unsigned long sizemask;//该哈希表已有节点的数量unsigned long used;
}dictht;typedf struct dictEntry{void *key;//键union{void val;unit64_t u64;int64_t s64;double d;}v;//值struct dictEntry *next//指向下一个节点的指针
}dictEntry;扩容和收缩的过程
如果执行扩展操作会基于哈希表创建一个大小等于ht[0].used*2n的哈希表每次都是根据原哈希表已使用的空间扩大一倍创建另一个哈希表。相反如果执行的是收缩操作每次收缩是根据已使用精简缩小一倍创建一个新的哈希表。重新利用hash算法计算索引值然后将键值对放到新的哈希表位置上。所有键值对都迁徙完毕后释放原哈希表的内存空间。
在redis执行扩容和收缩的规则是
服务器目前没有执行bgsave或bgrewrite命令并且负载因子大于等于1服务器目前没有执行bgsave或bgrewrite命令并且负载因子大于等于5
负载因子哈希表已保存节点数量/哈希表大小
渐进式rehash
扩容和收缩不是一次性集中式完成而是通过多次逐渐地完成的。为什么要采用这种方式呢在键值对数量达到几十万几百万的键值对要一次性进行rehash势必会导致redis性能严重下降自然而然地redis开发者就想到采用渐进式rehash过程如下
使用rehashindex字段保存迁移的进度从0开始在迁移过程中ht[0]和ht[1]同时保存数据ht[0]指向旧哈希表ht[1]指向新hash表每次对字典进行添加、删除、查找或更新操作是程序除了执行指定的操作外还会顺带将ht[0]的元素迁移到ht[1]中迁移完成后rehashindex设置为-1rehash完成后ht[0]指向的旧表会被释放之后会将新表的持有权交给ht[0]再重置ht[1]指向NULL
渐进式rehash的优缺点
优点
rehash操作分散到每一个字典操作和定时函数上避免了一次性集中式rehash带来的服务器压力
缺点
rehash期间需要使用两个hash表内存占用稍大
常用命令
hget、hset、hgetall
c.list
列表对象的编码有两种分别是ziplist、linkedlist。当列表的长度小于512并且所有元素的长度都小于64字节时使用ziplist存储否则使用linkedlist存储
redis中的linkedlist类似于java的linkedlist是一个双向链表插入和删除操作效率比较快时间复杂度是O(1)
typedef struct listNode {struct listNode *prev;struct listNode *next;void *value;
} listNode;typedef struct listIter {listNode *next;int direction;
} listIter;typedef struct list {listNode *head;listNode *tail;void *(*dup)(void *ptr);void (*free)(void *ptr);int (*match)(void *ptr, void *key);unsigned long len;
} list;常用命令
lpush、rpush、lpop、rpop、lrange
d.set
特点无序、不重复跟java的hashset类似。它的编码有两种分别是intset和hashtable。如果value可以转换成整数值并且长度不超过512的话就使用intset存储否则采用hashtable
typedef struct intset{uint32_t encoding;//编码方式uint32_t length;//集合包含的元素数量int8_t contents[];//保存元素的数组
}intset;encoding的值有三种分别是INTSET_ENC_INT16、INTSET_ENC_INT32、INTSET_ENC_INT64代表着整数的取值范围。redis会根据添加进来的元素的大小选择不同的类型进行存储。尽可能地节省内存空间。
INTSET_ENC_INT16–INTSET_ENC_INT32–INTSET_ENC_INT64的升级过程
根据新元素的类型扩展数组contents的空间从尾部将数据插入根据新编码格式重置之前的值因为这是的contents存在着两种编码的值。从插入的数据的位置也就是尾部从后到前将之前的数据按照新的编码格式进行移动和设置。从后往前是为了防止数据被覆盖
优点节省内存缺点升级会消耗系统资源。而且升级是不可逆的一旦升级编码就会一直保存升级后的状态
set常见的命令有
sadd、spop、smembers、sunion
redis为set类型提供了求交集、并集、差集的操作可以非常方便地实现比如共同关注、共同爱好、共同好友等功能
e.zset(有序集合)
zset和set一样是不可重复的区别在于多了score值用来代表排序的权重。也就是当你需要一个有序的不可重复的集合列表时就可以考虑使用这种数据类型。
zset的编码方式有两种分别是ziplist、skiplist。当zset的长度小于128并且所有元素的长度都小于64字节时使用ziplist存储否则使用skiplist存储。 跳远表的数据结构设计如上设计的好处是什么呢
查询的时候可以减少时间复杂度如果是链表我们要插入并且保持有序的话那就要从头节点开始遍历遍历到合适的位置然后插入如果这样性能肯定是不理想的。
而使用跳表可以像二分查找一样定位到插入的点查找过程
L4查询87查询一次L3查询到在24、87之间需要查询2次L2查询到48查询1次L1查询到37、48查询两次确定插入点在37、48之间
