[發(fā)明專利]一種基于鍵排序的數(shù)據(jù)存儲方法和裝置

有效

• 申請?zhí)枺?/td>: 201210541207.0
• 申請日: 2012-12-14
• 公開（公告）號: CN103870492B
• 公開（公告）日: 2017-08-04
• 發(fā)明（設(shè)計(jì)）人: 陳崢;鄧大付
• 申請（專利權(quán)）人: 騰訊科技（深圳）有限公司
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 北京德琦知識產(chǎn)權(quán)代理有限公司11018
• 代理人: 張馳,宋志強(qiáng)

技術(shù)領(lǐng)域

本發(fā)明實(shí)施方式涉及信息處理技術(shù)領(lǐng)域，更具體地，涉及一種基于鍵（Key）排序的數(shù)據(jù)存儲方法和裝置。

背景技術(shù)

在當(dāng)今的信息時(shí)代中，各種信息設(shè)備應(yīng)運(yùn)而生：有用于話音傳輸?shù)墓潭娫挕⒁苿与娫挘挥杏糜谛畔①Y源共享、處理的服務(wù)器和個(gè)人電腦；有用于視頻數(shù)據(jù)顯示的各種電視機(jī)等等。這些設(shè)備都是在特定領(lǐng)域內(nèi)為解決實(shí)際的需求而產(chǎn)生的。隨著電子消費(fèi)、計(jì)算機(jī)、通信（3C）融合的到來，人們越來越多地將注意力放到了對各個(gè)不同領(lǐng)域的信息設(shè)備進(jìn)行綜合利用的研究上，以充分利用現(xiàn)有資源設(shè)備來為人們更好的服務(wù)。

Key-value分布式存儲系統(tǒng)具有查詢速度快、存放數(shù)據(jù)量大、支持高并發(fā)等優(yōu)點(diǎn)，非常適合通過主鍵進(jìn)行查詢，但不能進(jìn)行復(fù)雜的條件查詢。如果輔以Real-Time Search Engine（實(shí)時(shí)搜索引擎）進(jìn)行復(fù)雜條件檢索、全文檢索，就可以替代并發(fā)性能較低的MySQL等關(guān)系型數(shù)據(jù)庫，達(dá)到高并發(fā)、高性能，節(jié)省幾十倍服務(wù)器數(shù)量的目的。以MemcacheDB、Tokyo Tyrant為代表的Key-value分布式存儲，在上萬并發(fā)連接下，輕松地完成高速查詢。

在目前有序Key的存儲技術(shù)中，現(xiàn)有技術(shù)方案是以單個(gè)Key為存儲單位，很難選取一個(gè)基準(zhǔn)Key進(jìn)行前綴壓縮，導(dǎo)致壓縮效率低，而且存儲空間的利用率很低。

而且，在現(xiàn)有技術(shù)的數(shù)據(jù)壓縮技術(shù)中，當(dāng)需要讀取數(shù)據(jù)時(shí)，需要遍歷整個(gè)文件，解析力度大，而且定位查詢速度慢。

發(fā)明內(nèi)容

本發(fā)明實(shí)施方式提出一種鍵排序的數(shù)據(jù)存儲方法，從而提高存儲空間的利用率。

本發(fā)明實(shí)施方式還提出一種鍵排序的數(shù)據(jù)存儲裝置，從而提高存儲空間的利用率，從而提高提醒事務(wù)的處理效率。

本發(fā)明實(shí)施方式的具體方案如下：

一種基于鍵排序的數(shù)據(jù)存儲方法，該方法包括：

在第一數(shù)據(jù)塊中存儲定長鍵及其值，其中所述存儲定長鍵包括：統(tǒng)一存儲各個(gè)定長鍵的公共前綴，并分別存儲各個(gè)定長鍵去除公共前綴后的剩余部分；

在第二數(shù)據(jù)塊存儲變長鍵及其值，其中所述存儲變長鍵包括：全量存儲基準(zhǔn)鍵類型的變長鍵，而對前綴壓縮鍵類型的變長鍵執(zhí)行前綴壓縮。

