计算机网络的拓扑结构分为哪些

如果采用非递归算法实现二叉树的前序遍历，需要借助于栈结构。其步骤如下：

如果根节点rt为空，则返回；否则，首先将根节点压入栈中，然后迭代执行以下步骤：

1. 弹出栈顶存放的节点n，访问该节点；

2. 依次将n的右子节点和左子节点压入栈中；

3. 如果栈不为空，则返回步骤1继续执行，否则结束迭代。

其中步骤1为节点访问操作；步骤2中先将右子节点压入栈中然后再将左子节点压入，这是因为在栈的弹出操作服从先入后出的准则，根节点访问结束后需要先访问的是左子节点，所以左子节点在右子节点之后压栈；步骤3是遍历过程终止的条件。

根据上述迭代步骤，图中二叉树的遍历步骤可以分解为如下步骤，对应如图所示。

1． 将n14压栈；

2． 弹出栈顶节点，此时为n14，访问节点n14；

3． 将n14的右子节点n13和左子节点n8依次压入栈中；

4． 弹出栈顶节点，此时为n8，访问节点n8；

5． 将n8的右子节点n7和左子节点n4依次压入栈中；

6． 弹出栈顶节点，此时为n4，访问节点n4；

7． 将n4的右子节点n3和左子节点n2依次压入栈中；

8． 弹出栈顶节点，此时为n2，访问节点n2；

9． n2的右子节点为空，则将n2的左子节点n1压入栈中；

10．弹出栈顶节点，此时为n1，访问节点n1；

11．n1的左子节点为空，则将n1的右子节点n0压入栈中；

12．弹出栈顶节点，此时为n0，访问节点n0；

13．n0为叶节点，则无子节点压栈；

14．弹出栈顶节点，此时为n3，访问节点n3；

15．n3为叶节点，则无子节点压栈；

16．弹出栈顶节点，此时为n7，访问节点n7；

17．将n7的右子节点n6和左子节点n5依次压栈；

18．弹出栈顶节点，此时为n5，访问节点n5；

19．n5为叶节点，无子节点压栈；

20．弹出栈顶节点，此时为n6，访问节点n6；

21．n6为叶节点，无子节点压栈；

22．弹出栈顶节点，此时为n13，访问节点n13；

23．将n13的右子节点n11和左子节点n12依次压栈；

24．弹出栈顶节点，此时为n12，访问节点n12；

25．n12为叶节点，无子节点压栈；

26．弹出栈顶节点，此时为n11，访问节点n11；

27．将n11的右子节点n10和左子节点n9依次压入栈中；

28．弹出栈顶节点，此时为n9，访问节点n9；

29．n9为叶节点，则无子节点压栈；

30．弹出栈顶节点，此时为n10，访问节点n10；

31．n10为叶节点，则无子节点压栈；

32．栈空，遍历过程结束。

图 二叉树前序遍历算法栈结构动态过程

迭代过称中利用了栈结构，图示的栈结构中栈的大小是固定的，事实上在实现时预先设定好栈的大小并不容易，所以在具体实现时，采用第XX章中讨论的链式栈，动态调整栈的大小。

中序遍历

第二种遍历算法称为中序遍历算法。与前序遍历算法相比，中序遍历算法首先访问节点的左子树，然后访问节点自身，最后访问节点的右子树。可见，节点自身是在访问左右子树中间访问的，顾称之为中序。图中的二叉树的中序遍历结果为：

内表刚定义时不会事先指定占用实际内存的大小，用INITAL SIZE也并不能使内表占用实际内存空间，只是预约内存空间。

标准表：有顺次索引的树形结构内表，是可以利用索引和关键字操作的内表；标准表的关键字不唯一，在定义时不能使用WITH UNIQUE KEY语句。

DATA: 表名 LIKE/TYPE STANDARD TABLE OF 要参考的变量或类型                                                   WITH NO-UNIQUE KEY    字段名.

排序表：与标准表一样都是索引表，其中排序表是已经按照关键字排序好的内表类型，且可以使用WITH UNIQUE KEY 或 WITH NO-UNIQUE KEY；排序表是已经排序好的内表类型，所以不能使用SORT语句进行再次排序。

