以mysql為例詳解ToplingDB?的?UintIndex

更新時間：2022年08月19日 10:13:14 作者：雷鵬

本文主要介紹了以mysql為例詳解ToplingDB的UintIndex，在ToplingDB的CO-Index(Compressed?Ordered?Index)家族中，Nest?Succinct?Trie是最通用的，更多相關內容需要的朋友可以參考一下

前言

在 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

id

通過配置，我們可以通過 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 來表達：

那么，這三種情況，在形式上就可以統(tǒng)一起來！實際上，在代碼實現中，這三種不同的 Rank-Select 實現是作為模板類 UintIndex 的模板參數的，在保持抽象的同時，又不損失性能。

應用到 MongoDB

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

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

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

壓縮率 & 性能

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

性能，最關鍵的是性能，相比傳統(tǒng)的塊壓縮，Nest Succinct Trie 最大的性能劣勢在于順序掃描（從頭至尾順序掃描，定位到某個點然后接著順序掃描），因為對于 Nest Succinct Trie，即便是順序掃描，它的計算也很復雜，并且內存訪問非常隨機。而對于 UintIndex，事情就簡單多了，比 Nest Succinct Trie 會快 100 倍以上，而其中占比最大的性能開銷，實際上是函數調用本身！

到此這篇關于以mysql為例詳解ToplingDB 的 UintIndex的文章就介紹到這了,更多相關mysql UintIndex內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: