怎么進(jìn)行Redis radix tree源碼解析

這篇文章將為大家詳細(xì)講解有關(guān)怎么進(jìn)行Redis radix tree源碼解析，文章內(nèi)容質(zhì)量較高，因此小編分享給大家做個(gè)參考，希望大家閱讀完這篇文章后對(duì)相關(guān)知識(shí)有一定的了解。

Redis實(shí)現(xiàn)了不定長(zhǎng)壓縮前綴的radix tree，用在集群模式下存儲(chǔ)slot對(duì)應(yīng)的的所有key信息。本文將詳述在Redis中如何實(shí)現(xiàn)radix tree。

核心數(shù)據(jù)結(jié)構(gòu)

raxNode是radix tree的核心數(shù)據(jù)結(jié)構(gòu)，其結(jié)構(gòu)體如下代碼所示：

typedef struct raxNode {
    uint32_t iskey:1;     
    uint32_t isnull:1;    
    uint32_t iscompr:1;   
    uint32_t size:29;     
    unsigned char data[];
} raxNode;

• iskey：表示這個(gè)節(jié)點(diǎn)是否包含key

• 0：沒(méi)有key

• 1：表示從頭部到其父節(jié)點(diǎn)的路徑完整的存儲(chǔ)了key，查找的時(shí)候按子節(jié)點(diǎn)iskey=1來(lái)判斷key是否存在

• isnull：是否有存儲(chǔ)value值，比如存儲(chǔ)元數(shù)據(jù)就只有key，沒(méi)有value值。value值也是存儲(chǔ)在data中

• iscompr：是否有前綴壓縮，決定了data存儲(chǔ)的數(shù)據(jù)結(jié)構(gòu)

• size：該節(jié)點(diǎn)存儲(chǔ)的字符個(gè)數(shù)

• data：存儲(chǔ)子節(jié)點(diǎn)的信息

• 
  

• iscompr=1：壓縮模式下，數(shù)據(jù)格式是：[header strlen=3][xyz][z-ptr](value-ptr?)，只有一個(gè)指針，指向下一個(gè)節(jié)點(diǎn)。size個(gè)字符是壓縮字符片段

• iscompr=0：非壓縮模式下，數(shù)據(jù)格式是：[header strlen=0][abc][a-ptr][b-ptr][c-ptr](value-ptr?)，有size個(gè)字符，緊跟著是size個(gè)指針，指向每個(gè)字符對(duì)應(yīng)的下一個(gè)節(jié)點(diǎn)。size個(gè)字符之間互相沒(méi)有路徑聯(lián)系。

Rax Insert

以下用幾個(gè)示例來(lái)詳解rax tree插入的流程。假設(shè)j是遍歷已有節(jié)點(diǎn)的游標(biāo)，i是遍歷新增節(jié)點(diǎn)的游標(biāo)。

場(chǎng)景一：只插入abcd

z-ptr指向的葉子節(jié)點(diǎn)iskey=1，使用了壓縮前綴。

場(chǎng)景二：在abcd之后插入abcdef

從abcd父節(jié)點(diǎn)的每個(gè)壓縮前綴字符比較，遍歷完所有abcd節(jié)點(diǎn)后指向了其空子節(jié)點(diǎn)，j = 0， i < len(abcded)。
查找到abcd的空子節(jié)點(diǎn)，直接將ef賦值到子節(jié)點(diǎn)上，成為abcd的子節(jié)點(diǎn)。ef節(jié)點(diǎn)被標(biāo)記為iskey=1，用來(lái)標(biāo)識(shí)abcd這個(gè)key。ef節(jié)點(diǎn)下再創(chuàng)建一個(gè)空子節(jié)點(diǎn)，iskey=1來(lái)表示abcdef這個(gè)key。

場(chǎng)景三：在abcd之后插入ab

