基于跳躍表編碼的NoSQL數(shù)據(jù)庫查詢研究

何欣峰 錢小軍

摘? 要：文章針對NoSQL數(shù)據(jù)庫中鍵值數(shù)據(jù)庫通過部分值進(jìn)行查詢效率極低的問題，提出了一種基于跳躍表編碼的NoSQL數(shù)據(jù)庫查詢操作的實(shí)現(xiàn)方法，并且實(shí)現(xiàn)了字段查詢的并與交操作。該文的算法適用范圍很廣，可以實(shí)現(xiàn)對不同數(shù)據(jù)類型的多種查詢與檢索，與此同時(shí)，文章設(shè)計(jì)的跳躍表其本身也是采用Key-Value鍵值對的方式進(jìn)行存儲的，滿足鍵值數(shù)據(jù)庫的定義。

關(guān)鍵詞：跳躍表編碼;NoSQL;數(shù)據(jù)庫查詢

中圖分類號：TP311? ? ? ?文獻(xiàn)標(biāo)識碼：A 文章編號：2096-4706（2021）05-0113-05

Research on NoSQL Database Query Based on Skip List Coding

HE Xinfeng，QIAN Xiaojun

（Jiangsu Golden Shield Detection Technology Co.，Ltd.，Nanjing? 210042，China）

Abstract：Aming at the problem that the query efficiency of key value database in NoSQL database is very low through partial values，this paper proposes a implementation method of NoSQL database query operation based on skip list coding，and realizes the union and intersection operation of field query. The algorithm proposed in this paper has a wide range of application，and can realize a variety of query and retrieval for different data types. At the same time，the skip list designed in this paper is also stored in the way of Key-Value key value pair，which meets the definition of key value database.

Keywords：skip list coding;NoSQL;database query

0? 引? 言

隨著社會的發(fā)展，人們產(chǎn)生的數(shù)據(jù)量也越來越多。有數(shù)據(jù)產(chǎn)生就必須要有個(gè)地方來存放。早期，人們通過紙質(zhì)書籍記錄存放數(shù)據(jù)，而隨著數(shù)據(jù)的不斷增多，這種方式越來越耗時(shí)間、耗人力，難以查詢與維護(hù)。因此，數(shù)據(jù)庫的產(chǎn)生和發(fā)展具有重大意義?；厥讛?shù)據(jù)庫的發(fā)展歷史，數(shù)據(jù)庫經(jīng)歷了將近半個(gè)世紀(jì)的發(fā)展。如圖1所示，從最開始的無庫時(shí)代到中期的層次數(shù)據(jù)庫、網(wǎng)狀數(shù)據(jù)庫和關(guān)系型數(shù)據(jù)庫，再到如今的NoSQL數(shù)據(jù)庫，每一個(gè)階段數(shù)據(jù)庫的產(chǎn)生都是創(chuàng)世紀(jì)的發(fā)明，尤其是關(guān)系型數(shù)據(jù)庫[1]。80年代以來，關(guān)系型數(shù)據(jù)庫已經(jīng)成為當(dāng)前最常見的一種數(shù)據(jù)庫類型[1]。

然而，隨著大數(shù)據(jù)和云計(jì)算的發(fā)展，半關(guān)系型數(shù)據(jù)和非關(guān)系型數(shù)據(jù)大量產(chǎn)生，已有的關(guān)系型數(shù)據(jù)庫越來越無法滿足需求[1-5]，因此，NoSQL數(shù)據(jù)庫應(yīng)運(yùn)而生。NoSQL數(shù)據(jù)庫泛指非關(guān)系型數(shù)據(jù)庫，與關(guān)系型數(shù)據(jù)庫有所不同。該種數(shù)據(jù)庫不保證數(shù)據(jù)的ACID特性，去掉了關(guān)系型數(shù)據(jù)庫存儲關(guān)系型數(shù)據(jù)的特點(diǎn)[2，3，6]。NoSQL具有高擴(kuò)展性、高性能、高容錯(cuò)性、高伸縮性等特性[2]。因此，在當(dāng)前由NoSQL數(shù)據(jù)庫主導(dǎo)的世界中，NoSQL數(shù)據(jù)庫解決方案變得越來越普遍[7]。NoSQL數(shù)據(jù)庫旨在為大量未結(jié)構(gòu)化的數(shù)據(jù)提供數(shù)據(jù)庫解決方案。目前，NoSQL主要分為四種類型，分別是鍵值數(shù)據(jù)庫、列式數(shù)據(jù)庫、文檔數(shù)據(jù)庫和圖形數(shù)據(jù)庫，如圖2所示[8]。其中，鍵值數(shù)據(jù)庫是NoSQL領(lǐng)域中應(yīng)用范圍最廣，涉及產(chǎn)品最多的一種模型[9]。本文可以將它理解為一個(gè)分布式的Hashmap。這個(gè)表中通過特定的鍵和指針指向特定的數(shù)據(jù)。鍵值數(shù)據(jù)庫的優(yōu)勢在于簡單且易于部署，例如Redis、LevelDB和Oracle BDB等[10]。在鍵值數(shù)據(jù)庫中，雖然能通過鍵很快地查詢到值，但是對部分值進(jìn)行查詢和更新時(shí)效率極低[11，12]。通常查詢部分值的方法是對庫中的Key值對進(jìn)行遍歷，逐個(gè)比較Value值，這樣實(shí)現(xiàn)的效率顯然是較低的。

