CN103124959A - 数据对象的组合 - Google Patents

Abstract

储存及修改计算装置中数据对象的数据处理系统实施例，其中通过在数据对象的存储空间里直接插入或删除数据，对数据对象进行修改。数据对象可为固定长度或可变长度。数据对象可为嵌套类型。数据对象的长度、名称、数据类型、数值及组合可进行修改。描述并展示了其他实施例。

Description

数据对象的组合

技术领域

本发明涉及计算机及其他电子设备上的数据对象结构。具体地涉及数据对象及嵌套数据对象的组合，以及在运行时，在数据对象及嵌套数据对象中插入可变长度数据，或将可变长度数据从数据对象及嵌套数据对象中删除。

背景技术——现有技术

数据处理系统，如计算机或其他电子设备，将数据对象储存在其存储单元中，如内存区域、文档或文件区域、数据结构等等。

数据对象包括按逻辑组织的若干数据元。数据元可为初级数据对象或组组合数据对象。作为另一个数据对象组合要素的数据对象被称为子数据对象或嵌套数据对象，另一个数据对象被称为原始数据对象。

出于数据组合的目的，需区分数据对象及该数据对象的指示字。由此，

i.数据对象可被存储在另一个数据对象的存储空间内。则该数据对象被称为子数据对象或嵌套数据对象。

ii.或者，数据对象可存储在自身的存储空间内。该数据对象的指示字、参照对象、句柄或其他地址被储存在另一个数据对象中。如此，该数据对象不是另一个数据对象的组合要素。相反，指示字、参照对象、句柄或其他地址为另一个数据对象的子数据对象或嵌套数据对象。

数据对象大小不一。C语言“结构体”便是一个数据对象。数据结构及文件结构同样也可称为数据对象。包含若干数据表和索引的数据库也是一个数据对象。数据对象所需的或使用的存储空间称为数据对象的尺寸或长度。

存储单元在逻辑地址空间内提供若干顺序地址，以供数据储存之用。数据对象可储存在存储单元内，如内存区域、文件等等。某些数据结构（如数组）还可提供若干顺序逻辑地址，供数据储存之用；且还可用作存储单元，储存数据对象。

存储单元同样也具有物理地址空间，如存储页面，磁盘扇区及磁盘簇。在某些情况下，物理地址可能与逻辑地址相同。但在其他情况下，物理地址与逻辑地址不同。在此情况下，为存取数据，需保持物理地址与逻辑地址之间的关联性。

运行时怎样分配存储空间

数据对象的动态组合，包括现有数据对象的修改，需要额外的存储空间。可在许多地方找到可用的自由存储空间：

1.可通过创建一个新的存储单元，分配自由存储空间。由此，可创建一个新的内存区域或新的文件，以提供存储空间。

2.若在数据对象中预留了备用空间，则可在其中找到自由存储空间。

3.堆管理器或其他堆式动态存储管理器可提供自由存储空间。堆包含一个较大的内存区域，该内存区域可分配若干较小的次区域，用于储存可变长度的数据对象。由此，

a.C语言具有“分配内存”的功能(malloc函数)，将一个堆分配成若干字节。

b.在许多文件结构中，堆式内存管理器追踪未使用的存储区域，并不断地提供存储空间。

4.在逻辑地址空间的末尾可分配自由存储空间。例如，

a.利用文件末尾的存储空间，可在文本文件中插入若干行。

b.许多C语言编译器可实现“分配堆栈空间”的功能(alloca函数)，可在进程堆栈的顶端分配可变长度的内存区域。

每种分配内存的方法都具有其劣势。方法的选择取决于数据长度、预期的常用数据操作方式，以及速度需求。

数据对象的组合方法

目前数据对象组合的方法有许多种。方法的选择通常取决于需存储数据的特性，以及预期的数据操作方式。现有的各种数据组合方法均有其优点和缺点。没有哪一种现有的数据组合方法是完美无瑕的。当数据对象为嵌套形式时，会更加复杂。当数据对象为嵌套形式时，这些方法的很多优点都不可用。

系统效率取决于采用的数据对象之组合方法，尤其是动态组合方法，包括对现有数据对象的修改。

与原始数据对象，或原始数据对象中其他数据元相关的数据元的放置颇为重要。若一个系统中的数据对象组织有序，则该系统能以更高的效率运行。

现有的某些数据组合方法提供了数据对象在系统中的优化布置，但就数据对象的动态组合或运行时间修改而言，只提供了初步支持或未提供支持。其他方法提供了有效的数据对象动态组合和运行时间修改，但未提供数据对象的优化布置。

由于多种原因，数据对象的动态组合和修改很难同时实现。其中一些原因如下：

i.需在数据对象内维持可变长度的数据元。

ii.需在数据对象内维持数量可变的数据元。

iii.需在运行时，在数据对象（包括嵌套数据对象）内插入或删除数据元。

iv.需维持高水平的操作效率。

v.需明智而审慎地使用可用的存储空间。

vi.需保持系统无误。

vii.在分配动态内存后，需维持数据放置秩序。

viii.每种分配动态内存的方法都具有其劣势。

因此，需要一种新的数据对象组合方法。

许多书籍中描述了数据对象的组合方法。例如，

i.Kernighan和Ritchie所著的《C程序设计语言》（C Programming Language），描述了C语言中数据对象的组合方法。

ii.Aho、Hopcroft和Ullman所著的《数据结构与算法》（Data Structures andAlgorithms），描述了数据结构的组合方法。

iii.Folk、Zoellick和Riccardi所著的《文件结构：面向对象法与C++》（FileStructures，An O bject-Oriented Approach with C++），描述了数据对象的组合方法，供储存在磁盘或文件中之用。