一種基于鍵排序的數(shù)據(jù)存儲裝置，該裝置包括定長鍵存儲單元和變長鍵存儲單元，其中：

定長鍵存儲單元，用于在在第一數(shù)據(jù)塊中存儲定長鍵及其值，其中所述存儲定長鍵包括：統(tǒng)一存儲各個(gè)定長鍵的公共前綴，并分別存儲各個(gè)定長鍵去除公共前綴后的剩余部分；

變長鍵存儲單元，用于在第二數(shù)據(jù)塊存儲變長鍵及其值，其中所述存儲變長鍵包括：全量存儲基準(zhǔn)鍵類型的變長鍵，而對前綴壓縮鍵類型的變長鍵執(zhí)行前綴壓縮。

從上述技術(shù)方案可以看出，在本發(fā)明實(shí)施方式中，在第一數(shù)據(jù)塊中存儲定長鍵及其值，其中所述存儲定長鍵包括：統(tǒng)一存儲各個(gè)定長鍵的公共前綴，并分別存儲各個(gè)定長鍵去除公共前綴后的剩余部分；在第二數(shù)據(jù)塊存儲變長鍵及其值，其中所述存儲變長鍵包括：全量存儲基準(zhǔn)鍵類型的變長鍵，而對前綴壓縮鍵類型的變長鍵執(zhí)行前綴壓縮。由此可見，應(yīng)用本發(fā)明實(shí)施方式之后，變長鍵數(shù)據(jù)塊內(nèi)采用前綴壓縮方式，以及優(yōu)選對每個(gè)數(shù)據(jù)塊進(jìn)行壓縮，因此可以有效減小數(shù)據(jù)的存儲空間，提高機(jī)器磁盤利用率。

另外，不同于現(xiàn)有技術(shù)中以單個(gè)Key為存儲單位，本發(fā)明實(shí)施方式以數(shù)據(jù)塊為存儲單元，因此可以有利于IO和解析的力度。

而且，本發(fā)明實(shí)施方式在讀取數(shù)據(jù)時(shí)，可以依據(jù)索引塊以及數(shù)據(jù)塊內(nèi)部的有序性，快速定位查詢的數(shù)據(jù)，從而提高查詢效率。

附圖說明

圖1為根據(jù)本發(fā)明實(shí)施方式的鍵排序的數(shù)據(jù)存儲方法流程圖；

圖2為根據(jù)本發(fā)明實(shí)施方式的文件格式示意圖；

圖3為根據(jù)本發(fā)明實(shí)施方式的數(shù)據(jù)塊的變長Key的寫入示意圖；

圖4為根據(jù)本發(fā)明實(shí)施方式的數(shù)據(jù)塊的定長Key的寫入示意圖；

圖5為根據(jù)本發(fā)明實(shí)施方式的布隆過濾器的存儲結(jié)構(gòu)示意圖；

圖6為根據(jù)本發(fā)明實(shí)施方式的索引塊（Block Index）的存儲結(jié)構(gòu)示意圖；

圖7為根據(jù)本發(fā)明實(shí)施方式的文件頭（Header）的存儲結(jié)構(gòu)示意圖；

圖8為根據(jù)本發(fā)明實(shí)施方式的記錄（record）數(shù)據(jù)寫入流程示意圖；

圖9為根據(jù)本發(fā)明實(shí)施方式的讀取順序示意圖；

圖10為根據(jù)本發(fā)明實(shí)施方式的記錄（record）數(shù)據(jù)讀取流程示意圖；

圖11為根據(jù)本發(fā)明實(shí)施方式的鍵排序的數(shù)據(jù)存儲裝置結(jié)構(gòu)圖。

具體實(shí)施方式

為使本發(fā)明的目的、技術(shù)方案和優(yōu)點(diǎn)更加清楚，下面結(jié)合附圖對本發(fā)明作進(jìn)一步的詳細(xì)描述。