数据结构与算法之美
王争
前Google工程师
立即订阅
71328 人已学习
课程目录
已完结 75 讲
0/4登录后,你可以任选4讲全文学习。
开篇词 (1讲)
开篇词 | 从今天起,跨过“数据结构与算法”这道坎
免费
入门篇 (4讲)
01 | 为什么要学习数据结构和算法?
02 | 如何抓住重点,系统高效地学习数据结构与算法?
03 | 复杂度分析(上):如何分析、统计算法的执行效率和资源消耗?
04 | 复杂度分析(下):浅析最好、最坏、平均、均摊时间复杂度
基础篇 (38讲)
05 | 数组:为什么很多编程语言中数组都从0开始编号?
06 | 链表(上):如何实现LRU缓存淘汰算法?
07 | 链表(下):如何轻松写出正确的链表代码?
08 | 栈:如何实现浏览器的前进和后退功能?
09 | 队列:队列在线程池等有限资源池中的应用
10 | 递归:如何用三行代码找到“最终推荐人”?
11 | 排序(上):为什么插入排序比冒泡排序更受欢迎?
12 | 排序(下):如何用快排思想在O(n)内查找第K大元素?
13 | 线性排序:如何根据年龄给100万用户数据排序?
14 | 排序优化:如何实现一个通用的、高性能的排序函数?
15 | 二分查找(上):如何用最省内存的方式实现快速查找功能?
16 | 二分查找(下):如何快速定位IP对应的省份地址?
17 | 跳表:为什么Redis一定要用跳表来实现有序集合?
18 | 散列表(上):Word文档中的单词拼写检查功能是如何实现的?
19 | 散列表(中):如何打造一个工业级水平的散列表?
20 | 散列表(下):为什么散列表和链表经常会一起使用?
21 | 哈希算法(上):如何防止数据库中的用户信息被脱库?
22 | 哈希算法(下):哈希算法在分布式系统中有哪些应用?
23 | 二叉树基础(上):什么样的二叉树适合用数组来存储?
24 | 二叉树基础(下):有了如此高效的散列表,为什么还需要二叉树?
25 | 红黑树(上):为什么工程中都用红黑树这种二叉树?
26 | 红黑树(下):掌握这些技巧,你也可以实现一个红黑树
27 | 递归树:如何借助树来求解递归算法的时间复杂度?
28 | 堆和堆排序:为什么说堆排序没有快速排序快?
29 | 堆的应用:如何快速获取到Top 10最热门的搜索关键词?
30 | 图的表示:如何存储微博、微信等社交网络中的好友关系?
31 | 深度和广度优先搜索:如何找出社交网络中的三度好友关系?
32 | 字符串匹配基础(上):如何借助哈希算法实现高效字符串匹配?
33 | 字符串匹配基础(中):如何实现文本编辑器中的查找功能?
34 | 字符串匹配基础(下):如何借助BM算法轻松理解KMP算法?
35 | Trie树:如何实现搜索引擎的搜索关键词提示功能?
36 | AC自动机:如何用多模式串匹配实现敏感词过滤功能?
37 | 贪心算法:如何用贪心算法实现Huffman压缩编码?
38 | 分治算法:谈一谈大规模计算框架MapReduce中的分治思想
39 | 回溯算法:从电影《蝴蝶效应》中学习回溯算法的核心思想
40 | 初识动态规划:如何巧妙解决“双十一”购物时的凑单问题?
41 | 动态规划理论:一篇文章带你彻底搞懂最优子结构、无后效性和重复子问题
42 | 动态规划实战:如何实现搜索引擎中的拼写纠错功能?
高级篇 (9讲)
43 | 拓扑排序:如何确定代码源文件的编译依赖关系?
44 | 最短路径:地图软件是如何计算出最优出行路径的?
45 | 位图:如何实现网页爬虫中的URL去重功能?
46 | 概率统计:如何利用朴素贝叶斯算法过滤垃圾短信?
47 | 向量空间:如何实现一个简单的音乐推荐系统?
48 | B+树:MySQL数据库索引是如何实现的?
49 | 搜索:如何用A*搜索算法实现游戏中的寻路功能?
50 | 索引:如何在海量数据中快速查找某个数据?
51 | 并行算法:如何利用并行处理提高算法的执行效率?
实战篇 (5讲)
52 | 算法实战(一):剖析Redis常用数据类型对应的数据结构
53 | 算法实战(二):剖析搜索引擎背后的经典数据结构和算法
54 | 算法实战(三):剖析高性能队列Disruptor背后的数据结构和算法
55 | 算法实战(四):剖析微服务接口鉴权限流背后的数据结构和算法
56 | 算法实战(五):如何用学过的数据结构和算法实现一个短网址系统?
加餐:不定期福利 (6讲)
不定期福利第一期 | 数据结构与算法学习书单
不定期福利第二期 | 王争:羁绊前行的,不是肆虐的狂风,而是内心的迷茫
不定期福利第三期 | 测一测你的算法阶段学习成果
不定期福利第四期 | 刘超:我是怎么学习《数据结构与算法之美》的?
总结课 | 在实际开发中,如何权衡选择使用哪种数据结构和算法?
《数据结构与算法之美》学习指导手册
加餐:春节7天练 (7讲)
春节7天练 | Day 1:数组和链表
春节7天练 | Day 2:栈、队列和递归
春节7天练 | Day 3:排序和二分查找
春节7天练 | Day 4:散列表和字符串
春节7天练 | Day 5:二叉树和堆
春节7天练 | Day 6:图
春节7天练 | Day 7:贪心、分治、回溯和动态规划
加餐:用户学习故事 (2讲)
用户故事 | Jerry银银:这一年我的脑海里只有算法
用户故事 | zixuan:站在思维的高处,才有足够的视野和能力欣赏“美”
结束语 (3讲)
结束语 | 送君千里,终须一别
第2季回归 | 这一次,我们一起拿下设计模式!
打卡召集令 | 60 天攻克数据结构与算法
免费
数据结构与算法之美
登录|注册

