Redis資料結構SortedSet的底層原理解析

2022-07-13 18:02:03

概述

一些常用命令

儲存：zadd key score value
獲取：zrange key start end
獲取：同時獲取分數：zrange key start end with score
刪除：zrem key value

儲存的時候我們可以發現，是有一個score（分數）的，這個就是用來排序的欄位。

實現

先說結論，SortedSet底層，根據設定會在不同的時候選用兩種不同的資料結構zset，或ziplist進行儲存：

首先，我們來看幾個引數：

zset-max-ziplist-entries 128
zset-max-ziplist-value 64

if (
    field-value對的數量 > ziplist.entries.size ||
    任意一個filed或value長度 > zset-max-ziplist-value
) {
    // 使用 zset 進行儲存
} else {
    // 使用 ziplist 進行儲存

zset的結構如下：

typedef struct zset {
    dict *dict;
    zskiplist *zsl;
} zset

可以發現，是由字典+跳躍表實現的。

zset 結構體裡有兩個元素，一個是 dict，用來維護資料到分數的關係，一個是 zskiplist，用來維護分數所在連結串列的關係
dict 裡通過維護雜湊表儲存了張三=>100，李四=>90 的分數關係。

而跳錶則是排序的關鍵

跳躍表

先上圖：

我們知道，連結串列的檢索效率是非常低的，如果要拿到100條資料中間的資料，則需要遍歷50個資料才行，為了解決這個問題，跳錶應運而生

如上圖，就是常規的跳錶，會在原有的資料上加上若干層，指向當前層的下一個節點。

跳錶的插入

如上圖所示：其實每個節點的層數是隨機的，而且新插入一個節點不會影響其它節點的層數。因此，插入操作只需要修改插入節點前後的指標，而不需要對很多節點都進行調整。這就降低了插入操作的複雜度。實際上，這是skiplist跳錶的一個很重要的特性，這讓它在插入效能上明顯優於平衡樹的方案。

如下圖，假如我們需要查詢23，查詢的路徑如下。

事實上，在插入之前也要先經歷一個類似的查詢過程，在確定插入位置後，再完成插入操作。

這也是SortedSet實現排序的原理。

壓縮列表

壓縮列表 ziplist 是為 Redis 節約記憶體而開發的。

壓縮列表是由一系列特殊編碼的連續記憶體塊組成的順序型資料結構，一個壓縮列表可以包含任意多個節點（entry），每個節點可以儲存一個位元組陣列或者一個整數值。

1、zl bytes：用於記錄整個壓縮列表佔用的記憶體位元組數

2、zl tail：記錄要列表尾節點距離壓縮列表的起始地址有多少位元組

3、zl len：記錄了壓縮列表包含的節點數量。

4、entryX：要說列表包含的各個節點

5、zl end：用於標記壓縮列表的末端

壓縮列表是一種為了節約記憶體而開發的順序型資料結構

壓縮列表被用作列表鍵和雜湊鍵的底層實現之一

壓縮列表可以包含多個節點，每個節點可以儲存一個位元組陣列或者整數值

新增新節點到壓縮列表，可能會引發連鎖更新操作。

以上為個人經驗，希望能給大家一個參考，也希望大家多多支援it145.com。

Redis資料結構SortedSet的底層原理解析

目錄

概述

一些常用命令

實現

跳躍表

跳錶的插入

壓縮列表

熱門文章