您所在位置：主题：[原创]快速目录树SDK开发包
freeland007
[专家分：0] 发布于 2009-12-06 09:22:00
1 概述
本文讲述有序目录树数据结构的技术特点、功能描述、应用领域以及性能参数等
内容。
有序目录树数据结构是基于有序HASH(Trie)树开发的，有关有序HASH(Trie)树可参考相关文档或者访问以下网址：
2 版权说明
1、本开发包免费，用户可用于学习、测试、商业用途，本软件没有功能上的限制和使用期限限
e-mail：freeland007@163.com
QQ: 723273055
3 有序目录树介绍
有序目录树数据结构类似文件系统中的目录系统，每个有序目录树有一个默认的
根目录节点，在根目录节点可以建立多个子目录，在子目录下还可以建立它的子
目录。每个目录节点有一个句柄保存数据, 一般情况保存一个结构体或对象的指
针，有序目录树的目录层次没有限制；每个目录下的子目录数量没有限制，每个目录下的子目录通过采用有序HASH（Trie）树建立索引。
提供以下操作有序目录树的方法：
1、在指定目录下新建子目录
2、在指定目录下删除子目录(支持递归删除)
3、在指定目录下查询子目录
支持精确查询、遍历、正向模糊匹配、反向模糊匹配
4、查询指定目录下的子目录的数量
5、清空指定目录下的子目录(支持递归删除)
6、获取指定目录的句柄值
7、设置指定目录的句柄值
8、获取指定目录的父目录节点
10、在目录树下建立多级目录
11、在目录树下删除目录(支持递归删除)
12、获取目录树下多级目录的目录句柄值
13、设置目录树下指定目录的句柄值
14、其它功能
以下介绍访问目录下子目录的功能：
1、可以通过外部提供的值在指定目录下获取到唯一子目录节点。
2、可以通过外部提供的值在指定目录下定位到符合条件的匹配规则目录节点。匹配规则表达式字符串由字符和2种通配符组成，例如以下形式的规则
表达式：
1）0755%、138%5678、%5678、%1234%
2）?234567890、12345678??、?23???789?
3）0755%56??、????1234%
通配符为%和?。
通配符%：包含零个或更多个字节的任意字符串。
通配符?：任意单字节字符。
3、可以通过外部提供的匹配模式字符串在指定目录下定位到符合条件的子目录节点。说明：本搜索方式和方式2是完全相反的方式，一般情况下可能会有多个子目录节点的目录名符合匹配模式，对于符合条件的目录节点可以指定排序方式顺序访问。
4、可以在指定目录下定位到指定目录名长度的子目录节点。
例如：
1）定位子目录名长度为10字节的所有子目录节点
2）定位子目录名长度为大于5小于10个字节的所有子目录节点
5、用整体遍历的方式访问指定目录下的的所有子目录节点，在遍历时可以指定排序方式（升序或降序）。
除了以上的访问HASH树节点方式外，还有以下功能：
1、对于返回多个子目录节点的情况可以指定排序方式（升序、降序）的方式访
问节点。例如：上面的方式3、4、5
2、对于返回多个子目录节点的情况可以指定访问的最大子目录节点数量
3、可以在查询有序目录树的回调函数中对子目录节点经行处理。
4 运行效率高
1、根据主键精确访问（插入、删除、查询、模糊匹配、遍历）节点的速度快。
1）在有 100万子目录的目录中新建或删除一个子目录需要不到1微秒，相当于100~200万次/秒新建或删除子目录操作。
2）在有 100万子目录的目录中查找一个子目录需要0.2~0.5个微秒，相当于170~300万次/秒查找操作。
3、对有序目录树其它操作的指标参考性能指标部分
4、支持超大容量目录结构
在有序目录树有庞大数量节点的情况下，仍然保持高效运行。根据主键精确
访问（新建、删除、查询、模糊匹配）节点的耗时与有序目录树中总目录数
量无关，只与目录层次有关。
5、在频繁插入、删除目录的情况下，系统仍然保持运行稳定，不会出现性能抖
动的情况。
5 功能强大
有序目录树功能强大，可以满足目前应用程序开发中对数据结构功能上的需求，
和有序HASH(Trie)树、有序HASH内存表是对目前C、C++标准库强有力的补充或部分替代功能。
具体功能可参考第6章SDK中API函数的功能介绍。
6 有序目录树SDK介绍
有序目录树以动态库的形式提供给开发人员，下面介绍常用的API。
1、HDIRTREE HdtCreateTree();
功能：生成有序目录树，返回有序目录树句柄。
2、int HdtDeleteTree(HDIRTREE hTree);
功能：删除有序目录树。
3、int HdtGetRootDir(HDIRTREE hTree);
功能：返回有序目录树的根目录节点句柄。
4、int HdtRemoveAll(HDIRTREE hTree, DIRAPI pPreDeleteFun = NULL,
void* pInputPara = NULL)
功能： 清空除根目录外的所有目录节点,可以使用回调函数处理被删除的
节点。
5、int HdtCreateDir(HDIRTREE hTree, int nLevel, char* sMultiDir[],
HANDLE hMultiValue[], bool bRecursive);
功能：在根目录下建立一级或多级目录，同时设置每级目录节点的句柄值。
6、int HdtDeleteDir(HDIRTREE hTree, int nLevel, char* sMultiDir[],
HANDLE hMultiValue[], bool bRecursive, DIRAPI pPreDeleteFun = NULL,
void* pInputPara = NULL);
功能：在根目录下删除一级或多级目录，同时返回每级目录节点的句柄值。
7、int HdtGetDir(HDIRTREE hTree, int nLevel, char* sMultiDir[],
HDIRNODE hMultiNode[]);
功能：用来获取指定路径中各级子目录的目录节点句柄。
8、int HdtGetDir(HDIRTREE hTree, int nLevel, char* sMultiDir[],
HANDLE hMultiValue[]);
功能：用来获取指定路径中各级子目录的目录节点句柄值。
9、int HdtSetDir(HDIRTREE hTree, int nLevel, char* sMultiDir[],
HANDLE hValue);
功能：用来设置指定路径中最后一级子目录的节点句柄值。
10、bool HdtCreateSubDir(HDIRNODE hDirNode, char* sDir, HANDLE hValue,
HDIRNODE& hSubDirNode);
功能：在指定的目录下创建一个子目录，并设置新建子目录的句柄值，同时返回新建子目录的目录句柄。
11、HDIRNODE HdtGetParentDir(HDIRNODE hDirNode);
功能：返回目录节点的父目录节点句柄。
12、bool HdtDeleteSubDir(HDIRNODE hDirNode, char* sDir, HANDLE& hValue,
bool bRecursive, DIRAPI pPreDeleteFun = NULL,
void* pInputPara = NULL);
功能：在指定的目录下删除一个子目录，删除成功时返回该子目录的目录句
柄值，也可以设置回调函数处理要删除的子目录节点。
13、HDIRNODE HdtSubGetDirNode(HDIRNODE hDirNode, char* sDir);
功能：根据目录名获取指定目录下某子目录的目录节点句柄
14、HANDLE HdtSubGetDirValue(HDIRNODE hDirNode, char* sDir);
功能：根据目录名获取指定目录下某子目录的目录节点句柄。
15、HANDLE HdtGetNodeValue(HDIRNODE hDirNode);
功能：根据目录节点句柄获取句柄值。
16、void HdtSetNodeValue(HDIRNODE hDirNode, HANDLE hValue);
功能：用来设置目录节点的句柄值。
17、void HdtGetLocalDirName(HDIRNODE hDirNode, char* sLocalDir);
功能：根据目录节点句柄获取对应的目录名。
18、int HdtGetSubDirCount(HDIRNODE hDirNode);
功能：返回指定目录下直接子目录的数量。
19、void HdtEmptyDir(HDIRNODE hDirNode, DIRAPI UserFun = NULL,
void* pInputPara = NULL);
功能：用来递归删除指定目录下的所有子孙目录，同时可以设置回调函数处
理要删除的子孙目录节点。
20、void HdtMoveDir(HDIRTREE hTree, int nSourLevel, char* sMultiSour[],
int nDestLevel, char* sDestSour[]);
功能：此函数用来把一个目录以及子孙目录移到另外一个目录下。
21、int HdtAccess(LPSELECTCOND pSelectCond);
功能：此函数用来访问指定目录下的子目录，通过此函数可以精确访问一个
子目录节点；也可以遍历所有子目录节点，也可以使用正向模糊匹配或者反
向模糊匹配访问符合条件的目录节点，通过用户编写的回调函数处理要访问
的目录节点。
其它功能函数：
7 有序目录树编程应用
有序目录树数据结构适用于有目录特点的应用，且对性能有极高要求的情况下。
例如：类文件系统、web URL地址处理、通讯录、权限管理等应用。
8 运行环境
1、windows 2000、windows 2003、windows XP
2、linux
3、unix（solarix、HP-UX、AIX等）
9 性能指标
9.1 测试环境
1、操作系统：windows xp professional
2、内存：1G /DDR2
3、CPU：AMD LE1100/1.9GHz
9.2 有序目录树的性能指标
测试条件：
1、有序目录的某个目录下有100万个子目录节点，目录名从
123456780000000000到123456780000999999
测试项目：
1、新建子目录
新建100万子目录，子目录名从123456780000000000到
123456780000999999，耗时1.000秒。
2、根据子目录名精确删除子目录
根据目录名删除100万子目录，子目录名从123456780000000000
到123456780000999999，耗时1.031秒。
3、根据目录名精确查询目录子节点
根据目录名精确查询100万子目录节点，目录名从123456780000000000
到123456780000999999，耗时0.562秒。
4、整体遍历所有子目录
遍历目录下的所有100万子目录，目录名从123456780000000000到
123456780000999999，耗时0.078秒。
6、清除目录所有子目录
一次清除指定目录下的所有100万子目录，目录名从123456780000000000
到123456780000999999，耗时0.094秒。
本文讲述有序目录树数据结构的技术特点、功能描述、应用领域以及性能参数等
内容。
有序目录树数据结构是基于有序HASH(Trie)树开发的，有关有序HASH(Trie)树可参考相关文档或者访问以下网址：
2 版权说明
1、本开发包免费，用户可用于学习、测试、商业用途，本软件没有功能上的限制和使用期限限
e-mail：freeland007@163.com
QQ: 723273055
3 有序目录树介绍
有序目录树数据结构类似文件系统中的目录系统，每个有序目录树有一个默认的
根目录节点，在根目录节点可以建立多个子目录，在子目录下还可以建立它的子
目录。每个目录节点有一个句柄保存数据, 一般情况保存一个结构体或对象的指
针，有序目录树的目录层次没有限制；每个目录下的子目录数量没有限制，每个目录下的子目录通过采用有序HASH（Trie）树建立索引。
提供以下操作有序目录树的方法：
1、在指定目录下新建子目录
2、在指定目录下删除子目录(支持递归删除)
3、在指定目录下查询子目录
支持精确查询、遍历、正向模糊匹配、反向模糊匹配
4、查询指定目录下的子目录的数量
5、清空指定目录下的子目录(支持递归删除)
6、获取指定目录的句柄值
7、设置指定目录的句柄值
8、获取指定目录的父目录节点
10、在目录树下建立多级目录
11、在目录树下删除目录(支持递归删除)
12、获取目录树下多级目录的目录句柄值
13、设置目录树下指定目录的句柄值
14、其它功能
以下介绍访问目录下子目录的功能：
1、可以通过外部提供的值在指定目录下获取到唯一子目录节点。
2、可以通过外部提供的值在指定目录下定位到符合条件的匹配规则目录节点。匹配规则表达式字符串由字符和2种通配符组成，例如以下形式的规则
表达式：
1）0755%、138%5678、%5678、%1234%
2）?234567890、12345678??、?23???789?
3）0755%56??、????1234%
通配符为%和?。
通配符%：包含零个或更多个字节的任意字符串。
通配符?：任意单字节字符。
3、可以通过外部提供的匹配模式字符串在指定目录下定位到符合条件的子目录节点。说明：本搜索方式和方式2是完全相反的方式，一般情况下可能会有多个子目录节点的目录名符合匹配模式，对于符合条件的目录节点可以指定排序方式顺序访问。
4、可以在指定目录下定位到指定目录名长度的子目录节点。
例如：
1）定位子目录名长度为10字节的所有子目录节点
2）定位子目录名长度为大于5小于10个字节的所有子目录节点
5、用整体遍历的方式访问指定目录下的的所有子目录节点，在遍历时可以指定排序方式（升序或降序）。
除了以上的访问HASH树节点方式外，还有以下功能：
1、对于返回多个子目录节点的情况可以指定排序方式（升序、降序）的方式访
问节点。例如：上面的方式3、4、5
2、对于返回多个子目录节点的情况可以指定访问的最大子目录节点数量
3、可以在查询有序目录树的回调函数中对子目录节点经行处理。
4 运行效率高
1、根据主键精确访问（插入、删除、查询、模糊匹配、遍历）节点的速度快。
1）在有 100万子目录的目录中新建或删除一个子目录需要不到1微秒，相当于100~200万次/秒新建或删除子目录操作。
2）在有 100万子目录的目录中查找一个子目录需要0.2~0.5个微秒，相当于170~300万次/秒查找操作。
3、对有序目录树其它操作的指标参考性能指标部分
4、支持超大容量目录结构
在有序目录树有庞大数量节点的情况下，仍然保持高效运行。根据主键精确
访问（新建、删除、查询、模糊匹配）节点的耗时与有序目录树中总目录数
量无关，只与目录层次有关。
5、在频繁插入、删除目录的情况下，系统仍然保持运行稳定，不会出现性能抖
动的情况。
5 功能强大
有序目录树功能强大，可以满足目前应用程序开发中对数据结构功能上的需求，
和有序HASH(Trie)树、有序HASH内存表是对目前C、C++标准库强有力的补充或部分替代功能。
具体功能可参考第6章SDK中API函数的功能介绍。
6 有序目录树SDK介绍
有序目录树以动态库的形式提供给开发人员，下面介绍常用的API。
1、HDIRTREE HdtCreateTree();
功能：生成有序目录树，返回有序目录树句柄。
2、int HdtDeleteTree(HDIRTREE hTree);
功能：删除有序目录树。
3、int HdtGetRootDir(HDIRTREE hTree);
功能：返回有序目录树的根目录节点句柄。
4、int HdtRemoveAll(HDIRTREE hTree, DIRAPI pPreDeleteFun = NULL,
void* pInputPara = NULL)
功能： 清空除根目录外的所有目录节点,可以使用回调函数处理被删除的
节点。
5、int HdtCreateDir(HDIRTREE hTree, int nLevel, char* sMultiDir[],
HANDLE hMultiValue[], bool bRecursive);
功能：在根目录下建立一级或多级目录，同时设置每级目录节点的句柄值。
6、int HdtDeleteDir(HDIRTREE hTree, int nLevel, char* sMultiDir[],
HANDLE hMultiValue[], bool bRecursive, DIRAPI pPreDeleteFun = NULL,
void* pInputPara = NULL);
功能：在根目录下删除一级或多级目录，同时返回每级目录节点的句柄值。
7、int HdtGetDir(HDIRTREE hTree, int nLevel, char* sMultiDir[],
HDIRNODE hMultiNode[]);
功能：用来获取指定路径中各级子目录的目录节点句柄。
8、int HdtGetDir(HDIRTREE hTree, int nLevel, char* sMultiDir[],
HANDLE hMultiValue[]);
功能：用来获取指定路径中各级子目录的目录节点句柄值。
9、int HdtSetDir(HDIRTREE hTree, int nLevel, char* sMultiDir[],
HANDLE hValue);
功能：用来设置指定路径中最后一级子目录的节点句柄值。
10、bool HdtCreateSubDir(HDIRNODE hDirNode, char* sDir, HANDLE hValue,
HDIRNODE& hSubDirNode);
功能：在指定的目录下创建一个子目录，并设置新建子目录的句柄值，同时返回新建子目录的目录句柄。
11、HDIRNODE HdtGetParentDir(HDIRNODE hDirNode);
功能：返回目录节点的父目录节点句柄。
12、bool HdtDeleteSubDir(HDIRNODE hDirNode, char* sDir, HANDLE& hValue,
bool bRecursive, DIRAPI pPreDeleteFun = NULL,
void* pInputPara = NULL);
功能：在指定的目录下删除一个子目录，删除成功时返回该子目录的目录句
柄值，也可以设置回调函数处理要删除的子目录节点。
13、HDIRNODE HdtSubGetDirNode(HDIRNODE hDirNode, char* sDir);
功能：根据目录名获取指定目录下某子目录的目录节点句柄
14、HANDLE HdtSubGetDirValue(HDIRNODE hDirNode, char* sDir);
功能：根据目录名获取指定目录下某子目录的目录节点句柄。
15、HANDLE HdtGetNodeValue(HDIRNODE hDirNode);
功能：根据目录节点句柄获取句柄值。
16、void HdtSetNodeValue(HDIRNODE hDirNode, HANDLE hValue);
功能：用来设置目录节点的句柄值。
17、void HdtGetLocalDirName(HDIRNODE hDirNode, char* sLocalDir);
功能：根据目录节点句柄获取对应的目录名。
18、int HdtGetSubDirCount(HDIRNODE hDirNode);
功能：返回指定目录下直接子目录的数量。
19、void HdtEmptyDir(HDIRNODE hDirNode, DIRAPI UserFun = NULL,
void* pInputPara = NULL);
功能：用来递归删除指定目录下的所有子孙目录，同时可以设置回调函数处
理要删除的子孙目录节点。
20、void HdtMoveDir(HDIRTREE hTree, int nSourLevel, char* sMultiSour[],
int nDestLevel, char* sDestSour[]);
功能：此函数用来把一个目录以及子孙目录移到另外一个目录下。
21、int HdtAccess(LPSELECTCOND pSelectCond);
功能：此函数用来访问指定目录下的子目录，通过此函数可以精确访问一个
子目录节点；也可以遍历所有子目录节点，也可以使用正向模糊匹配或者反
向模糊匹配访问符合条件的目录节点，通过用户编写的回调函数处理要访问
的目录节点。
其它功能函数：
7 有序目录树编程应用
有序目录树数据结构适用于有目录特点的应用，且对性能有极高要求的情况下。
例如：类文件系统、web URL地址处理、通讯录、权限管理等应用。
8 运行环境
1、windows 2000、windows 2003、windows XP
2、linux
3、unix（solarix、HP-UX、AIX等）
9 性能指标
9.1 测试环境
1、操作系统：windows xp professional
2、内存：1G /DDR2
3、CPU：AMD LE1100/1.9GHz
9.2 有序目录树的性能指标
测试条件：
1、有序目录的某个目录下有100万个子目录节点，目录名从
123456780000000000到123456780000999999
测试项目：
1、新建子目录
新建100万子目录，子目录名从123456780000000000到
123456780000999999，耗时1.000秒。
2、根据子目录名精确删除子目录
根据目录名删除100万子目录，子目录名从123456780000000000
到123456780000999999，耗时1.031秒。
3、根据目录名精确查询目录子节点
根据目录名精确查询100万子目录节点，目录名从123456780000000000
到123456780000999999，耗时0.562秒。
4、整体遍历所有子目录
遍历目录下的所有100万子目录，目录名从123456780000000000到
123456780000999999，耗时0.078秒。
6、清除目录所有子目录
一次清除指定目录下的所有100万子目录，目录名从123456780000000000
到123456780000999999，耗时0.094秒。