鍵樹又稱為數字查找樹（Digital Search Tree)或Trie樹(trie為retrieve中間4個字符)，其結構受啟發于一部大型字典的“書邊標目”。字典中標出首字母是A,B,C,....Z的單詞所在頁,再對各部分標出第二字母為A,B,C,...Z的單詞所在的頁, ....等等。
1：鍵樹的定義
鍵樹是一種特殊的查找樹，它的某個節點不是包含一個或多個關鍵字，而是只包含組成關鍵字的一部分（字符或數字），比如：如果關鍵字是數值，則節點中只包含一個數位；如果關鍵字是單詞，則節點中只包含一個字母字符。
2：鍵樹的存儲
鍵樹的存儲通常有兩種方式：
（1）雙鏈樹表示
如果以樹的孩子兄弟表示，則每個節點包含3個域。
A: symbol域: 存儲關鍵字的一個字符
B: son域: 存儲指向第一棵子樹的根的指針,葉子節點的son域指向該關鍵字記錄的指針
C: brother域: 存儲指向右兄弟的指針.
這時的鍵樹又稱為雙鏈樹.
//雙鏈樹的存儲表示
typedef struct DULNode{
char symbol; //結點字符域
struct DULNode *son, *brother; //son指向子樹根結點,brother指向右兄弟結點.
}DULNode ,*DLTree;
(2) 多重鏈表表示
如果以樹的多重鏈表表示鍵樹, 則樹的每個結點中應包含d個(d為關鍵字符的基,如:字符集由英文大寫字母構成時,則d=26+1=27)指針域，此時的鍵樹又稱為Trie樹。如果從鍵樹中某個結點到葉子結點的路徑上每個結點都只有一個孩子，則可以將該路徑上的所有結點壓縮為一個“葉子結點”，且在該葉子結點中存儲關鍵字及指向記錄的指針等信息。
以上數據結構很容易讓人聯想到電話號碼，如果關鍵字的取值為[0，9]，則很容易用來處理像電話號碼這類的數據。如果目前固定電話的長度算8位的話，那查找的的時間復雜度為常數8。
計費系統中的用戶資料在計費過程中使用非常頻繁，如果id作為關鍵字的鍵樹算法的話，將大大的提高查詢速度。
下面是它的實現代碼
鍵樹的實現代碼