CN1271442A

CN1271442A - 数据库结构

Info

Publication number: CN1271442A
Application number: CN98809345A
Authority: CN
Inventors: U·M·隆斯特伦
Original assignee: Telefonaktiebolaget LM Ericsson AB
Current assignee: Telefonaktiebolaget LM Ericsson AB
Priority date: 1997-07-21
Filing date: 1998-07-07
Publication date: 2000-10-25
Also published as: US6249788B1; WO1999005617A2; JP2001511563A; BR9810766A; SE510000C2; KR20010022028A; EP0996902B1; WO1999005617A3; SE9702761L; SE9702761D0; EP0996902A2; AU8365198A

Abstract

本发明涉及数据库内存储数据信息的一种结构,在该种结构内数据信息以节点层次结构组织,该层次结构由树结构组成。该树结构包括一个根节点(1),可能的一个或者多个中间节点(2,3),和一个或者多个叶节点(4),其中根节点(1)包括一个或多个根元素(1E),各中间节点(2,3)包括一个或者多个中间元素(2E1,2E2,2E3,…),各叶节点(4)包括一个或者多个叶元素(4E1,4E2,4E3,…)。各元素包括保持该树结构在一起所必需的、和能在该树和数据信息中执行搜索的地址信息。一个节点内的元素的顺序是关于数据信息的逻辑顺序,诸如数字或字母顺序,这里各元素中的数据信息组成相对于在该层次结构中前一元素内的数据信息的数据信息差。在根元素内的数据信息组成一个开始值。该开始值是实际数据信息,其余元素内的差信息由表示相对于属于前一元素的数据信息的数据信息的实际差的数据字组成,而不管该差位于所述数据信息内的什么位置。

Description

数据库结构

本发明涉及在数据库内存储数据信息的结构。

当数据信息以，形成B树的节点层次组织时其结构是适宜的。这种树包括根节点，可能有一层或者多层中间节点，和一个或者多个叶节点。

根节点包括根元素，各中间节点分别包括一个或者多个中间元素，而各叶节点分别包括一个或者多个叶元素。

通过把一个中间节点内的第一中间元素与根元素、或与位于该层次结构中较高级的一个中间节点内的中间元素连接而构造B树。在该中间节点内的其余中间元素连接到该第一中间元素。

类似地，各叶节点内的第一叶元素要么连接到根元素，要么连接到一个中间节点的中间元素。叶节点内的其余叶元素连接到该第一叶元素。各元素包括该连接的地址信息和数据信息。

在一个节点内的元素的顺序是相对于数据信息的逻辑顺序，诸如字母或数字顺序。

各元素中的数据信息组成相对于属于在层次结构中前一元素的数据信息的数据信息差。

很久以来就知道使用不同数据结构在数据库中存储数据。这些结构例如在所用存储空间和快速检索的可能性方面具有各种优点。

一种已知的结构基于B树，以之能使元素逻辑分布在数据库内的一个表中。

一个元素可以包括数据库内连接到一个外部键字例如一个电话号码的一个内部地址。当在表内插入一个新电话号码时，通过逻辑顺序计算将放置该电话号码的内部地址的元素。

B树的功能是在表中分布地址，使得所述地址以易于找到的方式分布。

使用B树主要建立顺序和简单的结构。

每一树以一个根节点开始，它指向另外的节点，在这另外的节点中可以基于某种判据检索希望的节点。这些节点常常包括一个键字或一个索引。

Http地址、文件名、时间印记、电话号码等都是存储在B树中的键字的例子。

还应该提到，前述节点是在意在说明存储键字或索引的层次结构的树结构中的节点，而不是在分布式数据库中的处理器节点。

还公知在逻辑顺序数据集合的场合只存储两个相互顺序数据集合之间的差信息。

例如，在图象处理中使用这一过程，此时需要存储大量信息和重放运动图片或图象，但是在相互顺序的图象之间的差别可以非常小，因此只存储这些图象之间的差别和在重放时使用这些差别。

还公知结合链接表，只存储两个互连元素之间的差别而不存储整个元素。

这需要较少存储空间，但是提供同样的信息。

