栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

Redis五种数据结构的底层结构及使用场景

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

Redis五种数据结构的底层结构及使用场景

一、五种数据结构 1、字符串String 底层结构

int:值为整数

embStr:非整数且大小小于39字节

raw:其他

使用场景

验证码等

2、哈希表Hash 底层结构

ZipList:键值对个数少于512且所有键值对大小小于64字节

HashTable:其他

使用场景

存取、修改用户的不同属性:如用户名、年龄、积分等,无需序列化与反序列化即可修改

3、列表List 底层结构

QuickList

使用场景

最新消息排行:利用双向链表的特性

消息队列:同上

4、集合Set 底层结构

intSet:元素个数少于512且所有元素均为整数

HashTable:其他

使用场景

筛选共同好友:集合取交集

统计访问网站的独立IP:利用集合的唯一性

5、有序集合Sorted Set 底层结构

ZipList:元素个数小于128且所有元素大小小于64字节

SkipList:其他

使用场景

带权重的排行榜

二、压缩列表ZipList 1、什么是压缩列表

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

数组的优势占用一片连续的空间可以很好的利用CPU缓存访问数据。如果我们想要保留这种优势,又想节省存储空间我们可以对数组进行压缩

但是这样有一个问题,我们在遍历它的时候由于不知道每个元素的大小是多少,因此也就无法计算出下一个节点的具体位置。这个时候我们可以给每个节点增加一个lenght的属性

如此,我们在遍历节点的之后就知道每个节点的长度(占用内存的大小),就可以很容易计算出下一个节点再内存中的位置。这种结构就像一个简单的压缩列表了

2、压缩列表在Redis中的应用

压缩列表可以节省空间,但是效率较低。所以只有当元素个数较少且元素大小较小时会选用这种结构

三、跳表SkipList 1、什么是跳表

对于一个单链表来讲,即便链表中存储的数据是有序的,如果我们要想在其中查找某个数据,也只能从头到尾遍历链表。这样查找效率就会很低,时间复杂度会很高,是 O(n)

如果我们想要提高其查找效率,可以考虑在链表上建索引的方式。每两个结点提取一个结点到上一级,我们把抽出来的那一级叫作索引

这个时候,我们假设要查找节点8,我们可以先在索引层遍历,当遍历到索引层中值为 7 的结点时,发现下一个节点是9,那么要查找的节点8肯定就在这两个节点之间。我们下降到链表层继续遍历就找到了8这个节点。原先我们在单链表中找到8这个节点要遍历8个节点,而现在有了一级索引后只需要遍历五个节点

从这个例子里,我们看出,加来一层索引之后,查找一个结点需要遍的结点个数减少了,也就是说查找效率提高了,同理再加一级索引

从图中我们可以看出,查找效率又有提升。在例子中我们的数据很少,当有大量的数据时,我们可以增加多级索引,其查找效率可以得到明显提升

像这种链表加多级索引的结构,就是跳跃表

2、跳表在Redis中的应用

跳表是有序集合的底层实现之一,如果一个有序集合包含的元素数量比较多,又或者有序集合中元素的成员是比较长的字符串时,Redis就会使用跳跃表来作为有序集合的底层实现

这里我们需要思考一个问题——为什么元素数量比较多或者成员是比较长的字符串的时候Redis要使用跳跃表来实现?

从上面我们可以知道,跳跃表在链表的基础上增加了多级索引以提升查找的效率,但其实是一个空间换时间的方案,必然会带来一个问题——索引是占内存的。原始链表中存储的有可能是很大的对象,而索引结点只需要存储关键值值和几个指针,并不需要存储对象,因此当节点本身比较大或者元素数量比较多的时候,其优势必然会被放大,而缺点则可以忽略

3、为什么不用红黑树

红黑树也可以保证有序,但由于以下几点,跳表更加有优势

1、实现更简单

2、内存占用少

3、有序集合有很多范围操作,而跳表更适合范围操作

四、快速列表 1、什么是快速列表

快速列表是一个由ZipList组成的双向链表,这样做的理由是

  • 双向链表便于在表的两端进行push和pop操作,但是它的内存开销比较大。首先,它在每个节点上除了要保存数据之外,还要额外保存两个指针;其次,双向链表的各个节点是单独的内存块,地址不连续,节点多了容易产生内存碎片
  • ziplist是一整块连续内存,所以存储效率很高。但是,它不利于修改操作,每次数据变动都会引发一次内存的realloc。特别是当ziplist长度很长的时候,一次realloc可能会导致大批量的数据拷贝,进一步降低性能

这样相当于达到了一种折中的效果

如果有一个包含4个节点的quicklist,每个节点的ziplist又包含4个数据项。那么对外表现上,这个quicklist就总共包含16个数据项

2、快速列表在Redis中的应用

在新版本的Redis中,List均采用快速列表来实现

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/294182.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号