100 行代碼的壓縮前綴樹：50- smaller

本文介紹一個壓縮前綴樹實現的（sorted set（github：succinct.Set [1]）區區 95 行代碼，包含了一組完整的功能：

loc100 分支是本文中使用的最簡實現，沒有任何外部依賴，main 分支中的實現面向生產環境，要快 4 倍左右。

如果要生產環境使用，移步 slim[2]。

用 20 萬個網上詞彙來測試本文實現的 succinctSet：

原始數據大小：2204 KB

跟 string 數組的 bsearch，以及 google btree [3] 的對比：

4wxZRu

場景和問題

計算機中的信息，爲了查詢方便，幾乎都是排序存儲的（即使是 hash 結構，hash map 中的 hash 值也是順序存儲的）。

數據存儲領域，大部分數據也都是靜態的，例如數據庫底層的一個 page，rocksdb 的一個 sstable。數據越來越大後對存儲空間的開銷也越來越敏感，畢竟影響性能的主要瓶頸都在 IO 上，不論是 CPU 對主存的訪問延遲，還是內存到磁盤的延遲，每 2 層之間的 IO 延遲，基本都在 1~2 個量級左右。於是更小的存儲開銷，不僅節省存儲成本，另一個 bonus 是幾乎毫無疑問的會提升性能。

本文針對這一個廣泛使用的場景：靜態排序數據，提供一個通用的實現方法來壓縮空間開銷。

生產環境中使用的算法，和本文介紹的方法同源，但包括更多的優化，例如通過 SIMD 指令一次處理多個字節的比較，用 bitmap 來優化 labels 的存儲，對只有一個出向 label 的節點的合併優化等。

思路：前綴樹

前綴樹 [4]，或字典樹，prefix tree，trie，是解決這類問題的一個典型思路。例如要存儲 5 個 key：[ab, abc, abcd, axy, buv] 可以建立下面這樣一個前綴樹，省去大量重複的前綴，其中 ^ 是 root 節點（也記做 0），1, 2, 3… 是 trie 節點，$標記一個葉子節點，字母 a, b... 表示一個節點到下級節點的邊（labeled branch）：

前綴樹的壓縮算法

在這個前綴樹中，每個節點至多有 256 個出向 label，指向下一級節點。一個節點可以是 inner 節點，例如 root 節點 ^，或 1, 2, 3。也可以是葉子節點，例如 3, 6, 9。這裏 3 既是一個 inner 節點也是一個 leaf 節點。

要壓縮這個 trie，對每個 trie 節點，我們需要的最核心的信息是：

我們有以下這種緊湊的結構來描述這個 trie：

一個 trie 節點的出向 label 都存儲在一個 []byte 中，再用一個 bitmap 來描述每個節點的分支，後面通過這個 bitmap 來定位 label 對應的節點。

先把每個節點對應的 label 列出來，併爲每個 label 分配一個 bit 0 來標記：

然後將所有的 label 保存在一個 []byte 中，再將對應的標記 label 的多個 0... 用 1 做分隔符連接到一起：這 2 塊信息是 succinctSet 核心的 2 個字段，有了這 2 部分數據就可以實現（不算高效的）key 查找：

壓縮後的查詢：

在標準的 trie 中查找一個 key 很簡單，在第 L 層的一個節點上，查找 key[L] 的 byte 是否是 trie 節點的一個出向 label，如果是，走到下一個節點，否則終止。

例如對 axy 的查找，要經歷 3 次查找，^ -a-> ① -x-> ④ -y-> ⑦ $：

在 succinctSet 中的查找也是一樣，唯一不同的是如何在這個沒有指針的結構中找到某個出向 label 對應的子節點。

我們把 trie 原來的 label 到子節點的關係，在壓縮後的結構中畫出來，端詳端詳：

從上圖可以看出，

例如：

你品，你細品…

品完後發現，**要找到某個 label 指向的節點，只需要先數數這個 label 對應第幾個 **0，例如是第 i 個0，再找到 bitmap 中的第 i 個 1，第 i 個 1 後面就是 label 對應的節點位置了。

這就是在壓縮前綴樹中逐層定位節點的算法。

舉個栗子 🌰

假設從根節點開始，要查找的 key 是 axy，

在 succinctSet 數據結構中畫出 axy 的查詢過程如下：

維護 leaf 節點：

上面介紹的查詢算法還有一個問題，就是當某些 key 是其他 key 的前綴時，它對應的節點既是 inner 節點，也是 leaf 節點，這時無法通過 label 的不匹配結束查詢。例如 abc 對應的節點 6:d，它本身有一個出向分支 d，是一個 inner 節點，同時也是一個 leaf 節點。

所以我們還需要額外的信息來標識所有的 leaf 節點：再建立一個 leaves 的 bitmap，它的第 i 個 bit 爲 1，表示 node-id 爲 i 的節點是 leaf 節點：

leaves 的檢查在查詢的最後一步，如果一個要查詢的 key 匹配到一個 trie 中的節點，最後再檢查它是否是一個 leaf 節點。

優化 bitmap 操作：

