Redis實現了不定長壓縮前綴的radix tree,用在集群模式下存儲slot對應的的所有key信息。本文將詳述在Redis中如何實現radix tree。
核心數據結構
raxNode是radix tree的核心數據結構,其結構體如下代碼所示:
typedef struct raxNode {
uint32_t iskey:1;
uint32_t isnull:1;
uint32_t iscompr:1;
uint32_t size:29;
unsigned char data[];
} raxNode;
- iskey:表示這個節點是否包含key
- 0:沒有key
- 1:表示從頭部到其父節點的路徑完整的存儲了key,查找的時候按子節點iskey=1來判斷key是否存在
- isnull:是否有存儲value值,比如存儲元數據就只有key,沒有value值。value值也是存儲在data中
- iscompr:是否有前綴壓縮,決定了data存儲的數據結構
- size:該節點存儲的字元個數
- data:存儲子節點的信息
- iscompr=0:非壓縮模式下,數據格式是:
[header strlen=0][abc][a-ptr][b-ptr][c-ptr](value-ptr?)
,有size個字元,緊跟著是size個指針,指向每個字元對應的下一個節點。size個字元之間互相沒有路徑聯繫。
- iscompr=1:壓縮模式下,數據格式是:
[header strlen=3][xyz][z-ptr](value-ptr?)
,只有一個指針,指向下一個節點。size個字元是壓縮字元片段
Rax Insert
以下用幾個示例來詳解rax tree插入的流程。假設j是遍歷已有節點的游標,i是遍歷新增節點的游標。
場景一:只插入abcd
z-ptr指向的葉子節點iskey=1,使用了壓縮前綴。