DATA: 表名 LIKE/TYPE SORTED TABLE OF 要参考的变量或类型                                                   WITH NO-UNIQUE KEY    字段名.

哈希表：没有索引，只能指定UNIQUE关键字（关键字内容不能重复）。

DATA:表名 LIKE/TYPE HASHED TABLE OF 要参考的变量或类型                                                   WITH UNIQUE KEY    字段名.

在定义内表时没有WITH HEADER LINE则该内表没有表头，在往内表里APPEND数据时，需要追加工作区（这里可以是结构体，也就是说需要先给工作区赋值，然后再APPEND 工作区 TO 内表）。其它对内表行内容执行的操作同样也要借助工作区才能实现。

如果在定义内表时追加WITH HEADER LINE(表头)，这时就定义了一个带表头的内表，表头的下一行就是内表的第一行，这时内表的表头就承担了工作区的职能。

往带表头的的内表里追加数据时，只需要先给表头赋值，在APPEN 内表名就可以了

APPEND itab = APPEND itab TO itab.(这句话的意思就是把表头里的数据追加到内表中）

这是因为内表名与表头名相同

INSERT itab/wa INTO TABLE itab. = INSERT TABLE itab.

COLLECT itab/wa INTO itab = COLLECT itab.

READ TABLE itab INTO itab/wa = READ TABLE itab.

...

内表赋值

MOVE itab1 TO itab2. "这里需要注意的是带表头的内表用这种赋值方法只会赋值表头中的数据。

要想赋值表体中的数据，可以用以下的方式：

MOVE itab1[] TO itab2[].

当然这两种赋值方式执行成功的前提是两个表的类型需一致，要想赋值不同类型的内表可以使用如下：

MOVE-CORRESPONDING itab1 TO itab2. "这种方式是赋值对应字段

内表的初始化

CLEAR itab (带表头的内表只删表头，不带表头的内表删表体）

CLEAR itab[] （删除带表头的表体）

内表排序

1.SORT（可以排序标准表和哈希表）

用内表的关键字堆排序语法：SORT itab [ASCENDING | DESCENDING].其中ASCENDING是升序（默认排序），DESCENDING是降序。对于没有设有关键字的内表进行排序时，讲组合字符串类型的字段作为主键进行排序。

2.指定排序字段

SORT itab [ASCENDING | DECENDING]  BY f1 [ ASCENDING | DECENDING]                                      ... fn [ASCENDING | DECENDING].(如果字段f1出现空值，则会排出此列）

3.Stable SORT

SORT itab ... STABLE. "保留序列号

内表属性

DESCRIBE TABLE itab [LINES gv_line] [OCCURS gv_init] [KIND kind]."LINES返回包含的数据件数,OCCURES返回内表的初始大小，KIND返回内表的类型T(标准表）S（排序表）H（哈希表）。

追加内表数据

1.INSERT

追加一条数据时（两个表的类型相同 ） INSERT wa INTO TABLE itab."没有定义表头的内表

                                                              INSERT itab.  "定义过表头的内表

追加多条数据时（两个表类型相同）

      INSERT lines OF itab1 [FROM n1] [TO n2] INTO TABLE itab2." 带不带表头的内表都可以使用这种方式。

2.利用索引追加一条数据（不能用于哈希表）

INSERT line INTO itab [Index idx]."利用Index语句可以在指定的索引位置追加一条数据，语句执行成功时SY-SUBRC返回0，SY-TABIX返回索引值，带表头的内表INSERT itab INDEX 1.

利用索引还可以追加多条数据

INSERT LINES OF itab1 INTO itab2 INDEX idx.

不同类型的内表具有各自不同的INSERT效果

标准表：追加数据到内表的最后一行（与APPEND效果相同）

排序表：按照内表排序好的顺序追加数据（若关键字是不唯一的，重复数据会追加到相同数据的上一行中,若关键字唯一则报错）

哈希表：按照表关键字的哈希索引顺序追加数据

2.APPEND

只能利用索引追加数据，因此哈希表不能使用此语句

追加一条数据时（表类型相同）： APPEND wa TO itab. （SY-TABIX保存追加数据的内表行，即追加后内表的索引编号）

追加多条数时（表类型相同）：APPEND LINES OF itab1 [FROM n1] [TO n2] TO itab2.      

注意：尽量不要使用APPEND往SORTED TABLE 里追加数据                                                                                                                  

3.COLLECT：可以合计内表中数字类型的字段

除了关键字以外的数据都需要是数字类型（f,i,p）（这不代表关键字不能是数字类型），当存在相同关键字的数据时，合计数字类型的字段，不存在相同关键字的数据时，直接追加数据（不存在关键字的内表，则会把char类型的字段作为关键字进行相同的操作）

COLLECT wa INTO itab.

1.MODIFY（可以利用关键字或索引修改数据）

    利用关键字修改一条数据（若内表关键字NON-UNIQUE，即存在重复数据时，会修改第一条数据）：MODIFY TABLE itab FROM wa [TRANSPORTING f1 ...fn].（ 利用transporting可以修改指定字段 ）；如果是带表头的内表可以省略FROM wa

    利用WHERe条件修改多条数据：MODIFY itab FROM wa TRANSORTING f1 .. fn WHERe cond. （其中cond是字段限制条件）

    利用索引修改一条数据：MODIFY TABLE itab FROM wa INDEX idx [TRANSPORTING f1 ... fn].（在loop循环中可以省略index选项，此时会修改当前行数据）

在LOOP循环中，MODIFY TABLE itab变为MODIFY itab.

    利用工作区删除内表中的一条数据：DELETe TABLE itab FROM wa.

    在关键字不唯一的标准表中使用WITH TABLE KEY删除重复数据中的一条数据：DELETe TABLE itab WITH TABLE KEY k1 = f1 ... kn = fn.

    利用WHERe条件删除多条数据：DELETE itab WHERe cond.

    利用索引删除内表数据：DELTE itab INDEX idx.

 利用索引也可以删除多条数据

DELETE itab FROM n1 TO n2."删除从n1到n2的数据

DELETe itab FROM n1."删除从n1开始之后的所有数据

DELETe itab TO n2."删除从开始到n2的数据

    利用ADJACENT DUPLICATE语句删除重复行（执行此语句前，先用SORT语句进行排序）

DELETE ADJACENT DUPLICATE FROM itab COMPARING  ALL FIELDS(所有字段相同才算重复）                                                            COMPARING 指定字段 （指定字段相同才算重复）

利用read读取内表数据。当存在表头时，对应得数据会保存到表头中。

    利用关键字读取内表：READ TABLE itab FROM wa INTO result.（wa和result均是工作区，可以利用给wa赋值某关键字去唯一确定内表中的一行数据，然后读取到result中）如果内表存在表头可以省略FROM以及之后的内容。                                                                          READ TABLE itab WITH TABLE KEY k1=f1 ... kn=fn INTO result.(带表头的内表可以省略INTO之后的内容）

    利用索引读取内表：READ TABLE itab INDEX INTO result.（带表头的内表省略INTO之后的内容）

数据库关系模型（数据库逻辑模型）是将数据概念模型转换为所使用的数据库管理系统（DBMS）支持的数据库逻辑结构，即将E-R图表示成关系数据库模式。数据库逻辑设计的结果不是唯一的，需利用规范化理论对数据库结构进行优化。

在关系模型中，数据库的逻辑结构是一张二维表。在数据库中，满足下列条件的二维表称为关系模型：

1）每列中的分量是类型相同的数据；

2）列的顺序可以是任意的；

3）行的顺序可以是任意的；

4）表中的分量是不可再分割的最小数据项，即表中不允许有子表；

5）表中的任意两行不能完全相同。

由此可见，有序的航空物探测量剖面数据不满足数据库关系模型条件第3条“行的顺序可以是任意的”，因此，不能简单地直接利用关系数据库（如Oracle，SQL Server，Sybase等）来管理剖面数据，需将数据在数据库中的存储方式改为大字段存储，确保不因数据库数据的增加和删除等操作改变剖面数据有序特性。

一、大字段存储

（一）大字段存储技术

大字段LOB（Large Object）技术是Oracle专门用于存放处理大对象类型数据（如多媒体材料、影像资料、文档资料等）的数据管理技术。LOB包括内部的和外部的两种类型。内部LOB又分CLOB（字符型）、BLOB（二进制型）等3种数据类型，其数据存储在数据库中，并且支持事务操作；外部LOB只有BFILE类型，其数据存储在操作系统中，并且不支持事务操作。LOB存放数据的长度最大可以达到4G字节，并且空值列（没有存放数据）不占空间（图2-6）。

图2-6 大字段存储示意图

由于外部LOB存放在操作系统文件中，其安全性比内部LOB差一些。此外，大字段的存储支持事务操作（批量提交和回滚等），而外部LOB不支持事务操作。所以，航空物探测量剖面数据采用BLOB来存储。对于BLOB类型，如果数据量小于4000字节，数据库通常采用行内存储，而数据量大于4000字节采用行外存储。分析航空物探测量剖面数据，每个场值数据占4个字节（单精度），目前航磁数据采样率为10次/s，4000字节只能存储100 s数据；一般情况下航空物探测量每条测线飞行时间至少在10 min以上，每条测线数据量远远大于4000字节。所以，航空物探测量剖面数据采用行外存储方式，即大字段列指定“Disable Storage In Row”的存储参数。

由于大字段类型长度可变，最大可到4G。假设测线飞行时间为T，场值采样率为n次/s，测线场值数据量为4Tn，所以有4Tn≤4G。单条测线飞行时间T不会超过10 h（36000 s，航空物探测量1架次至少飞行1个往返2条测线），则场值的采样率n≤4G/4T=4×1024×1024×1024/4×36000次/s=29826次/s。采用大字段来存储测量数据，不仅能够减少数据表的记录数，提高查询效率，而且使得采样率的扩展不受限制。

（二）大字段存储技术应用

由于航空物探数据的数据量较大，现有的航磁测量数据按基准点方式（点存储）存储可达几亿个数据记录。若按磁场数据采样点存储方式（简称“场值存储方式”），则记录条数=（磁场数据采样率/坐标采样率）点存储方式的记录数，达几十亿条数据记录，且随着数据采样率的扩展、测点的加密，航空物探测量数据量随着时间的推移呈现快速增长之势。显然，如果采用常规的表结构来存储，势必造成数据的存储、管理、检索、浏览和提取都非常困难。另一方面，从航空物探专业应用需求来说，很少对单个测点的场值数据进行运算、分析等操作，一般至少是对一条测线或以上测线，多数时候是需要对整个测区的场值数据进行化极、上延、正反演拟合等。

因此，在航空物探数据库表结构设计时，改变过去将基准点或场值点数据记录作为数据库最小管理对象的理念，采用了大字段存储技术，将测线作为数据库最小管理对象，将测线上的测量数据，如坐标数据和磁场、重力场数据分别存储在相应大字段中。在航空物探数据库建设中，大量采用数据库的大字段存储技术（详见《航空物探信息系统数据库结构设计》）。

（三）大字段存储效率

以航磁测量数据为例分析大字段存储技术优势。如果以场值存储方式存储测线数据，则每条记录包含架次号、测线号、基准号、地理坐标、投影坐标、磁场数据等，由于坐标数据采样率2次/s，磁场数据采样率10次/s，每5个磁场数据中，只有第1个磁场数据有坐标数据，其他4个坐标数据是内插出来，因此在测线记录中会产生大量冗余的数据坐标数据。采用点存储方式存储的测线数据记录数等于线上基准点数，若采用大字段存储方式，一条测线数据只存储为1条数据记录（图2-7），一般一条测线的测点数近万个，甚至更多，可见采用大字段存储大大减少测线数据存储记录数，提高数据的存取效率。

以某测区的两条航迹线为例，分别采用3种方式测试数据库的数据存储效率。磁场数据的采样率10次/s，坐标数据采样率2次/s，两条测线上共有基准点8801个。以场值方式存储先内插坐标信息，使得每个场值数据都拥有自己的坐标，然后存入数据库，共有数据记录44005条，写入数据库时间为57.22 s，读取时间为1.03 s。第二种方式是以采样点的方式进行存储，共有8801条记录，写入数据库时间为9.47 s，读取需要0.91 s。第三种方式是以大字段的形式存储，只有2条记录，写入数据库1.03 s，读取时间为0.44 s（表2-2）。大字段数据存储记录数最少，存取效率最高。用整个测区数据测试效果更加明显。

表2-2 三种数据存储方法的存取效率比较

图2-7 大字段存储方式示意图

二、联合主键

主外键是关系型数据库建立表间关系的核心。在航空物探空间数据库建设过程中，要素类与要素类之间、要素类与对象类之间，以及对象类与对象类之间的关系的描述有3种形式，即拓扑关系——描述要素类与要素类之间结点、邻接和联通关系；叠加关系——描述要素类与要素类之间的相交、包含与分类关系；隶属关系——描述对象类与对象类之间的派生关系。前两种关系是采用空间数据模型建立的关系，而隶属关系是通过主键建立的对象类与对象类之间的关系。在建立一对一、一对多的表间关系时，需要在整个数据库表中确定具有唯一性的一个字段作为主键（主关键字）。

按照传统的航空物探数据的档案管理模式，每个项目分配一个自然数作为档案号，项目的所有资料均与此档案号相联系。勘查项目和科研项目的档案号是独立编号的，且均从001开始。加之人工管理的原因，存在1个项目2个档案号和2个项目1个档案号的情况，因此现行的档案号与项目之间的对应关系不具备唯一性，不能作为项目的唯一标识，即不能作为数据库表的主键。项目编号也不能作为数据库表的主键，项目编号也只是近十年的事，以前的项目没有项目编号。

综合考虑上述因素和项目具有分级、分类的特点，提出了构造项目唯一标识码（简称“项目标识”）的方法，并以此码作为数据库表的主键。

项目标识（主键）：AGS+项目类别（2位）+项目起始年份（4位）+档案号（6位）

标识含义：AGS——航空物探的缩位代码；

项目类别——2位代码，01代表勘查项目、02代表科研项目；

起始年份——4位代码，项目开始年号；

档案号——6位代码，为了与传统的项目管理方式相衔接，后面3～4位是

项目档案管理模式下的档案号，不足部分补零。

以上15位编码是一级项目的项目标识，二级及其以下级别的项目标识是在上一级项目标识基础上扩展2位数字代码，中间用“.”号隔开，数字为该级项目的序号。项目标识定义为30位编码，适用于六级以内的项目。例如：AGS022004000576.08.04.02，表示该项目为2004年开展的档案号为576的航空物探科研项目（一级项目）的第8课题（二级项目）第4子课题（三级项目）的第2专题。由此可见，该项目标识不仅仅是一个建立表间关系的关键字，同时还表达了不同级别项目间的隶属关系。在系统软件开发时，利用此关系生成了项目的分级树形目录，用户对项目的层次关系一目了然，便于项目查询。

数据库的主键一经确定，相应地需要确定联合主键的组成及其表达方式。所谓联合主键就是数据资料的唯一标识，在一个数据库表中选择2个或者2个以上的字段作为主键。由于航空物探数据绝大部分与项目标识有关，加之数据的种类较多，分类复杂，单凭主键确定数据库表中记录的唯一性，势必需要构建极其复杂的主键，这种方法既不利于主键的数据操作，又会造成大量的数据冗余，合理地使用联合主键技术可以很好地解决资料唯一问题。以项目提交资料为例，提交的资料分为文字类资料、图件类资料和媒体类资料，我们对资料进行分类和编号，例如100代表文字资料（110——World文档，120——PDF文档），200代表图件资料（210——基础地理资料、220——基础地质资料，230——航迹线图，240——剖面图，250——等值线图等），300代表媒体资料（310——PPT文档，320——照片等），第1位（百位）表示该资料的类型，第2～3位表示该类资料的序号。

在数据库管理和项目资料查询时，采用项目标识与资料分类编号作为联合主键（图2-8），可以高效地实现复杂数据的查询。在整个数据库系统中多处（项目查询、数据提取等模块）使用联合主键技术。

图2-8 联合主键实例

三、信息标准化

为了实现数据共享，在航空物探数据库建模过程中，参考和引用了近百个国家信息化标准，编制了4个中心信息化标准和1个图件信息化工作指南。

（一）引用的国家信息化标准

1）地质矿产术语分类代码：地球物理勘查，地球化学勘查，大地构造学，工程地质学，结晶学及矿物学，矿床学，水文地质学，岩石学，地质学等。

2）国家基础信息数据分类与代码，国土基础信息数据分类与代码，地球物理勘查技术符号，地面重力测量规范，地面磁勘查技术规程，地面高精度磁测技术规程，大比例尺重力勘查规范，地理信息技术基本术语，地理点位置的纬度、经度和高程的标准表示法，地名分类与类别代码编制规则。

3）地球空间数据交换格式；数学数字地理底图数据交换格式；数字化地质图图层及属性文件格式。

（二）本系统建立的信息化标准

编写了“航空物探空间数据要素类和对象类划分标准”，“航空物探项目管理和资料管理分类代码标准”，“航空物探勘查分类代码标准”，“航空物探信息系统元数据标准”，“航空物探图件信息化工作指南”，以便与其他应用系统进行信息交换，实现数据库资料共享。

航空物探空间数据要素类和对象类划分标准：根据物探方法、数据处理过程以及推断解释方法和过程，把与GIS有关的数据划分为不同类型的要素类-对象类数据，按专业、比例尺、数据内容对要素类和对象类进行统一命名，使空间数据库中的每个要素类和对象类的命名具有唯一性，防止重名出现。规定要素类-对象类数据库表结构及数据项数值类型。

航空物探项目管理和资料管理分类代码标准：规定了航空物探项目管理和资料管理的相关内容，包括航空物探勘查项目和科研项目的项目立项、设计、实施、成果、评审、资料汇交等项目管理的全过程中的内容，以及项目成果资料和收集资料的归档、发送、销毁、借阅等资料管理与服务过程中的内容和数据项代码。

航空物探勘查分类代码标准：在“地质矿产术语分类代码 地球物理勘查”（国家标准GB/T 9649.28—1998）增加了航磁、航重专业方面所涉及的数据采集、物性参数、方法手段、仪器设备、资料数据解释及成图图件等内容和数据项代码。

航空物探信息系统元数据标准：规定了航空物探空间数据管理与服务的元数据（数据的标识、内容、质量、状况及其他有关特征）的内容。

四、航迹线数据模型

（一）航迹线模型的结构

航空物探测量是依据测量比例尺在测区内布置测网（测线和切割线）。当飞机沿着设计的测线飞行测量时，航空物探数据收录系统按照一定的采样率采集采样点的地理位置、高度和各种地球物理场信息。采用属性数据分置的方法，将测线地理位置信息从航空物探测量数据中分离出来，形成航迹线要素类表，在此表中只存储与航迹线要素类有关的数据，如项目标识、测区编号、测线号、测线类型（用于区分测线、切割线、不同高度线、重复线等）、坐标、高度值等；将航迹线的对象类数据（磁场、重力场基础数据）分别以大字段形式存储在各自的二维表中，它们共享航迹线，解决了多源有序不同采样率的航空物探测量数据的数据存储问题，在满足要素类空间查询的同时，统一数据的存储方式（图2-9）。航迹线要素类隶属于测区要素类，它们之间为空间拓扑（包含）关系。测区从属于勘查项目，每个勘查项目至少有一个测区，它们之间为1对多关系。有关项目信息存放在项目概况信息对象类表中，各种表之间通过项目标识进行联接。

图2-9 航迹线数据模型结构

（二）航迹线的UML模型

统一建模语言UML（Unified Modeling Language）是一种定义良好、易于表达、功能强大且普遍适用的建模语言。它溶入了软件工程领域的新思想、新方法和新技术。UML是面向对象技术领域内占主导地位的标准建模语言，成为可视化建模语言的工业标准。在UML基础上，ESRI定义了空间数据库建模的ArcGIS包、类库和扩展原则。

图2-10 与航迹线有关的数据库表逻辑模型结构图

在确定航迹线数据模型后，以它为基础，使用UML完成与航迹的有关的项目概况信息、测区信息、原始数据等数据库表逻辑模型设计（图2-10）。

由UML模型生成Geodatabase模式时，模型中的每个类都对应生成一个要素类或对象类。类的属性映射为要素类或对象类的字段。基类属性中包含的字段，在继承类中不需重复创建。例如，每个类都包括项目标识等字段，可以创建一个包含公共属性的基类，其他类从该类继承公共的属性，而无需重复建基类中包含的属性。因为基类没有对应的要素类或对象类，所以将基类设置为抽象类型。要素类之间的关系采用依赖关系表示。

五、数据库逻辑模型

关系数据库的逻辑结构由一组关系模式组成，因而从概念结构到关系数据库逻辑结构的转换就是将概念设计中所得到的概念结构（ER图）转换成等价的UML关系模式（图2-11）。在UML模型图中，要素数据集用Geodatabase工作空间下的静态包表示。要素集包不能互相嵌套，为了容易组织，在生成物理模型后，在要素数据集包中自定义嵌套。要素数据集与空间参考有关，但是空间参考不能在UML中表达。要素类和二维表都是以类的形式创建的，区别是要素类继承Feature Class的属性，而二维表继承Object属性。为了表达每种元素的额外属性，比如设置字符型属性字段的字符串长度，设置要素类的几何类型（点、线或面）需要使用Geodatabase预定义的元素标记值。

图2-11 逻辑设计关系转换

基于航空物探数据的内在逻辑关系进行分析，使用统一建模语言（UML）构建数据实体对象间的关系类，定义了航空物探数据库的逻辑模型（图2-12）。

一、数据的逻辑结构

指反映数据元素之间的逻辑关系的数据结构，其中的逻辑关系是指数据元素之间的前后间关系，而与他们在计算机中的存储位置无关。逻辑结构包括：

1、集合：数据结构中的元素之间除了“同属一个集合” 的相互关系外，别无其他关系；

2、线性结构：数据结构中的元素存在一对一的相互关系；

3、树形结构：数据结构中的元素存在一对多的相互关系；

4、图形结构：数据结构中的元素存在多对多的相互关系。

二、数据的物理结构

指数据的逻辑结构在计算机存储空间的存放形式。

数据的物理结构是数据结构在计算机中的表示（又称映像），它包括数据元素的机内表示和关系的机内表示。由于具体实现的方法有顺序、链接、索引、散列等多种，所以，一种数据结构可表示成一种或多种存储结构。

数据元素的机内表示（映像方法）： 用二进制位（bit）的位串表示数据元素。通常称这种位串为节点（node）。当数据元素有若干个数据项组成时，位串中与各个数据项对应的子位串称为数据域（data field）。因此，节点是数据元素的机内表示（或机内映像）。

关系的机内表示（映像方法）：数据元素之间的关系的机内表示可以分为顺序映像和非顺序映像，常用两种存储结构：

顺序存储结构和链式存储结构。顺序映像借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系。非顺序映像借助指示元素存储位置的指针（pointer）来表示数据元素之间的逻辑关系。

三、数据存储结构

数据的逻辑结构在计算机存储空间中的存放形式称为数据的物理结构(也称为存储结构)。一般来说，一种数据结构的逻辑结构根据需要可以表示成多种存储结构，常用的存储结构有顺序存储、链式存储、索引存储和哈希存储等。

数据的顺序存储结构的特点是：借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系；非顺序存储的特点是：借助指示元素存储地址的指针表示数据元素之间的逻辑关系。

扩展资料

在程序中，堆用于动态分配和释放程序所使用的对象。在以下情况中调用堆操作：

1、事先不知道程序所需对象的数量和大小。

2、对象太大，不适合使用堆栈分配器。

堆使用运行期间分配给代码和堆栈以外的部分内存。

传统上，操作系统和运行时库随附了堆实现。当进程开始时，操作系统创建称为进程堆的默认堆。如果没有使用其他堆，则使用进程堆分配块。语言运行时库也可在一个进程内创建单独的堆。（例如，C 运行时库创建自己的堆。）

除这些专用堆外，应用程序或许多加载的动态链接库 (DLL) 之一也可以创建并使用单独的堆。Win32 提供了一组丰富的 API用于创建和使用专用堆。有关堆函数的优秀教程，请参阅 MSDN 平台 SDK 节点。

当应用程序或 DLL 创建专用堆时，这些堆驻留于进程空间中并且在进程范围内是可访问的。某一给定堆分配的任何数据应为同一堆所释放。（从一个堆分配并释放给另一个堆没有意义。）

在所有虚拟内存系统中，堆位于操作系统的虚拟内存管理器之上。语言运行时堆也驻留在虚拟内存之上。某些情况下，这些堆在操作系统堆的上层，但语言运行时堆通过分配大的块来执行自己的内存管理。绕开操作系统堆来使用虚拟内存函数可使堆更好地分配和使用块。

典型的堆实现由前端分配器和后端分配器组成。前端分配器维护固定大小块的自由列表。当堆收到分配调用后，它尝试从前端列表中查找自由块。如果此操作失败，则堆将被迫从后端（保留和提交虚拟内存）分配一个大块来满足请求。通常的实现具有每个块分配的开销，这花费了执行周期，也减少了可用存储区。

Windows NT的实现（Windows NT 4.0 版及更高版本）使用 127 个从 8 到 1,024 字节不等的 8 字节对齐块的自由列表和 1 个混合列表。混合列表（自由列表【0】）包含大小超过 1,024 字节的块。自由列表包含在双向链接表中链接在一起的对象。默认情况下，进程堆执行合并操作。（合并操作是组合相邻的自由块以生成更大的块的操作。）合并操作花费了额外的周期，但减少了堆块的内部碎片。

单个全局锁可防止多线程同时使用堆。此锁主要用于保护堆数据结构不受多线程的任意访问。当堆操作过于频繁时，此锁会对性能造成负面影响。

参考资料来源：百度百科-数据结构

参考资料来源：百度百科-堆

邻接表想必大家都不陌生吧，用邻接表的关键是，在每个节点存储他的父节点的id。

在每一个部门信息中都存储了他的父节点id，parent_id字段

导入数据的过程就不说了，直接来看下数据吧：

这里使用常用的几种查询方式来看下这种方案的查询

可以通过parent_id做查询条件，可以快速查询到一个部门的直属下级部门

通过部门信息中的parent_id去查相应的父节点信息就可以快速实现

这种数据存储结构下，更新数据是比较方便快捷的，添加数据时直接找准父节点的id，组织部门变更时，也直接变更父id就好了，删除时候，看自己业务是否需要删除子节点这几种情况，

路径标的要点，就是每个节点存储根节点到该节点的路径，其实我觉得和别的几种方案可以共用

在每一个部门信息中都存储了他完整的路径，path字段

导入数据的过程就不说了，直接来看下数据吧：

使用路径表，通过path这个字段查询起来是比较困难的，一般都需要使用like，CONCAT函数、REPLACE函数等做字符串的处理逻辑，查询起来比较复杂，这里不做展示了，线上服务不建议使用这种方式，查询效率低会影响到服务性能，一般建议和邻接表方式统一使用，同时添加parent_id和path字段，parent_id用来查询，path用来查看节点完整的路径

这种数据存储结构下，更新数据是比较方便快捷的，添加数据时直接找准路径就好，组织部门变更时，也直接找准路径就好，删除时候，看自己业务是否需要删除子节点这几种情况，

Closure Table，百度直译过来叫闭合表，大多数人叫做闭包表，这种方案的要点是存储公司部门信息主表中，不存储节点关系的数据，使用另一张关系表来存储节点之间的关系，其中包含了任何两个有关系（上下级）节点的关联信息

公司部门信息主表，只需要存储部门的本身信息

主要包括三个字段

要点就是关系表的一条记录是一个上级节点、下级节点、与他们之间的路径距离。拿部门结构图来举例子

总公司-企划部的关系数据是：

总公司-大区A的关系数据是：

关系表中存储所有的节点路径信息，还用distance表示路径的距离，需要把树形结构中每两个节点之间的路径信息都维护进来。

数据存储的过程就拿导入总公司-门店A的过程做个示例。主表的数据存储就不说，说下关系中，存储部门结构的路径信息，总公司-门店A总共包含以下几条路径：

看到了么，是存储了所有总公司-门店A之间的路径信息

这里使用常用的几种查询方式来看下这种方案的查询

这种数据存储结构下，更新数据比较麻烦，因为他存储了两节点直接所有路径信息（包括中间节点的）