紅黑樹優(yōu)化的SQLite索引在測速系統(tǒng)中的應用

許如峰+楊明武+張青春+邱換春

摘 要： 針對當前以B樹為存儲結(jié)構(gòu)的SQLite數(shù)據(jù)庫在處理龐大數(shù)據(jù)量時效率低下的問題，使用紅黑樹結(jié)構(gòu)來替換B樹結(jié)構(gòu)，并將經(jīng)紅黑樹優(yōu)化過的SQLite應用在交通監(jiān)控測速儀系統(tǒng)上。首先在Visual Studio 2008環(huán)境下分別運行紅黑樹及B樹代碼，對隨機產(chǎn)生的大量數(shù)據(jù)執(zhí)行插入、查詢及刪除操作，并將上述操作的時間開銷進行對比分析；然后將優(yōu)化的SQLite應用在交通監(jiān)控測速儀系統(tǒng)中，并同使用原SQLite的同型號設(shè)備就處理數(shù)據(jù)的效率進行對比分析與測試。結(jié)果表明，在處理龐大數(shù)據(jù)時，紅黑樹對數(shù)據(jù)的操作效率要遠高于B樹，當數(shù)據(jù)量同為600萬條時，其插入、查詢和刪除操作的平均時間開銷分別降低68.5%，84.4%和68.8%；同原交通監(jiān)控測速儀相比，使用經(jīng)紅黑樹優(yōu)化的設(shè)備效率提高了40.16%。

關(guān)鍵詞： SQLite數(shù)據(jù)庫； 數(shù)據(jù)存儲； 紅黑樹； B樹； 時間開銷； 交通監(jiān)控測速儀

中圖分類號： 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是一種開源、資源占用少、超輕量級的嵌入式數(shù)據(jù)庫，它完全采用C語言編寫具有完全的獨立性和開放性，且不依賴外部環(huán)境[1?2]。SQLite數(shù)據(jù)庫支持嵌入式的設(shè)計目標，目前已經(jīng)應用在很多嵌入式產(chǎn)品中[3?4]。隨著SQLite處理的數(shù)據(jù)量變大和變復雜，在查詢操作時，若B樹節(jié)點存儲的關(guān)鍵字比較多，需要對每個節(jié)點中每個關(guān)鍵字依次遍歷，樹的高度越大，節(jié)點越多，遍歷的次數(shù)就越多，需要的時間也會大大增加。在插入、刪除操作時，為了保持其結(jié)構(gòu)的嚴格平衡，B 樹要通過多次的分裂或合并節(jié)點，同時也要進行多次旋轉(zhuǎn)，這種對數(shù)據(jù)循環(huán)的存取操作，勢必會大大增加其操作時間[5]。為了有效提高數(shù)據(jù)庫的訪問速度，一般主要從軟件方面去優(yōu)化其數(shù)據(jù)結(jié)構(gòu)，也即尋找性能優(yōu)異的索引機制應用到SQLite中，提高其處理數(shù)據(jù)的操作效率，尤其是提高其處理大量數(shù)據(jù)的能力。紅黑（RB）樹就是一種具有該優(yōu)勢的數(shù)據(jù)結(jié)構(gòu)，它的每個節(jié)點中包含一個關(guān)鍵字，并把節(jié)點著色，利用顏色來檢測樹的平衡。由于無論怎樣破壞其結(jié)構(gòu)，總能在經(jīng)過有限的旋轉(zhuǎn)（不超過3次）和染色操作后恢復平衡，和B樹相比，在查詢操作時，對每個節(jié)點進行遍歷所用的時間較短，同時由于它特有的性質(zhì)和旋轉(zhuǎn)規(guī)則，在插入、刪除操作時，它的旋轉(zhuǎn)次數(shù)少，操作效率比較高。如果將紅黑樹結(jié)構(gòu)應用到嵌入式數(shù)據(jù)庫SQLite 中，可有效提高SQLite處理龐大數(shù)據(jù)量的性能。

當前，超速行駛是我國道路交通事故的主要原因之一。以交通監(jiān)控測速儀為代表的測速設(shè)備是檢測車輛超速行駛的一大利器。筆者在參與研發(fā)某型交通監(jiān)控測速儀項目時，通過實際測試發(fā)現(xiàn)，作為使用嵌入式數(shù)據(jù)庫SQLite來管理其圖片數(shù)據(jù)的交通監(jiān)控測速儀，當其抓拍的圖片數(shù)據(jù)過多時，查找效率會顯著降低，嚴重影響后續(xù)的有關(guān)操作使用，進而影響交通道路執(zhí)法。該項目中的問題亟待解決。endprint

