红黑树优化的SQLite索引在测速系统中的应用

许如峰+杨明武+张青春+邱换春

摘 要： 针对当前以B树为存储结构的SQLite数据库在处理庞大数据量时效率低下的问题，使用红黑树结构来替换B树结构，并将经红黑树优化过的SQLite应用在交通监控测速仪系统上。首先在Visual Studio 2008环境下分别运行红黑树及B树代码，对随机产生的大量数据执行插入、查询及删除操作，并将上述操作的时间开销进行对比分析；然后将优化的SQLite应用在交通监控测速仪系统中，并同使用原SQLite的同型号设备就处理数据的效率进行对比分析与测试。结果表明，在处理庞大数据时，红黑树对数据的操作效率要远高于B树，当数据量同为600万条时，其插入、查询和删除操作的平均时间开销分别降低68.5%，84.4%和68.8%；同原交通监控测速仪相比，使用经红黑树优化的设备效率提高了40.16%。

关键词： SQLite数据库； 数据存储； 红黑树； B树； 时间开销； 交通监控测速仪

中图分类号： TN919?34； TP311 文献标识码： A 文章编号： 1004?373X（2018）04?0052?04

Abstract： In allusion to the low efficiency problem of the current SQLite database with B tree as the storage structure when processing a large amount of data， the B tree structure is replaced by the red?black （RB） tree structure， and the RB tree optimized SQLite is applied to the traffic monitoring velocimeter system. The codes of the RB tree and B tree are run respectively in Visual Studio 2008 environment to execute the insert， query and delete operations for the large amount of randomly generated data， and the contrast analysis is performed for the time cost of the above operations. The optimized SQLite is applied to the traffic monitoring velocimeter system， and the contrast analysis and test of data processing efficiency between the RB tree optimized device and the same model device using the original SQLite are performed. The results show that when processing a large amount of data， the data operation efficiency of the RB tree is much higher than the B tree， and when the data quantity reaches 6 million， the average time cost of insert， query and delete operations is reduced by 68.5%， 84.4% and 68.8% respectively， and in comparison with the previous traffic monitoring velocimeter， the efficiency of the RB tree optimized device increases by 40.16%.

Keywords： SQLite database； data storage； RB tree； B tree； time cost； traffic monitoring velocimeter

0 引 言

SQLite是一种开源、资源占用少、超轻量级的嵌入式数据库，它完全采用C语言编写具有完全的独立性和开放性，且不依赖外部环境[1?2]。SQLite数据库支持嵌入式的设计目标，目前已经应用在很多嵌入式产品中[3?4]。随着SQLite处理的数据量变大和变复杂，在查询操作时，若B树节点存储的关键字比较多，需要对每个节点中每个关键字依次遍历，树的高度越大，节点越多，遍历的次数就越多，需要的时间也会大大增加。在插入、删除操作时，为了保持其结构的严格平衡，B 树要通过多次的分裂或合并节点，同时也要进行多次旋转，这种对数据循环的存取操作，势必会大大增加其操作时间[5]。为了有效提高数据库的访问速度，一般主要从软件方面去优化其数据结构，也即寻找性能优异的索引机制应用到SQLite中，提高其处理数据的操作效率，尤其是提高其处理大量数据的能力。红黑（RB）树就是一种具有该优势的数据结构，它的每个节点中包含一个关键字，并把节点着色，利用颜色来检测树的平衡。由于无论怎样破坏其结构，总能在经过有限的旋转（不超过3次）和染色操作后恢复平衡，和B树相比，在查询操作时，对每个节点进行遍历所用的时间较短，同时由于它特有的性质和旋转规则，在插入、删除操作时，它的旋转次数少，操作效率比较高。如果将红黑树结构应用到嵌入式数据库SQLite 中，可有效提高SQLite处理庞大数据量的性能。

