免费观看又色又爽又黄的小说免费_美女福利视频国产片_亚洲欧美精品_美国一级大黄大色毛片

Redis中都有哪些數據結構

今天就跟大家聊聊有關redis中都有哪些數據結構,可能很多人都不太了解,為了讓大家更加了解,小編給大家總結了以下內容,希望大家根據這篇文章可以有所收獲。

創新互聯建站專注于阿克蘇企業網站建設,響應式網站,商城網站定制開發。阿克蘇網站建設公司,為阿克蘇等地區提供建站服務。全流程按需搭建網站,專業設計,全程項目跟蹤,創新互聯建站專業和態度為您提供的服務

Redis核心對象

在Redis中有一個「核心的對象」叫做redisObject ,是用來表示所有的key和value的,用redisObject結構體來表示String、Hash、List、Set、ZSet五種數據類型。

redisObject的源代碼在redis.h中,使用c語言寫的,感興趣的可以自行查看,關于redisObject我這里畫了一張圖,表示redisObject的結構如下所示:

Redis中都有哪些數據結構

閃瞎人的五顏六色圖

在redisObject中「type表示屬于哪種數據類型,encoding表示該數據的存儲方式」,也就是底層的實現的該數據類型的數據結構。因此這篇文章具體介紹的也是encoding對應的部分。

那么encoding中的存儲類型又分別表示什么意思呢?具體數據類型所表示的含義,如下圖所示:

Redis中都有哪些數據結構

圖片截圖出自《Redis設計與實現第二版》

可能看完這圖,還是覺得一臉懵。不慌,會進行五種數據結構的詳細介紹,這張圖只是讓你找到每種中數據結構對應的儲存類型有哪些,大概腦子里有個印象。

舉一個簡單的例子,你在Redis中設置一個字符串key 234,然后查看這個字符串的存儲類型就會看到為int類型,非整數型的使用的是embstr儲存類型,具體操作如下圖所示:

Redis中都有哪些數據結構

String類型

String是Redis最基本的數據類型,上面的簡介中也說到Redis是用c語言開發的。但是Redis中的字符串和c語言中的字符串類型卻是有明顯的區別。

String類型的數據結構存儲方式有三種int、raw、embstr。那么這三種存儲方式有什么區別呢?

int

Redis中規定假如存儲的是「整數型值」,比如set num 123這樣的類型,就會使用 int的存儲方式進行存儲,在redisObject的「ptr屬性」中就會保存該值。

Redis中都有哪些數據結構

SDS

假如存儲的「字符串是一個字符串值并且長度大于32個字節」就會使用SDS(simple dynamic string)方式進行存儲,并且encoding設置為raw;若是「字符串長度小于等于32個字節」就會將encoding改為embstr來保存字符串。

SDS稱為「簡單動態字符串」,對于SDS中的定義在Redis的源碼中有的三個屬性int len、int free、char buf[]。

len保存了字符串的長度,free表示buf數組中未使用的字節數量,buf數組則是保存字符串的每一個字符元素。

因此當你在Redsi中存儲一個字符串Hello時,根據Redis的源代碼的描述可以畫出SDS的形式的redisObject結構圖如下圖所示:

Redis中都有哪些數據結構

SDS與c語言字符串對比

Redis使用SDS作為存儲字符串的類型肯定是有自己的優勢,SDS與c語言的字符串相比,SDS對c語言的字符串做了自己的設計和優化,具體優勢有以下幾點:

(1)c語言中的字符串并不會記錄自己的長度,因此「每次獲取字符串的長度都會遍歷得到,時間的復雜度是O(n)」,而Redis中獲取字符串只要讀取len的值就可,時間復雜度變為O(1)。

(2)「c語言」中兩個字符串拼接,若是沒有分配足夠長度的內存空間就「會出現緩沖區溢出的情況」;而「SDS」會先根據len屬性判斷空間是否滿足要求,若是空間不夠,就會進行相應的空間擴展,所以「不會出現緩沖區溢出的情況」。