一些常用的数据组合方法描述如下：

1.固定、相同大小的数据对象：

根据常用的数据对象组合方法，若干固定、相同大小的数据对象被储存在存储单元中的连续逻辑地址处。通过此方法，可维持一个数据对象列表。

C程序设计语言中的“数组”便是一个例子。另一个例子就是储存在文件中的数据表，包含若干固定长度的记录。可通过记录编号直接存取每条记录。每条记录的相对位置是用前面的记录计数乘以记录大小加以确定的。通过此方法，可直接存取数据对象。此方法的另一个例子便是b-树节点，其中储存有若干固定、相同大小的条目。

由于已知晓或很容易确定每个单元的长度及相对地址，此方法无需追踪数据元的长度或地址。

若可扩大存储单元的大小，且数据对象不受该存储单元内其他数据对象的束缚，则可在该数据对象内插入或删除数据。由此，

i.可在b-树节点内插入若干附加的条目，但受限于b-树节点中针对此用途预留的备用空间量。

ii.可在储存在自身文件里的数据表中插入附加记录。

此方法具有许多缺点。其中一些缺点如下：

i.不可进行超出事先预留的存储空间的数据插入。同样不可或不利于提供一个无界逻辑地址空间，来储存数据对象。

ii.若数据对象并非为固定及相同大小的，则该方法不适用。

iii.通过该方法不能在数据对象之间建立关系（如主从关系或其他关系）。

因此，该方法不适合用于数据对象的组合，尤其是嵌套数据对象的组合。

2.定界数据：

根据另一种方法，若干可变长度的数据对象被储存在存储单元中的连续逻辑地址处。各数据对象通过“分隔符”或“定界符”，与相邻的数据对象分开或划定界限。

例如，

i.在文本文件中，“换行”字符用于将一行与另一行分开。

ii.在逗号分隔文件中，逗号或其他定界符用于划定字段界限。

iii.在b-树节点中，可通过定界符将可变长度的条目与其他条目分开。

iv.xml文档中，用“<”和“/>”标记作为分隔符。

若数据对象储存在一个无界地址空间（如一个文件）中，则可在其中插入附加数据。或者，若数据区中预留了备用存储空间，则可进行插入。当在文本文件中插入或删除字符时，该文件中的后续行会移至更高或更低的逻辑地址处。

此方法具有许多缺点。其中一些缺点如下：

i.需确保“分隔符”不会与数据对象混淆。

ii.若超出了事先预留的存储空间，则不可在无界数据对象内插入或删除数据。在许多情况下，不可或不利于为数据对象提供无界地址空间。因此，b-树节点中的条目插入受到该b-树节点尺寸的限制。

iii.未追踪数据元的相对地址或长度，也不可轻易知晓这些信息。照此，通过该方法，不可直接存取数据对象。例如，在文本文件中，为读取预定行，需查看该文件中的换行符。因此，若需频繁修改数据，且数据量很大或系统效率非常关键的情况下，该方法不适用。

iv.通过该方法，不能在数据对象之间建立关系，即使是可在数据区内描述的关系。因此，不容易推测出一个数据对象与另一个数据对象之间的关系（如主从关系），且在确定此类关系前，需扫描整个数据区。

3.基于数据类型的结构：

根据另一种方法，系统维持了数据对象的“数据类型”或“数据模板”。数据类型提供了一个存储模式，用于将若干数据元存储在数据对象内。该存储模式用于确定数据元地址。

在许多程序设计语言中，采用此方法。“C”语言程序中的结构体便是此方法的一个示例。此方法同样也用于许多文件结构中。在数据对象内，分配给一个数据元的存储空间可能与分配给另一个数据元的存储空间不同。通过该系统，可直接存取数据元。数据元的地址和长度为固定的，照此，无需追踪数据元的长度或相对地址。通过该方法，可组合嵌套数据对象。

通过该方法，可管理一定量的可变长度数据。通常，预留了一个相对较大的存储空间，用于储存可变长度的数据元。例如，“学生”数据类型可包含一个30个字符宽的字段，用于储存学生的姓名。但此方法具有许多缺点。其中一些缺点如下：

i.需预先估计存储空间量。

ii.若预留的存储空间太大，会造成存储空间浪费。

iii.若需储存的数据量超过了预留的空间，则会导致数据储存失败。

4.追踪长度或地址：

根据另一种方法，一个数据对象中的若干可变长度数据元，被储存在该数据对象存储空间内的若干地址处。

可通过追踪数据元的长度，直接存取这些数据元。或者，可追踪数据元的地址。正如所了解的，这两种方法为等效的，且具有同样的作用：可存取数据元，而无需扫描数据。为实现追踪数据元的长度或地址，可储存地址、偏移量、长度、累计长度、数据偏移或其他相关信息。

例如，在b-树节点中可储存若干可变长度条目。可通过许多方式进行此操作，其中一些如下：

i.在各条目的开始端储存一个长度指示符。

ii.在该节点内储存所有条目的长度指示符，后接相应条目。

iii.在该节点内储存这些条目的偏移量，后接相应条目。

iv.在该节点内储存这些条目的累计长度，后接相应条目。

若保留了相应的备用存储空间，则可在数据对象内插入或删除一定量的数据。从而可在现有数据对象中添加、插入或删除若干附加数据元。同样，可不时增加或减小数据元的长度。此方法在一些b-树中使用，以维持b-树节点中可变数量的条目。

该方法具有几个缺点。其中一些缺点如下：

i.需预先估计所需的备用空间量。

ii.若备用空间太大，会造成存储空间浪费。

iii.若需储存的数据量超过了备用空间，则会导致数据储存失败。

5.基于数组的数据对象结构

