基于跳跃表编码的NoSQL数据库查询研究

何欣峰 钱小军

摘  要：文章针对NoSQL数据库中键值数据库通过部分值进行查询效率极低的问题，提出了一种基于跳跃表编码的NoSQL数据库查询操作的实现方法，并且实现了字段查询的并与交操作。该文的算法适用范围很广，可以实现对不同数据类型的多种查询与检索，与此同时，文章设计的跳跃表其本身也是采用Key-Value键值对的方式进行存储的，满足键值数据库的定义。

关键词：跳跃表编码;NoSQL;数据库查询

中图分类号：TP311       文献标识码：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  引  言

随着社会的发展，人们产生的数据量也越来越多。有数据产生就必须要有个地方来存放。早期，人们通过纸质书籍记录存放数据，而随着数据的不断增多，这种方式越来越耗时间、耗人力，难以查询与维护。因此，数据库的产生和发展具有重大意义。回首数据库的发展历史，数据库经历了将近半个世纪的发展。如图1所示，从最开始的无库时代到中期的层次数据库、网状数据库和关系型数据库，再到如今的NoSQL数据库，每一个阶段数据库的产生都是创世纪的发明，尤其是关系型数据库[1]。80年代以来，关系型数据库已经成为当前最常见的一种数据库类型[1]。

然而，随着大数据和云计算的发展，半关系型数据和非关系型数据大量产生，已有的关系型数据库越来越无法满足需求[1-5]，因此，NoSQL数据库应运而生。NoSQL数据库泛指非关系型数据库，与关系型数据库有所不同。该种数据库不保证数据的ACID特性，去掉了关系型数据库存储关系型数据的特点[2，3，6]。NoSQL具有高扩展性、高性能、高容错性、高伸缩性等特性[2]。因此，在当前由NoSQL数据库主导的世界中，NoSQL数据库解决方案变得越来越普遍[7]。NoSQL数据库旨在为大量未结构化的数据提供数据库解决方案。目前，NoSQL主要分为四种类型，分别是键值数据库、列式数据库、文档数据库和图形数据库，如图2所示[8]。其中，键值数据库是NoSQL领域中应用范围最广，涉及产品最多的一种模型[9]。本文可以将它理解为一个分布式的Hashmap。这个表中通过特定的键和指针指向特定的数据。键值数据库的优势在于简单且易于部署，例如Redis、LevelDB和Oracle BDB等[10]。在鍵值数据库中，虽然能通过键很快地查询到值，但是对部分值进行查询和更新时效率极低[11，12]。通常查询部分值的方法是对库中的Key值对进行遍历，逐个比较Value值，这样实现的效率显然是较低的。

本文针对NoSQL数据库中键值数据库通过部分值进行查询效率极低的问题，提出了一种基于跳跃表编码的NoSQL数据库查询操作的实现方法。该方法不仅可以解决本文提出的问题而且可以实现字段查询的并与交操作。

1  相关工作

1.1  跳跃表

在数据结构中，若要在数表或链表中插入或查询一个数据，都会存在性能问题即效率极低。在这种情况下，跳跃表出现了。跳跃表是一种基于有序链表的扩展，简称“调表”。在跳跃表中，所有元素都是以有序方式在层次化的链表中保存的，其查找、删除、添加等操作的效率比先前均有所提升[13-15]。

如图3所示，当要插入一个新的节点4时，若使用单一链表，则须与原节点8，7，6，5，3逐一进行比较。

若使用如图4所示的跳跃表，当将所有奇数节点作为关键节点形成跳跃表时，只需比较关键节点7，5，3即可，6，8不用再进行比较，节省了时间。

在确定了新节点4是在关键节点3和5之间后，本文就可以回到原链表迅速定位，然后插入值4。当链表中的节点非常多，即达到十几万个节点时再进行该操作，比较次数会减少一半，这是相当可观的，虽然与此同时增加了50%的额外空间，但是性能却提高了将近一倍。当节点足够多时，可以不光提出一级的关键节点索引，还可以提出多层的关键节点索引，即从原链表节点中提取一部分到上一层。针对拔哪些节点，忽略哪些节点的问题，跳跃表设计者采用了随机方式，即类似于抛硬币的一种方式。本文可以认为每一层节点向上提拔的概率为50%。图3中原链表的多级索引构建跳跃表如图5所示。