這個算法中最後還有一個問題沒有解決：我們提到從 label 定位 node 的過程是: 找到一個 label 之前的 0 的個數 i，再找到第 i 個的 1 的位置。這 2 個操作都是 O(n) 的，要遍歷 bitmap，最終會導致一次查詢的時間效率變成 O(n²)。

爲了能讓查詢提升效率，我們需要建立 2 份額外的信息來優化這 2 個操作。

第一個是找出一個 bitmap 中第 i 個 bit 之前有多少個 1（或多少個 `0`），對定長整數，例如一個 uint64，它的有 O(1) 的實現，例如

第二個，要得到第 i 個 1 的位置的操作，叫做 select1(i)。

我們現在需要爲 rank1() 和 select1() 分別建立緩存：

rank：

建立一個數組 rank []int32：ranks[i] 記錄 bitmap 中前 i*64 個 bit 中的 1 的數量。. 這樣要計算 rank(i) 就只需要取 ranks[i/64]，再用一個 O(1) 的函數調用（如 bits.OnesCount64()）計算 bitmap[i:i % 64] 中的 1 的個數。

例如 bitmap 中第 0 個 uint64 有 25 個 1，第 1 個 uint64 有 11 個 1，那麼建立的 ranks 索引如下：[0, 25, 36]

select：

select 索引也是一個 []int32: select[i] 記錄第 i*32 個 1 在 bitmap 中哪個位置。

例如第 0 個 1 在第 1 個 bit，第 32 個 1 在第 67 個 bit，第 64 個 1 出現在第 126 個 bit，那麼 selects 的索引就是：[1, 67, 126]：

代碼實現

Set 結構定義：

有了 ranks 的索引, 找出第 i 個 bit 之前的 1（或 `0`）的數量就可以確定用 O(1) 時間完成；而 select 索引，可以儘可能讓找出第 i 個 1 的開銷趨近於 O(1)；因爲 selects 的 2 條索引之間可能跨越幾個 uint64，取決於 bitmap 中 1 的分佈。

這樣，整個 succinctSet 的數據結構就完整了：

我們接下來看看完整的代碼邏輯：

創建 Set：

依舊以 keys = [ab, abc, abcd, axy, buv] 爲例，來描述 Set 的建立，

最後直到所有隊列中的元素都處理完，trie 就建立完成。最後再通過 init() 給建好的 trie 做 rank 和 select 的索引。

掃描前綴的過程，也就是建立 trie 節點的順序，按照 node-id 標識如下：

查詢：

trie 的查詢過程也很簡單：在要查詢的 key 中取出一個 byte，看它是否在當前節點的 label 中，如果不在，就可以確認 key 不在 succinctSet 中。如果在，通過之前提到的 select1(rank0(i)) 的方法走到下一個節點，繼續以上步驟。

當 key 中所有 byte 都檢查完後，看最後是否停在一個 leaf 節點，最終確認是否匹配到一個在 Set 中存在的 key。

bitmap 的索引：

上面我們提到，從 label 定位節點的過程主要依賴於計算 bitmap 的 2 個操作：計算指定位置前有幾個 1: rank0(i)，以及找出第 i 個 1 的位置：select1(i)。

go 裏面提供了 uint64 的 rank 操作，bits.OnesCount64() 可以在 O(1) 的時間內返回一個 uint64 中被置爲 1 的 bit 數。我們用它來給 bitmap 中每個 unit64 提前計算好前面有幾個 1，這樣在使用的時候只需要再處理最後一個 uint64 就可以了。

select 的索引直接逐個計數 1 的個數，然後在個數滿 32 整數倍時添加一條索引。

當我們要利用索引取第 i 個 bit 前有幾個 0 時，通過 rank0(i) = i - rank1(i) 來計算：

在查找第 i 個 1 所在位置時，我們先通過 selects 索引找到一個最接近的 uint64，再向後逐個查找直到見到第 i 個 1。這一步的性能不是嚴格的 O(1)：

性能分析

我們用網上搜集到的數據集做了下測試。測試中使用的負載模型都是 zipf[6] 比較符合互聯網的真實場景，zipf 的參數 s 取 1.5，細節參考 report [7] 的代碼，結果如下：

4wxZRu

Eh4FJR

可以看出在內存方面：

對查詢性能:

引用鏈接

[1] succinct.Set : https://github.com/openacid/succinct/tree/loc100
[2] slim: https://github.com/openacid/slim
[3] google btree : https://github.com/google/btree
[4] 前綴樹: https://en.wikipedia.org/wiki/Trie
[5] popcount : https://en.cppreference.com/w/cpp/numeric/popcount
[6] zipf: https://blog.openacid.com/tech/zipf/
[7] report : https://github.com/openacid/succinct/blob/v0.1.0/report/main.go

關於 Databend

Databend 是一款開源、彈性、低成本，基於對象存儲也可以做實時分析的新式數倉。期待您的關注，一起探索雲原生數倉解決方案，打造新一代開源 Data Cloud。

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/2aJ0YUvA1LXlmLHfuTYyzA

猜你喜歡