技术领域
本发明总体上涉及在数据库和信息检索系统中有效使用特里(trie)数据结构，并涉及以高性能查询这样的系统。
背景技术
数据库和信息检索系统用于处理结构化和非结构化信息。通常，结构化数据是数据库(例如关系数据库)的领域，而非结构化信息是信息检索系统(例如全文搜索)的领域。数据库引擎是存储和检索数据的数据库管理系统(或其他应用程序)的一部分。对于信息检索系统，此功能由搜索引擎执行。
索引(indexing)用于提高数据库或信息检索系统的性能。在没有查询的索引(也称为按“键(key)”查找或访问)的情况下，将务必扫描整个数据库或信息库以递送结果，这将太慢而无用。
数据库索引与由书籍提供的索引相当：为了查找特定的关键字，用户不必阅读整本书，而是可以在索引中查找某个关键字，该索引包含对与该关键字有关的页面的引用。这也是搜索引擎背后的基本原理：对于任何给定的搜索项，他们都会通过查阅适当的索引来快速查找包含该搜索项的文档。信息检索系统的示例查询是全文搜索，对于该全文搜索，项(单词)存储为键，并且文档ID也存储为键(参见下面的图70的说明)。例如，如果在ID为10和33的文档中可以找到项“苹果”，则两个复合键(“苹果”，10)和(“苹果”，33)存储在索引中。这些项被存储为键，使得可以进行例如“苹果”和“梨”的搜索。
索引的经典方法是使用所谓的B树索引。B树由R.Bayer和E.McCreight于1972年发明，仍然是用于此目的主要数据结构。但是，B树索引具有主要缺点。例如，访问数据的时间随着数据量而对数地增加。数据大小增加一个数量级大约会使访问时间增加一倍，数据大小增加两个数量级会使访问时间增加两倍，等等。此外，B树索引无助于提高所谓的低基数的标准的查询性能。例如，与扫描和过滤所有记录相比而言，在属性“性别”上创建具有值“男性”、“女性”和“未知”的索引不会提高性能。最后，由于B树索引不能有效地连接(组合)，因此多维查询、即涉及多个条件/属性的查询很难有效地处理。
M.Boehm等人，“Efficient In-Memory Indexing with Generalized Prefix-Trees”，在：T.
节省空间的trie数据结构
一种实施trie数据结构的方式是将节点分别存储在存储器中，每个节点包括：节点类型信息，其指示该节点是否为叶节点；指向其子节点(child node)的指针数组(至少在该节点不是叶节点的情况下)；以及在叶节点的情况下可能的有效负载，例如与键相关联的值。使用这种方法，从节点到节点的遍历是恒定时间操作，这是因为相应子指针对应于表示相应键部分的数组条目。但是，由于对应的数组包括并存储许多空条目，因此对于只具有几个子节点的节点，存储器使用可能非常低效。当使用较大的字母表时尤其如此，这是因为它们需要存储大量的子指针(child-pointer)。
为了更有效地使用存储器空间，已经开发了避免存储空指针的trie数据结构的实施方式。这样的解决方案可以包括仅存储非空指针的列表以及它们相应的键部分值，而不是包含所有可能指针的数组。这种方法的缺点是，对于从节点到节点的遍历，必须扫描相应父节点(parent node)中的列表，或者如果该列表是按键部分的值排序的，则必须执行二进制搜索。另外，由于需要识别用于键部分的特定值的特定指针，因此还必须存储键部分的相关联的值，这降低了存储器空间效率。
已经开发了以紧凑格式存储trie数据结构的其他方式。例如，Bagwell博士，“FastAnd Space Efficient Trie Searches”，技术报告，EPFL，瑞士(2000)，公开了一种基于位图的trie数据结构。这种trie数据结构使用位图来标记父节点的所有非空指针。特别地，位图中的设置位标记了有效(非空)分支。每个父节点还包括一个或多个指针，其中每个指针与位图中设置的位相关联，并指向父节点的子节点。子节点的键部分的值由父节点所包括的位图中(设置)的位的值来确定，其中位关联于指向该子节点的指针。
指针具有预定的长度或大小，并且可以与在位图中设置的位相同或相反的顺序存储。基于位图中设置的最低有效位的数量，可以容易地计算与位图中设置的位关联的指针的存储器地址。由于可以使用简单的位操作和确定设置位的数量的CTPOP(计数填充)操作来有效地计算所设置的最低有效位的数量，所以对相应指针以及因此下一个子节点的确定是快速的。例如，这种计数填充方法在Java编程语言中可用，并称为“Long.bitCount()”。使用“位-黑客(bit-hack)”可以非常高效地实施CTPOP本身，并且许多现代CPU甚至将CTPOP提供为内部指令。
由于位图指示与有效分支相关联的字母表值，因此仅需要存储现有(非空)指针。因此，可以减少存储器使用。另一方面，基于位图中的设置位当中的其相关联的位的等级，可以在恒定时间内容易地确定特定指针的地址。最后，与指向子节点的指针相关联的位的值以有效的方式表示子节点的键部分值。因此，与基于如图4中示出的列表的trie数据结构相比而言，基于位图的trie数据结构提供了一种更有效的方法来处理存储器分配和处理trie。
然而，发明人发现在许多应用程序场景中，存储器空间的使用效率低。当trie稀疏地填充和/或退化为节点链(每个节点都具有单个子指针而浪费空间)时，尤其如此。因此，期望进一步减少存储由数据库应用程序或信息检索系统使用的trie所需的存储空间，并且特别是减少存储用于实施trie的指针和/或位图所需的存储器的数量，而不会显着增加遍历trie所需的速度。
键编码
典型地，在现有技术中使用的trie的字母表的基数相对较大，例如256，以便能够容纳来自较大的字母表(如Unicode)中的字符。使用256个不同的值，可以编码8个位(2
此外，trie在现有技术中仅用于存储预定义的数据类型，其中，数据类型典型地限于如数字或字符的原始数据类型。这样的使用对可存储在trie中的键施加约束，并使trie数据结构不太适合于存储数据库或信息检索系统索引。
因此，本发明的另一个目的是提供可以以灵活的方式使用的trie、和/或以灵活的方式使用trie的方法。实际上，本发明的目的是提供可用作通用数据库或信息检索系统索引的trie数据结构，以及使用trie数据结构作为通用数据库或信息检索系统索引的方法。此外，本发明的目的是提供trie，其以以下这样的方式存储数据库索引的键：可以以省时的方式处理涉及超过一个数据项的数据库查询。
查询执行
在数据库中执行的查询通常以逻辑代数(例如SQL)表示。为了查询的执行，必须将查询转换为物理代数：物理查询执行计划(QEP)。该查询被重写、优化，并准备了QEP，使得查询执行引擎(QEE)在数据库上执行由前面的步骤生成的QEP。
对于处理，QEP通常包括旨在产生查询结果的有关运算符的集合。大多数数据库由树表示QEP，其中节点是运算符，叶节点是数据源，并且边是以生产者-消费者形式的运算符之间的关系。
许多数据库引擎在QEE中遵循基于迭代器的执行模型，其中运算符实施以下方法：Open(使运算符准备产生数据)、Next(在运算符消费者的需求下产生新的数据单元)、Close(完成执行并释放资源)。从根运算符开始调用这些操作之一，会将其传播到其运算符子节点，依此类推，直到到达数据源(以及叶节点)为止。以这种方式，在查询执行计划运算符树中，控制从消费者向下流到生产者，而数据从生产者向上流到消费者。由于每个运算符都不需要全局知识，因此这种方法提供了简洁的设计和封装。
但是，这样的执行模型具有严重的缺点。首先，由于每个运算符都不具有全局知识，因此无法应用从全局角度来看将是有益的优化。另外，由于查询计划是静态的，因此在查询执行期间应用自适应优化可能会很困难。结果，强烈依赖查询优化器来创建涉及复杂算法的良好QEP。并且最后，迭代器方法仅递送一个数据单元，例如记录每个运算符的调用。这种方法对于组合大的子结果集(它们本身返回小的结果集)的运算符是低效率的。
作为这些缺点之一的示例，如果要在数据库上执行的查询是诸如“A交(B并C)”的表达式，其中A返回记录ID的短列表，例如(1、2、...10)，但B和C返回长列表，例如(1、2、...10.000)和(20.000、...50.000)。如果查询优化器没有预测能力，并且在其执行之前没有将该查询重写为(A交B)并(A交C)，则查询非常低效。
因此，期望有一种执行数据库或信息检索系统查询的更省时的方法，其包括对存储在数据库或信息检索系统中的键的两个或更多个集合、或数据库或信息检索系统的输入集或结果键集进行诸如交集(AND)、并集(OR)和差集(AND NOT)的操作。
此外，现有技术数据库的范围查询性能随着索引的大小(由数据库所包括的并且由索引所索引的记录的数量)而降低。因此，期望有一种执行范围查询的更省时的方法，其可以随着索引大小的增加而很好地扩展。
发明内容
通过独立权利要求的主题实现这些目的中的一个或多个目的。优选实施例是从属权利要求的主题。
本发明提供了用于数据库应用程序的索引解决方案，其中B树和衍生品仍然是主要策略，以及用于信息检索应用程序的索引解决方案，其中典型地使用反向索引。反向索引是这样一种索引，其中项列出了包含该索引的文档。本发明可以在当trie被逐级处理时，利用分层的trie结构以允许惰性计算(lazy evaluation)。因此，本发明可以使用第一级上的trie作为关联数组来实施反向索引，其中项是存储在trie中的键。在第二级上(即，作为关联数组的叶节点)，本发明可以使用trie作为集合来实施文档列表(即，ID集合)。因此，本发明允许利用一种通用解决方案代替B树和反向索引，因此可以将其称为“汇合索引(confluence index)”。
本发明的索引数据结构和查询处理模型基于逐位trie，并且具有代替现有技术索引结构的潜力：该数据结构可以被频繁地更新，适用于具有低基数和高基数的键，并且在没有压缩/解压缩的情况下节省空间(数据结构是紧凑的或在某些情况下甚至是简洁的)。另外，由于它基于trie，因此它继承了O(|M|)恒定时间复杂度，以用于通过键操作进行插入、更新、删除和查询(其中|M|为键长)。它比基于树的方法通常的O(logn)复杂度更好(其中n是索引中的键的数量)。然后，它可以提供与数据库填充无关的查询时间。在优选实施例中，在查询处理中集合运算符的结果“显示”为trie。这允许功能组成和惰性计算。作为副作用，物理代数直接对应于逻辑代数，从而简化了如典型地在查询优化器中完成的针对给定查询创建合适的物理执行计划的任务。
本发明的第1实施例是一种用于电子数据库应用程序或信息检索系统的trie，所述trie包括一个或多个节点，其中由所述trie所包括的父节点、优选地具有超过一个子节点的每个父节点包括位图和一个或多个指针，其中每个指针与所述位图中设置的位相关联并指向所述父节点的子节点。所述trie的特征在于，由所述trie所包括的父节点、优选地仅具有一个子节点的每个父节点不包括指向所述子节点的指针，和/或所述子节点被存储在存储器中相对于所述父节点的预定义位置中。
根据第2实施例，在第1实施例中，仅具有一个子节点的父节点的子节点被存储在存储器中直接位于所述父节点后面的位置中。
根据第3实施例，在第1或第2实施例中，节点、优选地每个子节点与键部分相关联，并且从所述trie中的根节点到另一节点、特别是到叶节点的路径定义了键，所述键是与所述路径中的节点相关联的键部分的级联。
终端优化
本发明的第4实施例是一种用于电子数据库应用程序或信息检索系统的trie，所述trie包括一个或多个节点，其中由所述trie所包括的父节点、优选地具有超过一个子节点的至少每个父节点包括位图；节点、优选地每个子节点与键部分相关联；并且子节点的键部分的值、优选地其父节点具有超过一个子节点的至少每个子节点的键部分的值，由所述父节点所包括的位图中(设置)的位的值确定，取决于所述子节点与哪个位相关联。所述trie的特征在于，节点，优选地仅具有一个子节点并且其所有后代节点至多具有一个子节点的每个节点，被标记为终端分支节点，并且与终端分支节点、优选地每个终端分支节点的后代节点、优选地每个后代节点相关联的键部分的值不是由所述后代节点的父节点所包括的位图中的(设置)位的值确定出的。
根据第5实施例，在第4实施例中，所述终端分支节点具有超过一个后代节点。
根据第6实施例，在第4或第5实施例中，所述终端分支节点的父节点具有超过一个子节点。
根据第7实施例，在第4至第6实施例中，作为终端分支节点的标记是没有设置位的位图。
根据第8实施例，在第7实施例中，所述终端分支节点的位图具有与由具有超过一个子节点的父节点所包括的位图相同的长度或格式。
根据第9实施例，在第4至第8实施例中的任何一个中，终端分支节点、优选地由所述trie所包括的每个终端分支节点和/或所述终端分支节点的后代节点、优选地每个后代节点不包括指向其子节点的指针，和/或所述子节点被存储在存储器中相对于所述父节点的预定义位置中，优选地在存储器中直接位于所述父节点后面的位置中。
根据第10实施例，在第4至第9实施例中的任何一个中，与终端分支节点、优选地每个终端分支节点的后代节点、优选地每个后代节点相关联的键部分的值由所述后代节点的父节点所包括。
根据第11实施例，在第4至第10实施例中的任何一个中，与终端分支节点、优选地每个终端分支节点的后代节点、优选地所有后代节点相关联的键部分的值，在所述终端分支节点之后被连续存储。
根据第12实施例，在第4至第11实施例中的任一个中，相比由具有超过一个子节点的父节点所包括的位图而言，与终端分支节点、优选地每个终端分支节点的后代节点、优选地每个后代节点相关联的键部分的值的编码需要较少的存储器空间。
根据第13实施例，在第4至第12实施例中的任一个中，与终端分支节点、优选地每个终端分支节点的后代节点、优选地所述后代节点中的每个相关联的键部分的值被编码为二进制数。
根据第14实施例，在第4至第13实施例中的任一个中，由父节点、优选地具有超过一个子节点的每个父节点所包括的位图具有32、64、128或256位，并且与终端分支节点、优选地每个终端分支节点的后代节点、优选地所述后代节点中的每个相关联的键部分分别由5、6、7或8位编码。
根据第15实施例，在第4至第14实施例中的任何一个中，与终端分支节点、优选地所述终端分支节点中的每个的后代节点、优选地所述后代节点中的每个相关联的键部分的值被编码为整数值。
根据第16实施例，在第4至第14实施例中的任何一个中，作为父节点的终端分支节点的后代节点、优选地作为父节点的每个后代节点不包括其中设置位确定了与其子节点相关联的键部分的值的位图。
根据第17实施例，在第4至第16实施例中的任何一个中，由所述trie所包括的父节点、优选地具有超过一个子节点的至少每个父节点包括一个或多个指针，其中，每个指针与由所述父节点所包括的位图中设置的位相关联，并指向所述父节点的子节点。
根据第18实施例，在第4至第17实施例中的任何一个中，所述trie是根据第1或第2实施例中的任一个的trie。
位图压缩
本发明的第19实施例是一种用于电子数据库应用程序或信息检索系统中的trie，所述trie包括一个或多个节点，其中节点、优选地具有超过一个子节点的至少每个父节点包括以逻辑位图形式的位图和多个指针，其中每个指针与所述逻辑位图中设置的位相关联并指向所述节点的子节点。所述trie的特征在于，将所述逻辑位图分为多个区部(section)，并由头部位图和多个内容位图进行编码；其中每个区部与所述头部位图中的位相关联；并且其中，对于其中设置了一个或多个位的逻辑位图的每个区部，设置与所述头部位图中的区部相关联的位，并将所述区部存储为内容位图。
根据第20实施例，在第19实施例中，对于其中未设置位的逻辑位图的每个区部，不设置与所述头部位图中的区部相关联的位，并且不将所述区部存储为内容位图。
根据第21实施例，在第19或第20实施例中的任何一个中，所述区部中的每个是连贯的。
根据第22实施例，在第19至第21实施例中的任何一个中，所有区部具有相同的大小。
根据第23实施例，在第22实施例中，所述区部的大小是一个字节。
根据第24实施例，在第19至第23实施例中的任何一个中，被存储为内容位图的区部的数量等于在所述头部位图中设置的位的数量。
根据第25实施例，在第19至第24实施例中的任何一个中，所述头部位图的大小是一个字节。
根据第26实施例，在第19至第25实施例中的任何一个中，所述内容位图被存储在存储器中相对于所述头部位图的预定义位置中。
根据第27实施例，在第19至第26实施例中的任何一个中，所述逻辑位图的内容位图被存储在数组中、列表中或者连续的物理或虚拟存储器位置中。
根据第28实施例，在第19至第27实施例中的任何一个中，所述内容位图以相同或相反的顺序被存储，其中与它们的区部相关联的设置位被布置在所述头部位图中。
根据第29实施例，在第19至第28实施例中的任何一个中，在所述头部位图中的所有设置位中，所述逻辑位图的所有内容位图中的内容位图的等级对应于与所述内容位图的区部相关联的设置位的等级。
根据第30实施例，在第19至第29实施例中的任一个中，由节点所包括的指针、优选地节点的每个指针和/或不是叶节点的每个节点的每个指针，以第19至第29实施例中的任何一个中针对逻辑位图定义的编码的方式进行编码。
根据第31实施例，在第19至第30实施例中的任一个中，所述trie是在第1至第18实施例中的任一个中的trie。
根据第32实施例，在第19至第31实施例中的任何一个中，节点优选地每个子节点与键部分相关联，并且从所述trie中的根节点到另一节点、特别是到叶节点的路径定义了键，所述键是与所述路径中的节点相关联的键部分的级联。
包括控制信息的键
本发明的第33实施例是一种用于电子数据库应用程序或信息检索系统的trie，所述trie包括一个或多个节点，其中节点、优选地每个子节点与键部分相关联；从所述trie中的根节点到另一个节点、特别是到叶节点的路径定义了与所述节点相关联的键，所述键是与所述路径上的节点相关联的键部分的级联。所述trie的特征在于，所述键包括控制信息和内容信息。
根据第34实施例，在第33实施例中，所述键包括包含了内容信息的一个或多个键部，并且对于所述键部中的每个，所述控制信息包括数据类型信息元素，所述数据类型信息元素指定了由所述键部所包括的内容信息的数据类型。
根据第35实施例，在第34实施例中，键部、优选地每个键部包括数据类型信息元素，所述数据类型信息元素指定了由所述键部所包括的内容信息的数据类型。
根据第36实施例，在第35实施例中，所述数据类型信息元素由所述内容信息元素定位，优选地位于所述内容信息元素之前。
根据第37实施例，在第34实施例中，所述数据类型信息元素位于一起，并且优选地以与它们指定了其数据类型的内容信息元素相同或相反的顺序布置。
根据第38实施例，在第37实施例中，所述控制信息位于所述键中的所述内容信息之前。
根据第39实施例，在第34至第38实施例中的任何一个中，所述键包括两个或更多个键部，其包括不同数据类型的内容信息。
根据第40实施例，在第34至第39实施例中的任何一个中，所述数据类型中的至少一种是固定大小的数据类型。
根据第41实施例，在第40实施例中，固定大小的数据类型是整数、长整数或双精度浮点或时间/日期原语(primitive)。
根据第42实施例，在第34至第41实施例中的任何一个中，所述数据类型中的至少一种是可变大小的数据类型。
根据第43实施例，在第42实施例中，所述可变大小的数据类型是字符串、优选地Unicode字符串或者可变精度整数。
根据第44实施例，在第34至第43实施例中的任何一个中，键部的信息由两个或更多个键部分所包含。
根据第45实施例，在第34至第44实施例中的任何一个中，由键部所包括的内容信息的数据类型是可变大小的数据类型，并且所述内容信息元素的末端由包含所述键部的键部分中的特定一个中的特定位或特定符号标记。
根据第46实施例，在第34至第45实施例中的任何一个中，所述控制信息包括标识所述最后一个键部的信息。
根据第47实施例，在第33至第46实施例中的任何一个中，所述控制信息包括关于所述trie是用于存储动态集合还是关联数组的信息。
根据第48实施例，在第33至第47实施例中的任何一个中，所述trie是根据第1至第32实施例中的任一个的trie。
根据第49实施例，在第33至第48实施例中的任何一个中，节点、优选地具有超过一个子节点的至少每个父节点包括位图和多个指针，其中，每个指针与在所述位图中设置的位相关联并指向所述节点的子节点。
交错的多项键
本发明的第50实施例是一种用于电子数据库应用程序或信息检索系统的trie，所述trie包括一个或多个节点，其中节点、优选地每个子节点与键部分相关联；从所述trie中的根节点到另一个节点、特别是到叶节点的路径定义了与所述节点相关联的键，所述键是与所述路径上的节点相关联的键部分的级联。所述trie的特征在于两个或更多个数据项被编码在键中，所述数据项中的至少一个或两个、优选地每个由两个或更多个分量组成；并且所述键包含两个或更多个连续区部，所述区部中的至少一个或两个、优选地每个包括所述键中编码的数据项中的两个或更多个的分量。
根据第51实施例，在第50实施例中，键的区部、优选地区部中的每个包含来自所述键中编码的数据项中的每个数据项的至少一个分量和/或至多一个分量。
根据第52实施例，在第50或第51实施例中的任何一个中，对于键的两个或更多个区部优选地所有区部，属于不同数据项的分量在所述区部内以相同序列排序。
根据第53实施例，在第50至第52实施例中的任何一个中，包括数据项的分量的区部的顺序对应于所述数据项内的分量的顺序。
根据第54实施例，在第50至第53实施例中的任何一个中，与子节点、优选地与子节点中的每个相关联的键部分对应于数据项的分量的一部分。
根据第55实施例，在第50至第53实施例中的任一个中，与子节点、优选地与子节点中的每个相关联的键部分对应于数据项的一个分量，和/或数据项优选地每个数据项的分量优选地每个分量对应于与所述trie的一个子节点相关联的键部分。
根据第56实施例，在第50至第53实施例中的任何一个中，与子节点、优选地与所述子节点中的每个相关联的键部分对应于数据项的超过一个分量。
根据第57实施例，在第50至第56实施例中的任何一个中，键的两个或更多个、优选地所有数据项具有相同数量的分量。
数据项的类型及其分量
根据第58实施例，在第50至第57实施例中的任何一个中，两个或更多个数据项表示地理位置数据。
根据第59实施例，在第50至第58实施例中的任何一个中，数据项表示经度、纬度或索引、或字符串或这些中的两个或更多个的组合。
根据第60实施例，在第50至第59实施例中的任何一个中，数据项的分量是所述数据项的二进制编码的位组。
根据第61实施例，在第60实施例中，位组包括6位。
根据第62实施例，在第50至第61实施例中的任何一个中，数据项是数目。
根据第63实施例，在第62实施例中，所述数据项是整数、长整数或双长整数。
根据第64实施例，在第62或第63实施例中的任一个中，数据项是64位整数。
根据第65实施例，在第62至第64实施例的任何一个中，所述数据项的分量是数位。
根据第66实施例，在第65实施例中，所述数位具有预定义基数，优选为64。
根据第67实施例，在第50至第66实施例中的任何一个中，数据项是字符串。
根据第68实施例，在第67实施例中，所述数据项的分量是单个字符。
根据第69实施例，在第50至第68实施例中的任何一个中，数据项是字节数组。
根据第70实施例，在第50至第69实施例的任一个中，所述trie是根据第1至第49实施例中的任一个的trie。
根据第71实施例，在第70实施例中，当从属于第34实施例时，数据项对应于键部或由键部所包括的内容信息。
根据第72实施例，在第33至第71实施例中的任何一个中，节点、优选地具有超过一个子节点的至少每个父节点包括位图和多个指针，其中，每个指针与在所述位图中设置的位相关联，并指向所述节点的子节点。
总体trie特征
位图和存储器详细信息
根据第73实施例，在第1至第32、或第49或第72实施例中的任何一个中，所述位图作为预定义大小的整数而存储在存储器中。
根据第74实施例，在第1至第32、或第49或第72或第73实施例中的任何一个中，所述位图的大小是32、64、128或256位。
根据第75实施例，在第1至第32、或第49或第72至第74实施例中的任何一个中，所述trie适合于在目标计算机系统上存储和处理，并且所述位图的大小等于所述目标计算机系统的CPU的寄存器、系统总线、数据总线和/或地址总线的位宽。
根据第76实施例，在第1至第32、或第49或第72至第75实施例中的任一个中，所述trie的位图和/或指针和/或节点被存储在数组中，优选地存储在长整数数组或字节数组中、列表中或连续的物理或虚拟存储器位置中。
根据第77实施例，在第1至第16、或第26至第27或第76实施例中的任何一个中，所述存储器是或包括物理存储器或虚拟存储器，优选地连续存储器。
指针
根据第78实施例，在第1至第32、或第49或第72至第77实施例中的任何一个中，由父节点、优选地具有超过一个子节点的至少每个父节点所包括的指针的数量等于由所述父节点所包括的位图中设置的位的数量。
根据第79实施例，在第1至第32、或第49或第72至第78实施例中的任一个中，指针在父节点的所有指针中的指针的等级对应于指针的相关联的设置位在所述父节点的位图中的所有设置位中的等级。
根据第80实施例，在第1至第32、或第49或第72至第79实施例中的任一个中，所述指针以与在所述位图中设置的位相同或相反的顺序存储。
根据第81实施例，在第1至第33、或第49或第72至第80实施例中的任何一个中，由父节点所包括的指针指向由所述子节点所包括的位图。
根据第82实施例，在第1至第33、或第49或第72至第81实施例中的任何一个中，由所述叶节点、优选地所述trie的每个叶节点所包括的指针的数量为零。
键部分
根据第83实施例，在第3或第33至第82实施例中的任何一个中，子节点的键部分的值、优选地其父节点具有超过一个子节点的至少每个子节点的键部分的值由所述父节点所包括的位图中(设置)的位的值确定，取决于所述子节点与哪个位相关联。
根据第84实施例，在第4至第18中的任何一个或第83实施例中，可用于所述键部分的不同值的最大量由所述位图的大小定义。
根据第85实施例，在第4至第18、或第83或第84实施例中的任何一个中，所述位图的大小定义了所述键部分的可能字母表。
根据第86实施例，在第3或第32至第85中的任何一个中，所述trie中的每个键部分能够存储相同的预定义大小的值。
根据第87实施例，在第86实施例中，所述预定义大小对应于5位、6位、7位或8位值。
有效范围查询的键编码
根据第88实施例，在前述实施例中的任何一个中，通过将数据项的数据类型转换为包含无符号整数的偏移二进制表示来获得数据项的值的编码、优选地所有数据项的值的编码。
根据第89实施例，在第88实施例中，所述整数是长整数。
根据第90实施例，在第88或第89实施例中的任何一个中，如果数据项的数据类型是浮点数，则通过将所述数据项的数据类型转换为偏移二进制表示来获得所述编码。
根据第91实施例，在第88至第90实施例中的任何一个中，如果数据项的数据类型是二进制补码有符号整数，则通过将数据项的数据类型转换为偏移二进制表示来获得所述编码。
其他
根据第92实施例，在前述实施例中的任何一个中，所述trie存储动态集合或关联数组。
对trie的布尔操作
本发明的第93实施例是一种从电子数据库或信息检索系统检索数据的方法，包括以下步骤：获得两个或更多个输入trie的表示；评估(evaluate)结果trie的至少部分，所述结果trie是使用逻辑运算的输入trie的组合；并提供以下作为输出：结果trie的表示，与结果trie的节点相关联的键和/或其他数据项的集或子集，或从与结果trie的节点相关联的键导出的键集或值集。
根据94实施例，在第93实施例中，与结果trie的叶节点相关联的键和/或其他数据项被提供作为输出。
根据第95实施例，在93或94实施例中，其中，作为输出而提供的键集在trie中提供。
根据第96实施例，在93或94实施例中的任何一个中，其中，作为输出而提供的键集由游标或迭代器提供。
根据第97实施例，在实施例93至96中的任一项中，其中trie的部分是trie的节点和/或分支。
根据第98实施例，在实施例93至97中的任一项中，其中trie的表示是物理trie数据结构或能够评估trie的trie运算符的句柄。
根据第99实施例，在实施例93至98中的任一项中，其中trie的表示代表trie的根节点并实现trie节点接口，其中trie节点接口代表trie节点并提供用于查询和/或遍历它所代表的trie节点的子节点的方法或功能。
根据第100实施例，在实施例93至99中的任一实施例中，其中评估trie或trie的部分包括遍历trie或trie的部分。
根据第101实施例，在实施例100中，其中评估trie或trie的部分包括提供以下信息：所遍历的节点存在于trie中。
根据第102实施例，在实施例100或101中的任一项中，其中在对trie或trie的部分的评估期间的任何给定时刻，实现该trie或该trie的部分的物理数据结构的至少那些部分，其需要在那个时刻被实现以为了遍历trie或trie的部分。
根据第103实施例，在实施例100至102中的任一实施例中，其中在任何给定时刻，实现少于所述trie或所述trie的部分的整个物理数据结构，并且优选地实现trie或trie的部分的物理数据结构的仅那些部分，其需要在那个时刻被实现以为了遍历所述trie或所述trie的部分。
根据第104实施例，在实施例93至102中的任一实施例中，其中评估trie或trie的部分包括实现作为整体的trie或trie的部分的物理数据结构。
根据第105实施例，在实施例93至104中的任一实施例中，其中至少一个输入trie是虚拟trie，其至少部分在评估结果trie的至少部分的步骤期间被评估。
根据第106实施例，在实施例105中，其中至少在获得虚拟trie的表示的时刻，不存在作为整体的虚拟trie的物理数据结构。
根据第107实施例，在实施例105或106中的任一实施例中，其中，未实现作为整体的虚拟trie或虚拟trie的部分的物理数据结构。
根据第108实施例，在实施例105至107中的任一实施例中，其中评估虚拟trie的至少那些部分，其对于评估结果trie的至少部分是需要的。
根据第109实施例，在实施例105至108中的任一实施例中，其中，不评估虚拟trie的至少一些部分，其对于评估结果trie的至少部分不是需要的，并且优选地，评估虚拟trie的仅那些部分，其对于评估结果trie的至少部分是所需的。
根据第110实施例，在实施例105至109中的任一实施例中，其中，在已评估结果trie的至少部分之后，对虚拟trie部分的至少部分进行评估。
根据第111实施例，在实施例105至110中的任一实施例中，其中以交错的方式评估结果trie的部分和虚拟trie的部分。
根据第112实施例，在实施例105至111中的任何一个中，其中，两个或更多个输入trie是高阶输入trie，并且结果trie是高阶结果trie；并且提供至少一个虚拟trie的表示作为执行以下步骤的低阶组合运算符的输出：获得两个或更多个低阶输入trie的表示；至少部分地评估低阶结果trie，该低阶结果trie是使用低阶逻辑运算的低阶输入trie的组合；并提供低阶结果trie的表示作为输出。
根据第113实施例，在实施例112中，其中在完成至少部分地评估低阶结果trie的步骤之前执行提供低阶结果trie的表示作为输出的步骤。
根据第114实施例，在实施例112或113中的任一项中，其中低阶逻辑运算是与高阶逻辑运算相同的逻辑运算。
根据第115实施例，在实施例112或113中的任一项中，其中低阶逻辑运算是与高阶逻辑运算不同的逻辑运算。
根据第116实施例，在实施例112至115中的任何一个中，其中至少一个低阶输入trie是如在实施例105至111中的任何一个所定义的虚拟特例，必要时作必要的变通，其表示作为甚至更低阶组合运算符的输出被提供。
根据第117实施例，在实施例93至116中的任一实施例中，其中输入trie存储了被存储在电子数据库或信息检索系统中的键集或从被存储在电子数据库或信息检索系统中的一个或多个键集导出的结果键集。
根据第118实施例，在实施例93至117中的任何一个中，其中trie包含一个或多个节点，每个子节点与一个键部分相关联，并且从该trie中的根节点到另一个节点的路径定义了与该节点相关联的键，该键是与路径上的该节点相关联的键部分的级联。
根据第119实施例，在实施例93至118中的任何一个中，其中，使用逻辑运算的两个或更多个输入trie的组合是以下trie，其存储了在当使用逻辑运算组合由相应输入trie存储的相应键集时获得的键集。
根据第120实施例，在实施例93至119中的任何一个中，如果逻辑运算不同，则所述结果trie的父节点是第一输入trie的父节点，并且所述结果trie的父节点的叶节点是使用所述逻辑运算的、第一输入trie中的对应父节点的子节点集与其他输入trie中的任何对应父节点的子节点集的组合，并且如果所述逻辑运算没有不同，则所述结果trie中的每个节点的子节点集是使用所述逻辑运算的、输入trie中的对应节点的子节点集的组合；并且如果与不同trie的节点相关联的键相同，则不同trie的两个或更多个节点彼此对应。
根据第121实施例，在实施例93至120中的任一实施例中，其中，通过使用逻辑运算组合与所述结果trie的节点相对应的所述输入trie的节点的子节点集来确定所述结果trie的节点的子节点集。
合并步骤
根据第122实施例，在第93至第122实施例中的任何一个中，其中，评估结果trie或结果trie的部分的步骤包括：对所述结果trie的根节点执行组合函数；其中，对所述结果trie的输入节点执行所述组合函数包括：通过使用所述逻辑运算组合对应于所述结果trie的输入节点的输入trie的节点的子节点集来确定所述结果trie的输入节点的子节点集；并且对针对所述结果trie的输入节点确定出的每个子节点执行所述组合函数。
根据第123实施例，在第93至第122实施例中的任何一个中，使用深度优先遍历、广度优先遍历或其组合来执行评估结果trie或结果trie的部分的步骤。
根据第124实施例，在第123实施例中，以深度优先遍历执行评估结果trie或结果trie的部分的步骤包括：对所述输入节点的子节点之一执行所述组合函数，并在对该子节点的下一个兄弟节点执行所述组合函数之前遍历由该子节点形成的子trie。
根据第125实施例，在第123或第124实施例中的任何一个中，以广度优先遍历执行评估结果trie或结果trie的部分的步骤包括：对针对所述结果trie的输入节点确定出的每个子节点执行所述组合函数，并且在对所述结果trie的输入节点的任何孙子节点执行所述组合函数之前，确定针对所述结果trie的输入节点确定出的每个子节点的子节点集。
位图
根据第126实施例，在第93至第125实施例中的任何一个中，输入trie中的节点、优选地输入trie中的至少所有父节点包括位图。
根据第127实施例，在第126实施例中，trie中的子节点的键部分的值由所述子节点的父节点所包括的位图中(设置)的位的值确定，取决于所述子节点与哪个位相关联。
根据第128实施例，在第126或第127实施例中的任何一个中，其中，使用逻辑运算来组合与结果trie的节点相对应的输入trie的节点的子节点集，优选地包括：使用逻辑运算按位组合与结果trie的节点相对应的输入trie的每个节点的位图，从而获得组合位图。
根据第129实施例，在实施例128中，其中基于组合位图、优选地仅基于组合位图来确定和/或评估结果trie的节点的子节点。
根据第130实施例，在实施例128或129中的任一项中，其中在确定和/或评估结果trie的节点的子节点之前和/或对结果trie的评估遍历结果trie的节点的子节点之前，执行组合所述位图的步骤。
逻辑运算
第131实施例，在第93至第130实施例中的任何一个中，所述逻辑运算是求交集、并集、差集或异或。
根据第132实施例，在第131实施例中，使用所述逻辑运算包括使用AND布尔运算、OR布尔运算、AND NOT布尔运算或XOR布尔运算进行组合。
根据第133实施例，在第93至第132实施例以及第105实施例中的任一个中，使用所述逻辑运算包括使用按位AND布尔运算、按位OR布尔运算、按位AND NOT布尔运算、或按位XOR布尔运算来组合节点的位图。
范围查询
第134实施例是一种通过对被存储在电子数据库或信息检索系统中的键集或者从被存储在电子数据库或信息系统中的一个或多个键集导出的结果键集执行范围查询来从所述电子数据库或信息检索系统中检索数据的方法，所述方法包括以下步骤：获得一个或多个范围的定义；并执行第93到第133实施例中任何一个所述的从电子数据库或信息检索系统检索数据的方法，其中一个输入trie是输入集trie，其存储要搜索所述一个或多个范围的键集或结果键集；另一个输入trie是范围trie，其存储已获得所述定义的所述一个或多个范围中包括的所有值；并且所述逻辑运算是交集。
根据第135实施例，在第134实施例中，范围是离散的有序值的集合，包括某个数据类型的第一值和第二值之间的所有值。
根据第136实施例，在第135实施例中，所述范围包括所述第一值和/或第二值。
根据第137实施例，在第134至第136实施例中的任何一个中，在执行实施例93至133中任一项的方法的步骤中，执行实施例93至111中任一项的方法，其中，作为虚拟trie的输入trie中的至少一个是范围trie。。
单项输入集trie
根据第138实施例，在第137实施例中，所述一个或多个范围的定义包括针对所述一个数据项的一个或多个范围的定义。
多项输入集trie
根据第139实施例，在第134至第137实施例中的任一项中，与所述输入集trie的叶节点相关联的键对特定数据类型的两个或更多个数据项进行编码。
根据第140实施例，在第139实施例中，所述一个或多个范围的定义包括针对所述数据项中的一个或多个数据项的一个或多个范围的定义。
从单项范围trie获得多项范围trie
根据第141实施例，在第139或第140实施例中的任何一个中，所述范围trie是多项范围trie，其通过组合针对由与所述输入集trie的叶节点相关联的键所编码的数据项中的每个数据项的单项范围trie而获得，其中针对数据项的单项范围trie存储所述数据项的一个或多个范围中包括的所有值。
根据第142实施例，在第141实施例中，在实施所述输入集trie与所述多项范围trie的组合的函数内执行所述单项范围trie的组合。
根据第143实施例，在第141实施例中，所述单项范围trie的组合由以下函数执行，其将所述多项范围trie作为输入提供至实施所述输入集trie与所述多项范围trie的组合的函数。
根据第144实施例，在第141至第143实施例中的任何一个中，单项范围trie是以下虚拟trie，其至少部分在组合单项范围trie的操作期间被评估，优选地如实施例105至111中任一实施例所定义的虚拟trie(加以必要的修改)。
根据第145实施例，在第141至第144实施例中的任何一个中，没有获得范围定义的每个数据项的单项范围trie存储了所述数据项的可能值的整个范围。
根据第146实施例，在第141至第144实施例中的任何一个中，所述多项范围trie存储了被存储在所述单项范围trie中的数据项的值的所有组合。
范围trie的结构
根据第147实施例，在第141到第146实施例中的任何一个中，范围trie具有与所述输入集trie相同的结构或格式。
根据第148实施例，在第147实施例中，与范围trie的叶节点相关联的键对与同所述输入集trie的叶节点相关联的键相同数据类型的数据项进行编码。
根据第149实施例，在第147或第148实施例中的任何一个中，在范围trie中，将特定数据类型的数据项或这种数据项的分量在相同等级的节点中编码为输入集trie中的对应数据项或所述数据项的分量。
范围查询的输出
根据第150实施例，在第134至第149实施例中的任何一个中，所述方法提供与输入集trie的叶节点相关联的键集作为输出。
根据第151实施例，在第139至第149实施例中的任何一个中，所述方法提供简化项键集作为输出，其对由与所述输入集trie的叶节点相关联的键所编码的数据项的子集进行编码。
根据第152实施例，在第151实施例中，在提供所述输出之前，合并了作为所述输入集trie与所述范围trie的组合的结果的、从与未在所述简化项键中编码的数据项有关的输入集trie的不同分支中获得的简化项键集被合并。
根据第153实施例，在第151或第152实施例中的任一个中，在提供所述输出之前，作为组合所述输入集trie与所述范围trie的操作的结果而获得的简化项键集被写入新创建的trie，从而消除重复的键。
模糊搜索
第154实施例是一种通过执行近似字符串匹配从电子数据库或信息检索系统中检索数据的方法，所述方法包括以下步骤：获得搜索字符串；构建匹配trie，其存储近似字符串集，所述近似字符串集包括所述搜索字符串和/或所述搜索字符串的变型；评估结果trie的至少部分，所述结果trie是使用交集运算将匹配trie与存储trie的组合，所述存储trie存储了被存储在所述电子数据库或信息检索系统中的字符串集；提供与所述结果trie的节点的结果集相关联的字符串和/或其他数据项作为输出；其中trie包括一个或多个节点，每个子节点与键部分相关联，并且从所述trie中的根节点到另一个节点的路径定义了与所述节点相关联的键，所述键是与所述路径上的节点相关联的键部分的级联。
根据第155实施例，在154中实施例，由存储在匹配trie中的字符串集所包括的字符串被永久地存储在电子数据库或信息检索系统中。
根据第156实施例，在154或155实施例中的任何一个中，由存储在匹配trie中的字符串集所包括的字符串表示电子数据库或信息检索系统中的条目。
根据第157实施例，在第154至156实施例中的任何一个中，匹配trie中的一个或多个子节点具有超过一个父节点。
根据第158实施例，在第154或157实施例中的任何一个中，匹配trie中的一个或多个子节点具有仅一个父节点。
根据第159实施例，在第154至第158实施例中的任何一个中，结果trie是以下trie，其存储了在当存储trie所存储的键集与匹配trie所存储的键集进行交集运算时获得的键集。
根据第160实施例，在第154至第158实施例中的任何一个中，所述结果trie中的每个节点的子节点集是所述匹配trie中和所述存储trie中的对应节点的子节点集的交集，其中如果相同键与不同trie的节点相关联，则所述不同trie的节点彼此对应。
根据第160实施例，在第154至第160实施例中的任何一个中，所述匹配trie是虚拟trie，其至少部分在评估结果trie的至少部分的步骤期间被评估或动态地生成。
根据第161实施例，在实施例160中，其中没有实现作为整体的虚拟trie或虚拟trie的部分的物理数据结构。
根据第162实施例，在实施例160或161中的任何一个中，其中评估虚拟trie的至少那些部分，其是评估所述结果trie的至少部分所需的。
根据第163实施例，在实施例160至162中的任何一个中，其中，不评估虚拟trie的至少一些部分，其是评估结果trie的至少部分不是所需的，并且优选地仅评估虚拟trie中的那些部分，其是评估结果trie的至少部分所需的。
根据第164实施例，在实施例160至163中的任何一个中，其中，在结果trie的至少部分已被评估之后，对虚拟trie的至少部分进行评估。
根据第165实施例，在实施例160至164中的任何一个中，其中，以交错的方式评估结果trie的部分和虚拟trie的部分。
根据第166实施例，在实施例154至165中的任何一个中，其中评估trie或trie的部分包括遍历该trie或该trie的部分。
根据第167实施例，在实施例154至166中的任何一个中，其中评估trie或trie的部分包括提供以下信息：所遍历的节点存在于trie中。
根据第168实施例，在实施例154至167中的任何一个中，其中在对trie或trie的部分进行评估期间的任何给定时刻，实现trie或trie的部分的物理数据结构的至少那些部分，其需要在那个时刻被实现以用于遍历trie或trie的部分。
根据第169实施例，在实施例154至168中的任一实施例中，其中在任何给定时刻，实现少于trie或trie的部分的整个物理数据结构，并且优选地，仅实现trie或trie的部分的物理数据结构的那些部分，其需要在那个时刻被实现以用于遍历所述trie或所述trie的部分。
根据第170实施例，在154至169实施例中的任何一个中，其中评估trie或trie的部分包括：实现作为整体的trie或trie的部分的物理数据结构。
根据第171实施例，在第154至第170实施例中的任何一个中，在所述输出中提供的数据项表示数据单元，所述数据单元包含与所述结果trie的节点的结果集的节点相关联的字符串，优选地文档标识符。
根据第172实施例，在第154至第171实施例中的任何一个中，所述存储trie是索引trie或物理索引trie，优选地将由文档和相应的文档标识符所包括的字符串存储为例如两个键部(字符串、long)。
根据第173实施例，在第154至第172实施例中的任一个中，所述匹配trie包括匹配节点集，每个匹配节点与对应于来自所述近似字符串集的字符串之一的一个或多个键相关联，并且节点的结果集是对应于所述匹配trie中的匹配节点集的结果trie的节点集，其中，如果与所述结果trie的节点相关联的键与所述匹配trie的节点相关联的键相同，则所述结果trie的节点对应于所述匹配trie的节点。
根据第174实施例，在第154至第173实施例中的任何一个中，还包括获得数字N的步骤，其中，所述搜索字符串的变型包括能通过对所述搜索字符串的至多N个单字符插入、删除和/或替换而获得的字符串集。
根据第175实施例，在第154至第174实施例中的任何一个中，建立所述匹配trie的步骤包括：建立表示所述近似字符串集的有限自动机；并且从所述有限自动机中导出所述匹配trie。
根据第176实施例，在前述实施例中，所述有限自动机的两个状态之间的转换、优选地每个转换与特定字符、优选地由所述搜索字符串所包括的字符、或通配符或空字符串相关联。
根据第177实施例，在第175或第176实施例中的任何一个中，建立所述有限自动机的步骤包括：建立表示所述近似字符串集的非确定性有限自动机；并且从所述非确定性有限自动机中导出确定性有限自动机；并且其中所述匹配trie是从所述确定性有限自动机中导出的。
根据第178实施例，在前述实施例中，所述确定性有限自动机的两个状态之间的转换、优选地每个转换与特定字符、优选地由所述搜索字符串所包括的字符或通配符相关联。
根据第179实施例，在第154至第178实施例中的任一个中，所述匹配trie和所述存储trie中的节点、优选地至少所有父节点包括位图，并且trie中的子节点的键部分的值由所述子节点的父节点所包括的位图中的位(集)的值确定，取决于所述子节点与哪个位相关联。
根据第180实施例，在前述实施例中，其中确定结果trie的节点的子节点包括：将匹配trie的节点的子节点集和与结果trie的节点相对应的存储trie的节点的子节点集相交。
根据第181实施例，在前述实施例中，其中将匹配trie的节点的子节点集与存储trie的节点的子节点集相交包括：使用按位AND运算将匹配trie的节点与存储trie的节点的位图组合，从而获得组合位图。
根据第182实施例，在前述实施例中，其中，基于组合位图、优选地仅基于组合位图，确定和/或评估结果trie节点的子节点。
根据第183实施例，在实施例181或182中的任何一个中，其中在确定和/或评估结果trie的节点的子节点和/或对结果trie的评估遍历到结果trie的节点的子节点之前，执行组合所述位图的步骤。
根据第184实施例，在第171以及第179至第183实施例中的任何一个中，从所述有限自动机中导出所述匹配trie的步骤包括：通过关联与所述有限自动机的两个状态之间的转换优选地每个转换经由与转换相关联的特定字符或通配符的编码来获得增强有限自动机，其中所述编码由一个或多个位图组成或表示，其长度和/或格式等于被所述匹配trie的父节点包括的位图的，并且其中所述匹配trie是从所述增强有限自动机中导出的。
根据第185实施例，在前述实施例中，对于特定字符的编码，在由所述编码包括或表示的位图中的每个中恰好设置了一位。
根据第186实施例，在第184或第185实施例中的任何一个中，对于通配符的编码，所有有效字符编码的位都设置在由所述编码包括或表示的位图中，或者除了与所述转换所离开的状态相关联的特定字符的编码以外的所有有效字符编码的位。
根据第187实施例，在第179至第186实施例中的任何一个中，被存储在所述匹配trie、所述存储trie或所述结果trie中的字符由数量为M>1、优选5>M的相应trie的键部分编码。
根据第188实施例，在前述实施例中，从所述有限自动机中导出所述匹配trie的步骤包括：通过使用M–1个级别的中间状态和经由M–1个中间状态链接两个状态的M个转换的一个或多个序列来替换所述有限自动机的两个状态之间的转换优选地每个转换、或通过将所述有限自动机的两个状态之间的转换优选地每个转换与M–1个级别的中间状态和经由M–1个中间状态链接所述两个状态的M个转换的一个或多个序列相关联而获得表示所述近似字符串集的完全有限自动机，其中序列中的M个转换中的每个与中间编码相关联，所述中间编码由位图组成或表示，其长度和/或格式等于被所述匹配trie的父节点所包括的位图，并且其中，所述匹配trie从完全有限自动机导出。
根据第189实施例，在第188实施例中，如果所述有限自动机的两个状态之间的转换与特定字符相关联，则由与序列的M个转换相关联的中间编码所包括或表示的位图的级联是所述特定字符的编码，并且在所述位图中的每个中恰好设置了一位。
根据第190实施例，在第188或第189实施例中的任何一个中，如果所述有限自动机的两个状态之间的转换与通配符相关联，则由与序列的M个转换相关联的中间编码所包括或表示的位图的级联包括：以下编码，其中所有有效字符编码的位都设置在由所述编码所包括或表示的位图中，或者除了与所述转换所离开的状态相关联的特定字符的编码之外的所有有效字符编码的位，和/或一个或多个编码，包括特定字符的编码的一个或多个部分和以下编码的一个或多个部分，其中所有有效字符编码的位都设置在由所述编码所包括或表示的位图中，或者除了与所述转换所离开的状态相关联的特定字符的编码之外的所有有效字符编码的位。
根据第191实施例，在第184到第186的任何一个中，或在188到190的任何一个实施例中，所述增强有限自动机或完全有限自动机分别由包括多个行的数据结构表示或存储在其中，每一行表示增强有限自动机或完全有限自动机的一个状态，并包括针对离开所述状态的转换中的每个的元组，每个元组包括与所述转换相关联的编码以及对所述转换结束的状态的引用。
根据第192实施例，在前述实施例中，针对转换结束的每个状态，所述数据结构包括关于所述状态是否是匹配状态的信息，优选地在对所述状态的每个引用中被编码为位。
根据第193实施例，在第191或第192实施例中的任何一个中，所述数据结构包括转换从其离开的各自针对所述增强有限自动机或所述完全有限自动机的状态中的每个的行。
数据结构
根据第194实施例，在第93至第193实施例中的任何一个中，trie是根据第1至第92实施例中的任何一个的trie。
不同类别的发明
第195实施例是一种在电子数据库应用程序或信息检索系统中使用第1至第92实施例中的任何一个所述的trie的计算机实施的方法，特别是用于存储键或者键和值、用于存储结果键或者查询的键和值、或用于存储输入键或者查询的键和值。
第196实施例是生成第1至第92实施例中的任何一个的trie的计算机实施的方法。
第197实施例是一种非暂时性计算机可读介质，其上存储有第1至第92实施例中的任何一个的trie。
第198实施例是电子数据流，其表示第1至第92实施例中的任何一个的trie。
第199实施例是一种电子数据库或信息检索系统，其借由第1至第92实施例中任何一个的trie来存储键或者键和值、结果键或者查询的键和值、或输入键或者查询的键和值。
本发明的第200实施例是一种计算机程序、特别是数据库应用程序或信息检索系统程序，包括用于执行第93至第196实施例中的任何一个的方法的指令。
本发明的第201实施例是一种数据处理装置或系统，包括一个或多个处理器和存储器，所述数据处理装置或系统被配置为执行第93至第196实施例中的任何一个的方法。
本发明的第202实施例是优选地非暂时性计算机可读介质，其上存储有第201实施例的计算机程序。
附图说明
在下文中，将组合优选实施例并参考附图来更详细地描述本发明，其中
图1示出了现有技术数据库中使用的trie数据结构的示例；
图2示出了现有技术中使用的trie数据结构的另一示例；
图3示出了图2的trie数据结构的现有技术实施方式；
图4示出了图2的trie数据结构的另一现有技术实施方式；
图5示出了图2的trie数据结构的另一现有技术实施方式；
图6示出了在现有技术trie中如何确定节点的子指针；
图7A至图7C示出了根据本发明的叶节点如何被存储在映射中以及“最后”位图如何被存储在trie中的集合中；
图8提供了trie的示例，其中根据本发明的第一空间优化是有效的；
图9示出了根据本发明的第一空间优化；
图10提供了trie的示例，其中根据本发明的第二空间优化是有效的；
图11示出了根据本发明的第二空间优化的一般存储配置；
图12示出了根据本发明的第二空间优化；
图13示出了如何以统一的方式访问根据本发明进行了空间优化的trie的节点；
图14A至图14C示出了将键插入到根据本发明进行了空间优化的trie中；
图15示出了为测量根据本发明的第一空间优化和第二空间优化的效率而进行的实验的结果；
图16示出了根据本发明的第三空间优化；
图17示出了为测量根据本发明的第三空间优化的效率而进行的实验的结果；
图18示出了根据本发明将控制和内容信息布置在要存储在trie中的键中的第一方式；
图19示出了根据本发明将控制和内容信息布置在要存储在trie中的键中的第二方式；
图20示出了根据本发明的键编码的示例；
图21示出了存储根据本发明编码的键的trie；
图22示出了具有值(X＝12，Y＝45)的二维键的示例；
图23给出了根据本发明如何将图21中示出的键存储在trie中的示例；
图24示出了现有技术中数据库查询处理的阶段；
图25示出了在现有技术数据库中使用的示例性查询执行计划；
图26示出了根据现有技术数据库中的查询执行模型的运算符控制和数据流；
图27示出了根据现有技术数据库的查询执行模型的一次元组(tuple-at-a-time)处理；
图28示出了根据现有技术数据库的查询执行模型的一次运算符(operator-at-a-time)处理；
图29示出了根据本发明的查询执行模型的trie控制和数据流；
图29A示出了根据本发明的查询执行模型的另一个trie控制和数据流；
图30示出了根据本发明的将交集运算符应用于两个trie的示例；
图31示出了将在其上执行根据本发明的交集操作的两个示例trie；
图32示出了在级别1和级别2上对图31的两个示例trie的位图执行的按位AND操作；
图33示出了在图31的对两个trie的交集运算期间的分支跳跃；
图34示出了在图31的对两个trie的交集运算的结果trie；
图35示出了根据本发明的将并集运算符应用于两个trie的示例；
图36示出了图35的两个trie上并集运算的结果trie；
图37示出了根据本发明的将差集运算符应用于两个trie的示例；
图37A示出了将根据图29A所示的数据流进行组合的三个trie；
图37B示出了图37A所示的trie的组合的结果；
图38示出了根据本发明的交集运算符、输入集trie和范围trie在范围查询中的交互；
图39示出了根据本发明的执行范围查询的方法的示例；
图40示出了根据本发明的执行二维范围查询的方法的示例；
图41示出了如何以交错方式组合图40的一维范围trie；
图42示出了由于图41获得的交错范围trie；
图43示出了如何以非交错方式组合图40的一维范围trie；
图44示出了由于图43获得的非交错范围trie；
图45示出了如果以非交错方式存储输入集trie，则在范围查询期间访问了图40的输入集trie的哪些节点；
图46示出了如果以交错方式存储输入集trie，则在范围查询期间访问了图40的输入集trie的哪些节点；
图47示出了根据本发明的具有一维输出的二维范围查询；
图48A示出了非确定性有限自动机，以匹配具有最大编辑距离为2的搜索字符串“abc”；
图48B示出了编辑距离为1时用于匹配“abc”的确定性有限自动机；
图48C示出了图48B的自动机的转换的增强，其中使用了参照图21描述的Unicode字符和Unicode字符串的编码方案；
图48D显示了匹配trie的结果顶部，其中每个10位Unicode字符由两个键部分表示；
图48E示出了作为数组的数组的数据结构，其可以用来表示完全有限自动机的状态，从中可以导出图48D的匹配trie；
图49示出了针对慕尼黑地区小矩形内所有位置的实验性地理数据搜索查询的规范；
图50示出了加载到数据库中以执行第一系列的实验地理数据搜索查询的剩余记录；
图51示出了加载到数据库中以执行第二系列的实验地理数据搜索查询的剩余记录；
图52示出了由实验地理数据搜索查询确定出的临时结果集和最终结果集；
图53示出了现有技术方法的性能测量结果；
图54示出了在根据本发明的标准索引方法中使用的非交错二维索引trie的抽象视图；
图55示出了在根据本发明的标准索引方法中的多OR运算符的使用；
图56提供了根据本发明的在标准索引方法中使用的分量的概述；
图57示出了根据本发明的标准索引方法的性能测量结果；
图58示出了根据本发明的用于可变精度索引方法的第一级索引的示例；
图59示出了根据本发明的用于可变精度索引方法的第二级索引的示例；
图60示出了根据本发明的可变精度索引的性能测量结果；
图61示出了根据本发明的以交错方式存储的二项键的部分如何彼此组合或与二维索引方法中的范围trie的部分组合；
图62示出了根据本发明的二维索引方法的性能测量结果；
图63示出了根据本发明的用于单索引的索引方法的存储三个项键的索引的结构；
图64提供了在根据本发明的单索引的索引方法中使用的分量的概述；
图65示出了根据本发明的单索引的索引方法的性能测量结果；
图66示出了其中在增加结果大小的情况下测量了查询性能的实验结果；
图67在具有对数x轴的图中示出了图66的结果；
图68示出了其中在增加的索引大小上测量索引性能的实验结果；
图69示出了对不同索引方法的空间要求；
图70A-70F在信息检索应用程序中将使用现有技术索引的数据库的索引性能、索引大小和查询性能与使用根据本发明的索引的数据库进行比较。
具体实施方式
本发明的优选实施例的详细描述
图1示出了根据现有技术的数据库中使用的trie数据结构的示例。它示出了trie数据结构101，其中每个子节点(即，除根节点外的所有节点)都与键部分相关联，键部分的值由来自父节点的指针指示并从字母表{0…9}中选择，即除根节点外的每个级别上的节点都与一个十进制数位相关联。从trie中的根节点到另一个节点的路径定义了与该节点相关联的键，该键是与路径上的节点相关联的键部分的级联(concatenation)。trie 101“存储”具有值“007”和“042”的键，这是因为trie 101的叶节点107与具有值“007”的键相关联，并且trie 101的叶节点108与具有值“042”的键相关联。
位于第一级110上的根节点102具有与值“0”的键部分相关联的一个子节点104。因此，存在从根节点102到位于trie 101的第二级111上的子节点104的指针103，其指示值为“0”。从第二级上的子节点104，两个不同的指针指向位于第三级112上的节点105、106，并且从这些节点105、106中的每个，一个另外的指针分别指向叶节点107、108。因此，从根节点到叶节点的路径上的节点的键部分的级联导致值为“007”和“042”的键。
图2示出了现有技术中使用的trie数据结构的另一示例。此示例的trie数据结构与图1的trie数据结构类似，但是具有与节点相关联的键部分的可能值的较大字母表。特别地，图2示出了256进制trie数据结构，其中键部分值的表示具有大小为8位(或1个字节)。
图2的trie数据结构存储两个不同的键(具有与其叶节点相关联的两个不同的键)“0000FD”和“002A02”，并具有四个级别210到214。位于第一级210上的根节点202具有指向与键部分值“00”相关联的子节点204的指针。子节点204包括指向子节点205、206的两个指针，分别与键部分值“00”和“2A”相关联。位于第三级212中的子节点205、206中的每个分别包括指向叶节点207、208的一个指针。叶节点207、208位于第四级213中。叶节点207与键部分值“FD”相关联，并且叶节点208与键部分值“02”相关联。
图3示出了图2的trie数据结构的现有技术实施方式。具有相关联的指针的节点完全在存储器中分配。因此，在这种情况下，即使是空(nil)指针也会占用存储器空间。例如，根节点302在其数组306中分配了256个指针，其中只有一个指针303不为空，该指针303与键部分值“00”相关联并指向子节点304。子节点以相同的方式实施。
图4描绘了图2的trie数据结构的示例性实施方式，其提供了用于更有效地使用存储器空间、避免存储空(null)指针的已知解决方案。该解决方案包括仅存储非空指针列表及其相应的键部分值，而不是包含所有可能的指针的数组。例如，具有与键部分值“00”相关联的一个子节点的根节点402包括具有一个条目的列表。该列表条目包括键部分值403和指向子节点405的相关联的指针404。相应地实施其他子节点。
图5示出了图2的trie数据结构的另一示例性实施方式，其基于用于标记父节点的所有非空指针的位图而提供了分配问题的已知解决方案。换句话说，位图中的设置位标记有效(非空)分支。每个父节点还包括一个或多个指针，其中每个指针与位图中的设置位相关联并指向父节点的子节点。
为了确定子节点的指针，必须计算前面的子指针的数量。如图6中示出的，用于查找指针的偏移是目标位置之前位图中设置的最低有效位的数量。这种紧凑的trie节点结构消除了存储nil指针的需要，并且同时允许非常快速的访问。
图5的示例的trie数据结构的字母表基数为256，这导致位图大小为256位。换句话说，每个位图可以为256个不同的键部分值(或子节点)标识256个指针。利用256个不同的值，可以编码8位(2
根节点502在其位图中设置了一个位，表示键部分值“00”。因此，根节点502仅包括指向子节点504的一个指针503，该子节点与具有值“00”的键部分相关联。子节点504在其位图中设置了两个位505、507，即表示键部分值“2A”和“00”的位。因此，子节点504包括两个指针507和508，其指向相应的子节点509、510。
通过计算从表示键部分值“2A”的位505开始设置多少个最低有效位来寻址与位图中值为“2A”的位相关联的指针506。在这种情况下，仅存在一个最低有效位被设置，即位506，因此可以确定存在一个指针的偏移，并且我们正在寻找的指针是由子节点504所包括的第二指针。
根据本发明的trie的优选实施例的一般特征
类似于所有trie，根据本发明的trie或trie数据结构包括一个或多个节点。如在上面参考图1至图6描述的现有技术trie中，优选地，优选实施例的trie的每个子节点与键部分相关联，其中从trie中的根节点到另一个节点、特别是到叶节点的路径定义了键，该键是与路径中的节点相关联的键部分的级联。根节点不与键部分相关联，并且将理解，trie可以包括不与键部分相关联的另外的节点，例如，因为它们用于其他目的。例如，子树中的条目数可以存储在这样的节点中，以避免或加速计数操作，这通常需要遍历整个树。
在根据本发明的trie的优选实施例中，节点、优选地具有超过一个子节点的至少每个父节点包括位图和多个指针。每个指针与在位图中设置的位相关联，并指向该节点的子节点。典型地，如果位的值为“1”，则在位图中“设置”该位。然而，在特定实施例中，如果位的值为“0”，则该位可以视为“设置”。如果位图中的位的值对应于与位图中的位标记了有效分支的概念相关联的值，则该位图中的位在此处视为“设置”，如上面参考图5中示出的现有技术trie所解释的。
优选地，位图作为预定义大小的整数存储在存储器中。此外，位图的大小优选地为32、64、128或256位。可以通过选择位图的大小以使得其等于目标计算机系统的CPU的寄存器、系统总线、数据总线和/或地址总线的位宽，来提高目标计算机系统存储和处理trie的操作性能。
例如，如上面提到的，可以基于在位图中设置的最低有效位的数量来计算与在位图中设置的位相关联的指针的存储器地址。使用简单的位操作和确定设置位的数量的CTPOP(计数填充)操作可以非常有效地进行此确定。许多现代CPU甚至将CTPOP作为内部指令提供。但是，由于在现代CPU中，长整数为64位宽，因此CTPOP仅在64位上工作。这意味着对于使用256位的位图的现有技术trie，该操作至多执行四次(4x 64＝256)。可替选地，现有技术trie将前面的位图的总位计数与前三个位图一起存储。然后可以将最低有效位的数量计算为最后的位组的CTPOP+先前位组的位计数。
由于当前在大多数计算机系统中系统位宽是64位，因此64位的位图大小当前是最优选的大小，并且被发明人用于他的发明的示例实施方式。这导致64进制的trie，这意味着每个节点都可以存储64个符号的字母表的符号，也就是说，它可以编码6位(2
可以将位图和/或指针存储在例如数组中、列表中或连续的物理或虚拟存储器位置中。注意，无论何时在本文中使用术语“存储器”，它都可以指物理或虚拟存储器，优选地是连续存储器。在优选实施例中，长整数(64位)用于表示位图，并且还用于表示子指针中的每个。代替在存储器中分开地分配节点，将节点存储在长整数数组中，并且代替具有针对节点的存储器指针，由索引将当前节点指定到该数组中。子指针可以是数组中节点位置的索引。当遍历trie时，用于基于当前节点索引发现子节点的索引的偏移则为针对位图的目标位置之前在位图中设置的最低有效位的数量加上1。
优选实施例适用于几个这样的数组。指针的一部分、例如下部是数组内的索引，而指针的另一部分、例如上部是对数组的引用。这样做是出于存储器管理的原因，这是因为并非总是可能分配任意大大小的数组。例如，在Java中，数组的大小限制为32位整数，并且这导致数组大小为2
类似于在图5和图6的现有技术trie中，父节点、优选地具有超过一个子节点的至少每个父节点典型地包括等于由所述父节点包括的位图中设置的位的数量的指针的数量。例如，图5中的节点504具有设置了两个位505、506的位图，并且包括两个指针507、508。在父节点的所有指针中的指针的等级优选地对应于父节点的位图中的所有设置位中的指针的相关联的设置位的等级。例如，在图5的父节点504中，第一指针507对应于位图的第一设置位505，并且第二指针508对应于第二设置位506。指针典型地以与位图中设置的位相同或相反的顺序存储。它们中的每个优选地指向由子节点包括的位图(的地址)，如例如下面在图9和图12中示出的，例如此位图的起始地址。
类似于在图5或图6的现有技术trie中，优选实施例的trie的子节点的键部分的值、优选地其父节点具有超过一个子节点的至少每个子节点的键部分的值，由父节点所包括的位图中(设置)的位的值确定，取决于所述子节点与哪个位相关联。因此，典型地通过位图的大小来定义可用于键部分的不同值的最大数量，和/或位图的大小定义键部分的可能字母表。
在本发明的优选实施例中，trie中的每个键部分都能够存储相同的预定义大小的值，例如5位值(如果位图的大小是32位的话)、6位值(如果位图的大小是64位的话)、7位值(如果位图的大小是128位的话)或8位值(如果位图的大小是256位的话)。由节点或键部分表示的字符的字母表是具有该大小的所有可能的位组的集合。例如，在键部分能够存储6位值的情况下，字母表是包括6位的所有位组的集合。
根据本发明的trie数据结构可用于实施：键-值映射(也称为“关联数组”)，其中值存储在叶节点中；以及键集(也称为“动态集合”)，其中叶节点中没有存储任何数据。在每个键只有一个值的情况下，使用映射来查找给定键的值，而集合用于确定给定集合是否包含给定键。对于这两种情况，对键的集合运算(诸如并集、交集或差集)也是经常需要的操作。
图7A至图7C示出了如何以紧凑的方式将叶节点存储在映射中以及如何将“最后的”位图存储在集合中，并且使得可以在恒定时间内访问所有值。图7A示出了如何针对具有较大和/或可变大小的值数据类型(诸如较长的字符串或文本)的键值映射存储叶节点。如图7A中示出的，该值被分别存储。如果值的大小与指针的大小相比而言较大，则指向该值的另外的指针idx所需的空间可以忽略。
在值数据类型为固定大小(诸如日期或整数)的情况下，存储值“内联(inline)”更为有效，如图7B中示出的，例如，直接在其父节点的位图后面。例如，根据本发明具有内联的优选实施例，可以通过trie数据结构有效地实施长到长映射，即其中键是长整数类型并且值也是长整数类型的映射。内联仅起作用于固定大小值的数据类型，这是因为在这种情况下，可以计算位置，例如作为CTPOP(位图&(bitpos-1))*大小。相反，对于可变大小值的数据类型，必须通过所有值条目来确定位置。
图7C示出了存储“最后的”位图的内联可以如何用于集合。由于不存在值，因此在无需指针的情况下最后的位图本身被内联。注意，在本文使用的术语中，物理级别上的这些“最后的”位图是叶节点的父节点的一部分，但是在这些位图中设置的位指示出逻辑级别上的叶节点的键部分的值。
trie数据结构以有序的方式存储键，并且因此允许按顺序遍历键。例如，可以存储从最高有效6位(或4位，因为64＝4+10*6)到最低有效6位开始的64位长整数键。这样，整数将被视为无符号长整数。对于典型地使用二进制补码编码的有符号整数，要具有正确的顺序，必须将其转换为偏移二进制表示，例如通过为64位长整数添加2
节省空间的trie数据结构
在许多应用场景中，存储器空间的使用效率很低。当trie稀疏地填充和/或退化为节点链时，尤其如此，其中每个节点只有单个子指针。
链式结点优化
发明人在经验研究中发现，对于任意键，典型应用场景中的trie有许多节点只有单个子节点。这是因为许多键共享公共的前缀、中缀或后缀。在这种情况下，现有技术的trie退化为具有单个子指针的节点链，并且现有技术的trie数据结构的空间效率低。
当节点仅具有单个子节点时，即在由父节点包括的位图中仅设置单个位时，本发明的第一空间优化消除了子指针。该方法在本文中被称为“链式节点优化”。图8中示出了链式节点优化有效的trie的示例。trie的级别4上的叶节点841、842、843共享公共前缀，该前缀包括：级别0上的根节点800；级别1上的节点810，其是根节点800的唯一子节点；级别2上的节点820，其是节点810的唯一子节点；以及级别3上的节点830，其是节点280的唯一子节点。
本发明的第一空间优化应用于包括一个或多个节点的trie，其中由trie所包括的父节点、优选地具有超过一个子节点的每个父节点包括位图和一个或多个指针，其中每个指针与位图中设置的位相关联，并指向父节点的子节点。通过以下事实来实现优化：由trie包括的父节点、优选地仅具有一个子节点的每个父节点不包括指向该子节点的指针，和/或将子节点存储在存储器中相对于父节点的预定义位置中。优选地，仅具有一个子节点的父节点的子节点被存储在存储器中直接位于父节点后面的位置中。
在图9中示出了根据本发明的第一空间优化，其示出了在链式节点优化之前的trie 910的部分，以及与在应用链式节点优化之后的trie 910相对应的trie 920的部分。如上面描述的优选实施例中，trie 910、trie 920中的节点存储在长整数数组中，其由trie910、trie 920的部分的图示左侧的表达式“long[]”指示出。
trie 910包括第一节点911，该第一节点911仅具有一个单个子节点，如由节点911的(64位宽)位图指示出的，其中仅一个位被设置(1)，并且所有其他位未被设置(0)。类似于在现有技术trie中，节点911因此包括一个单个指针914，其是长整数，指向节点911的子节点(节点912)。节点912具有两个子节点，在图9中未示出，如由在节点912的(64位宽)位图中设置的两位以及由节点912包括的两个指针915、916指示出的。如由节点911和节点912之间的三个点(“…”)指示出的，节点912将典型地不存储在直接位于节点911后面的存储器位置中，而是可以被存储在长整数数组中的任何位置。
trie 920还包括仅具有一个单个子节点的第一节点921，如节点921的(64位宽)位图指示出的，其中仅一个位被设置(1)，并且所有其他位未被设置(0)。但是，与trie 910中的节点911相比而言，trie 920中的节点921不包括指向节点921的子节点(节点922)的指针。代替的是，节点922存储在直接位于节点921后面的存储器位置中，如优选地，但是可替选地，可以存储在长整数数组中的任何位置，只要预定义了存储器中相对于父节点921的位置即可。例如，子节点922可以直接存储在父节点921前面，或者在父节点921和子节点922之间可以存在固定长度的另一个数据对象。类似于trie 910的节点912，trie 920的节点912具有两个子节点，在图9中未示出，其在存储器中的位置(在长整数数组中)由节点922所包括的两个指针925和926指示出。
在图9的示例实施例中，由长整数、即由相同数据类型或相同长度的数据类型来表示节点所包括的位图和指针中的每个，根据本发明的链式节点优化将存储节点与一个单个子节点所需的存储器空间减少了50％。
终端优化
本发明的第二空间优化提供了存储器中的trie的更紧凑的表示，其中trie的“末端”包括单个节点的链或串，即，许多键没有共同的后缀。图10中示出了第二空间优化有效的trie的示例。图10中的trie的叶节点1041、1042、1043、1044、1045中的每个是独立(非公共)后缀的一部分。每个后缀包括在trie的级别3上的一个节点1021、1022、1023、1024、1025，在trie的级别4上的一个节点1031、1032、1033、1034、1035和在级别5上的一个叶节点。级别2上的节点1021、1022、1023、1024、1025和级别4上的节点1031、1032、1033、1034、1035中的每个只有一个单个子节点。
根据第二空间优化，在单个节点的字符串的开始处的节点被标记为“终端分支节点”。在图10中，终端分支节点是在trie的级别3上的节点1021、1022、1023、1024、1025。字符串中其余节点的键部分的值仅以其“本地”或文字编码连续存储，而不是由其父节点包括的位图中的位(集合)的值确定。该方法在本文中被称为“终端优化”。
因此，本发明的第二空间优化适用于包括一个或多个节点的trie，其中由trie所包括的父节点、优选地具有超过一个子节点的至少每个父节点包括位图；节点、优选地每个子节点与键部分相关联；并且子节点(优选地是其父节点具有超过一个子节点的至少每个子节点)的键部分的值，由父节点所包括的位图中的位(集合)的值确定，取决于所述子节点与哪个位相关联。
在Bagwell博士的“Fast And Space Efficient Trie Searches”，技术报告，EPFL，瑞士(2000)中，其中在存储器中独立分配节点，称为“树尾压缩”的方法使用指向字符串节点的指针进行引用，或将终端字符串的数值直接存储在终端分支节点中。但是，由于偏移和节点类型(具有位图的节点或具有字符/指针列表的节点)必须存储在节点中，因此该方法不节省空间。
根据本发明的终端优化通过以下方式来克服该问题：通过没有位被设置的位图来标记节点，优选地trie中的仅具有一个子节点的并且其所有后代节点至多具有一个子节点作为终端分支节点的每个节点。本发明使用由优选实施例的标准节点包括的位图的特殊质量，即它们总是至少一位被设置。这是因为具有全零位图的节点将是一个没有子节点的节点，但是没有子节点的节点不需要在存储器中表示。因此，特殊含义可以归因于未设置位的位图，并且终端分支节点的位图的长度或格式可以与具有超过一个子节点的父节点所包括的位图的长度或格式相同。
与终端分支节点(优选地每个终端分支节点)的后代节点(优选地每个后代节点)相关联的键部分的值不是由后代节点的父节点所包括的位图中(设置)的位的值确定出的。相反，对键部分的值进行编码，使得其表示相比具有超过一个子节点的父节点所包括的位图而言需要较少的存储器空间。典型地，键部分的值将被编码为二进制数(数字)，诸如整数值。例如，在由标准节点包括的位图分别具有32位、64位、128位或256位的情况下，与终端分支节点的后代节点相关联的键部分分别由5位、6位、7位或8位编码。
图11中示出了根据本发明的优选实施例的终端优化的一般存储配置。在其中未设置任何位的64位宽位图后面跟着多个(通常至少两个)编码为二进制数的6位键部分。但是，在优选实施例中，每个6位键部分存储在8位块(一个字节)中。由于仅使用了可用的8位中的6位，因此这浪费了一些空间，但是从8位中的6位转换为8位中的8位编码并返回增加实施方式的复杂性并降低性能。发明人进行的测量示出了浪费空间是可以接受的，并且通过存储8位中的8位来改善空间是非常有限的。
终端分支节点和/或其后代节点不需要包括指向其一个子节点(如果有的话)的指针，这是因为子节点可以存储在存储器中相对于父节点的预定义位置，优选地直接在父节点后面，如图12中示出的。此外，与终端分支节点(优选地每个终端分支节点)的后代节点(优选地所有后代节点)相关联的键部分的值在终端分支节点之后连续存储。最后，如可以在图12中观察到的，在单个节点的字符串中，仅对于终端分支节点，它必须具有位图，以便将该节点标记为终端分支节点，而没有终端分支节点的后代节点需要包括位图，特别是其中设置位确定了与其子节点相关联的键部分的值的位图。
如从图14C中示出的和下面讨论的示例将变得显而易见的是，仅在终端分支节点具有超过一个后代节点的情况下，相比链节点优化而言，根据最优选实施例的终端优化更节省空间。此外，如果已经将一连串的单个节点中的第一个节点标记为终端分支节点，则可以实现最大的空间节省，使得终端分支节点的父节点具有超过一个子节点。
在图12中示出了根据本发明的第二空间优化，其示出了终端优化之前的trie1210的部分以及与应用终端优化之后的trie 1210相对应的trie 1220的部分。trie 1210、trie 1220的节点再次存储在长整数数组中。
trie 1210包括第一节点1211，该第一节点1211仅具有一个单个子节点，如由节点1111的位图指示出的，其中仅一个位被设置(1)，并且所有其他位未被设置(0)。设置的一位的值为“60”，如从以下事实可以看出，它是64位宽位图中左起的第四位，其中最右边的位的值为“0”，并且最左边的位的值为“63”。节点1211包括一个单个指针1213，其是长整数，指向节点1211的子节点(节点1212)。如节点1211和节点1212之间的三个点(“…”)指示出的，节点1112将典型地不存储直接在节点1111后面的存储器位置中，但可以存储在长整数数组中的任何位置。节点1212还具有一个子节点，如由从节点1212的64位宽位图中设置的右数第二位指示出的，该位值为“01”。但是，由于节点1212的子节点是叶节点，因此节点1212不包括指向其子节点的指针，而是指向叶节点部分1214的指针，其可以是映射的指针或值(参见图7A和图7B)，或为空的集合(请参见图7C)。叶节点未在存储器中表示。注意，不需要特定的“叶节点指示符”，这是因为在优选实施例中，trie的深度或存储在trie中的键的长度是已知的。
如可以观察到的，节点1211是终端分支节点，这是因为它只有一个子节点1212，并且其所有后代节点(1212和1212的子节点)至多具有一个子节点(节点1212具有一个子节点，并且1212的子节点具有零个子节点)。作为终端优化的应用程序的结果，从trie 1210获得trie 1220。对应于trie 1210的节点1211的trie 1220的节点1221通过向其提供没有设置位的64位宽的位图而已被标记为终端分支节点。与其子节点1222相关联的键部分的值(对应于trie 1211的子节点1212)不是由节点1221的位图中(设置)的位的值确定出的。键部分的值被编码为由节点1221所包括的二进制数，诸如整数，如图12中的数字“60”指示出的。键部分的值的这样的表示仅需要6位(64＝2
终端分支节点1221不包括指向其子节点1222的指针。相反，子节点1222被存储在存储器中相对于其父节点1221的预定义位置中，即直接在父节点后面。作为终端分支节点1221的后代节点的节点1222不包括位图，也不包括指向其子节点的指针，而仅包括对与节点1222的子节点相关联的键部分的值进行编码的二进制数，如在图12中由数字“01”指示出的。例如，值01可以编码为二进制数“000001”。节点1222的表示后面跟着存储器中的叶节点部分1224。同样，叶节点部分1224可以是映射的指针或值(参见图7A和图7B)，或者空的集合(参见图7C)。
在图12的示例实施例中，其中节点所包括的位图和指针中的每个均由长整数表示，终端优化的trie 1220需要64+6+6＝76位用于存储节点1221和1222。相比之下，未优化的trie 1210需要64+64+64＝192位来存储相同的信息(节点1211和1212，不计入trie 1210和trie 1220中都存在的叶节点部分1214)。
类似于在优选实施例中，长整数数组用于存储trie，根据本发明的终端优化遭受对准损失。在最坏的情况下，一个6位键部分存储在64位长整数中。但是，实验表明，平均而言，用于存储终端分支节点的后代节点的空间的50％被占用。此外，相比利用指针或利用链式节点优化存储数个单个子节点而言，终端优化仍然需要更少的空间。
现在将参考图13概述以统一的方式访问标准节点、通过链式节点优化而优化的节点和通过终端优化而优化的节点的方法。在示例实施方式中的查询执行模型中使用的节点访问的主要方法为：getBitSet()，其返回具有为trie节点的所有非空子指针设置的位的位图；以及getChildNode(bitNum)，其返回由位数指定的给定节点分支的子节点。这两个方法都由接口CDBINode提供，其中CDBI代表“汇合数据库索引”。另一个接口CDBINodeMem通过CDBINode接口提供了对数据模型的面向对象的访问。
必须克服的困难是如何在统一的中央位置处理这三种情况，而不必在代码中的许多地方分别处理它们。根据发明人发现的解决方案，并且如图13中示出的，不仅经由节点指针(索引)来引用节点，而且还经由基本节点索引(“nodeRef”)和节点内的索引(“idxInNode”)来引用节点，将没有指针的链以及终端视为一个节点，其基本节点索引指向终端节点或链的起点。以这种方式，存储器空间优化不会为“获取”操作增加显著的复杂性，并且因此不会降低性能。
由于nodeRef始终指向第一个位图，因此它用于检测getBitSet()和getChildNode(bitNum)的实施方式中的三种情况：
-如果位图设置了超过一个位，则它属于常规节点。getBitSet()返回该位图；getChildNode(bitNum)确定idx(指向子节点的指针)，并返回新的CDBINodeMem，将nodeRef设置为它(并且idxInNode设置为0)。
-如果位图为0(未设置位)，则它属于终端分支节点。getBitSet()将在idxInNode位置处字面存储的6位值转换为位图并返回它；getChildNode(bitNum)返回具有相同nodeRef和idxInNode+1的新CDBINodeMem。
-如果位图设置了一位，则它属于链式节点。getBitSet()返回idxInNode位置处的位图；getChildNode(bitNum)再次返回具有相同nodeRef和idxInNode+1的新CDBINodeMem。通过不创建新的耗时的子节点，而只是更新nodeRef和idxInNode(gotoChildNode方法)，即通过修改充当代理的现有对象，也可以将CDBINodeMem用作轻量模式。
图14A至图14C示出了将两个键插入空的trie的trie增长，第一个键的键部分值为[00，02，02]，并且第二个键的键部分值为[00，03，00，01]。图14A示出了空的trie，其由值为0的根索引指针表示。图14B示出了在添加键部分值为[00，02，02]的第一个键之后的trie。由于没有先前的条目，因此使用终端优化来存储第一个键。图14C示出了在添加键部分值为[00，03，00，01]的第二个键之后的trie。现有终端节点已拆分。由于匹配前缀(“00”)只有一个子节点，因此将其存储为链式节点，随后是具有两个子节点(“02”和“03”)的常规节点。第一个键(“02”)的其余部分作为具有叶节点部分的节点存储(利用终端优化存储其将需要更多空间)。第二个键(“00”和“01”)的其余部分再次使用终端优化进行存储。
为了测量根据本发明的各个实施例的数据结构的空间需求，进行了实验，其中存储了具有完整的长整数值范围的长整数的随机集合。图15示出了测量结果，其中，x轴以对数刻度指示加载到trie索引中的条目数，并且y轴指示平均存储一个条目所需要的字节数。
可以观察到，链式节点优化单独减少约40％的空间需求，并且终端优化单独减少约60-75％。与单独的终端优化相比而言，组合的链式节点和终端优化并未提供可见的空间改进(该图与终端优化情况重叠)。但是，发明人进行的经验测量表明，这两种优化仍然有值得一起应用。除了终端优化外还应用链式节点优化时，由于必须遵循较少的指针，因此性能提高，并且数据局部性更好，并且尊重存储器层次结构(CPU缓存)。
位图压缩
本发明的第三空间优化提供了在稀疏填充trie的存储器中trie的更紧凑表示。通过分组并有效地存储相同值的区部(例如，在稀疏填充的节点的情况下值为0的区部或在密集填充的节点的情况下值为1的区部)，可以减少位图(例如指示出子节点的键部分值的位图)的存储器空间。该第三空间优化在本文中被称为“位图压缩”。
本发明的第三空间优化应用于包括一个或多个节点的trie，其中节点、优选地具有超过一个子节点的至少每个父节点包括以逻辑位图形式的位图和多个指针，其中每个指针与逻辑位图中设置的位相关联，并指向该节点的子节点。如关于本发明的其他方面所提到的，逻辑位图可以对应于包括键部分值的位图。通过以下事实来实现优化：将逻辑位图划分为多个区部，并由头部位图和多个内容位图进行编码，其中，每个区部与头部位图中的位相关联，并且其中对于逻辑位图的每个区部，其中设置了一个或多个位，设置了与头部位图中的区部相关联的位，并将该区部存储为内容位图。
使用头部位图和多个内容位图来存储逻辑位图可以通过为没有设置位的逻辑位图的区部省略内容位图来显着减少所需的存储空间。换句话说，只有具有至少一个设置位的内容位图(即逻辑位图的区部)被存储在存储器中。在最坏的情况下，其中逻辑位图的每个区部至少具有一个设置位，由于需要存储另外的头部位图，因此存储器使用会略微增加。但是，节点通常是稀疏填充的，并且因此使用位图压缩时典型地需要较少的存储器。
在图16中示出了根据本发明的位图压缩的实施例，其在上部示出了trie 1601的区部，其父节点包括没有位图压缩的逻辑位图1602。在其下部中，示出了trie 1611的区部，其父节点是在已将位图压缩应用于trie 1601的父节点之后获得的。trie 1611的父节点包括头部位图1612和由位图压缩产生的两个内容位图1613、1614。
trie 1601、trie 1611中的父节点还包括指针1603至1605。在trie 1601中，每个指针与在逻辑位图1602中设置的位1606至1608相关联。在trie 1611中，指针1603至1605与在内容位图中设置的位1616至1618相关联。
通过将逻辑位图1602划分为区部1621(例如8位)、并存储将至少一个位设置为内容位图1613、1614的区部1622、1623，而将trie 1601中的逻辑位图转换为下部1611中的头部位图1612和内容位图1613、1614。没有设置位的区部不被存储为内容位图。头部位图1612中的每个位表示逻辑位图的不同区部。内容位图1613、1614由在头部位图1612中设置的相应位1619、1620引用。内容位图1613、1614可以以相同的顺序(未示出)或相反的顺序存储，其中与其区部相关联的设置位1619、1620被布置在头部位图1612中。换句话说，在逻辑位图的所有内容位图中的内容位图的等级可以对应于头部位图中的所有设置位中与内容位图的区部相关联的设置位的等级。以这种方式，在处理trie时可以容易地寻址内容位图。同样，逻辑位图的区部优选地在存储器中全部连贯。因此，整个逻辑位图可以由头部位图随后是多个内容位图而连贯地在存储器中表示。
在优选实施例中，所有区部都具有相同的大小。相同大小的区部允许对逻辑位图进行压缩和解压缩的有效处理，这是因为不需要关于区部的结构的进一步信息。同样，头部位图的大小可以与区部的大小相同。
可以使用用于存储头部位图和内容位图的不同结构。逻辑位图的头部位图和内容位图可以存储在数组中、列表中或连续的物理或虚拟存储器位置中。当头部位图和内容位图的大小为一个字节时，如图16中示出的，可以将该位图存储在字节数组中，而不是在长整数数组中，如在trie 1601中或图9和图12至图14的trie中进行的那样，这减少了对准损耗。内容位图优选地存储在存储器中相对于头部位图的预定义位置中。将内容位图和头部位图彼此靠近存储可以提高处理效率。在图16中，内容位图直接存储在存储器中的头部位图后面。
前面描述的位图压缩还可以应用于指针，如用于引用子节点的指针，并且还可以应用于内联叶节点位图。这将典型地进一步提高空间效率，但会损害性能，这是因为在计算特定指针的偏移时，可变大小编码使得有必要遍历指针。
位图压缩可以与本发明的其他方面组合。例如，组合指针减少，由(逻辑)位图标记而未设置设置位的根据本发明的终端分支节点可以被编码为仅头部位图而没有任何内容位图。
图17示出了上面参考图15所描述的实验结果。但是，除了链式节点和终端优化之外，还应用了位图压缩。如与图15的比较中可以观察出，当不应用链式节点或终端优化时，通过位图压缩实现的空间节省约40％，另外仅应用链式节点优化时，节省约50-70％，并且另外仅应用终端优化或者应用链式节点和终端优化时，节省约30-60％。
键编码
本发明提供了存储具有固定或可变大小的键(例如字符串)的键的不同原始数据类型的方式，以及包括trie中的原始数据类型的两个或更多个项的复合键。
包括控制信息的键
在本发明的优选实施例中，可以以一种灵活的方式对键进行编码，以使得即使在没有事先知道在键中存储的分量的数量、数据类型或长度的情况下，也可以例如通过游标进行迭代。
这些实施例应用于在数据库应用程序或信息检索系统中使用的trie，例如，根据如上面描述的trie和trie数据结构的实施例之一的trie或trie数据结构。trie包括一个或多个节点，其中节点、优选地每个子节点与键部分相关联，从trie中的根节点到另一个节点、特别是到叶节点的路径定义了与该节点相关联的键，其中该键是与路径上的节点相关联的键部分的级联。通过以下事实来实现上面提到的灵活性：除了内容信息之外，键还包括控制信息。
该键典型地将包括一个或多个键部(key part)，其中每个键部包括内容信息，该内容信息是由该键所包括的全部内容信息的一部分。对于键部中的每个，控制信息优选地包括数据类型信息元素，该数据类型信息元素指定由键部所包括的内容信息的数据类型。
原则上，有两种方式来布置与键部相关联的控制信息和内容信息。第一种方式在图18中示出，其中键部或者优选地每个键部10、20、30包括数据类型信息元素(图18中的阴影元素)和内容信息元素。数据类型信息元素指定内容信息元素的数据类型。这意味着控制信息和内容信息跨不同的键部10、20、30分布。在这种情况下，键的数据类型信息元素或每个数据类型信息元素典型地由与键中的数据类型信息元素相关联的内容信息元素定位，优选地(直接)在该数据类型信息元素之前。因此，数据类型信息元素类似于键部10、20、30的前缀或头部元素。
图19中示出了布置与键部相关联的控制信息和内容信息的第二种方式，其中数据类型信息元素(图19中的阴影元素)位于一起，并且优选地以与它们指定其数据类型的内容元素相同或相反的顺序布置。如数据类型信息元素的控制信息优选地位于键中的内容信息之前，作为键的前缀或头部元素。由发明人进行的研究表明，存储数据类型信息元素的第二种方法是可取的，这是因为具有相同数据类型的键具有相同的前缀(trie中的起始节点)，并且因此减少了trie中所需节点的数量，从而导致节省空间。
与键部相关联的内容信息的数据类型可以具有固定大小，诸如在整数、长整数或双精度浮点或时间/日期原语的情况下，或者其可以具有可变大小，诸如在字符串的情况下，例如Unicode字符串或可变精度整数。在本发明的一些实施例中，键包括两个或更多个键部，其包括不同(原始)数据类型的内容信息。
如将在下面参考图20和图21所解释的，控制信息可以包括(例如由数据类型信息元素的高位状态)标识最后的键部的信息。可替选地，键部计数可以分别存储。此外，控制信息可以包括关于trie是用于存储动态集合还是关联数组的信息。
键部的内容信息可以由一个单个键部分包含，但是典型地它由两个或更多个键部分包含。对于固定大小的键部，典型地已知包含由键部所包括的内容信息所需的键部分的数量。在由键部包括的内容信息的数据类型是可变大小的数据类型的情况下，内容信息元素的末端可以由特定的符号标记，例如以空结尾的字符串，字符串的最后一个字符为空字符('\0'，在ASCII中称为NUL)。可替选地并且优选地，它可以由包含键部的键部分之一的特定一个中的特定位来标记，如将在下面参考图21的Unicode字符串进行解释的那样。
尽管如上面提到的，键部的内容信息通常将由两个或更多个键部分所包含，但是键部分优选地不包含两个或更多个键部的内容信息。换句话说，键部的内容信息与键部分的边界对准。类似地，键部分优选地不包含两个或更多个控制信息元素的信息，如数据类型信息元素、键部计数或关于trie是否用于存储动态集合或关联数组的信息。这种方法使实施方式更容易且更有效，通常没有重大的对准损失。此外，如下面将解释的，它允许以交错的方式存储不同键部的内容信息。
在图20中示出了根据本发明的键编码的示例。要存储在trie中的键包括控制信息2010和内容信息2020。键包括数个包含内容信息的键部，并且对于键部中的每个，控制信息2010包括指定由键部所包括的内容信息的数据类型的数据类型信息元素2012、2013。此外，控制信息2010包括关于trie是用于存储动态集合还是关联数组的信息2011。如果使用trie来存储相关联的数组，则与键相关联的trie的叶节点典型地将包括叶节点值2030或指向该叶节点值的指针。
如上面提到的，在本发明的优选实施例中，trie中的每个父节点包括64位宽的位图，并且因此trie中的每个键部分都能够存储6位的值。关于trie是用于存储动态集合还是关联数组的信息2011由第一键部分存储，并且因此6位用于该信息。实际上，对于该是/否信息，1位就足够了，但是出于上面提到的对准的原因，使用了能够存储6位值的整个键部分。该信息在节点2041中编码，包括64位宽的位图(其中设置了相应的位)和指向节点2041的相应子节点的指针(idx)。
数据类型信息元素2012、2013中的每个还由一个键部分存储，其值在节点2042、2043的位图中被编码。5位用于数据类型信息，其允许32个不同的类型标识符。可以由相应键部分存储的第6位(例如键部分的高位)用于指示与数据类型信息元素相关联的键部分是否为键中的最后一个键部。在图20的示例中，数据类型信息元素2013的高位被设置为指示与数据类型信息元素2013相关联的键部是键中的最后一个键部。
键部中的每个所包括的内容信息也被分解为通常6位的值2021、2022，并且值中的每个被一个键部分存储。由于空间原因，未在图20中示出其位图用于编码(6位)值2021、2022的节点。例如，在键部包括32位整数值的情况下，此32位值由六个键部分存储，第一个键部分存储2位值，并且最后五个键部分每个存储6位值(32＝2+6+6+6+6+6)。
图21示出了存储根据本发明编码的键的trie。trie的每个父节点包括64位宽的位图。键包括第一键部和第二键部，第一键部包括值为“100”的32位整数，并且第二键部包括值为“ab”的字符串。键的控制信息包括(1)动态集合标识符、(2)整数标识符和(3)具有最后一种类型的标记的字符串类型标识符。键的内容信息包括(1)32位整数值“100”和(2)以Unicode编码的字符串值“ab”。
动态集合标识符是值为0(0x00)的6位数字。因此，图21的trie的根节点2100的位图具有设置了值“0”的位，并且与该位相关联的第二级节点与值“0”的键部分相关联。整数标识符是值为5(0x05)的6位数字。因此，第二级节点的位图具有设置了值“5”的位，并且与该位相关联的第三级节点与值为“5”的键部分相关联。最后一个键部的具有标记的字符串类型标识符是值为39(0x27)的6位数字。因此，第三级的位图具有设置了值“39”的位，并且与该位相关联的第四级节点与值“39”的键部分相关联。
整数值“100”以32位二进制编码为“00 000000 000000 000000 000001100100”。因此，与用于存储整数值“100”的级别5到10上的节点相关联的键部分分别与值0(0x00)、0(0x00)、0(0x00)、0(0x00)、1(0x01)和36(0x24)相关联。
字符串值“ab”被编码为字符“a”的Unicode值，随后是字符“b”的Unicode值。每个Unicode字符使用2-4个键部分存储，这取决于Unicode值，其可能需要10、15或21位。在本发明的优选实施例中使用的用于Unicode字符的编码方案如下：
10位Unicode字符：00xxxx xxxxxx
15位Unicode字符：010xxx xxxxxx xxxxxx
21位Unicode字符：011xxx xxxxxx xxxxxx xxxxxx
通过设置高位来标记字符串中的最后一个字符，这将导致最后一个字符的以下编码方案：
10位Unicode字符：10xxxx xxxxxx
15位Unicode字符：110xxx xxxxxx xxxxxx
21位Unicode字符：111xxx xxxxxx xxxxxx xxxxxx
Unicode字符“a”的值为97(0x61)，并以10位的Unicode编码为“0001 100001”。根据优选实施例中使用的编码方案，Unicode字符“a”被编码为“000001 100001”。Unicode字符“b”的值为98(0x62)，并以10位的Unicode编码为“0001 100010”。根据优选实施例中使用的编码方案，Unicode字符“b”被编码为“100001100010”，其设置高位，这是因为“b”是字符串中值为“ab”的最后一个字符。因此，与用于存储字符串值“ab”的级别11至14上的节点相关联的键部分分别与值1(0x01)、33(0x21)、33(0x21)和34(0x22)相关联。
交错的多项键
本发明的实施例提供了一种存储trie中的数据的方式，使得可以以更有效的方式执行涉及超过一个数据项的查询。本发明的方法对于以下特别有用：将键或者键和值存储在数据库或信息检索系统中使得可以更有效地查询它们、存储数据库或信息检索系统查询的结果键或者键和值、或者存储用于数据库查询的输入键或键和值使得可以更有效地执行查询。
本发明的存储数据的方式使用trie，诸如具有上面描述的数据结构的trie，该trie包括节点，其中节点、优选地每个子节点与键部分相关联，并且其中从trie中的根节点到另一个节点的路径定义了与该节点相关联的键，其中该键是与路径上的节点相关联的键部分的级联。为了在涉及多个数据项的查询中实现性能提升，将两个或更多个数据项编码在键中，并且至少一个或两个、优选地数据项中的每个由两个或更多个分量组成。键包含两个或更多个连续的区部，区部中的至少一个或两个、优选地区部中的每个包括在键中编码的数据项中的两个或更多个的分量。“项”在本文中有时被称为“维度”，并且它可以对应于上面所谓的“键部”或“键部的内容信息”。
图22示出了值为(X＝12，Y＝45)的二维键的示例，即对两个数据项X和Y进行编码的键。这两个数据项均由两个分量组成，即在项X的情况下为“1”和“2”，并且在项Y的情况下为“4”和“5”。键包括两个连续的区部S1和S2。两个区部都包括在键中编码的数据项x和y中的每个的一个分量：区部S1包括数据项X的第一分量“1”和数据项y的第一分量“4”；区部S2包括数据项X的第二分量“2”和数据项Y的第二分量“5”。可以说在优选实施例中，键以交错的方式对多个数据项进行编码，诸如X
根据优选实施例，键的编码使得键的区部、优选地区部中的每个包含来自键中编码的数据项中的每个的至少和/或至多一个分量。例如，图22中示出的键的区部S1和S2都包含在键中编码的数据项X＝12和Y＝45中的每个的恰好一个分量。
此外，对于键的两个或更多个区部、优选地所有区部，属于不同数据项的分量在该区部内以相同顺序排序。例如，在图22示出的键的两个区部中，分量以这样的序列排列：数据项X的分量排在第一位，并且数据项Y的分量排在第二位。
此外，包括数据项的分量的区部的顺序优选地对应于数据项内的分量的顺序。例如，在图22中示出的键中，区部S1位于区部S2之前，这对应于它们所包括的分量的顺序，在它们相应的项中：S1包括项X的分量“1”，其在项X中位于由区部S2所包括的分量“2”之前。S1还包括项Y的分量“4”，其在项Y中位于由区部S2所包括的分量“5”之前。
键的两个或更多个数据项、优选地所有数据项具有相同数量的分量。例如，在图22中示出的键中编码的项X和Y都具有两个分量。但是，键的数据项也可以具有不同数量的分量。例如，可能是这种情况，其中一个项是64位整数，并且另一项是32位整数。在键以严格规则的交错方式对数据项进行编码的情况下，诸如X
图23给出了如何将图22中示出的键存储在trie中的示例。在优选实施例中，与子节点、优选地与子节点中的每个相关联的键部分对应于数据项的一个分量。换句话说，数据项、优选地每个数据项的分量、优选地每个分量对应于与trie的一个子节点相关联的键部分。在图23的示例中，第二级节点2302与对应于项X的第一分量的键部分1相关联，第三级节点2303与对应于项Y的第一分量的键部分4相关联，第四级节点2304与对应于项X的第二分量的键部分2相关联，并且第五级节点2305与对应于项Y的第二分量的键部分5相关联。尽管这不是优选的，但与子节点相关联的键部分还可以仅对应于数据项的分量的一部分，或者对应于数据项的超过一个分量。
在图22和23的示例中，数据项X和Y是2数位十进制数字，并且分量是十进制数位。根据本发明，由trie存储在键中编码的数据项的其他示例是地理位置数据，诸如经度或纬度、索引，任何种类的数字或数据类型，诸如整数、长整数或双长整数、32-位整数或64位整数、字符串、字节数组或这些中的两个或更多个的组合。
在数据项是数目的情况下，数据项的分量可以是数位(类似于图22和图23的示例中)。在数据项是字符串的情况下，数据项的分量可以是单个字符。在数据项是字节数组的情况下，数据项的分量可以是单个字节。
然而，在优选实施例中，数据项的分量是数据项的二进制编码的位组，该位组优选地包括6位。这是因为如上面解释的，在优选实施例中，子节点的键部分的值由父节点所包括的位图中(设置)的位的值确定，取决于所述子节点与哪个位相关联。因此，位图的大小定义了键部分的可能字母表。例如，在每个位图的大小为64位的情况下，可用于节点的键部分的不同值的数量为2
例如，在数据项是64位长整数、并且每个分量是整数的二进制编码的6位组的情况下，该数据项具有64/6＝11个分量。在数据项是以Unicode编码的字符的情况下，它可能具有2至4个6位分量，如上面解释的。在数据项是由几个字符组成的字符串的情况下，优选实施例中的分量仍然是6位组，即，类似于任何其他数据项，字符串具有相同类型的分量(6位组)。字符串的数字分量对应于单个字符的分量数乘以字符串中的字符数。
代替将优选实施例的分量视为位组，例如6位组，它们也可以被视为具有预定义基数或基的数位，例如64。
如从下面参考图45和图46以及图61至图65的范围查询的描述将变得显而易见的是，存储具有多个数据项的键的交错方式可以大大提高涉及多个数据项的范围查询的性能。此外，技术人员将理解，交错存储可以提高双向搜索以及涉及“NOT”运算符的搜索的性能，该“NOT”运算符涉及多个数据项。
集合运算
本发明的实施例提供了一种在数据库或信息检索系统中执行查询的省时方法，包括对存储在数据库或信息检索系统中的键的两个或更多个集合、或数据库或信息检索系统查询的结果键集进行的诸如交集(布尔AND)、并集(布尔OR)、差集(布尔AND NOT)和异或(布尔XOR)的运算。这些运算在此称为“集合运算”或“逻辑运算”。
仍然大多数数据库使用Volcano处理模型，这意味着“一次一个元组”。但是，对于考虑了多级缓存和存储器数据库的现代CPU体系结构来说，这效率不高。由于物理执行计划中的所有运算符紧密地交错运行，因此运算符的组合指令占用空间可能太大而无法装入指令高速缓存中，并且运算符的组合状态可能太大而无法装入数据高速缓存中。因此，某些数据库应用一次运算符模型或两者的组合、矢量化的执行模型。根据本发明的索引数据结构和统一的逐级处理模型导致关于访问索引trie和运算符实施方式的非常精简的指令占用空间(footprint)。
图24示出了根据现有技术的数据库查询处理的各个阶段的说明性流程图。查询被解析2401、重写2402和优化2403，并且查询执行计划QEP被准备和细化2404，使得查询执行引擎(QEE 2405)可以在数据库2406上执行由前面的步骤生成的QEP。
图25示出了在现有技术数据库中使用的示例性QEP。QEP由树表示，其中父节点2501、2502是运算符，并且叶节点2503、2504是数据源。在第一操作中，来自表格扫描2504的结果由排序运算符2502排序。在第二操作中，将排序结果与索引扫描2503的结果合并连接。
图26示出了现有技术数据库的基于迭代器的执行模型中的运算符控制和数据流，其中运算符实施以下方法：Open(准备运算符以产生数据)、Next(根据运算符的消费者的需求产生新的数据单元)、以及Close(完成执行并释放资源)。每次调用Next方法都会产生新的元组。
基于迭代器的执行模型为运算符提供了统一的模型，其独立于数据源(数据库表或数据库索引)的数据模型，并且统一了运算符节点的临时结果。但是，每次运算符调用仅递送一个数据单位，例如记录。这种方法对于组合大型子结果集的运算符效率不高，子结果集本身返回的是较小的结果集。
元组可以传递给其他运算符，如图27中示出的，其示出了根据现有技术数据库的查询执行模型的一次元组处理。从根运算符2701开始，对next()的调用将传播到其运算符子节点2702、2703，依此类推，直到到达数据源(和树表示的叶节点)为止。以这种方式，在查询执行计划运算符树中，控制从消费者向下流到生产者，并且数据从生产者向上流到消费者。
一次元组处理模型具有较小的中间结果，并且因此存储器需求较低。执行计划中的运算符紧密地交错运行，并且可能非常复杂。但是，大量的函数调用以及所有运算符的组合状态会导致大量的函数调用开销以及指令和数据高速缓存未命中，这是因为它们的占用空间通常太大而无法装入CPU高速缓存中。
基于迭代器的执行模型和一次元组处理模型都需要复杂的查询优化器变得高效。
图28示出了根据现有技术数据库的查询执行模型的一次运算符处理，其在合适的数据结构(如列表)中作为运算符的结果立即返回所有元组。一次运算符方法是高速缓存高效的，并具有紧密的循环且函数调用开销较低，但每个运算符会产生较大的中间结果，这些中间结果可能不装入数据高速缓存中，或者甚至可能不装入主存储器中，这可能导致此方法无用。
本发明通过其中所有数据源以及优选地所有运算符是trie的新颖执行模型解决了现有技术的问题。根据相应的逻辑运算(集合运算)组合两个或更多个输入trie，以获得与相应的结果trie的节点相关联的键集。
然后，数据库查询提供结果trie的表示、与结果trie的节点相关联的键集、或与结果trie的节点相关联的键的子集、特别是与结果trie的叶节点相关联的键、或从与结果trie的节点相关联的键导出的键集或值集合作为输出。可替选地，它可以提供与结果trie的节点相关联的其他数据项，如文档标识符。可以在trie中例如在物理trie数据结构中提供作为输出提供的键集。应当注意，本文使用“结果trie”的概念来定义在使用逻辑运算组合输入trie时需要获得的键集。但是，在输入trie的组合期间，不一定必须在物理trie数据结构中形成结果trie，并且键的输出集也可以例如由游标或迭代器提供。
一般而言，使用逻辑运算将两个或更多个输入trie的组合导致了以下(结果)trie，其存储了当使用逻辑运算组合由相应输入trie存储的相应键集时所获得的键集。特别地，如果逻辑运算是求差集(AND NOT)，则结果trie中的父节点是第一个输入trie中的父节点，并且结果trie中的父节点的叶节点是第一个输入trie中对应父节点的子节点集以及其他输入trie中对应父节点的子节点集的AND NOT组合，如果有的话。如果逻辑运算不是求差集，例如如果逻辑运算是求交集(AND)、并集(OR)或异或(XOR)，则结果trie中每个节点的子节点集是使用输入trie中对应节点的子节点集的逻辑运算(例如AND、OR或XOR)的组合。在这种情况下，由于每个子节点都与键部分相关联，并且从trie中的根节点到另一个节点的路径定义了与该节点相关联的键，该键是与路径上的节点相关联的键部分的级联，如果与不同trie的节点相关联的键相同，则不同trie的两个或更多个节点彼此“对应”。
在优选的实施方式中，对于其消耗者来说，每个运算符本身再次作为trie出现(包括消耗者是使用逻辑运算的另一运算符的情况)直到查询执行计划树中的根运算符节点为止，例如通过实施相应的trie(节点)接口。这样的trie节点接口代表trie节点，并提供查询或遍历它所代表的trie节点的子节点的方法或功能，并且trie的表示代表trie的根节点。因此，代替使用迭代器接口，可以使用节点接口。这允许功能组合以及更简单且更简洁的软件体系结构，并且其进一步提高了数据库引擎的性能，这是因为较低的实施方式复杂性直接导致更少的函数调用开销以及更少的数据和指令高速缓存未命中。
优选地，用于实施trie的数据结构如上面描述的。特别地，如果输入trie中的节点、优选地输入trie中的至少所有父节点都包括位图，并且trie中的子节点的键部分的值由父节点所包括的位图中的位(集合)的值确定(取决于所述子节点与哪个位相关联)，则这是有利的。通常，通过使用逻辑运算组合与结果trie的节点相对应的输入trie的节点的子节点集，而确定结果trie的节点的子节点集。在这样的实施方式中，可以通过使用逻辑运算(诸如按位AND、按位OR、按位AND NOT或按位XOR)来按位组合输入trie的对应节点的每个节点的位图而容易地执行输入trie的对应节点的子节点集的组合。获得组合位图，并且在组合位图的基础上执行组合的结果。换句话说，基于组合位图优选地仅基于组合位图来确定(评估)结果trie的节点的子节点。结果，在确定结果trie的节点的子节点之前，并且在对结果trie的评估遍历到结果trie的节点的子节点之前，执行组合该位图的步骤。
因此，trie的实施方式中的物理代数直接对应于集合运算的逻辑代数。而在现有技术中，位图仅在trie中用于减少指针所需的存储器空间，本发明利用位图来对trie执行集合运算。
如上面提到的，名为“CDBINode”的trie节点接口的示例性实施方式具有以下主要方法：getBitSet()–返回位图，其具有为trie节点的所有非空子指针设置的位；以及getChildNode(bitNum)–返回由位数指定的给定节点分支的子节点。
图29示出了根据本发明的查询执行模型的trie控制和数据流。运算符2903对两个输入基本数据集合2901、2902执行集合运算，例如，交集、并集、差集或异或。基本数据的两个集合每个在输入trie中提供，其例如在物理trie数据结构中存储，并且两个输入trie由运算符2901根据相应集合运算而组合。通过实施与输入trie相同的trie(节点)接口，对于其使用者来说，运算符2903本身作为trie出现。执行器2904调用上面提到的trie节点方法getBitSet和getChildNode，以遍历由运算符2903提供的结果，如由执行器和运算符之间的虚线箭头指示出的。当执行集合运算时，运算符2903调用相同的方法getBitSet和getChildNode遍历输入trie 2901、2902，如由运算符和输入trie之间的虚线箭头指示出的。在由实线箭头指示出的数据流方向上，将位图和子trie节点从输入trie 2901、2902传递给运算符2903，并从运算符2903传递给执行器2904。
如将理解的，通过使用相同或不同逻辑运算符，用于高阶集合运算的输入trie中的一个或多个可以是对trie的另一个(低阶)集合运算的输出。如上所述，可以将对trie的低阶集合运算的这种输出提供作为物理trie数据结构。然而，在优选实施例中，将用于高阶集合运算的输入trie(其是低阶集合运算的输出)提供作为虚拟trie。虚拟trie可以被理解为能够评估要在高阶运算中使用的trie的低阶运算符。在这种情况下，在当高阶运算符接收到其输入trie的表示并且至少一个输入trie作为低阶运算符的输出被提供时的时刻，该输入trie的物理数据结构作为整体不存在，并且实际上可能根本无法实现。
在图29A中示出了这种情况，其中高阶运算符2906对例如以物理Trie数据结构提供的输入基本数据集2905以及低阶运算符2903的输出执行高阶集合运算。高阶运算符2905评估高阶结果trie的至少部分，它是使用高阶集合运算的、输入基本数据2905和低阶运算符2903的输出的组合。低阶运算符2903至少部分评估低阶结果trie，该低阶结果trie是使用低阶集合运算的例如以物理trie数据结构提供的两个输入基本数据2901、2902集合的组合。低阶集合运算可以是与高阶集合运算相同的集合运算，也可以是不同的集合运算。如本文中所使用的，表述“trie的部分”可指代trie的节点和/或分支。
仅在评估高阶结果trie的至少部分的步骤中计算低阶结果trie的至少部分。根据高阶运算符的要求评估低阶结果trie的部分，因此以交错方式评估高阶结果trie的部分和低阶输入结果trie的部分。因此，仅在计算出高阶结果trie的至少部分之后，才计算低阶结果trie的至少部分。
可以理解，当高阶运算符2905评估高阶结果trie时，可能不需要访问低阶结果trie的所有部分。因此，不评估低阶结果trie的部分的至少一些(最好是全部)，其不是评估高阶结果trie所需的。但是，显然需要评估低阶结果trie的至少那些部分，其是评估高阶结果trie所需的。
图30示出了对两个输入trie 3001、3002应用交集(布尔AND)运算符3003的示例。为了可读性，输入trie是8进制的，但是在优选的实施方式中，使用了如上面描述的trie数据结构。输入trie 3001包括与键“13”、“14”和“55”相关联的三个叶节点。输入trie 3002还包括与键“13”、“15”和“64”相关联的三个叶节点。trie 3005描绘了输入trie 3001、3002的AND组合获得的结果trie。
如可以观察到的，结果trie中每个节点的子节点集是输入trie中对应节点的子节点集的AND组合。例如，结果trie 3005的根节点具有与键“1”相关联的一个子节点。当形成输入trie 3001的根节点的子节点集(“1”、“5”)和输入trie3002的根节点的子节点集(“1”、“6”)的交集时，获得该一个子节点。此外，与键“1”相关联的节点还具有一个与键“13”相关联的子节点。实际上，当形成输入trie 3001的节点“1”的子节点集(“13”、“14”)与输入trie3002的对应节点“1”的子节点集(“13”、“15”)的交集时，获得节点“13”。
因此，交集操作的结果trie(这里是结果trie 3005)包括所有节点，并且仅包括由输入trie(这里是输入trie 3001、3002)中的每个所包括的节点。特别地，结果trie的叶节点集(这里是与键“13”相关联的节点)包括所有叶节点，并且仅包括由每个输入trie和所有输入trie所包括的叶节点。
由交集运算符3003的优选实施例执行的算法可以用伪代码描述如下：
在该优选实施例中，所有trie节点都包括如上面描述的位图。此外，trie由节点实施包括如上面描述的getBitSet和getChildNode方法的接口而形成。在两个输入trie的对应节点的位图之间执行按位AND操作，以确定两个对应节点共有的子节点集。
如以下参考图31至图34将示出的，本发明的解决方案利用了分层trie结构。由于trie是逐级处理的，因此它允许进行惰性计算。因此，可以显着改善集合运算的性能。
图31示出了两个示例输入trie 3110、3120，将在其上执行交集操作。类似于所有trie，输入trie 3110和3120在级别1上具有一个(根)节点。输入trie 3110在级别2上具有两个节点，如由以下事实指示出的，在由输入trie 3110的根节点所包括的位图3111中设置了第四位和第七位。输入trie 3120在级别2上具有一个节点，由在输入trie 3120的根节点所包括的位图3121中设置的第七位指示出。两个输入trie在级别3或更深的级别上有更进一步的子trie，如取决于在级别2的节点的相应位图中设置的位的三角形指示出的。
图32示出了在级别1和级别2上对输入trie 3110和3120的对应节点的位图执行的按位AND操作。输入trie的级别1上的根节点始终彼此对应，并且因此它们的位图与第一个按位AND操作组合。由于在输入节点3110的根节点的位图3111中设置了第四位和第七位，并且(仅)在输入节点3120的根节点的位图3121中设置了第七位，(仅)在组合的位图3201中设置第七位。在级别2上，取决于输入trie 3110的根节点的位图3111的第七位的节点对应于取决于输入trie 3120的根节点的位图3121的第七位的节点，而取决于输入trie 3110的根节点的位图3111的第二位的节点在输入trie 3120中没有对应的节点。因此，(仅)在级别2上利用按位AND操作组合位图3113和3122，并且在组合的位图3202中设置第三位和第六位。
图33示出了在输入trie 3110和3120的交集操作期间的分支跳过。由于对两个输入trie的根节点的位图3111和3121进行按位AND操作会产生其中仅设置了第七位的组合的位图3201，因此取决于输入trie 3110根节点的位图3111的第四位，交集操作不需要遍历输入trie 3110的分支。这在图33中由位图3111的第四位置中的“X”以及用于绘制跳过的分支的虚线指示出。同样，在级别2上，第七位仅在输入trie 3110中的节点的位图3113中设置，而不在输入trie 3120中的对应节点的位图3122中设置。因此，取决于位图3113的第七位，交集操作不需要遍历该分支。
最后，图34示出了trie 3110和3120上交集操作的结果trie。与级别1和级别2上的结果trie的节点相关联的位图3201和3202分别对应于由图32中示出的按位AND操作所计算出的组合的位图。
图31至图34的示例表明，大致上，在组合输入trie的集合运算的过程中，无需遍历输入trie的某些分支，这可以显着提高性能。组合的位图可用于确定需要进一步遍历哪些分支以及可以跳过哪些分支。这种方法可以称为“结果预测”或“树修剪”。
图35示出了对图30的两个输入trie 3001、3002应用并集(布尔OR)运算符3503的示例。通过输入trie 3001、3002的OR组合获得的结果trie 3605的说明在图36中示出。
如可以观察到的，结果trie中每个节点的子节点集是输入trie中对应节点的子节点集的OR组合。例如，结果trie 3605的根节点具有三个子节点，它们与键“1”、“5”和“6”相关联。当形成输入trie 3001的根节点的子节点集(“1”、“5”)和输入trie 3002的根节点的子节点集(“1”、“6”)的并集时，获得这三个子节点。与键“1”相关联的节点还具有三个子节点，其与键“13”、“14”和“15”相关联。实际上，这些节点是在形成输入trie 3001的节点“1”的子节点集(“13”、“14”)和输入trie 3002的对应节点“1”的子节点集(“13”、“15”)的并集时获得的。最后，结果trie中分别与键“5”和“6”相关联的节点每个具有分别与键“55”和“64”相关联的一个子节点，其分别是输入trie 3001和3002的对应节点的子节点。
因此，并集操作的结果trie(这里是结果trie 3605)包括任何输入trie所包括的所有节点，这里是输入trie 3001、3002。特别地，结果trie的叶节点集(这里是与“13”、“14”、“15”、“55”和“64”相关联的节点)包括由任何输入trie所包括的所有叶节点。
由并集运算符3503的优选实施例执行的算法可以用伪代码描述如下：
同样，所有trie节点都包括如上面描述的位图，并且trie由实施包括如上面描述的getBitSet和getChildNode方法的接口的节点形成。在两个输入trie的对应节点的位图之间执行按位OR操作，以确定两个对应节点中的任何一个所包括的子节点集。如果仅在两个对应节点之一的位图中设置了位，则将取决于该一个节点的子trie添加到结果trie，其在上面的伪代码中由“仅递归trieA”/“仅递归trieB”指示出。
图37示出了对图30的两个输入trie 3001、3002应用差集(布尔AND NOT)运算符3703的示例。trie 3705是由输入trie 3001、3002的AND NOT组合获得的结果trie的说明。
如可以观察到的，结果trie 3705的所有父节点对应于第一输入trie 3001的父节点。取决于结果trie 3705的父节点的叶节点是第一输入trie 3001中的对应父节点的子节点集以及输入trie 3002中任何对应父节点的子节点集的AND NOT组合。
例如，结果trie 3705的根节点具有与键“1”和“5”相关联的两个子节点，其本身是父节点。这两个节点对应于输入trie 3002的根节点的两个子节点，其本身是父节点。与键“1”相关联的节点具有一个子节点，其是叶节点并与键“14”关联。当形成第一输入trie3001的节点“1”的子节点集(“13”、“14”)与输入trie 3002的对应节点“1”的子节点集(“13”、“15”)的差集时，获得该叶节点。最后，在与键“5”相关联的结果trie中的节点具有一个子节点，其与键“55”相关联并且对应于具有第一输入trie 3001的键“5”的节点的子节点。具有键“5”的此节点在输入trie 3002中没有对应的节点。
因此，差集操作的结果trie(这里是结果trie 3605)包括由第一输入trie(这里是输入trie 3001)所包括的所有父节点。结果trie的叶节点集(这里是与键“14”和“55”相关联的节点)包括第一输入trie(这里是trie 3001)的所有叶节点减去第二输入trie(这里是trie 3002)的叶节点。
由差集运算符3703的优选实施例执行的算法可以用伪代码描述如下：
同样，所有trie节点都形成并实施了如上面描述的接口。如果在输入trie 3001和3002的对应节点的位图中都设置了位，则在两个trie上都存在递归。如果仅在第一输入trie 3001的节点的位图中设置了位，则将取决于该节点的子trie添加到结果trie，其在上面的伪代码中由“仅递归trieA”指示出。仅在trie 3002的节点的位图中设置的位被忽略。如果两个输入trie的对应节点的子节点是叶节点，则仅在两个输入trie的对应节点的位图之间执行按位AND NOT操作。
运算符的执行包括在trie级别上的递归下降(在优选实施方式中，每个级别都是基数/基64的一个数位)。在每个级别处，每个节点的位图都用作结果预测，随后通过预测位进行迭代。因此，评估结果trie包括对结果trie的根节点执行组合函数。为结果trie的输入节点执行组合函数包括：通过组合对应于结果trie的输入节点的输入trie的节点的子节点集来确定结果trie的输入节点的子节点集(其也可以为空)；使用逻辑运算；并且针对结果trie的输入节点确定出的子节点中的每个执行组合函数。如上面已经提到的，结果trie的根节点和/或输入节点不必物理生成。
可以使用深度优先遍历、广度优先遍历或其组合来执行评估结果trie的步骤。在深度优先遍历中评估结果trie包括：对输入节点的子节点之一执行组合函数，并在对该子节点的下一个兄弟节点执行组合函数之前遍历由该子节点形成的子trie。在广度优先遍历中评估结果trie包括：对针对结果trie的输入节点确定出的子节点中的每个执行组合函数；并且在对结果trie的输入节点的任何孙子节点执行组合函数之前针对结果trie的输入节点确定出的子节点中的每个确定子节点集。
用于集合运算的输入trie中的一个或多个可以是虚拟trie，即在组合输入trie的运算期间根据需要动态生成的trie。典型地，仅动态生成虚拟trie的那些部分，其是使用逻辑运算组合输入trie所需的。针对虚拟输入trie的应用程序存在几种情况，其中一种是数据库范围查询的实施方式，稍后将对此进行描述。另一种情况是，针对高阶集合运算的一个或多个输入trie是对trie的低阶集合运算的输出，这参考图29A在上面进行了描述。
虚拟trie是这样的trie：当例如作为集合运算符的输入trie接收到虚拟trie时，其物理数据结构作为整体不存在。虚拟trie可理解为能够评估trie的运算符。优选地，运算符代表trie的根节点并实现trie节点接口，其中trie节点接口代表trie节点，并提供查询或遍历它所代表的trie节点的子节点的方法或功能。
“评估”trie或trie的部分也可以称为“呈现”或“合成”该trie或trie的部分，并通常包括遍历该trie或trie的部分，并提供以下信息：所遍历的节点存在于trie中。它可以包括实现作为整体的trie或trie的部分的物理数据结构。然而，在优选实施例中，在任何给定的时刻，实现少于trie或trie的部分的整个物理数据结构，并且优选地，仅实现trie或trie的部分的物理数据结构的那些部分，其需要在那个时刻被实现用于遍历trie或trie的部分。显然，在评估trie或trie的部分期间的任何给定时刻，实现trie或trie的部分的物理数据结构的至少那些部分，其需要在那个时刻被实现用于遍历trie或trie的部分。
在优选实施例中，在虚拟trie实施trie(节点)接口的情况下，如上所述，使用方法getBitSet和getChildNode来评估trie或其部分。例如，在输入trie之一是虚拟trie情况下的高阶相交运算期间，高阶相交运算符访问并且虚拟范围trie通过应用程序编程接口(API)“实时(on the fly)”递送为评估高阶结果trie所需的虚拟trie的分量。例如，虚拟trie的当前节点的位图可以通过上面介绍的getBitSet()方法访问，而子节点可以通过上述getChildNode()方法访问。API一方面返回相应的位图，另一方面返回对象(而不是真实trie的子节点)，该对象将为下一次递归提供相应的位图。对于高阶运算符，虚拟trie看起来就像在物理trie数据结构中实施的trie。
通常，将虚拟trie的表示提供给运算符，该运算符使用虚拟trie作为某些运算的输入。在执行运算的步骤期间，(按需)评估虚拟trie的至少部分。在并非需要访问虚拟trie的所有部分以执行运算的情况下，不评估部分的至少一些，其不是执行该运算所需的，并且优选地，仅评估虚拟trie的那些部分，其是执行运算所需的。这对于图29A所示的情况在图37A和图37B中进行了说明，其中虚拟trie是低阶集合运算符2903，并且将该虚拟trie的表示作为输入trie提供给高阶集合运算符2906，其使用虚拟trie来评估高阶结果trie的至少部分。高阶结果trie是使用逻辑运算的、集合运算符2906的输入trie(即虚拟trie)与基本数据2905的组合。在图37A和图37B的情况下，高阶集合运算是AND运算，低阶集合运算是OR运算。
图37A示出了三个trieA，B和C。在优选实施例中，如上所述，trie是32进制，64进制。因此，引用指向子节点的指针的位图可以包括32或64位。为简单起见，该示例显示了四进制trie。trie由用于trie A的tire根节点3701，用于trieB的3702和用于trie C的3703表示。每个trie节点包括如上所述的位图3704、3705、3706。
图37B示出了如何进行((A或B)和C)评估而没有实现或具体化(A或B)作为中间结果即创建物理trie数据结构。该图示出了两个级别的表达式及其评估。对于第一级，通过逐位OR运算将trieA(3704)和trieB(3705)的根节点的位图组合，得到位图3709。通过与trie3706的根节点的位图3706进行按位AND运算来组合位图3709。由于与Trie C不匹配，所得位图3710出于进一步考虑而修剪TrieB。所得的物理Trie数据结构用根节点3712表示。对于第二级，trie A和trie C的位图3707和3708组合在一起–trie B在这里没有匹配-导致了位图3711。
从图37A和37B的示例可以看出，将低阶OR运算的结果作为虚拟输入trie提供给高阶AND运算符而不是作为全面评估的物理trie数据结构，这一事实使得进行“惰性计算”。在评估高阶AND运算的高阶结果trie期间，会评估低阶OR运算的低阶结果trie。因此，在评估了高阶结果trie的至少部分之后，评估低阶结果trie的至少部分。实际上，以交错方式评估高阶结果trie的部分和低阶结果trie的部分，其中，根据高阶运算符的要求评估低阶结果trie的部分。这仅允许评估低阶结果trie中的那些部分，其是评估高阶结果trie所必需的。
注意，对于某些运算，不需要实际实现物理结果trie数据结构，例如如果仅需要结果的计数(基数)的话。如本领域技术人员还将理解的那样，高阶运算符可以评估高阶结果trie的仅部分，例如如果将高阶结果trie用作甚至更高阶运算符的输入的话。类似地，用于低阶运算符的输入trie不必必须是物理trie数据结构，而可以再次是虚拟trie，例如是甚至更低阶运算符的输出。最后，请注意，运算符通常获得输入trie的表示，其中trie的表示可以是物理trie数据结构的句柄，如同指针。在虚拟trie的情况下，表示可以是能够评估trie的trie运算符的句柄。
范围查询
通过交集操作(布尔AND)的两个或更多个输入trie的组合可以有利地用于以有效方式执行范围查询。“范围”可以描述为离散的有序值的集合，其包括某种数据类型的第一值和第二值之间的所有值，其中第一值和/或第二值可以包括或可以不包括在该范围内。范围查询返回键集中的键，这些键的值对应于(匹配)一个或多个指定的值范围。
根据本发明的范围查询通过trie的交集操作来执行，该trie存储了要搜索一个或多个范围的键集(以下称为“输入集trie”)，其中trie存储包括在一个或多个范围内(以下称为“范围trie”)的所有值。trie优选地如上面描述的实施。要搜索的键集典型地与输入集trie的节点相关联，并且指示要匹配的值范围的值(键)典型地与范围trie的节点相关联，特别是与范围trie的叶节点相关联。要搜索的键集典型地是存储在数据库中的键集或数据库查询的结果或输入键集、或存储在信息检索系统中的键集或信息检索系统查询的结果或输入键的集合。
通过用户输入或其他方式获得用于执行查询的一个或多个范围的定义。该定义用于生成范围trie，其中与范围trie的节点(典型地是叶节点)相关联的值对应于一个或多个范围所包括的值。在下一步中，通过如上面描述的交集操作，将输入集trie与范围trie组合，以获得与结果trie的节点相关联的键集。最后，与结果trie的节点相关联的键集、或与结果trie的节点相关联的键的子集、特别是与结果trie的叶节点相关联的键、或从与结果trie的节点相关联的键导出的键集或值集合作为输出而获得。
图38示出了存储要在一个或多个范围内搜索的键集的输入集trie 3801、以及被生成以存储包括在一个或多个范围内的所有值的范围trie 3802。trie 3801和3802两者都由交集运算符3803组合以获得输入集trie 3801中的键集，其值位于由范围trie 3802所存储的一个或多个范围内。如上面描述的，不仅输入集trie和范围trie，而且交集运算符本身也可以实施相应的trie(节点)接口，如由图38中的三个三角形指示出的。在trie节点接口具有如上面呈现的getBitSet()和getChildNode(bitNum)方法的情况下，交集运算符3803可以调用这些操作，以遍历输入集trie 3801和范围trie 3802，如由图38中的虚线箭头指示出的。在由实线箭头指示出的数据流方向上，位图和子trie节点从集合trie 3801和范围trie3802传递至交集运算符3803。
图39示出了根据本发明的执行范围查询的方法的示例。输入集trie 3901的叶节点与值为“13”、“14”和“55”的三个键相关联。范围trie 3902被生成为包括与其值在范围内或[14..56]中的键相关联的所有叶节点。在范围trie的每个级别处，范围末端处的节点(在范围trie 3902节点1和5的示例中)对结果有部分贡献。范围末端之间的节点(在范围trie3902节点2、3和4的示例中)以及取决于它们的子trie完全有助于结果。由交集运算符3903对输入trie 3901和范围trie 3902的AND组合获得与结果trie 3905的节点相关联的键集。执行器3904可输出例如与结果trie 3905的叶节点相关联的键的值，即“14”和“55”。此输出对应于与输入集trie 3901的叶节点相关联的所有键的值，其位于[14..56]的范围内。
由交集运算符3903执行的算法可以用伪代码描述如下：
范围trie 3902是示出范围trie可以包括很多节点的示例。因此，具体化(materialize)范围trie 3902及其所有节点在时间和存储器空间方面将是昂贵的。由于这个原因，范围trie可被实施为虚拟trie，如上面已描述的那样，即在交集操作期间根据需要动态生成的trie。这在图39中通过利用虚线绘制的范围trie3902的三角形的内容指示出。
在交集运算期间，交集运算符访问并且虚拟范围trie通过应用程序编程接口(API)“即时”递送评估交集运算的结果trie所需的虚拟trie的分量。例如，虚拟trie的当前节点的位图可以通过上面介绍的getBitSet()方法访问，而子节点可以通过getChildNode()方法访问。API一方面返回相应的位图，并且另一方面返回对象(代替真实trie的子节点)，该对象将为下一次递归提供相应的位图。对于交集运算符来说，虚拟trie看上去就像是真实的、以物理trie数据结构实施的trie。
典型地，不评估虚拟trie的部分的至少一些，其不是评估交集运算的结果tire所需的，并且优选地仅动态生成虚拟范围trie的那些部分，其是通过交集运算将输入集trie和范围trie组合在一起所需的。在图39的示例中，由于如上面解释的分支跳过，在交集运算期间未访问与在范围trie的根节点的位图中设置的位2、3、4和5相关联的虚拟子trie，并且出于此原因，它们的节点都不曾被物理地生成(呈现或者整合)。
在根据本发明的范围查询的一些实施例中，类似于图39中示出的实施例，与输入集trie的叶节点相关联的键对特定数据类型的一个数据项进行编码。这些实施例也可以称为“一维”范围查询。在一维范围查询中，一个或多个范围的定义包括一个数据项的一个或多个范围的定义。
多维范围查询处理
在根据本发明的范围查询的其他实施例中，与输入集trie的叶节点相关联的键对特定数据类型的两个或更多个数据项进行编码。在这种情况下，一个或多个范围的定义包括数据项中的一个或多个数据项的一个或多个范围的定义。这样的实施例也可以被称为“多维”范围查询。虽然原则上可以对每个维度执行范围查询并执行结果的交集，但由于将涉及过多的trie和过多的运算符，因此其效率不高。
图40中示出了根据本发明的有效的多项或多维范围查询处理的示例。输入集trie4001是二维或二项trie，其中其叶节点中的每个与指定值对(x，y)的键相关联。这样的值对可以用于例如指定地理位置数据的经度和纬度，或者如(经度，ID)或(纬度，ID)的复合键，如下面将参照图54至图57所解释的。在此示例中，维度x和y中的每个维度在8进制系统中都包含两个数位，以提高可读性，但是在优选实施方式中，使用了上面描述的trie数据结构。如将从下面的解释将变得明显的是，根据一个键中的多个数据项的上面描述的交错编码，x维和y维以交错方式存储在输入集trie 4001中。
输入集trie 4001在级别1上具有根节点。与该根节点相关联的位图指示x维的第一个数位的值。在与根节点相关联的位图中设置了位“1”和“5”，这指示出存储在输入集trie中的键的x维的第一个数位是“1”或“5”。与级别2上的节点相关联的位图指示出y维的第一个数位的值。在与级别2上的节点相关联的位图中设置位“3”和“4”，其依赖于根节点的位“1”，并且在与级别2上的节点相关联的位图中设置位“6”，其依赖于根节点的位“5”。这指示出其x维以“1”开始的键的y维的第一个数位是“3”或“4”，并且其x维以“5”开始的键的y维的第一个数位为是“6”。与级别3上的节点相关联的位图指示x维的第二个数位的值。这些位图中设置的位指示出存在其y维以“3”开始的x维为“12”和“16”的键、其y维以“4”开始的x维为“12”和“15”的键、以及其y维以“6”开始的x维为“56”的键。级别4上的节点和级别5上的节点的位图未在图40中示出，而仅由取决于级别4上节点的小三角形指示出。
用于多项或多维范围查询的范围trie可以是通过针对由与输入集trie的叶节点相关联的键编码的数据项中的每个组合单项或一维范围trie而获得的多项范围trie，数据项的单项范围trie存储了数据项的一个或多个范围中包括的所有值。如上面描述的，单项范围trie可以是虚拟范围trie。这意味着仅动态生成虚拟单项trie的那些部分，其是组合单项范围trie以获得多项范围trie或通过交集操作组合输入集trie和单项trie所必需的。
在图40的示例中，针对二维范围查询获得了两个一维输入范围：针对x维的[15..55]的范围，以及针对y维的[30，31]的范围。创建(虚拟)范围trie 4002，其存储针对x维的[15..15]的范围，并且创建(虚拟)范围trie 4003，其存储针对y维的[30..31]的范围。
在某些多维范围查询中，对于某些数据项(维度)，无法获得范围的定义。例如，用户可以仅指定针对x维的范围[15..55]，以便对图40的二维输入集trie4001执行范围查询处理，但没有针对y维的范围的定义。这意味着用户对存储在输入集trie 4001中的所有键感兴趣，这些键的x维的值位于15到55之间，而与它们针对y维的值无关。未指定范围的维度将被跳过或忽略。这可以通过甚至为没有获得范围定义的数据项创建(虚拟)单项范围trie来实现，其存储数据项的可能值的整个范围。这样的trie也可以被称为“通配符trie”。例如，在一个实施方式中，MatchAll trie是实施上面提到的trie(节点)接口(“CDBINode”)的trie。在其任何节点上调用getBitSet()方法将始终返回设置了所有位的位图。
从单项或一维范围trie的组合获得的多项或多维范围trie典型地存储被存储在单项(一维)范围trie中的数据项的值的所有组合。例如，如果针对x维的范围是[11..13]，并且针对y维的范围是[7..8]，则组合的二维范围trie将存储(x，y)值对(11，7)、(11，8)、(12，7)、(12，8)、(13，7)和(13，8)的键。
图41示出了如何组合图40的一维范围trie 4002和4003的不同部分，以获得图42中示出的交错的二维范围trie。如在图42中可以观察出的，组合的二维范围trie中的x维和y维以与图40的输入集trie 4001相同的交错方式存储。相比之下，图43示出了如何将图40的一维范围trie 4002和4003组合以获得图44中示出的非交错的二维范围trie。从抽象的角度来看，这将导致包括所有X值键的trie，其中每个叶节点是包括所有Y值键的trie的根节点。
在本发明的优选实施例中，并且对于一维和多维范围查询都是如此，范围trie具有与输入集trie相同的结构或格式。因此，在多维输入集trie以交错方式存储数据项的情况下，多维范围trie优选地使用交错存储，并且在输入集trie以非交错方式存储数据项的情况下，多维范围trie优选地也不使用交错存储。此外，与范围trie的叶节点相关联的键优选地对与输入集trie的叶节点相关联的键相同的数据类型的数据项进行编码。最后，在范围trie中，优选地在与输入集trie中的对应数据项或数据项的分量相同级别的节点中编码某种数据类型的数据项或这种数据项的分量。
在多项或多维范围查询处理的一些实施例中，组合单项或一维范围trie以获得多项或多维范围是由以下函数执行，其提供了多项范围trie作为至函数(例如交集运算符)的输入，其实施了输入集trie与多项范围trie的组合。这在图64的示例中示出，其中由交错运算符6404执行组合。
在其他实施例中，在实施输入集trie与范围trie的交集的函数或运算符中执行单项或一维范围trie的组合以获得多项或多维范围trie。在这种情况下，多维范围trie将仅在概念上存在。实际上，实施输入集trie与范围trie的组合的函数或运算符访问(虚拟)一维范围trie，诸如如果它们一起形成了(虚拟)多维范围trie的话。如果存在未指定范围的维度，则实施输入集trie与范围trie的交集的函数或运算符将跳过或忽略这些维度，例如通过如上面描述的创建通配符trie。
在图40的示例中，组合是由二维交集(AND)运算符4004执行的。由交集运算符4004执行的算法可以用伪代码描述如下：
从概念上创建(虚拟)多维范围trie，其中，如果实际上组合一维范围trie以获得(虚拟)多维范围trie，至少如果多维范围trie具有与输入集trie相同的结构或格式，则结果trie中的每个节点的子节点集将是输入集trie与多维范围trie的中的对应节点的子节点集的AND组合的结果。
例如，图40示出了结果trie 4006，其类似于输入集trie 4001以交错方式存储x维和y维。结果trie 4006具有节点4007，该节点4007与值为(x＝1，y＝3)的键相关联。该节点表示节点4108的整个子节点集，其与值为x＝1的键相关联。对应于结果trie 4006的节点4007的输入集trie 4001的节点是节点4009，其是与值为x＝1的键相关联的节点。图41中示出了如果图40的一维范围trie 4002和4003则将获得的多维范围trie 4100被实际组合，并且其具有与输入集trie 4001相同的结构和格式。对应于结果trie 4006的节点4007的多维范围trie 4100的节点是节点4101，其是与值为x＝1的键相关联的节点。输入集trie 4001的节点4009的子节点集(节点4010和4011)与多维范围trie 4100的节点4101的子节点集(节点4102)的AND组合导致结果trie 4006的节点4007。
在许多情况下，以交错方式存储多维或多项输入集trie的不同维度或项将导致更有效的范围查询，如现在将参考图45和图46解释的。
图45示出了存储与图40的输入集trie 4001相同的值的输入集trie 4501，但是以非交错的方式。就像输入集trie 4001，输入集trie 4501在级别1上具有根节点，并且与该根节点相关联的位图指示x维的第一个数位的值。但是，与输入集trie 4501的级别2上的节点相关联的位图指示x维的第二个数位的值，而不是交错输入集trie 4001中的y维的第一个数位的值。与级别3上的节点相关联的位图指示y维的第一个数位的值，并且级别4上的节点的位图(图45中未示出)指示y维的第二个数位的值。
当根据本发明执行输入集trie 4501与相应的(同样是非交错的)二维范围trie的AND组合时遍历针对具有范围X＝[15..55]和Y＝[30..31]的二维范围查询的节点在图45中以阴影示出(未示出级别5上的节点)。尽管级别4中只有一个节点(x＝16，y＝3)是着色节点，但在三个较高级别上，总共需要遍历(访问)六个节点：根节点x＝1、x＝5、x＝15、x＝16和x＝53。
相比之下，图46示出了图40的交错输入集trie 4001，其中再次对根据本发明的针对具有范围X＝[15..55]和Y＝[30..31]的二维范围查询遍历的节点进行着色(未示出级别5上的节点)。与图45相同的级别4中的一个节点(x＝16，y＝3)是着色节点，但是在三个较高级别上，总共只需要遍历四个节点：根节点x＝1、x＝5和(x＝1，y＝3)。
这样做的原因是，虽然在非交错输入集trie 4501中，落入[15..55]的范围内的所有x值都被确定直到最后一个(第二个)数位，但是在交错输入集trie 4001中，通过查看y维的第一个数位，可以更快地消除不值得遍历的节点。通过查看另一个维度的第一个数位来消除节点的机会高于通过查看同一维度的另一个数位来消除节点的机会。如将理解的，不同维度的数位越多，交错存储的性能收益将越高。
如上面提到的，范围查询处理可以提供与输入集trie的叶节点相关联的键集作为输出，例如，在一维范围查询的情况下，或者如果用户对存储在输入集trie中的多维键的所有维度感兴趣的话。可替选地，范围查询处理可以提供简化项键集作为输出，其对由与输入集trie的叶节点相关联的键编码的数据项的子集进行编码。图47和图48中示出了其示例。
在图47中，二维或二项trie输入集trie 4701与图40的输入集trie 4001相同，其中其叶节点中的每个与指定值对(x，y)的键相关联。示例中的用户对存储在输入集trie中的所有x值感兴趣。因此，尽管未详细示出，但是一维范围trie 4702是通配符trie，其存储了x维的可能值的整个范围，而一维范围trie 4703是通配符trie，其存储了y维的可能值的整个范围。
类似于图40的一维范围trie 4002和4003，一维范围trie 4702和4703至少在概念上被组合，以获得二项或二维范围trie。由于两个一维范围trie都是通配符trie，因此二维范围trie包含所有可能的值对(x，y)。然后通过二维交集(AND)运算符4704将二维范围trie与二维输入集trie 4701组合。类似于图40的二维交集(AND)运算符4004，交集运算符4704根据交集操作将二维输入集trie与二维范围trie组合，以获得与相应结果trie的节点相关联的键集。此外，如上面解释的，结果trie中每个节点的子节点集是二维输入集trie中的对应节点的子节点集与二维范围trie中的对应节点的子节点集的AND组合。由于二维范围trie存储所有可能的值对(x，y)，因此结果trie与输入集trie相同。
与图40的交集运算符4004相比而言，由于用户仅对存储在输入集trie中的x值感兴趣，因此图47的交集运算符4704没有提供与输入集trie的叶节点相关联的键集(x，y)作为输出。而是，交集运算符4704仅提供用于x维的值集合作为输出，在该示例中，存储在输入集trie中的所有x值的集合。
在范围查询处理提供简化项键集作为输出的情况下，类似于在图47中，从与未在简化项键中编码的数据项有关的输入集trie的不同分支中获得的简化项键集可能包含重复项。例如，如在图47中可以看到，输入集trie 4701中存在其x值为12的至少两个叶节点，即y值的第一个数位为3(12，3…)的至少一个叶节点和y值的第一个数位为4(12，4…)的至少一个叶节点。为了在提供输出之前消除重复的键，特别是如果在上游运算符中使用输出集，从与未在简化项键中编码的数据项有关的输入集trie的不同分支获得的简化项键集在提供该输出之前进行合并。对于两个维度，可以以可接受的有效方式对输入集trie的每个级别执行合并。但是，将简化项键集写入新创建的trie中通常将更高效(例如，其中输入集trie具有大于两个维度)，从而自动消除重复。
在图47的示例中，为了消除输出集中的重复x值，通过交集操作将输入集trie4701与二维范围trie组合而获得的x值键集被写入新创建的一维trie，其节点与仅具有x值的键相关联。这个新创建的一维trie如图48中示出的。与其叶节点相关联的键的值对应于存储在输入集trie 4701中的所有x值的集合。
由仅输出x值的二维交集运算符4004所执行的算法可以用伪代码描述如下：
在图47的示例中，仅提供x维的值作为输出。如将理解的，当仅提供y维的值作为输出时，适用相同的原理。此外，由于一维范围trie 4702和4703都是通配符trie，因此提供存储在输入集trie 4701中的所有x值作为输出。如将理解的，在一维范围trie 4702和/或4703仅存储所有可能的x和/或y值的子集的情况下，可以仅提供存储在输入集trie 4701中的所有x值的子集作为输出。例如，如果一维范围trie 4702与图40的范围trie 4002相同，仅将x值存储在[15..55]的范围内，则由交集运算符4004提供的输出将不包括x＝12的值。作为另一示例，如果两个一维范围trie 4702和4703都与图40的相应范围trie 4002和4003相同，仅将x值存储在[15..55]的范围内，并且相应地仅将y值存储在[30..31]的范围内，则由交集运算符4004提供的输出将仅包括x＝16的值。
模糊搜索
文本检索应用程序的常见要求是提供近似的字符串匹配-也称为模糊搜索功能。那就是查找与模式近似匹配而非完全匹配的字符串。
这种“模糊性”(两个字符序列之间的差异)的典型测量是Levenshtein距离。两个字符串之间的Levenshtein距离是将一个字符串更改为另一个字符串所需的单字符编辑(字符插入、删除或替换)的最小数量。
类似于以上讨论的虚拟范围trie，本发明的一个方面针对一种优选虚拟模糊匹配trie，其使用布尔AND与如索引trie的存储trie进行交集，以返回匹配键字符串或包括匹配键字符串的文档。如上面描述的，索引trie可以将每个出现的术语和文档ID存储为两个键部(字符串、long)。
根据本发明的这个方面，通过执行近似字符串匹配从电子数据库或信息检索系统中检索数据。首先，获得搜索字符串。接下来，建立存储包括搜索字符串和/或搜索字符串的变型的近似字符串的匹配trie。使用交集操作将匹配trie与存储trie组合，该存储trie存储被存储在电子数据库或信息检索系统中的字符串或电子数据库或信息检索系统查询的结果字符串集。换句话说，结果trie的至少部分被评估，该结果trie是使用相交运算的、匹配trie与存储了被存储在电子数据库或信息检索系统中的字符串集的存储trie的组合。结果trie是以下trie，它存储了在当存储trie所存储的键集与匹配trie所存储的键集相交时获得的键集。
该存储trie可以是索引trie，例如存储由文档和相应的文档标识符所包括的字符串作为两个键部，诸如(字符串、long)。由被存储在匹配trie中的字符串集所包括的字符串通常被永久地存储在电子数据库或信息检索系统中和/或代表电子数据库或信息检索系统中的条目。
类似于在上面描述的trie的交集中，获得了结果trie。结果trie中的每个节点的子节点集是匹配trie和存储trie中的对应节点的子节点集的交集，其中，如果相同的键与不同trie的节点相关联，则不同trie的节点将彼此对应。典型地，匹配trie、存储trie和结果trie具有相同的结构或格式。除非本节中另有说明，否则以上讨论的对trie的交集操作的所有方面也适用于模糊搜索的上下文中的trie的交集。
如上面描述的，trie包括一个或多个节点，每个子节点与键部分相关联，并且从trie中的根节点到另一个节点的路径定义了与该节点相关联的键，该键是与路径上的节点相关联的键部分的级联。可以使用上面描述trie数据结构来实施trie。但是，与上面描述的示例不同，匹配trie典型地是无向循环。这意味着匹配trie中的子节点可能有超过一个父节点。图48B至图48E中提供了无向循环的示例，下面将对其进行详细说明。相反，存储trie和结果trie中的每个子节点典型地只有一个父节点。
根据本发明的模糊搜索特别高效，匹配trie是虚拟trie，其是在匹配trie与存储trie的交集期间动态生成的。仅(动态)生成虚拟trie的那些部分，其是匹配trie与存储trie的交集所必需的，其有时也称为“惰性计算”。除非本节中另有说明，否则上面讨论的虚拟trie的所有方面也适用于在模糊搜索的情况下使用虚拟匹配trie。
作为模糊搜索的输出，提供了字符串和/或其他数据项，诸如与结果trie的节点的结果集相关联的文档标识符。典型地，匹配trie包括匹配节点的集合，每个匹配节点与一个或多个键相关联，所述一个或多个键对应于来自近似字符串集的字符串之一。在这种情况下，节点的结果集可以是与匹配trie中的匹配节点集相对应的结果trie的节点集(如果与结果trie的节点相关联的键和与匹配trie的节点相关联的键相同，则结果trie的节点对应于匹配trie的节点)。这意味着仅提供如文档标识符的那些字符串数据项作为输出，这些字符串数据项与对应于匹配trie的匹配节点的结果trie的节点相关联。
参照图48A至图48E，现在将描述可以如何生成(虚拟)匹配trie，其存储包括搜索字符串和/或搜索字符串的变型的近似字符串集。匹配trie是从表示近似字符串集的有限自动机中导出的。首先，建立表示近似字符串集的非确定性有限自动机。在非确定性自动机中，两个状态之间的每个转换典型地与由搜索字符串所包括的特定字符、通配符或空字符串相关联。从非确定性有限自动机，可以导出也表示近似字符串集的确定性有限自动机，其中，确定性有限自动机的两个状态之间的转换典型地与由搜索字符串包括的特定字符或者通配符相关联。然后从确定性有限自动机中导出匹配trie。
图48A示出了非确定性有限自动机(NFA)，以匹配最大编辑距离为2的搜索字符串“abc”，也称为Levenshtein自动机。如技术人员所知，有限自动机包括状态以及状态之间的转换。标记有附图标记0001的状态为开始状态，状态0006匹配0次编辑的结束状态，状态0007为1次编辑的状态，并且状态0008为2次编辑的状态。对于更大的编辑距离，务必在顶部添加另外的状态行。较大的字符串会在右侧导致另外的状态。
状态0002是匹配第一个字符(“a”)的状态转换。对于“abc”作为输入，到达最终状态0006。状态0003是开始时插入字符的状态转换，例如，如果将“xabc”提供给自动机的话。状态转换0004反映了字符替换，例如将“ybc”提供给自动机。最后，转换0005反映了字符删除，例如将“bc”提供给自动机。
可以看出，图48A的自动机是不确定的。例如，提供“a”作为第一个输入字符将导致状态01、11、10、12、21、22和32。该状态集合包含匹配状态(32，附图标记0008)，这是因为“abc”需要删除两个字符以得到“a”。
可以使用例如所谓的Powerset构造方法将NFA转换为确定性有限自动机(DFA)。用于有效创建Levenshtein自动机DFA的其他方法包括由Klaus Schulz和Stoyan Mihov提出的方法。图48B示出了这样的DFA，用于匹配编辑距离为1的“abc”，以减少示例的状态数。由附图标记1001标记的状态是开始状态。附图标记1002是指特定字符(“b”)的转换。附图标记1003是指任何其他字符(通配符)的转换。如标记为1005的灰色状态是匹配状态。
在优选实施例中，匹配trie和存储trie中的父节点包括位图，并且trie中子节点的键部分的值由子节点的父节点所包括的位图中(设置)的位的值确定，取决于所述子节点与哪个位相关联。在上面的示例中已经描述了这种trie数据结构。它们允许特别有效的交集操作，这是因为可以通过使用交集操作组合子节点中的每个的位图来实现匹配trie的子节点与存储trie的子节点的交集。
可以通过与转换相关联的特定字符或通配符的编码来关联有限自动机的状态之间的转换以获得增强有限自动机来从(确定性)有限自动机中导出具有这种数据结构的匹配trie，其编码由一个或多个位图组成或表示，该一个或多个位图的长度和/或格式等于由匹配trie的父节点所包括的位图。对于特定字符的编码，在由编码所包括或表示的位图中的每个中恰好设置了一位。对于通配符的编码，将所有有效字符编码的位设置在由该编码所包括或表示的位图中，从而“屏蔽”所有有效字符编码(或所有有效字符编码的位，除了与转换所离开的状态相关联的特定字符的编码之外)。换句话说，通配符的编码是所有有效字符编码的位图的OR组合(或所有有效字符编码的位图的OR组合，除了与转换所离开的状态相关联的特定字符的编码之外)。
图48C示出了图48B的DFA的转换的这种增强，其中使用了如上面参考图21所描述的用于Unicode字符和Unicode字符串的编码方案。为了提高可读性，仅使用10位Unicode字符编码。这些编码使用两个每个64位的位图。如上面描述的，由于在这些位图中的每个中恰好设置了一位，因此它们每个都能够编码6位(2
编码2001表示编码为两个6位值1(“000001”)和33(“10001”)的“a”，每个位位置编码为
和
以十六进制表示，其中0000＝0，0001＝1，0010＝2，0011＝3，…，1111＝F，这对应于0x0000000000000002和0x0000000200000000。
编码2003表示编码为两个6位值1(“000001”)和34(“10010”)的“b”，每个位位置编码为
和
以十六进制表示，这对应于0x0000000000000002和0x0000000400000000。
在通配符的情况下，设置所有允许字符的编码的位(在这种情况下为完整的Unicode字母表)。例如，编码2002的位设置为表示所有10位编码的Unicode字符，即6位值“000000”…“001111”和“000000”…“111111”，每个位位置编码为
和
以十六进制表示，这对应于0x000000000000FFFF和0xFFFFFFFFFFFFFFFFFF。
编码2004和2005表示相同的字符“b”，一个为非最终情况，并且一个为匹配状态，即，“b”是输入字符串中的最后一个字母。编码2006和2007示出了通配符的模拟情况。2008和2009示出了字符“c”和通配符的最终匹配状态的情况。
导致不匹配状态的所有Unicode字符(如上参考图21所解释的10位、15位和21位编码)的完整通配符掩码为：
导致匹配状态的所有Unicode字符的完整通配符掩码为：
图48D示出了匹配trie的结果顶部，每个10位Unicode字符由两个键部分表示。由于trie上的布尔AND运算符首先需要位图，并且随后又下降到匹配的子节点，因此将特定字符编码为单个位，并且将通配符编码为位图，并为所有有效字符编码设置位。
这种匹配trie可以直接从上面描述的任何有限自动机、特别是增强有限自动机中导出。然而，在存储在匹配trie、存储trie或结果trie的字符是由相应trie的多个M＞1个键部分编码、即由超过一个级别的节点编码的情况下，匹配trie优选地从表示近似字符串集的完全有限自动机导出。优选地，M在2至4之间。
来自如上面描述的优选地确定性有限自动机、更优选地来自增强有限自动机的完全有限自动机，通过使用M–1个级别的中间状态以及经由M–1个中间状态链接两个状态的M个转换的一个或多个序列来替换有限自动机的两个状态之间的转换优选地每个转换、或通过将有限自动机的两个状态之间的转换优选地每个转换与M–1个级别的中间状态以及经由M–1个中间状态链接两个状态的M个转换的一个或多个序列相关联。因此，与完整字符串不相关的状态将添加到有限自动机中。
例如，在图48B和图48C的有限自动机中，存在从状态0离开并在状态1中结束的转换。在完全有限自动机中，从图48D可以变得明显的，该转换被中间状态110代替，并且转换序列包括状态1和状态110之间的转换以及状态110和状态1之间的另一个转换。作为另一示例，在图48B和图48C的有限自动机中，存在从状态0离开并在状态10结束的转换。在完全有限自动机中，该转换被中间状态110所代替，并且转换序列包括状态1与状态110之间的转换以及状态110与状态10之间的另一转换。作为第三示例，在图48B和图48C中的有限自动机中，存在从状态0离开并在状态14结束的转换。在完全有限自动机中，该转换被中间状态110和111以及两个转换序列代替。第一转换序列包括状态1与状态110之间的转换以及状态110与状态14之间的另一转换。第二转换序列包括状态1与状态111之间的转换以及状态111与状态14之间的另一转换。
序列中的M个转换中的每个都与中间编码相关联，该中间编码由位图组成或表示，其长度和/或格式等于由匹配trie的父节点所包括的位图，并且其中，匹配trie从完全有限自动机导出。该编码在这里被称为“中间”，这是因为它仅表示整个字符的编码的一部分，在完全有限自动机的示例中，从中可以导出图48D的匹配trie的整个字符的编码的一半。
例如，在可以从中导出图48D的匹配trie的完全有限自动机中，状态0和状态110之间的转换与由以下位图组成或表示的编码相关联：
以十六进制表示，它对应于0x0000000000000002。该编码与状态0和110之间的转换的关联由转换的编码2001之间的上方虚线箭头指示出。该箭头指向的“1”代表由图48D的匹配trie的父节点0包括的位图中的位号1(第二位)。
作为另一示例，在可以从其导出图48D的匹配trie的完全有限自动机中，状态0和状态111之间的转换与由以下位图组成或表示的编码相关联：
以十六进制表示，这对应于0x000000000000FFFF。该编码与状态0和111之间的转换的关联由转换的编码2002之间的上方虚线箭头指示出。该箭头指向的“0，2…63”代表由图48D的匹配trie的父节点0包括的位图中的位号0、2…63(第一、第三…第64位)。
在有限自动机的两个状态之间的转换与特定字符相关联的情况下，由与序列的M个转换相关联的中间编码所包括或表示的位图的级联是特定字符的编码，并且恰好一个位在位图中的每个中设置。
在图48B和图48C的有限自动机的示例中，状态0和1之间的转换与字符“a”相关。因此，在可以从中导出图48D的匹配trie的完全有限自动机中，由与状态0和1之间的两个转换(经由状态110)相关联的中间编码包括或表示的位图的级联是字符“a”的编码，其中位图中的每个中恰好设置了一位。该编码如下：
和
在十六进制表示中，这对应于0x0000000000000002和0x0000000200000000。
如果有限自动机的两个状态之间的转换与通配符相关联，则由与序列的M个转换相关联的中间编码包括或表示的位图的级联包括一种编码，其中所有有效字符编码的位设置在由编码所包括或表示的位图中，或者除了与转换所离开的状态相关联的特定字符的编码之外的所有有效字符编码的位。
在图48B和图48C的有限自动机的示例中，状态0和14之间的转换与通配符相关。因此，在可以从其导出图48D的匹配trie的完全有限自动机中，由与状态0和14之间的两个转换(经由状态111)相关联的中间编码的序列之一包括或表示的位图的级联是通配符的编码。该编码如下：
和
在十六进制表示中，这对应于0x000000000000FFFF和0xFFFFFFFFFFFFFFFFFF。
此外，在有限自动机的两个状态之间的转换与通配符相关联的情况下，由与序列的M个转换相关联的中间编码所包括或表示的位图的级联典型地将包括一个或多个编码，其包括特定字符的编码的一个或多个部分以及编码的一个或多个部分，其中所有有效字符编码的位都设置在由该编码所包括或表示的位图中，或者除了用于与转换所离开的状态相关联的特定字符的编码之外的所有有效字符编码的位。
例如，在可以从其导出图48D的匹配trie的完全有限自动机中，由与状态0和14之间的两个转换(经由状态110)相关联的中间编码的序列之一包括或表示的位图的级联是一种编码，包括字符“a”的编码的第一部分(其也是字符“b”的编码的第一部分)和通配符的编码的第二部分。该编码如下：
和
在十六进制表示中，其对应于0x0000000000000002和0xFFFFFFFFFFFFFFFFFF。
增强有限自动机或完全有限自动机可以分别由包括多个行的数据结构表示或存储在其中，每一行表示增强有限自动机或完全有限自动机的一个状态，并且包括离开状态的转换中的每个的元组，每个元组包括与转换相关联的编码和对转换结束状态的引用。图48E示出了作为数组的数组的这样的数据结构，其可以用于表示完全有限自动机的状态，可以以特定有效的方式从其导出图48D的匹配trie。对于转换结束的每个状态，这样的数据结构可以包括关于该状态是否是匹配状态的信息，优选地在对该状态的每个引用中将其编码为位。数据结构典型地包括转换从其离开的各自增强有限自动机或完全有限自动机的状态中的每个的行。
这种(虚拟)匹配trie方法的益处是性能良好，这是因为导致有效执行的实施方式的简单性，因为无需使用复杂的状态机等，并且还由于AND运算符在优选实施例中的位图上工作的方式。
索引方法和性能测量
为了测量根据本发明的各个实施例的范围查询的性能，进行了实验，其结果将在下面参考图53至图70进行讨论。具有空间查询的地理位置应用程序被用作示例。样本数据从欧洲区域的OpenStreetMap数据导出，其可以从http://download.geofabrik.de/europe.html获得。示例数据库中的每个条目都包含10数位ID、每个纬度和经度在小数点后具有七个位置的值、以及表示街道名称和门牌号的字符串。
进行第一个实验，以查看索引大小(索引记录的数量)如何影响恒定结果大小的查询处理性能。查询数据库以返回慕尼黑区域中的小矩形内的所有位置的ID(经度11.581981+/-0.01和纬度48.135125+/-0.01，如图49中示出的)。该数据库总共包含约2850万条记录，并且其中3,143个匹配。
对于第一个系列的测量，首先加载匹配的记录，并且然后将大约2850万条其他记录添加到数据库中。这些其他记录在图50中以阴影区域示出。每添加100,000条记录，就会进行查询并测量其执行时间。显然，每个查询返回3,143个匹配。
对于第二系列的测量，还首先加载了矩形内的匹配记录，但是在没有匹配经度或纬度的“带”内的记录的情况下加载了其余记录。图51中示出了第二系列测量中加载的其余记录。
第一个实验是在五种不同的索引和查询地理位置的方法上进行的。
在现有技术方法中，这里使用了称为“现有技术索引”的Apache Lucene 6.0.1数据库引擎的SpatialPrefixTree，其支持组合了经度和纬度的空间索引(https://lucene.apache.org，包org.apache.lucene.spatial.prefix.tree)。SpatialPrefixTree不是trie，而是用于创建针对空间查询优化的反向索引。因此，它为此处采用的方法提供了良好的基准。
为了查询指定矩形内的所有位置，在两个维度上都执行了范围查询。每个查询都返回表示位于指定的经度或纬度带的记录的ID的集合，其由基于游标的迭代器收集以创建临时结果集。临时结果集进行交集以获得最终结果集。如图52中示出的，其中阴影区域标记了指定的经度和纬度带(临时结果集)，并且黑色区域标记了指定的矩形(最终结果集)。SpatialPrefixTree不是trie，而是用于创建针对空间查询优化的反向索引。通过为几个分辨率级别创建几个索引，可以增强查询性能，类似于trie的可变精度索引，下面将参考图58至图60对其进行解释。
图53示出了现有技术方法的测量结果。x轴指示出已加载到数据库中的记录数，并且y轴指示出在对数刻度中每秒执行的查询数。可以观察到，具有或和没有加载到数据库中的匹配带的情况下，查询性能都会随着数据库中的记录数量的增加而降低。这种性能行为对于现有技术数据库来说是典型的，其中访问时间取决于索引的填充级别。
做出了使用上面描述的trie的优选实施例索引和查询地理位置的第一方法，其在本文中被称为“标准索引”。借由优选实施例的第一二维trie创建一个纬度索引，并借由优选实施例的第二二维trie创建另一个经度索引。换句话说，二维索引trie中的每个分别存储两个项，即(纬度，ID)或(经度，ID)。二维索引trie以非交错的方式存储，如上面图44的trie中示出的，其中纬度/经度形成第一键部，并且ID形成第二键部。从抽象的角度来看，这导致包含所有纬度/经度的trie，其中每个叶节点是包括具有相应纬度/经度的所有位置的ID的trie的根节点，如图54中示出的。
第一键部(纬度/经度)上的范围查询返回具有匹配的纬度/经度的位置的ID的trie根节点。为了利用trie接口递送这些结果，使用提供trie接口的多OR运算符组合trie根节点的列表，如图55中示出的。因此，如图56中示出的，根据本发明的标准索引使用两个索引trie 5601、5603，其每个具有两个键部：(纬度，ID)或(经度，ID)。对于trie的第一个键部，使用虚拟纬度/经度trie 5602、5604执行范围查询。使用多OR运算符5605、5606组合范围查询中的每个的结果。使用AND运算符5607组合两个多OR运算符的结果，其递送最终结果。
图57示出了标准索引的测量结果。可以观察到，在没有匹配记录加载到数据库中的情况下，查询处理时间是恒定的，这是由于trie具有恒定的访问时间，即与其填充水平无关。鉴于Lucene数据库引擎的SpatialPrefixTree已针对空间查询进行了优化，查询处理时间也比使用现有技术的方法短约10倍，这是非常明显的。
在匹配的记录加载到数据库中的情况下，标准索引的查询性能下降，这是因为必须组合越来越多的独立纬度和经度查询结果。具有匹配记录的标准索引的性能不是很好，这是因为出现了很长的节点(ID)列表。为了提高性能，需要减少务必通过OR操作组合的节点数量。
在本文中称为“可变精度索引”的方法中，可以通过保持具有可变精度的多个索引、创建层次结构来显着减少需要进行OR的节点数量。这与在上面提到的现有技术数据库引擎中为几个分辨率级别创建几个索引的概念相当。例如，使用存储2数位十进制数字的trie中的范围，可以使每个级别的索引表示前缀：
-0，1，2，...9
-00，01，02，...，09，10，...99
借由示例，图58中示出了X值的第一级的索引(第一个键部)，并且图59中示出了X值的第二级的索引，其中第二键部(Y项)可以是ID。图58中示出的第一级索引中的条目(第一个键部的叶节点或X项)包含相应前缀范围中的X值的所有ID(第二个键部的trie)。X范围从10到53的查询将组合图58的索引上的范围1..4的查询结果(两个命中，由虚线矩形标记)与图59的索引上的范围50..53的查询结果(一次命中，由虚线矩形标记)。这导致仅需在随后的多OR操作中组合三个节点，代替仅使用图59的索引trie时的五个节点。
由发明人进行的实际实验针对每个精度步骤使用了6位。精度长度存储在键的第一个字节中。trie具有11个级别，并且trie中的节点在根节点级别处具有至多16个子节点，在随后的10个级别(包括叶节点)处具有至多64个子节点。这意味着对于必须进行OR的trie的左右部分，在根节点级别处最多16-2个节点，并且在下一级别处2*(64-1)个节点。这导致上限为务必进行OR的16-2+2*(64-1)*10＝1274个trie。接受范围查询的每个键值均以11个精度级别存储。如上面描述的，基于虚拟范围trie的范围查询被用于执行查询。创建了选择所需节点所需的所有键的列表。
图60示出了可变精度索引的测量结果。当未加载匹配段时，查询执行非常快(比使用标准索引时快约10倍)，并且时间恒定。即使将匹配的记录加载到数据库中，查询性能也几乎是恒定的。但是，如下面将示出的，可变精度索引在存储器需求和索引性能方面很昂贵。
索引和查询地理位置的另一种方法(在本文中称为“二维索引”)表明，存在一种比标准索引更快的解决方案，但没有可变精度索引的缺点。在这种方法中，在图61中示出的，数据库条目的经度/纬度和ID存储在交错的trie中，其具有上面讨论的结构，例如，参考图32和图46。就像标准索引，在两个不同的trie中分别对纬度和经度进行索引，即trie 6110(经度，ID)和trie 6120(纬度，ID)。
为了查询矩形，创建了指定经度范围的虚拟范围trie 6130和指定了纬度范围的虚拟范围trie 6140。当经度索引与经度范围trie进行交集、并且同时纬度索引与纬度范围trie进行交集时，组合交集的中间结果，如将在下面进行解释的。
在第一步中，在经度索引trie 6110的根节点6111和经度范围trie 6130的根节点的位图之间执行按位AND操作，如由图61中的箭头6151指示出的。同样地，在纬度索引trie6120的根节点6121与纬度范围trie 6130的根节点的位图之间执行按位AND操作，如由图61中的箭头6152指示出的。
图61中的节点6112和6122表示索引trie 6110和6120的级别2上的节点。级别2上的这些节点中的每个都是索引中的ID键部的根节点。因此，经度索引trie 6110的根节点6111和经度范围trie 6130的根节点的位图之间的按位AND操作产生属于具有指定经度范围的位置的ID的第一键部分，并且纬度索引trie 6120的根节点6121和纬度范围trie 6140的根节点的位图之间的按位AND操作将产生属于具有指定纬度范围的位置的ID的第一键部分。
在第二步中，索引trie中不属于落入指定经度和纬度范围内的位置的键按如下方式过滤：由第一个步骤产生的经度/纬度索引trie 6110/6120的节点的位图通过按位OR操作组合，并在按位OR操作的结果之间执行按位AND操作，如由图61中的箭头6153指示出的。
图61中的节点6113和6123表示索引trie 6110和6120的级别3上的节点。级别3上的这些节点中的每个都存储被存储在索引trie中的经度/纬度键部的第二键部分。第三步中的操作继续进行，级别3上的节点属于第二步中尚未过滤掉的键。如由图61中的箭头6154、6155指示出的，在这些节点与相应范围trie 6130、6140的对应节点(在级别2上)的位图之间执行按位AND操作。
图61中的节点6114和6124表示索引trie 6110和6120的级别4上的节点。级别4上的这些节点中的每个点都存储被存储在索引trie中的ID键部的第二键部分。第四步中的操作继续，级别4上的节点作为第三步中的按位AND操作的结果产生。与第二步类似，由第一步产生的具有相同父节点的经度/纬度索引trie 6110/6120的节点的位图通过按位OR操作组合，并在按位OR操作的对应结果之间执行按位AND操作，如由图61中的箭头6156指示出的。
以相同的方式继续操作，直到到达索引trie的叶节点为止。总之，使用匹配器组合两个索引，其仅返回具有第一维(x)的交替索引的“视图”。匹配器的输出中第二维被抑制。
图62示出了二维索引的测量结果。同样，当没有匹配的段加载到数据库中时，查询时间是恒定的。在将匹配的段加载到数据库中的情况下，与标准索引相比而言，查询性能得到了显着改善。
匹配和抑制维度的策略原则上可以应用于两个以上的维度。但是，这会导致节点链很大：x维的每个节点可能具有y维的64个子节点，而这些子节点又可能具有64个子节点，总共已经有4096个子节点。
在索引和查询地理位置的最后一种方法(在本文中称为“单索引的索引”)中，仅创建了一个多维索引，其将经度和纬度都存储在一个交错的trie中，如上面讨论的，例如，参考图32和图46。该索引trie的示意图在图63中示出，其中表示经度和纬度的第一键部X和第二键部Y以交错的方式存储，并且表示位置的ID的第三键部存储在子trie中，其取决于X/Ytrie的叶节点。存储在子trie中的每个中的ID属于具有相同经度和纬度的位置集。
为了查询矩形，如上面描述的，例如参考图40，执行二维范围查询。如图64中示出的，经度的范围由第一一维虚拟范围trie 6402指定，并且纬度的范围由第二一维虚拟范围trie 6403指定。由交错运算符6404组合两个一维范围trie，以形成交错的二维范围trie。为了获得属于匹配的经度和纬度的ID子trie的集合，AND运算符6405在二维范围trie和索引trie 6401的X/Y部分之间执行交集。
图65示出了单索引的索引的测量结果。可以观察到，单索引的索引提供了完美的可伸缩性，并且即使加载了匹配的带时，查询性能也不明显取决于数据库中的记录数。请注意，性能的峰值是由Java虚拟机垃圾收集引起的。
图66示出了第二个实验的结果，其中在增加的结果大小上测量了查询性能(每秒查询)。查询矩形的纬度和经度从+/-0.01增加到+/-0.20度。首先，将2850万条记录加载到数据库中。可以观察到，对于较大的结果，可变精度索引的缩放比例最佳(请注意，由于存储器的限制，只能为可变精度索引加载部分数据)。单索引的索引还提供了良好的性能。当除纬度和经度外，ID还以交错方式存储时，尤其如此。可以相信，三重交错索引的性能收益是由于公共前缀路径数量的增加而引起的，这也由较小的存储器占用空间(46.01对44.76字节/点)证明。由于树中的分支较少，因此性能可能会更好，这可能导致遍历树的递归步骤更少。
使用Lucene数据库的现有技术索引对于所有结果大小都递送了几乎恒定的结果，但是性能水平低于单索引的索引。对于较小的结果大小，标准索引(两个索引不交错)和二维索引(两个索引交错)的性能比使用Lucene数据库的现有技术索引要好，但是对于较大的结果大小，性能较差。图67示出了与图66相同的结果，但在x轴上具有对数刻度。在该表示中，可以看出，根据本发明的索引的查询性能随着结果大小的增加而直线下降。这意味着特别是这两个单索引方法具有线性可伸缩性，即结果大小加倍使查询时间加倍。
在第三个实验中，测量了索引性能(每秒索引的条目)。加载了2850万条记录，并且每添加100,000条记录就测量时间。可以观察到，现有技术索引和所有基于trie的方法在索引增长方面提供了几乎恒定的性能。结果总结在图68中。如上面提到的，可变精度索引性能不佳，这是因为每个记录必须创建2x 11个索引条目。其方法类似于可变精度索引的现有技术索引(Lucene)性能甚至更差。基于trie的标准索引和二维索引都为每个记录创建2个索引条目，并且因此具有相似的索引性能。单索引的索引每条记录仅创建一个索引条目，并且性能最佳。请注意，在基于trie的方法中，黑色列表示未压缩trie的结果，并且浅色列表示使用位图压缩的trie的结果。
图69比较了每个索引位置的不同索引所需的存储器空间。现有技术的Lucene索引比基于trie的标准索引和具有位图压缩的二维索引(浅色列)和单索引的索引使用了更多的空间，即使没有位图压缩也是如此。基于trie的可变精度索引比任何其他方法都需要更多的空间。
可以得出结论，对于低基数或中基数的属性，标准索引工作足够好。例如，产品价格典型地没有连续的值空间，而是离散的值，如3.99、4.49、4.89等。代替将如订单日期之类的内容存储为具有毫秒精度的时间戳，可以按天或小时精度将其存储，以满足使值空间“更”离散的要求。要对具有连续值空间的列进行索引，可变精度索引提供了更好的性能，尤其是如果在多维查询中使用的话。但是，由于索引速度慢且存储器需求高，因此只能建议在静态应用程序和有足够存储器可用的情况下使用可变精度索引。对于紧密联系的维度，单索引的索引是中等预期结果大小的最佳解决方案。
即使此处已在空间查询的上下文中提出了多维索引，基于trie的范围查询也可以应用于许多其他情况，例如用于图数据库。属性图数据库基于通过边连接的节点，节点和边都具有属性。如果节点和边每个都由唯一的ID表示，则可以使用这三个ID作为维度来表示和查询节点-边-节点三元组。请注意，这同样适用于资源描述框架(RDF)及其主语-谓语-宾语表达式的上下文，在RDF术语中称为三元组。
如上面提到的，通过将每个出现的术语和文档ID存储为两个键部(字符串，long)，本发明也可以容易地用于全文搜索应用程序。由于本发明基于前缀树，因此它继承了前缀树的字符串搜索功能。例如，它可以用于有效地实施模糊(相似)搜索。
实际上，发明人进行的测量示出了在信息检索应用程序中的竞争性能。在本申请的优先权日之前不久进行的实验中，对500,000篇英语Wikipedia文章进行了索引。图70A示出了以字符/秒为单位与Lucene信息检索软件库相比而言的本发明实施例的平均索引性能。可以看出，当使用长整数的数组(黑色列)时，本发明的系统仅递送了稍低的索引性能。如预期的那样，当使用具有字节数组的位图压缩(浅色列)时，索引性能略微降低。
图70B比较了索引大小(索引大小/文本大小，以％为单位)。令人惊讶的是，即使基于长整数数组(黑色列)的存储器模型也可以与Lucene媲美-尽管存在对准损失。基于位图压缩并具有字节数组(浅色列)的存储器模型所需的空间比Lucene少。
图70C示出了查询性能(查询/秒)。在此实验中的术语查询会搜索所有包含组合“来自”的单词“哪个”或“他的”的文档，以提供一定的复杂性和数量。利用多个并发线程，本发明系统的性能比Lucene的性能高出至多七倍。
本实验中的模糊查询搜索包含类似于“chica”的单词的文档。相似性是由编辑距离(Levenshtein距离)为1定义的，即最多删除、插入和替换一个字符。在这门学科中，发明的系统被证明比Lucene快四到六倍。值得注意的是，Lucene和本发明的系统都递送了完全相同数量的结果文档：用于术语查询的319,809和用于模糊查询的30,994。
在本申请的提交日期之前不久，即大约一年之后，重复上面描述的实验。重复实验的结果可见于图70D至图70F中。
从图70D中可以看出，索引性能现在比之前的实验要低。在本发明的系统中，它较低是因为现在已经完全实施了存储器管理，以牺牲一些性能为代价。在Lucene系统中，它较低是因为Lucene索引仅在一个线程/CPU内核上运行。这样做是为了获得更好的可比性，这是因为根据本发明的系统也仅用一个线程/CPU内核来实施。注意，本发明的系统的索引也可以并行化，但是本发明人尚未实施。
图70E示出了与早期的实验相比，索引大小实际上保持不变。
图70F示出了与较早的实验相比，本发明的系统的查询性能得到了改善，特别是在模糊搜索中。在较早的实验中，仅预先生成了如图48C示出的DFA，其仅包括对应于与全字符串相关联的状态的节点。图48D中示出的中间状态(不与完整字符串相关联的有限自动机的状态)是由于字符编码需要两个或更多个键部分的事实而存在的，其是在交集操作期间运行中动态确定的。相反，在后面的实验中，具有状态和转移的完整集合的有限自动机是预先生成的，并存储为数组(矩阵)的数组，如图48E中示出的。这种方法使查询性能提高了两倍左右。与早期的实验相比而言，Lucene系统的改进程度相似，这是由于Lucene系统在本申请的优先权日和申请日之间进行了某些优化。
机译： 在数据库中有效使用TRIE数据结构
机译： 在数据库中有效使用TRIE数据结构
机译： 在数据库中有效使用TRIE数据结构
