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

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

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

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

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

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

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

1 算法及工程應(yīng)用

1.1 SQLite與B樹

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

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

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

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

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

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

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

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

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

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

1.2 紅黑樹

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

1） 每個(gè)節(jié)點(diǎn)非紅即黑；

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

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

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

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

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

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

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

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

2 實(shí)驗(yàn)分析與應(yīng)用實(shí)例

2.1 實(shí)驗(yàn)分析

2.1.1 測(cè)試環(huán)境

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

2.1.2 算法測(cè)試與分析

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

1） 插入操作性能測(cè)試

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

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

2） 等值查詢性能測(cè)試

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

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

3） 刪除操作性能測(cè)試

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

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

2.2 應(yīng)用實(shí)例

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

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

3 結(jié) 語(yǔ)

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

參考文獻(xiàn)

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