redis性能为何如此突出？
- 纯内存操作，内存操作本身就很快。
- 键值对是按一定的数据结构来组织的，操作键值对最终就是对数据结构进行增删改查操作，所以高效的数据结构是 Redis 快速处理数据的基础。
redis类型有哪些？
- string 字符串
- list 列表
- hash 哈希
- set 集合
- sorted set 有序集合
底层数据结构有哪些及分别对应了哪些类型？
- 简单动态字符串
- 双向链表
- 压缩列表
- 哈希表
- 跳跃表
- 整数数组
类型对应的数据结构
String 类型的底层实现只有简单动态字符串。而 List、Hash、Set 和 Sorted Set (四种类型称为集合类型)，两种底层数据结构实现，特点是一个键对应了一个集合的数据。
键和值用什么结构去组织，怎么快速找到键的？
一个全局哈希表(可以理解为数组)，数组的key是计算出来的哈希值，元素是哈希桶，哈希桶保存了键值指针，*key和*value，所以在查找键的速度还是很快的。
全局哈希表
全局哈希表带来的问题
1. hash冲突
我们知道hash值计算必然会产生冲突的问题，redis采用了下拉式解决哈希冲突，也称之为链式哈希。
哈希冲突解决方式
这种解决方式在数据量可能会引起哈希表冲突过多，会导致某个链上效率低下。
哈希表冲突多，链上效率变慢？
redis采用rehash，默认使用两张哈希表，当第1张哈希表冲突过多时，采用rehash，rehash分三步:
- 给哈希表 2 分配更大的空间，例如是当前哈希表 1 大小的两倍；
- 把哈希表 1 中的数据重新映射并拷贝到哈希表 2 中；
- 释放哈希表 1 的空间。
至此，哈希表1留作下次的rehash时使用。
redis单线程，如果rehash(第二步)到2表数据量大时造成严重阻塞？
是的，所以redis采用了渐进式rehash，简单来说就是在第二步拷贝数据时，Redis 仍然正常处理客户端请求，每处理一个请求时，从哈希表 1 中的第一个索引位置开始，顺带着将这个索引位置上的所有 entries 拷贝到哈希表 2 中；等处理下一个请求时，再顺带拷贝哈希表 1 中的下一个索引位置的 entries。如下图所示：
渐进式rehash
什么是压缩列表？
压缩列表
- zlbytes(列表长度)
- zltail(列表尾的偏移量)
- zllen列表的 entry 个数
- zlend(列表结束)
查找第一个元素和最后一个元素O(1)，其他元素O(N)
什么是跳表？
增加多级索引。
跳表
结构复杂度
回归题目答案总结
-
单元素操作是基础
如：(hash类型HGET、HSET 和 HDEL，Set 类型的 SADD、SREM、SRANDMEMBER)，都为O(1),如果同时添加多个元素此时为O(N) -
范围操作很耗时
如：Hash 类型的 HGETALL 和 Set 类型的 SMEMBERS，或者范围类如List 类型的 LRANGE 和 ZSet 类型的 ZRANGE。O(N),可以尝试使用SCAN解决，避免一次返回所有数据阻塞。 -
统计操作通常高效
集合类型对集合中所有元素个数的记录，例如 LLEN 和 SCARD。这类操作复杂度只有 O(1)，压缩列表、双向链表、整数数组这些数据结构时，记录了总数 -
例外情况有几个
压缩列表和双向链表都会记录表头和表尾的偏移量。这样一来，对于 List 类型的 LPOP、RPOP、LPUSH、RPUSH 这四个操作来说，它们是在列表的头尾增删元素，这就可以通过偏移量直接定位，所以它们的复杂度也只有 O(1)，可以实现快速操作
网友评论