Redis key-value结构组织

首先，Redis使用了一个全局哈希表来保存所有的键值对。这个全局哈希表，也就是一个存放哈希桶(entry)的数组。Redis可以用哈希算法算出某个key的哈希值，直接取到这个数组这个位置的元素，也就是O(1)的读写。每个entry包含了两到三个部分，一个是*key也就是指向键key的指针，一个*value指向值value的指针，一级有可能会有*next,当发生hash冲突时，使用链表存储值的下一个entry的位置指针。

冲突解决

上面提到了如果发生哈希冲突，会用一个链表的结构保存entry,一旦冲突变多势必影响读写性能，所以Redis会进行Rehash。Redis进行rehash的方式，是一开始就准备好两个数组h1, h2, h2为h1大小的两倍，使用h1的过程中，一旦h1元素多了，就将h1的内容拷贝到h2,然后释放h1。

为了保证rehash对读写业务影响尽可能小，Redis采用了渐进式rehash:开始rehash的时候，redis仍然正常处理客户端请求，但每处理一个请求就顺便从h1的第一个元素开始，把h1上的entries都拷贝到h2（这个思想倒是挺多地方有见到）。而且对于读的请求会先读h1没有就去读h2,而对于更新，删除操作也会对两个表进行，新增只会新增到h2,保证h1的数量会只减少不增。

Redis 数据结构

Redis有很多数据类型，这些数据类型都有一些元数据需要记录。Redis会封装这些数据在一个RedisObject里面，我们看看这个RedisObject长啥样：

RedisObject主要包括了8字节的元数据和8字节的指针。元数据里有保存的数据类型，编码方式（底层实现），LRU即最后一次访问的时间，refcount引用计数。

RedisObject对整型数和简单字符串也做了优化，如果是整型数，*ptr就直接存整型数；如果是字符串，那么根据字符串大小（是否超过44字节）分为embstr编码方式，即ptr后紧凑地再分配一块内存存字符串，和raw方式，指针指向字符串。

应用数据结构

我们知道key就是一个字符串，而value,Redis提供了多种数据结构可以选择，包括常见的:String, List, Hash, Set, Sorted Set,和特殊的一些例如Bitmap,HyperLogLog和GEO。

底层实现的数据结构

Redis底层实现主要依靠了SDS(Simple Dynamic String),双向链表,压缩列表,哈希表,跳表,整数数组，其和应用数据结构的关系如下表：

压缩列表

压缩列表其实就是一个数组，只是比数组在表头多了三个字段zlbytes列表长度，zltail列表尾部偏移量，zllenentry的个数，表尾多了一个字段zlend表示结束，如下图：

在压缩列表中，查找第一个和最后一个元素的时间复杂度是O(1),而其他的则是O(N)

跳表

之前讲过这个，这里就不多说了//todo