(3)SDS還提供「空間預分配」和「惰性空間釋放」兩種策略。在為字符串分配空間時,分配的空間比實際要多,這樣就能「減少連續的執行字符串增長帶來內存重新分配的次數」。

當字符串被縮短的時候,SDS也不會立即回收不適用的空間,而是通過free屬性將不使用的空間記錄下來,等后面使用的時候再釋放。

具體的空間預分配原則是:「當修改字符串后的長度len小于1MB,就會預分配和len一樣長度的空間,即len=free;若是len大于1MB,free分配的空間大小就為1MB」。

(4)SDS是二進制安全的,除了可以儲存字符串以外還可以儲存二進制文件(如圖片、音頻,視頻等文件的二進制數據);而c語言中的字符串是以空字符串作為結束符,一些圖片中含有結束符,因此不是二進制安全的。

為了方便易懂,做了一個c語言的字符串和SDS進行對比的表格,如下所示:

c語言字符串SDS
獲取長度的時間復雜度為O(n)獲取長度的時間復雜度為O(1)
不是二進制安全的是二進制安全的
只能保存字符串還可以保存二進制數據
n次增長字符串必然會帶來n次的內存分配n次增長字符串內存分配的次數<=n

String類型應用

說到這里我相信很多人可以說已經精通Redis的String類型了,但是純理論的精通,理論還是得應用實踐,上面說到String可以用來存儲圖片,現在就以圖片存儲作為案例實現。

(1)首先要把上傳得圖片進行編碼,這里寫了一個工具類把圖片處理成了Base64得編碼形式,具體得實現代碼如下:

/**     * 將圖片內容處理成Base64編碼格式      * @param file      * @return      */     public static String encodeImg(MultipartFile file) {         byte[] imgBytes = null;         try {             imgBytes = file.getBytes();         } catch (IOException e) {             e.printStackTrace();         }         BASE64Encoder encoder = new BASE64Encoder();         return imgBytes==null?null:encoder.encode(imgBytes );     }

(2)第二步就是把處理后的圖片字符串格式存儲進Redis中,實現的代碼如下所示:

/**     * Redis存儲圖片     * @param file     * @return     */    public void uploadImageServiceImpl(MultipartFile image) {        String imgId = UUID.randomUUID().toString();        String imgStr= ImageUtils.encodeImg(image);        redisUtils.set(imgId , imgStr);        // 后續操作可以把imgId存進數據庫對應的字段,如果需要從redis中取出,只要獲取到這個字段后從redis中取出即可。    }

這樣就是實現了圖片得二進制存儲,當然String類型得數據結構得應用也還有常規計數:「統計微博數、統計粉絲數」等。

Hash類型

Hash對象的實現方式有兩種分別是ziplist、hashtable,其中hashtable的存儲方式key是String類型的,value也是以key value的形式進行存儲。

字典類型的底層就是hashtable實現的,明白了字典的底層實現原理也就是明白了hashtable的實現原理,hashtable的實現原理可以與HashMap的是底層原理相類比。

字典

兩者在新增時都會通過key計算出數組下標,不同的是計算法方式不同,HashMap中是以hash函數的方式,而hashtable中計算出hash值后,還要通過sizemask 屬性和哈希值再次得到數組下標。

我們知道hash表最大的問題就是hash沖突,為了解決hash沖突,假如hashtable中不同的key通過計算得到同一個index,就會形成單向鏈表(「鏈地址法」),如下圖所示:

Redis中都有哪些數據結構

rehash

在字典的底層實現中,value對象以每一個dictEntry的對象進行存儲,當hash表中的存放的鍵值對不斷的增加或者減少時,需要對hash表進行一個擴展或者收縮。

這里就會和HashMap一樣也會就進行rehash操作,進行重新散列排布。從上圖中可以看到有ht[0]和ht[1]兩個對象,先來看看對象中的屬性是干嘛用的。

在hash表結構定義中有四個屬性分別是dictEntry **table、unsigned long size、unsigned long sizemask、unsigned long used,分別表示的含義就是「哈希表數組、hash表大小、用于計算索引值,總是等于size-1、hash表中已有的節點數」。

ht[0]是用來最開始存儲數據的,當要進行擴展或者收縮時,ht[0]的大小就決定了ht[1]的大小,ht[0]中的所有的鍵值對就會重新散列到ht[1]中。

擴展操作:ht[1]擴展的大小是比當前 ht[0].used 值的二倍大的第一個 2 的整數冪;收縮操作:ht[0].used 的第一個大于等于的 2 的整數冪。

當ht[0]上的所有的鍵值對都rehash到ht[1]中,會重新計算所有的數組下標值,當數據遷移完后ht[0]就會被釋放,然后將ht[1]改為ht[0],并新創建ht[1],為下一次的擴展和收縮做準備。

漸進式rehash

假如在rehash的過程中數據量非常大,Redis不是一次性把全部數據rehash成功,這樣會導致Redis對外服務停止,Redis內部為了處理這種情況采用「漸進式的rehash」。

Redis將所有的rehash的操作分成多步進行,直到都rehash完成,具體的實現與對象中的rehashindex屬性相關,「若是rehashindex 表示為-1表示沒有rehash操作」。

當rehash操作開始時會將該值改成0,在漸進式rehash的過程「更新、刪除、查詢會在ht[0]和ht[1]中都進行」,比如更新一個值先更新ht[0],然后再更新ht[1]。

而新增操作直接就新增到ht[1]表中,ht[0]不會新增任何的數據,這樣保證「ht[0]只減不增,直到最后的某一個時刻變成空表」,這樣rehash操作完成。

上面就是字典的底層hashtable的實現原理,說完了hashtable的實現原理,我們再來看看Hash數據結構的兩一種存儲方式「ziplist(壓縮列表)」

ziplist

壓縮列表(ziplist)是一組連續內存塊組成的順序的數據結構,壓縮列表能夠節省空間,壓縮列表中使用多個節點來存儲數據。

壓縮列表是列表鍵和哈希鍵底層實現的原理之一,「壓縮列表并不是以某種壓縮算法進行壓縮存儲數據,而是它表示一組連續的內存空間的使用,節省空間」,壓縮列表的內存結構圖如下:

Redis中都有哪些數據結構

壓縮列表中每一個節點表示的含義如下所示:

  1. 鴻蒙官方戰略合作共建——HarmonyOS技術社區

  2.  zlbytes:4個字節的大小,記錄壓縮列表占用內存的字節數。

  3.  zltail:4個字節大小,記錄表尾節點距離起始地址的偏移量,用于快速定位到尾節點的地址。

  4.  zllen:2個字節的大小,記錄壓縮列表中的節點數。

  5.  entry:表示列表中的每一個節點。

  6.  zlend:表示壓縮列表的特殊結束符號'0xFF'。

再壓縮列表中每一個entry節點又有三部分組成,包括previous_entry_ength、encoding、content。

  1. 鴻蒙官方戰略合作共建——HarmonyOS技術社區

  2.  previous_entry_ength表示前一個節點entry的長度,可用于計算前一個節點的其實地址,因為他們的地址是連續的。

  3.  encoding:這里保存的是content的內容類型和長度。

  4.  content:content保存的是每一個節點的內容。

Redis中都有哪些數據結構

說到這里相信大家已經都hash這種數據結構已經非常了解,若是第一次接觸Redis五種基本數據結構的底層實現的話,建議多看幾遍,下面來說一說hash的應用場景。

應用場景

哈希表相對于String類型存儲信息更加直觀,存儲更加方便,經常會用來做用戶數據的管理,存儲用戶的信息。

hash也可以用作高并發場景下使用Redis生成唯一的id。下面我們就以這兩種場景用作案例編碼實現。

存儲用戶數據

第一個場景比如我們要儲存用戶信息,一般使用用戶的ID作為key值,保持唯一性,用戶的其他信息(地址、年齡、生日、電話號碼等)作為value值存儲。

若是傳統的實現就是將用戶的信息封裝成為一個對象,通過序列化存儲數據,當需要獲取用戶信息的時候,就會通過反序列化得到用戶信息。

Redis中都有哪些數據結構

但是這樣必然會造成序列化和反序列化的性能的開銷,并且若是只修改其中的一個屬性值,就需要把整個對象序列化出來,操作的動作太大,造成不必要的性能開銷。

若是使用Redis的hash來存儲用戶數據,就會將原來的value值又看成了一個k v形式的存儲容器,這樣就不會帶來序列化的性能開銷的問題。

Redis中都有哪些數據結構

分布式生成唯一ID

第二個場景就是生成分布式的唯一ID,這個場景下就是把redis封裝成了一個工具類進行實現,實現的代碼如下:

// offset表示的是id的遞增梯度值   public Long getId(String key,String hashKey,Long offset) throws BusinessException{       try {           if (null == offset) {               offset=1L;           }           // 生成唯一id           return redisUtil.increment(key, hashKey, offset);       } catch (Exception e) {           //若是出現異常就是用uuid來生成唯一的id值           int randNo=UUID.randomUUID().toString().hashCode();           if (randNo < 0) {               randNo=-randNo;           }           return Long.valueOf(String.format("%16d", randNo));       }   }

List類型

Redis中的列表在3.2之前的版本是使用ziplist和linkedlist進行實現的。在3.2之后的版本就是引入了quicklist。

ziplist壓縮列表上面已經講過了,我們來看看linkedlist和quicklist的結構是怎么樣的。

linkedlist是一個雙向鏈表,他和普通的鏈表一樣都是由指向前后節點的指針。插入、修改、更新的時間復雜度尾O(1),但是查詢的時間復雜度確實O(n)。

linkedlist和quicklist的底層實現是采用鏈表進行實現,在c語言中并沒有內置的鏈表這種數據結構,Redis實現了自己的鏈表結構。

Redis中都有哪些數據結構

Redis中鏈表的特性:

  1. 鴻蒙官方戰略合作共建——HarmonyOS技術社區

  2.  每一個節點都有指向前一個節點和后一個節點的指針。

  3.  頭節點和尾節點的prev和next指針指向為null,所以鏈表是無環的。

  4.  鏈表有自己長度的信息,獲取長度的時間復雜度為O(1)。

Redis中List的實現比較簡單,下面我們就來看看它的應用場景。

應用場景

Redis中的列表可以實現「阻塞隊列」,結合lpush和brpop命令就可以實現。生產者使用lupsh從列表的左側插入元素,消費者使用brpop命令從隊列的右側獲取元素進行消費。

(1)首先配置redis的配置,為了方便我就直接放在application.yml配置文件中,實際中可以把redis的配置文件放在一個redis.properties文件單獨放置,具體配置如下:

spring  redis:  host: 127.0.0.1  port: 6379  password: user  timeout: 0  database: 2  pool:  max-active: 100  max-idle: 10  min-idle: 0  max-wait: 100000

(2)第二步創建redis的配置類,叫做RedisConfig,并標注上@Configuration注解,表明他是一個配置類。

@Configuration  public class RedisConfiguration {  @Value("${spring.redis.host}")  private String host;  @Value("${spring.redis.port}")  private int port;  @Value("${spring.redis.password}")  private String password;  @Value("${spring.redis.pool.max-active}")  private int maxActive;  @Value("${spring.redis.pool.max-idle}")  private int maxIdle;  @Value("${spring.redis.pool.min-idle}")  private int minIdle;  @Value("${spring.redis.pool.max-wait}")  private int maxWait;  @Value("${spring.redis.database}")  private int database;  @Value("${spring.redis.timeout}")  private int timeout;  @Bean  public JedisPoolConfig getRedisConfiguration(){  JedisPoolConfig jedisPoolConfig= new JedisPoolConfig();  jedisPoolConfig.setMaxTotal(maxActive);  jedisPoolConfig.setMaxIdle(maxIdle);  jedisPoolConfig.setMinIdle(minIdle);  jedisPoolConfig.setMaxWaitMillis(maxWait);  return jedisPoolConfig;  }  @Bean  public JedisConnectionFactory getConnectionFactory() {  JedisConnectionFactory factory = new JedisConnectionFactory();  factory.setHostName(host);  factory.setPort(port);  factory.setPassword(password);  factory.setDatabase(database);  JedisPoolConfig jedisPoolConfig= getRedisConfiguration();  factory.setPoolConfig(jedisPoolConfig);  return factory; }  @Bean  public RedisTemplate<?, ?> getRedisTemplate() {  JedisConnectionFactory factory = getConnectionFactory();  RedisTemplate<?, ?> redisTemplate = new StringRedisTemplate(factory);  return redisTemplate;  }  }

(3)第三步就是創建Redis的工具類RedisUtil,自從學了面向對象后,就喜歡把一些通用的東西拆成工具類,好像一個一個零件,需要的時候,就把它組裝起來。

@Component  public class RedisUtil {  @Autowired  private RedisTemplate<String, Object> redisTemplate;  /**  * 存消息到消息隊列中  * @param key 鍵  * @param value 值  * @return  */  public boolean lPushMessage(String key, Object value) {  try {  redisTemplate.opsForList().leftPush(key, value);  return true;  } catch (Exception e) {  e.printStackTrace();  return false;  }  }  /**  * 從消息隊列中彈出消息  * @param key 鍵  * @return  */  public Object rPopMessage(String key) {  try {  return redisTemplate.opsForList().rightPop(key);  } catch (Exception e) {  e.printStackTrace();  return null;  }  }  /**  * 查看消息  * @param key 鍵  * @param start 開始  * @param end 結束 0 到 -1代表所有值  * @return  */  public List<Object> getMessage(String key, long start, long end) {  try {  return redisTemplate.opsForList().range(key, start, end);  } catch (Exception e) {  e.printStackTrace();  return null;  }  }

這樣就完成了Redis消息隊列工具類的創建,在后面的代碼中就可以直接使用。

Set集合

Redis中列表和集合都可以用來存儲字符串,但是「Set是不可重復的集合,而List列表可以存儲相同的字符串」,Set集合是無序的這個和后面講的ZSet有序集合相對。

Set的底層實現是「ht和intset」,ht(哈希表)前面已經詳細了解過,下面我們來看看inset類型的存儲結構。

inset也叫做整數集合,用于保存整數值的數據結構類型,它可以保存int16_t、int32_t 或者int64_t 的整數值。

在整數集合中,有三個屬性值encoding、length、contents[],分別表示編碼方式、整數集合的長度、以及元素內容,length就是記錄contents里面的大小。

在整數集合新增元素的時候,若是超出了原集合的長度大小,就會對集合進行升級,具體的升級過程如下:

  1. 鴻蒙官方戰略合作共建——HarmonyOS技術社區

  2.  首先擴展底層數組的大小,并且數組的類型為新元素的類型。

  3.  然后將原來的數組中的元素轉為新元素的類型,并放到擴展后數組對應的位置。

  4.  整數集合升級后就不會再降級,編碼會一直保持升級后的狀態。

應用場景

Set集合的應用場景可以用來「去重、抽獎、共同好友、二度好友」等業務類型。接下來模擬一個添加好友的案例實現:

@RequestMapping(value = "/addFriend", method = RequestMethod.POST)  public Long addFriend(User user, String friend) {      String currentKey = null;      // 判斷是否是當前用戶的好友      if (AppContext.getCurrentUser().getId().equals(user.getId)) {          currentKey = user.getId.toString();      }      //若是返回0則表示不是該用戶好友      return currentKey==null?0l:setOperations.add(currentKey, friend);  }

假如兩個用戶A和B都是用上上面的這個接口添加了很多的自己的好友,那么有一個需求就是要實現獲取A和B的共同好友,那么可以進行如下操作:

public Set intersectFriend(User userA, User userB) {      return setOperations.intersect(userA.getId.toString(), userB.getId.toString());  }

舉一反三,還可以實現A用戶自己的好友,或者B用戶自己的好友等,都可以進行實現。

ZSet集合

ZSet是有序集合,從上面的圖中可以看到ZSet的底層實現是ziplist和skiplist實現的,ziplist上面已經詳細講過,這里來講解skiplist的結構實現。

skiplist也叫做「跳躍表」,跳躍表是一種有序的數據結構,它通過每一個節點維持多個指向其它節點的指針,從而達到快速訪問的目的。

skiplist有如下幾個特點:

  1. 鴻蒙官方戰略合作共建——HarmonyOS技術社區

  2.  有很多層組成,由上到下節點數逐漸密集,最上層的節點最稀疏,跨度也最大。

  3.  每一層都是一個有序鏈表,至少包含兩個節點,頭節點和尾節點。

  4.  每一層的每一個每一個節點都含有指向同一層下一個節點和下一層同一個位置節點的指針。

  5.  如果一個節點在某一層出現,那么該以下的所有鏈表同一個位置都會出現該節點。

具體實現的結構圖如下所示:

Redis中都有哪些數據結構

在跳躍表的結構中有head和tail表示指向頭節點和尾節點的指針,能快速的實現定位。level表示層數,len表示跳躍表的長度,BW表示后退指針,在從尾向前遍歷的時候使用。

BW下面還有兩個值分別表示分值(score)和成員對象(各個節點保存的成員對象)。

跳躍表的實現中,除了最底層的一層保存的是原始鏈表的完整數據,上層的節點數會越來越少,并且跨度會越來越大。

跳躍表的上面層就相當于索引層,都是為了找到最后的數據而服務的,數據量越大,條表所體現的查詢的效率就越高,和平衡樹的查詢效率相差無幾。

應用場景

因為ZSet是有序的集合,因此ZSet在實現排序類型的業務是比較常見的,比如在首頁推薦10個最熱門的帖子,也就是閱讀量由高到低,排行榜的實現等業務。

下面就選用獲取排行榜前前10名的選手作為案例實現,實現的代碼如下所示:

@Autowired  private RedisTemplate redisTemplate;  /**   * 獲取前10排名   * @return   */      public static List<levelVO > getZset(String key, long baseNum, LevelService levelService){          ZSetOperations<Serializable, Object> operations = redisTemplate.opsForZSet();          // 根據score分數值獲取前10名的數據          Set<ZSetOperations.TypedTuple<Object>> set = operations.reverseRangeWithScores(key,0,9);          List<LevelVO> list= new ArrayList<LevelVO>();          int i=1;          for (ZSetOperations.TypedTuple<Object> o:set){              int uid = (int) o.getValue();              LevelCache levelCache = levelService.getLevelCache(uid);              LevelVO levelVO = levelCache.getLevelVO();              long score = (o.getScore().longValue() - baseNum + levelVO .getCtime())/CommonUtil.multiplier;              levelVO .setScore(score);              levelVO .setRank(i);              list.add( levelVO );              i++;          }          return list;      }

看完上述內容,你們對Redis中都有哪些數據結構有進一步的了解嗎?如果還想了解更多知識或者相關內容,請關注創新互聯行業資訊頻道,感謝大家的支持。

當前文章:Redis中都有哪些數據結構
新聞來源:http://m.newbst.com/article48/jpjjep.html

成都網站建設公司_創新互聯,為您提供網站維護網站設計電子商務Google營銷型網站建設軟件開發

廣告

聲明:本網站發布的內容(圖片、視頻和文字)以用戶投稿、用戶轉載內容為主,如果涉及侵權請盡快告知,我們將會在第一時間刪除。文章觀點不代表本網站立場,如需處理請聯系客服。電話:028-86922220;郵箱:631063699@qq.com。內容未經允許不得轉載,或轉載時需注明來源: 創新互聯

網站優化排名