跳跃表中一个最重要的方法就是抛硬币的方式，因为跳跃表对节点的删除和添加都是不可预测的，所以无法用一个固定的算法来保证跳跃表的索引层始终均匀。而抛硬币的方式可以让索引部分相对保持均匀。跳跃表主要有查询和删除两项操作。

对添加节点的操作来說，跳跃表主要有三个步骤：

（1）自下而上将新节点与各索引层节点逐一比较大小，以确定原链表的插入位置。

（2）把新节点插入到跳跃表。

（3）利用抛硬币的方式，确定新节点是否为上一级索引，是则继续抛硬币，不是则停止抛硬币。

如图6所示，当要插入一个新节点9时，将其与原链表层中各节点的大小作比较，确定插入节点的位置，然后以抛硬币方式随机判断是否为上一级索引，如果是就重复抛硬币，如果不是就停止抛硬币。

对删除节点操作来说，跳跃表主要有两个步骤：

（1）自上而下查找第一次出现节点的索引，并逐层找到每一层对应的节点。

（2）删除每一层查找到的节点，如果恰巧删除该节点后只有一个节点的话，则删除整层。

如图7所示，当要删除节点5时，则自上而下逐层找到该节点并删除。

1.2  NoSQL数据库

NoSQL数据库不仅仅是SQL的意思，在当今的计算机网络上每天都会产生庞大的数据量。其中很大一部分都是存在着一定的关联性，即存在一定的关系。这些存在关联性的数据通常由数据库管理系统进行处理。然而实际上还有一部分数据是没有关联性的，这些数据就不能用关系数据库来管理了，因此NoSQL数据库应运而生。它不仅可以管理处理关联性数据，而且还可以管理处理无关联性数据。NoSQL数据库与关系数据库的对比结果如表1所示。

常见的NoSQL数据库有HBase、Redis、MongoDB、Couchbase、LevelDB等。HBase的数据存储是基于列的，存储得非常松散，比如Hbase允许某行某列值为空时不做任何存储，减少了空间占用，提高了读性能。Hbase存储容量很大，但是其基于Java语言实现，因此API更适合Java项目。Redis的数据存储是依赖于键值的，操作十分方便且简单。Redis拥有非常丰富的数据结构，数据存于内存之中，读写很快，但是由于其是内存数据库，所以内存增长过快，需要定期删除数据。MongoDB是一个高性能、开源、无模式的文档型数据库，是键值存储方式。MongoDB支持全索引，查询非常高效，但是对内存要求比较高，且无法保证事件的原子性。Couchbase是面向文档的数据库。Couchbase具有高并发性、高灵活性、高拓展性、高容错性，但是存储方式为key/value，value的类型单一，不支持数组。LevelDB不属于分布式数据库。LevelDB操作接口简单，数据量增大后，读写性能不断下降直至趋于平缓，但是随机读取性能一般，且对分布式事务的支持不够成熟。

2  模型

本文实现的模型如图8所示，其中，最上层为跳跃表，跳跃表最底层中各个节点的值就是存储Key-Value值的Value值，跳跃表最底层中每个节点都指向一个链表，该链表是由Value值与跟跳跃表底层节点Value一样的Key-Value值对组成的单向链表。

本文模型算法具体解释为：

（1）跳跃表中各节点的结构满足两种关系，跳跃表本身也是存储在Key-Value键对值的数据库中，因此每个节点都是采用;其中通过Value来组织构建上述表格：

1）的结构是，其中Value是跳跃表节点的值，跳跃表中的数据是各个索引节点的值。

2）对于跳跃表底层指向的链表中节点，Value是数据库中有效数据的Key，LeftNodeKey为空，DownNodeKey指向同一个Value值的下一个Key-Value键值对。

（2）Key-Value键值跳跃表的构建算法为：

1）按数据的Value值进行排序。如果是数据类型，则按数值大小排序;如果是字符类型，则按字符串大小排序。

2）根据跳跃表预置的层次，划分出Value值区间的大小，然后自下而上构建出上层的跳跃表。

3）再根据跳跃表最底层的节点Value值，按库中各字段Value值的大小，属于同一区段的Key-Value键值对挂在对应的跳跃表节点上。

