使用者: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
參考資料
編輯外部連結
編輯
|