键树在计费系统中的应用

我们首先看看键树是怎么回事：

键树又称为数字查找树（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作为关键字的键树算法的话，将大大的提高查询速度。

下次再具体谈谈键树算法的实现，以及在共享内存中的实现。