本文針對NoSQL數(shù)據(jù)庫中鍵值數(shù)據(jù)庫通過部分值進(jìn)行查詢效率極低的問題，提出了一種基于跳躍表編碼的NoSQL數(shù)據(jù)庫查詢操作的實(shí)現(xiàn)方法。該方法不僅可以解決本文提出的問題而且可以實(shí)現(xiàn)字段查詢的并與交操作。

1? 相關(guān)工作

1.1? 跳躍表

在數(shù)據(jù)結(jié)構(gòu)中，若要在數(shù)表或鏈表中插入或查詢一個(gè)數(shù)據(jù)，都會存在性能問題即效率極低。在這種情況下，跳躍表出現(xiàn)了。跳躍表是一種基于有序鏈表的擴(kuò)展，簡稱“調(diào)表”。在跳躍表中，所有元素都是以有序方式在層次化的鏈表中保存的，其查找、刪除、添加等操作的效率比先前均有所提升[13-15]。

如圖3所示，當(dāng)要插入一個(gè)新的節(jié)點(diǎn)4時(shí)，若使用單一鏈表，則須與原節(jié)點(diǎn)8，7，6，5，3逐一進(jìn)行比較。

若使用如圖4所示的跳躍表，當(dāng)將所有奇數(shù)節(jié)點(diǎn)作為關(guān)鍵節(jié)點(diǎn)形成跳躍表時(shí)，只需比較關(guān)鍵節(jié)點(diǎn)7，5，3即可，6，8不用再進(jìn)行比較，節(jié)省了時(shí)間。

在確定了新節(jié)點(diǎn)4是在關(guān)鍵節(jié)點(diǎn)3和5之間后，本文就可以回到原鏈表迅速定位，然后插入值4。當(dāng)鏈表中的節(jié)點(diǎn)非常多，即達(dá)到十幾萬個(gè)節(jié)點(diǎn)時(shí)再進(jìn)行該操作，比較次數(shù)會減少一半，這是相當(dāng)可觀的，雖然與此同時(shí)增加了50%的額外空間，但是性能卻提高了將近一倍。當(dāng)節(jié)點(diǎn)足夠多時(shí)，可以不光提出一級的關(guān)鍵節(jié)點(diǎn)索引，還可以提出多層的關(guān)鍵節(jié)點(diǎn)索引，即從原鏈表節(jié)點(diǎn)中提取一部分到上一層。針對拔哪些節(jié)點(diǎn)，忽略哪些節(jié)點(diǎn)的問題，跳躍表設(shè)計(jì)者采用了隨機(jī)方式，即類似于拋硬幣的一種方式。本文可以認(rèn)為每一層節(jié)點(diǎn)向上提拔的概率為50%。圖3中原鏈表的多級索引構(gòu)建跳躍表如圖5所示。

跳躍表中一個(gè)最重要的方法就是拋硬幣的方式，因?yàn)樘S表對節(jié)點(diǎn)的刪除和添加都是不可預(yù)測的，所以無法用一個(gè)固定的算法來保證跳躍表的索引層始終均勻。而拋硬幣的方式可以讓索引部分相對保持均勻。跳躍表主要有查詢和刪除兩項(xiàng)操作。

對添加節(jié)點(diǎn)的操作來說，跳躍表主要有三個(gè)步驟：

（1）自下而上將新節(jié)點(diǎn)與各索引層節(jié)點(diǎn)逐一比較大小，以確定原鏈表的插入位置。

（2）把新節(jié)點(diǎn)插入到跳躍表。

