网站建设需要什么系统,品牌网站建设流程,做网站交互效果用什么软件,电商类网站开发项目流程面试题#xff1a; 谈谈Redis数据类型的底层数据结构#xff1a;
SDS动态字符串双向链表玉缩列表ziplist哈希表hashtable跳表kiplist整数集合intset快速列表quicklist紧凑列表listpack Redis源代码的核心部分
官网#xff1a;GitHub - redis/redis: Redis is an in-memory…面试题 谈谈Redis数据类型的底层数据结构
SDS动态字符串双向链表玉缩列表ziplist哈希表hashtable跳表kiplist整数集合intset快速列表quicklist紧凑列表listpack Redis源代码的核心部分
官网GitHub - redis/redis: Redis is an in-memory database that persists on disk. The data model is key-value, but many different kind of values are supported: Strings, Lists, Sets, Sorted Sets, Hashes, Streams, HyperLogLogs, Bitmaps. 源码位置\redis-7.0.5\src Redis基本数据结构
官网说明 主要包括这些源码文件Redis对象 object.c、字符串 t_string.c、列表 t_list.c、字典 t_hash.c、集合及有序集合 t_set.c 和 t_zset.c、数据流 t_stream.cStreams的底层实现结构 listpack.c 和 rax.c。
还包括简单动态字符串 sds.c、整数集合 intset.c、压缩列表 ziplist.c、快速链表 quicklist.c、listpack、字典 dict.c
Redis数据库的实现
数据库的底层实现 db.c持久化 rdb.c 和 aof.c
Redis服务端和客户端实现
事件驱动 ae.c 和 ae_epoll.c网络连接 anet.c 和 networking.c服务满程序 server.c客户端程序edis-cli.c
其他实现
主从复制replication.c哨兵 sentinel.c集群 cluster.c其他数结构如 hyperloglog.c、geo.c 等其他功能如 pub/sub、Lua 脚本 Redis字典数据库中 KV 键值对到底是什么
如何实现键值对(key-value)数据库的
redis是key-value存储系统key一般都是String类型的字符串对象value类型则为redis对象(redisObject)。
注value可以是字符串对象也可以是集合数据类型的对象比如List对象、Hash对象、Set对象和Zset对象。 十大类型说明
传统 5 大类型String、List、Hash、Set、ZSet
新介绍的 5 大类型 bitmap实质StringhyperLogLog实质StringGEO实质ZsetStream实质StreamBITFIELD看具体key 上帝视角
Redis定义了redisObjec结构体来表示string、hash、list、set、zset等数据类型 Redis中每个对象都是一个redisObject结构。 字典、KV是什么(重点 每个键值对都会有一个dictEntry 源码位置(dict.h) 重点从dictEntry到RedisObject 这些键值对是如何保存进Redis并进行读取操作O(1)复杂度 redisObjectRedis数据类型Redis所有编码方式底层实现三者之间的关系 5大结构底层语言源码分析
C语言struct结构体语法简介 Redis数据类型与数据结构总纲图
源码分析总体数据结构大纲 1.SDS动态字符串 2.双向链表 3.压缩列表ziplist 4.哈希表hashtable 5.跳表skiplist 6.整数集合intset 7.快速列表quicklist 8.紧凑列表listpack redis6之前老版本 Redis7版本 源码分析总体数据结构大纲 redisObject操作底层定义来自那里 举例
从set hello world说起每个键值对都会有一个dictEntry。 set hello word为例因为Redis是KV键值对的数据库每个键值对都会有一个dictEntry(源码位置dict.h)里面指向了key和value的指针next 指向下一个 dictEntry。 key 是字符串但是 Redis 没有直接使用 C 的字符数组而是存储在redis自定义的 SDS中。 value 既不是直接作为字符串存储也不是直接存储在 SDS 中而是存储在redisObject 中。 实际上五种常用的数据类型的任何一种都是通过 redisObject 来存储的。 备注 查看key类型type key 查看key编码object encoding hello redisObjec结构的作用 为了便于操作Redis采用redisObjec结构来统一五种不同的数据类型这样所有的数据类型就都可以以相同的形式在函数间传递而不用使用特定的类型结构。同时为了识别不同的数据类型redisObjec中定义了type和encoding字段对不同的数据类型加以区别。简单地说redisObjec就是string、hash、list、set、zset的父类可以在函数间传递时隐藏具体的类型信息所以作者抽象了redisObjec结构来到达同样的目的。 RedisObject各字段的含义 解释
1、4位的type表示具体的数据类型
2、4位的encoding表示该类型的物理编码方式见下表同一种数据类型可能有不同的编码方式。(比如String就提供了3种:int embstr raw) 3、lru字段表示当内存超限时采用LRU算法清除内存中的对象。
4、refcount表示对象的引用计数。
5、ptr指针指向真正的底层数据结构的指针。 举例 前置知识
各个类型的数据结构的编码映射和定义 Debug Object key 使用 开启debug模式 配置文件config修改 enable-debug-command local 开启前 开启后 解释 1、Value at: 内存地址 2、refcount: 引用次数 3、encoding: 物理编码类型 4、serializedlength: 序列化后的长度注意这里的长度是序列化后的长度保存为rdb文件时使用了该算法不是真正存贮在内存的大小),会对字串做一些可能的压缩以便底层优化 5、lru记录最近使用时间戳 6、lru_seconds_idle空闲时间 String数据结构介绍
3大物理编码方式
RedisObject内部对应3大物理编码int、embstr、raw 1、int 编码
保存long型长整型的64位(8个字节)有符号整数。最大值9223372036854775807其中数字最多19位。 补充只有整数才会使用int如果是浮点数Redis内部其实先将浮点数转化为字符串值然后再保存。
2、embstr 编码
代表embstr格式的SDS(Simple Dynamic String 简单动态字符串保存长度小于44字节的字符串。
embstr 顾名思义即embedded string表示嵌入式的String。
3、raw 编码
保存长度大于44字节的字符串。
编码案例 C语言中的字符串形式 假如现在展现一个字符串Redis Redis没有直接复用C语言的字符串而是新建了属于自己的结构-----SDS
在Redis数据库里包含字符串值的键值对都是由SDS实现的(Redis中所有的键都是由字符串对象实现的即底层是由SDS实现Redis中所有的值对象中包含的字符串对象底层也是由SDS实现)。 源码分析
官网GitHub - antirez/sds: Simple Dynamic Strings library for C
1、sds.h源码分析 说明 Redis中字符串的实现,SDS有多种结构sds.h sdshdr5、(2^532byte) sdshdr8、(2 ^ 8256byte) sdshdr16、(2 ^ 1665536byte64KB) sdshdr32、 (2 ^ 32byte4GB) sdshdr642的64次方byte17179869184G用于存储不同的长度的字符串。 len 表示 SDS 的长度使我们在获取字符串长度的时候可以在 O(1)情况下拿到而不是像 C 那样需要遍历一遍字符串。 alloc 可以用来计算 free 就是字符串已经分配的未使用的空间有了这个值就可以引入预分配空间的算法了而不用去考虑内存分配的问题。 buf 表示字符串数组真存数据的。 2、Redis为什么重新设计一个SDS数据结构 C语言没有Java里面的String类型只能是靠自己的char[]来实现字符串在 C 语言中的存储方式想要获取 「Redis」的长度需要从头开始遍历直到遇到 \0 为止。所以Redis 没有直接使用 C 语言传统的字符串标识而是自己构建了一种名为简单动态字符串 SDSsimple dynamic string的抽象类型并将 SDS 作为 Redis 的默认字符串。 3、set k1 v1命令底层发生了什么调用关系是怎么样的 4、INT编码格式 命令示例 set k3 123 当字符串键值的内容可以用一个64位有符号整形来表示时Redis会将键值转化为long型来进行存储此时即对应 OBJ_ENCODING_INT 编码类型。内部的内存结构表示如下 Redis 启动时会预先建立 10000 个分别存储 0~9999 的 redisObject 变量作为共享对象这就意味着如果 set字符串的键值在 0~10000 之间的话则可以 直接指向共享对象 而不需要再建立新对象此时键值不占空间 set k1 123 set k2 123 源码内容 redis源代码server.h定义一个共享变量 redis6源代码object.c redis7源代码object.c 5、EMBSTR编码格式 命令示例set k3 abc redis源代码object.c 对于长度小于 44的字符串Redis 对键值采用OBJ_ENCODING_EMBSTR 方式EMBSTR 顾名思义即embedded string表示嵌入式的String。从内存结构上来讲 即字符串 sds结构体与其对应的 redisObject 对象分配在同一块连续的内存空间字符串sds嵌入在redisObject对象之中一样。 进一步createEmbeddedStringObject方法 redis源代码object.c 高明之处ptr指针指向下一个地址。 6、RAW编码格式 命令示例set k3 abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyz 当字符串的键值为长度大于44的超长字符串时Redis 则会将键值的内部编码方式改为OBJ_ENCODING_RAW格式这与OBJ_ENCODING_EMBSTR编码方式的不同之处在于此时动态字符串sds的内存与其依赖的redisObject的内存不再连续了。 个别情况明明没有超过阈值为什么变成raw了 结果判断不出来就取最大Raw 逻辑图 案例结论 1、只有整数才会使用 int如果是浮点数 Redis 内部其实先将浮点数转化为字符串值然后再保存。 2、embstr 与 raw 类型底层的数据结构其实都是 SDS (简单动态字符串Redis 内部定义 sdshdr 一种结构)。 这两者的区别见下图
1、intLong类型整数时RedisObject中的ptr指针直接赋值为整数数据不再额外的指针再指向整数了节省了指针的空间开销。
2、embstr当保存的是字符串数据且字符串小于等于44字节时embstr类型将会调用内存分配函数只分配一块连续的内存空间空间中依次包含 redisObject 与 sdshdr 两个数据结构让元数据、指针和SDS是一块连续的内存区域这样就可以避免内存碎片。
3、raw当字符串大于44字节时SDS的数据量变多变大了SDS和RedisObject布局分家各自过会给SDS分配多的空间并用指针指向SDS结构raw 类型将会调用两次内存分配函数分配两块内存空间一块用于包含 redisObject结构而另一块用于包含 sdshdr 结构。 结果Rdis内部会根据用户给的不同键值而使用不同的编码格式自适应地选择较优化的内部编码格式而这一切对用户完全透明
Hash数据结构介绍
Redis 6
1、结构 hash-max-ziplist-entries使用压缩列表保存时哈希集合中的最大元素个数。 hash-max-ziplist-value使用压缩列表保存时哈希集合中单个元素的最大长度。 Hash类型键的字段个数 小于 hash-max-ziplist-entries 并且每个字段名和字段值的长度 小于 hash-max-ziplist-value 时Redis才会使用 OBJ_ENCODING_ZIPLIST来存储该键前述条件任意一个不满足则会转换为 OBJ_ENCODING_HT的编码方式。
2、案例 3、结论 a.哈希对象保存的键值对数量小于512个 b.所有的键值对的健和值的字符串长度都小于等于64byte一个英文字母一个字节时用ziplist反之用hashtable。 注意ziplist升级到hashtable可以反过来降级不可以 。 一旦从压缩列表转为了哈希表Hash类型就会一直用哈希表进行保存而不会再转回压缩列表了。在节省内存空间方面哈希表就没有压缩列表高效了。 4、流程 5、源码分析
a、t_hash.c文件
在Redis中hashtable被称为字典(dictionary),它是一个数组链表的结构。 OBJ_ENCODING_HT编码分析每个键值对都会有一个dictEntry OBJ_ENCODING_HT 这种编码方式内部才是真正的哈希表结构或称为字典结构其可以实现O(1)复杂度的读写操作因此效率很高。 在 Redis内部从 OBJ_ENCODING_HT类型到底层真正的散列表数据结构是一层层嵌套下去的组织关系见面图 hset 命令解读 类型ziplist b、ziplist.c 文件 Ziplist 压缩列表是一种紧凑编码格式总体思想是多花时间来换取节约空间即以部分读写性能为代价来换取极高的内存空间利用率因此只会用于 字段个数少且字段值也较小 的场景。压缩列表内存利用率极高的原因与其连续内存的特性是分不开的。 想想我们的学过的一种GC垃圾回收机制标记--压缩算法。当一个 hash对象只包含少量键值对且每个键值对的键和值要么就是小整数要么就是长度比较短的字符串那么它用 ziplist 作为底层实现。 ziplist 结构解读 为了节约内存而开发的它是由连续内存块组成的顺序型数据结构有点类似于数组。 ziplist是一个经过特殊编码的双向链表它不存储指向前一个链表节点prev和指向下一个链表节点的指针next而是存储上一个节点长度和当前节点长度通过牺牲部分读写性能来换取高效的内存空间利用率节约内存是一种时间换空间的思想。只用在字段个数少字段值小的场景里面。 ziplist各个组成单元什么意思 ziplist 存取情况 prevlen记录了前一个节点的长度 encoding记录了当前节点实际数据的类型以及长度 data记录了当前节点的实际数据 zlentry 结构解读压缩列表节点的构成 压缩列表zlentry节点结构 每个zlentry由前一个节点的长度、encoding和entry-data三部分组成 前节点(前节点占用的内存字节数)表示前1个zlentry的长度privious_entry_length有两种取值情况1字节或5字节。取值1字节时表示上一个entry的长度小于254字节。虽然1字节的值能表示的数值范围是0到255但是压缩列表中zlend的取值默认是255因此就默认用255表示整个压缩列表的结束其他表示长度的地方就不能再用255这个值了。所以当上一个entry长度小于254字节时prev_len取值为1字节否则就取值为5字节。记录长度的好处占用内存小1或者5个字节。 enncoding记录节点的content保存数据的类型和长度。 content保存实际数据内容。 为什么zlentry这么设计 -- 数组和链表数据结构对比 privious_entry_lengthencoding长度都可以根据编码方式推算真正变化的是content而content长度记录在encoding里 因此entry的长度就知道了。entry总长度 privious_entry_length字节数encoding字节数content字节数。 为什么entry这么设计记录前一个节点的长度 链表在内存中一般是不连续的遍历相对比较慢而ziplist可以很好的解决这个问题。如果知道了当前的起始地址因为entry是连续的entry后一定是另一个entry想知道下一个entry的地址只要将当前的起始地址加上当前entry总长度。如果还想遍历下一个entry只要继续同样的操作。 明明有链表了为什么出来一个压缩链表 1、普通的双向链表会有两个指针在存储数据很小的情况下我们存储的实际数据的大小可能还没有指针占用的内存大得不偿失。ziplist 是一个特殊的双向链表没有维护双向指针:previous next而是存储上一个 entry的长度和当前entry的长度通过长度推算下一个元素在什么地方。牺牲读取的性能获得高效的存储空间因为(简短字符串的情况)存储指针比存储entry长度更费内存。这是典型的“时间换空间”。 2、链表在内存中一般是不连续的遍历相对比较慢而ziplist可以很好的解决这个问题普通数组的遍历是根据数组里存储的数据类型找到下一个元素的(例如int类型的数组访问下一个元素时每次只需要移动一个sizeof(int)就行)但是ziplist的每个节点的长度是可以不一样的而我们面对不同长度的节点又不可能直接sizeof(entry)所以ziplist只好将一些必要的偏移量信息记录在了每一个节点里使之能跳到上一个节点或下一个节点。 备注:sizeof实际上是获取了数据在内存中所占用的存储空间以字节为单位来计数。 3、头节点里有头节点里同时还有一个参数 len和string类型提到的 SDS 类似这里是用来记录链表长度的。因此获取链表长度时不用再遍历整个链表直接拿到len值就可以了这个时间复杂度是 O(1)。 ziplist 总结 1、ziplist为了节省内存采用了紧凑的连续存储。 2、ziplist是一个双向链表可以在时间复杂度为 O(1) 下从头部、尾部进行 pop 或 push。 3、新增或更新元素可能会出现连锁更新现象(致命缺点导致被listpack替换)。 4、不能保存过多的元素否则查询效率就会降低数量小和内容小的情况下可以使用。 Redis 7
1、结构 hash-max-listpack-entries使用压缩列表保存时哈希集合中的最大元素个数。 hash-max-listpack-value使用压缩列表保存时哈希集合中单个元素的最大长度。 Hash类型键的字段个数 小于 hash-max-listpack-entries且每个字段名和字段值的长度 小于 hash-max-listpack-value 时Redis才会使用OBJ_ENCODING_LISTPACK来存储该键前述条件任意一个不满足则会转换为 OBJ_ENCODING_HT的编码方式。
2、案例 3、结论 a、哈希对象保存的键值对数量小于512个 b、所有的键值对的健和值的字符串长度都小于等于64byte一个英文字母一个字节时用listpack反之用hashtable 注意listpack升级到hashtable可以反过来降级不可以 。 一旦从压缩列表转为了哈希表Hash类型就会一直用哈希表进行保存而不会再转回压缩列表了。在节省内存空间方面哈希表就没有压缩列表高效了。 4、流程同Redis6只不过ziplist修改为listpack 5、源码解析
object.c 文件 listpack.c 文件 lpNew 函数创建了一个空的 listpack一开始分配的大小是 LP_HDR_SIZE 再加 1 个字节。LP_HDR_SIZE 宏定义是在 listpack.c 中它默认是 6 个字节其中 4 个字节是记录 listpack 的总字节数2 个字节是记录 listpack 的元素数量。 此外listpack 的最后一个字节是用来标识 listpack 的结束其默认值是宏定义 LP_EOF。和 ziplist 列表项的结束标记一样LP_EOF 的值也是 255 明明有ziplist了为什么出来一个listpack紧凑列表 原因ziplist的连锁更新问题。 压缩列表新增某个元素或修改某个元素时如果空间不不够压缩列表占用的内存空间就需要重新分配。而当新插入的元素较大时可能会导致后续元素的 prevlen 占用空间都发生变化从而引起「连锁更新」问题导致每个元素的空间都要重新分配造成访问压缩列表性能的下降。 案例说明压缩列表每个节点正因为需要保存前一个节点的长度字段就会有连锁更新的隐患。 第一步现在假设一个压缩列表中有多个连续的、长度在 250253 之间的节点如下图 因为这些节点长度值小于 254 字节所以 prevlen 属性需要用 1 字节的空间来保存这个长度值一切OKO(∩_∩)O哈哈~ 第二步这时如果将一个长度大于等于 254 字节的新节点加入到压缩列表的表头节点即新节点将成为entry1的前置节点如下图 因为entry1节点的prevlen属性只有1个字节大小无法保存新节点的长度此时就需要对压缩列表的空间重分配操作并将entry1节点的prevlen 属性从原来的 1 字节大小扩展为 5 字节大小。 第三步连续更新问题出现 entry1节点原本的长度在250253之间因为刚才的扩展空间此时entry1节点的长度就大于等于254因此原本entry2节点保存entry1节点的 prevlen属性也必须从1字节扩展至5字节大小。entry1节点影响entry2节点entry2节点影响entry3节点......一直持续到结尾。这种在特殊情况下产生的连续多次空间扩展操作就叫做「连锁更新」。 listpack 结构 官网https://github.com/antirez/listpack/blob/master/listpack.md listpack由4部分组成total Bytes、Num Elem、Entry以及End a、total-bytes为整个listpack的空间大小占用4个字节每个listpack最多占用4294967295Bytes。 b、num-elements为listpack中的元素个数即Entry的个数占用2个字节 c、element-1~element-n为每个具体的元素 d、listpack-end-byte为listpack结束标志占用1个字节内容为0xFF。 entry结构 a、当前元素的编码类型(entry-encoding) b、元素数据(entry-data) c、以及编码类型和元素数据这两部分的长度(entry-len) listpackEntry结构定义listpack.h ziplist内存布局 VS listpack内存布局 和ziplist 列表项类似listpack 列表项也包含了元数据信息和数据本身。不过为了避免ziplist引起的连锁更新问题listpack 中的每个列表项不再像ziplist列表项那样保存其前一个列表项的长度。 总结
redis6ziplist 或 hashtable redis7listpack 或 hashtable
List数据结构介绍
Redis 6
1、案例 解释 (1) ziplist压缩配置list-compress-depth 0 表示一个quicklist两端不被压缩的节点个数。这里的节点是指quicklist双向链表的节点而不是指ziplist里面的数据项个数。 参数list-compress-depth的取值含义如下 0: 是个特殊值表示都不压缩。这是Redis的默认值。 1: 表示quicklist两端各有1个节点不压缩中间的节点压缩。 2: 表示quicklist两端各有2个节点不压缩中间的节点压缩。 3: 表示quicklist两端各有3个节点不压缩中间的节点压缩。 依此类推… (2) ziplist中entry配置list-max-ziplist-size -2 当取正值的时候表示按照数据项个数来限定每个quicklist节点上的ziplist长度。比如当这个参数配置成5的时候表示每个quicklist节点的ziplist最多包含5个数据项。当取负值的时候表示按照占用字节数来限定每个quicklist节点上的ziplist长度。这时它只能取-1到-5这五个值每个值含义如下 -5: 每个quicklist节点上的ziplist大小不能超过64 Kb。注1kb 1024 bytes -4: 每个quicklist节点上的ziplist大小不能超过32 Kb。 -3: 每个quicklist节点上的ziplist大小不能超过16 Kb。 -2: 每个quicklist节点上的ziplist大小不能超过8 Kb。-2是Redis给出的默认值 -1: 每个quicklist节点上的ziplist大小不能超过4 Kb。 2、Iist用quicklist来存储
quicklist存储了一个双向链表每个节点都是一个ziplist。 在Redis3.0之前list采用的底层数据结构是ziplist压缩列表linkedList双向链表。然后在高版本的Redis中底层数据结构是quicklist(替换了ziplistlinkedList)而quicklist也用到了ziplist。 结论quicklist就是「双向链表 压缩列表」组合因为一个 quicklist 就是一个链表而链表中的每个元素又是一个压缩列表。 3、quicklist 总纲是ziplist和inkedlist的结合体 quicklist 实际上是 zipList 和 linkedList 的混合体它将 linkedList按段切分每一段使用 zipList 来紧凑存储多个 zipList 之间使用双向指针串接起来。 4、源码分析 quicklist.hhead和tail指向双向列表的表头和表尾。 quicklist结构 quicklistNodes结构 quicklistNode 中的 *zl 指向一个 ziplist一个 ziplist 可以存放多个元素。 Redis 7
1、案例listpack紧凑列表 是用来替代 ziplist 的新数据结构在 7.0 版本已经没有 ziplist 的配置了6.0版本仅部分数据类型作为过渡阶段在使用
2、源码说明 t_list.c 文件 lpush命令执行后直接调用pushGenericCommand命令 object.c 文件 3、Redis7的List的一种编码格式 Iist用quicklistlistpacki和linkedlist的结合体来存储quicklist存储了一个双向链表每个节点都是一个listpack。
Set数据结构介绍
1、案例
Redis用intset或hashtable存储set。如果元素都是整数类型就用intset存储。
如果不是整数类型就用hashtable数组链表的存来储结构。key就是元素的值value为null。 2、Set的两种编码格式 intset 或 hashtable
3、源码分析 t_set.c文件 ZSet数据结构介绍
案例
1、Redis 6 当有序集合中包含的元素数量超过服务器属性 server.zset_max_ziplist_entries 的值默认值为 128 或者有序集合中新添加元素的 member 的长度大于服务器属性 server.zset_max_ziplist_value 的值默认值为 64 时redis会使用跳跃表作为有序集合的底层实现。否则会使用ziplist作为有序集合的底层实现。 2、Redis7 ZSet 的两种编码格式
1、Redis 6 ziplist 或 skiplist
2、Redis 7 listpack 或 skiplist
redis6源码分析 t_zset.c 文件 redis7源码分析 t_zset.c 文件 skiplist 跳表面试题
1、为什么引出跳表 先说单链表对于一个单链表来讲即便链表中存储的数据是有序的如果我们要想在其中查找某个数据也只能从头到尾遍历链表。这样查找效率就会很低时间复杂度会很高O(N) 痛点 解决方法升维也叫空间换时间。 优化1 从这个例子里我们看出加来一层索引之后查找一个结点需要遍历的结点个数减少了也就是说查找效率提高了。 优化2 画了一个包含64个结点的链表按照前面讲的这种思路建立了五级索引。 2、跳表是什么 跳表是可以实现二分查找的有序链表 skiplist是一种以空间换取时间的结构。由于链表无法进行二分查找因此借鉴数据库索引的思想提取出链表中关键节点索引先在关键节点上查找再进入下层链表查找提取多层关键节点就形成了跳跃表。但是由于索引也要占据一定空间的所以索引添加的越多空间占用的越多。 总结来讲跳表 链表多级索引
3、跳表时间/空间复杂度介绍
跳表的时间复杂度时间复杂度是O(logN) 跳表查询的时间复杂度分析如果链表里有N个结点会有多少级索引呢 按照我们前面讲的两两取首。每两个结点会抽出一个结点作为上一级索引的结点以此估算 第一级索引的结点个数大约就是n/2 第二级索引的结点个数大约就是n/4 第三级索引的结点个数大约就是n/8依次类推...... 也就是说第k级索引的结点个数是第k-1级索引的结点个数的1/2那第k级索引结点的个数就是n/(2^k) 跳表的空间复杂度空间复杂度是O(N) 比起单纯的单链表跳表需要存储多级索引肯定要消耗更多的存储空间。那到底需要消耗多少额外的存储空间呢 我们来分析一下跳表的空间复杂度。 第一步首先原始链表长度为n。 第二步两两取首每层索引的结点数n/2, n/4, n/8 ... , 8, 4, 2 每上升一级就减少一半直到剩下2个结点,以此类推如果我们把每层索引的结点数写出来就是一个等比数列。 这几级索引的结点总和就是n/2n/4n/8…842n-2。所以跳表的空间复杂度是O(n) 。也就是说如果将包含n个结点的单链表构造成跳表我们需要额外再用接近n个结点的存储空间。 第三步思考三三取首每层索引的结点数n/3, n/9, n/27 ... , 9, 3, 1 以此类推 第一级索引需要大约n/3个结点第二级索引需要大约n/9个结点。每往上一级索引结点个数都除以3。为了方便计算我们假设最高一级的索引结点个数是1。我们把每级索引的结点个数都写下来也是一个等比数列。 通过等比数列求和公式总的索引结点大约就是n/3n/9n/27…931n/2。尽管空间复杂度还是O(n) 但比上面的每两个结点抽一个结点的索引构建方法要减少了一半的索引结点存储空间。 所以空间复杂度是O(n) 4、优缺点
优点 跳表是一个最典型的空间换时间解决方案而且只有在数据量较大的情况下才能体现出来优势。而且应该是读多写少的情况下才能使用所以它的适用范围应该还是比较有限的。 缺点 维护成本相对要高在单链表中一旦定位好要插入的位置插入结点的时间复杂度是很低的就是O(1) 但是新增或者删除时需要把所有索引都更新一遍为了保证原始链表中数据的有序性我们需要先找到要动作的位置这个查找操作就会比较耗时最后在新增和删除的过程中的更新时间复杂度也是O(log n)。 总结
redis6类型-物理编码-对应表 redis6数据类型对应的底层数据结构 1. 字符串 int:8个字节的长整型。 embstr:小于等于44个字节的字符串。 raw:大于44个字节的字符串。 Redis会根据当前值的类型和长度决定使用哪种内部编码实现。 2. 哈希 ziplist(压缩列表):当哈希类型元素个数小于hash-max-ziplist-entries 配置(默认512个)、同时所有值都小于hash-max-ziplist-value配置(默认64 字节)时 Redis会使用ziplist作为哈希的内部实现ziplist使用更加紧凑的 结构实现多个元素的连续存储所以在节省内存方面比hashtable更加优秀。 hashtable(哈希表):当哈希类型无法满足ziplist的条件时Redis会使 用hashtable作为哈希的内部实现因为此时ziplist的读写效率会下降而hashtable的读写时间复杂度为O(1)。 3. 列表 ziplist(压缩列表):当列表的元素个数小于list-max-ziplist-entries配置 (默认512个)同时列表中每个元素的值都小于list-max-ziplist-value配置时 (默认64字节) Redis会选用ziplist来作为列表的内部实现来减少内存的使 用。 linkedlist(链表):当列表类型无法满足ziplist的条件时Redis会使用 linkedlist作为列表的内部实现。quicklist ziplist和linkedlist的结合以ziplist为节点的链表(linkedlist) 4. 集合 intset(整数集合):当集合中的元素都是整数且元素个数小于set-max-intset-entries配置(默认512个)时Redis会用intset来作为集合的内部实现从而减少内存的使用。 hashtable(哈希表):当集合类型无法满足intset的条件时Redis会使用hashtable作为集合的内部实现。 5. 有序集合 ziplist(压缩列表):当有序集合的元素个数小于zset-max-ziplist- entries配置(默认128个)同时每个元素的值都小于zset-max-ziplist-value配 置(默认64字节)时 Redis会用ziplist来作为有序集合的内部实现ziplist 可以有效减少内存的使用。 skiplist(跳跃表):当ziplist条件不满足时有序集合会使用skiplist作 为内部实现因为此时ziplist的读写效率会下降。 redis6数据类型以及数据结构的关系 redis7数据类型以及数据结构的关系 redis数据类型以及数据结构的时间复杂度