ab在abcd能找到前兩位的前綴，也就是i=len(ab)，j < len(abcd)。
將abcd分割成ab和cd兩個(gè)子節(jié)點(diǎn)，cd也是一個(gè)壓縮前綴節(jié)點(diǎn)，cd同時(shí)被標(biāo)記為iskey=1，來(lái)表示ab這個(gè)key。
cd下掛著一個(gè)空子節(jié)點(diǎn)，來(lái)標(biāo)記abcd這個(gè)key。

場(chǎng)景四：在abcd之后插入abABC

abcABC在abcd中只找到了ab這個(gè)前綴，即i < len(abcABC)，j < len(abcd)。這個(gè)步驟有點(diǎn)復(fù)雜，分解一下：

• step 1：將abcd從ab之后拆分，拆分成ab、c、d 三個(gè)節(jié)點(diǎn)。

• step 2：c節(jié)點(diǎn)是一個(gè)非壓縮的節(jié)點(diǎn)，c掛在ab子節(jié)點(diǎn)上。

• step 3：d節(jié)點(diǎn)只有一個(gè)字符，所以也是一個(gè)非壓縮節(jié)點(diǎn)，掛在c子節(jié)點(diǎn)上。

• step 4：將ABC 拆分成了A和BC， A掛在ab子節(jié)點(diǎn)上，和c節(jié)點(diǎn)屬于同一個(gè)節(jié)點(diǎn)，這樣A就和c同屬于父節(jié)點(diǎn)ab。

• step 5：將BC作為一個(gè)壓縮前綴的節(jié)點(diǎn)，掛在A子節(jié)點(diǎn)下。

• step 6：d節(jié)點(diǎn)和BC節(jié)點(diǎn)都掛一個(gè)空子節(jié)點(diǎn)分別標(biāo)識(shí)abcd和abcABC這兩個(gè)key。

場(chǎng)景五：在abcd之后插入Aabc

abcd和Aabc沒(méi)有前綴匹配，i = 0，j = 0。
將abcd拆分成a、bcd兩個(gè)節(jié)點(diǎn)，a節(jié)點(diǎn)是一個(gè)非壓縮前綴節(jié)點(diǎn)。
將Aabc拆分成A、abc兩個(gè)節(jié)點(diǎn)，A節(jié)點(diǎn)也是一個(gè)非壓縮前綴節(jié)點(diǎn)。
將A節(jié)點(diǎn)掛在和a相同的父節(jié)點(diǎn)上。
同上，在bcd和abc這兩個(gè)節(jié)點(diǎn)下掛空子節(jié)點(diǎn)來(lái)分別表示兩個(gè)key。

Rax Remove

刪除

刪除一個(gè)key的流程比較簡(jiǎn)單，找到iskey的節(jié)點(diǎn)后，向上遍歷父節(jié)點(diǎn)刪除非iskey的節(jié)點(diǎn)。如果是非壓縮的父節(jié)點(diǎn)并且size > 1，表示還有其他非相關(guān)的路徑存在，則需要按刪除子節(jié)點(diǎn)的模式去處理這個(gè)父節(jié)點(diǎn)，主要是做memove和realloc。

合并

刪除一個(gè)key之后需要嘗試做一些合并，以收斂樹(shù)的高度。
合并的條件是：

• iskey=1的節(jié)點(diǎn)不能合并

• 子節(jié)點(diǎn)只有一個(gè)字符

• 父節(jié)點(diǎn)只有一個(gè)子節(jié)點(diǎn)（如果父節(jié)點(diǎn)是壓縮前綴的節(jié)點(diǎn)，那么只有一個(gè)子節(jié)點(diǎn)，滿足條件。如果父節(jié)點(diǎn)是非壓縮前綴的節(jié)點(diǎn)，那么只能有一個(gè)字符路徑才能滿足條件）

關(guān)于怎么進(jìn)行Redis radix tree源碼解析就分享到這里了，希望以上內(nèi)容可以對(duì)大家有一定的幫助，可以學(xué)到更多知識(shí)。如果覺(jué)得文章不錯(cuò)，可以把它分享出去讓更多的人看到。