还应该提到，结合例如文件名或http地址，使用不同的格式或后缀，这些可能使以简单方式说明在两个相邻节点之间的差信息变得困难。

下面的出版物说明以B树构造的信息的处理。

J.Gray，A.Reuter，所著“事务处理：概念和技术”，1993年，Morgen Kaufman出版社。

R.Bayer，K.Unterauer发表的“前缀B树”，关于数据库的ACM学报，1977年，第二卷，第一期，11-26页。

还应该提到，公知在所谓的容器(container)中存储不同元素，在容器中元素彼此顺序相连，且容器可视为单元对待。

当考虑上述现有技术的状态时，可以看到，一个技术问题在于，通过只存储相对于先前节点的差信息，提供一种在数据库中存储数据信息的结构，该种结构比公知结构需要的存储空间少得多，即使是对公知的压缩。

另一技术问题存在于提供易于高效找到希望的元素或对象的压缩结构。

另一技术问题在于提供一种结构的能力，在该种结构中数据字能以明确而简单的方式说明出现的差别。

再一技术问题在于提供数据字的结构，它以简单方式处理要存储的数据信息的不同后缀。

另一技术问题在于，当所述差不在数据信息的末尾时能够容易地表示两组数据信息之间的差，而不需要表示在数据信息中这一差别后面找到的相似性便能容易地表示。

另一技术问题在于处理压缩B树中的元素或对象的改变。

再一技术问题是能使压缩B树中的元素或对象被复制。

另一技术问题是当寻找一特定元素时加速B树的搜索。

另一技术问题是提供一种结构，在该种结构中当寻找一特定元素时数据信息的压缩提供本质上加速搜索B树的可能性。

再一技术问题是提供一种结构，它能使B树中的元素的插入和清除容易和高效，其中数据信息是被压缩的，且只包括涉及先前节点的差信息。

另一技术问题是提供一种结构，从而可通过读入超高速缓冲存储器而使包括多个元素的一个节点可供使用。

另一技术问题是提供一种结构，在该种结构中，参考不同节点和在其中包括的元素需要的地址信息量比常规上需要的少得多。

旨在解决上述一个或多个技术问题，并以在引言中所述结构作为开始点，本发明建议，根元素内的数据信息构成开始值，并且该开始值构成实际数据信息。还建议，其余元素内的差信息包括一个数据字，它表示相对于先前元素的数据信息的数据信息的实际差，不管该差在数据信息内的什么位置。

由于只存储实际差，不管该差是否在末尾，因此可以得到高度压缩结构。

根据本发明的一个实施例，通过允许差信息包括某种指令建立这种结构，这种指令例如为是否某些相对于前一元素的数据信息要被清除，和如果是的话，要去掉的东西的性质和在数据信息中的什么地方去掉，以及允许差信息包括某种指令，这种指令例如为相对于属于前一元素的数据信息是否要添加的东西的性质，如果是的话，要添加的东西的性质和在要进行这一添加的数据信息中的什么地方添加。

为提供表示差信息的压缩的或紧凑的方式，本发明建议，数据字包括头标和信息部分，其中头标表示信息部分应如何被解释。

还建议，信息部分可以包括5个不同的位组，其中：

-第一组，它在本文件中称为后缀，它表示属于该数据信息的后缀类型；

-第二组，它在本文件中称为减信息，它表示相对于前一元素要去掉的字节数目；

-第三组，它在本文件中称为加信息，它表示相对于前一元素要加上的字节数目；

-第四组，它在本文件中称为相似性，它表示除后缀外，从末尾开始相似于前一元素的字节数目；

-第五组，它在本文件中是指定的差，它组成由明文表示的要添加的字符，亦即加信息。

为能够正确解释前述各组，建议头标由3位组成：

-第一位表示第四组是否存在，亦即表示差是否存在于数据信息末尾；

-第二位表示第二和第三组是包括4位还是8位；

-第三位表示第二、第三和第五组是否存在，亦即在后缀外是否发现任何差信息。

这样，提供了一种结构，其中第一组包括5位，第二组和第三组包括4或8位，第四组包括0或8位，第五组包括表示相对于前一元素要添加的任何信息所需要的字节数目。