（3）查询的算法实现为：

1）从跳跃表的根节点出发定位到跳跃表的最底层节点。

2）然后再从最底层节点出发，遍历最底层节点指向的Key-Value键值对链表。

3）根据待查询的值，逐个查询链表中Key-Value键值对的Value值，并返回最终的查询结果。

伪代码表示为：

Begin

输入 value//value为待查询的值大小

For i = 0 To n-1 Step 1  //n为划分出的Value值区间个数加1即跳跃表最后一层节点个数

If i = 0 and value<= SkipListNode[i+1].value //SkipListNode为跳跃表最后一层节点

then For j = 0 To SkipListNodeSum Step 1  // SkipListNodeSum为跳跃表最后一层节点挂载下单链长度

If value=Node[Link[j].value].value  //Node为键值数据库数据对，Link为跳跃表最后一层节点挂载下单链

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）查询结果的并操作算法实现为：

1）并操作是指同时查询两个或多个值，最终将查询的结果集并后返回。

2）算法实现是构建多个线程，每个线程对应一个值的查询操作。

3）将各线程的操作结果集结合，同时去除重复的节点，然后返回。

（5）查询结果的交操作算法实现为：

1）交操作是指同时查询两个或多个值，最终将查询的结果集进行相交后返回。

2）操作过程与并相似，只是后面的操作是判断节点是否同时在二个集合中。

3  实验

本文分析了跳跃表和NoSQL数据库原理，试图通过将跳跃表与NoSQL数据库存储方式Key-Value相结合，解决NoSQL数据库中查询数据速度较慢的问题。本文基于文本分词分成的词文本材料，材料共包括中文分词6 493个，分别基于原始非排序KEY-VALUE，以及本文的跳跃表方式构建的索引，进行对比实验。

实验结果表明，本文提出的方法在查询速度上快于原始NoSQL数据库Key-Value方法，如表2所示。

通过上述实验结果可知，本文提出的方法可在一定程度上提高查询速度。因此，将该方法应用于NoSQL数据库可在一定程度上提升SQL语言查询速度。虽然该方法增加了存储内存，但却在一定程度上提高了查询速度，与此同时本文采用的跳跃表也是以Key-Value键值对方式进行存储的，符合NoSQL数据库的特性。

4  结  论

本文针对现有NoSQL数据库中键值数据库查询速度较慢、效率极低的问题，提出了一种基于跳跃表编码的NoSQL数据库查询操作的实现方法。该方法適用范围极其广泛，可以实现对不同数据类型的多种查询与检索。与此同时，该方法本身使用的跳跃表也是采用Key-Value键值对的方式进行存储的。

参考文献：

[1] 郎云海.NoSQL数据库与关系型数据库对比 [J].低碳世界，2019，9（5）：323-324.

[2] 叶文.NoSQL数据库与缓存一致性研究 [J].信息与电脑（理论版），2018（21）：143-144.

[3] 陈果.大数据时代基于NoSQL数据库查询技术的应用 [J].办公自动化，2021，26（5）：59-60+46.

[4] 赵永强.基于NoSQL的特色数据库系统研究 [J].图书馆工作与研究，2018（S1）：97-99+124.

[5] 张华兵，林志达，张今革.基于NoSQL数据库的模型设计方法 [J].电子技术与软件工程，2019（23）：174-175.

[6] 杨岚.大数据环境下NoSQL数据库查询技术应用研究 [J].湖北第二师范学院学报，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数据库的大数据查询技术实践探索 [J].电脑编程技巧与维护，2018（11）：89-90+131.

[9] 马文龙，朱妤晴，蒋德钧，等.Key-Value型NoSQL本地存储系统研究 [J].计算机学报，2018，41（8）：1722-1751.

[10] 陈忠菊.NoSQL数据库的研究和应用 [J].电脑编程技巧与维护，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数据库的数据存储 [J].科学与信息化，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读写性能研究与优化 [D].徐州：中国矿业大学，2016.

[15] 陈庆全，黄文明，崔亚楠.基于改进跳跃表的数据检索系统应用 [J].计算机系统应用，2008（12）：73-76.

作者简介：何欣峰（1974—），男，汉族，江苏南京人，中级工程师，高级测评师，CISP，CIIPT，本科，研究方向：网络应用与安全。