根据另一种方法，若干数据对象被储存在线性存储空间内。数据对象之间建立了某种关系，所以一个数据对象与若干其他数据对象相关。

例如，Aho、Hopcroft和Ullman描述了一堆数组中树型数据结构的组合方法（见艾迪生-威斯利出版社（Addison Wesley Publishing Company）1983年版《数据结构与算法》中“树的数组表示法”章节，第84页）。作者同样描述了遍历该树型的方法。在此，阐述了该树型中某个树节点与若干子树节点之间的关系。

在某些情况下，可通过在文件的末尾储存新数据，从而插入及删除数据。由此，例如某个文件某条记录中的“学生”字段可通过下述方式，被更大的字段替代：

i.在该文件的末尾分配一个新数据区域，用于储存更大的新字段。

ii.使该文件中数据对象内的现有字段无效，且

iii.在该字段位置，储存指示字，指示该文件末尾的新数据区域。

但采用该方法插入或删除数据，存在许多缺点：

i.使用该方法，每当对数据进行修改时，便会产生许多小的数据区域，导致无法存取数据。

ii.采用该方法，不可保持访问局部性，会导致大量的页面错误和高速缓存缺失，以及系统操作无效。

iii.当对数据进行修改时，在该文件中产生若干不用的、失效的数据区域。

iv.数据并未保持在最优化状态。每次修改，会使数据越来越无序。

v.必须定期将数据按正确次序重写到新的文件中，以重新获得操作的有效性。

6.重新创建数据对象

根据该方法，通过在插入、删除或修改新的数据元时重新创建数据对象，数据对象可维持可变长度数据。例如：

i.在C语言中，一个数组可储存固定数量的单元。为插入附加单元，可通过分配新的内存空间创建一个新的数组。随后，将原数组中的若干已有单元及新单元一并复制到新的数组中。之后，通常将原数组废弃，取而代之的是新数组。

ii.为在文件中插入数据元，可将原始文件中的内容，以及新数据元一并复制到新的文件中。之后，通常将原文件废弃，取而代之的是新文件。

由于该方法涉及存取或复制大量的数据，因此采用该方法效率很低。

由于上述缺点，以上讨论的所有方法均不适合用于数据对象的动态组合，尤其是嵌套或大数据对象的动态组合。

7.基于堆的数据储存

根据另一种方法，采用从堆分配的存储空间储存可变长度数据。数据对象自身不存储数据。反而，数据对象储存数据的指示字、参照对象或其他句柄。出于数据组合的目的，指示字、参照对象或其他句柄为数据对象的子单元。

由此，此方法能使可变长度数据储存在数据对象内。而无需预先了解数据的长度。因此，该方法比上述的其他方法更灵活。

此方法同样也用于许多文件结构中。该方法的另一个例子便是文件中的b-树结构。在b-树中，使用堆式动态内存管理器追踪不用的存储区域，以对存储空间进行动态分配。

但该方法同样具有数个缺点。其中一些缺点如下：

i.该方法需要管理堆中不用的存储区域。

ii.该方法要求管理并追踪数据元，会造成许多故障。

iii.该方法导致存储空间片段化，页面错误及高速缓存缺失增加，从而使系统运行变缓。

iv.未保持访问局部性，从而导致效率低。

v.该方法导致产生无法使用的存储空间区域。

vi.通常不能使数据储存在最优位置。

发明目的

本发明的目的在于提供一个数据处理系统，其中储存有若干数据对象，且可进行许多操作，如下所述。该数据处理系统中的数据对象包含了若干固定或可变长度的数据元。数据对象可为嵌套类型。在数据对象中可直接存取数据元。数据对象中的数据元可通过其索引或名称存取。

根据本发明，提供了一种方法，可通过在数据对象中插入或删除存储空间，组合数据对象，并在运行时修改数据对象。采用该方法，不需要堆。采用该方法，同样也无需预留备用存储空间。通过该方法，可将数据元按逻辑顺序及有效顺序放置在数据对象中。即使在插入或删除了若干数据元后，仍保持了访问局部性。

可不时修改数据对象的长度、数据类型、名称或数值。还可在数据对象中插入或删除若干数据元。同样可在嵌套数据对象内进行修改。该方法能表示并维持一个数据对象与另一个数据对象，或其他多个数据对象之间的关系。

本发明的优点：

本发明具有许多优点。

i.该方法能储存可变长度数据，而无需使用指示字。一个数据对象可由数量不定的数据元组合。数据对象的长度可不时变化。不要求数据元为固定或相同大小。

ii.该方法支持嵌套数据对象中的数据插入和删除。无需预留备用空间，以支持附加数据插入。

iii.该方法支持数据元在最优位置储存。

iv.该方法可使系统更有效地运行。

v.通过该方法可直接存取数据元，即使是在插入或删除数据之后。

vi.该方法可通过数据元名称或索引，存取数据元。

vii.碎片、页面错误及高速缓存缺失降低。即使是在插入或删除数据后，也可维持访问局部性。

viii.无需维护或管理动态分配的存储空间。

ix.堆内无法使用的存储区域问题减少。

x.该方法可用于修改数据元的数据类型。

xi.该方法可用于维护缺失数据元的缺省值。

附图

在说明书附图中，密切相关的图编号相同，但字母后缀不同。

图1展示了依照本发明实施例的数据处理系统。

图2展示了可变长度数组VA，在其运行中，可插入或删除若干数据元。

图3为流程图，展示了在可变长度数组VA中插入或删除附加数据元的方法。

图4展示了可变型数据对象VTDO，用于储存数据元，该数据元的数据类型可进行不时修改。

图5为流程图，展示了用于修改储存在可变型数据对象VTDO中的数据元的数据类型的方法。

