Redis理论知识1
# 基本问题
# 1、redis 几种基本数据结构
- SET performs an assignment.
- Redis strings store sequences of bytes, including text, serialized objects, and binary arrays.
- Redis lists are linked lists of string values.
- Redis lists are implemented via Linked Lists. This means that even if you have millions of elements inside a list, the operation of adding a new element in the head or in the tail of the list is performed in constant time. The speed of adding a new element with the LPUSH command to the head of a list with ten elements is the same as adding an element to the head of list with 10 million elements. Redis 列表通过链接列表实现。这意味着即使在一个列表中有数百万个元素,在列表的头部或尾部添加新元素的操作也是在固定的时间内执行的。使用 LPUSH 命令向包含10个元素的列表的头部添加新元素的速度与向包含1000万个元素的列表的头部添加元素的速度相同。
- What's the downside? Accessing an element by index is very fast in lists implemented with an Array (constant time indexed access) and not so fast in lists implemented by linked lists (where the operation requires an amount of work proportional to the index of the accessed element). 坏处是什么?通过索引访问元素在使用 Array 实现的列表中非常快(固定时间索引访问) ,而在使用链表实现的列表中不那么快(其中操作需要与被访问元素的索引成比例的工作量)。
- Redis Lists are implemented with linked lists because for a database system it is crucial to be able to add elements to a very long list in a very fast way. Another strong advantage, as you'll see in a moment, is that Redis Lists can be taken at constant length in constant time. Redis List 是用链表实现的,因为对于一个数据库系统来说,能够以非常快的方式向一个非常长的列表添加元素是至关重要的。另一个强大的优势,正如您稍后将看到的,是可以在恒定的时间内以恒定的操作代价去操作 Redis List。
- When fast access to the middle of a large collection of elements is important, there is a different data structure that can be used, called sorted sets. 当我们非常需要访问到一个集合中的中间元素的时候,我们就可以使用有序集
- A Redis set is an unordered collection of unique strings (members).
- Most set operations, including adding, removing, and checking whether an item is a set member, are O(1). This means that they're highly efficient.
- Redis hashes are record types structured as collections of field-value pairs
- Redis hashes are maps between string fields and string values, so they are great to represent objects (e.g. A User with a number of fields like name, surname, age, and so forth).
- A Redis sorted set is a collection of unique strings (members) ordered by an associated score. When more than one string has the same score, the strings are ordered lexicographically. Redis 排序集是按关联分数排序的唯一字符串(成员)的集合。当多个字符串具有相同的分数时,字符串按字典顺序排列。
- Redis sorted sets are similar to Redis sets, but every member of a sorted set is associated with a score, that is used in order to take the sorted set ordered, from the smallest to the greatest score. While members are unique, scores may be repeated.
- Implementation note: Sorted sets are implemented via a dual-ported data structure containing both a skip list and a hash table, so every time we add an element Redis performs an O(log(N)) operation. That's good, but when we ask for sorted elements Redis does not have to do any work at all, it's already sorted. Note that the ZRANGE order is low to high, while the ZREVRANGE order is high to low: 实现说明: 排序集是通过包含跳过列表和散列表的双端口数据结构实现的,因此每次添加元素 Redis 都会执行 O (log (N))操作。这很好,但是当我们请求已排序的元素时,Redis 根本不需要做任何工作,它已经被排序了。注意, ZRANGE 顺序从低到高,而 ZREVRANGE 顺序从高到低:
# 2、zset底层数据结构?简单说说跳表底层的数据结构?
- Sorted sets are implemented via a dual-ported data structure containing both a skip list and a hash table, so every time we add an element Redis performs an O(log(N)) operation.
- 排序集是通过包含跳过列表和哈希表的双端口数据结构实现的,因此每次我们添加元素时,Redis都会执行O(log(N))操作。
- 增加了多级索引,通过多级索引位置的转跳,实现了快速查找元素,将时间复杂度降到 logN 级别。
跳跃表(Skip List):
- 跳跃表是一种有序的数据结构,它允许快速查找、插入和删除操作,并且可以实现有序性。跳跃表由多层链表组成,每一层链表都是原始链表的一种“跳跃”,跳跃的跨度随着层级的增加而增加。每个节点包含一个分数和一个成员,以及指向同一层其他节点的指针。跳跃表中的节点按照分数从小到大排序,这样就可以实现有序集合的功能。
- 跳表的原理就是将所有元素分成多个层级,然后不同层级均匀分布着这些点,也就是最低的一层存储的所有的节点,每往上一层是当前层数的一半。理想的层数就是logN,这也代表着我们最终的寻址操作就是 log n 时间复杂度。
哈希表(Hash Table):
- Redis 使用哈希表来存储成员和其对应的分数。哈希表的键是成员,值是成员对应的分数。这样可以通过成员快速定位到对应的分数,从而实现高效的查找、插入和删除操作。
哈希表适合存储无序数据,并且需要快速的插入、删除和查找操作的情况;而链表作为 Sorted Set 的实现则适合存储有序数据,并且不需要频繁进行范围查询操作的情况。
# 3、什么时候采用压缩列表、什么时候采用跳表呢?
当元素个数较少时,我们会采用压缩列表作为实现;当元素个数较多时,我们才会采用跳表作为实现,大幅的提升查询性能
# 4、跳表的时间复杂度
- 跳表的时间复杂度是 logN
- 跳表的查询时间复杂度是 O(logN),这是因为跳表的查询操作是从最高层开始,逐层向右查找,直到找到目标元素或者到达最底层。在每一层中,最多需要跨越跳表中节点的个数总是下一层的一半,有点类似于2分法的思想。因此,跳表的查询操作的时间复杂度是 O(logN)。
# 5、简单描述一下跳表如何查找某个元素呢?
在 Redis 中,跳跃表的索引层数是由 Redis 自动管理的,而不是由用户手动设定的。Redis 会根据数据集合的大小和分布等因素自动调整索引的层数,以达到平衡性能和内存消耗的目的。
跳跃表查找过程,例如有100个节点,但我们需要找到第63个元素:
- Redis 首先会从跳跃表的顶层开始查找。
- 在每一层中,Redis 会从当前节点开始,向右移动直到找到一个分数大于等于 63 的节点,或者到达该层的末尾。
- 如果找到了分数大于等于 63 的节点,那么 Redis 就会进入下一层,继续进行查找;如果找不到,则会退回到上一层,再次向右移动。随着层级的不断下移,整个范围的粒度会越来越细
- 这个过程会一直持续,直到到达跳跃表的底层。 ---------------------------------------------直到到达跳表的最底层
- 在跳跃表的底层,Redis 会找到最后一个分数小于等于 63 的节点和第一个分数大于等于 63 的节点,然后在这两个节点之间进行线性查找,以精确定位目标元素。
- 如果找到了目标元素 63,那么 Redis 就会返回该元素的值;如果没有找到,则返回空。
# 6、zset为什么用跳表而不用二叉树或者红黑树呢?
- 高并发要求:因为 reds 要支持高并发的环境使用,而对于红黑树,它有一个左旋右旋自平衡的调节方式,这种调节方式会极大的占用 CPU 无法满足高并发高性能的要求
- 实现高效:相比于红黑树,跳表的实现更简单,占用的资源更少,而查询效率都是logN,能够满足使用要求。
- 范围查询:跳表支持范围查询,而红黑树不支持范围查询,这也是 Redis 选择跳表的原因之一。
- b+tree四层,可以存储256亿行数据,但是只需要进行四次IO就可以查到。跳表就不止四次,从磁盘获取数据可比从内存获取数据难多了,所以需要尽可能的减少磁盘IO。而跳跃表要比b+tree实现简单,redis是基于内存操作,没有磁盘IO,所以选择更加容易实现的跳跃表。
# 其他问题
川哥问了这几个问题
飞跃表/跳表?原理是啥?为什么这么设计的?
redis怎么做秒杀
怎么做分布式
额外做个lua不过分吧
手写lru算法
redis最新6版本的多线程:IO多路复用原理
计算机操作系统
redistemplate
谁都会`get/set`、但是比的就是八股文
1
2
3
4
5
6
7
8
9
10
11
12
2
3
4
5
6
7
8
9
10
11
12
- redistemplate,其实就是 Java 调用 Redis 的方法,一般我们都是用 spring boot 来完成的
- 没想到很久没跟川哥聊天,他的聊天记录还是震撼到了我。什么叫做八股文的真正理解?一般人最多也就是知道八股文并且只准备了最简单的面试题,而川哥不同,他对于平常的八股文也是有自己的理解在里面的,而高手做八股文最多也就到这里了。并且他掌握的八股文并不是简单的八股文,而是八股文之中最难理解的部分,是学习过程中最困难的理论部分。所以面试的时候,任何八股文都一定要结合自己的理解去对别人讲出来。不能只是依靠自己大脑的记忆,一定要有自己的理解,自己的输出。————2024年3月6日
- 所以这也是做任何事情的态度,做任何事都一定要好好认真的做到极致。香港有个口头禅叫“博到尽”