当前，超速行驶是我国道路交通事故的主要原因之一。以交通监控测速仪为代表的测速设备是检测车辆超速行驶的一大利器。笔者在参与研发某型交通监控測速仪项目时，通过实际测试发现，作为使用嵌入式数据库SQLite来管理其图片数据的交通监控测速仪，当其抓拍的图片数据过多时，查找效率会显著降低，严重影响后续的有关操作使用，进而影响交通道路执法。该项目中的问题亟待解决。endprint

本文为了提高SQLite数据库处理庞大数据量的性能，对B树和RB树索引安排了三组数据进行测试，主要针对相同数据量下二者执行插入、查询和删除操作的时间开销方面进行测试比较与分析。将红黑树优化的嵌入式数据库SQLite应用到交通监控测速仪系统中，并同使用原SQLite的同型号设备对处理数据的效率进行对比分析与测试。

1 算法及工程应用

1.1 SQLite与B树

1.1.1 SQLite的体系结构

SQLite拥有简洁、模块化的体系结构，在体系结构的“编译器”中编译查询语句，所有的SQL语句都是先编译成虚拟机语言，B树作为嵌入式数据库SQLite的索引，其作用是负责排序，通过它维护着多个页（pager）之间错综复杂的关系，而这些关系能够保证快速定位并找到一切有联系的数据[6?7]。具体结构如图1所示。

1.1.2 B树相关介绍

B树作为数据库常用的一种索引结构，其是通过平衡二叉树演变过来的一种严格平衡多路查找树，M阶的B树一般使下列条件成立[8?9]：

1） 树中每个节点至多含有M个子节点（M≥2）；

2） 除根节点和叶子节点外，其他每个节点至少有[M2]个子节点；

3） 若根节点不是叶子节点，则至少有2个子节点；

4） 所有的叶子节点在同一层；

5） 有K个子节点的非根节点恰好包含K-1个关键字。

就M阶B树而言，其每个节点中最多存放M-1个关键字，在查询操作时，首先要对根节点所有关键字进行遍历，当数据量较小时，由于每个节点可以拥有大量的子节点，在一定程度上进行查询操作确实很高效。但随着数据量的增加，原有的层数不足以存放现有的数据，就会分层，即B树的高度会增加，导致查询效率以对数级下降。插入和删除数据时，除了对数据节点的查询遍历外，随着新节点的加入或旧節点的删除，B树原有结构会遭到破坏，为了继续保持原有结构的平衡，就要对B数执行修复操作：不断地向上分裂及合并节点，平衡旋转相应的节点，会使其处理大量数据的效率降低。

1.2 红黑树

红黑树定义：一种二叉查找树，但在每个节点上增加一个存储位表示节点的颜色，可以是Red或Black。对所有从根到叶子路径上各个节点着色，通过这一方式来确保没有一条路径的高度是其他路径的两倍，因而其结构是近似平衡的。红黑树有5个重要性质：

1） 每个节点非红即黑；

2） 根节点必须是黑；

3） 每个叶节点（叶节点即指树尾端NIL指针或NULL节点）都是黑的；

4） 如果一个节点是红的，那么它的两个子节点都要是黑的；

5） 对于任意节点而言，其到叶节点树尾端NIL指针的每条路径都包含相同数目的黑节点[10]。

红黑树的红色节点和黑色节点无特别的含义，仅仅是对红黑树的平衡结构提出一种辅助的约束。红黑树的结构体类型如下：

对红黑树中进行查询，当红黑树非空时，首先将给定值和根节点的关键字比较，若相等，则查询成功，否则将依据给定值和根节点的关键字之间的大小关系分别在左子树或右子树上继续进行查询，直到查询成功或指向外部节点。因此，当红黑树深度越高，则其查询操作的时间复杂性便越大，但在最坏情况下的时间复杂度为一定值[11?12][OlgN]。在插入和删除数据时，红黑树不同于普通的平衡二叉树，其能够在牺牲严格平衡性的条件下，可通过最多3次旋转来解决任何不平衡，无需多次循环存取数据，故随着节点个数N的增加，红黑树会获得高速的数据插入、删除的速度，从而大幅提高数据的操作效率。

1.3 交通监控测速仪