因此，除第五组外，当只在后缀中存在差时，所有差信息可以至少用8位，亦即1字节表示；或当所有组包括最大位数时，最多用32位，亦即4字节。

当其由加信息组成时，1到4字节，加上实际差，这相对于公知技术来说是显著的压缩。这一数量的信息需要相应于无压缩所需要的存储空间的20％。

通过5位的介质，第一组能够表示一个预定后缀表的32种不同的后缀，这将允许处理大量的后缀，而每一后缀可以只用5位表示。

在各叶元素中的数据信息还包括寻找的对象。

为处理一个对象是某事务处理的主体时的对象锁定，本发明建议，各对象包括4个不同的位组合，其中第一位组合表示该对象是否锁定。

当第一位组合表示一个对象未锁定时，第二位组合组成对象状态位，第三位组合包括有关属于一个对象的对象键字长度的信息，而第四位组合包括该对象键字。

当第一位组合表示该对象被锁定时，属于其余位组合的位表示对一个事务处理寄存器的参考。该事务处理寄存器包括对象状态位，有关属于所述对象的一个对象键字的长度的信息，该对象键字自身，有关施加在该对象上的锁的类型的信息。

状态位用于对象复制过程，此时各位指示该对象是否已经被复制。多个同时复制过程每一个使用一个单独的状态位。

为从B树中能去除元素，本发明建议，使属于一个可能的后继元素的差信息适应组成相对于位于去除的元素之前的元素的差信息，并且使属于后继元素的地址信息适应指向前一元素，和使属于前一元素的地址信息适应指向该后继元素。

相似地，当加一元素时，建议，使属于被加元素的差信息适应组成相对于前一元素的差信息，使属于被加元素的地址信息适应指向前一元素和任何后继元素，以及使属于所述可能的后继元素的差信息适应组成相对于被加元素的差信息，使属于所述后继元素的地址信息适应指向该被加元素，使属于前一元素的地址信息适应指向该被加元素。

为加速B树中搜索的可能性，本发明建议，一个节点包含一个容器，属于一个节点的各元素在所述容器中一个紧接一个分配位置。

此外，使在一个容器中的信息量适应为小于或等于可以在一次存取中读到一个超高速缓冲存储器中的信息量，超高速缓冲存储器属于在该数据库中活跃的处理器或使用该数据库的处理器。

容器大小的限制允许当存储所述信息到存储器中时保持B树所能提供的灵活性。

不管这一大小的限制，由于各元素的广泛压缩，容器能够容纳较大数量的元素。

这样，当访问存储器时，一次同时将多个元素读入超高速缓冲存储器。在通常链接表的场合，常常需要为读入的每一元素访问存储器。

此外，容器中元素的连续存储比链接表需要较少的指针，从而允许进一步压缩需要的空间。

使用较少可能地址信息的可能性是把树结构的节点最大程度地放置在一个公共页上，因为参考一页比参考其它页需要显著少的地址信息。

本发明结构具有的基本优点之一是可以表示在两个相邻节点或元素之间的任何差。当忽略必需的地址信息时，实践这一方法时必要的存储空间可以减少到为非压缩B树需要的存储空间的约20％。

本发明所具有的另一优点是可以以较少次访问存储信息的存储器而搜索B树。

于是，一个创造性树结构能优化(减少)基于链接表的数据结构中必需的地址存储空间，这里存储结构是一个有序结构，它提供通过链接表的逻辑的、较快的搜索可能性。

总之，本发明通过比原先更好地数据压缩的方法和通过在一页上重新排列的更大的可能性，结合给树添加或从中去除元素，而提供有效地处理。这些重新排列的可能性由下述事实产生，即可以通过一次访问把每一容器读入超高速缓冲存储器并在其内处理，这是非常快且高效的处理过程。

本发明结构的这一基本特征在后面的权利要求1的特征部份叙述。

为使本发明更容易理解，且使其其它特征明显起见，现在参考一个说明性实施例结合参考附图说明本发明的结构，附图中：

图1是一个略图，高度简化说明按照公知技术的元素的链接表；

图2表示以公知方式的树结构构造的按照图1的链接表的一部分；

图3概略说明打算表示两个相邻元素之间的差信息的一个数据字如何根据本发明构造；

