以mysql為例詳解ToplingDB 的 UintIndex

2022-08-19 14:03:56

前言

在 ToplingDB 的 CO-Index(Compressed Ordered Index) 家族中，Nest Succinct Trie 是最通用的。但是，伴隨通用的，往往是低效。我們針對一些特殊場景，採用了特殊的實現，用以提高效能……

這裡面，最特殊的一類 Index，就是 UintIndex，顧名思義，就是 Key 為 unsigned int 時的 index。

以 MySQL 為例

在 MySQL 中，我們往往會建立這樣一個表：

CREATE TABLE Student(
    id INT PRIMARY KEY AUTO_INCREMENT,
    name VARCHAR(255) INDEX,
    dorm_id INT INDEX,
    -- others ...
);

這裡的 PRIMARY KEY 最終體現到 MyRocks，是這樣的形式：

PrefixID

通過設定，我們可以通過 keyPrefixLen 將 PrefixID 分離出去，這樣，Index 中就只剩下一個 id 欄位了，並且，在 SST 中，這些 id 往往都是比較緊密的範圍（被刪除的 id 是範圍中的空洞），比如，在某個 SST 中，儲存的 id 範圍是 1,000,000~2,000,000。

並且，我們知道，CO-Index 會將使用者 Key(在這裡就是 id 欄位) 對映到一個 內部ID，再用這個 內部ID 去存取 PA-Zip……

在一個 SST 中，把這一切串起來，我們就能使用簡單且高效的方式來實現 Index 了：

圖中的 ValueOrd 就是前面說的 內部ID，Index 共有 108 個 Key，BitMap 中有 MaxKey - MinKey + 1 = 229 個 Bit。

如果這個範圍中，一個空洞也沒有，那麼，Index 中我們只需要儲存 id 的最大最小值。
- 內部ID = Student.id - MinStudentID
如果這個範圍中，只有極少數的空洞，那麼，Index 中我們只需要儲存那些空洞 中的 id。
- 內部ID = Student.id - (Hole num before this Student.id)
如果這個範圍中，有相當數量的空洞，那麼，Index 中我們只需要儲存一個 BitMap，其中相應 bit 的含義是這個 id 是否存在。
- 利用 Rank-Select 的思想：內部ID = BitMap.rank1(id)

進一步，在概念上，如果我們把一個空洞也沒有和只有極少數的空洞也用 Rank-Select 來表達：

那麼，這三種情況，在形式上就可以統一起來！實際上，在程式碼實現中，這三種不同的 Rank-Select 實現是作為模板類 UintIndex 的模板引數的，在保持抽象的同時，又不損失效能。

應用到 MongoDB

在 MongoDB 中，也存在類似 MySQL Student.id 這樣的東西：

MongoDB 有兩大類 Key Value 資料，RecordStore（即 Collection）和 Index：

這樣，MongoDB 的 RecordStore 也可以利用 UintIndex

壓縮率 & 效能

壓縮率自然不用說，UintIndexAllOne 的壓縮率接近於無窮大，壓縮率最差的 UintIndexBitMap，其壓縮率也在 30 倍以上！

效能，最關鍵的是效能，相比傳統的塊壓縮，Nest Succinct Trie 最大的效能劣勢在於順序掃描（從頭至尾順序掃描，定位到某個點然後接著順序掃描），因為對於 Nest Succinct Trie，即便是順序掃描，它的計算也很複雜，並且記憶體存取非常隨機。而對於 UintIndex，事情就簡單多了，比 Nest Succinct Trie 會快 100 倍以上，而其中佔比最大的效能開銷，實際上是函數呼叫本身！

到此這篇關於以mysql為例詳解ToplingDB 的 UintIndex的文章就介紹到這了,更多相關mysql UintIndex內容請搜尋it145.com以前的文章或繼續瀏覽下面的相關文章希望大家以後多多支援it145.com！

以mysql為例詳解ToplingDB 的 UintIndex

目錄

前言

以 MySQL 為例

應用到 MongoDB

壓縮率 & 效能

熱門文章