北京网站建设方案外包,怎么设计门户网站,建设一个网站要学什么,电子商务网站建设开题报告Redis数据结构
Redis新旧版本中一共出现过八种数据结构#xff0c;分别是SDS、双向链表、压缩列表、整数集合、哈希表、跳表、quicklist、listpack。
SDS
SDS是用于存储Redis中字符串的数据结构#xff0c;Redis底层使用的语言是C语言#xff0c;因此字符串也是C语言的字…Redis数据结构
Redis新旧版本中一共出现过八种数据结构分别是SDS、双向链表、压缩列表、整数集合、哈希表、跳表、quicklist、listpack。
SDS
SDS是用于存储Redis中字符串的数据结构Redis底层使用的语言是C语言因此字符串也是C语言的字符串。然而C语言字符串存在一些问题。
1.获取长度时间复杂度为O(N)因为C语言中没有预置的字符串数据类型而是用一个以“/0”结尾的字符数组代替的所以要获取字符串长度的话就需要遍历整个数组数组长度越大消耗时间就越多。
2.无法存储二进制数据因为C语言字符串就是以/0结尾的字符数组所以如果存储二进制数据的话可能会含有/0的内容会混淆数组结尾的/0。
3.存在缓冲区溢出的风险因为C语言不像Java等语言有自己的自动内存管理机制如Java的垃圾回收器而是依靠程序员手动管理内存因此字符数组在添加内容时就可能会导致缓冲区溢出的问题。
为了解决这些问题Redis中的字符串在原来的基础上添加了三个元数据分别是len、alloc、flags分别代表长度、空间长度、SDS类型。具体来说len记录了字符串的长度这样在获取字符串长度的时候直接从这个字段获取就行时间复杂度为O(1)而且由于len表明了字符串的长度因此字符串最后一位就不是必须使用“/0”结尾所以可以存储二进制数据
alloc则记录了字符串的空间大小在修改字符串的时候首先会查看alloc大小是否满足如果不满足的话会进行扩容小于1MB翻倍大于1MB增加1MB这样就能避免缓冲区溢出的问题
flags用来表示不用类型的SDS一共有5种类型分别是sdshdr5、sdshdr8、sdshdr16、sdshdr32和sdshdr64。这五种类型的区别在于数据结构中的len和alloc成员变量的数据类型不同因此字符串可以用来存放不同类型的数据而不是只能为原来的字符型。
链表
由于C语言中没有链表这一数据结构所以Redis自己实现了一个双向链表的数据结构。对于每一个节点来说拥有前置节点、后置节点、节点值三个属性而链表在节点的基础上封装了头结点、尾结点、节点复制函数、节点释放函数、节点比较函数、链表节点数量等属性和方法。
对链表的属性和方法中可以看出该链表对于获取节点的上/下一个节点、头/尾节点、节点数量等操作都非常快而且链表节点中可以保存不同类型值。
但是也有缺陷因为链表和数组不同内存地址并不是连续的所以不像数组那样可以充分利用CPU缓存加速访问而且每添加一个节点都需要为其元数据等添加额外的内存增加了内存的开销。
压缩列表
压缩列表相对于链表来说内存地址是连续的和数组一样可以充分地利用CPU缓存提高了查询的速度而且会针对不同长度的数据进行相应编码这种方法能有效地节省内存开销。
在Redis中List、Hash、Zset等数据类型在包含的元素数量较少的情况下才会使用到压缩列表存储数据。
除此之外其他和列表不同的是压缩列表在表头有几个默认字段分别为zlbytes列表占用内存的字节数、zltail列表尾部的偏移量可以理解为列表的容量大小、zllen列表包含的节点数量、zlend列表的结束点。这些字段能够帮助快速获取列表大小、高效访问尾元素、元素数量等。
压缩列表中的节点也有自己的元数据分别为prevlen前一个节点的长度、encoding当前节点的数据类型和长度、data当前节点的实际数据。由此可以看出不同节点的空间大小会根据其实际的数据类型进行分配节省了内存。
连锁更新问题由于一个节点中有prevlen属性记录上一个节点的大小因此当插入节点的时候如果插入节点的下一个节点中的prevlen长度不足以标明节点的大小的时候那么就需要更新下一个节点的大小也就是增加其prevlen属性大小进而也就改变了下一个节点的大小以此类推也可能改变其他节点。
尽管压缩列表能够通过连续地址和类型分配节省内存提供一些较为高效的数据操作但是当其所包含的元素数量过多时由于是一片连续的内存空间就可能导致重新分配内存地址导致性能下降。
哈希表
Redis中的哈希表是一个数组每个元素指向哈希表节点哈希表节点中除了值以外还有指向下一个哈希表节点的指针形成单向链表因此和Java中的hashmap类似使用链表的结构存放hash冲突的元素。
不过这里的负载因子算法是哈希表中的节点数/哈希表大小因此当负载因子大于等于1的时候就需要进行扩容rehash操作。
整数集合
当一个Set中只有整数值元素的时候就会使用整数集这个数据结构作为底层实现。
当将一个新元素添加进整数集合的时候并且这个元素的长度大于整数集合中的最大元素长度时就会触发整数集合的升级一旦升级后就无法降级。由于添加新的元素才触发升级所以这个机制能够节省内存资源。
跳表
Redis中唯一使用到了跳表的数据类型是ZsetZset中使用到了跳表哈希表两种数据结构跳表这一数据结构能够实现范围查询。
链表查询元素效率很低而跳表在链表的基础上实现了一种多层结构简单来说就是按照一定的跨度两个节点之间的距离将原来的链表进行了分层不同的跨度能够实现跳跃式的查询。因此跳表中存在多级索引占用的空间较大但是查询效率得到提升。
quicklist
在Redis3.2后list数据类型的底层实现由原来的双向链表或压缩列表改为了quicklist解决了由于压缩列表无法存储大量数据的问题。
quicklist的结构和链表类似但是将链表的每个元素改为设置一个压缩列表并且控制每个链表节点中压缩列表的大小这样就能利用压缩列表的优势同时避免了一个压缩列表存储大量数据的问题。
在quicklist中并不是所有元素都会进行压缩在两端处有一些数据会频繁地进行操作像lpush、rpush、lpop、rpop等操作都是直接访问两端节点数据因此这部分数据可以不用进行压缩以减少性能损耗除此之外如果有的压缩列表中只有一个元素那也不会为之创建一个压缩列表。
quicklist允许对数据进行压缩原理是如果数据与之前的数据重复则只会记录重复的位置和重复的长度。
listpack
虽然quicklist降低了连锁更新的概率和造成的影响但是没有完全避免因为数据结构中还是用了压缩列表因此Redis在5.0后设计了一个新的数据结构listpack来替代压缩列表在listpack中取消了prevlen字段避免了因为更新而可能需要不断更新相邻节点的prevlen的隐患。
listpack头也有两个属性分别为listpack总字节数和元素数量在尾部有结尾标识。
每个listpack节点中有lenencodingdata三个字段其中encoding定义元素的编码类型data为实际存放的数据len则是encodingdata的总长度。所以listpack节点没有记录前一个节点长度而是只记录当前节点长度所以向listpack中加入新元素的时候不会影响其他节点进而避免了连锁更新问题。
由于取消了prevlen字段listpack无法像压缩列表那样进行双向遍历但是节省了内存避免了连锁更新。