图4概略表示一个锁定对象的构造；

图5是一个锁定对象的概略表示；

图6概略说明怎样从树结构中去除元素；

图7概略说明怎样往树结构中添加元素；

图8表示另一可选实施例，其中在容器中收集属于一个节点的元素；

图9概略表示一树如何分成一些更小的子树；以及

图10概略说明一个B树，以及表示如何通过B树实现搜索。

为使更容易理解本发明，现在使用在后面用于说明本发明的术语，说明打算用于存储数据信息的树结构。

树结构表示以树形式建立键接表的方法，以便简化和更有效地搜索表中一给定元素。

为简化B树的说明，我们使用一个例子，其中给1000个元素从0到999编号。可以把这些元素放在一个按照图1的正常的链接表A中，或按照图2的树B中，这里，一些元素E1、E2、E3、...以从0到999的号码顺序分布在一个树结构中。

当在正常的链接表A中搜索元素“312”E313时，该搜索从元素“0”E1开始，它进一步连接该搜索到元素“1”E2，等等，直到达到元素“312”E313。这导致312次搜索，不包括对第一元素“0”E1的搜索。

图2所示树结构能使同一元素通过较少次搜索找到。

图示的树有一个根节点1，它包括一个根元素1E，其值为“0-999”。该元素连接到第一中间节点2，它包括多个元素2E1、2E2、2E3、...，每一这样的元素连接到包括另外元素的另外的中间节点。图2表示元素“300-399”2E4如何连接到中间节点3。

中间节点3中的元素3E1、3E2、3E3、...依次进一步连接到一个包括多个叶元素的叶节点。图2表示叶元素“310-319”3E2如何进一步连接到包括多个叶元素4E1、4E2、4E3、...的叶节点4。

叶元素包括实际被寻找的信息。

在我们的例子中，要搜索元素“312”4E3，在图示树结构中如下进行。

首先，在第一中间节点2中通过元素2E1、2E2、2E3、...进行搜索，直到找到元素“300-399”2E4，这需要4次搜索。

然后通过第二中间节点3进行搜索，直到找到元素“310-319”3E2，这需要两次搜索。

最后，通过叶元素4E1、4E2、4E3、...，直到找到元素“312”4E3，这需要3次搜索。

这导致总共9次搜索，不包括搜索根元素“0-999”1E，在正常链接表A的情况下需要312次搜索。

在正常链接表A的情况，搜索元素“999”E1000需要1000次搜索，而在B树B的场合只需要30次搜索。另一方面，在正常链接表A的场合，元素“0”到“9”查找较快，因为在B树中到叶元素需要另外两次搜索。

还公知与链接表结合，只存储两个互连元素的差而不存储完整的元素。

这样，在图2的例子中，根元素1E可能包含数据信息“0”，在第一中间节点2中的所有元素可能包含数据信息“+100”，它为相对于前一元素的差，类似地，在第二中间节点3中的所有元素包含数据信息“+10”，而在叶节点4中的叶元素可能包含数据信息“+1”。

这需要较少存储空间，但是提供同样的信息。

信息并不总是可以如上述例子所示以简单方式排序存储。

例如，在文件名或http地址的场合，数据信息是更复杂的数据结构。此外，使用不同的格式和后缀，这可能使得以简单方式说明两个相邻节点之间的差信息更困难。

关于这点，以例子给出下面链接的http地址。

1)http：//www.ericsson.se/ndb/description.html

2)http：//www.ericsson.se/ndb/nodedescription.html

3)http：//www.ericsson.se/ndb/system_arch.pdf

4)http：//www.ericsson.se/ndb/system_arch.ps

在这种场合，对于2、3和4的信息需要128字节。这可以以压缩形式从开始值的开始点说明，它为地址号1。在存储对前一元素的差的方法中，可以以下述方式表示上述地址：

1)http：//www.ericsson.se/ndb/description.html

2)-″description.html″+″nodedescription.html″

3)-″nodedescription.html″+″system_arch.pdf″

4)-″df″+″s″

它对于2、3和4需要80字节，因此是对必须存储以便重现希望信息的数据信息的压缩。这相应于在没有任何压缩情况下需要的存储空间的大约60％。