本文為了提高SQLite數(shù)據(jù)庫處理龐大數(shù)據(jù)量的性能，對B樹和RB樹索引安排了三組數(shù)據(jù)進行測試，主要針對相同數(shù)據(jù)量下二者執(zhí)行插入、查詢和刪除操作的時間開銷方面進行測試比較與分析。將紅黑樹優(yōu)化的嵌入式數(shù)據(jù)庫SQLite應用到交通監(jiān)控測速儀系統(tǒng)中，并同使用原SQLite的同型號設(shè)備對處理數(shù)據(jù)的效率進行對比分析與測試。

1 算法及工程應用

1.1 SQLite與B樹

1.1.1 SQLite的體系結(jié)構(gòu)

SQLite擁有簡潔、模塊化的體系結(jié)構(gòu)，在體系結(jié)構(gòu)的“編譯器”中編譯查詢語句，所有的SQL語句都是先編譯成虛擬機語言，B樹作為嵌入式數(shù)據(jù)庫SQLite的索引，其作用是負責排序，通過它維護著多個頁（pager）之間錯綜復雜的關(guān)系，而這些關(guān)系能夠保證快速定位并找到一切有聯(lián)系的數(shù)據(jù)[6?7]。具體結(jié)構(gòu)如圖1所示。

1.1.2 B樹相關(guān)介紹

B樹作為數(shù)據(jù)庫常用的一種索引結(jié)構(gòu)，其是通過平衡二叉樹演變過來的一種嚴格平衡多路查找樹，M階的B樹一般使下列條件成立[8?9]：

1） 樹中每個節(jié)點至多含有M個子節(jié)點（M≥2）；

2） 除根節(jié)點和葉子節(jié)點外，其他每個節(jié)點至少有[M2]個子節(jié)點；

3） 若根節(jié)點不是葉子節(jié)點，則至少有2個子節(jié)點；

4） 所有的葉子節(jié)點在同一層；

5） 有K個子節(jié)點的非根節(jié)點恰好包含K-1個關(guān)鍵字。

就M階B樹而言，其每個節(jié)點中最多存放M-1個關(guān)鍵字，在查詢操作時，首先要對根節(jié)點所有關(guān)鍵字進行遍歷，當數(shù)據(jù)量較小時，由于每個節(jié)點可以擁有大量的子節(jié)點，在一定程度上進行查詢操作確實很高效。但隨著數(shù)據(jù)量的增加，原有的層數(shù)不足以存放現(xiàn)有的數(shù)據(jù)，就會分層，即B樹的高度會增加，導致查詢效率以對數(shù)級下降。插入和刪除數(shù)據(jù)時，除了對數(shù)據(jù)節(jié)點的查詢遍歷外，隨著新節(jié)點的加入或舊節(jié)點的刪除，B樹原有結(jié)構(gòu)會遭到破壞，為了繼續(xù)保持原有結(jié)構(gòu)的平衡，就要對B數(shù)執(zhí)行修復操作：不斷地向上分裂及合并節(jié)點，平衡旋轉(zhuǎn)相應的節(jié)點，會使其處理大量數(shù)據(jù)的效率降低。

1.2 紅黑樹

紅黑樹定義：一種二叉查找樹，但在每個節(jié)點上增加一個存儲位表示節(jié)點的顏色，可以是Red或Black。對所有從根到葉子路徑上各個節(jié)點著色，通過這一方式來確保沒有一條路徑的高度是其他路徑的兩倍，因而其結(jié)構(gòu)是近似平衡的。紅黑樹有5個重要性質(zhì)：

1） 每個節(jié)點非紅即黑；

2） 根節(jié)點必須是黑；

3） 每個葉節(jié)點（葉節(jié)點即指樹尾端NIL指針或NULL節(jié)點）都是黑的；

4） 如果一個節(jié)點是紅的，那么它的兩個子節(jié)點都要是黑的；

5） 對于任意節(jié)點而言，其到葉節(jié)點樹尾端NIL指針的每條路徑都包含相同數(shù)目的黑節(jié)點[10]。

紅黑樹的紅色節(jié)點和黑色節(jié)點無特別的含義，僅僅是對紅黑樹的平衡結(jié)構(gòu)提出一種輔助的約束。紅黑樹的結(jié)構(gòu)體類型如下：

