Redis数组和链表深入详解

1.数组和链表基础知识

数组
数组会在内存中开辟一块连续的空间存储数据,这种存储方式有利也有弊端。当获取数据的时候,直接通过下标值就可以获取到对应的元素,时间复杂度为O(1)。但是如果新增或者删除数据会移动大量的数据,时间复杂度为O(n)。数组的扩容机制是:如果数组空间不足,会先开辟一块新的空间地址,将原来的数组复制到新的数组中。

链表
链表不需要开辟连续的内存空间,其通过指针将所有的数据连接起来。新增或者删除的时候只需要将指针指向的地址修改就行了,时间复杂度为O(1)。但是查询的时间复杂度为O(n)。

2、链表

2.1、双向链表

双向链表是各个节点之间的逻辑关系是双向的。
双向链表中节点的组成是:prior: 指向当前节点的前置节点,data:当前节点存储的数据。next:指向当前节点的后置节点。

2.2、压缩链表

  • 压缩链表是为了节约内存开发的。
  • ziplist是一个特别的双向链表,没有维护双向指针prev next;反而是存储上一个entry的长度和当前entry长度,通过长度推算出下一个元素在什么地方。
  • 牺牲读取的性能,获得高效的存储空间,因为存储指针比存储entry长度更费内存,这就是典型的时间换空间。

2.3、quicklist链表

  • 官网介绍:
A doubly linked list of ziplists
A generic doubly linked quicklist implementation
  • 介绍:

quicklist是一个双向链表,并且是一个ziplist的双向链表,ziplist本身是一个维持数据项先后顺序的列表,而且数据项保存在一个连续的内存块种。

3、对比

3.1、双向链表

  • 双端链表便于在表的两端进行push和pop操作,但是它的内存开销比较大。
  • 双端链表每个节点上除了要保存的数据之外,还要额外保存两个指针。
  • 双端链表的各个节点是单独的内存块,地址不连续,节点多了容易产生内存碎片。

3.2、压缩列表

  • ziplist由于是一块连续的内存,所以存储效率很高。
  • ziplist不利于修改操作,每次数据变动都会引发一次内存的realloc。
  • 当ziplist长度很长的时候,一次realloc可能会导致大批量的数据拷贝,进一步降低性能。

3.3、quicklist链表

  • 空间效率和时间效率的折中。
  • 结合了双端链表和压缩列表的优点。

4、总结

在redis 3.2版本之前使用的是 双向链表和压缩链表 两种,因为双向链表占用的内存要比压缩链表高,所以创建链表时首先会创建压缩链表,在合适的时机会转化成双向链表。redis 3.2之后使用的是quicklist链表。