本发明基本建立在一种方法上，该种方法基于只存储B树中各元素对前面元素的差，该方法能使在树结构中需要的数据信息相对于公知技术进一步压缩或减少。

这一方法提供建立两相邻元素之间差信息的可能性，而不需存储全部数据信息的末尾，只要差不位于该元素的末端。

在上面的例子中，在开始值(1)和后继元素(2)之间的差从离开数据信息末端的一些字符中找到。

这意味着，差信息-″description.html″+″nodedescription.html″大于必需的信息，因为在两元素中的数据信息之间的实际差在实际中相对小，+″node″。

本发明建议，各元素中的差信息由表示相对于属于前一元素的数据信息的数据信息中的实际差组成，不管该差在该数据信息中的什么地方。

这一差信息包括关于是否某些数据信息要从属于前一元素的数据信息中要被清除，和如果是的话，要去掉的东西的性质和在数据信息中的什么地方去掉的指令。

该差信息还可以包括相对于属于前一元素的数据信息要添加什么，以及在这种场合，要添加什么和在数据信息中的什么地方添加的指令。

图3打算表示数据字的构造。在所示例子中，数据字5包括头标51和信息部分52，其中头标51公开信息部分52应被如何解释。

信息部分52可以包括5个不同的位组，其中

-第一组521，这里称为后缀，表示在该数据信息中包含的后缀类型；

-第二组522，这里称为减信息，它表示相对于前一元素要去掉的字节数目；

-第三组523，这里称为加信息，它表示相对于前一元素要加上的字节数目；

-第四组524，这里称为相似性，它表示除后缀外，从末尾开始相似于前一元素的字节数目；

-第五组525，这里称为差，它组成要添加的字符，亦即明文形式的加信息523。

头标51由3位组成，其中

-第一位511公开第四组524是否存在，亦即表示差是否存在于数据信息末尾；

-第二位512公开第二和第三组522、523是包括4位还是8位；

-第三位513公开第二、第三和第五组522、523、525是否存在，亦即在后缀521外是否发现任何差信息。

第一组521包括5位，第二和第三组522、523包括4位或8位，第四组524包括0或8位，第五组525包括为表示可能添加的内容必需的字节数。

这样，除第五组525外，所有差信息可以至少用8位表示，也就是说1个字节，当差只存在于后缀时；或者最多32位，亦即4字节，当所有组包括最大位数时。

通过5位的介质，第一组521能够表示根据一预定后缀表的32个不同的后缀。

例如，可以把后缀“html”分配值“00000”，而后缀“pdf”可以分配值“00001”。这样，在这两种场合，各后缀都可用5位表示。另一方面，如果写出后缀“html”需要4字节，32位，而“pdf”需要3字节，24位。

为说明这一点，我们返回到链接的http地址的例子：

1)http：//www.ericsson.se/ndb/description.html

2)http：//www.ericsson.se/ndb/nodedescription.html

3)http：//www.ericsson.se/ndb/system_arch.pdf

4)http：//www.ericsson.se/ndb/system_arch.ps

根据本发明，这可以以比公知技术所能实现更进一步压缩的形式描述，例如：

1)http：//www.ericsson.se/ndb/description.html

2)头标51：101(3位)；后缀521：HTML(5位)；减信息522：-0(4位)；加信息523：4(4位)末尾的相似性524：11(8位)；差525：“node”(4字节)

3)头标51：001(3位)；后缀521：pdf(5位)；减信息522：-15(4位)；加信息523：+11(4位)；差525：″system_arch″(11字节)

4)头标51：000(3位)；后缀521：ps(5位)

这导致为行2、3和4用21字节，而根据公知技术的压缩需要80字节，对于无压缩信息为128字节。

对这一信息，必须添加维护树结构和能使搜索通过所述结构进行需要的地址信息。

属于各叶元素的数据信息还包括实际对象，例如，为用户看到的外部http地址的内部表示，所谓的对象键字。

一个元素可以受事务处理不同方式的影响，例如通过改变或者更新该对象。在某些改变的场合，必须相对于其它事务处理锁定该元素或对象。可以使用不同类型的锁定，取决于该对象为其它事务处理可用的程度。

