还有就是数据结构的设计快。

这是因为#xff0c;键值对是按一定的数据结构来组织的#xff0c;操作键值对最终就是对数据结构进行增删改查操…redis为什么快

首先可以想到内存读写数据本来就快然后IO复用快单线程没有静态消耗和锁机制快。

还有就是数据结构的设计快。

这是因为键值对是按一定的数据结构来组织的操作键值对最终就是对数据结构进行增删改查操作所以高效的数据结构是

Redis

Set有序集合。

而这里我们说的数据结构是要去看看它们的底层实现。

底层数据结构一共有

种分别是简单动态字符串、双向链表、压缩列表、哈希表、跳表和整数数组。

它们和数据类型的对应关系如下图所示

List、Hash、Set

这四种数据类型都有两种底层实现结构。

通常情况下我们会把这四种类型称为集合类型它们的特点是一个键对应了一个集合的数据。

这里应该是错的有序集合使用了压缩列表、哈希表、跳表三种数据结构并且哈希表和跳表共存哈希表是为了点查使用跳表是为了扫描使用。

O(1)

的时间复杂度来快速查找到键值对——我们只需要计算键的哈希值就可以知道它所对应的哈希桶位置然后就可以访问相应的

entry

所以是渐进式rehash。

第二步是每处理一次客户端请求把一个数组的位置进行转移。

压缩列表

压缩列表实际上类似于一个数组数组中的每一个元素都对应保存一个数据。

和数组不同的是压缩列表在表头有三个字段

zlbytes、zltail

在压缩列表中如果我们要查找定位第一个元素和最后一个元素可以通过表头三个字段的长度直接定位复杂度是

O(1)。

而查找其他元素时就没有这么高效了只能逐个查找此时的复杂度就是

O(N)

具体来说跳表在链表的基础上增加了多级索引通过索引位置的几个跳转实现数据的快速定位如下图所示

可以看到这个查找过程就是在多级索引上跳来跳去最后定位到元素。

这也正好符合“跳”表的叫法。

当数据量很大时跳表的查找复杂度就是

操作复杂度分析

1.单元素操作是指每一种集合类型对单个数据实现的增删改查操作。

例如Hash

HGET、HSET

等。

这些操作的复杂度由集合采用的数据结构决定例如HGET、HSET

HDEL

2、范围操作是指集合类型中的遍历操作可以返回集合中的所有数据比如

Hash

ZSCAN这类操作实现了渐进式遍历每次只返回有限数量的数据。

这样一来相比于

HGETALL、SMEMBERS

O(1)这是因为当集合类型采用压缩列表、双向链表、整数数组这些数据结构时这些结构中专门记录了元素的个数统计因此可以高效地完成相关操作。

第四例外情况是指某些数据结构的特殊记录例如压缩列表和双向链表都会记录表头和表尾的偏移量。

这样一来对于

List

这四个操作来说它们是在列表的头尾增删元素这就可以通过偏移量直接定位所以它们的复杂度也只有

总结:数据结构为什么快因为采用了全局哈希表可以快速定位key-value。

然后value的数据结构很多采用哈希表实现比如hash,set,sortedset。

而且有序集合采用了跳表实现logn级别的查找复杂度。

当需要遍历时最好用SCAN比较快。

FIFO类型可以用list

问题整数数组和压缩列表在查找时间复杂度方面并没有很大的优势那为什么

Redis

**内存利用率数组和压缩列表都是非常紧凑的数据结构**它比链表占用的内存要更少。

Redis是内存数据库大量数据存到内存中此时需要做尽可能的优化提高内存的利用率。

数组对CPU高速缓存支持更友好所以Redis在设计时集合数据元素较少情况下默认采用内存紧凑排列的方式存储同时利用CPU高速缓存不会降低访问速度。

当数据元素超过设定阈值后避免查询时间复杂度太高转为哈希和跳表数据结构存储保证查询效率。

Redis底层的使用数组和压缩链表对数据大小限制在64个字节以下当大于64个字节会改变存储数据的数据结构所以随机访问对于CPU高速缓存没啥影响