交通监控测速仪广泛应用在国内高速公路及其他一些需要重点监控的路段上，该设备通过平板窄波雷达判断机动车是否超速，可对超速车辆进行抓拍，并把超速车辆的信息（如超速值、车牌号及时间等）叠加到抓拍的图片上进行保存供执法工作人员使用。在交通监控测速仪系统中，选用SQLite作为图片数据的存储数据库，抓拍图片以当时的日期、时间和速度值命名并保存。该数据库里面存放的为图片数据的索引信息。可以通过调用SQLite给出的接口来实现对数据库的访问操作。SQLite在具体工作时，会将设备连续抓拍的图片数据载入，生成一棵B树，以图片名为查找索引；当插入或删除信息时，会向树中加入或删去一个节点，并且会根据B树规则进行树节点的更新；查找数据时，按照图片名为索引，进行查找。为了改善并提高原有SQLite数据库处理大量数据的性能，本文把经红黑树优化的SQLite应用到交通监控测速仪设备中。

2 实验分析与应用实例

2.1 实验分析

2.1.1 测试环境

在Windows 7系统Intel[?] Core（TM） i3?2120 CPU@3.30 GHz 4 GB内存的PC机上测试；编译器为Visual Studio 2008；使用clock（）计时函数来统计实验中各操作所消耗时间；程序均用C++语言编写。

2.1.2 算法测试与分析

为了保证实验测试中的精确性，先让两种索引机制使用相同的测试数据。程序中使用的无重复随机数据，均是由经过处理的random（）函数产生。每组的测试方法和结果分析描述如下。

1） 插入操作性能测试

本实验在原来为空的B树和RB树索引结构上通过分别调用B_Insert（）函数和RB_Insert（）函数，先后插入50万条、100万条、150万条、200万条、250万条、300万条和350万条、400万条、450万条、500万条、550万条、600万条数据。测试结果如图2所示。

分析图2可知，相比于B树索引，RB树索引在插入操作上的效率明显要更高。因为随着数据量不断增加，插入过程导致不平衡旋转的频率也会增加，所以RB树有限（不超过3次）的旋转优势便显现出来。在同为600万条数据量的情况下，B树插入的平均时间开销为39.1 s；RB树插入的平均时间开销为12.3 s，可得平均时间开销降低了68.5%。endprint

2） 等值查询性能测试

在实验1的基础上，对B树索引和RB树索引结构通过分别调用B_Search（）函数和RB_Search（）函数，先后查询B树和RB树里面的数据，并分别记录下所用的时间开销。测试结果如图3所示。

分析图3可知，随着数据量的增加，B树的高度会增加，加上其逐一遍历关键字，则会降低查询效率。由于RB树对数据进行二分查找遍历，当数据量不断增加时仍具有很高的查询效率。在同为600万条数据量的情况下，B树查询的平均时间开销为41.8 s；RB树查询的平均时间开销为6.5 s，可得平均时间开销降低了84.8%。

3） 删除操作性能测试

同样在实验1的基础上，对B树索引和RB树索引通过分别调用B_Delete（）函数和RB_Delete（）函数，依次删除50万条、100万条、150万条、200万条、250万条、300万条和350万条、400万条、450万条、500万条、550万条、600万条数据。并分别记录下所用的时间开销。测试结果如图4所示。

分析图4可知，由于删除数据时，需要平衡旋转和指针移动的频率会高很多，故二者在删除操作的耗时也会有较大差距。在同为600万数据量的情况下，B树删除的平均时间开销为37.9 s；RB树删除的平均时间开销为11.8 s，可得平均时间开销降低了68.8%。

2.2 应用实例

把红黑树优化过的SQLite数据库应用到笔者参与研发的交通监控测速仪上，并同以前的同型号设备对处理数据的效率进行对比分析与测试。测试结果见图5。

通过图5可知，在同为5万条图片数据的条件下，原来SQLite处理以上数据量的时间开销约为62.5 s，使用红黑树优化SQLite处理相同的数据量，其时间开销为37.4 s，容易得出时间开销比原来降低了40.16%。明显地，使用红黑树优化的SQLite应用到交通監控测速仪上后，有效提高了设备对庞大数据量的处理能力，改善了设备的性能。