對紅黑樹中進行查詢，當紅黑樹非空時，首先將給定值和根節(jié)點的關(guān)鍵字比較，若相等，則查詢成功，否則將依據(jù)給定值和根節(jié)點的關(guān)鍵字之間的大小關(guān)系分別在左子樹或右子樹上繼續(xù)進行查詢，直到查詢成功或指向外部節(jié)點。因此，當紅黑樹深度越高，則其查詢操作的時間復雜性便越大，但在最壞情況下的時間復雜度為一定值[11?12][OlgN]。在插入和刪除數(shù)據(jù)時，紅黑樹不同于普通的平衡二叉樹，其能夠在犧牲嚴格平衡性的條件下，可通過最多3次旋轉(zhuǎn)來解決任何不平衡，無需多次循環(huán)存取數(shù)據(jù)，故隨著節(jié)點個數(shù)N的增加，紅黑樹會獲得高速的數(shù)據(jù)插入、刪除的速度，從而大幅提高數(shù)據(jù)的操作效率。

1.3 交通監(jiān)控測速儀

交通監(jiān)控測速儀廣泛應用在國內(nèi)高速公路及其他一些需要重點監(jiān)控的路段上，該設(shè)備通過平板窄波雷達判斷機動車是否超速，可對超速車輛進行抓拍，并把超速車輛的信息（如超速值、車牌號及時間等）疊加到抓拍的圖片上進行保存供執(zhí)法工作人員使用。在交通監(jiān)控測速儀系統(tǒng)中，選用SQLite作為圖片數(shù)據(jù)的存儲數(shù)據(jù)庫，抓拍圖片以當時的日期、時間和速度值命名并保存。該數(shù)據(jù)庫里面存放的為圖片數(shù)據(jù)的索引信息。可以通過調(diào)用SQLite給出的接口來實現(xiàn)對數(shù)據(jù)庫的訪問操作。SQLite在具體工作時，會將設(shè)備連續(xù)抓拍的圖片數(shù)據(jù)載入，生成一棵B樹，以圖片名為查找索引；當插入或刪除信息時，會向樹中加入或刪去一個節(jié)點，并且會根據(jù)B樹規(guī)則進行樹節(jié)點的更新；查找數(shù)據(jù)時，按照圖片名為索引，進行查找。為了改善并提高原有SQLite數(shù)據(jù)庫處理大量數(shù)據(jù)的性能，本文把經(jīng)紅黑樹優(yōu)化的SQLite應用到交通監(jiān)控測速儀設(shè)備中。

2 實驗分析與應用實例

2.1 實驗分析

2.1.1 測試環(huán)境

在Windows 7系統(tǒng)Intel[?] Core（TM） i3?2120 CPU@3.30 GHz 4 GB內(nèi)存的PC機上測試；編譯器為Visual Studio 2008；使用clock（）計時函數(shù)來統(tǒng)計實驗中各操作所消耗時間；程序均用C++語言編寫。

2.1.2 算法測試與分析

為了保證實驗測試中的精確性，先讓兩種索引機制使用相同的測試數(shù)據(jù)。程序中使用的無重復隨機數(shù)據(jù)，均是由經(jīng)過處理的random（）函數(shù)產(chǎn)生。每組的測試方法和結(jié)果分析描述如下。

1） 插入操作性能測試

本實驗在原來為空的B樹和RB樹索引結(jié)構(gòu)上通過分別調(diào)用B_Insert（）函數(shù)和RB_Insert（）函數(shù)，先后插入50萬條、100萬條、150萬條、200萬條、250萬條、300萬條和350萬條、400萬條、450萬條、500萬條、550萬條、600萬條數(shù)據(jù)。測試結(jié)果如圖2所示。

分析圖2可知，相比于B樹索引，RB樹索引在插入操作上的效率明顯要更高。因為隨著數(shù)據(jù)量不斷增加，插入過程導致不平衡旋轉(zhuǎn)的頻率也會增加，所以RB樹有限（不超過3次）的旋轉(zhuǎn)優(yōu)勢便顯現(xiàn)出來。在同為600萬條數(shù)據(jù)量的情況下，B樹插入的平均時間開銷為39.1 s；RB樹插入的平均時間開銷為12.3 s，可得平均時間開銷降低了68.5%。endprint

2） 等值查詢性能測試