图6A及图6B展示了在将数据对象插入数据处理系统之前及之后，存储单元内的数据对象布局。

图7展示了组合数据对象GO，其中可储存、修改、插入及删除若干可变长度的数据对象。

图8为流程图，展示了在组合数据对象CO中插入附加数据对象的方法。

图9为流程图，展示了在嵌套数据对象中插入附加数据元的方法。

图10A、10B、10C和10D展示了分级数据结构HDS，其中的数据元分级布局。

图11展示了一个数据处理系统，其中数据储存在一个具有可变尺寸页面的虚拟内存区域。

图12为使用虚拟内存区域，在数据处理系统中插入附加数据的流程图。

图13展示了一个数据处理系统，其中数据储存在一个具有固定尺寸页面的虚拟内存区域。

附图-参考图号

101       数据处理系统              706        单元名称字段

102       存储单元                  707        数据空间字段

103       数据对象                  801-806    流程图步骤

104       逻辑地址                  901-904    流程图步骤

201       可变长度数组VA            1001       分级数据结构HDS

202       Len(长度)字段             1002-1013  HDS内节点

203       数据空间字段              1101       数据处理系统

301-303   流程图步骤                1102       数据对象

401       可变型数据对象VTDO        1103       虚拟内存区域

402       数据类型字段              1104       逻辑地址空间

403       数据空间字段              1105       页面列表

404       数据元                    1106       内存管理单元

501-505   流程图步骤                1201-1203  流程图步骤

601-605   数据对象                  1301       数据处理系统

603A-603D 数据对象603中的数据元     1302       数据对象

611-651   逻辑地址                  1303       虚拟内存区域

701       组合数据对象              1304       逻辑地址空间

702       单元数字段                1305       页面列表

703       数据对象管理器            1306       内存管理单元

704       单元大小字段              1307       页面交换设备

705       数据类型字段

发明描述

根据本发明的优选实施例，提供了一个用于储存若干数据对象的数据处理系统。

提供了在运行时修改数据对象的方法。可在数据对象中插入附加数据，借此插入一个或多个附加数据元，和/或增加数据对象的长度。同样地，也可删除数据对象中的现有数据，借此删除数据处理系统中的一个或多个数据对象，和/或减少数据对象的长度。

以下为数据插入步骤：

i.在存储单元内识别一个逻辑地址，用于储存附加数据。

ii.在存储单元中插入附加存储空间，以将附加数据储存在已识别的逻辑地址处。由此，可将储存在前述逻辑地址之外的一个或多个现有数据对象，从现有的逻辑地址移至更高的逻辑地址。

iii.将附加数据储存在插入的存储空间中，由此，在系统中插入附加数据对象，或增加数据对象的长度。

iv.附加数据对象也可作为另一个数据对象的子对象插入。若该数据对象作为子数据对象插入，则原始数据对象的长度也会由此增加。

删除数据元的步骤与上述内容相反。

插入或删除数据过程中，储存在原始数据对象存储空间内，但在插入点或删除点之外的若干数据元，可重新移位至存储单元内新的逻辑地址。该存储单元中的若干其他数据对象同样也可重新移位至新的逻辑地址。

数据对象管理器可根据需要，将相对地址、长度、数据类型，或与数据元相关的其他信息储存在数据对象中，以追踪数据对象的地址。由此，可直接存取数据对象。在插入或删除数据的过程中，数据对象管理器得到更新。

数据对象管理器将若干数据对象名存储在系统或一个数据对象中。该方法可通过数据元的名称存取数据元。同样也可不时修改数据对象的名称。

数据对象管理器储存了数据对象的数据类型。同样也可不时修改数据对象的数据类型。数据对象的数据类型或数据模板可用于确定该数据对象的结构。数据对象的数据类型同样可用于确定该数据对象中缺失数据元的缺省值。

同样展示了分级储存若干数据元的方法。

其他实施例展示了该方法的使用，数据存储在其中的虚拟内存区域内。

数据处理系统将数据对象储存在存储单元内，可在其中有效地插入或删除数据，如下文所述。

数据对象组合的存储单元

最常用的存储单元不能有效地插入或删除数据。一般而言，在存储单元内插入或删除数据所花的时间，取决于该存储单元内插入点或删除点之外的数据量。因此，若在存储单元内插入点之外的数据量较大，相应地，插入数据所花的时间越长。这使得数据插入和删除不切实际。在这些存储单元内的插入及删除操作称作命令O（n），其中n为存储单元内的数据量。

但其他一些存储单元可提供有效的数据插入或删除。在这些存储单元内，插入或删除操作所花的时间不取决于插入点或删除点之外的数据量。这些存储单元的一些例子如下：

i.本申请人的发明（专利申请号PCT/IN2010/000259）描述了一个可用于在存储单元内有效插入和删除数据的存储系统，如文件系统和内存系统。

ii.本申请人的发明（专利申请号PCT/IN2010/000641）描述了一个使用可变尺寸页面的虚拟内存系统，并介绍了虚拟内存系统内的有效数据插入和删除。

iii.Sinclair和Alan Welsh描述的优化了Flash的文件系统（专利申请号PCT/UD2007/088165），为可在基于flash的文件系统中提供有效数据插入或删除的文件系统。

iv.Simon Tatham描述的被计数的b-树是b-树数据结构的一种形式，可支持未排序b-树内指定索引处的项插入或删除。

（http：//www.chiark.greenend.org.uk/～sgtatham/algorithms/cbtree.html）.

该类其他的存储单元将插入点或删除点之外的数据，重新移位至新的地址，而无需存取或复制该数据。反而，这些存储单元是通过从其逻辑地址分离此类数据的物理地址，并将这些物理地址与新的逻辑地址结合，而重新移位数据。因此，这些存储单元可提供更高效的数据插入或删除。由此，