（3）利用拋硬幣的方式，確定新節(jié)點(diǎn)是否為上一級索引，是則繼續(xù)拋硬幣，不是則停止拋硬幣。

如圖6所示，當(dāng)要插入一個(gè)新節(jié)點(diǎn)9時(shí)，將其與原鏈表層中各節(jié)點(diǎn)的大小作比較，確定插入節(jié)點(diǎn)的位置，然后以拋硬幣方式隨機(jī)判斷是否為上一級索引，如果是就重復(fù)拋硬幣，如果不是就停止拋硬幣。

對刪除節(jié)點(diǎn)操作來說，跳躍表主要有兩個(gè)步驟：

（1）自上而下查找第一次出現(xiàn)節(jié)點(diǎn)的索引，并逐層找到每一層對應(yīng)的節(jié)點(diǎn)。

（2）刪除每一層查找到的節(jié)點(diǎn)，如果恰巧刪除該節(jié)點(diǎn)后只有一個(gè)節(jié)點(diǎn)的話，則刪除整層。

如圖7所示，當(dāng)要刪除節(jié)點(diǎn)5時(shí)，則自上而下逐層找到該節(jié)點(diǎn)并刪除。

1.2? NoSQL數(shù)據(jù)庫

NoSQL數(shù)據(jù)庫不僅僅是SQL的意思，在當(dāng)今的計(jì)算機(jī)網(wǎng)絡(luò)上每天都會產(chǎn)生龐大的數(shù)據(jù)量。其中很大一部分都是存在著一定的關(guān)聯(lián)性，即存在一定的關(guān)系。這些存在關(guān)聯(lián)性的數(shù)據(jù)通常由數(shù)據(jù)庫管理系統(tǒng)進(jìn)行處理。然而實(shí)際上還有一部分?jǐn)?shù)據(jù)是沒有關(guān)聯(lián)性的，這些數(shù)據(jù)就不能用關(guān)系數(shù)據(jù)庫來管理了，因此NoSQL數(shù)據(jù)庫應(yīng)運(yùn)而生。它不僅可以管理處理關(guān)聯(lián)性數(shù)據(jù)，而且還可以管理處理無關(guān)聯(lián)性數(shù)據(jù)。NoSQL數(shù)據(jù)庫與關(guān)系數(shù)據(jù)庫的對比結(jié)果如表1所示。

常見的NoSQL數(shù)據(jù)庫有HBase、Redis、MongoDB、Couchbase、LevelDB等。HBase的數(shù)據(jù)存儲是基于列的，存儲得非常松散，比如Hbase允許某行某列值為空時(shí)不做任何存儲，減少了空間占用，提高了讀性能。Hbase存儲容量很大，但是其基于Java語言實(shí)現(xiàn)，因此API更適合Java項(xiàng)目。Redis的數(shù)據(jù)存儲是依賴于鍵值的，操作十分方便且簡單。Redis擁有非常豐富的數(shù)據(jù)結(jié)構(gòu)，數(shù)據(jù)存于內(nèi)存之中，讀寫很快，但是由于其是內(nèi)存數(shù)據(jù)庫，所以內(nèi)存增長過快，需要定期刪除數(shù)據(jù)。MongoDB是一個(gè)高性能、開源、無模式的文檔型數(shù)據(jù)庫，是鍵值存儲方式。MongoDB支持全索引，查詢非常高效，但是對內(nèi)存要求比較高，且無法保證事件的原子性。Couchbase是面向文檔的數(shù)據(jù)庫。Couchbase具有高并發(fā)性、高靈活性、高拓展性、高容錯(cuò)性，但是存儲方式為key/value，value的類型單一，不支持?jǐn)?shù)組。LevelDB不屬于分布式數(shù)據(jù)庫。LevelDB操作接口簡單，數(shù)據(jù)量增大后，讀寫性能不斷下降直至趨于平緩，但是隨機(jī)讀取性能一般，且對分布式事務(wù)的支持不夠成熟。

2? 模型

本文實(shí)現(xiàn)的模型如圖8所示，其中，最上層為跳躍表，跳躍表最底層中各個(gè)節(jié)點(diǎn)的值就是存儲Key-Value值的Value值，跳躍表最底層中每個(gè)節(jié)點(diǎn)都指向一個(gè)鏈表，該鏈表是由Value值與跟跳躍表底層節(jié)點(diǎn)Value一樣的Key-Value值對組成的單向鏈表。

本文模型算法具體解釋為：

