2022年用二叉树对嵌入式系统的配置进行数据库管理的方法资料 .pdf

1 用二叉树对嵌入式系统的配置进行数据库管理的方法唐强E-mail: 【摘要】嵌入式系统的配置管理就是一个微型的数据库系统，对设备的各种操作，通过嵌入式系统的API 转换，就映射成对数据库的操作了。最基本的操作就是添加，删除，修改，查询。 嵌入式系统的数据库存储方式大同小异，而数据库管理技术就因系统平台的不同而相差甚大。 本文主要探讨通过使用二叉树来对嵌入式系统的配置进行数据库管理的方法，重点是如何使用二叉树来组织配置的结构。关键词： 嵌入式二叉树 TR069 嵌入式系统配置的数据库组织形式多种多样，经常会为了满足一些功能特性或者缩小其它功能的开发时间，而引入新的数据库组织形式。TR069 是近年来家庭网关中引入的一项新的管理平台和技术，通过节点路径的管理方式，使用的数据采用XML 标准格式。转换成树形结构显示如下：RootNode |-FUNCTION1 | |-PARAM1-1 | |-PARAM1-2 |-FUNCTION2 |-PARAM2-1 |-PARAM2-2 |-PARAM2-3 由于软件开发的特性要向下兼容，所以大多数平台都是采取把TR069 作为一个新增的独立功能来开发，TR069 分成两大模块，一个是TR069 的消息管理模块，另一个是系统配置与 TR069 数据之间的转换模块。早期家庭网关设备功能单一，所以配置转换模块的开发工作量不是很大， 但随着互联网的发展和各种多媒体业务的扩展，家庭网关设备越来越复杂，每种功能特性都有对应的配置信息，而配置转换模块要针对每一种功能特性来做相应的开发，维护的成本很高，模块也越来越庞大。不仅如此， TR069 是个很开放的功能，除了 TR98标准等规定的节点外，很多网络运营商还要求支持私有的节点。这种情况下， 配置转换模块的维护开发就越来越混乱，很多代码不具有可移植性。越到后期， 就越是一个客户一套代码，代码维护的工作量相当大。基于上述原因， 很多新的平台开始考虑使用新的配置组织架构，以让各种配置信息可以简单映射到各种管理平台所需的数据结构。对用户来说， 就是前面说到的树形结构，而对于设备内部和开发人员，就是以某一种数据结构来组织数据了。以下将分别说明如何使用二叉树来组织嵌入式系统的配置数据，包括描述配置数据的二叉树抽象结构、说明二叉树数据结构及操作、以范例描述管理操作到配置数据库的映射过程。1 二叉树抽象结构二叉树的典型结构是一个父节点，有两个子节点，一个是左子节点，一个是右子节点。基础结构如下：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 7 页 - - - - - - - - - 2 图一每一个节点有几个基础属性，最重要的是指向左子节点的指针和指向右子节点的指针，由这两个指针构成一个二叉树节点，多个相关联的二叉树节点通过左右子节点指针又组成了完整的二叉树。 通常为了访问方便，每个二叉树节点还包含一个父节点指针，这样就行成了双向链表。这样的二叉树有如下特点：1、除了最上面的节点，所有的节点都有父节点，这个节点我们通常叫做根节点，它的父节点指针为空，通过以它为起点，可以查找到任意节点；2、标准的二叉树， 只有子节点指针为空的节点才叫做叶子节点，叶子节点可以存放数据。具体使用的时候， 并不完全按照这样的特性来做，需要根据实际情况做一些变通。多个二叉树节点组合到一起，就形成二叉树，如下图：图二如上的二叉树并不直接适用于嵌入式系统的配置管理，首先需要了解嵌入式系统配置方面的特点， 才能讨论如何用二叉树的结构来管理。由于嵌入式设备的特性，本身拥有的物理内存和存储器的大小很有限，大多只有几MB ，甚至几百KB ，这就要求设计数据模型要充分利用有限的内存空间。所以如果要使用二叉树来设计配置的数据结构，就必须利用上所有的节点来存储数据。在性能方面的要求不是很高，但要比较迅速的找到所需要的节点上的信息，在用户对设备进行操作的情况下，往往要在很短的时间内对几十个，甚至几百个节点的信息进行访问， 并用读取出的数据进行功能性上的各种操作，否则会影响到用户的体验。还有就是配置信息的特点，对于每一个功能特性，它有这个功能的一些公共的，或者说是全局的参数， 如防火墙功能， 它会有一个全局的总开关，即是启用还是禁用防火墙功能，我们把这个叫静态属性；另外大部分功能它还会有一些让功能具体生效的规则，如防火墙规则， 它有如下信息：规则应用于的源IP 地址及端口，规则是要允许通过还是拒绝访问，规则生效的时间访问等。 可动态添加规则的属性，我们叫做动态属性。这种配置的特点概述起来，就是有一部分配置信息是全局只有一份的；另一部分配置信息是具有相同的数据结构，但所保存的值有差别，一般有一个从1 开始的索引号，在TR069 的管理上，这种叫做实例。功能Parent Lchild Rchild 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 7 页 - - - - - - - - - 3 图表的结构大致如下：图三剩下是如何用抽象的方法把配置数据用二叉树的结构来表示出来。我做了如下定义：凡是第一个子节点，就放入到父节点的左子节点中；与第一个子节点同层的其它子节点，依次作为前一节点的右子节点顺序连接起来。首先是从根节点开始，各功能的起始节点都属于同一个层次， 我们把第一个功能的节点用根节点的左子节点指针连接起来，然后把第二个功能节点作为第一个功能的右子节点连接起来，再把第三个功能节点作为第二个功能的右子节点连接起来，依次类推，得到如下的图（我们假设只有3 个功能）：图四备注：为了简便，根节点我们用R 表示，功能用F1，F2Fn 表示，属性用A1,A2 An 表示，实例用O1，O2On 表示，实例1 的属性用O1-1， O1-2O1-n 表示。以下相同。我们取功能一为例说明，如前面讨论的， 功能一有一般的静态属性和可动态添加实例的动态属性。 这些属性在同一个层次，所以我们按照前面所述的功能的表示方法，第一个属性作为功能 F1 的左子节点，其它属性依次作为右子节点顺序排列下来。动态属性下面可以添加实例， 实例作为下一层的节点，我们依旧是按照属性和功能的排列方式。如此我们假设功能 F1 有 2 个静态属性和一个动态属性，动态属性下面添加了2 个实例，每个实例有3 个属配置管理功能 1 属性 1 2 m 功能 2 属性 功能 n 1 2 m 属性 1 2 m R F1 F2 F3 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 7 页 - - - - - - - - - 4 性，这样把功能F1 的所有子节点补充到上述图中，得到如下的结果：图五备注：为了清晰，上图实例O2 省去了属性O2-1，O2-2，O2-3。如上图的结构，我们就把系统中的配置抽象到了二叉树上。如前面所述， 当我们要把配置管理应用于TR069 之中时， 上述配置结构要能很方便地转换成XML 结构。在上面的描述中，已经说到了配置中层的概念，转换后得到如下内容，左边是XML 结构，右边是树形结构： R |-F1 | |-A1 | |-A2 | |-A3 | |-O1 | | |-O1-1 | | |-O1-2 | | |-O1-3 | | | |-O2 | |-O2-1 | |-O2-2 | |-O2-3 |-F2 |-F3 (省略) R F1 F2 F3 A1 A2 A3 O1 O2 O1-1 O1-2 O1-3 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 7 页 - - - - - - - - - 5 (省略) 图六图七如上， XML 结构就可以和设备的配置进行相互映射，为了方便转换和用户查看，我们再补充上路径的表示方法。如O1-2 节点，用路径来表示：R.F1.A3.O1.O1-2 这里用的分隔符是英文中的点符号，设计者可以自定义分隔符，由于TR069 管理中使用点符号，所以为了方便，可以统一采用点符号。2 二叉树数据结构二叉树的数据结构本身有指向父节点的指针和左右两个子节点指针，还有就是我们在配置管理中需要用到的属性，根据需要补充必要的结构体成员。struct scew_true char *name; /节点的名字char *value; /节点的属性值。叶子节点才有值，叶子节点与根节点之间的节点作为查/找路径struct attribute_list attribute; /可以定义一个结构体或者枚举类型等，用来表示此节点、/的相关属性，如节点值是什么属性，节点是否是实例。unsigned int n_child; /用来保存下一层的节点数。通常用于保存实例节点的数目，如配/置防火墙功能添加的规则数目。struct scew_true *parent; /指向父节点的指针struct scew_true *left; /保存左子节点的指针struct scew_true *right; /保存右子节点的指针; 余下是对此数据结构的操作了。四个最基本的操作是查询，插入，删除，修改。由于前面对二叉树的配置结构作了定义，所以这几个操作的细节与通常不同。以下简单描述这四个操作的过程方法。查询根据路径来查询，如R.F1.A3.O1.O1-2 结构的路径， 也称 OID。从根节点开始，由于有如下定义： 如果左子节点不为空， 则此节点不是叶子节点， 否则就是叶子节点。所以我们找到根节点的左子节点，并通过轮询右子节点指针，查找name属性为 F1 的节点。找到 F1 的节点后，再重复前一步骤， 从 F1 的左子节点开始，轮询右子节点，查找name属性为 A3 的节点。依次类推，最后得到O1-2 节点，由于 O1-2 的左子节点指针为空，所以这是一个叶子节点，返回value值。查询结束。修改修改的操作要先利用查询的操作，找到指定的节点，设置value 值属性。修改结束。插入嵌入式产品中， 并不关心新增加的配置是否需要插入到某一个节点之前，大多数都是在结尾接着添加即可。不过我们这里用了二叉树，都可以实现。 首先利用查询功能，找到指定的节点， 如果是添加， 则找到最后一个节点的位置。然后赋值指针，把新添加的节点串联起名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 7 页 - - - - - - - - - 6 来。新添加节点的构造方法根据情况实现，不在这里讨论。插入完成。删除删除操作前， 也是利用查询操作找到指定的节点，然后把此节点前后的节点用指针串联起来， 如果已经是最后一个节点，则直接把上一节点的右子节点设为空。最后再用轮询的方式，把此节点以下的所有节点都释放掉。删除操作完成。3 配置管理到配置数据库的映射嵌入式产品中有各种各样的操作，细化开来， 都可以用上面的四种基本操作来表达。以下用一个添加防火墙规则的范例来描述用户配置操作，到嵌入式系统中数据库配置的映射过程。嵌入式系统具有一个用户配置界面（CLI ） ，在用户添加一条新的防火墙规则前，要填写这条防火墙规则的相关信息：源IP 地址，端口号，允许或者拒绝。这里我们利用上图五，用 F1 代表防火墙功能，A3 节点下的实例所包含的属性Oi-1,Oi-2,Oi-3 分别对应于防火墙规则的三个属性。 当用户提交防火墙规则的信息后，嵌入式系统收到请求后，先对信息进行解析处理。 信息确认完毕后，系统告诉配置管理模块：要在防火墙功能节点下添加一条新的规则（提供防火墙节点的路径，这个是固定的），并附上规则具体的信息。配置管理模块首先构造这条防火墙规则的节点结构。首先是实例号， 因为此时还不知道当前已经有多少条防火墙规则，所以实例号暂时用Oi 表示，即name 属性为 ” Oi ” 。然后依次添加三个叶子节点，得到如下防火墙规则的结构：图八接着查找配置数据库中的实例节点，动态实例都添加在A3 节点下面。 找到 A3 节点后，A3 的左子节点指针不为空，即当前已经有实例，或者可以通过n_child 成员来判断。 然后得到第一个实例节点O1，并依次根据右子节点指针，找到最后一个实例O2。我们新添加的实例就要放到这后面。确定添加的位置后，就把O2 的 right 指针指向 Oi，把 Oi 的 parent 指针指向O2，Oi 的right 指针赋为空， 表示这是此队列最后一个实例。接着把 Oi 修改为 O3，并把 A3 的 n_child的值加 1。这样新的防火墙规则在配置数据库中就添加完成了。图五经过添加操作，得到最终的二叉树结构图（实例O1 和 O2 的属性省略了） ，如图九。剩下的就是嵌入式设备对此防火墙规则生效处理了。到此， 对嵌入式设备的操作，到对配置数据库的操作，通过对二叉树的访问操作，就完成了。 这里在很多细节方面因为不在本文讨论范围内，只做了简单说明。同时，这里选用的例子也是相对简化的，实际上在对嵌入式设备的操作，会有更多的对配置数据库的操作，但操作都是由查询，添加， 删除和修改这四项基本操作来组合完成的。只要掌握基本操作，其它所有的操作都可以组合完成。Oi Oi-1 Oi-2 Oi-3 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 7 页 - - - - - - - - - 7 图九A Method to Operate Configuration of Embedded System with Database Management by Binary Tree Tang Qiang Abstract Configuration management of embedded systems is a mini-database system, a variety of operating the equipment are mapping to the database operations through embedded system API conversion. The most basic operation is to add, delete, modify, and query. All the storage of embedded database system are much the same, but database management technology on different system platforms is a big gap. This paper discusses the configuration of embedded systems by using the binary tree to the database management, focusing on how to use the binary tree to organize the structure of the configuration. Keywords: Embedded; Binary Tree; TR069 R F1 F2 F3 A1 A2 A3 O1 O2 O3 O3-1 O3-2 O3-3 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 7 页 - - - - - - - - -