i.本申请人的发明（上述第i.项）中所述的存储单元（如文件或内存区域）提供了若干逻辑地址，用于储存数据。该存储单元还包含可变大小的存储块列表，在这些存储块中可实现数据的物理存储。存储块中同样也可包含备用容量。这些存储块内的地址被映射到逻辑地址空间中。存储块中数据的逻辑地址取决于之前的存储块内的使用容量。

由此，存储单元可维持其存储块内的备用容量。可通过在列表中插入附加存储块，从而在存储单元中插入附加的备用容量。当在文件中插入数据时，便占用了备用容量。

插入完成后，存储单元内插入点之外的数据可被重新移位至更高的逻辑地址。因此，重新移位无需将数据从其物理地址处复制或移动至新的物理地址处。重新移位的数据的存储块及物理地址仍保持不变。

本申请人的发明（上述第ii.项）中所述的虚拟内存系统中，使用映像装置如页表或转换后备缓冲器（或TLB），若干可变尺寸页面可被映射到虚拟地址区域。

在该系统提供的虚拟内存区域，可通过取消虚拟地址空间若干页面的映射，并将这些页面重新映射到新的虚拟地址空间，从而在预定点插入附加数据。因此，这些页面中的数据重新移位至新的逻辑地址，而无需将此类数据从其物理地址移至新的逻辑地址。在插入点映射一个或多个附加页面，为插入的数据提供存储空间。由此，无需从数据的物理地址处复制或移动大量的数据，便可在内存区域内插入或删除数据。

优化了flash的文件系统（上述第iii.项）描述了一种方法，通过重新映射若干物理地址到若干新的文件地址，在基于flash的存储媒介内的文件中插入数据。在插入操作中，储存在插入点之外的若干数据对象无需重新物理移位至物理媒介中的新地址。

被计数的b-树（上述第iv.项）将若干条目储存在若干节点中。可在被计数的b-树中某个索引处储存、检索、插入和删除某一条目，无需使用密匙。

将字节作为条目储存在b-树中，可创建一个逻辑地址空间。这些条目的索引可被认作是数据的逻辑地址。被计数的b-树可用作存储单元，用于数据组合。

b-树中的各节点可看作是存储块，可提供储存条目的若干物理地址。节点中储存条目的各物理地址，与逻辑地址或b-树中的索引有关。

当在b-树中插入新的条目时，少数节点内的小部分条目重新排列。这导致在插入点之外索引处的多个条目被移至更高的索引。由此，通过改变物理地址与逻辑地址之间的联系，可将被计数的b-树中的若干条目重新移位至更高的地址。在插入操作中，未存取或物理复制多个的条目。

此类其他存储单元内数据插入和删除效率命令优于O（n），其中n为该存储单元内的数据量。例如，在b-树（及被计数的b-树）内数据插入和删除效率称作命令O（1og n）。

现有数据对象组合方法未利用此类其他存储单元的性能。本申请人的发明建议利用这些存储单元提供的快速插入及删除数据的性能。根据本发明，用于储存数据对象的存储单元，同样也可为不具上述低效率的任何其他存储单元。

发明的详细描述

将结合附图说明本发明。

图1中阐明数据处理系统的优选实施例。数据处理系统101包括存储单元102和存储单元内连续逻辑地址104处所存多个数据对象103。

存储单元102为一个文件、内存区域、数据结构或其他存储单元，能按上文所述有效地插入和删除数据。

数据处理系统中的数据对象103可为预先存在的数据对象或在运行时创建的数据对象。数据处理系统中的数据对象可为‘结构体’、‘数组’‘基于长度的’数据对象、数据结构、文件结构、或上文所述任一其他数据类型、或下文所述任一数据对象的一个实例等等。数据对象也可为另一个数据对象的子数据对象。

下文结合附图说明数据处理系统相关若干操作。

图2显示了可变长度数组VA201的数据模板。VA201为一个组合数据对象，用于将多个固定大小的数据元存储到存储空间。VA201包括：

i.Len字段202；和

ii.数据空间字段203。

数据空间字段203表示为存储VA201内多个单元而预留的空间。Len字段202为一个整数字段，用于存储数据空间字段203的长度。

但是，数据空间字段203未预留任何备用空间。

创建一个VA实例时，创建足够大的数据空间字段，以存储预定数量的固定大小的记录。数据空间字段的长度存储在Len字段内。VA所分配的总存储空间等同于数据空间字段长度和Len字段长度总和。数据元存储于数据空间字段内。

可随时将附加的数据元插入VA。图3为数据元插入VA的方法流程图。相应地，

i.步骤301，将附加的存储空间（等同新记录大小）插入存储单元102，由此

a.将在插入点及其以外数据处理系统102内一个或多个现有数据对象移动至更高的

地址；且

b.增加数据空间字段303长度；

ii.步骤302，更新Len字段值；且

iii.步骤303，将新数据元存储到数据空间字段。

删除VA内数据元的步骤与插入数据元的步骤相反。

附加存储空间插入数据空间字段时，将插入点处及其以外数据单元102内一个或多个数据对象移到更高地址，且增大VA。同样地，删除VA内存储空间时，将插入点以外一个或多个数据对象移到更低地址，且减小VA。

修改VA长度时，将VA内现有的一个或多个数据元移到新地址。相应地，若VA自身为另一数据对象的子数据对象，数据元插入或删除VA时，可重新定位原始对象内一个或多个数据元。

图4显示了一个可变型数据对象VTDO401。VTDO401用于存储单一数据元。VTDO401内存储的数据元的数据类型可随时变化，如下文阐释。

