使用者:Drmingdrmer/沙盒

SlimTrie 類似於Trie, 是一種有序的樹，用於索引關聯數組，其中的鍵通常是字符串。 SlimTrie與Trie的不同之處在於, 它不保存完整鍵的信息, 而只保存用於定位一個鍵的關鍵信息, 因此SlimTrie具有的內存占用非常低, 對每個鍵平均占用6個byte。

應用場景

• 靜態數據索引

數據生成之後在使用階段不修改, 依賴於這個假設我們可以對索引進行更多的優化: 預先對所有的key進行掃描, 提取特徵, 大大降低索引信息的量。 在存儲系統中, 需要被索引的數據大部分是靜態的: 數據的更新是通過Append 和 Compact這2個操作完成的. 一般不需要隨機插入一條記錄.

• SlimTrie保證存在的key被正確的定位

只對存在的key給出正確返回。對於不存在的key不保證返回的結果正確，可能直接返回沒被定位到，也可能返回一個存儲存在的key的信息，這樣的設計是為了可以去掉更多與定位一個key無關的信息。

• 允許被索引到的key不一定存在

索引的目的在於快速定位一個對象, 但不保證定位到的對象一定存在，就像Btree的中間節點, 用來確定key的範圍, 但要查找的key是否真的存在, 需要在Btree的葉子節點(真實數據)上來確定。

• SlimTrie支持順序遍歷存在的key

索引很多情況下需要支持範圍查詢，SlimTrie 作為索引的數據結構，一定是支持順序遍歷的特點。SlimTrie 在結構上與樹形結構有相似點，順序遍歷的實現並不難。

• SlimTrie的內存開銷只與key的個數n相關，不依賴於key的長度k.

• SlimTrie支持最大16KB的key.

• SlimTrie查詢速度要快.

術語

• n: key的總數: 1 - 2^32
• k: key的平均長度 1 - 2^16
• k[i]: 某個key的長度 1 - 2^16
• userdata: 要索引的用戶數據, 這裡userdata是一組(offset, size)
• leaf: SlimTrie中的葉子節點, 每個leaf對應一個存在的key
• inner: SlimTrie中的非葉子節點

算法

SlimTrie的生成分為三部分。

• 先用一個Trie來做所有key的索引, 並在Trie的基礎上做裁剪, 將索引數據的量級從O(n * k)降低到O(n)。
• Trie的壓縮, 通過一個compacted array來存儲整個Trie的數據結構, 在實現上將內存開銷降低。
• 對小文件的優化, 將多個相鄰的小文件用1條索引來標識, 平衡IO開銷和內存開銷。

中間節點剪裁

將標準SlimTrie作為索引使用的時候, 不需要對每個branch都進行保存，因為我們只需要滿足設計目標1和目標2，因此在索引層只負責讓存在的key可以被定位到, 不存在的key在數據層反饋。 基於以上設計，可以意識到：多分支的SlimTrie節點是關鍵的，單分支的節點對定位一個存在的key沒有任何幫助。所以可以裁剪掉單分支節點。

葉子節點剪裁

上圖中abdfg中的g節點不需要保留, 因為合法key的前綴如果是abdf, 它最後1個字符只能是g，abdfg的g去掉, 同理，b123中的3去掉, 於是裁剪之後的結果:

壓縮數組

使用壓縮數組來保存SlimTrie的邏輯結構, 壓縮數組用來保存最大大小不超過65536 個條目的信息，首先定義壓縮數組的結構：

4bit word

將全量數據拆分成較小的組, 每個組內使用SlimTrie索引, 再通過id來替代指針(16bit id)，組間使用標準的SlimTrie索引，即對索引進行分層。 將1個8bit的byte拆分成2個4bit的word作為SlimTrie上節點的單位. 這樣可以有效減少bitmap在使用時額外的內存開銷。

時間空間效率分析

• 
  Caption1
• 
  Caption2

外部連結

• SlimTrie at github