52 | 算法实战（一）：剖析Redis常用数据类型对应的数据结构

精选留言(46)

• 

  在路上

  思考题1：redis的数据结构由多种数据结构来实现，主要是出于时间和空间的考虑，当数据量小的时候通过数组下标访问最快、占用内存最小，而压缩列表只是数组的升级版；
  因为数组需要占用连续的内存空间，所以当数据量大的时候，就需要使用链表了，同时为了保证速度又需要和数组结合，也就有了散列表。
  对于数据的大小和多少采用哪种数据结构，相信redis团队一定是根据大多数的开发场景而定的。
  
  思考题2：二叉查找树的存储，我倾向于存储方式一，通过填充叶子节点形成完全二叉树，然后以数组的形式存储到硬盘，数据还原过程也是非常高效的。如果用存储方式二就比较复杂了。

  2019-01-25

  

   37
• 

  郑晨Cc

  老师 关于redis的压缩列表有个地方不太明白
  虽然压缩列表看起来想数组 但他能像数组一样支持按照下标进行直接随机访问吗？比如我要访问下标为n的数据我启不是需要知道之前从0到n-1的所有数据的长度才能找到n，那这跟链表的时间复杂读没啥区别啊，而且还占用了连续的内存空间？ 还是说压缩列表中的每个元素的长度都记录在它的头部可以一次性的获取？

  作者回复: 哈哈，你说的没错。压缩列表不支持随机访问。有点类似链表。但是比较省存储空间啊。Redis一般都是通过key获取整个value的值，也就是整个压缩列表的数据，并不需要随机访问。

  2019-01-25

  

   23
• 

  Jerry银银

  发现一个功能：左滑进入上一篇，右滑进入下一篇

  编辑回复: 看来是没少刷专栏😄

  2019-01-25

   1

   11
• 

  李靖峰

  数据量小时采用连续内存的数据结构是为了CPU缓存读取连续内存来提高命中率，而限制数据数量和数据大小应该是考虑到CPU缓存的大小

  2019-02-02

  

   8
• 

  张淼

  问题1: 压缩列表优点：访问存取快速，节省内存。但是受到操作系统空闲内存限制。越大的连续内存空间越不容易申请到。所以用了其他数据结构比如链表替代。

  2019-01-26

  

   5
• 

  田伟 คิดถึง

  看完前边的课程，当知识点连成线和面之后，才发现原来是这么回事，再来看redis确认是豁然开朗。知识成体系之后记忆会更深刻，不过也带来了更多的思考和发现-----知识边界扩大了

  2019-01-25

  

   5
• 

  来碗绿豆汤

  压缩列表每个元素所占用的空间大小是不一定的，所以当想要随机访问某个元素的时候还是要像列表那样从头开始遍历，所以不能太大。理解对吗？

  作者回复: 是的 没错

  2019-04-10

  

   3
• 

  Geek_54edc1

  思考题2：对二叉搜索树进行前序遍历，得到的结果以数组的形式存储到磁盘，还原的过程就是顺序遍历数组，构建二叉搜索树

  2019-06-01

  

   2
