Redis为何这么快——数据存储角度

杜绝缓冲区溢出：使用C字符串的操作时，如果字符串长度增加（如strcat操作）而忘记重新分配内存，很容易造成缓冲区的溢出；而SDS由于记录了长度，相应的操作在可能造成缓冲区溢出时会自动重新分配内存，杜绝了缓冲区溢出。

四、List

List对象的底层实现是quicklist（快速列表，是ziplist 压缩列表 和linkedlist 双端链表 的组合）。Redis中的列表支持两端插入和弹出，并可以获得指定位置（或范围）的元素，可以充当数组、队列、栈等。

typedef struct listNode {  
 // 前置节点  
 struct listNode *prev;  
 // 后置节点  
 struct listNode *next;  
 // 节点的值  
 void *value;  
 } listNode;  
 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; 

•  rpush: listAddNodeHead ---O(1)
•  lpush: listAddNodeTail ---O(1)
•  push:listInsertNode ---O(1)
•  index : listIndex ---O(N)
•  pop:ListFirst/listLast ---O(1)
•  llen:listLength ---O(N)

4.1 linkedlist（双端链表）

此结构比较像Java的LinkedList，有兴趣可以阅读一下源码。

从图中可以看出Redis的linkedlist双端链表有以下特性：节点带有prev、next指针、head指针和tail指针，获取前置节点、后置节点、表头节点和表尾节点的复杂度都是O（1）。len属性获取节点数量也为O（1）。

与双端链表相比，压缩列表可以节省内存空间，但是进行修改或增删操作时，复杂度较高；因此当节点数量较少时，可以使用压缩列表；但是节点数量多时，还是使用双端链表划算。

4.2 ziplist（压缩列表）

当一个列表键只包含少量列表项，且是小整数值或长度比较短的字符串时，那么redis就使用ziplist（压缩列表）来做列表键的底层实现。

ziplist是Redis为了节约内存而开发的，是由一系列特殊编码的连续内存块(而不是像双端链表一样每个节点是指针)组成的顺序型数据结构；具体结构相对比较复杂，有兴趣读者可以看 Redis 哈希结构内存模型剖析。在新版本中list链表使用 quicklist 代替了 ziplist和 linkedlist：

quickList 是 zipList 和 linkedList 的混合体。它将 linkedList 按段切分，每一段使用 zipList 来紧凑存储，多个 zipList 之间使用双向指针串接起来。因为链表的附加空间相对太高，prev 和 next 指针就要占去 16 个字节 (64bit 系统的指针是 8 个字节)，另外每个节点的内存都是单独分配，会加剧内存的碎片化，影响内存管理效率。

quicklist 默认的压缩深度是 0，也就是不压缩。为了支持快速的 push/pop 操作，quicklist 的首尾两个 ziplist 不压缩，此时深度就是 1。为了进一步节约空间，Redis 还会对 ziplist 进行压缩存储，使用 LZF 算法压缩。

五、Hash

Hash对象的底层实现可以是ziplist（压缩列表）或者hashtable（字典或者也叫哈希表）。

Hash对象只有同时满足下面两个条件时，才会使用ziplist（压缩列表）：1.哈希中元素数量小于512个；2.哈希中所有键值对的键和值字符串长度都小于64字节。

（编辑：晋中站长网）

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