Apakah struktur data asas Redis?

Set integer

Jika set mengandungi hanya beberapa elemen integer, Redis akan menggunakan set integer. Mula-mula lihat struktur data intset:

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

Malah, struktur data intset agak mudah difahami. Elemen penyimpanan data, panjang menyimpan bilangan elemen, iaitu saiz kandungan, dan pengekodan ialah kaedah pengekodan yang digunakan untuk menyimpan data.

Kita boleh tahu daripada kod bahawa jenis pengekodan termasuk:

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

Malah, kita boleh melihatnya. Jenis pengekodan Redis merujuk kepada saiz data. Sebagai pangkalan data dalam memori, reka bentuk ini diguna pakai untuk menjimatkan memori.

Memandangkan terdapat tiga struktur data dari kecil hingga besar, gunakan struktur data kecil sebanyak mungkin untuk menjimatkan memori semasa memasukkan data Jika data yang dimasukkan lebih besar daripada struktur data asal, pengembangan akan dicetuskan.

Terdapat tiga langkah untuk pengembangan:

1. Mengikut jenis elemen baharu, ubah suai jenis data keseluruhan tatasusunan dan peruntukkan semula ruang

2. Tukar data asal kepada jenis data baharu, letak semula di tempat yang sepatutnya dan simpan pesanan

3. Masukkan elemen baharu

Koleksi integer tidak menyokong operasi turun taraf Setelah dinaik taraf, ia tidak boleh diturunkan.

Senarai lompat

Senarai lompat ialah sejenis senarai terpaut, struktur data yang menggunakan ruang untuk bertukar masa. Senarai langkau menyokong O(logN) secara purata dan kerumitan O(N) paling teruk.

Senarai langkau terdiri daripada zskiplist dan berbilang zskiplistNode. Mari kita lihat struktur mereka dahulu:

/* 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;

Jadi berdasarkan kod ini kita boleh melukis gambar rajah struktur berikut:

Malah, jadual lompat ialah ruang penggunaan Struktur data perubahan masa menggunakan tahap sebagai indeks senarai terpaut.

Seseorang bertanya kepada pengarang Redis sebelum ini mengapa dia menggunakan jadual lompat dan bukannya pokok untuk membina indeks? Jawapan penulis ialah:

1. Simpan memori.

2. Apabila menggunakan ZRANGE atau ZREVRANGE, ia melibatkan senario operasi senarai terpaut biasa. Prestasi kerumitan masa adalah serupa dengan pokok seimbang.

3. Perkara yang paling penting ialah pelaksanaan jadual lompat adalah sangat mudah dan boleh mencapai tahap O(logN).

Senarai termampat

Senarai terpaut termampat Pengarang Redis memperkenalkannya sebagai senarai terpaut dua kali yang direka untuk menjimatkan memori sebanyak mungkin.

Struktur data yang diberikan dalam ulasan dalam kod untuk senarai termampat adalah seperti berikut:

zlbytes mewakili bilangan bait memori yang digunakan oleh keseluruhan senarai dimampatkan. 🎜> ialah nod senarai zip

zltail Menandai penghujung senarai dimampatkan

Terdapat juga satu penunjuk dalam senarai ini: zllen

offset kepala nod permulaan senarai entry

Offset kepala nod akhir senarai zlend

Offset hujung nod ekor senarai

Lihat struktur entri sekali lagi: ZIPLIST_ENTRY_HEAD

/*
 * 保存 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;

dalam urutan Terangkan parameter ini.

ZIPLIST_ENTRY_TAIL

Panjang nod sebelumnya Terdapat saiz tambahan di sini, yang sebenarnya merekodkan saiz prevrawlen. Untuk menjimatkan memori, Redis tidak secara langsung menggunakan panjang int lalai, tetapi menaik tarafnya secara beransur-ansur.

Begitu juga, ZIPLIST_ENTRY_END merekodkan panjang nod semasa dan

merekodkan panjang len.

ialah jumlah dua saiz yang dinyatakan di atas.

ialah jenis data nod ini. Perhatikan di sini bahawa jenis pengekodan hanya termasuk integer dan rentetan.

prevrawlen Penunjuk nod, tidak perlu menjelaskan terlalu banyak.
lenSatu perkara yang perlu diambil perhatian ialah setiap nod menyimpan panjang nod sebelumnya Jika nod dikemas kini atau dipadamkan, data selepas nod ini juga perlu diubah suai Senario kes terburuk ialah jika setiap Setiap nod berada pada titik sifar yang perlu dikembangkan, yang akan menyebabkan nod selepas nod ini mengubah suai parameter saiz, mencetuskan tindak balas berantai. Pada masa ini, kerumitan masa yang paling teruk untuk memampatkan senarai terpaut ialah O(n^2). Walau bagaimanapun, semua nod berada pada nilai kritikal, jadi kebarangkalian boleh dikatakan agak kecil. lensize

Atas ialah kandungan terperinci Apakah struktur data asas Redis?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!