根据本发明，对象6包括4个不同的位组合，如图4所示。

对象6中的第一位组合61表示该对象是否锁定。

当第一位组合61表示对象6未锁定时，第二位组合62包括对象状态位，第三位组合63包括关于属于所述对象的对象键字的长度的信息，第四位组合64包括实际对象键字。

当第一位组合61表示该对象被锁定时，根据图5，属于其余位组合的位表示对属于引起该锁定被施加的事务处理的事务处理寄存器7的参考65。

该事务处理寄存器7包括对象状态位62，关于对象键字长度的信息63，对象键字64自身，以及关于施加到对象6上的锁的类型的信息66。

状态位62用于对象复制过程，此时各位指示该对象是否被复制。一些同时的复制过程的每一个使用其各自的状态位，从而该对象可为和状态位同样多的不同的复制过程使用。

图6意在表示根据本发明如何清除元素E′2。图6表示使属于一个可能的后继元素E′3的差信息E′31适应组成相对于位于被清除的元素E′2前一元素E′1的差信息。

属于后继元素E′3的任何地址信息E′13也将适应指向前一元素E′1，而属于前一元素E′1的地址信息E′13将适应指向后继元素E′3。

图7以类似方式表示当添加一个元素E″2时，使属于被添加的元素E″2的差信息E″21适应组成相对于前一元素E″1的差信息。

然后使属于可能后继元素E″3的差信息E″31适应于组成相对于被添加的元素E″2的差信息。

使属于被添加的元素E″2的任何地址信息E″12、E″23适应指向前一元素E″1和后继元素E″3，使任何后继元素E″3的地址信息E″23适应指向被添加的元素E″2，而使属于前一元素E″1的地址信息E″12适应指向被添加的元素E″2。

在上面的说明中，一个节点内的元素在一个链接表内互连。这意味着，通过这些元素的搜索可能需要对为每一元素的存储器进行访问。

因为上述压缩结构提供对必需的存储器空间明显的压缩，因此，该结构能使大量元素存储在一个公共容器中。

图8表示本发明的一个优选实施例，其中各节点包含一个容器8。

属于一个节点的各元素8E1、8E2、8E3、...在容器8中一个紧接一个分配位置。

为使通过本发明的树结构的搜索可能性更有效，建议，包含在容器8中的信息量少于或等于可以通过一次读入操作读到一个超高速缓冲存储器中的信息量，该超高速缓冲存储器属于操作该数据库或使用所述数据库的处理器。

因为在容器8中的元素8E1、8E2、8E3、...彼此相继排列，因此不必为各元素包含链接表中需要的所有地址信息。

这样，当元素8E1、8E2、8E3、...包含在一个容器中时，本发明建议，在各中间元素8E1、8E2、8E3、...内发现的连接和关联的地址信息被限制到关于属于在该层次结构中的后继节点8′的第一元素8′E1的一个连接81与关联地址信息、和从各第一中间元素8E1到在该层次结构中前一节点内的元素8″E3和关联容器8″的一个连接82与关联地址信息。

类似地，在各叶元素8′E1、8′E2、8′E3、...内的连接和关联地址信息限制到从各第一叶元素8′E1到在该层次结构中前一节点和关联容器8的连接81与关联地址信息。

当在一个表内寻址时需要不同数量的地址信息，这一数量依赖于各种节点如何放置。如果要寻址在另一页上的一个节点，则寻址过程在最坏情况下可能需要8字节。

页可以给定不同大小，并可使适应不同的数据结构。

在本发明的一个优选实施例中，尽可能把树节点放在同一页上。这使得更容易访问另一节点。根据本发明，给定容器特定的大小，使其适应能通过一次访问将其内容读入超高速缓冲存储器。

当今的处理器通常能一次读入128字节到超高速缓冲存储器，下面的说明基于这一数值。然而应该理解，容器的大小和在下面的说明中提到的数量将适应可以在任何一次性读入所涉及的处理器的超高速缓冲存储器的信息量，以便获得希望的效果。