（1）跳躍表中各節(jié)點(diǎn)的結(jié)構(gòu)滿足兩種關(guān)系，跳躍表本身也是存儲在Key-Value鍵對值的數(shù)據(jù)庫中，因此每個(gè)節(jié)點(diǎn)都是采用;其中通過Value來組織構(gòu)建上述表格：

1）的結(jié)構(gòu)是，其中Value是跳躍表節(jié)點(diǎn)的值，跳躍表中的數(shù)據(jù)是各個(gè)索引節(jié)點(diǎn)的值。

2）對于跳躍表底層指向的鏈表中節(jié)點(diǎn)，Value是數(shù)據(jù)庫中有效數(shù)據(jù)的Key，LeftNodeKey為空，DownNodeKey指向同一個(gè)Value值的下一個(gè)Key-Value鍵值對。

（2）Key-Value鍵值跳躍表的構(gòu)建算法為：

1）按數(shù)據(jù)的Value值進(jìn)行排序。如果是數(shù)據(jù)類型，則按數(shù)值大小排序;如果是字符類型，則按字符串大小排序。

2）根據(jù)跳躍表預(yù)置的層次，劃分出Value值區(qū)間的大小，然后自下而上構(gòu)建出上層的跳躍表。

3）再根據(jù)跳躍表最底層的節(jié)點(diǎn)Value值，按庫中各字段Value值的大小，屬于同一區(qū)段的Key-Value鍵值對掛在對應(yīng)的跳躍表節(jié)點(diǎn)上。

（3）查詢的算法實(shí)現(xiàn)為：

1）從跳躍表的根節(jié)點(diǎn)出發(fā)定位到跳躍表的最底層節(jié)點(diǎn)。

2）然后再從最底層節(jié)點(diǎn)出發(fā)，遍歷最底層節(jié)點(diǎn)指向的Key-Value鍵值對鏈表。

3）根據(jù)待查詢的值，逐個(gè)查詢鏈表中Key-Value鍵值對的Value值，并返回最終的查詢結(jié)果。

偽代碼表示為：

Begin

輸入 value//value為待查詢的值大小

For i = 0 To n-1 Step 1? //n為劃分出的Value值區(qū)間個(gè)數(shù)加1即跳躍表最后一層節(jié)點(diǎn)個(gè)數(shù)

If i = 0 and value<= SkipListNode[i+1].value //SkipListNode為跳躍表最后一層節(jié)點(diǎn)

then For j = 0 To SkipListNodeSum Step 1? // SkipListNodeSum為跳躍表最后一層節(jié)點(diǎn)掛載下單鏈長度

If value=Node[Link[j].value].value? //Node為鍵值數(shù)據(jù)庫數(shù)據(jù)對，Link為跳躍表最后一層節(jié)點(diǎn)掛載下單鏈

then 輸出Node[Link[j].value]

If i ≠ 0 and value> SkipListNode[i].value and value<= SkipListNode[i+1].value

then For j = 0 To SkipListNodeSum Step 1

If value=Node[Link[j].value].value

then 輸出Node[Link[j].value]

End

（4）查詢結(jié)果的并操作算法實(shí)現(xiàn)為：

1）并操作是指同時(shí)查詢兩個(gè)或多個(gè)值，最終將查詢的結(jié)果集并后返回。

2）算法實(shí)現(xiàn)是構(gòu)建多個(gè)線程，每個(gè)線程對應(yīng)一個(gè)值的查詢操作。

3）將各線程的操作結(jié)果集結(jié)合，同時(shí)去除重復(fù)的節(jié)點(diǎn)，然后返回。

（5）查詢結(jié)果的交操作算法實(shí)現(xiàn)為：

1）交操作是指同時(shí)查詢兩個(gè)或多個(gè)值，最終將查詢的結(jié)果集進(jìn)行相交后返回。

2）操作過程與并相似，只是后面的操作是判斷節(jié)點(diǎn)是否同時(shí)在二個(gè)集合中。

3? 實(shí)驗(yàn)

本文分析了跳躍表和NoSQL數(shù)據(jù)庫原理，試圖通過將跳躍表與NoSQL數(shù)據(jù)庫存儲方式Key-Value相結(jié)合，解決NoSQL數(shù)據(jù)庫中查詢數(shù)據(jù)速度較慢的問題。本文基于文本分詞分成的詞文本材料，材料共包括中文分詞6 493個(gè)，分別基于原始非排序KEY-VALUE，以及本文的跳躍表方式構(gòu)建的索引，進(jìn)行對比實(shí)驗(yàn)。

