一種改進的內存索引算法在中藥追溯數據處理中的應用*

張　博，盛　魁，陳繼祥，董　輝

(1.亳州職業技術學院 信息工程系，安徽 亳州 236800；2.安徽省中醫藥科學院 亳州中醫藥研究所，安徽 亳州 236800)

?

一種改進的內存索引算法在中藥追溯數據處理中的應用*

張博1，2，盛魁1，2，陳繼祥1，2，董輝1，2

(1.亳州職業技術學院 信息工程系，安徽 亳州 236800；2.安徽省中醫藥科學院 亳州中醫藥研究所，安徽 亳州 236800)

摘要:在中藥質量追溯系統中，為了保證中藥材在流通環節中的數據采集效果，需要部署RFID標簽和傳感器.在大規模RFID應用中，后臺服務器處理的標簽數據量巨大，容易造成數據傳輸的瓶頸.在數據檢索時采用改進的遍歷索引算法，構建高效的內存數據結構，能夠加快RFID標簽數據讀取速度，提高數據源的穩定性，同時降低后臺數據庫的負擔，確保數據處理的高效性和安全性.

關鍵詞:數據處理；索引結構；RFID

在RFID系統應用中，RFID讀寫器通過無線射頻方式與標簽通信，獲取標簽的感知數據并發送到服務器平臺進行處理.在中藥材質量追溯系統中，為了保證中藥材流通過程中的溯源效果，需要大規模部署RFID標簽和傳感器，由于讀寫器需要讀寫的藥材標簽數據量較大，這就會產生大量標簽數據發送給后臺服務器，造成網絡數據吞吐量增加，容易導致網絡堵塞和服務器負擔過重[1].為解決上述問題，目前主流的解決方法是通過設置前置數據處理服務器，將讀寫器獲取的RFID標簽數據進行提前分組和篩選，經過前置服務器處理后的數據發送給后臺數據庫服務器，這樣就可以減少網絡數據吞吐量，降低了后臺數據庫服務器的負擔.

如何優化前置服務器的數據處理算法和數據結構，是提高前置服務器效率的關鍵.本文提出一種改進的T+樹內存數據結構算法，在傳統T樹的基礎上引入鏈式存儲結構，通過實際環境的測試驗證，能夠達到預期的目的.

1RFID數據處理基本方法

1.1標簽數據狀態特性

在 RFID 系統中，標簽和讀寫器通過事先分配的OID識別碼，能夠自動完成感知和匹配過程[2]；當標簽和讀寫器之間完成數據傳送后，感知關系將斷開.整個感知過程中，標簽的狀態分別處于感知、相應、斷開三個狀態，并且這三種狀態處于不斷的循環過程中[3].

在物聯網系統的應用中，感知設備之間通過無線信號進行聯系，當標簽和讀寫器的距離處于感知和斷開的臨界狀態時，或者標簽的電量不足導致標簽收發無線射頻信號強度不夠時，可能會使標簽處于兩種狀態的交替階段，這時讀寫器可能會失去對標簽的感知.因此系統判斷RFID標簽是否處在被感知狀態，應該觀察標簽的連續讀寫和感知狀態[4]，而不能憑某一個獨立的周期來進行判斷.

1.2標簽數據處理過程

在RFID系統部署中，每一個標簽包含的信息有：標簽識別碼、標簽來源、標簽保持狀態、標簽當前讀取序號.RFID系統數據庫服務器會對每一個周期的標簽狀態數據進行讀取對比[5]，具體操作類型有：①標簽數據的插入：RFID讀寫器讀取標簽的狀態數據后，將其與數據庫中已保存的RFID標簽數據進行比較，如果重合則該標簽已存在，如果比較結果沒有重合，則確認該標簽為新標簽，并更新標簽數據庫的信息[6].

②事件查詢：通過查詢標簽的當前狀態，生成標簽匯總信息，同時將匯總信息上傳到后臺服務器.

③刪除標簽數據：查詢處于非激活狀態的標簽并進行刪除操作，同時更新數據庫.

