制造企业网站建设,怎样建立一个营销的公司网站,江苏最新消息今天实时,住房和城乡建设部网站电话文章目录 1. 前言2. redis 动态字符串2.1. 字符串的数据结构#xff1a;2.2. 剖析#xff0c;length#xff1b;2.3. 剖析#xff0c;free#xff1b;2.3. 使用c字符串函数#xff1b; 3. redis 链表4. 字典5. 跳跃表 1. 前言
reids作为最常用的缓存数据库#xff0c;深… 文章目录 1. 前言2. redis 动态字符串2.1. 字符串的数据结构2.2. 剖析length2.3. 剖析free2.3. 使用c字符串函数 3. redis 链表4. 字典5. 跳跃表 1. 前言
reids作为最常用的缓存数据库深入了解对于业务开发大有裨益那么从这里开始我们从《redis设计与实现》这本书我们同最常用的字符串入手了解redis的设计与思路。
2. redis 动态字符串
字符串作为redis最为核心最为常用的数据类型后面我们称sds我们深入了解一下。
2.1. 字符串的数据结构
我们从数据结构入手猜测字符串实现的功能和特性我们可以发现这里相比于c字符串多了两个属性。free和len
2.2. 剖析length 快速获取length 首先leng最简单的效果便是可以直接获取redis字符串的长短由于是直接获取属性时间复杂度为O(1)。 二进制安全 除了获取长度外为了实现redis的sds可以存储任意数据的功能sds通过length判断字符串是否到结尾这和c字符串不同‘/0’因此可以存储任意二进制数据。
2.3. 剖析free
其实简单length之后发现基本功能都差不多了那么这个free有什么作用呢
预留free空间 减少重新分配在sds除了记录length之外还会分配一倍length1mb大小以内的未使用空间如果length在再次增加的情况下不过增加的长度小于free则不需要重新分配内存。
2.3. 使用c字符串函数
redis虽然自行实现了字符串数据机构但是还是在字符串末尾增加一个’/0’空字符目的是为了使用c字符串的函数。
3. redis 链表
redis链表并没有非常奇特的地方在redis链表中主要有两个数据结构。
list 统计 这里包括list的一些概要信息和一些函数目的是为了后面使用链表节点方便一点。listnode 节点。
一般来说这个在学习数据结构中用的很多一般情况下只需要记录一个pre node便可以遍历整个链表。
redis链表为双向链表。并没有过于多的特殊。
4. 字典
字典又称为符号表mapkey-value。 dicththash表属性包括hash表数组表大小hash表大小掩码已有节点数量。 dictEntry表数据是key-value结构
redis对于hash冲突的解决方案是链地址法即如果冲突在原来dictEntrt下面通过next链接冲突节点。 字典hash的上层结构和java中的hashMap功能类似。 dictType 可以指定不同低操作函数。 ht 为两个hash表另外一个用于备份。在再hash时使用 hash算法 hash算法和普通的hash表别无二致通话hash算法hashkey mask把数组放到表里。 hash冲突。 redis使用链地址发把键值对存储在链表之前解决冲突这样的时间复杂度为O1。 rehash 当hash表空间不够的时候一般需要再次hash 渐进式再hash在渐进式 rehash 过程中Redis 会同时保持旧的哈希表和新的哈希表。然后在每次执行命令时Redis 会从旧哈希表中移动一小批键值对到新哈希表这个过程分散在多个操作中逐步完成。 具体条件为 当负载因子大于1且没在持久化BGSAVEBGREWRITEAOF会进行再hash。当负载因子大于3目前在执行BGSAVEBGREWRITEAOF时会进行再hash。在负载因子小于0.1时会进行收缩。 BGSAVE 命令用于在后台创建 Redis 数据库的快照。当执行此命令时Redis 会 fork 出一个子进程子进程则将内存中的数据写入到磁盘上的一个 RDB 文件中。这个过程不会阻塞主 Redis 进程所以 Redis 可以继续处理客户端请求。RDBRedis DataBase文件是一个压缩的二进制文件表示某一时刻 Redis 数据库的完整快照BGREWRITEAOF 命令用于优化 AOFAppend Only File文件的大小。Redis 的 AOF 持久化通过记录数据库的所有写操作到一个文件中来工作这个文件随着操作的积累会不断增长。BGREWRITEAOF 命令会在后台创建一个当前数据的最小操作集以此来重写 AOF 文件这个过程同样不会阻塞主 Redis 进程。 5. 跳跃表
跳跃表几乎只用于有序集合。
zskiplistNode: 这是跳跃表的节点结构定义。每个节点代表有序集合中的一个元素。zskiplistLevel: 这个结构体定义了跳跃表节点在不同层级的信息每个节点可以有一个或多个层级level。 forward: 是一个指向同一层级的下一个节点的指针。在查找操作中这个指针允许我们“跳过”一些节点从而更快地在跳跃表中进行搜索。 span: 这是一个无符号整数它记录了当前节点与通过 forward 指针所指向的下一个节点之间的跨度。在进行范围查询或者计算排名时这个值非常有用因为它可以快速计算出两个节点之间的间隔。 backward: 这是一个指向当前节点前一个节点的指针在双向遍历时使用。 score: 这是一个双精度浮点数用来保存节点的分数值。在有序集合中元素是根据这个分数进行排序的分数相同时则按照存储的对象obj来进行字典序比较。 obj: 这是一个指向实际存储数据的指针通常是一个字符串类型。在 Redis 中这是指向 robjRedis 对象的指针它可以存储字符串、列表、哈希表等不同类型的数据结构。 level[]: 这是一个大小可变的数组它的具体长度取决于节点所在的层数。这个数组存储每一层的 zskiplistLevel 结构体允许节点在跳跃表的多个层级上存在。
可以通过zskiplist持有这些节点。 为什么要用跳跃表 简单性跳表的算法和代码实现相比平衡树要简单得多。对于平衡树如 AVL 树或红黑树它们的旋转操作逻辑复杂难以编写且容易出错。跳表提供了一种容易理解和实现的高效有序数据结构。 效率跳表的查找、插入和删除操作的平均时间复杂度都是 O(log n)与平衡树相当。 灵活性跳表支持快速的顺序访问和有效的范围查询这对于数据库索引来说是非常重要的。 并发性跳表的数据结构更容易实现锁定机制这使得在并发环境下的性能表现更好。由于节点的层次结构跳表可以更容易地实现细粒度锁或无锁并发算法。 动态跳表无需预先知道数据规模它可以根据实际需要动态地进行扩展这在不可预知数据量的实时系统中非常有用。 空间效率虽然跳表的多层结构需要额外的空间来存储指针但它的空间复杂度仍然是线性的O(n)而且在实践中这个额外空间的使用通常是可控的。 实践在实际应用中跳表往往能够提供与平衡树相似或有时候更优的性能表现特别是在插入和删除操作频繁的场景中。
