一种基于目录树的分类数据存储及分类目录查询方法

摘要

公开了一种基于目录树的分类数据存储方法，所述目录树上的每个节点至少包括孩子节点指针、兄弟节点指针以及数据指针；包括：建立所述目录树的根节点，令该根节点的兄弟节点指针为空，数据指针为空，并建立一个新的节点，令所述根节点的孩子节点指针指向所建立的新节点，将所述新节点对应于分类数据的一个一级分类目录；利用递归算法分别建立与所述分类数据的各级所有分类目录一一对映的节点，可以有效地节省内存空间，增加内存资源的使用效率，同时简化分类数据的存储以及分类目录的移动、增加以及删除操作。本发明还公开了一种基于目录树的分类目录查询方法，可以快速查找到所要查询的分类目录，获得所需的分类数据。

说明书

技术领域

本发明涉及到分类数据的管理技术，特别涉及到一种基于目录树的分类数据存储及分类目录查询方法。

背景技术

随着目前数据信息的爆炸性增长以及计算机应用领域的不断扩大，计算机已经成为人们生活中不可或缺的数据管理工具，无论是数据采集、处理、存储以及检索等等操作均离不开计算机，因此，如何有效、快速地存储数据以及如何快速地检索出所需要的数据已成为当前数据管理所要解决的主要问题。

目前对于分类数据通常可以采用树状结构来进行存储，存储这些分类目录的树状结构又称为目录树。使用目录树存储分类数据的方法包括：首先建立一个根节点，该根节点包含至少一个一级子节点，所述一级子节点的数量根据所述分类数据经过一次分类以后得到的一级分类目录的个数而定，令每个子节点对应一个一级分类目录，记录该一级分类目录的名称或标识等信息。其中，每个一级子节点还可以进一步包含至少一个二级子节点，相应地，每个二级子节点将对应于其父节点所对应一级分类目录所包含的数据经过分类后得到的二级分类目录，记录该二级分类目录的名称等信息。如此循环下去，得到若干个n级子节点(在这里所述的n为自然数)，这些n级子节点所对应的n级分类目录将不能够再进一步分类了，此时，可以将这些n级子节点称为叶子节点，这些叶子节点除了要记录所对应n级分类目录的名称或标识之外，还需要进一步存储所对应n级分类目录所包含的分类数据。

图1显示了一种使用上述目录树存储的商品目录。从图1可以看出，各种商品数据经过一次分类后得到若干一级分类目录，例如电脑、珠宝首饰以及手机等等目录，将对应于图1所示目录树的各个一级子节点；而每个一级分类目录所包含商品还可以进一步进行二次分类得到的若干二级分类目录，例如，电脑目录还可以进一步划分为笔记本、台式机以及办公设备等等目录，这些二级分类目录将对应于图1所示目录树的各个二级子节点。对于无法再进行分类的分类目录而言，例如IBM或DELL等目录，将对应于图1所示目录树的叶子节点，除了在上述叶子节点上存储对应分类目录的名称或标识之外，还将进一步存储其对应分类目录所包含的各种商品信息，例如IBM笔记本电脑的各个商品信息或DELL笔记本电脑的各个商品信息。

通过上述树状结构可以清楚的指示出各级分类目录之间的分类关系，实现对分类数据的有效管理。然而，由于上述目录树实际上采用了多叉树的数据结构，该多叉树中每个节点所包含子节点的数目将对应于该节点所对应目录划分的子目录个数，因此，每个节点所包含子节点的数目是不确定的，或者说是不可预知的，这将导致目录树上的每个节点所需要存储空间的大小不能确定，从而造成数据存储过程中对存储空间的分配操作过于复杂。特别是在将上述存储方法应用到海量数据的管理时，例如电子商务中的商品目录管理、以及图书馆信息管理等等，由于海量数据所包含的信息量是非常巨大的，使得每个节点所包含的子节点数目过多，这将导致每个节点所存储的信息过于庞大，不但进一步增加了存储空间分配操作的复杂度，还将造成存储空间资源的浪费。

另外，在上述由多叉树结构目录树存储的分类数据的分类关系发生变化时，例如在增加、移动或删除某个分类目录时，还需要考虑该分类目录父节点存储空间的分配以及回收等问题，使得分类目录的增加、删除以及移动操作非常复杂。

发明内容

为了解决现有技术存在的问题，本发明提供了一种基于目录树的分类数据存储方法，可以有效地节省内存空间，同时简化分类数据的存储以及分类目录的移动、增加以及删除操作。

本发明还提供了一种基于目录树的分类目录查询方法，可以快速的检索到需要查询的分类目录，获得该分类目录所包含的分类数据。