在實驗1的基礎(chǔ)上，對B樹索引和RB樹索引結(jié)構(gòu)通過分別調(diào)用B_Search（）函數(shù)和RB_Search（）函數(shù)，先后查詢B樹和RB樹里面的數(shù)據(jù)，并分別記錄下所用的時間開銷。測試結(jié)果如圖3所示。

分析圖3可知，隨著數(shù)據(jù)量的增加，B樹的高度會增加，加上其逐一遍歷關(guān)鍵字，則會降低查詢效率。由于RB樹對數(shù)據(jù)進行二分查找遍歷，當數(shù)據(jù)量不斷增加時仍具有很高的查詢效率。在同為600萬條數(shù)據(jù)量的情況下，B樹查詢的平均時間開銷為41.8 s；RB樹查詢的平均時間開銷為6.5 s，可得平均時間開銷降低了84.8%。

3） 刪除操作性能測試

同樣在實驗1的基礎(chǔ)上，對B樹索引和RB樹索引通過分別調(diào)用B_Delete（）函數(shù)和RB_Delete（）函數(shù)，依次刪除50萬條、100萬條、150萬條、200萬條、250萬條、300萬條和350萬條、400萬條、450萬條、500萬條、550萬條、600萬條數(shù)據(jù)。并分別記錄下所用的時間開銷。測試結(jié)果如圖4所示。

分析圖4可知，由于刪除數(shù)據(jù)時，需要平衡旋轉(zhuǎn)和指針移動的頻率會高很多，故二者在刪除操作的耗時也會有較大差距。在同為600萬數(shù)據(jù)量的情況下，B樹刪除的平均時間開銷為37.9 s；RB樹刪除的平均時間開銷為11.8 s，可得平均時間開銷降低了68.8%。

2.2 應用實例

把紅黑樹優(yōu)化過的SQLite數(shù)據(jù)庫應用到筆者參與研發(fā)的交通監(jiān)控測速儀上，并同以前的同型號設(shè)備對處理數(shù)據(jù)的效率進行對比分析與測試。測試結(jié)果見圖5。

通過圖5可知，在同為5萬條圖片數(shù)據(jù)的條件下，原來SQLite處理以上數(shù)據(jù)量的時間開銷約為62.5 s，使用紅黑樹優(yōu)化SQLite處理相同的數(shù)據(jù)量，其時間開銷為37.4 s，容易得出時間開銷比原來降低了40.16%。明顯地，使用紅黑樹優(yōu)化的SQLite應用到交通監(jiān)控測速儀上后，有效提高了設(shè)備對龐大數(shù)據(jù)量的處理能力，改善了設(shè)備的性能。

3 結(jié) 語

本文使用紅黑樹結(jié)構(gòu)來替換B樹存儲結(jié)構(gòu)，對B樹和RB樹索引安排了三組數(shù)據(jù)進行測試，對相同數(shù)據(jù)量下二者執(zhí)行插入、查詢和刪除操作的時間開銷進行測試比較與分析；然后將紅黑樹優(yōu)化的SQLite應用在交通監(jiān)控測速儀中，并同使用原SQLite的同型號設(shè)備就處理數(shù)據(jù)的效率進行對比分析與測試。在處理龐大數(shù)據(jù)時，紅黑樹對數(shù)據(jù)的操作效率要遠高于B樹，當數(shù)據(jù)量同為600萬條時，其插入、查詢和刪除操作的平均時間開銷分別降低68.5%，84.4%和68.8%。同以前交通監(jiān)控測速儀相比，使用經(jīng)紅黑樹優(yōu)化的設(shè)備對圖片數(shù)據(jù)處理時，效率提高了40.16%，解決了該項目中交通監(jiān)控測速儀在處理龐大數(shù)據(jù)量時效率低下的問題，改善了設(shè)備的性能。

參考文獻

[1] 梅強，胡勤友，楊春.基于Android平臺的船用北斗通信導航系統(tǒng)設(shè)計[J].合肥工業(yè)大學學報（自然科學版），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標簽文件系統(tǒng)中的研究與應用[J].計算機工程與設(shè)計，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數(shù)據(jù)庫在雷達日志管理中的應用[J].雷達科學與技術(shù)，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] 畢攀.基于紅黑樹的嵌入式數(shù)據(jù)庫SQLite索引機制的優(yōu)化方案的研究[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] 朱閱岸，周烜，張延松，等.多核處理器下事務型數(shù)據(jù)庫性能優(yōu)化技術(shù)綜述[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