您所在位置：主题：[原创]推荐功能强大的有序HASH(Trie)树SDK
freeland007
[专家分：0] 发布于 2009-10-24 15:15:00
1 概述
本文讲述普遍应用在程序开发中快速HASH树数据结构的技术特点、功能描述、应用领域以及性能参数和其他类库的对比。
目前实时处理系统对内存数据结构的普遍有以下要求：
1、功能要求
功能要强大且完备，满足业务功能的需求。
2、性能要求
要能满足实时处理系统对处理速度的需求，同时能长期运行且性能保持稳定
3、系统容量大
要能保持超大规模数据，且在海量数据情况下还能保持优异的性能。
快速HASH树是目前速度最快功能最强大的数据结构，可以满足电信以及其他行业软件开发对数据结构的要求。
2 版权说明
作者联系方式
e-mail：freeland007@163.com
QQ: 723273055
3 单级HASH树介绍
Hash树数据结构是根据键值插入到树中形成节点，节点保存用户数据，一般情况保存一个结构体或对象的指针，树中的各个
节点再插入后即排序，形成有序的节点多叉树结构。
可以通过以下方式访问树节点以及用户数据
1、可以通过外部提供的值在HASH树中快速定位到唯一树中的节点。
2、可以通过外部提供的值在HASH树中快速定位到符合条件的匹配规则节点。
匹配规则表达式字符串由字符和2种通配符组成，例如以下形式的规则表达式：
1）0755%、138%5678、%5678、%1234%
2）?234567890、12345678??、?23???789?
3）0755%56??、????1234%
通配符为%和?。
通配符%：包含零个或更多个字节的任意字符串。
通配符?：任意单字节字符。
3、 可以通过外部提供的匹配模式字符串在HASH树中定位到符合条件的节点。
说明：本搜索方式和方式2是完全相反的方式，一般情况下可能会有多个节点的键值符合匹配模式，对于符合条件的节
点可以可以指定排序方式顺序访问。
4、 可以在HASH树中定位指定键值长度的节点。
例如：
1）定位键值长度为10字节的所有节点
2）定位键值长度为大于5小于10个字节的所有节点
5、 可以在HASH树中定位键值在某个区域的节点。
例如：
1）返回大于“1234000000”的节点
2）返回小于“1235000000”的节点
3）返回大于“1234000000”并且小于“1235000000” 的节点
6、 用整体遍历的方式访问HASH树中的节点，再遍历时可以指定排序方式，可以按主键的升序或降序顺序遍历
7、 根据指定排序（升、降）方式获取头（尾）节点
8、 根据指定排序（升、降）方式删除头（尾）节点，同时获取头（尾）节点的用户数据（指针）
除了以上的访问HASH树节点方式外，还有以下功能：
1、对于返回多个节点的情况可以指定排序方式（升序、降序）的方式访问节点
例如：上面的方式3、4、5、6
2、对于返回多个节点的情况可以指定访问的最大节点数量
3、 可以再查询HASH树的回调函数中对节点数据经行再处理。
4、根据节点可以获取该节点的用户数据（指针）以及该节点的键值。
4 多级HASH树介绍
如果HASH树中的节点保存的数据是指向另外一个HASH树的指针，如此递归形成一棵多级HASH树，最后一棵HASH树保存用户
数据，一般为结构体或对象的指针。
用户通过插入多个键值插入到多级树的各个HASH树中，也可以通过多个键值删除多级树中指定的节点。多级HASH树采用以
下方式遍历用户数据节点。
从顶层HASH树开始向底层树遍历，对每层次的HASH树可以指定访问树节点的访问方式（参考单级树的访问方式），一致到
最底层数的叶子节点。
开发包访问多级树的API和访问单级树是统一的。
5 运行效率高
1、根据主键精确访问（插入、删除、查询、模式匹配）节点的速度快。
1）在有 1000万节点的HASH树中插入或插入一个节点需要1~2个微秒，相当于50~100万次/秒插入或删除节点操作。
2）在有 1000万节点的HASH树中查找一个节点需要0.3~0.6个微秒，相当于130~300万次/秒查找操作。
2、在按指定排序的情况下获取（删除）头（尾）节点的速度快。
在有 1000万节点的HASH树中删除入一个头（尾）节点需要2~3个微秒，相当于30~50万次/秒删除头（尾）节点操作。
3、对HASH其它操作的指标参考性能指标部分
4、支持超大容量节点
在HASH树有庞大数量节点的情况下，仍然保持高效运行。根据主键精确访问（插入、删除、查询、模式匹配）节点的
耗时与HASH树中节点数量无关，只与键值的长度有关。
5、在频繁插入、删除节点的情况下，系统仍然保持运行稳定，不会出现性能抖动的情况。
6 功能强大
单（多）级HASH树功能强大，可以满足目前应用程序开发中对数据结构功能上的需求，是对目前C、C++标准库强有力的补充
或部分替代功能。
以下是HASH树和MFC中CMAP类的功能比较。
序号 比较功能 快速HASH树 CMAP(MFC)
1 精确查询节点 支持 支持
2 精确删除节点 支持 支持
3 根据匹配模式匹配节点 支持 不支持
4 根据字符串匹配规则表达式节点 支持 不支持
5 查询指定键值长度的节点 支持 不支持
6 查询指定键值范围的节点 支持 不支持
7 支持键值有序（升、降）遍历 支持 不支持
8 支持头（尾）节点操作 支持 不支持
9 根据节点位置获取键值 支持 不支持
10 根据节点位置获取用户指针数据 支持 不支持
11 根据节点位置删除树节点 支持 不支持
12 支持多级（树、MAP）方式 支持 不支持
13 多级(树、表)的功能 支持 N/A
14 其它功能 支持 不支持
具体功能可参考第7章SDK中API函数的功能介绍。
7 快速HASH树SDK介绍
快速HASH树以动态库的形式提供给开发人员，下面介绍常用的API。
1、HANDLE HTreeCreate(LPHTREEDESC pTreeDesc);
功能：生成单（多）级HASH树
2、void HTreeDrop(HANDLE hTree);
功能：删除单（多）级HASH树。
3、int HTreeGetCount(HANDLE hTree);
功能：获取HASH树中节点的数量。
4、int HTreeAddKey(HANDLE hTree, char* sMultiKey[], HANDLE hValue);
功能：根据键值插入一个节点到单（多）级HASH树中。
5、HANDLE HTreeRemoveKey(HANDLE hTree, char* sMultiKey[]);
功能：根据键值在单（多）级HASH树中精确删除相应的节点。
6、HANDLE HTreeGetKeyValue(HANDLE hTree, char* sMultiKey[]);
功能：根据键值在单（多）级HASH树中精确查找相应的一个节点。
7、HANDLE HTreeGetMatchValue(HANDLE hTree, char* sMultiKey[]);
功能：根据外部提供的字符串在单（多）级HASH树中匹配出最精确的规则表达式。
8、HANDLE HTreeGetHead(HANDLE hTree, bool bAsc[]);
功能：在指定树的各级主键排序的情况下，获取头结点的值
9、HANDLE HTreeGetTail(HANDLE hTree, bool bAsc[]);
功能：在指定树的各级主键排序的情况下，获取尾结点的值
10、bool HTreeGetHeadPosition(HANDLE hTree, bool bAsc[], HANDLE hNodeSet[]);
功能：在指定树的各级主键排序的情况下，获取各级树在指定排序情况下头结点，并把各级头结点保存到节点数组中。
11、bool HTreeGetTailPosition(HANDLE hTree, bool bAsc[], HANDLE hNodeSet[]);
功能：在指定树的各级主键排序的情况下，获取各级树在指定排序情况下尾结点，并把各级尾结点保存到节点数组中。
12、HANDLE HTreeRemoveHead(HANDLE hTree, bool bAsc[]);
功能：在指定树的各级主键排序的情况下，删除头节点，并返回头节点句柄值。
13、HANDLE HTreeRemoveTail(HANDLE hTree, bool bAsc[]);
功能：在指定树的各级主键排序的情况下，删除尾节点，并返回尾节点句柄值。
14、 HANDLE HTreeRemoveAt(HANDLE hTree, HANDLE hNodeSet[]);
功能：根据各级树种的节点，删除指定叶子节点
15、void HTreeGetNodeKey(HANDLE hTree, HANDLE hNode, char* sKey);
功能：根据节点获取节点对应的键值
16、HANDLE HTreeGetNodeValue(HANDLE hTree, HANDLE hNode)
功能：根据节点获取节点对应的句柄值
17、void HTreeRemoveAll(HANDLE hTree);
功能：一次清除HASH树中的所有节点
18、 int HTreeSelect(LPSELECTCOND pSelectCond);
功能：此函数用来根据指定的条件访问单（多）级HASH树中的节点，此函数功能强大，可以指定访问各级子树的访问方
式，对于满足访问条件的节点可以由用户编写的回调函数处理。
19、void HTreeGetCurrentPosition(LPSELECTCOND pSelectCond, HANDLE hNodeSet[]);
功能：此函数在执行HTreeSelect中的回调函数中使用，用来获取当前各级子树节点，并保存在节点数组中。
20、HANDLE HTreeGetCurrentValue(LPSELECTCOND pSelectCond);
功能：此函数在执行HTreeSelect中的回调函数中使用，用来获取当前节点的句柄值。
其它功能函数：略
8 HASH树行业应用
快速单（多）级HASH树已经广泛应用到可应用于多个行业软件开发领域，特别适合于超大规模信息的实时处理的情况。
8.1 电信实时处理系统
1、电话（手机）号码路由
2、电话号码区号匹配
3、手机号码归属地查询
4、手机短信违禁词过滤
5、电话（手机）号码黑白名单查询过滤
6、号码路由
7、订购关系处理
8、实时鉴权系统
9、实时计费系统
8.2 互联网应用
1、高效数据库缓存服务器
2、产品编码查询
3、身份查询
4、网络游戏服务器
5、域名系统
6、路由查询
7、邮件系统
8.3 实时处理系统
1、实时监控系统
2、数据采集系统
3、跟踪系统
8.4 内存数据库系统
内存数据库的其中之一的核心数据结构式内存数据库表，而索引时其中最重要部分，内存数据库的索引可选择HASH树可
作为内存数据库的索引数据结构。
9 运行环境
1、windows 2000、windows 2003、windows XP
2、linux
3、unix（solarix、HP-UX、AIX等）
10 性能指标
10.1 测试环境
1、 操作系统：windows xp professional
2、 内存：1G /DDR2
3、 CPU：AMD LE1100/1.9GHz
10.2 单级HASH树的性能指标
测试条件：
1、单级HASH树
2、树中有100万节点，节点的键值从123456780000000000到123456780000999999
测试项目：
1、插入节点
插入100万节点到HASH树中，节点的键值从123456780000000000到123456780000999999，耗时2.140秒。
2、根据键值精确删除节点
从HASH树中根据键值删除100万节点，节点的键值从123456780000000000到123456780000999999，耗时2.172秒。
3、根据键值精确查询节点
根据键值从HASH树中精确查询100万节点，节点的键值从123456780000000000到123456780000999999，耗时0.610秒。
4、整体遍历
遍历HASH树中的100万节点，节点的键值从123456780000000000到123456780000999999，耗时0.062秒。
5、删除头（尾）节点
用删除头（尾）节点的方式删除HASH树中的100万节点，节点的键值从123456780000000000到123456780000999999，耗
时2.600秒。
6、清除HASH树中所有节点
一次清除HASH树中的所有100万节点，节点的键值从123456780000000000到123456780000999999，耗时0.100秒。
本文讲述普遍应用在程序开发中快速HASH树数据结构的技术特点、功能描述、应用领域以及性能参数和其他类库的对比。
目前实时处理系统对内存数据结构的普遍有以下要求：
1、功能要求
功能要强大且完备，满足业务功能的需求。
2、性能要求
要能满足实时处理系统对处理速度的需求，同时能长期运行且性能保持稳定
3、系统容量大
要能保持超大规模数据，且在海量数据情况下还能保持优异的性能。
快速HASH树是目前速度最快功能最强大的数据结构，可以满足电信以及其他行业软件开发对数据结构的要求。
2 版权说明
作者联系方式
e-mail：freeland007@163.com
QQ: 723273055
3 单级HASH树介绍
Hash树数据结构是根据键值插入到树中形成节点，节点保存用户数据，一般情况保存一个结构体或对象的指针，树中的各个
节点再插入后即排序，形成有序的节点多叉树结构。
可以通过以下方式访问树节点以及用户数据
1、可以通过外部提供的值在HASH树中快速定位到唯一树中的节点。
2、可以通过外部提供的值在HASH树中快速定位到符合条件的匹配规则节点。
匹配规则表达式字符串由字符和2种通配符组成，例如以下形式的规则表达式：
1）0755%、138%5678、%5678、%1234%
2）?234567890、12345678??、?23???789?
3）0755%56??、????1234%
通配符为%和?。
通配符%：包含零个或更多个字节的任意字符串。
通配符?：任意单字节字符。
3、 可以通过外部提供的匹配模式字符串在HASH树中定位到符合条件的节点。
说明：本搜索方式和方式2是完全相反的方式，一般情况下可能会有多个节点的键值符合匹配模式，对于符合条件的节
点可以可以指定排序方式顺序访问。
4、 可以在HASH树中定位指定键值长度的节点。
例如：
1）定位键值长度为10字节的所有节点
2）定位键值长度为大于5小于10个字节的所有节点
5、 可以在HASH树中定位键值在某个区域的节点。
例如：
1）返回大于“1234000000”的节点
2）返回小于“1235000000”的节点
3）返回大于“1234000000”并且小于“1235000000” 的节点
6、 用整体遍历的方式访问HASH树中的节点，再遍历时可以指定排序方式，可以按主键的升序或降序顺序遍历
7、 根据指定排序（升、降）方式获取头（尾）节点
8、 根据指定排序（升、降）方式删除头（尾）节点，同时获取头（尾）节点的用户数据（指针）
除了以上的访问HASH树节点方式外，还有以下功能：
1、对于返回多个节点的情况可以指定排序方式（升序、降序）的方式访问节点
例如：上面的方式3、4、5、6
2、对于返回多个节点的情况可以指定访问的最大节点数量
3、 可以再查询HASH树的回调函数中对节点数据经行再处理。
4、根据节点可以获取该节点的用户数据（指针）以及该节点的键值。
4 多级HASH树介绍
如果HASH树中的节点保存的数据是指向另外一个HASH树的指针，如此递归形成一棵多级HASH树，最后一棵HASH树保存用户
数据，一般为结构体或对象的指针。
用户通过插入多个键值插入到多级树的各个HASH树中，也可以通过多个键值删除多级树中指定的节点。多级HASH树采用以
下方式遍历用户数据节点。
从顶层HASH树开始向底层树遍历，对每层次的HASH树可以指定访问树节点的访问方式（参考单级树的访问方式），一致到
最底层数的叶子节点。
开发包访问多级树的API和访问单级树是统一的。
5 运行效率高
1、根据主键精确访问（插入、删除、查询、模式匹配）节点的速度快。
1）在有 1000万节点的HASH树中插入或插入一个节点需要1~2个微秒，相当于50~100万次/秒插入或删除节点操作。
2）在有 1000万节点的HASH树中查找一个节点需要0.3~0.6个微秒，相当于130~300万次/秒查找操作。
2、在按指定排序的情况下获取（删除）头（尾）节点的速度快。
在有 1000万节点的HASH树中删除入一个头（尾）节点需要2~3个微秒，相当于30~50万次/秒删除头（尾）节点操作。
3、对HASH其它操作的指标参考性能指标部分
4、支持超大容量节点
在HASH树有庞大数量节点的情况下，仍然保持高效运行。根据主键精确访问（插入、删除、查询、模式匹配）节点的
耗时与HASH树中节点数量无关，只与键值的长度有关。
5、在频繁插入、删除节点的情况下，系统仍然保持运行稳定，不会出现性能抖动的情况。
6 功能强大
单（多）级HASH树功能强大，可以满足目前应用程序开发中对数据结构功能上的需求，是对目前C、C++标准库强有力的补充
或部分替代功能。
以下是HASH树和MFC中CMAP类的功能比较。
序号 比较功能 快速HASH树 CMAP(MFC)
1 精确查询节点 支持 支持
2 精确删除节点 支持 支持
3 根据匹配模式匹配节点 支持 不支持
4 根据字符串匹配规则表达式节点 支持 不支持
5 查询指定键值长度的节点 支持 不支持
6 查询指定键值范围的节点 支持 不支持
7 支持键值有序（升、降）遍历 支持 不支持
8 支持头（尾）节点操作 支持 不支持
9 根据节点位置获取键值 支持 不支持
10 根据节点位置获取用户指针数据 支持 不支持
11 根据节点位置删除树节点 支持 不支持
12 支持多级（树、MAP）方式 支持 不支持
13 多级(树、表)的功能 支持 N/A
14 其它功能 支持 不支持
具体功能可参考第7章SDK中API函数的功能介绍。
7 快速HASH树SDK介绍
快速HASH树以动态库的形式提供给开发人员，下面介绍常用的API。
1、HANDLE HTreeCreate(LPHTREEDESC pTreeDesc);
功能：生成单（多）级HASH树
2、void HTreeDrop(HANDLE hTree);
功能：删除单（多）级HASH树。
3、int HTreeGetCount(HANDLE hTree);
功能：获取HASH树中节点的数量。
4、int HTreeAddKey(HANDLE hTree, char* sMultiKey[], HANDLE hValue);
功能：根据键值插入一个节点到单（多）级HASH树中。
5、HANDLE HTreeRemoveKey(HANDLE hTree, char* sMultiKey[]);
功能：根据键值在单（多）级HASH树中精确删除相应的节点。
6、HANDLE HTreeGetKeyValue(HANDLE hTree, char* sMultiKey[]);
功能：根据键值在单（多）级HASH树中精确查找相应的一个节点。
7、HANDLE HTreeGetMatchValue(HANDLE hTree, char* sMultiKey[]);
功能：根据外部提供的字符串在单（多）级HASH树中匹配出最精确的规则表达式。
8、HANDLE HTreeGetHead(HANDLE hTree, bool bAsc[]);
功能：在指定树的各级主键排序的情况下，获取头结点的值
9、HANDLE HTreeGetTail(HANDLE hTree, bool bAsc[]);
功能：在指定树的各级主键排序的情况下，获取尾结点的值
10、bool HTreeGetHeadPosition(HANDLE hTree, bool bAsc[], HANDLE hNodeSet[]);
功能：在指定树的各级主键排序的情况下，获取各级树在指定排序情况下头结点，并把各级头结点保存到节点数组中。
11、bool HTreeGetTailPosition(HANDLE hTree, bool bAsc[], HANDLE hNodeSet[]);
功能：在指定树的各级主键排序的情况下，获取各级树在指定排序情况下尾结点，并把各级尾结点保存到节点数组中。
12、HANDLE HTreeRemoveHead(HANDLE hTree, bool bAsc[]);
功能：在指定树的各级主键排序的情况下，删除头节点，并返回头节点句柄值。
13、HANDLE HTreeRemoveTail(HANDLE hTree, bool bAsc[]);
功能：在指定树的各级主键排序的情况下，删除尾节点，并返回尾节点句柄值。
14、 HANDLE HTreeRemoveAt(HANDLE hTree, HANDLE hNodeSet[]);
功能：根据各级树种的节点，删除指定叶子节点
15、void HTreeGetNodeKey(HANDLE hTree, HANDLE hNode, char* sKey);
功能：根据节点获取节点对应的键值
16、HANDLE HTreeGetNodeValue(HANDLE hTree, HANDLE hNode)
功能：根据节点获取节点对应的句柄值
17、void HTreeRemoveAll(HANDLE hTree);
功能：一次清除HASH树中的所有节点
18、 int HTreeSelect(LPSELECTCOND pSelectCond);
功能：此函数用来根据指定的条件访问单（多）级HASH树中的节点，此函数功能强大，可以指定访问各级子树的访问方
式，对于满足访问条件的节点可以由用户编写的回调函数处理。
19、void HTreeGetCurrentPosition(LPSELECTCOND pSelectCond, HANDLE hNodeSet[]);
功能：此函数在执行HTreeSelect中的回调函数中使用，用来获取当前各级子树节点，并保存在节点数组中。
20、HANDLE HTreeGetCurrentValue(LPSELECTCOND pSelectCond);
功能：此函数在执行HTreeSelect中的回调函数中使用，用来获取当前节点的句柄值。
其它功能函数：略
8 HASH树行业应用
快速单（多）级HASH树已经广泛应用到可应用于多个行业软件开发领域，特别适合于超大规模信息的实时处理的情况。
8.1 电信实时处理系统
1、电话（手机）号码路由
2、电话号码区号匹配
3、手机号码归属地查询
4、手机短信违禁词过滤
5、电话（手机）号码黑白名单查询过滤
6、号码路由
7、订购关系处理
8、实时鉴权系统
9、实时计费系统
8.2 互联网应用
1、高效数据库缓存服务器
2、产品编码查询
3、身份查询
4、网络游戏服务器
5、域名系统
6、路由查询
7、邮件系统
8.3 实时处理系统
1、实时监控系统
2、数据采集系统
3、跟踪系统
8.4 内存数据库系统
内存数据库的其中之一的核心数据结构式内存数据库表，而索引时其中最重要部分，内存数据库的索引可选择HASH树可
作为内存数据库的索引数据结构。
9 运行环境
1、windows 2000、windows 2003、windows XP
2、linux
3、unix（solarix、HP-UX、AIX等）
10 性能指标
10.1 测试环境
1、 操作系统：windows xp professional
2、 内存：1G /DDR2
3、 CPU：AMD LE1100/1.9GHz
10.2 单级HASH树的性能指标
测试条件：
1、单级HASH树
2、树中有100万节点，节点的键值从123456780000000000到123456780000999999
测试项目：
1、插入节点
插入100万节点到HASH树中，节点的键值从123456780000000000到123456780000999999，耗时2.140秒。
2、根据键值精确删除节点
从HASH树中根据键值删除100万节点，节点的键值从123456780000000000到123456780000999999，耗时2.172秒。
3、根据键值精确查询节点
根据键值从HASH树中精确查询100万节点，节点的键值从123456780000000000到123456780000999999，耗时0.610秒。
4、整体遍历
遍历HASH树中的100万节点，节点的键值从123456780000000000到123456780000999999，耗时0.062秒。
5、删除头（尾）节点
用删除头（尾）节点的方式删除HASH树中的100万节点，节点的键值从123456780000000000到123456780000999999，耗
时2.600秒。
6、清除HASH树中所有节点
一次清除HASH树中的所有100万节点，节点的键值从123456780000000000到123456780000999999，耗时0.100秒。