3 结 语

本文使用红黑树结构来替换B树存储结构，对B树和RB树索引安排了三组数据进行测试，对相同数据量下二者执行插入、查询和删除操作的时间开销进行测试比较与分析；然后将红黑树优化的SQLite应用在交通监控测速仪中，并同使用原SQLite的同型号设备就处理数据的效率进行对比分析与测试。在处理庞大数据时，红黑树对数据的操作效率要远高于B树，当数据量同为600万条时，其插入、查询和删除操作的平均时间开销分别降低68.5%，84.4%和68.8%。同以前交通监控测速仪相比，使用经红黑树优化的设备对图片数据处理时，效率提高了40.16%，解决了该项目中交通监控测速仪在处理庞大数据量时效率低下的问题，改善了设备的性能。

参考文献

[1] 梅强，胡勤友，杨春.基于Android平台的船用北斗通信导航系统设计[J].合肥工业大学学报（自然科学版），2013，36（5）：595?598.

MEI Qiang， HU Qinyou， YANG Chun. Design of maritime Beidou communication and navigation system based on Android platform [J]. Journal of Hefei University of Technology （Natural science edition）， 2013， 36（5）： 595?598.

[2] CHEN Dai， HAN Xudong， WANG Wei. Use of SQLite on embedded system [C]// Proceedings of International Conference on Intelligent Computing and Cognitive Informatics. Washington： IEEE Computer Society， 2010： 210?213.

[3] 陈毅辉，龙昭华.红黑树在RFID标签文件系统中的研究与应用[J].计算机工程与设计，2016，37（10）：2837?2843.

CHEN Yihui， LONG Zhaohua. Applying red?black tree in RFID tag file system [J]. Computer engineering and design， 2016， 37（10）： 2837?2843.

[4] 林回祥，程小军.SQLite数据库在雷达日志管理中的应用[J].雷达科学与技术，2016，14（2）：194?197.

LIN Huixiang， CHENG Xiaojun. Application of SQLite database in radar log management [J]. Radar science and technology， 2016， 14（2）： 194?197.

[5] 毕攀.基于红黑树的嵌入式数据库SQLite索引机制的优化方案的研究[D].太原：太原科技大学，2012.

BI Pan. Optimization study of indexing mechanism of embedded database SQLite Based on red?black tree [D]. Taiyuan： Taiyuan University of Science and Technology， 2012.

[6] L? Junyan， XU Shiguo， LI Yijie. Application research of embedded database SQLite [C]// Proceedings of International Forum on Information Technology and Applications. Chengdu： IEEE， 2009： 539?543.endprint

[7] ALLEN G， OWENS M. The definitive guide to SQLite [M]. 2nd ed. New York： Apress， 2010.

[8] JALUTA I. Transaction management in B?tree?indexed database systems [C]// Proceedings of International Conference on Information Science， Electronics and Electrical Engineering. Sapporo： IEEE， 2014， 3： 1968?1975.

[9] 朱阅岸，周烜，张延松，等.多核处理器下事务型数据库性能优化技术综述[J].计算机学报，2015，38（9）：1865?1879.

ZHU Yuean， ZHOU Xuan， ZHANG Yansong， et al. A Survey of optimization methods for transactional database in multi?core era [J]. Chinese journal of computers， 2015， 38（9）： 1865?1879.

[10] CORMEN T H， LEISERSON C E， RIVEST R L， et al. Introduction to Algorithms [M]. 3rd ed. Cambridge： MIT Press， 2009.

[11] HOONG P K， SHYANG O Y， TAN I K T. Red?black tree architecture for P2P media streaming [C]// Proceedings of IEEE Region 10 Conference. Xian： IEEE， 2013： 1?4.

[12] HOLENDERSKI M， BRIL R J， LUKKIEN J J. Red?black trees with relative node keys [J]. Information processing letters， 2014， 114（11）： 591?596.endprint