如图4所示，VTDO401包括：

i.数据类型字段402；

ii.数据空间字段403；和

iii.数据元404。

数据类型字段402用于存储数据元404的数据类型。

根据数据类型字段402内存储的数据类型，数据空间字段403表示存储数据元404的预留空间。

数据元404存储于数据空间字段403内。

创建一个VTDO实例时，数据类型字段用于存储预定数据类型。为数据空间字段提供足够的存储空间，以存储一个预定数据类型的实例。VTDO所分配的总存储空间等同于数据类型字段所分配的存储空间和数据元大小的总和。

可随时修改数据元404的数据类型。图5为修改数据元的数据类型的方法流程图。相应地，

i.步骤501，将新数据类型存储到数据类型字段。

ii.步骤502，对比新数据类型的存储要求与已分配至数据空间字段的存储空间数量。

iii.步骤503，若新数据类型的存储需要大于现有数据空间字段长度，将附加存储空间插入数据空间字段，由此增大VTDO。

iv.步骤504，若新数据类型的存储需要小于现有数据空间字段长度，将多余存储空间删除数据空间字段，由此减小VTDO。

v.步骤505，根据新数据类型，将数据元值存储到数据空间字段。

由于插入或删除存储空间，可将数据处理系统101内VTDO外存储的多个数据对象移到数据单元内新逻辑地址。

图6A和6B显示了插入数据对象前后，存储单元内典型的数据处理系统内数据对象布置。

图6A显示了插入前多个数据对象的地址。相应地，数据对象601、602、603、604和605的存储地址分别为存储单元611至622，623至630，631至635，636至643，和644至650。数据对象603为可变长度数组VA，且为数据元603A、603B、603C和603D的原始对象。VA的Len字段存储在地址631处。数据元603A、603B、603C和603D的存储地址分别为632、633、634和635。

图6B显示了附加数据元插入数据对象603后的数据对象地址。在数据元603C后，将附加数据元603E插入数据对象603。数据对象601、602、603、604和605现在的存储地址分别为611至622，623至630，631至636，637至644，和645至651。VA的Len字段的存储地址为631。数据元603A、603B、603C、603E和603D（在数据对象603内）的存储地址分别为632、633、634、635和636。

图7显示了组合对象CO701。其为一个存储多个可变长度数据元的数据对象。CO内数据元数量不固定。可随时将多个数据元插入CO或从CO删除。CO内数据元的大小可变。不要求一个数据元与另一个数据元的大小相同。可随时修改数据元的大小。

如图7所示，CO701包括

i.单元数字段702；

ii.数据对象管理器703；

iii.数据空间字段707。

数据对象管理器703包括

i.单元大小字段704；

ii.数据类型字段705；和

iii.单元名称字段706。

单元数字段702为一个整数字段，用于存储CO内单元计数。CO内单元插入或删除时，此字段内值更新。

数据对象管理器703用于跟踪CO内所存数据元的长度、数据类型和单元名称。

单元大小字段704为VA201的一个实例，且用于存储一个整数列表。本数组内各条目表示CO内存储的相应数据元的大小。

数据类型字段705为VA201的一个实例，且用于存储一个数据类型列表。本数组内各条目表示CO内相应数据元的大小。

单元名称字段706为VA101的一个实例，且用于存储一个名称列表。本数组内各条目表示CO内相应数据元的名称。

数据空间字段707表示用于存储CO内多个单元的预留空间。数据空间字段707未预留任何备用空间。

CO内所存数据元可通过其索引或位置获取。数据元的相对地址可通过合计先前数据元的大小找到。数据元可在数据空间字段内的相对地址处获取。

CO内所存数据元也可通过其名称获取。各数据元名称可在单元名称字段内找到。

通过下列步骤创建一个空的CO实例：

i.设置单元数字段值为零；

ii.创建一个空单元大小字段；

iii.创建一个空数据类型字段；

iv.创建一个空单元名称字段；和

v.创建一个空数据空间字段。

可随时将多个数据元插入CO。图8显示了将附加数据元插入到CO内预定索引处的方法流程图。相应地，

i.步骤801，单元数字段值为递增的；

ii.步骤802，在预定索引的单元大小字段插入一个整数值，以表示新数据元的大小。

iii.步骤803，在预定索引的数据类型字段插入一个数据类型值，以表示新数据元的数据类型。

iv.步骤804，在预定索引的单元名称字段插入一个名称值，以表示新数据元的名称。

v.步骤805，将等于新数据元大小的存储空间插入数据空间字段的适当位置，由此

a.增加数据空间字段长度；且

b.将插入点处及其以外现有数据元移到更高的地址；

iv.步骤806，将新数据元存储到步骤805中插入的存储空间。

删除CO内数据元的过程与插入数据元的过程相反。

附加存储空间插入CO时，将数据对象界限及其以外一个或多个数据移到更高的地址。多余存储空间从VA1删除时，将数据对象界限及其以外一个或多个数据移到更低的地址。

相应地，可修改一个或多个数据元的地址。类似地，若此数据对象本身为另一个数据对象的子对象，存储空间插入CO时，可修改原始对象内一个或多个数据元的地址。

嵌套数据对象的大小也可随时修改。例如，VTDO为存储在CO内预定索引处的嵌套数据元。修改数据元大小时，更新单元大小字段内的相应条目。此方法确保数据插入或删除后，可从现有地址或新地址获取全部数据对象。相应地，可随时将数据插入数据对象或从数据对象中删除，包括嵌套数据对象。

图9显示了将附加数据元插入嵌套在CO内的嵌套数据对象的流程图。相应地，

