...类型的底层数据结构

  • 时间:
  • 浏览:0
  • 来源:跟我学网络

最后发布:2018-07-12 19:01:30首次发布:2018-07-12 19:01:30

前言:

阅读 redis设计与实现 一书的记录。未完待续。。。

redis我们都知道有5种数据类型,分别是string,list,hash,set,zset,那么你知道它们的底层数据结构实现吗?

redis底层有6种数据结构,分别是简单动态字符串(SDS),链表,字典,跳跃表,整数集合,压缩列表

每种数据类型都有着2种以上的数据结构实现,在不同状态下会进行数据结构的转换。现在来看看这6种数据结构是什么吧!

1.简单动态字符串(SDS)

2.链表



3.字典





其中渐进式hash能有效解决重新分配hash表带来的服务器停顿问题,不一次性把所有的数据迁移到新的hash表上,而是每次增加,删除,修改后把一个index上的所有数据移动到新hash表中。

过程如下:



4.跳跃表





每个节点的生成都会随机产生1到32个层,来给前面的节点来”跳跃“

5.整数集合



当编码方式不足以应对过大的整数时,会调整编码方式,把在整数集合里的数的编码调整为新的编码方式,再把需要加入的大整数加入进来。编码方式只能升级不能降级。

6.压缩列表





压缩链表由于保留了前面节点的长度和最后节点的位置,能够有效的向后遍历,但不足之处就是调整了一个节点的大小可能会形成羊群效应,因为节点保留了前面节点的长度,大小改变时,后面节点需要做出相应调整。

第二部分,各个数据类型的数据结构