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







下载
客户端

返回
顶部