i.步骤901，将附加数据元插入嵌套数据对象以增加嵌套数据对象的长度。相应地，

将嵌套数据对象以外存储单元内一个或多个数据对象移到新地址。下一步骤为步骤902。

ii.步骤902，更新CO内单元大小字段内的数据对象长度。下一步骤为903。

iii.由于步骤901和902，原始数据对象CO的大小也修改了。步骤903，若CO嵌套在另一数据对象内，采取步骤902在其原始数据对象的单元大小字段内更新CO的新长度。下一步骤为904。

iv.步骤904，完成数据插入嵌套对象的过程。

可能会发生若干变更。例如，

i.在CO内的数据对象管理器中，可用单元地址字段代替单元大小字段。单元地址字段持续跟踪CO内所存数据元的相对地址。

ii.数据类型字段可用于跟踪数据类型，及由此产生的数据元的长度。在这种情况下，则不必跟踪单元大小字段。

iii.若各数据元的数据类型相同或可另行确定，则不必跟踪数据类型字段。

iv.若不要求通过名称获取数据元，则不必跟踪单元名称字段。

v.本方法易改善，以向缺失数据元提供默认值。例如，可在数据对象的数据模板内定义数据对象内缺失单元的默认值。

图10A和10B显示了本发明的分层数据结构HDS1001。分层数据结构HDS1001为数据对象，其中在层次结构中布置了多个数据元。在层次结构中的各数据元为节点，且节点可能有分节点。

图10A显示了HDS内节点间关系的示意图。根据图10A，节点1002为层次结构的根节点。节点1002有三个分节点，即为节点1003、1004和1005。节点1003有两个分节点，即为节点1006和1007。节点1004有三个分节点：节点1008、节点1009和节点1010。节点1005有两个分节点：节点1011和节点1012。各节点的长度为10字节。

各节点有一个索引。节点的索引为与层次结构内其他节点有关的位置，遍历时使用层序遍历或广度优先遍历。相应地，节点1002、1003、1004、1005、1006、1007、1008、1009、1010、1011和1012的索引分别为1、2、3、4、5、6、7、8、9、10和11。数据对象内节点的地址由其索引确定。

图10B显示了存储单元内节点的地址。相应地，节点1002、1003、1004、1005、1006、1007、1008、1009、1010、1011和1012的存储地址分别为10、20、30、40、50、60、70、80、90、100和110。

图10C和图10D显示了附加节点插入层次结构后的层次数据结构HDS1001。

图10C显示了层次数据结构HDS1001示意图。相应地，附加节点（即节点1013）作为分节点，在分节点1008后被插入分节点1004。

图10D显示了附加节点插入后的节点地址。附加节点插入后，节点1002、1003、1004、1005、1006、1007、1008、1013、1009、1010、1011和1012的索引分别为1、2、3、4、5、6、7、8、9、10、11和12。节点1002、1003、1004、1005、1006、1011、1007、1008、1009和1010的存储地址分别为10、20、30、40、50、60、70、80、90和100。

若数据元大小未固定且大小可变，可较灵活地表示数据对象之间的关系。上文中已详述了可变大小的数据对象的使用方法。

图11显示了本发明的另一个优选实施例。相应地，数据处理系统1001包括

i.多个数据对象1102；和

ii.虚拟内存区域1103；

虚拟内存区域1103包括

i.逻辑地址空间1104；

ii.页面列表1105；和

iii.内存管理单元1106。

虚拟内存系统内页面列表1105由若干页面组成，且各页面提供了多个物理地址以存储虚拟内存区域内的数据。

页面大小不固定，且页面大小可不同于列表中另一页面的大小。

内存管理单元1106包括一个页面表、TLB或其他装置。其他装置用于将一个页面中的多个物理地址映射到虚拟内存区域中的多个逻辑地址。该内存管理单元能将多个可变大小页面映射到逻辑地址空间。例如，可能使用本申请人的发明(专利申请号PCT/IN2010/000641)中所述内存管理单元。

页表条目内各可变大小页面与一个逻辑地址有关。内存管理单元用于将一个页面映射到其相关的逻辑地址。一个页面的逻辑地址由列表中预定页面内多个字节决定。

多个附加字节可随时插入虚拟内存区域。图12显示了多个附加字节插入虚拟内存区域的流程图。相应地，

i.步骤1201，通过使用‘不存在’值标记相应的页表条目，取消映射内存管理单元内的多个页面。

ii.步骤1202，将一个或多个大小适当的附加页面插入页面列表。这会致使

a.将列表内一个或多个页面移到更高的逻辑地址；和

b.将附加数据插入虚拟内存区域。

iii.步骤1203，通过使用‘存在’值标记相应的页表条目，将列表内一个或多个页面映射到虚拟内存区域。

删除虚拟内存区域数据的方法与上文所述相反。

本方法用于将附加数据对象插入或从数据处理单元删除。上文已描述了数据插入数据处理单元的其他详情。

可能会发生若干变更。例如，图13显示了数据处理系统1301。相应地，数据处理系统1301包括：

i.多个数据对象1302；和

ii.虚拟内存区域1303；

虚拟内存区域1303包括

i.逻辑地址空间1304；

ii.页面列表1305；和

iii.内存管理单元1306；和

iv.页面交换装置1307。

页面列表1305由多个固定大小页面组成。内存管理单元1306可为任一将固定大小页面映射到虚拟内存区域的内存管理单元。

内存系统也包括页面交换装置1307。页面交换装置1307为本申请人的发明（PCT/IN2010/0000259）中所述的一份文件。如先前讨论的那样，该文件支持有效地插入和删除数据。该页面交换装置通过使用磁盘空间扩展逻辑地址。该页面时常位于物理内存或页面交换装置内。