在物聯網系統的部署過程中，對于來自于感知層的無線射頻標簽數據處理，將產生大量的處理任務，如何提高任務處理的效率[7]，已經成為RFID應用需要重點關注的地方.

1.3內存數據處理方法

(1)RFID系統部署對數據庫的要求.在RFID系統進行部署時，實時處理數據將增加服務器的負荷，由于來自于RFID標簽的大量數據需要進行處理，同時大部分情況下無法預測標簽的長度和標簽數據的長度，因此傳統的算法普遍處理效率不高[8]，大大影響了RFID系統的部署效果.由于RFID系統的數據主要來自于實時數據讀取和采集，因此和傳統數據庫的結構不同，需要將數據庫的活動部分常駐主存，這樣才可以提高數據庫的訪問速度和效率，從而滿足RFID系統的運行需求.如何設計合理的內存索引數據結構，提高數據庫的訪問速度和數據吞吐量，已經成為RFID服務器部署時需要重點考慮的環節[9].

(2)內存索引的構建原理.構建合理的內存數據庫的索引結構，是提高數據讀寫訪問效率的重要基礎，在業界比較流行的模式是采用B樹與T樹索引.

①B樹.B樹結構由R.Bayer和 E.Mccreight提出，B樹的關鍵字在整棵樹中均勻分布，適合于順序查找[10].

假設一棵p階的B樹的結構如下：

a.如果根節點不是葉子節點，則其擁有2個孩子，其余各節點最多擁有 p個孩子[11]；

b.除根節點和葉子節點外，其他節點最少擁有p/2 個孩子；

c.所有葉子節點都處于同階；

d.有q個孩子的節點(除根節點和葉子節點)具備 q-1 個關鍵字.

在B樹中每個節點按照值域順序生成，由于B樹屬于平衡多叉樹，其完成數據索引的步驟是：先搜索到根節點，然后在根節點擁有的關鍵字(r1，……，ri)中查詢目標關鍵字，如果找到目標關鍵字就返回查找成功的結果，若未找到目標關鍵字則將查找范圍擴大至ri到ri+1之間，如果查找結束以后返回指向節點的指針為空，則表示查找過程失敗.

B樹的關鍵字均勻分布在樹中,并且出現在單個節點中, B樹采用二分法對關鍵字進行查找，其算法復雜度為O(log2n).

②T 樹.T樹索引結構由TobinJ Lhemna和Mihcael Carye提出，T樹結合了AVL樹和B樹的優點，適合于構建內存數據庫的索引結構.T樹的每一個節點可以保存多個索引鍵值，這樣提高了節點的空間效率[12]，由于T樹本質是AVL樹，所以各個節點有序排列，左子樹比根節點鍵值小，右子樹比根節點鍵值大.T樹特征如下：

a.T樹中某一節點的左右子樹相差1；

b.T樹中的節點擁有多個鍵值，這些鍵值按照順序排列；

c.每個節點包含的鍵值小于指定值，為小于等于節點中最大鍵值-2.

一個T樹節點包含了一個指向上一級父節點的指針，分別指向左右子節點的指針.在每一個節點中包含L和M兩個關鍵值，L是遍歷T樹時本節點前的所有節點中最大值，M是遍歷T樹時在節點后的所有節點中最小值，T樹的結構圖如圖1所示.

圖1　T樹節點結構圖

T樹的主要操作包括查找、插入、刪除.

a.T樹查找操作：首先要檢索目標值是否處于當前節點的左右鍵值之間，如果處于之間，將進行二分法查找；如果目標值大于右鍵值，將開始檢索右子節點；如果小于左鍵值，則對左子節點進行掃描.

b.T樹的插入操作：首先要查找插入位置，當位置檢索成功后，需要判斷樹中存儲空間是否充足，如果還有剩余空間，則將目標值插入到檢索成功位置，否則將根據目標值與左右鍵值的大小關系，為目標值分配新的節點，并將該節點關聯到上一節點的左子樹或右子樹.同時對T樹進行平衡檢查，若不滿足平衡調節則進行旋轉操作.

c.T樹的刪除操作：首先搜索刪除節點，搜索目標成功后將該節點鍵值刪除，如果刪除后該節點變為空節點，則將該節點也刪除，同時對T樹進行AVL檢查，確定是否進行旋轉操作.

