面试官：你看过Redis数据结构底层实现吗？

引用https://segmentfault.com/a/1190000016901154中的两个图：

6.1 源码

ziplist没有明晰界说布局体，这里只作或许的演示。

typedef struct entry {  
     /*前一个元素长度必要空间和前一个元素长度*/  
    unsigned int prevlengh;  
     /*元素内容编码*/  
    unsigned char encoding;  
     /*元素现实内容*/  
    unsigned char *data;  
}zlentry;  

typedef struct ziplist{  
     /*ziplist分派的内存巨细*/  
     uint32_t zlbytes;  
     /*到达尾部的偏移量*/  
     uint32_t zltail;  
     /*存储元素实体个数*/  
     uint16_t zllen;  
     /*存储内容实体元素*/  
     unsigned char* entry[];  
     /*尾部标识*/  
     unsigned char zlend;  
}ziplist; 

第一次看也许会出格蒙蔽，你细细的把我这段话看完就必然能懂。

Entry的说明

entry布局体内里有三个重要的字段：

1.  previous_entry_length: 这个字段记录了ziplist中前一个节点的长度，什么意思？就是说通过该属性可以举办指针运算到达表尾向表头遍历，这个字段尚有一个大题目下面会讲。
2.  encoding:记录了数据范例(int16? string?)和长度。
3.  data/content: 记录数据。

连锁更新

previous_entry_length字段的说明

上面有说到，previous_entry_length这个字段存放上个节点的长度，那默认长度给分派几多呢?redis是这样分的，假如前节点长度小于254,就分派1字节，大于的话分派5字节，那题目就来了。

假如前一个节点的长度刚开始小于254字节，其后大于254,那不就存放不下了吗？ 这就涉及到previous_entry_length的更新，可是改一个必定不可阿，后头的节点内存信息都必要改。以是就必要从头分派内存，然后连锁更新包罗该受影响节点后头的全部节点。

除了增进新节点会激发连锁更新、删除节点也会触发。

7. 快速列表(quicklist)

一个由ziplist构成的双向链表。可是一个quicklist可以有多个quicklist节点，它很像B树的存储方法。是在redis3.2版本中新加的数据布局，用在列表的底层实现。

布局体源码

表头布局：

typedef struct quicklist { 
    //指向头部(最左边)quicklist节点的指针 
    quicklistNode *head;  
    //指向尾部(最右边)quicklist节点的指针 
    quicklistNode *tail;  
    //ziplist中的entry节点计数器 
    unsigned long count;        /* total count of all entries in all ziplists */  
    //quicklist的quicklistNode节点计数器 
    unsigned int len;           /* number of quicklistNodes */  
    //生涯ziplist的巨细，设置文件设定，占16bits 
    int fill : 16;              /* fill factor for individual nodes */  
    //生涯压缩水平值，设置文件设定，占16bits，0暗示不压缩 
    unsigned int compress : 16; /* depth of end nodes not to compress;0=off */ 
} quicklist; 

（编辑：湖南网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!