说到redis，大家的第一印象就是它快，它接收到一个键值对操作后，能以微秒级别的速度找到数据，并快速完成操作。我们知道redis是内存数据库，所有的操作都是在内存上实现的，这是它快的一个重要原因，那么，它另外一个重要原因就是redis高效的数据结构设计，下面我们一起来学习一下。

        简单来说，底层数据结构一共有 6 种，分别是简单动态字符串、双向链表、压缩列表、哈希表、跳表和整数数组。它们和数据类型的对应关系如下图所示：

         可以看到有三种数据类型底层使用了压缩列表：List，Hash，Sorted Set（有序集合）。另外Sorted Set 还使用了跳表这一数据结构。下面我们来详细分析一下这两种数据结构。 

        一. 跳表

        跳表（skiplists）是一种有序的数据结构，它通过在每个节点中维持多个指向其他的节点指针，从而达到快速访问队尾目的。

跳表的原理如图所示， 由 William Pugh 在Skip Lists: A Probabilistic Alternative to Balanced Trees论文中提出，是一种可以于平衡树媲美的层次化链表结构——查找、删除、添加等操作都可以在对数期望时间下完成。

        可以看到，从a到e跳表的层级越来越多，查询速度也会相应变快。我们查询的时候，是从上往下开始查找。这个查找过程就是在多级索引上跳来跳去，最后定位到元素。这也正好符合“跳”表的叫法。当数据量很大时，跳表的查找复杂度就是 O(logN)。 

       二. 压缩列表

         听到“压缩”两个字，直观的反应就是节省内存。之所以说这种存储结构节省内存,是相较于数组的存储思路而言的。我们知道,数组要求每个元素的大小相同,如果我们要存储不同长度的字符串,那我们就需要用最大长度的字符串大小作为元素的大小(假设是20个字节)。存储小于 20 个字节长度的字符串的时候，便会浪费部分存储空间。

         为了更好的利用数组的优势（排列紧凑，内存连续，CPU局部性原理优势），同时避免上述不足。我们可以对数组进行压缩。不过这样我们遍历的时候并不知道每个元素的大小，因此也就无法计算出下一个节点的具体位置，那么，redis压缩列表是如何解决这个问题的呢？

         压缩列表实际上类似于一个数组，数组中的每一个元素都对应保存一个数据。和数组不同的是，压缩列表在表头有三个字段 zlbytes、zltail 和 zllen，分别表示列表长度、列表尾的偏移量和列表中的 entry 个数；压缩列表在表尾还有一个 zlend，表示列表结束。

        压缩列表实现如图所示：         我们再来看entry，压缩列表节点的具体实现：

         上文说了，压缩列表的每个节点的长度是可以不一样的，而我们面对不同长度的节点又不可能直接sizeof(entry)，那么它是怎么访问下一个节点呢？压缩列表将一些必要的偏移量信息记录在了每一个节点里，使之能跳到上一个节点或下一个节点。

每个节点由三部分组成：previous_entry_length、encoding、content

• previous_entry_length: 记录上一个节点的长度，为了方便反向遍历ziplist
• encoding: 当前节点的编码规则，记录了节点的content属性所保存数据的类型以及长度
• content: 当前节点的值，可以是数字或字符串。

        在压缩列表中，如果我们要查找定位第一个元素和最后一个元素，可以通过表头三个字段的长度直接定位，复杂度是 O(1)。而查找其他元素时，就没有这么高效了，只能逐个查找，此时的复杂度就是 O(N) 了。 

        如果觉得对你有帮助，记得给博主点个赞再走哦~~