通过以下方式可将多个附加字节插入虚拟内存区域：

i.使内存管理单元内一个或多个页表条目无效，和取消逻辑地址空间到一个或多个页面的映射；

ii.通过下列方式将附加存储空间插入文件：

a.使用存储块内备用容量；或

b.通过插入一个或多个存储块的方式，将附加备用容量插入本文件；

iii.将一个或多个页面映射到逻辑地址空间。

上文中已描述了修改数据对象的其他详情。

结论、后果和范围

相应地，各实施例的数据处理系统可用于有效地创建大型和复杂的数据对象。

数据处理系统可为操作数据和数据对象的任一系统。数据处理系统可用于应用程序和系统程序。

本方法可用于广泛而多样的系统。本方法可用于编译程序或解释程序。本方法可用于编译工具、数据库系统、文字处理系统、文件系统、虚拟内存系统、网络系统和设备等。本方法也对实现数据结构、文件结构和数据库有用。本方法也可用于附加数据插入进程堆栈。本方法也可用于以有效的形式存储xml数据，其中可直接操作此数据。

本数据可存储在电脑、其他计算装置上，或分布式环境中任何合适的存储单元内，包括内存区域、字段、数组和其他数据结构。

Claims (14)

1.一种处理数据的方法，包括：

a.提供包含用于存储数据的多个连续逻辑地址的存储单元；

b.提供存储在所述存储单元内的多个固定或可变长度数据对象；和

c.修改所述存储单元内的数据，数据修改的特征在于

i.将预定逻辑地址附加存储空间插入所述存储单元；

ii.将存储于所述预定逻辑地址处及其以外的多个数据对象重置于所述存储单元内的新逻辑地址；

iii.若需要，将附加数据存储到所述存储单元；和

iv.跟踪一个或多个数据对象的新地址或新长度。

2.根据权利要求1所述的方法，其中所述数据修改的性质为：

a.将附加数据对象插入所述存储单元；或

b.将数据元插入数据对象；或

c.将数据对象从所述存储单元中删除；或

d.将嵌套数据对象从其原始数据对象中删除；或

e.修改数据对象长度；或

f.修改嵌套数据对象长度和其原始数据对象长度；或

g.修改数据对象的数据类型；或

h.重命名数据对象。

3.根据权利要求1所述的方法，其中表明了数据对象与所述存储单元内一个或多个其他数据对象的关系，以及原始数据对象与其子数据对象的关系。

4.根据权利要求1所述的方法，其中所述存储单元为虚拟内存区域、文件、数组、被计数的树或其他数据结构。

5.根据权利要求1所述的方法，其中将存储于所述预定逻辑地址处及其以外的一些或全部数据重置到所述存储单元内的新逻辑地址

a.未复制上述数据；或

b.未获取上述数据。

6.根据权利要求1所述的方法，其中：

a.所述存储单元还包括多个物理地址；

b.一个或多个所述物理地址与所述存储单元内所述一个或多个逻辑地址有关；

c.通过下列方式将存储于所述预定逻辑地址处及其以外的一些或全部数据重置于所述存储单元内的新逻辑地址；

i.使一个或多个物理地址分离开所述存储单元内一个或多个逻辑地址；且

ii.使上述一个或多个物理地址与所述存储单元内一个或多个新逻辑地址重新联系。

7.根据权利要求6所述的方法，其中：

a.所述存储单元还包括一个或多个存储块，且

b.所述物理地址包括在所述存储单元内一个或多个存储块内。

8.一种处理数据的装置，包括：

a.包含用于存储数据的多个连续逻辑地址的存储单元；

b.存储在所述存储单元内的多个固定或可变长度数据对象；和

c.修改所述存储单元内的数据的装置，数据修改的特征在于

i.将预定逻辑地址附加存储空间插入所述存储单元；

ii.将存储于所述预定逻辑地址处及其以外的多个数据对象重置于所述存储单元内的新逻辑地址；

iii.若需要，将附加数据存储到所述存储单元；和

iv.跟踪一个或多个数据对象的新地址或新长度。

9.根据权利要求8所述的装置，其中数据修改的性质为：

a.将附加数据对象插入所述存储单元；或

b.将数据元插入数据对象；或

c.将数据对象从所述存储单元中删除；或

d.将嵌套数据对象从其原始数据对象中删除；或

e.修改数据对象长度；或

f.修改嵌套数据对象长度和其原始数据对象长度；或

g.修改数据对象的数据类型；或

h.重命名数据对象。

10.根据权利要求8所述的装置，其中表明了数据对象与所述存储单元内一个或多个其他数据对象的关系，以及原始数据对象与其子数据对象的关系。

11.根据权利要求8所述的装置，其中所述存储单元为虚拟内存区域、文件、数组、被计数的树或其他数据结构。

12.根据权利要求8所述的装置，其中将存储于所述预定逻辑地址处及其以外的一些或全部数据重置到所述存储单元内的新逻辑地址

a.未复制上述数据；或

b.未获取上述数据。

13.根据权利要求8所述的装置，其中：

a.所述存储单元还包括多个物理地址；

b.一个或多个所述物理地址与所述存储单元内所述一个或多个逻辑地址有关；

c.通过下列方式将存储于所述预定逻辑地址处及其以外的一些或全部数据重置于所述存储单元内的新逻辑地址；

i.使一个或多个物理地址分离开所述存储单元内一个或多个逻辑地址；且

ii.使所述一个或多个物理地址与所述存储单元内一个或多个新逻辑地址重新联系。

14.根据权利要求13的装置，其中：

a.所述存储单元还包括一个或多个存储块，且

b.所述物理地址包括在所述存储单元内一个或多个存储块内。

Images