在T樹的使用過程中，為了避免樹節點的臃腫，規定T樹內的每一個節點的關鍵字個數都不能大于左右子樹之差.當完成插入和刪除操作后，必須要對T數進行平衡性檢查，以此保證T樹的使用效率.

2改進的內存索引結構T+樹

2.1T+樹的內存索引結構

對于 RFID 應用來說，需要部署大規模感知設備和RFID標簽，因此數據處理的負擔也隨之增加.由于T樹的樹高較大，導致在樹節點進行更新時處理量加大，同時需要進行加鎖的節點數量也隨之增加，從而影響了T樹的遍歷過程，降低了內存數據的處理性能，因此針對傳統的T樹結構進行改進，以適應大規模并發數據處理的情況.

本文提出了一種改進的T+樹，在原有T樹結構上增加3個指針，F指針指向樹的上一級節點，L指針指向包含每個節點的頭指針鏈表，E指針指向包含每個節點的控制域鏈表，這樣可以通過指針將標簽數據的節點進行有機鏈接，從而更好地完成整個樹的查找、刪除、插入和旋轉操作，能夠使T+樹在構建內存索引結構中的效率更高，其結構圖如圖2所示.

圖2　T+樹節點結構圖

2.2RFID標簽數據處理過程實現

RFID數據服務器在對標簽數據進行處理時，主要涉及到的狀態數據有：標簽識別碼、標簽來源、標簽保持狀態、標簽當前讀取序號.在T+樹中，每個節點中設置對應的相關數據域，對上述5類數據進行分別保存，同時在T+樹中設置3個控制節點，分別用于保存下列鏈表的指針：查找成功的節點指針、已處理完畢的節點指針和處于被查找狀態的節點指針.

標簽數據存儲在T+樹結構的內存索引數據庫中，對數據進行讀寫和存儲操作時使用T+樹完成，在對標簽數據進行狀態更新時使用鏈表指針完成對內存索引結構的遍歷操作.

2.3算法的實施

RFID服務器在處理標簽數據時，使用T+樹建立的內存索引結構對數據進行處理，主要包括查詢、插入和刪除操作.

(1)查詢：當標簽進入T+樹的讀寫隊列后，首先讀取標簽的狀態指針關鍵值，然后判斷鍵值是否處于鏈表關鍵節點的鍵值范圍，如果處于范圍內，則返回查找成功狀態，否則依次按照上述步驟查找鏈表關鍵節點的左右子樹的鍵值.

(2)插入：首先讀取E指針中指向包含每個節點的控制域數據，然后判斷和查找插入位置，插入位置確定后，同時要檢查該節點中的存儲空間是否滿足插入標簽數據的要求，成功后則將標簽數據成功插入到檢索位置，否則將繼續對下一節點的左右子樹控制域進行讀取，直到檢索到滿足標簽數據插入的位置，重復上述的插入操作.

(3)刪除：通過讀取L指針指向當前節點的頭指針鏈表，判斷頭指針狀態，若為空則完成刪除節點操作，若不為空，則將L指針移動到左(右)子樹節點的鏈表，再次進行是否為空鏈表的判斷，從而完成刪除節點的操作.

在上述操作中，對于標簽的每一次數據操作周期，由于E指針和L指針的循環使用，可以更高效地完成對整個內存數據的遍歷過程，進一步提高數據處理速度.

2.4性能分析

通過對T+樹的算法進行計算驗證，與基于T樹結構的內存索引結構相比，T+樹結構的內存索引數據庫在實際使用中，插入、刪除等操作的效率更高，同時表現出更好的穩定性.驗證平臺為使用INTEL I3-4170 3.7Ghz(3M Cache)CPU,4G DDR3內存的計算機，操作系統為WINDOWS 7(64位)系統，數據庫版本采用MS-SQL Server 2012 SP2版本，RFID標簽數選用13.56M高頻電子標簽，標簽存儲容量32B，數量為10個，算法采用C++語言編寫，完成對索引結構的遍歷、刪除、插入操作,節點數為1000個.

