数据库“路径法”无限级分类节点算法设计与实现

吴承辉

(福建省经济信息中心教育培训处,福州350002)

0 引言

信息社会中,数据信息大量以数据库为媒介进行存储,要提高数据的检索速度,除了提高计算机软、硬件性能,合理设置使用索引等,亦可以通过进行数据信息的类别划分来提高检索性能。应用系统数据库设计时,分类设置可以分为:“固定级分类”和“无限级分类”。“无限级分类”常采用“递归法”进行设计,但因“递归法”进行“递归”操作难度高,效率低。所以本论文主要分析“路径法”的设计与实现。

1 分类算法类别

1.1 有限级分类

有限级分类一般是在数据库中建立对应数量的级别表,以主、外键关联来实现多个不同的分类级别。这种分类实现简单,级别间关系清晰,代码易于实现,但是,它只能实现固定层次的分类,而无法做到无限级别,在特定的场合使用会受到极大的限制。

1.2 递归法无限级分类

数据库无限级分类常用“递归法”,即仅建立一张分类表,采用“自连接”操作,主键、外键都在此表上;理论上,表的数据行无限,则级别无限,采用循环递归的查询,就可以把各个级别查询出来;优点是结构简单清晰,可以无限扩充级别,容易添加级别数据;缺点是用“递归算法”创造的结构,对分类数据查询难度高、效率低,要精确查询某个分类及层次比较困难。

1.3 路径法无限级分类

无限级分类还可以采用“路径法”。此算法同样用一张表就可以实现无限级的分类。类别之间的层次直接使用类别的编号组成的字符串先后秩序来识别。此算法优点是数据查询速度快,效率高,容易得到各个分类所在的层次。缺点是:路径信息维护比较烦琐,需要依靠专门算法过程来实现来维护;“路径法”理论上是“无限”级分类,但实际分类的级别会受到路径字段的长短限制,而无法真正达到绝对“无限级”。

2 “路径法”分类设计原理

2.1 表结构及示例数据图

“路径法”采用一张表保存各个分类,结构如表1所示。

iListID_PK:分类ID号,系统自动编号,并设置唯一值。

sListGUID:预留字段,GUID值,可以为每个分类编排一个全球唯一标识。

sListName:类别名。

sOrder:排序路径,此字段设置为主键,用它来进行数据类别的先后顺序排列。“sOrder”字段内保存各个分类级别路径分类编号的ID值。

iDepth:类别所在的级别和深度,它是计算字段

iVisible:预留字段,设置此类别是否可见。

示例数据图如图1所示。

表1 “路径法”结构表

图1 示例数据图

2.2 sOrder排序算法规则

(1)sOrder为字符串类型,默认值为当前iListID_PK转换成长度为10个字符的字符串。

例:类别“中国”的 sOrder为“0000000001”。

(2)若当前分类在某一其他分类下,则sOrder数值则为父节点的sOrder值合并上本节点的排序值。

例:“江西省”的值为父节点的 sOrder值“0000000001”加上本节点的 sOrder值“0000000002”,所以“江 西省”的 sOrder值为“00000000010000000002” 。

例:“南昌市”的值为,父节点的 sOrder值“00000000010000000002”加上本节点的 sOrder值“0000000004”,所以“南 昌市”的 sOrder值为“000000000100000000020000000004”

(2)sOrder建立聚集索引。聚集索引的组织形式为Balance Tree,所以分类会严格按照字符串的大小顺序排列。

(3)类别顺序也是由聚集索引决定。

按照字符串的排序由小到大规则,“000000000100000000020000000004”一定排列在“000000000100000000020000000008”之前 ,即“南昌市”排列在“吉安市”之前。

若需要调整“南昌市”和“吉安市”的顺序,只需要调换 sOrder最右边的 10个字符。即把“0000000004”和“0000000008”调换即可,不需要改变iListID_PK的值。

(4)类别所在层次用iDepth表示,此字段绑定在一个数据库函数上,函数根据sOrder的长度除10,计算出当前类别所在的层次。

3 核心算法代码

3.1 计算分类节点函数

向函数传入一个参数,即 sOrder的值,根据sOrder返回出节点层次。此函数绑定在iDepth字段上。

3.2 添加分类节点值存储过程。

向存储过程传入2个参数,参数@sListName是分类节点名称;参数@iParentID是父节点ID,如果父节点ID为0不存在,则视为创建一个根节点。

3.3 查询某节点值存储过程。

向此存储过程传入3个参数。参数@iListID_PK是要查询的分类节点ID;参数@sShowSelf表示是否显示本节点,值为“true”表示显示,“false”表示不显示;参数@iListCount是需要查询的层次,值为-1表示当前分类节点下的所有层次。

4 结语

无限级分类算法在实际的软件开发中具有极高的实际运用价值。本文论述的“路径法”无限级分类具有结构简单,查询运行效率高,分类层次容易识别等特点,可以配合绝大部分的实际系统的分类处理,有较高的实用价值。此算法因路径为字符串组成,理论上可以达到无限级,此字符串长度受到数据库字段长度的限制,实际分类只能是相对“无限”。本设计的sOrder长度为900,即只能达到90级,最大行数编码为9999999999行,超过10亿的大小,这样的数量级已可以满足绝大部分的分类需求。

本论文仅写出基础核心算法代码,分类节点操作中还有分类节点位置调整,分类节点移动,删除分类节点,根据某节点分类ID找出父节点的ID等操作有待读者进一步挖掘和完善。

[1]Itzik Ben-Gan.Microsoft SQL Server 2008技术内幕[M].北京:电子工业出版社,2009:346-354.

[2]Robert Vieira.SQ L Server 2005高级程序设计[M].北京:人民邮电出版社,2008:221-259.

[3]胡百敬,姚巧玫,刘承修.SQL Server 2005 Performance Tuning性能调校[M].北京:电子工业出版社.2008:605-619.

[4]李如平.数据挖掘中决策树分类算法的研究[J].东华理工大学学报:自然科学版,2010,33(2):192-196.

[5]赵慧玲,刘美荣.SQL数据库中并发控制的研究[J].长春工程学院学报:自然科学版,2009,10(2):78-81.

[6]史晓峰,林和平.面向对象数据库及其对象查询处理的研究[J].长春工程学院学报:自然科学版,2008,6(3):66-68.

[7]赵洁红.购物订单数据库新息验证[J].长春工程学院学报:自然科学版,2006,7(1):57-59.