Redis核心技术与实战
蒋德钧
中科院计算所副研究员
立即订阅
2763 人已学习
课程目录
已更新 3 讲 / 共 50 讲
0/4登录后,你可以任选4讲全文学习。
开篇词 (1讲)
开篇词 | 这样学Redis,才能技高一筹
免费
基础篇 (2讲)
01 | 基本架构:一个键值数据库包含什么?
02 | 数据结构:快速的Redis有哪些慢操作?
Redis核心技术与实战
15
15
1.0x
00:00/00:00
登录|注册

02 | 数据结构:快速的Redis有哪些慢操作?

蒋德钧 2020-08-03
你好,我是蒋德钧。
一提到 Redis,我们的脑子里马上就会出现一个词:“快。”但是你有没有想过,Redis 的快,到底是快在哪里呢?实际上,这里有一个重要的表现:它接收到一个键值对操作后,能以微秒级别的速度找到数据,并快速完成操作。
数据库这么多,为啥 Redis 能有这么突出的表现呢?一方面,这是因为它是内存数据库,所有操作都在内存上完成,内存的访问速度本身就很快。另一方面,这要归功于它的数据结构。这是因为,键值对是按一定的数据结构来组织的,操作键值对最终就是对数据结构进行增删改查操作,所以高效的数据结构是 Redis 快速处理数据的基础。这节课,我就来和你聊聊数据结构。
说到这儿,你肯定会说:“这个我知道,不就是 String(字符串)、List(列表)、Hash(哈希)、Set(集合)和 Sorted Set(有序集合)吗?”其实,这些只是 Redis 键值对中值的数据类型,也就是数据的保存形式。而这里,我们说的数据结构,是要去看看它们的底层实现。
简单来说,底层数据结构一共有 6 种,分别是简单动态字符串、双向链表、压缩列表、哈希表、跳表和整数数组。它们和数据类型的对应关系如下图所示:
可以看到,String 类型的底层实现只有一种数据结构,也就是简单动态字符串。而 List、Hash、Set 和 Sorted Set 这四种数据类型,都有两种底层实现结构。通常情况下,我们会把这四种类型称为集合类型,它们的特点是一个键对应了一个集合的数据
取消
完成
0/1000字
划线
笔记
复制
© 版权归极客邦科技所有,未经许可不得传播售卖。 页面已增加防盗追踪,如有侵权极客邦将依法追究其法律责任。
该试读文章来自付费专栏《Redis核心技术与实战》,如需阅读全部文章,
请订阅文章所属专栏新⼈⾸单¥29.9
立即订阅
登录 后留言

精选留言(8)

  • 刘忽悠
    redis底层的数据压缩搞的很细致,像sds,根据字节长度划分的很细致,另外采用的c99特性的动态数组,对短字符串进行一次性的内存分配;跳表设计的也很秀,简单明了,进行范围查询很方便;dict的扩容没细看,但是看了一下数据结构,应该是为了避免发生扩容的时候出现整体copy;
    个人觉得老师应该把sds,dict等具体数据结构的源码也贴上
    2020-08-03
    7
  • 樱花落花
    Redis的List底层使用压缩列表本质上是将所有元素紧挨着存储,所以分配的是一块连续的内存空间,虽然数据结构本身没有时间复杂度的优势,但是这样节省空间而且也能避免一些内存碎片;
    2020-08-03
    3
  • 刘忽悠
    至于问题答案,采用压缩列表或者是整数集合,都是数据量比较小的情况,所以一次能够分配到足够大的内存,而压缩列表和整数集合本身的数据结构也是线性的,对cpu的缓存更友好一些,所以真正的执行的时间因为高速缓存的关系,速度更快
    2020-08-03
    1
  • Kaito
    两方面原因:

    1、内存利用率,数组和压缩列表都是非常紧凑的数据结构,它比链表占用的内存要更少。Redis是内存数据库,大量数据存到内存中,此时需要做尽可能的优化,提高内存的利用率。

    2、数组对CPU高速缓存支持更友好,所以Redis在设计时,集合数据元素较少情况下,默认采用内存紧凑排列的方式存储,同时利用CPU高速缓存不会降低访问速度。当数据元素超过设定阈值后,避免查询时间复杂度太高,转为哈希和跳表数据结构存储,保证查询效率。
    2020-08-04
  • 🐻🐻
    有一个疑问:
    List 压缩列表 LPOP 时, 是O(1)吗 ? 因为压缩列表实际上还是加上了一些附加信息的数组,在数组起始位置增加元素, 是需要搬移元素的

    请老师解答一下,对底层代码的实现有兴趣
    2020-08-04
  • 曾轼麟
    intset 和 ziplist 如果直接使用确实是时间复杂度上不是很高效,但是结合Redis的使用场景,大部分Redis的数据都是零散碎片化的,通过这两种数据结构可以提高内存利用率,但是为了防止过度使用这两种数据结构Redis其实都设有阈值或者搭配使用的,例如:ziplist是和quicklist一起使用的,在quicklist中ziplist是一个个节点,而且quicklist为每个节点的大小都设置有阈值避免单个节点过大,从而导致性能下降
    2020-08-03
  • 杨逸林
    我以为是 keys 这种,慢操作,原来是针对底层数据结构讲解的“慢”操作。
    2020-08-03
  • 小氘
    我是没有用过redis的小白,尝试回答课后思考题。
    数组这种基本数据结构的两个特点:1 连续的内存空间分布,符合程序的局部性原理,可以利用cpu高速缓存;2 根据数组下标随机访问元素的时间复杂度是O(1)。如果实现上可以利用这两个特点,那还是有它的存在价值。
    2020-08-03
收起评论
8
返回
顶部