52 | 算法实战(一):剖析Redis常用数据类型对应的数据结构

王争 2019-01-25
到此为止,专栏前三部分我们全部讲完了。从今天开始,我们就正式进入实战篇的部分。这部分我主要通过一些开源项目、经典系统,真枪实弹地教你,如何将数据结构和算法应用到项目中。所以这部分的内容,更多的是知识点的回顾,相对于基础篇、高级篇的内容,其实这部分会更加容易看懂。
不过,我希望你不要只是看懂就完了。你要多举一反三地思考,自己接触过的开源项目、基础框架、中间件中,都用过哪些数据结构和算法。你也可以想一想,在自己做的项目中,有哪些可以用学过的数据结构和算法进一步优化。这样的学习效果才会更好。
好了,今天我就带你一块儿看下,经典数据库 Redis 中的常用数据类型,底层都是用哪种数据结构实现的?

Redis 数据库介绍

Redis 是一种键值(Key-Value)数据库。相对于关系型数据库(比如 MySQL),Redis 也被叫作非关系型数据库
像 MySQL 这样的关系型数据库,表的结构比较复杂,会包含很多字段,可以通过 SQL 语句,来实现非常复杂的查询需求。而 Redis 中只包含“键”和“值”两部分,只能通过“键”来查询“值”。正是因为这样简单的存储结构,也让 Redis 的读写效率非常高。
除此之外,Redis 主要是作为内存数据库来使用,也就是说,数据是存储在内存中的。尽管它经常被用作内存数据库,但是,它也支持将数据存储在硬盘中。这一点,我们后面会介绍。
取消
完成
0/1000字
划线
笔记
复制
© 版权归极客邦科技所有,未经许可不得传播售卖。 页面已增加防盗追踪,如有侵权极客邦将依法追究其法律责任。
该试读文章来自付费专栏《数据结构与算法之美》,如需阅读全部文章,
请订阅文章所属专栏。
立即订阅
登录 后留言

精选留言(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,画个图便清楚了。
    还原的时候,首先获取数组第一个节点,构建节点,放入队列中,再使用类似广度遍历的方式,节点出对,在数组中查找其两个子节点,构建并连接两个子节点,子节点入队,直至队列空,构建就完成了。
    保存与还原的时间复杂度与空间复杂度都是O(n)。
    2)非平衡的树的保存
    情况复杂一点,但是仍然能够使用下标。
    保存的时候,为了方便后面的查找和读取,我们访问节点的顺序,是按下标升序的顺序走的,也就是广度遍历的顺序(加入子节点的时候注意先加左节点后右节点(好像本来就是这样的:-D)),这样一来,就能保存一条升序的列表,因而能够使用二分查找的方法寻找子节点的下标。
    还原的时候,构建根节点,入队。进入循环,节点出队,使用二分查找的方法找到其两个子节点,构建连接并入队,直至队列为空。
    空间复杂度为O(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
收起评论
46
返回
顶部