圖解Redis中的Radix樹

2020 年 3 月 11 日
筆記

在Redis里，有好幾個地方都用到了Radix樹。比如阿里的Redis的每個slot槽里存儲的key就是使用了Radix樹。還有Redis 5.0發佈的一個新功能Stream也有用到Radix來存儲key。

你也許會想通過key查找value，為什麼不通過hash map之類的，java的小夥伴肯定知道hash對於大量的key的hash後最後還是要落到鏈表（現在變成了紅黑樹）。hash這個被認為只適合少量的數據存儲查找，多了遭不住，而且還要rehash之類的，肯定不能用這個來搞定redis的key存儲。這會你也許想過使用紅黑樹這樣的平衡樹來存儲redis的key。這確實是個不錯的方案，但紅黑樹也被認為是有一些性能問題，而且在Redis key檢索的場景下，也許會有更適合的算法來hold住。

為此Redis的大佬們決定使用Radix樹來解決問題。Radix樹是從哪裡來的呢？是從Trie樹來的。我們先來簡單的了解一下Trie長啥樣。

Trie樹

Trie Tree，字典樹。Trie Tree的原理是將每個key拆分成每個單位長度字符，然後對應到每個分支上，分支所在的節點對應為從根節點到當前節點的拼接出的key的值。它的結構圖如下所示：

（此圖摘自Trie Tree wiki，水印忽略）

大體就長這樣，可以看出Trie樹已經很厲害了。Trie樹把很多的公共前綴獨立出來共享了。這樣避免了很多重複的存儲。想想字典集的方式，一個個的key被單獨的存儲，即使他們都有公共的前綴也要單獨存儲。相比字典集的方式，Trie樹顯然節省更多的空間。

Trie樹其實依然比較浪費空間，有人曾經反饋他們在實際的項目發現，隨着key的數量的增加，發現Trie樹會佔用大量的內存和空間。

現在我們就演繹下Trie樹是如何浪費內存和空間的。比如下面的一組數據：

{ "deck": someValue, "did": someValue, "doe": someValue, "dog": someValue, "doge": someValue, "dogs": someValue }

我用Trie樹的畫法把上面的key value畫出來如下：

Radix樹：壓縮後的Trie樹

也許你已經發現了一些問題。比如"deck"這一個分支，有沒有必要一直往下來拆分嗎？還是"did"，有必要d，然後i，然後d嗎?像這樣的不可分叉的單支分支，其實完全可以合併，也就是壓縮。像下面這樣：

這樣看起來是不是要更節省一點空間呢？這只是6個單詞的樣子，數據越多，空間節省的效果越明顯。而且這樣壓縮後，不可分叉的分支高度也變矮了。我們叫這樣的Trie樹為壓縮Trie樹（Compressed Trie Tree）。

壓縮Trie樹也就是今天的主角Radix樹，只不過他有多個名字，有人叫壓縮Trie樹，有人叫Radix樹。

Redis中就用到了Radix樹。

計算機是怎麼處理Radix樹的呢?

現在還沒完，因為計算機可不會像人類一樣可以通過英文像上面的圖一樣來構建樹，計算機只認識0和1。所以為了真正的了解Radix樹，我們需要知道機器是怎麼讀取Radix樹的。計算機對於Radix樹的處理是以bit（或二進制數字）來讀取的。一次被對比r個bit，2的r次方是radix樹的基數。這也是基數樹的這個名字的由來。

現在我們把上面的三個單詞變成二進制的樣子，然後一位一位的看：

dog: 01100100 01101111 01100111 doge: 01100100 01101111 01100111 01100101 dogs: 01100100 01101111 01100111 01110011

按照字符串的比對，你會發現dog是dogs和doge的子串。

但我們現在比對二進制，一位一位的比對，你會發現dog和doge是在第二十五位的時候不一樣的。dogs和doge是在第二十八位不一樣的。按照位的比對的結果，你會發現doge居然是dogs二進制子串。秀不秀？

這就是計算機的方式。

到此，我們其實已經基本了解Radix了。

現在看看它在Redis內部是怎麼布局的。

Redis是如何實現Radix樹的呢？

以下內容摘自http://mysql.taobao.org/monthly/2019/04/03/

raxNode是radix tree的核心數據結構，其結構體如下所示：

typedef struct raxNode {

uint32_t iskey:1; //是否包含key,

uint32_t isnull:1; //是否有存儲value值，比如存儲元數據就只有key，沒有value值。value值也是存儲在data中

uint32_t iscompr:1; //是否做了前綴壓縮

uint32_t size:29; //該節點存儲的字符個數

unsigned char data[]; //存儲子節點的信息

} raxNode;

下面我們就以插入場景為例，挨個插入幾個字符串。假設j是遍歷已有節點的游標，i是遍歷新增節點的游標。

場景一：只插入abcd

z-ptr指向的葉子節點iskey=1，使用了壓縮前綴。

場景二：在abcd之後插入abcdef

從abcd父節點的每個壓縮前綴字符比較，遍歷完所有abcd節點後指向了其空子節點，j = 0， i < len(abcded)。查找到abcd的空子節點，直接將ef賦值到子節點上，成為abcd的子節點。ef節點被標記為iskey=1，用來標識abcd這個key。ef節點下再創建一個空子節點，iskey=1來表示abcdef這個key。

場景三：在abcd之後插入ab

ab在abcd能找到前兩位的前綴，也就是i=len(ab)，j < len(abcd)。將abcd分割成ab和cd兩個子節點，cd也是一個壓縮前綴節點，cd同時被標記為iskey=1，來表示ab這個key。 cd下掛着一個空子節點，來標記abcd這個key。

場景四：在abcd之後插入abABC

abcABC在abcd中只找到了ab這個前綴，即i < len(abcABC)，j < len(abcd)。這個步驟有點複雜，分解一下：

step 1：將abcd從ab之後拆分，拆分成ab、c、d 三個節點。
step 2：c節點是一個非壓縮的節點，c掛在ab子節點上。
step 3：d節點只有一個字符，所以也是一個非壓縮節點，掛在c子節點上。
step 4：將ABC 拆分成了A和BC， A掛在ab子節點上，和c節點屬於同一個節點，這樣A就和c同屬於父節點ab。
step 5：將BC作為一個壓縮前綴的節點，掛在A子節點下。
step 6：d節點和BC節點都掛一個空子節點分別標識abcd和abcABC這兩個key。

總結

1、Redis用到了Radix樹來存儲key，Redis Stream中的key也用到了Radix樹。

2、Radix樹是壓縮版的Trie樹。

3、計算機處理Radix樹是比較二進制位，和我們的直覺會有所偏差。

4、Radix和Trie樹對於字符串的檢索，特別是有公共前綴的場景。如當輸入一個網址，可以自動搜索出可能的選擇。當沒有完全匹配的搜索結果，可以返回前綴最相似的可能。總之對於字符串的檢索，Trie類樹都比較適合，比如本文中的Redis的key這樣的場景就非常適合。