[發明專利]一種基于分類特性和平衡二叉樹的數據存儲、查詢方法

有效

• 申請號: 201110403732.1
• 申請日: 2011-12-07
• 公開（公告）號: CN102521334A
• 公開（公告）日: 2012-06-27
• 發明（設計）人: 韓一石;孫運龍;王建華;黃明政
• 申請（專利權）人: 廣東工業大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 廣州粵高專利商標代理有限公司 44102
• 代理人: 林麗明

技術領域

?本發明屬于物聯網通信領域中大數據量的存儲、查詢方法領域，特別是一種基于分類特性和平衡二叉樹的數據存儲、查詢方法。

背景技術

通信技術中，傳統的數據查詢方法包括靜態查找方法和動態查找方法。靜態查找方法包括順序查找、二分查找、索引查找；動態查找方法包括二叉搜索樹、B-樹、哈希（Hash）查找法、鍵樹等。

順序查找中假設對于n個記錄的查找表，其查找成功時的平均查找長度為ASL(Average?Search?Length),ASL=???????????????????????????????????????????????=，且比較次數為=n-i+1,查找到的概率為P_i=則ASL=nP₁+(n-1)P₂+……+2P_n-1+P_n?==，則其算法時間復雜度為O(n)。

二分查找法，對于一般情況下假設有序表的長度為n=2^h-1，在每個記錄的查找概率都相等的情況下，即P_i=，可得其ASL=log₂（n+1）-1,當n值大于50，其ASL可近似為log₂（n+1）-1，故其算法的時間復雜度為O（log_2?n）。

索引查找法，是介于順序查找和二分查找之間的一種方法，又可稱為“分塊有序”查找法，即將順序表進行分塊，按前一塊的最大關鍵字小于后一塊中的最小關鍵字，內部關鍵字不一定有序，假設索引表的長度為b，順序表的長度為n,則其ASL=ASL_Index(b)+ASL_Seq(n/b)≈log₂（b+1）-1+(n/b+1)/2，故其算法的時間復雜度為（O(log₂?n)+?O(n)）/2。

二叉搜索樹查找法，對于有n個節點的二叉搜索樹，在平衡情況下其樹高為log_2?n，則其每次查找的時間代價為O(log₂?n),而在極端情況下如其n個節點成一條直鏈表形則樹高為n，對于查找到每個節點的時間代價為O(n),又知其是插入節點的遍歷時間代價均為O(n),則其總的算法的時間復雜度最佳為O(n·log₂n)，最差為O（n²）。

B-樹是一種平衡的多路查找樹，對結點內的關鍵字（有序）序列進行二分查找，如果命中則結束，否則進入查詢關鍵字所屬范圍的兒子結點；重復，直到所對應的兒子指針為空，或已經是葉子結點，故其算法的時間復雜度為O（log_2?n）。

哈希（Hash）查找法由于自身的散列性使得其在應用于分類查找中查找效率不高。

鍵樹一般用于特殊查找，從根到葉子節點的一條“路徑”對應為一個關鍵字，不適合通用的大數據量的查詢。

當前物聯網通信領域中,通信數據技術的發展，越來越趨向于高實時性和巨型化。傳統的靜態查找方法如：順序查找、二分查找、索引查找，很難滿足當前大數據量處理對實時性的要求。而對于動態查找（DST），如二叉搜索樹，B-樹，哈希（Hash）查找法，鍵樹等，其時間復雜度遠遠高于靜態查找。

發明內容

本發明針對以上不足，提供一種針對大量數據的速度快、能耗低、占用內存少、算法簡單的基于分類特性和平衡二叉樹的數據存儲、查詢方法。

本發明提供一種基于分類特性和平衡二叉樹（AVL樹）的數據存儲、查詢方法，實現方法包括以下步驟：

1.1?構建AVL樹，創建結點；

1.2?按照遍歷規則，動態地將數據信息存儲到相應結點；

1.3?輸入需要查詢的信息，動態遍歷AVL樹，直到找到所需的數據信息或遍歷完AVL樹返回查找失敗。

所述AVL樹為有序的，AVL樹按照順序（中序、前序、后序）遍歷規則，動態地將數據信息存儲到相應結點。

???所述結點數據儲存結構按實現的語言分為C語言和C++語言。

本發明的具體實現方法如下：?