前言

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

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

以 MySQL 為例

在 MySQL 中，我們往往會(huì)建立這樣一個(gè)表：

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

這里的 PRIMARY KEY 最終體現(xiàn)到 MyRocks，是這樣的形式：

通過配置，我們可以通過 keyPrefixLen 將 PrefixID 分離出去，這樣，Index 中就只剩下一個(gè) id 字段了，并且，在 SST 中，這些 id 往往都是比較緊密的范圍（被刪除的 id 是范圍中的空洞），比如，在某個(gè) SST 中，存儲(chǔ)的 id 范圍是 1,000,000~2,000,000。

并且，我們知道，CO-Index 會(huì)將用戶 Key(在這里就是 id 字段) 映射到一個(gè) 內(nèi)部ID，再用這個(gè) 內(nèi)部ID 去訪問 PA-Zip……

在一個(gè) SST 中，把這一切串起來，我們就能使用簡單且高效的方式來實(shí)現(xiàn) Index 了：

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

• 如果這個(gè)范圍中，一個(gè)空洞也沒有，那么，Index 中我們只需要保存 id 的最大最小值。
  • 內(nèi)部ID = Student.id - MinStudentID
• 如果這個(gè)范圍中，只有極少數(shù)的空洞，那么，Index 中我們只需要保存那些空洞 中的 id。
  • 內(nèi)部ID = Student.id - (Hole num before this Student.id)
• 如果這個(gè)范圍中，有相當(dāng)數(shù)量的空洞，那么，Index 中我們只需要保存一個(gè) BitMap，其中相應(yīng) bit 的含義是這個(gè) id 是否存在。
  • 利用 Rank-Select 的思想：內(nèi)部ID = BitMap.rank1(id)

進(jìn)一步，在概念上，如果我們把 一個(gè)空洞也沒有 和 只有極少數(shù)的空洞 也用 Rank-Select 來表達(dá)：

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

應(yīng)用到 MongoDB

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

MongoDB 有兩大類 Key Value 數(shù)據(jù)，RecordStore（即 Collection） 和 Index：

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

壓縮率 & 性能

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

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

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

最新評論