Skip to content

Latest commit

 

History

History
65 lines (63 loc) · 2.69 KB

2.高级数据结构.md

File metadata and controls

65 lines (63 loc) · 2.69 KB
Raw

redis-study

1.redisObject

typedef struct redisObject {
    unsigned type:4;
    unsigned encoding:4;
    unsigned lru:LRU_BITS; /* LRU time (relative to global lru_clock) or
                            * LFU data (least significant 8 bits frequency
                            * and most significant 16 bits access time). */
    int refcount;
    void *ptr;
} robj;
  • type存储redis的对象类型：(OBJ_STRING 0) (OBJ_LIST 1) (OBJ_SET 2) (OBJ_ZSET 3) (OBJ_HASH 4),rediscli中type+对象名 获取
  • encoding记录对象的底层数据结构，如ziplist和hashtable等等,rediscli中object+encoding+对象名 获取
  • lru记录最后一次被访问的时间，当超过maxmemory时，会优先选择最久没使用的进行回收
  • lfu对数计数器，使用object freq 查看对象的使用次数
  • refcount与共享对象相关，常见10000个字符串，整数0-9999 浮点数是使用字符串存储，共享对象共享lru，判断字符串相等时间复杂度为O(n)
  • prt类似于object,可以存储任意对象
/* 创建字符串 raw或embstr 还有一种int(tryObjectEncoding该方法中) int有共享int和非共享 */
robj *tryCreateStringObject(const char *ptr, size_t len) {
    if (len <= OBJ_ENCODING_EMBSTR_SIZE_LIMIT) /* 44 */
        return createEmbeddedStringObject(ptr,len);   
    else
        return tryCreateRawStringObject(ptr,len);
}
  • embstr与raw比较
  • Bulk request max size ：512M

2.hash

  • Redis的hash对象采用了两种方式，ziplist或dict, 超过64会转为hashtable，可通过hash-max-ziplist-value配置
  • ziplist作为底层对象时，其查找的时间复杂度为O(n)

3.set

  • Redis的set对象采用了两种方式，intset或dict
  • 由intset转dict的操作是不可逆的,参数set-max-intset-entries可在配置文件中进行修改
  • dict作为底层对象时，value值为null,intset作为底层对象时，其查找的时间复杂度为O(logN)
robj *setTypeCreate(sds value) {
    if (isSdsRepresentableAsLongLong(value,NULL) == C_OK)
        return createIntsetObject();
    return createSetObject();
}

4.zset

  • 在skiplist的基础上，还需要创建dict的原因是当需要获取某个元素的score时，skplist的时间复杂度为O(n)，而dict时间复杂度为O(1)
  • 当底层为ziplist时，该操作依旧为O(n)
  • skiplist和dict共享元素和分值（指针复制）
  • 由ziplist转skiplist的操作是不可逆的
  • 两个参数zset-max-ziplist-entries和zset-max-ziplist-value可在配置文件中进行修改
typedef struct zset {
    dict *dict;
    zskiplist *zsl;
} zset;