Redis底层数据结构

互联网 2021/4/7 19:09:02

redis SDS 回顾: 1、redis 只会使用C字符串作为字面量,在大多数情况下,redis使用SDS(简单动态字符串)做为字符串表示。 2、比起C字符串,SDS字符串具有以下优点: 常数复杂度获取字符串常量。杜绝缓冲区溢出。减少字符串修改长度时重新分配内存的次数。二进制安全。兼容…

redis SDS 回顾:
1、redis 只会使用C字符串作为字面量,在大多数情况下,redis使用SDS(简单动态字符串)做为字符串表示。

2、比起C字符串,SDS字符串具有以下优点:

  1. 常数复杂度获取字符串常量。
  2. 杜绝缓冲区溢出。
  3. 减少字符串修改长度时重新分配内存的次数。
  4. 二进制安全。
  5. 兼容部分C字符串函数。

redis 链表回顾:
1、链表被广泛用于实现redis的各种功能,比如列表键、发布与订阅、慢查询、监视器等。
2、每个链表节点由一个listNode 结构来表示,每个节点都有一个指向前置节点和后置节点的指针。所以redis链表的实现是双端链表。
3、每个链表由一个list结构来表示,这个结构带有表头节点指针、表尾节点指针,以及链表长度信息。
4、因为链表表头节点指针和尾节点指针都是指向NULL,所以redis的实现是无端链表。

redis字典回顾:
1、字典被广泛用于实现redis的各种功能,其中包括数据库和哈希键。
2、redis的字典使用哈希表作为底层实现,每个字典代表两个哈希表,一个在平时使用,另一个在rehash时使用。
3、当字典被用作数据库的底层实现,或者哈希键的底层实现时,redis使用murmurHash2() 方法来计算哈希键的值。
4、哈希表使用链接地址来解决hash冲突,被分配到同一个节点的多个hash值会被分配为一个单向链表。
5、在对hash表进行扩展或者收缩操作时,程序需要将现有hash表所包含的全部键值对重新rehash到新的hash表中,这个过程并不是一次性完成的,是渐进式完成的。

redis跳跃表回顾:
1、跳跃表是一种有序数据结构,他通过在某个节点中维持多个指向其他节点的指针,从而达到快速访问其他节点的目的。
2、redis使用跳跃表来作为有序集合键的底层实现之一,如果一个有序集合包含的元素数量比较多,又或者集合中元素的成员是比较长的字符串,redis就会使用跳跃表来作为集合键的底层实现。
3、redis只在两个地方用到了跳跃表,一个用于实现redis有序集合键的底层实现,另一个是在集群节点中用作内部数据结构。
4、每个跳跃表的层高都是1到32之间的整数。
5、在同一个跳跃表中,多个节点可以包含相同的分值,但是每个节点的成员对象必须唯一。
6、跳跃表中的节点按照分值大小进行排序,当分支大小相同时,按照成员大小的值进行排序。

redis整数集合回顾:
1、整数集合是集合键的底层实现之一,当一个集合只包含整数值元素,并且这个集合的元素数量不多时,redis就会使用整数集合作为集合键的底层实现方式。
2、当我们将一个新的元素添加到整数集合中时,如果该元素的类型比现有集合中所有的元素类型都要长的时候,这时,该集合会进行升级,然后才能将新元素添加到整数集合中去。
升级分为3步进行:

  1. 根据新元素的类型,扩展底层集合底层数组空间的大小,并为新元素分配空间。
  2. 将底层数组现有的所有元素都转化成新元素的数据类型,并将类型转化后的元素放到正确的位置上,而且在放置的过程中,需要保持底层元素的有序性。
  3. 将新元素添加到底层元素里面。
    3、因为每次像整数集合中添加新元素,都会引起升级,而每次升级都需要对底层元素的类型进行升级。因此添加新元素的复杂度为O(N)。
    整数集合的类型有两个好处:
  4. 提升证书集合的灵活性。
  5. 尽可能的节约内存。

4、整数集合是集合键的底层实现之一。
5、证书集合的底层实现维数组,这个数组以有序、无重复的方式保存集合元素,在有需要时,程序会根据新增加的元素类型改变数组的类型。
6、证书集合只支持升级操作,不支持降级操作。

redis压缩列表回顾:
1、压缩列表是hash键和列表键的实现之一。当一个列表键只包含少量的列表项时,并且每个列表项是比较小的整数值,或者是比较短的字符串时,那么redis就会使用压缩列表来做列表键的底层实现。另外当一个hash键只包含少量键值对时,并且每个键值对的键和值都是小整数值或者较短的字符串时,redis就会使用压缩列表来作为列表的底层实现。
2、压缩列表是一种为节约内存而单独开发的一种顺序性数据结构。
3、压缩列表被用作列表键和hash键的实现方式之一。
4、压缩列表可以包含多个节点,每个节点可以保存一个字节数组和一个整数值。
5、添加新节点或者删除节点,会引发连锁更新操作。

随时随地学软件编程-关注百度小程序和微信小程序
关于找一找教程网

本站文章仅代表作者观点,不代表本站立场,所有文章非营利性免费分享。
本站提供了软件编程、网站开发技术、服务器运维、人工智能等等IT技术文章,希望广大程序员努力学习,让我们用科技改变世界。
[Redis底层数据结构]http://www.zyiz.net/tech/detail-153411.html

上一篇:redis集群的口述理解

下一篇:Linux环境下部署Redis环境

赞(0)

共有 条评论 网友评论

验证码: 看不清楚?
    关注微信小程序
    程序员编程王-随时随地学编程

    扫描二维码或查找【程序员编程王】

    可以随时随地学编程啦!

    技术文章导航 更多>
    扫一扫关注最新编程教程