在本发明所述的基于目录树的分类数据存储方法中，所述目录树上的每个节点至少包括孩子节点指针、兄弟节点指针以及数据指针；

所述分类数据的存储方法包括：

A、建立所述目录树的根节点，令该根节点的兄弟节点指针为空，数据指针为空，并建立一个新的节点，令所述根节点的孩子节点指针指向所建立的新节点，将所述新节点对应于分类数据的一个一级分类目录；

B、利用递归算法分别建立与所述分类数据的各级所有分类目录一一对映的节点，对应每个节点，若该节点所对应的分类目录包含下一级的分类目录，则令该节点的孩子节点指针指向一个对应于本节点所对应分类目录下一级分类目录的节点，并令该节点数据指针为空，否则，令该节点孩子节点指针为空，并令该节点数据指针指向用于保存本节点所对应的分类目录所包含的分类数据的内存空间；若所述目录树中已包含对应于该节点所对应分类目录同级分类目录的所有节点，则令该节点的兄弟节点指针为空，否则，令该节点的兄弟节点指针指向一个对应于本节点所对应分类目录的同级目录且未包含在所述目录树中的节点。

步骤B所述利用递归算法在所述目录树中建立与所述分类数据的所有分类目录一一对映的所有节点包括一下步骤：

C、令新建立的节点为当前节点，并判断当前节点所对应的分类目录是否具有下一级分类目录，如果有，则设置当前节点的数据指针为空，再建立一个新的节点，令当前节点的孩子节点指针指向在本步骤建立的新节点，并设置所述新节点对应于当前节点所对应分类目录的一个下一级分类目录，然后返回本步骤C；否则，设置当前节点的孩子节点指针为空，并将当前节点的数据指针指向用于保存当前节点对应分类目录所包含的分类数据的内存空间，然后执行步骤D；

D：判断当前节点所对应的分类目录是否具有未加入到该目录树中的同级分类目录，如果有，则建立一个新的节点，令当前节点的兄弟节点指针指向本步骤所建立的新节点，并设置所述新节点对应于当前节点所对应分类目录的一个未加入到该目录树中的同级分类目录，然后返回步骤C；否则，返回到当前节点所对应分类目录上一级分类目录对应的节点，并判断该节点是否为根节点，如果是，则结束，否则，令该节点为当前节点，并返回本步骤D。

本发明所述方法进一步包括添加分类数据到某个分类目录，具体为：

A1：根据所要添加到的分类目录在所述目录树中找到对应该分类目录的节点；

A2：设置该节点数据指针所指向的指针数组的第一个指针元素为当前的指针元素；

A3：判断当前指针元素所指向的内存空间是否为空，如果是，则向内存中请一块固定大小的内存空间，并令该指针元素指向新申请的内存空间，然后执行A4；否则，判断当前指针元素所指向的内存空间是否已满，如果是，则设置当前指针元素为指针数组的下一个指针元素，然后返回本步骤；否则，执行步骤A4；

A4：在当前指针元素指向的内存空间中添加所要添加的分类数据信息。

基于本发明所述基于目录树的分类数据存储方法，本发明还给出了一种基于目录树的分类目录查询方法，所述目录树上的每个节点至少包括孩子节点指针、兄弟节点指针以及数据指针；

所述分类目录的查询方法包括：

a、根据所要查询的分类目录在所述目录树种找到该分类目录所对应的节点；

b、判断该节点的孩子节点指针是否为空，如果是，则将该节点加入到一个容器中，然后执行步骤d；否则，执行步骤c；

c、通过递归算法读出该节点整个左树枝所包含所有叶子节点，并将读出的所有叶子节点依次加入到一个容器中，然后执行步骤c；

d、从所述容器中依次读出叶子节点，根据所读出叶子节点数据指针指向的内存空间，获取所述内存空间中存储的所有分类数据，返回给用户。

本发明所述目录树上的每个节点进一步包括用于标识该节点所对应分类目录的节点标识，在建立每个节点时，令每个节点的节点标识为该节点所对应分类目录的分类标识；

所述方法进一步包括：预先在内存中生成一个分类目录对应节点的节点标识与指向该节点所在物理内存空间指针的映射表，并在建立每个节点的同时在预先生成的映射表中保存该节点的节点标识与指向该节点所在内存空间的指针之间的映射关系；

步骤a所述根据所要查询、浏览的分类目录找到所述该分类目录所在的节点包括：

a1、在所述映射表中找到指向所述所要查询的分类目录对应的节点所在内存空间的指针；

