Redis의 기본 데이터 구조는 무엇입니까?

Integer set

세트에 소수의 정수 요소만 포함된 경우 Redis는 정수 세트 intset을 사용합니다. 먼저 intset의 데이터 구조를 살펴보세요.

typedef struct intset {
    // 编码方式
    uint32_t encoding;
    // 集合包含的元素数量
    uint32_t length;
    // 保存元素的数组
    int8_t contents[];
} intset;

사실 intset의 데이터 구조는 비교적 이해하기 쉽습니다. 데이터 저장 요소인 길이는 요소의 개수, 즉 콘텐츠의 크기를 저장하며, 인코딩은 데이터를 저장하는 데 사용되는 인코딩 방법입니다.

인코딩 유형에 다음이 포함된다는 것을 코드에서 알 수 있습니다.

#define INTSET_ENC_INT16 (sizeof(int16_t))
#define INTSET_ENC_INT32 (sizeof(int32_t))
#define INTSET_ENC_INT64 (sizeof(int64_t))

실제로 볼 수 있습니다. Redis 인코딩 유형은 데이터 크기를 나타냅니다. 인메모리 데이터베이스로서 메모리 절약을 위해 이 설계를 채택했습니다.

작은 것부터 큰 것까지 세 가지 데이터 구조가 있으므로 데이터 삽입 시 메모리를 절약하기 위해 가능한 작은 데이터 구조를 사용하세요. 삽입된 데이터가 원래 데이터 구조보다 클 경우 확장이 발생합니다.

확장에는 세 가지 단계가 있습니다.

1. 새 요소 유형에 따라 전체 배열의 데이터 유형을 수정하고 공간을 재할당합니다.

2. 원본 데이터를 새 데이터 유형으로 바꾸고 교체합니다. it 새 요소를 삽입하기 전에

3. 위치에 있어야 하며 순서를 유지해야 합니다.

정수 컬렉션은 한 번 업그레이드되면 다운그레이드할 수 없습니다.

점프 리스트

점프 리스트는 연결 리스트의 일종으로, 공간을 이용해 시간을 교환하는 데이터 구조입니다. 건너뛰기 목록은 평균적으로 O(logN)을 지원하고 최악의 경우 O(N) 복잡성을 지원합니다.

스킵 목록은 zskiplist와 여러 zskiplistNode로 구성됩니다. 먼저 구조를 살펴보겠습니다.

/* ZSETs use a specialized version of Skiplists *//*
 * 跳跃表节点
 */

typedef struct zskiplistNode {
    // 成员对象
    robj *obj;
    // 分值
    double score;
    // 后退指针
    struct zskiplistNode *backward;
    // 层
    struct zskiplistLevel {
        // 前进指针
        struct zskiplistNode *forward;
        // 跨度
        unsigned int span;
    } level[];

    } zskiplistNode;
        
/*
 * 跳跃表
 */

typedef struct zskiplist {
    // 表头节点和表尾节点
    struct zskiplistNode *header, *tail;
    // 表中节点的数量
    unsigned long length;
    // 表中层数最大的节点的层数
    int level;

} zskiplist;

이 코드를 기반으로 다음과 같은 구조 다이어그램을 그릴 수 있습니다.

사실 점프 목록은 공간을 사용하여 시간을 교환하고 레벨을 다음과 같이 사용하는 데이터 구조입니다. 연결리스트의 인덱스

누군가 Redis 작성자에게 왜 인덱스를 구축하기 위해 트리 대신 점프 테이블을 사용하는지 물었습니다. 저자의 답변은 다음과 같습니다.

1. 메모리를 절약하세요.

2. ZRANGE 또는 ZREVRANGE를 사용하는 경우 일반적인 연결 목록 작업 시나리오가 포함됩니다. 시간 복잡도의 성능은 균형 트리의 성능과 유사합니다.

3. 가장 중요한 점은 점프 테이블의 구현이 매우 간단하고 O(logN) 수준에 도달할 수 있다는 것입니다.

압축된 목록

압축된 연결 목록 Redis의 저자는 메모리를 최대한 절약하기 위해 설계된 이중 연결 목록이라고 소개합니다.