實(shí)驗(yàn)結(jié)果表明，本文提出的方法在查詢速度上快于原始NoSQL數(shù)據(jù)庫Key-Value方法，如表2所示。

通過上述實(shí)驗(yàn)結(jié)果可知，本文提出的方法可在一定程度上提高查詢速度。因此，將該方法應(yīng)用于NoSQL數(shù)據(jù)庫可在一定程度上提升SQL語言查詢速度。雖然該方法增加了存儲內(nèi)存，但卻在一定程度上提高了查詢速度，與此同時(shí)本文采用的跳躍表也是以Key-Value鍵值對方式進(jìn)行存儲的，符合NoSQL數(shù)據(jù)庫的特性。

4? 結(jié)? 論

本文針對現(xiàn)有NoSQL數(shù)據(jù)庫中鍵值數(shù)據(jù)庫查詢速度較慢、效率極低的問題，提出了一種基于跳躍表編碼的NoSQL數(shù)據(jù)庫查詢操作的實(shí)現(xiàn)方法。該方法適用范圍極其廣泛，可以實(shí)現(xiàn)對不同數(shù)據(jù)類型的多種查詢與檢索。與此同時(shí)，該方法本身使用的跳躍表也是采用Key-Value鍵值對的方式進(jìn)行存儲的。

參考文獻(xiàn)：

[1] 郎云海.NoSQL數(shù)據(jù)庫與關(guān)系型數(shù)據(jù)庫對比 [J].低碳世界，2019，9（5）：323-324.

[2] 葉文.NoSQL數(shù)據(jù)庫與緩存一致性研究 [J].信息與電腦（理論版），2018（21）：143-144.

[3] 陳果.大數(shù)據(jù)時(shí)代基于NoSQL數(shù)據(jù)庫查詢技術(shù)的應(yīng)用 [J].辦公自動化，2021，26（5）：59-60+46.

[4] 趙永強(qiáng).基于NoSQL的特色數(shù)據(jù)庫系統(tǒng)研究 [J].圖書館工作與研究，2018（S1）：97-99+124.

[5] 張華兵，林志達(dá)，張今革.基于NoSQL數(shù)據(jù)庫的模型設(shè)計(jì)方法 [J].電子技術(shù)與軟件工程，2019（23）：174-175.

[6] 楊嵐.大數(shù)據(jù)環(huán)境下NoSQL數(shù)據(jù)庫查詢技術(shù)應(yīng)用研究 [J].湖北第二師范學(xué)院學(xué)報(bào)，2020，37（8）：36-41.

[7] BROOKS A. Comparing NoSQL MongoDB to an SQL DB [J].Computing reviews，2014，55（10）：628-628.

[8] 薛濤.基于NoSQL數(shù)據(jù)庫的大數(shù)據(jù)查詢技術(shù)實(shí)踐探索 [J].電腦編程技巧與維護(hù)，2018（11）：89-90+131.

[9] 馬文龍，朱妤晴，蔣德鈞，等.Key-Value型NoSQL本地存儲系統(tǒng)研究 [J].計(jì)算機(jī)學(xué)報(bào)，2018，41（8）：1722-1751.

[10] 陳忠菊.NoSQL數(shù)據(jù)庫的研究和應(yīng)用 [J].電腦編程技巧與維護(hù)，2020（9）：81-83.

[11] KLEIN J，GORTON I，ERNST N，et al. Performance Evaluation of NoSQL Databases： A Case Study [C]//PABS15：Proceedings of the 1st Workshop on Performance Analysis of Big Data Systems.Austin：Association for Computing Machinery，2015：5-10.

[12] 尹妍，朱立偉.淺談NoSQL數(shù)據(jù)庫的數(shù)據(jù)存儲 [J].科學(xué)與信息化，2019（6）：61，64.

[13] PUGH W. Skip lists：A probabilistic alternative to balanced trees [J].Communications of the ACMVolume，1990，33（6）：668–676.

[14] 葉楓.Key-Value Store讀寫性能研究與優(yōu)化 [D].徐州：中國礦業(yè)大學(xué)，2016.

[15] 陳慶全，黃文明，崔亞楠.基于改進(jìn)跳躍表的數(shù)據(jù)檢索系統(tǒng)應(yīng)用 [J].計(jì)算機(jī)系統(tǒng)應(yīng)用，2008（12）：73-76.

作者簡介：何欣峰（1974—），男，漢族，江蘇南京人，中級工程師，高級測評師，CISP，CIIPT，本科，研究方向：網(wǎng)絡(luò)應(yīng)用與安全。