a2、通过所述该指针直接定位到所述所要查询、浏览的分类目录所对应的节点。

由此可以看出，使用二叉目录树代替现有的多叉目录树存储分类信息可以获得以下有益效果：

首先，由于二叉目录树每个节点的大小是固定的，并且占用的空间很小，因此，使用二叉目录树存储分类信息可以大大节约内存资源，使内存可以存储更多的分类数据，提高的内存的存储效率。

另外，由于二叉树的生成以及节点的移动、增加、删除操作算法简单、开销小，并且在某个节点被移动、增加或删除的过程中，不需要考虑其父节点存储空间的分配以及回收等问题，使得使用二叉目录树对分类数据进行管理简单易行。

附图说明

图1为采用现有多叉树结构目录树存储的商品目录示意图；

图2为本发明优选实施例所采用目录树中每个节点的结构示意图；

图3为本发明优选实施例所述基于目录树的分类数据存储方法流程图；

图4为采用本发明优选实施例所述目录树存储的商品目录示意图；

图5为在本发明优选实施例所述二叉目录树中查询、浏览某个分类目录所包含的分类数据的方法流程图；

图6为在本发明优选实施例所述二叉目录树的某个分类目录中添加分类数据的方法流程图。

具体实施方式

为使本发明的目的、技术方案及优点更加清楚明白，以下参照附图并举实施例，对本发明作进一步详细说明。

考虑到二叉树是一种被广泛用于数据查找的数据结构，其生成以及节点搜索等算法比较成熟，且收敛速度快，因此本发明的核心思想在于利用二叉树结构存储分类数据。

本发明的一个优选实施例给出了用于存储分类数据的二叉树结构目录树(简称二叉目录树)中每个节点的结构，如图2所示，每个节点包含用于标识该节点所对应分类目录的节点标识(ID)，一个指向该节点下一级子节点的孩子节点指针，一个指向该节点同级节点中另一个节点的兄弟节点指针以及一个指向用于保存分类数据内存空间的数据指针。

本发明一个优选实施例所述使用上述二叉目录树存储分类数据的方法如图3所示，主要包括以下步骤：

A：建立根节点，即在内存中开辟一块空间存储该根节点的节点ID、其孩子节点指针、兄弟节点指针以及数据指针，设置该根节点的节点ID为0，令其兄弟节点指针为空(NULL)，数据指针也为NULL。

B：建立一个新的节点，令所述根节点的孩子节点指针指向本步骤所建立的新节点，并令所述新节点的节点ID为一个一级分类目录的分类标识。

在这里所述的分类标识是预先确定的、可以唯一标识分类数据每个分类目录的标识，例如，在本实施例中，前面描述过的商品目录中一级分类目录电脑的分类标识为1，珠宝首饰的分类标识为2，手机的分类标识为3；二级分类目录笔记本的分类标识为11，台式机的分类标识为12；三级分类目录IBM的分类标识为111，DELL的分类标识为112等等。这样，通过将当前节点的ID设置为某个分类目录的分类标识，就可以将当前节点与一个分类目录对应起来了。需要说明的是，在本发明中每个分类目录的标识可以采用任何形式，只要能够唯一标识各个分类目录即可，而不限于上述优选实施例给出的形式。在本步骤中，设置所述新节点的节点ID为一个一级分类目录的分类标识实质上是将所述新节点与一个一级分类目录对应起来。

本步骤所述建立新节点与步骤A所述建立根节点的方法相同，即在内存中开辟一块空间存储该节点的节点ID、孩子节点指针、兄弟节点指针以及数据指针。

在后续的步骤中，将通过递归算法创建用于存储所述分类数据的二叉目录树，具体包括：

C：令所述新节点为当前节点，判断当前节点所对应的分类目录是否具有下一级分类目录，如果有，则执行步骤D；否则，执行步骤E。

D：设置当前节点的数据指针为NULL，再建立一个新的节点，令当前节点的孩子节点指针指向在本步骤建立的新节点，并设置所述新节点的节点ID为当前节点所对应分类目录的下一级分类目录中一个分类目录的分类标识，即将所述新节点对应于当前节点所对应分类目录的一个下一级分类目录，然后返回步骤C。

在该步骤中，若所述当前节点对应于一个n级分类目录，则所述新节点的节点ID将为该n级分类目录所包含的一个n+1级分类目录的分类标识，例如当前节点对应二级分类目录笔记本，则所述新节点的节点ID就可以为三级分类目录IBM的分类标识111或三级分类目录DELL的分类标识112。