• 

  wei

  老师，如果字典保存的键和值的大小都小于 64 字节，并且键值对的个数小于 512 个，Redis 用压缩列表实现。从 [源码](https://github.com/antirez/redis/blob/unstable/src/ziplist.c) （ziplist.c ziplistFind） 来看压缩列表根据键查找值的方式，就是一个个遍历。如果有几百个键值对，这么查找比散列表快吗？

  2019-01-26

  

   2
• 

  readyao

  老师您好，有这样一个场景，A关注了B,这样的操作会同时写两个链表一个是A的关注列表，另一个是B的粉丝列表，比如用redis 的sortset来存储。现在要检查所有不一致的情况(比如，A的关注列表有B，但是B的粉丝列表没有A，或者A的关注列表没有B，但是B的粉丝列表有A)。这种情况有什么好的方法吗?

  2019-01-26

  

   2
• 

  package coder.wjx;

  关于思考题二，我想可以有两种方法。
  1）平衡的树的保存
  那么说明其高度是接近logn的，也就是接近完全二叉树的状态，那么使用数组就能够高效的保存这棵树，即便有些地方会是空的，但是这是以空间换时间，加上数组对缓存友好，保存读取应该都会很快。
  保存的时候，首先查看最大的高度，申请一个足够大的数组。然后，从根节点开始，进行遍历，顺序无所谓。重要的是，我们要确定每个节点在数组中的下标，不过很简单，节点i的两个子节点的下标分别是2i+1和2i+2，画个图便清楚了。
  还原的时候，首先获取数组第一个节点，构建节点，放入队列中，再使用类似广度遍历的方式，节点出对，在数组中查找其两个子节点，构建并连接两个子节点，子节点入队，直至队列空，构建就完成了。
  保存与还原的时间复杂度与空间复杂度都是Ｏ(n)。
  2）非平衡的树的保存
  情况复杂一点，但是仍然能够使用下标。
  保存的时候，为了方便后面的查找和读取，我们访问节点的顺序，是按下标升序的顺序走的，也就是广度遍历的顺序（加入子节点的时候注意先加左节点后右节点（好像本来就是这样的:-D）），这样一来，就能保存一条升序的列表，因而能够使用二分查找的方法寻找子节点的下标。
  还原的时候，构建根节点，入队。进入循环，节点出队，使用二分查找的方法找到其两个子节点，构建连接并入队，直至队列为空。
  空间复杂度为Ｏ(n)，时间复杂度，保存的是O(n)。还原时，n个节点的遍历需要O(n)，而遍历单个节点需要查找两次数组，因此是O(logn)，总体就是O(nlogn)。
  不知有没有更快的方法，大家可以一起讨论下

  2019-09-18

  

   1
• 

  锦

  常常听人说可以使用Redis作为消息队列，这是为什么呢？

  作者回复: 😂 自己看看redis官方文档吧

  2019-06-13

   1

   1
• 

  xuery

  1. 这个是因为每种数据结构都有适合自己的场景，比如压缩列表（特殊的有序数组）比较适合查询操作，删除新增的时间复杂度较高为O（n）,数据量小的时候可以使用，因为结构简单，数据量大的时候删除新增的效率非常低；所以量大的时候要考虑增删改查都比较快的数据结构，比如散列表、跳表、二叉树、红黑树等等数据结构了
  2. 二叉树可以通过前序+中序写入磁盘，之后通过前序+中序还原；或者类似于将堆的时候，将数据按层遍历存入数组中，从下标1开始存储，下标i的左右子树存储在(2*i,2*i+1)下标中，然后顺序写入磁盘，这个的缺点是会产生空洞，因为不一定是满二叉树

  2019-04-10

  

   1
• 

  青铜5 周群力

  我猜压缩列表的好处是能利用l2缓存?

  作者回复: 是的，有这么个好处。越小越有利于CPU缓存。

  2019-02-06

  

   1
• 

  三木子

  有个疑问，比如对于有序集合，这个数据量可能会逐步增加，那么数据量达到阈值时就会切换成跳表吗？是数据全部移动到跳表，然后删除列表吗？

  2019-01-25

  

   1
• 

  复兴

  值是字符串类型，老师一笔带过了，其实我想知道的是，值为字符串的键值对，是不是通过hash实现的，将键转换成index存储在hash表中。

  作者回复: 是的，你理解的没错

  2019-09-30

  

  
• 

  复兴

  老师能说下，压缩列表具体怎样实现的嘛

  2019-09-30

  

  
• 

  方晓斌

  第二题清除数据结构存储有两种思路，保持前中后序遍历串，或者填充成完全二叉树用数组。都能还原

  2019-09-24

  

  
• 

  Magic

  1 只所以采用不同的数据结构，目的都是为了优化性能。因为数据结构和算法性能是依托于具体的场景和数据规模的。例如redis中的列表，当数据规模较小时，使用的是ziplist，节约了空间，同时数据连续存储有利于cpu缓存。当数据量较大时使用双向链表，这是因为ziplist要求连续内存存储，数据量大的话要求的连续内存尺寸也会增大，这不利于利用碎片化的内存
  2 二叉树的结构化存储，实际上难点是指针的序列化，二叉树节点中包含数据，左子节点指针和由子节点指针，序列化左右子节点指针时，我们直接存储其所指向的子节点的数据在文件中的存储位置

  2019-09-22

  

  
• 

  Amark

  请教一个问题，redis hash 能存储多级字典吗?，比如:{‘a’: {'b': {'c': 9}}}

  作者回复: 貌似有点难度

  2019-09-19

  

  