압축 목록 코드의 주석에 제공된 데이터 구조는 다음과 같습니다.

zlbytes는 전체 압축 목록에서 사용하는 메모리 바이트 수를 나타냅니다.zlbytes 表示的是整个压缩列表使用的内存字节数

zltail 指定了压缩列表的尾节点的偏移量

zllen 是压缩列表 entry 的数量

entry 就是 ziplist 的节点

zlend 标记压缩列表的末端

这个列表中还有单个指针：

ZIPLIST_ENTRY_HEAD 列表开始节点的头偏移量

ZIPLIST_ENTRY_TAIL 列表结束节点的头偏移量

ZIPLIST_ENTRY_END 列表的尾节点结束的偏移量

再看看一个 entry 的结构：

/*
 * 保存 ziplist 节点信息的结构
 */

typedef struct zlentry {
    // prevrawlen ：前置节点的长度
    // prevrawlensize ：编码 prevrawlen 所需的字节大小
    unsigned int prevrawlensize, prevrawlen;
    // len ：当前节点值的长度
    // lensize ：编码 len 所需的字节大小  
    unsigned int lensize, len;
    // 当前节点 header 的大小
    // 等于 prevrawlensize + lensize
    unsigned int headersize;
    // 当前节点值所使用的编码类型
    unsigned char encoding;
    // 指向当前节点的指针
    unsigned char *p;

} zlentry;

依次解释一下这几个参数。

prevrawlen 前置节点的长度，这里多了一个 size，其实是记录了 prevrawlen 的尺寸。Redis 为了节约内存并不是直接使用默认的 int 的长度，而是逐渐升级的。
同理 len 记录的是当前节点的长度，lensize 记录的是 len 的长度。
headersize 就是前文提到的两个 size 之和。
encoding 就是这个节点的数据类型。这里注意一下 encoding 的类型只包括整数和字符串。
p

zltail 압축 목록의 꼬리 노드 오프셋을 지정합니다.

zllen은 압축 목록의 항목 수입니다. 🎜🎜entry는 압축 목록의 노드입니다. ziplist 🎜🎜zlendcode> 압축 목록의 끝을 표시합니다. 🎜🎜이 목록에는 단일 포인터도 있습니다: 🎜🎜ZIPLIST_ENTRY_HEAD 압축 목록의 시작 노드의 헤드 오프셋 list 🎜🎜ZIPLIST_ENTRY_TAIL 목록의 끝 노드의 헤드 Offset 🎜🎜ZIPLIST_ENTRY_END 목록의 끝 노드 끝의 오프셋🎜🎜구조를 살펴보세요. 항목을 다시 입력하세요. 🎜rrreee🎜이 매개변수를 차례로 설명하세요. 🎜🎜prevrawlen 여기에는 prevrawlen의 크기를 실제로 기록하는 추가 크기가 있습니다. 메모리 절약을 위해 Redis는 기본 int 길이를 직접 사용하지 않고 점진적으로 업그레이드합니다.
마찬가지로 len은 현재 노드의 길이를 기록하고, lensize는 len의 길이를 기록합니다.
headersize는 위에서 언급한 두 가지 크기의 합입니다.
인코딩은 이 노드의 데이터 유형입니다. 여기서 인코딩 유형에는 정수와 문자열만 포함된다는 점에 유의하세요.
p 노드의 포인터이므로 너무 많이 설명할 필요가 없습니다. 🎜🎜한 가지 주의할 점은 각 노드가 이전 노드의 길이를 저장한다는 것입니다. 노드가 업데이트되거나 삭제되면 이 노드 이후의 데이터도 수정되어야 합니다. 최악의 시나리오는 각 노드가 0에 있는 경우입니다. 확장해야 하는 경계 지점은 이 노드 뒤의 노드가 크기 매개변수를 수정하게 하여 연쇄 반응을 유발합니다. 이때 연결리스트 압축의 최악의 시간복잡도는 O(n^2)이다. 그러나 모든 노드가 임계값에 있으므로 확률은 상대적으로 낮다고 할 수 있습니다. 🎜

위 내용은 Redis의 기본 데이터 구조는 무엇입니까?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!