目录

• 数组和链表
• 链表
• 比照
• 总结

1、数组和链表

数组：
数组会在内存中开拓一块间断的空间存储数据，这种存储形式无利也有弊病。当获取数据的时候，间接通过下标值就能够获取到对应的元素，工夫复杂度为 O(1)。然而如果新增或者删除数据会挪动大量的数据，工夫复杂度为O(n)。 数组的扩容机制是：如果数组空间有余，会先开拓一块新的空间地址，将原来的数组复制到新的数组中。

链表：
链表不须要开拓间断的内存空间，其通过指针将所有的数据连接起来。新增或者删除的时候只须要将指针指向的地址批改就行了，工夫复杂度为O(1)。然而查问的工夫复杂度为O(n)。

2、链表

2.1、双向链表

双向链表是各个节点之间的逻辑关系是双向的。
双向链表中节点的组成是：prior： 指向以后节点的前置节点，data：以后节点存储的数据。next：指向以后节点的后置节点。

2.2、压缩链表

• 压缩链表是为了节约内存开发的。
• ziplist 是一个特地的双向链表，没有保护双向指针 prev next; 反而是存储上一个 entry 的长度和以后 entry 长度，通过长度推算出下一个元素在什么中央。
• 就义读取的性能，取得高效的存储空间，因为存储指针比存储 entry 长度更费内存，这就是典型的工夫换空间。

2.3、quicklist 链表

• 官网介绍：

    A doubly linked list of ziplists
    A generic doubly linked quicklist implementation

• 介绍:

quicklist 是一个双向链表，并且是一个 ziplist 的双向链表，ziplist 自身是一个维持数据项先后顺序的列表，而且数据项保留在一个间断的内存块种。

3、比照

3.1、双向链表

• 双端链表便于在表的两端进行 push 和 pop 操作，然而它的内存开销比拟大。
• 双端链表每个节点上除了要保留的数据之外，还要额定保留两个指针。
• 双端链表的各个节点是独自的内存块，地址不间断，节点多了容易产生内存碎片。

3.2、压缩列表

• ziplist 因为是一块间断的内存，所以存储效率很高。
• ziplist 不利于批改操作，每次数据变动都会引发一次内存的 realloc。
• 当 ziplist 长度很长的时候，一次 realloc 可能会导致大批量的数据拷贝，进一步升高性能。

3.3、quicklist 链表

• 空间效率和工夫效率的折中。
• 联合了双端链表和压缩列表的长处。

4、总结

在 redis 3.2 版本之前应用的是 双向链表和压缩链表 两种，因为双向链表占用的内存要比压缩链表高，所以创立链表时首先会创立 压缩链表 ，在适合的时机会转化成 双向链表 。redis 3.2 之后应用的是quicklist 链表。