以mysql為例詳解ToplingDB?的?UintIndex
前言
在 ToplingDB 的 CO-Index(Compressed Ordered Index) 家族中,Nest Succinct Trie 是最通用的。但是,伴隨通用的,往往是低效。我們針對一些特殊場景,采用了特殊的實現(xiàn),用以提高性能……
這里面,最特殊的一類 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
最終體現(xiàn)到 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 中,把這一切串起來,我們就能使用簡單且高效的方式來實現(xiàn) Index 了:
圖中的 ValueOrd
就是前面說的 內部ID
,Index 共有 108 個 Key,BitMap 中有 MaxKey - MinKey + 1 = 229
個 Bit。
- 如果這個范圍中,一個
空洞
也沒有,那么,Index 中我們只需要保存id
的最大最小值。- 內部ID = Student.id - MinStudentID
- 如果這個范圍中,只有極少數(shù)的
空洞
,那么,Index 中我們只需要保存那些空洞
中的id
。- 內部ID = Student.id - (Hole num before this Student.id)
- 如果這個范圍中,有相當數(shù)量的
空洞
,那么,Index 中我們只需要保存一個 BitMap,其中相應 bit 的含義是這個 id 是否存在
。- 利用 Rank-Select 的思想:內部ID = BitMap.rank1(id)
進一步,在概念上,如果我們把 一個空洞也沒有 和 只有極少數(shù)的空洞 也用 Rank-Select 來表達:
那么,這三種情況,在形式上就可以統(tǒng)一起來!實際上,在代碼實現(xiàn)中,這三種不同的 Rank-Select 實現(xiàn)是作為模板類 UintIndex 的模板參數(shù)的,在保持抽象的同時,又不損失性能。
應用到 MongoDB
在 MongoDB 中,也存在類似 MySQL Student.id 這樣的東西:
MongoDB 有兩大類 Key Value 數(shù)據(jù),RecordStore(即 Collection) 和 Index:
這樣,MongoDB 的 RecordStore 也可以利用 UintIndex
壓縮率 & 性能
壓縮率自然不用說,UintIndexAllOne 的壓縮率接近于無窮大,壓縮率最差的 UintIndexBitMap,其壓縮率也在 30 倍以上!
性能,最關鍵的是性能,相比傳統(tǒng)的塊壓縮,Nest Succinct Trie 最大的性能劣勢在于順序掃描(從頭至尾順序掃描,定位到某個點然后接著順序掃描),因為對于 Nest Succinct Trie,即便是順序掃描,它的計算也很復雜,并且內存訪問非常隨機。而對于 UintIndex,事情就簡單多了,比 Nest Succinct Trie 會快 100 倍以上,而其中占比最大的性能開銷,實際上是函數(shù)調用本身!
到此這篇關于以mysql為例詳解ToplingDB 的 UintIndex的文章就介紹到這了,更多相關mysql UintIndex內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家!
相關文章
Centos7使用yum安裝MySQL及實現(xiàn)遠程連接的方法
因為MySQL被Oracle收購,目前推薦使用mariadb數(shù)據(jù)庫。下面通過本文給大家分享Centos7使用yum安裝MySQL及實現(xiàn)遠程連接的方法,感興趣的朋友一起看看吧2017-07-07mysql如何分別按年/月/日/周分組統(tǒng)計數(shù)據(jù)詳解
我們在用Mysql抽取數(shù)據(jù)時候,經(jīng)常需要按照天、周、月等不同的粒度對數(shù)據(jù)進行分組統(tǒng)計,下面這篇文章主要給大家介紹了關于mysql如何分別按年/月/日/周分組統(tǒng)計數(shù)據(jù)的相關資料,需要的朋友可以參考下2022-12-12window10中mysql8.0修改端口port不生效的解決方法
mysql配置文件默認位置,端口號等信息需要在my.ini文件中修改,若修改安裝位置的my-default文件文件或新建my.ini文件是不生效的,本文主要介紹了window10中mysql8.0修改端口port不生效的解決方法,感興趣的可以了解一下2023-11-11Mysql聯(lián)合查詢UNION和Order by同時使用報錯問題的解決辦法
很多朋友剛使用聯(lián)合查詢UNION的時候常常會理所當然的將聯(lián)合查詢理解為把沒一個子查詢的結果集組合成一個大的結果集2014-04-04