E：设置当前节点的孩子节点指针为NULL，并将当前节点的数据指针指向用于保存当前节点对应分类目录所包含的分类数据的内存空间，然后执行步骤F。

本步骤所述的用于保存当前节点对应分类目录所包含的分类数据的内存空间可以是大小任意并可以动态扩展的内存空间。

在本发明的另一个优选实施例中，为了方便进行内存资源管理，在该步骤中可以进一步设置一个指针数组，并将当前节点的数据指针指向该指针数组，其中，该指针数据的每个指针元素将分别指向固定大小的内存空间，所述固定大小的内存空间将用于记录各个叶子节点所对应的分类目录所包含的分类数据。所述指针数组所包含指针元素的个数n可以根据分类数据的多少预先设定，比如设定为10个，这样每个叶子节点就可以具有10个固定大小的内存空间。但并不是在每个叶子节点创建的时候就统一为该叶子节点申请n块内存空间，而是按需分配的，当一个内存空间存满的时候，才会申请下一个内存空间，并且每次申请仅分配一块内存空间。上述采用固定大小内存空间以及按需分配的方法主要是为了提高内存分配效率，有效地避免采用大小任意的内存空间存储分类数据时所需要的对内存空间的动态扩展操作。

F：判断当前节点所对应分类目录的所有同级目录中是否具有未加入到该二叉目录树中的，如果有，则执行步骤G；否则，执行步骤H。

G：建立一个新的节点，令当前节点的兄弟节点指针指向本步骤所建立的新节点，并设置所述新节点的节点ID为当前节点所对应分类目录的一个未加入该二叉目录树中的同级目录的分类标识，即将所述新节点对应于当前节点所对应分类目录的一个同级分类目录，然后返回步骤C。

在该步骤中，若所述当前节点对应于一个n级分类目录，则所述新节点的节点ID将为未加入所述二叉目录树的另一个n级分类目录的分类标识，例如当前节点对应二级分类目录笔记本，则所述新节点的节点ID就可以为未加入该二叉目录树的二级分类目录台式机的分类标识12或二级分类目录办公设备的分类标识13。

H：返回到当前节点所对应分类目录上一级分类目录对应的节点，并判断该节点是否为根节点，如果是，则结束；否则，执行步骤I。

I：令该节点为当前节点，并返回步骤F。

通过执行上述步骤A～I，用于存储分类数据的二叉目录树已经建立完成，并且所述二叉目录树的所有节点将与所述分类数据的所有分类目录一一对映。图4显示了采用上述二叉目录树存储的商品目录示意图。如图4所示，根节点的孩子节点指针将指向各种商品数据经过一次分类后得到一个一级分类目录，例如电脑目录对应的一级子节点。该一级子节点的孩子节点指针将指向该一级分类目录经过二次分类得到的一个二级分类目录例如笔记本目录对应的二级子节点；而其兄弟节点指针将指向另一个一级分类目录，例如珠宝首饰目录对应的一级子节点，如此类推。上述二叉目录树中的叶子节点，例如对应IBM或DELL等分类目录的节点的数据指针将指向一个指针数组，所述指针数组的指针元素将指向存储各个分类目录所包含商品信息的内存空间，即物理内存块。

下面将结合图5详细描述在上述二叉目录树中查询某个分类目录所包含的分类数据的方法，如图5所示，该方法主要包括以下步骤：

a1、根据所要查询或浏览的分类目录的分类标识在二叉目录树中找到所述该分类目录所对应的节点；

由于每个节点的节点ID就是该节点所对应分类目录的分类标识，本步骤所述查找对应节点的方法可以是将该分类目录的ID作为索引遍历所述二叉目录树，找到所述分类目录对应的节点；

a2、判断该节点的孩子节点指针是否为NULL，如果是，则执行a3；否则执行步骤a4；

a3、将该节点加入到一个容器中，然后执行步骤a5；

本步骤所述的容器是一块用于暂时存放叶子节点的临时内存空间；

a4、通过递归算法读出该节点整个左树枝所包含所有叶子节点，并将读出的所有叶子节点依次加入到一个容器中，然后执行步骤a5；

a5、从所述容器中依次读出叶子节点，根据所读出叶子节点数据指针指向的内存空间，获取所述内存空间中存储的所有分类数据，返回给用户。

若上述二叉目录树的叶子节点的数据指针指向的是一个指针数组，在步骤a5还需要进一步通过该指针数组找到存储分类数据的内存空间。

接下来将详细描述在上述二叉目录树中添加分类数据的方法，例如添加某个商品信息到一个分类目录的方法。