到此这篇关于Redis数组和链表深入详解的文章就介绍到这了,更多相关Redis数组和链表内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

  • 两路归并的数组与链表的实现方法

    复制代码 代码如下: #include<iostream>#include<assert.h>using namespace std;struct node{    int val;    node * next;    node(int v)    {        val=v;        next=NULL;    }}; node * merge(node* list1 , node * list2){    assert(list1!=NULL&&lis

  • 使用python实现数组、链表、队列、栈的方法

    引言 什么是数据结构? 数据结构是指相互之间存在着一种或多种关系的数据元素的集合和该集合中数据元素之间的关系组成. 简单来说,数据结构就是设计数据以何种方式组织并存储在计算机中. 比如:列表,集合和字典等都是数据结构 N.Wirth:"程序=数据结构+算法" 数据结构按照其逻辑结构可分为线性结构.树结构.图结构 线性结构:数据结构中的元素存在一对一的互相关系. 树结构:数据结构中的元素存在一对多的互相关系. 图结构:数据结构中的元素存在多对多的互相关系. 数组 在python中是没有数

  • Python实现队列的方法示例小结【数组,链表】

    本文实例讲述了Python实现队列的方法.分享给大家供大家参考,具体如下: Python实现队列 队列(FIFO),添加元素在队列尾,删除元素在队列头操作 列表实现队列:利用python列表方法 代码如下: # 列表实现队列 class listQueue(object): def __init__(self): self.items = [] def is_empty(self): return self.items == None def size(self): return len(sel

  • java使用数组和链表实现队列示例

    (1)用数组实现的队列: 复制代码 代码如下: //先自己定义一个接口  public interface NetJavaList {    public void add(Student t);    //继承该接口的类必须实现的方法    public Student get(int index);//队列的加入,取出,队列的大小    public int size(); } 定义一个学生类 复制代码 代码如下: class Student {      private String na

  • JavaScript将数组转换为链表的方法

    JS中将数组转换为链表 /** * 将数组转换为链表 * @param array arr 需要转换的数组 * @param int type 转换的类型,0为单链表,1为循环链表 * @return object 返回链表 */ function array2List(arr, type = 0) { if (!arr.length) return null; let header = { index: 0, data:arr[0], next: null }; let obj = heade

  • php数组和链表的区别总结

    PHP中数组和链表的区别 从逻辑结构来看 1..数组必须事先定义固定的长度(元素个数),不能适应数据动态地增减的情况.当数据增加时,可能超出原先定义的元素个数:当数据减少时,造成内存浪费:数组可以根据下标直接存取. 2.链表动态地进行存储分配,可以适应数据动态地增减的情况,且可以方便地插入.删除数据项.(数组中插入.删除数据项时,需要移动其它数据项,非常繁琐)链表必须根据next指针找到下一个元素. 从内存存储来看 1.(静态)数组从栈中分配空间, 对于程序员方便快速,但是自由度小. 2.链表从

  • Python实现栈的方法详解【基于数组和单链表两种方法】

    本文实例讲述了Python实现栈的方法.分享给大家供大家参考,具体如下: 前言 使用Python 实现栈. 两种实现方式: 基于数组 - 数组同时基于链表实现 基于单链表 - 单链表的节点时一个实例化的node 对象 完整代码可见GitHub: https://github.com/GYT0313/Python-DataStructure/tree/master/5-stack 目录结构: 注:一个完整的代码并不是使用一个py文件,而使用了多个文件通过继承方式实现. 1. 超类接口代码 arra

  • Redis数组和链表深入详解

    1.数组和链表基础知识 数组: 数组会在内存中开辟一块连续的空间存储数据,这种存储方式有利也有弊端.当获取数据的时候,直接通过下标值就可以获取到对应的元素,时间复杂度为O(1).但是如果新增或者删除数据会移动大量的数据,时间复杂度为O(n).数组的扩容机制是:如果数组空间不足,会先开辟一块新的空间地址,将原来的数组复制到新的数组中. 链表: 链表不需要开辟连续的内存空间,其通过指针将所有的数据连接起来.新增或者删除的时候只需要将指针指向的地址修改就行了,时间复杂度为O(1).但是查询的时间复杂度

  • JavaScript数据结构链表知识详解

    最近在看<javascript数据结构和算法>这本书,补一下数据结构和算法部分的知识,觉得自己这块是短板. 链表:存储有序的元素集合,但不同于数组,链表中的元素在内存中不是连续放置的.每个元素由一个存储元素本身的节点和一个指向下一个元素的引用(也称指针或链接)组成. 好处:可以添加或移除任意项,它会按需扩容,且不需要移动其他元素. 与数组的区别: 数组:可以直接访问任何位置的任何元素: 链表:想要访问链表中的一个元素,需要从起点(表头)开始迭代列表直到找到所需的元素. 做点小笔记. funct

  • PHP操作Redis常用命令的实例详解

    redis常用命令有: 1.连接操作命令: 2.持久化命令: 3.远程服务控制命令: 4.对value操作命令:5.string命令: 6.list命令: 7.set命令: 8.hash命令等等. Redis 常用命令 登录 redis-cli -p 5566 -a password 检查key是否存在 EXISTS key 搜索某关键字 KSYS *4 返回一个Key所影响的vsl的类型 TYPE key 下面通过代码看下PHP操作Redis命令,代码如下所示: //连接本地的 Redis 服

  • Redis数据类型string和Hash详解

    目录 String类型命令操作 设置指定key的值 获取指定key的值 返回key中字符串值的子串 获取多个给定key的值 返回key所对应的字符串的长度 设置一个或多个键值对 将key中所存储的数值加一 将key中所存储的数值减一 字符串追加 Hash类型 设置一个Hash数据 获取指定哈希表中所有的字段和值 获取存储在哈希表中指定字段的值 删除一个或多个哈希表字段 获取哈希表中字段的数量 获取哈希表中的所有字段 获取哈希表中所有的值 摘要:Redis中有五大数据类型,分别是String.Li

  • redis protocol通信协议及使用详解

    目录 简介 redis的高级用法 Redis中的pipline Redis中的Pub/Sub RESP protocol Simple Strings Bulk Strings RESP Integers RESP Arrays RESP Errors Inline commands 总结 简介 redis是一个非常优秀的软件,它可以用作内存数据库或者缓存.因为他的优秀性能,redis被应用在很多场合中. redis是一个客户端和服务器端的模式,客户端和服务器端是通过TCP协议进行连接的,客户端

  • C语言数据结构之单链表存储详解

    目录 1.定义一个链表结点 2.初始化单链表 3.输出链表数据 4.完整代码 如果说,顺序表的所占用的内存空间是连续的,那么链表则是随机分配的不连续的,那么为了使随机分散的内存空间串联在一起形成一种前后相连的关系,指针则起到了关键性作用. 单链表的基本结构: 头指针:永远指向链表第一个节点的位置. 头结点:不存任何数据的空节点,通常作为链表的第一个节点.对于链表来说,头节点不是必须的,它的作用只是为了方便解决某些实际问题. 首元结点:首个带有元素的结点. 其他结点:链表中其他的节点. 1.定义一

  • C语言数据结构之单链表操作详解

    目录 1.插入操作 2.删除操作 3.查找操作 4.修改操作 5.完整代码 1.插入操作 (1)创建一个新的要插入的结点 (2)将新结点的 next 指针指向插入位置后的结点 (3)将插入位置前的节点指针 next 指向新的结点 注意:步骤(2)(3)的顺序不能颠倒,否则会导致插入位置后的部分链表丢失. 插入位置一共分三种,分别是头部插入.中间插入和尾部插入. 如图: 代码: link* insertElem(link* p,int elem,int pos){ link* temp = p;/

  • JavaScript 中有关数组对象的方法(详解)

    JS 处理数组多种方法 js 中的数据类型分为两大类:原始类型和对象类型. 原始类型包括:数值.字符串.布尔值.null.undefined 对象类型包括:对象即是属性的集合,当然这里又两个特殊的对象----函数(js中的一等对象).数组(键值的有序集合). 数组元素的添加 arrayObj.push([item1 [item2 [. . . [itemN ]]]]); 将一个或多个新元素添加到数组结尾,并返回数组新长度 arrayObj.unshift([item1 [item2 [. . .

  • Redis Set 集合的实例详解

     Redis Set 集合的实例详解 Redis的Set是string类型的无序集合.集合成员是唯一的,这就意味着集合中不能出现重复的数据. redis 中 集合是通过哈希表实现的,所以添加,删除,查找的复杂度都是O(1). 集合中最大的成员数为 232 - 1 (4294967295, 每个集合可存储40多亿个成员). 实例 redis 127.0.0.1:6379> SADD runoobkey redis (integer) 1 redis 127.0.0.1:6379> SADD ru

  • Redis Sentinel服务配置流程(详解)

    1.Redis Sentinel服务配置 1.1简介 Redis 的 Sentinel 系统用于管理多个 Redis 服务器(instance), 该系统执行以下三个任务: 监控(Monitoring): Sentinel 会不断地检查你的主服务器和从服务器是否运作正常. 提醒(Notification): 当被监控的某个 Redis 服务器出现问题时, Sentinel 可以通过API 向管理员或者其他应用程序发送通知. 自动故障迁移(Automatic failover): 当一个主服务器不

随机推荐