在本发明的进一步应用中可能需要考虑的另一参数是处理读入超高速缓冲存储器的信息需要的时间。当处理时间超过超高速缓冲存储器的不命中时间时，限制容器大小和其它数量到某值，在该值下处理容器需要的时间小于超高速缓冲存储器的不命中需要的时间，而不管可以一次读入该超高速缓冲存储器的信息量，这是适宜的。

当希望用适应的小地址信息量寻址在一页上获得空间的所有容器时，本发明建议，使一页适应至少容纳可以借助于1字节寻址的容器的数目。256个容器可以用1字节寻址，它们相应于32768字节。这样，一页将适应能包括至少33K字节和属于一页的其它必需的信息。

图9概略表示一个B树是如何分成一些较小的部分树T1、T2、T3。这使得大到不能在一页上容纳的树能够分成较小的部分树。

当一个部分树T1容纳在一页p1上时，必需的地址信息R1为每一参考只需要1个字节。当参考R2、R3位于部分树T1、T2、T3之间时，需要大量地址信息，亦即需要寻址在不同页p1、p2、...、pn上的容器需要的信息量。

这样，在整个树中的大部分参考可以每次容纳在一个字节中。仅在部分树之间的那些参考需要较大存储器空间。

现在以例子说明本发明通过B树搜索的一种方法。

图10概略表示一个树。搜索从所谓的根页开始，并向下继续。由于B树的元素只包含差信息，因此在所有搜索级上必须具有一个开始值。存储的实际对象可以使用该开始值和差信息找出。在根页上的根节点包含开始值“空”。

与第一元素9e11比较希望的对象。如果该对象小于或等于元素9e11，则搜索跟随左指针9p11进行，否则，接着与下一元素9e12比较。如果该对象小于或等于元素9e12，则搜索跟随左指针9p12进行，这是我们的例子的情况。

于是指针9p12所指节点的开始值是元素9e12，因为在该节点内的所有元素大于元素9e12。该搜索以这种方式继续，向下通过一页上的节点。

如果搜索通过到另一页，则该页具有和根节点同样的开始值，仿佛搜索通过树继续，而不注意页。从上面的叙述明显看出，在整个搜索中隐含知道开始值。这样，不必与搜索结合存储开始值。

如果在容器中不能容纳某对象，则分配另外的容器，并与第一容器组合，这样形成一个具有必需空间的较大的容器。

于是该容器对其内容来说太大，以致不能一次读入超高速缓冲存储器，这导致结合搜索该容器内的某些元素的超高速缓冲存储器不命中。这提供一种功能，然而，它是以性能损失为代价的。

应该理解，本发明并不限制于上述图示实施例，可以在下述权利要求中说明的本发明概念的范围内进行修改和改变。

Claims

1.数据库内存储数据信息的一种结构，在该种结构内数据信息以包含树结构的节点层次组织，该树结构包括根节点，可能的一层或者多层中间节点，和一个或者多个叶节点，其中根节点包括一个或多个根元素，各中间节点包括一个或者多个中间元素，各叶节点包括一个或者多个叶元素，其中，在中间节点内的第一中间元素连接到根元素或连接到位于该层次结构中较高一级的中间节点内的中间元素，其中，在该中间节点内的其余中间元素连接到所述第一中间元素，其中，各叶节点内的第一叶元素要么连接到根元素，要么连接到中间节点之一的一个中间元素，叶节点内的其余叶元素连接到第一叶元素，其中，各元素包括用于连接的地址信息和数据信息，这里在节点内的元素的顺序相对于数据信息是逻辑顺序，诸如字母或数字顺序，这里各元素中的数据信息组成相对于属于在该层次结构中前一元素的数据信息的数据信息的差，其特征在于，在所述根元素内的数据信息组成一个开始值；所述开始值包含实际数据信息；其余元素内的差信息包括表示相对于属于前一元素的数据信息的数据信息的实际差，而不管该差位于所述数据信息内的什么位置。

2.根据权利要求1的结构，其特征在于，所述差信息包括相对于属于前一元素的数据信息是否要清除某些东西的信息，在这种情况下，什么东西要被清除和在所述数据信息内从什么地方清除；以及所述差信息包括指令，它为是否相对于属于前一元素的数据信息要添加某些东西，在这种情况下，要添加什么，和在所述数据信息内的什么地方添加。