若上述二叉目录树的叶子节点的数据指针指向的是大小任意并可以动态扩展的内存空间，则首先根据所要添加到的分类目录的分类标识找到所述该分类目录所在的节点；然后将需要添加的分类数据添加到该节点数据指针所指向的内存空间中。若该内存空间已满，还需要首先通过内存动态扩展操作扩展该节点数据指针所指向的内存空间。

若上述二叉目录树的叶子节点的数据指针指向的是一个指针数组，则需要执行以下步骤，如图6所示：

b1：根据要将分类数据添加到的分类目录的分类标识在二叉目录树中找到所述该分类目录所在的节点；

本步骤所采用的方法与步骤a1所述的方法相同；

b2：设置该节点数据指针所指向的指针数组的第一个指针元素为当前的指针元素；

b3：判断当前指针元素所指向的内存空间是否为NULL，如果是，则执行步骤b4；否则，执行步骤b6；

b4：向内存申请一块固定大小的内存空间，并令该指针元素指向新申请的内存空间，然后执行步骤b5；

b5：在当前指针元素所指向的内存空间中添加所要添加的分类数据信息，然后结束；

b6：判断当前指针元素所指向的内存空间是否已满，如果是，则执行步骤b7；否则，执行步骤b5；

b7：设置当前指针元素为指针数组的下一个指针元素，然后返回步骤b3。

在该步骤中，若当前指针元素为指针数组的最后一个指针元素，并且其指向的内存空间已满，则无法在当前的目录树中添加相应的分类数据，应当返回错误信息给用户。

从上述优选实施例可以看出，由于二叉目录树每个节点的大小是固定的，并且占用的空间很小，因此，使用二叉目录树代替多叉目录树存储分类信息可以大大节约内存资源，从而可以存储更多的分类数据，并获得较高的存储效率。另外，由于二叉树的生成以及节点的移动、增加、删除操作算法简单、开销小，并且在某个节点被移动、增加或删除的过程中，仅需要修改其父节点的指针指向，而不需要考虑其父节点存储空间的分配以及回收等问题，使得使用二叉目录树对分类数据进行管理简单易行，可以在系统正常运行的环境下指向分类目录的变更操作，而不需要停机。

经过测试，在实际的应用中，假如有1000万件商品，共有2000个最小的分类目录，应用上述二叉目录树的方法，系统可能存在的节点，包括叶子节点和非叶子节点一共为3000个，每个节点占用的空间约为16字节(其中节点ID、孩子节点指针、兄弟节点指针以及数据指针各需4字节)，并且每件商品在仅存储商品标识的情况下仅需要4字节的存储空间，那么所有的节点以及商品所需要的总的内存空间约为3000×16+10,000,000×4＝40.048兆字节。完全可以全部存放在计算机内存空间中，从而可以极大地提高数据的检索效率。

在上述二叉目录树中查询、浏览某个分类目录所包含的分类数据的方法以及在二叉目录树中添加分类数据的方法中，均需要首先根据分类目录的分类标识通过遍历二叉目录树的方法找到所述该分类目录所在的节点，这种遍历操作将耗费较多的时间。

为了方便查找各个分类目录，本发明的又一个优选实施例预先在内存中生成一个分类目录对应节点的节点ID与指向该节点所在物理内存块指针的映射表，并在执行上述步骤A～I生成所述二叉目录树的过程中，在步骤C进一步执行如下操作：在预先生成的映射表中保存步骤C所述当前节点的节点ID与指向当前节点所在内存空间的指针之间的映射关系。

这样，由于每个节点的节点ID就是该节点所对应分类目录的分类标识，因此，在上述二叉目录树中查询、浏览某个分类目录所包含的分类数据的方法以及在二叉目录树中添加分类数据的方法中可以首先直接根据要将分类数据添加到的分类目录的分类标识，在所述分类目录对应节点的节点ID与指向该节点所在物理内存块指针的映射表中找到指向该分类目录对应的节点所在内存空间的指针，然后通过所述指针直接定位到所述分类目录对应的节点，而无需进行二叉目录树的遍历。例如，现在有1000万件商品，分布在1000个叶子下面，这样，平均每个叶子节点下有1万件商品。如果用户需要浏览某个分类目录，这个分类目录下包含了20万件商品，通过预先保存的节点ID与指向该节点所在内存空间的指针之间的映射关系可以直接定位到该分类目录对应的节点，因此，系统需要检索的商品总数只有20W，而不需要从整个1000万件商品中过滤，并且，用户每选择查找下一级的分类目录，所需要检索的商品总数都会快速减少，从而大大地提高了节点的查找效率，进一步提高了分类数据的管理效率。