圖3　插入節點操作

圖4　刪除節點操作

圖5　遍歷節點操作

上述性能對比結果顯示(見圖3～圖5)，T樹結構由于其本質屬于平衡二叉樹，運行效果較好，具備很好的穩定性.T+樹具有T樹的節點，在節點的控制過程中引入了鏈表結構，同時利用增加的3個指針，進一步提高了T+樹的操作靈活性和穩定性，使整個內存索引的數據操作達到了高效率的目標，兩種索引結構在遍歷節點的操作性能相差不大，但是T+樹在插入和刪除操作的時間耗費均低于傳統的T樹結構，符合內存索引算法的發展方向.在大規模部署中藥材溯源系統時，由于所需要的RFID標簽數量較大，涉及到的數據量較多，單位時間內存數據庫的負擔加重，需要考慮到T+樹需要搜索整棵樹才可以完成處理任務的特點，因此當前的算法可能會對系統的部署造成一定影響，降低內存數據庫的運行效率和速度，這是未來需要改進和完善的地方.

3結論

本文針對在大規模部署RFID標簽過程中，如何應對事件處理服務器的工作模式進行了探討，對目前常見的內存數據索引結構進行了比較，在基于T樹結構的基礎上，提出了改進的T+樹內存索引結構，同時將T+樹與傳統的B樹和T樹的運行效果進行對比，改進的T+樹結構能夠較好地處理大規模RFID標簽數據的讀寫任務，為中藥材溯源系統的建設提供技術基礎.

參考文獻：

[1]龔華明，陰躲芬.基于T*樹的RFID數據緩存的研究與實現[J].計算機與數字工程，2013，41(12):1967-1969.

[2]陳毅紅，馮全源，談文蓉.物聯網中RFID多標簽識別技術研究綜述[J].西南民族大學學報(自然科學版)，2014,40(5):719-723.

[3]董紹嬋，周敏奇，張蓉，等.內存數據索引以處理器為核心的性能優化技術[J].華東師范大學學報(自然科學版)，2014(5):192-206.

[4]張建華，張楠.基于混沌的RFID雙向認證協議[J].鐵道學報，2013(7):85-89.

[5]趙海，歐陽元新，熊璋.用于RFID中間件的主存數據庫索引結構[J].西南民族大學學報(自然科學版)，2014，40(4)：531-536.

[6]羅元劍，姜建國，王思葉,等. 基于有限狀態機的RFID流數據過濾與清理技術[J].軟件學報，2014，25(8):1713-1728.

[7]張博，南淑萍，孟利軍. RFID技術在道地中藥材質量溯源中的應用研究[J].長沙大學學報，2015，29(2):64-66.

[8]呂鵬，蔣平，吳欽章.一種T-樹的優化設計與實現方法[J].計算機工程，2013，29(2):5-8.

[9]薛世帥，劉丹，徐展，等.有源RFID標簽安全文件系統的設計[J].計算機工程與應用，2014(24)：47-49.

[10]王向前，洪一，鄭啟龍.分塊內存的數據分布優化[J].小型微型計算機系統，2015,4(6):350-352.

[11]唐軍，盧正新.支持內存數據庫索引緩存優化的CST樹的設計與實現 [J].計算機與數字工程，2010,38(1):173-176.

[12]劉勇，奚建清，黃東平,等.圖形處理器上內存數據庫索引T-樹的研究[J].華南理工大學學報(自然科學版)，2013,41(3):22-28.

(責任編輯:王前)

DOI:10.13877/j.cnki.cn22-1284.2016.06.022

*收稿日期：2016-03-15

基金項目：2014年度安徽省教育廳自然科學基金重點項目(KJ2014A171)；2014年度安徽省高校振興計劃優秀青年人才支持計劃(皖教秘人2014(181)號)；2014年度亳州市政府創新創業領軍人才行動計劃(亳組2014(21)號)；2015年度亳州市產業創新團隊(亳組2015(20)號)

作者簡介：張博，男，安徽界首人，副教授.

中圖分類號：TP274

文獻標志碼：A

文章編號：1008-7974(2016)03-0070-04