3.根据权利要求2的结构，其特征在于，所述数据字包括头标和信息部分，所述头标表示所述信息部分应如何解释。

4.根据权利要求3的结构，其特征在于，所述信息部分可以包括5个不同的位组，其中

-第一组，这里称为后缀，表示由所述数据信息拥有的后缀类型；

-第二组，这里称为减信息，它表示相对于前一元素要去掉的字节数目；

-第三组，这里称为加信息，它表示相对于前一元素要加上的字节数目；

-第四组，这里称为相似性，它表示除所述后缀外，从末尾开始相似于前一元素的字节数目；以及

-第五组，这里称为差，它组成要添加到该数据信息的字符，亦即明文形式的所述加信息。

5.根据权利要求4的结构，其特征在于，所述头标包括3位，其中

-第一位表示第四组是否存在，亦即表示差是否存在于所述数据信息末尾；

-第二位表示所述第二和第三组是包括4位还是8位；及

-第三位表示第二、第三和第四组是否存在，亦即在所述后缀外是否存在差信息。

6.根据权利要求5的结构，其特征在于，所述第一组包括5位；所述第二和第三组包括4或8位；所述第四组包括0或8位；所述第五组包括必需的字节数。

7.根据权利要求6的结构，其特征在于，所述第一组通过其5位介质，能够表示按照一个预定后缀表的32个不同的后缀。

8.根据权利要求8的结构，其特征在于，对各叶元素，所述数据信息包括一个寻找对象；所述对象包括4个不同的位组合，其中第一位组合表示该对象是否被锁定。

9.根据权利要求8的结构，其特征在于，当所述第一位组合表示所述对象未锁定时，第二位组合包括对象状态位，第三位组合包括有关属于所述对象的一个对象键字的长度信息，第四位组合包括所述对象键字。

10.根据权利要求8的结构，其特征在于，当所述第一位组合表示所述对象被锁定时，属于其余位组合的位表示对一个事务处理寄存器的引用；所述事务处理寄存器包括对象状态位、有关属于所述对象的一个对象键字长度的信息、所述对象键字自身和有关施加给所述对象的锁定的类型信息。

11.根据权利要求9和10的结构，其特征在于，所述状态位用于对象复制过程；各位指示所述对象是否被复制；及多个同时的复制过程每一个使用各自的一个状态位。

12.根据权利要求1的结构，其特征在于，当清除一个元素时，使属于可能的后继元素的差信息适应组成相对于被清除元素前一元素的差信息；使属于所述后继元素的地址信息适应指向所述前一元素；及使属于所述前一元素的地址信息适应指向所述后继元素。

13.根据权利要求1的结构，其特征在于，当添加一个元素时，使属于所述被添加元素的差信息适应组成相对于前一元素的差信息；使属于所述被添加元素的地址信息适应指向所述前一元素和一个可能的后继元素；使属于所述可能的后继元素的差信息适应组成相对于所述被添加元素的差信息；使属于所述后继元素的地址信息适应指向所述被添加的元素；及使属于所述前一元素的地址信息适应指向所述被添加元素。

14.根据权利要求1的结构，其特征在于，一个节点包含一个容器；属于一个节点的各元素在所述容器内分配密切连接的顺序位置。

15.根据权利要求14的结构，其特征在于，容器容纳小于或等于可以一次读入一个超高速缓冲存储器内的信息量的信息量，所述超高速缓冲存储器属于在所述数据库内作用的处理器或使用所述数据库的处理器。

16.根据权利要求14或15的结构，其特征在于，在各中间元素内的所述连接和关联的地址信息限制在有关属于在所述层次结构中一个后继节点的第一元素的连接及其关联的地址信息；及在各叶元素内的所述连接及其关联的地址信息限制在从各第一叶元素到属于在所述层次结构中前一节点的一个元素的一个连接及其关联的地址信息。

17.根据权利要求13的结构，其特征在于，使一页适应容纳可通过一个字节寻址的多个节点；树结构被分成多个部分树，其中各部分树由一页包含；属于在一个公共部分树内的两节点之间各引用的地址信息包含1字节；及属于两不同部分树之间的各引用的地址信息包含它们必需的存储器空间。