用于数据库系统的考虑了高速缓存的并行控制方案

1.一种访问索引结构的索引节点的方法，用于在其中驻留在主存 储器中的索引结构包括索引节点的环境中搜索数据库中的数 据，其中每个索引节点具有：节点内容、指示节点内容更新状 态的版本号、以及控制对每一节点的并行存取的锁存，所述方 法包括对一个节点执行无锁存读取操作的步骤，对一个节点执 行无锁存读取操作还包括以下步骤：
将所述节点的版本号复制到寄存器中；
在复制所述版本号后，读取所述节点的内容；
读取所述内容后，校验所述节点的锁存，并且如果所述 节点的锁存已锁定，返回复制所述节点的所述版本号的步骤以 重试；以及
在通过校验所述锁存后，校验所述节点的版本号，并且 如果当前的版本号与复制的版本号不同，返回复制所述节点的 所述版本号的步骤以重试。
2.根据权利要求1所述的方法，其中通过对节点执行更新操作来 更新所述节点内容，所述更新操作包括以下步骤：
在更新前，锁定所述节点的锁存；
更新所述节点的内容；
更新后，增加所述节点的版本号；以及
通过重置所述锁存来释放所述锁存。
3.根据权利要求2所述的方法，其中所述锁存和版本号包含在一 个单字中，所述单字包括所述锁存和所述版本号。
4.根据权利要求3所述的方法，其中所述单字的最低有效位被用 于所述锁存，而其它位被用于版本号。
5.根据权利要求4所述的方法，其中复制所述节点的所述版本号 的步骤，利用关闭最低有效位功能来执行，所述功能以一个值 返回其最低有效位关闭的单字的值；而校验所述锁存的步骤和 校验所述版本号的步骤，通过将所述值与所述单字的当前值进 行比较来执行。
6.根据权利要求4所述的方法，其中锁定所述节点的锁存的步骤 包括：
执行关闭最低有效位功能，所述执行关闭最低有效位功 能以第一值返回其最低有效位关闭的所述单字的值；
执行打开最低有效位功能，所述执行打开最低有效位功 能以第二值返回其最低有效位打开的所述单字的值；
执行比较和交换指令，所述指令将所述第一值与所述单 字的当前值进行比较，如果两个值相同，则用所述第二值替换 所述单字；以及
如果所述两个值不同，则转到执行关闭最低有效位功能 的步骤。
7.根据权利要求4所述的方法，其中增加所述版本号的步骤与释 放所述锁存的步骤，通过将单字的值加1的指令来实现。
8.根据权利要求1所述的方法，进一步包括：当所述节点上的锁 存已锁定时，在返回复制所述版本号的步骤之前，插入一个时 延的步骤。
9.根据权利要求1所述的方法，进一步包括：如果当前版本号与 复制的版本号不同，在返回复制所述版本号的步骤前，插入一 个时延的步骤。
10.根据权利要求1所述的方法，进一步包括将重试的次数限制到 某一预设值的步骤。
11.根据权利要求10所述的方法，进一步包括：当重试次数超过 所述预设值时，在读取一个节点前，取得一个共享锁存的步骤。
12.根据权利要求1所述的方法，其中所述数据库驻留在主存储器 中。
13.根据权利要求1所述的方法，其中所述数据库驻留在磁盘中。
14.根据权利要求1所述的方法，其中访问所述数据库以进行事务 处理。
15.根据权利要求1所述的方法，其中所述环境包括独立存取所述 索引结构的多个处理器。
16.根据权利要求1所述的方法，其中所述环境包括运行多个线程 的单处理器，每个线程独立存取所述索引结构。
17.根据权利要求1所述的方法，其中所述数据库是一种关系数据 库管理系统。
18.根据权利要求1所述的方法，其中所述索引结构是一种树型结 构，且所述节点内容进一步包括一个指示所述节点中键值的上 界的高键以及指向同一级其它节点的链指针。
19.根据权利要求1所述的方法，其中所述索引结构是索引树，并 且一部分索引树驻留在一个或多个高速缓存中。
20.根据权利要求1所述的方法，其中所述索引结构是一种 B+-tree。
21.根据权利要求1所述的方法，其中所述索引结构是一种 CSB+-tree。
22.根据权利要求1所述的方法，其中所述索引结构是一种B-tree。
23.根据权利要求1所述的方法，其中所述索引结构是一种 B*-tree。
24.根据权利要求1所述的方法，其中所述索引结构是一种T-tree。
25.根据权利要求1所述的方法，其中所述索引结构是一种R-tree。
26.根据权利要求1所述的方法，其中所述索引结构是一种 CR-tree。
27.根据权利要求1所述的方法，其中所述索引结构是一种GiST。
28.一种在多处理环境中管理数据库的系统，包括：
用于储存索引结构的主存储器，所述索引结构具有用于
访问所述数据库的索引节点，其中每个索引节点具有：用于访 问所述数据库的每一条记录的节点内容、用于指示已更新版本 的版本号、以及用于控制并行存取所述节点的锁存；
用于储存频繁存取索引节点的一个或多个高速缓存；以 及
用于执行节点无锁存读取操作的装置，该装置包括：
用于将所述节点的版本号复制到寄存器中的装置；
用于在复制所述版本号后，读取所述节点的内容的装置；
用于读取所述内容后，校验所述节点的锁存，并且如果 所述节点的锁存已锁定，返回复制所述节点的所述版本号的步 骤以重试的装置；以及
用于在通过校验所述锁存后，校验所述节点的版本号， 并且如果当前的版本号与复制的版本号不同，返回复制所述节 点的所述版本号的步骤以重试的装置。
29.根据权利要求28所述的系统，该系统还包括用于执行节点一
致更新操作的装置，该装置包括：
用于在更新前，锁定所述节点的锁存的装置；
用于更新所述节点的内容的装置；
用于更新后，增加所述节点的版本号的装置；以及
通过重置所述锁存来释放所述锁存。
30.根据权利要求28所述的系统，进一步包括用于包含每个节点 的所述版本号和所述锁存的单字。
31.根据权利要求28所述的系统，其中所述节点内容包括指向其 它节点的指针和键值。
32.根据权利要求28的系统，其中所述数据库驻留在主存储器中。
33.根据权利要求28所述的系统，其中所述数据库驻留在磁盘中。
34.根据权利要求28所述的系统，其中所述数据库被访问，以进 行事务处理。
35.根据权利要求28所述的系统，其中所述多处理环境包括独立 存取所述索引结构的多个处理器。
36.根据权利要求28所述的系统，其中所述环境包括运行多个线 程的单处理器，每个线程独立存取所述索引结构。
37.根据权利要求28所述的系统，其中所述索引结构是一种 B+-tree。
38.根据权利要求28所述的系统，其中所述索引结构是一种 CSB+-tree。
39.根据权利要求28所述的系统，其中所述索引结构是一种 B-tree。
40.根据权利要求28所述的系统，其中所述索引结构是一种 B*-tree。
41.根据权利要求28所述的系统，其中所述索引结构是一种 T-tree。
42.根据权利要求28所述的系统，其中所述索引结构是一种 R-tree。
43.根据权利要求28所述的系统，其中所述索引结构是一种 CR-tree。
44.根据权利要求28所述的系统，其中所述索引结构是一种 GiST。

技术领域\n本发明一般涉及数据库管理系统。更具体地讲，本发明涉及用 于数据库系统中驻留存储器索引结构的考虑了高速缓存 (cache-conscious)的并行控制方案。\n背景技术\n由于服务器DRAM(动态随机存储器)组件价格的不断降低， 主存储器数据库管理系统(MM DBMS)在许多应用中就成为了驻 留磁盘数据库管理系统(DR DBMS)的一种经济可行的替代。不 仅在读事务方面而且在更新事务方面，MM DBMS在性能上比DR DBMS潜在地高出几个数量级。\n然而，MM DBMS相对于DR DBMS显著的性能优势的取得并 不是自动实现的，而是需要MM DBMS专用的优化技术，尤其是高 速缓存的有效利用。高速缓存，一种存取时间比主存储器快得多的 特殊的存储设备，储存着频繁引用的数据项，从而提高总的存储存 取性能。在主存储器索引和查询处理的设计中，MM DBMS中的高 速缓存的效果是一个重要的考虑因素。\n目前，存在所谓的考虑高速缓存的索引结构，例如CSS-tree(高 速缓存灵敏搜索树)以及CSB+-tree(高速缓存灵敏B+树)，它们 是作为能减少高速缓存丢失而因此提高搜索效率而提出的替代索 引结构。CSS-tree是在一个数组中一层一层地设置索引节点，通过 计算数组偏移实现索引遍历(index traversal)。CSB+-tree每个节点 仅保留B+-tree的一个子节点指针，它可以将树的扇出(fanout)几 乎增加一倍，但这是以增加更新成本为代价的。\n此外，还有其它索引结构，例如CR-tree。认识到对于MBR关 键字比指针大得多的R-tree而言，删除指针不是很有效，CR-tree 对MBR关键字进行了有效地压缩，以便在每个节点装入更多的条 目。通过将局部-关键字信息储存在索引中而不管非无效关键字的大 小，pkT-tree和pkB-tree有效地减小了缓存丢失。\n虽然所有这些考虑高速缓存的索引结构采用了一些有效增加 索引扇出、减小所谓的冷(cold)高速缓存丢失和容量高速缓存丢 失的方法，但它们的索引结构设计并未考虑到并行控制因素。并行 控制需要协调多用户或多处理器的多处理环境中同时执行的事务。 对于运行涉及索引更新的现实的主存储器数据库应用，以及利用现 有多处理器平台提高此类应用的性能，并行控制至关重要。\n处理这一问题的一种方法是使用传统的、驻留磁盘系统中用到 的并行控制方案，例如锁耦合(lock coupling)。在索引遍历期间， 锁耦合锁存索引节点。通过在申请子节点上的锁存的同时，持有父 节点上的一个锁存，从而进行从一个节点到其子节点的索引遍历。 如果子节点不是目标节点，则所申请的锁存为共享模式。如果子节 点是目标节点，则根据要对目标节点执行的操作，所申请的锁存可 以是共享或独占模式。当事务希望从节点读取数据时，则发布共享 锁。当事务希望在节点上写入数据项时，则发布独占锁。只要子节 点闭锁，父节点的锁存就被释放。然而，锁存涉及存储器写入，在 多处理环境中，容易发生相干高速缓存丢失。\n有一种称为物理版本的技术，它允许无锁存的索引遍历。其思 想是：创建一个用于更新的索引节点的新型版本，这样读取现有索 引节点的事务就不会干扰那些更新索引节点的事务。这就可以实现 无锁存的索引遍历，实现读取事务的高级并行。将更新过的版本加 入索引需要获得树级或树和将要更新的节点的锁存。这种物理版本 技术存在的主要问题在于需要很高的创建版本成本。随着更新率的 提高，索引性能会急剧下降。对于多处理单元的数量而言，更新性 能的可扩展性很差。\n因此，需要一种高效的索引结构以及并行控制方案，能在多处 理环境中优化数据库管理系统，消除高速缓存无效的高昂代价。\n发明内容\n本发明的一个目的在于提供一种高效的索引结构，用于在主存 储器中具有数据库的数据库管理系统(DBMS)。\n本发明的另一目的在于提供一种高效的索引结构，用于带有高 速缓存的DBMS中，该高速缓存用于存储频繁存取的索引节点以提 高存储器存取性能。\n本发明的再一目的在于提供一种并行控制方案，用于多处理环 境中具有高速缓存的MM DBMS中。\n本发明的又一目的在于提供一种并行控制方案，以保证索引读 取器不会干扰并行的索引更新器。\n利用本发明的不用锁存任何节点可有效遍历索引的开放式、无 锁存索引遍历(“OLFIT”)并行控制方案，可以实现上述目的及其 它目的。在每个节点中，该OLFIT方案保留一个锁存、一个版本号、 以及一个指向同一级的下个节点的链接。\n索引遍历涉及一致节点更新操作以及从根节点开始的无锁存 节点读取操作。为了保证无锁存条件下节点读操作的一致性，每次 节点更新首先获得该节点的锁存，并在更新节点内容后将版本号加 1。节点的读操作从将版本号读入寄存器开始，并以校验当前版本 号是否与寄存器存储的版本一致结束。如果它们相同，则读操作是 一致的。否则，重新进行节点读取操作，直至校验成功。本发明的 并行控制方案可应用于B+-trees、CSB+-trees、及其变体。\n附图说明\n图1为一个涉及多处理器的多处理环境中的高速缓存无效的实 例图。\n图2为使用开放式、无锁存索引遍历(OLFIT)的本发明的并 行控制方案的框图，其中数据库和索引结构驻留在主存储器中。\n图3是本发明的另一实施例的框图，其中数据库和索引结构驻 留在磁盘中而不是主存储器中。\n图4是本发明的第三实施例的框图，其中多个线程独立地存取 索引结构。\n图5是根据本发明的B+-tree索引节点的结构图。\n图6为节点分裂期间没有高键和链指针的节点分裂操作的实例 图。\n图7为节点分裂期间带有一个高键和一个链指针以保证正确的 索引遍历的节点分裂操作的实例图。\n图8A和8B为用于OLFIT的CSB+-Tree节点结构的实例图。\n图9A和9B分别为B+-tree和完全CSB+-tree中OLFIT的八线 程性能随节点大小变化的曲线。\n图10A和10B分别为B+-tree和完全CSB+-tree中各种并行控 制方案的搜索性能曲线。\n图11A和11B分别为在B+-tree和完全CSB+-tree中各种并行 控制方案的插入与删除的性能曲线。\n图12A和12B分别为在B+-tree和完全CSB+-tree中各种并行 控制方案的单线程性能随着更新率变化的曲线。\n图13A和13B分别是在B+-tree和完全CSB+-tree中各种并行 控制方案的八线程性能随更新率变化的曲线。\n具体实施方式\nI并行控制\n相干高速缓存丢失\n图1显示了在具有传统数据库管理系统(DBMS)的查询处理 系统中，相干高速缓存丢失是如何发生的。DBMS是一个管理数据 库结构以及控制数据库存取的程序集合。在主存储器100中，有一 个包括节点n1到n7(101至107)的索引树，用于访问磁盘或主存 储器中的数据库。为了简单起见，假设每个节点对应一个高速缓存 块，且包含一个锁存。如同上文所述，锁存可以保证一次事务唯一 地存取一个数据项。有四个处理器(108到111)通过高速缓存 (112-115)访问主存储器100。\n让我们考虑这样一种情况：在主存储器查询处理系统冷启动 时，处理器p1 108遍历路径(n1 101，n2 102，n4 104)，这样这些 节点就被复制在p1 108的高速缓存器c1 112中。在这过程中，保持 和释放n1和n2上的锁存。现在，p2 109遍历路径(n1 101，n2 102， n5 105)，然后这些节点被复制到c2 113，这样锁存这些节点的p2 109 就使高速缓存在c1 112中的n1和n2无效。可以注意到：即使在高 速缓存c1 112中有足够的空间，也会发生高速缓存无效的情况。如 果p3 110遍历路径(n1 101，n3 103，n6 106)，c2 113中的n1就变 得无效。最后，如果p4 111遍历路径(n1 101，n3 103，n7 107)， c3 114中的n1和n3就变得无效。\n本发明的OLFIT方案\n图2示出了根据本发明实现开放的无锁存索引遍历(OLFIT) 方案的整个系统，它利用了数据库事务的“开放(optimistic)”特点， 这样大部分数据库事务都不会发生冲突。\n主存储器201储存数据库203和索引结构202(通常为树型结 构)，从而有效管理该数据库。为处理单元#1204(或处理单元#2 205)设置的高速缓存#1206(或高速缓存#2207)，用于储存频繁 存取的索引节点208(或209)，以提高总的存储器存取时间性能。 为了协调处理单元或线程，以维持处理的一致性而不会有太频繁的 高速缓存项目无效，设置了并行控制单元210(优选在软件中实现)。 具体地，并行控制单元210提供了索引节点的无锁存遍历所需的控 制，这种控制基于开放式索引并行控制。\n图3显示了本发明的另一实施例，其中数据库225和索引树224 驻留在磁盘223中，而不是图1的主存储器201中。主存储器221 储存着索引节点的子集(“缓存的索引节点”)222。为处理单元#1 226 设置的高速缓存#1 228，用于储存频繁存取的索引节点(“高速缓存 索引节点”)230。相似地，为处理单元#2 227设置的高速缓存#2 229， 用于储存高速缓存索引节点231。并行控制单元232(优选在软件 中执行)用于在多处理环境中控制高速缓存#1 228和高速缓存#2 229。\n图4示出了本发明的另一可选实施例，其中多处理通过能够对 数据库执行独立存取的几个处理线程实现。一个线程就是程序中的 控制的一个单个顺序流(sequential flow)。线程#1 245和线程#2 246 运行在处理器244中，它们独立地访问主存储器241中的数据库 243，主存储器241也存储引用数据库项目的索引树242。设置了高 速缓存248，用于储存频繁存取的索引，具有用于线程#1和线程#2 的每个线程检索节点的专用高速缓存条目。\nOLFIT的节点操作\n图5显示了本发明的OLFIT方案所使用的B+-tree索引节点的 结构。节点内容信息和并行控制信息储存在每个索引节点中。节点 内容包括用于存取数据库的键值和指向其它节点的指针305。并行 控制信息包括控制并行存取节点的锁存301和代表节点内容更新状 态的版本号302。节点内容还包括指定树索引中节点级别的级别 303、指示节点中项数的大小304、高键306，以及链指针307。高 键306和链指针307的使用将在下面解释。\nOLFIT方案基于字的基本读取与基本写入操作，每个操作均为 单一的不可再分的工作单元。目前产生的体系结构均支持字的基本 读取与基本写入。在读取和更新节点的描述原语(primitive)中， 假定以下操作都能够由基本操作实现：读取版本号、更新版本号、 更新锁存、以及校验锁存是否已锁定。\nUpdate Node(更新节点)原语\nU1.以独占模式取得锁存。\nU2.更新节点的内容。\nU3.将版本号加1。\nU4.释放锁存。\nUpdate Node原语是“一致的”，它保证更新将某一节点从一个 一致的状态改变到另一个一致的状态。为了做到这一点，节点的更 新操作利用节点上的1-bit锁存将其隔离和串行化。独占模式中的锁 存保证了当发生更新时不会有其它事务存取该节点。在更新节点内 容(例如级别、大小、键&指针、高键，以及链指针)前，当在该 节点上没有独占锁时，更新器将取得该节点上的锁存用于独占方式 存取。锁存在更新后释放。在释放锁存前，更新器也要将版本号加 1。与节点读取不同，节点更新总能成功而无需再试。步骤U3(即， 将版本号加1)是为了使读取器能够读取无锁存的所述节点，并校 验它们读取的节点是否处于一致的状态。\nRead Node(读取节点)原语\nR1.将版本号复制到寄存器X中。\nR2.读取节点的内容。\nR3.如果锁存被锁定该节点上，转到R1(在某一选择延迟后)。\nR4.如果当前版本号与X中复制的值不同，转到R1(在某一选 择延迟后)。\nRead Node原语是“一致的”，在这种意义下，步骤R3和R4保 证了读取器以一致的状态只读取不持有任何锁存的节点。只有在 R2中读取的数据处于一致状态的情况下，读取器才能够通过R3和 R4，否则读取器要从R1重新开始。在从R1重新开始前，Read Node 原语可选择等待一段时间，直至解决了与并行的更新节点原语的冲 突。Read Node原语所读取信息的一致性可以表述为一个定理，证 明如下。\n定理：与Update Node原语一起，Read Node原语保证在R2中 读取的节点的内容不能处于不一致的状态。换言之，如果在R2中 读取的节点的内容处于不一致的状态，R3中的条件或R4中的条件 变为真，则读取器无法全部通过R3和R4。\n证明：R3校验是否有任何并行的更新。如果R3中的条件为假 而读取器能够通过R3，由于U1是持有锁存而U4是释放锁存，那 么，或者任何并行更新的U4在R3之前一定已经完成；或者在R3 之后一定开始了任何并行更新的U1。R4校验在R1与R4之间是否 存在版本号的任何更新。如果R4中的条件为假而读取器能够通过 R4，由于U3更新了版本号，所以任何并行更新的U3必须在R1 之前或R4之后发生。在下述公式中，A→B表示A在B之前执行。 根据Read Node和Update Node原语的定义，保持有两条语句 R1→R2→R3→R4和U1→U2→U3→U4。均通过R3和R4的情况(当 R3和R4中的条件都为假时)可表示及推导如下：\n((U4→R3)∨(R3→U1))∧((U3→R1)∨(R4→U3))\n＝((U4→R3)∧(U3→R1))∨((R3→U1)∧(U3→R1))∨((U4→R3)∧(R4→U3)\n∨((R3→U1)∧(R4→U3))\n＝((U4→R3)∧(U3→R1))∨FALSE∨FALSE∨((R3→U1)∧(R4→U3)\n(U3→R1)∨(R3→U1)\n因此，如果R3和R4中的条件均为假，要么任何并行更新的 U3必须在R1之前，要么任何并行更新的U1必须在R3之后。由 于更新U2中所述节点内容在U1与U3之间，且读取R2中节点内 容在R1和R3之间，所以在R2中读取的某一节点内容不能处于非 一致状态。Q.E.D.\n注意：R3(校验锁存的步骤)和R4(校验当前版本号的步骤) 可以在一条单个指令中执行。\n为了保持坚固性(robustness，也可称之为鲁棒性)，可以调整 ReadNode原语以限制重试的次数。限定重试次数的ReadNode被描 述为RobustReadNode。RobustReadNode原语使用一条Conversative ReadNode原语，当重试次数超过某一限制时，该原语会在读取节 点前取得一个共享模式的锁存。共享模式锁存允许并行地进行多个 读取事务，并且只要并行事务为只读，则它就不会产生冲突。在 RobustReadNode原语中，RETRY_LIMIT为用户定义的重试次数的 上界，而重试次数为一个局部变量(用于计算重试的次数)。为了 简单起见，在RobustReadNode中，ReadNode的R3和R4由“或” 操作连接。\nConservativeReadNode原语：\nPR1.以共享模式取得一个锁存。\nPR2.读取节点的内容。\nPR3.释放锁存。\nRobustReadNode原语：\nRR1.将重试次数初始化为0。\nRR2.将版本号复制到寄存器X中。\nRR3.读取节点的内容。\nRR4.如果锁存锁定于独占模式或者当前版本号与X中复制的 版本号不同，\nRR4-A.如果重试次数小于或等于RETRY_LIMIT，则重试次数 加1并转到RR2。\nRR4-B.否则，执行ConservativeReadNode。\n与无冲突多数情况的ReadNode相比，RobustReadNode在RR1 中只多使用了一条指令。\n以下示出了Read Node和Update Node原语的执行。为了简便 起见，只显示了ReadNode而不是RobustReadNode的实现。因而， 本领域技术人员将意识到，可以容易地将ReadNode的实现修改为 RobustReadNode的实现。procedure latch(word)\nbegin\n1.do{\n2.     t:＝turn-off-LSB(word)；\n3.}while(compare-and-swap(word，t，turn-on-LSB(t))≠t)；\nend\nprocedure unlatch(word)\nword:＝word+1；\nend\nprocedure update_node(node)\nbegin\n1.  latch(node.ccinfo)；\n2.  //Update the contents of node\n3.  unlatch (node.ccinfo)；\nend\nprocedure read_node(node)\nbegin\n1.do{\n2.    t:＝turn-off-LSB(node.ccinfo)；\n3.    //Read the contents of node\n4.}while(t≠node.ccinfo)\nend\n如果使用目前这一代计算机体系结构普遍支持的“检验与设 置”和“比较与交换”操作等基本的读取与写入操作中的一种已经执 行锁存，则Read Node和Update Node原语的实现能够直接取自该 操作的描述。\n然而，在一个或两个高速缓存块数量级下，由于考虑到节点的 大小，每个节点的锁存和版本号占用两个字成本太高，所以将这两 个字合并到一个称作ccinfo的单字中。ccinfo的最低有效位(″LSB″) 用于锁存，字中的其它比特用于版本号。这种合并能够进一步优化， 而仅使用一个条件跳转用于校验ReadNode原语中的R3和R4的状 态。\n操作compare-and-swap(A，B，C)是比较A与B的值，如果相 同，则用C的值取代A的一项基本操作。该操作返回A的初始值。 Turn-on-LSB(字)与turn-off-LSB(字)分别为打开和关闭一个字 的LSB的比特操作。\nupdate_node过程可实现UpdateNode原语。过程latch的步骤2 复制LSB关闭的ccinfo的值。过程latch的步骤3通过比较ccinfo 的值和步骤2中复制的t值以校验ccinfo的LSB是否打开，并通过 用LSB打开的t替代ccinfo的值，以自动地打开ccinfo的LSB。过 程unlatch用于释放锁存，并通过增加的ccinfo而将其版本号加1。 由于ccinfo的LSB在过程latch中被打开，所述过程unlatch中的加1 关闭了锁存并同时将版本号加1。\nRead_node过程可实现ReadNode原语。read_node的步骤4同 时校验了ReadNode的R3与R4中的条件，因为如果t等于ccinfo， 则当前ccinfo的LSB一定已被关闭，而从步骤2起其它比特一定已 被更改。\nOLFIT的树操作\n在节点进行开行分裂与删除的同时，不用锁存，OLFIT可以保 证根据搜索键，树遍历能到达正确的叶节点。无锁存遍历减少了相 干高速缓存丢失，并且由于搜索、插入、以及删除操作包括树遍历， 从而提高了这些树操作的性能。例如，包含搜索键的搜索操作从最 左端叶节点开始遍历，然后向右遍历叶节点。插入操作开始遍历找 到将包括新条目的叶节点，然后将条目插入该节点。删除操作开始 遍历以找到包括要删除的条目的叶节点，然后从所述节点删除该条 目。\n节点分裂的处理\n由于当向下遍历树索引时，OLFIT方案不使用锁耦合，并行更 新器可以在遍历到达该子节点之前，分裂遍历的目标子节点。此外， 由于读取节点时不持有锁存，并行更新器也可以分裂正在被读取的 节点。\n图6A和6B显示了使用传统的索引结构，节点分裂之前和之 后的节点分裂实例。这些图显示了带有搜索键25的读取器正在从 n2 402向下遍历的情形，而插入n10的并行更新器通过n6 406分裂 为(n6 416和n10 420)的分裂繁殖，可以将图6A中的n2 402分裂 为图6B中的(n2 412和n11 421)。如果所述遍历在分裂后通过n2， 它就会选路到n5 415(而不是n6 416)，而最后会到达一个错误的叶 节点。\n图7A和7B分别为利用本发明的索引结构的节点分裂前和分 裂后的节点分裂实例，为了解决上述节点分裂出现的问题，本发明 的索引结构中加入了一个指示节点中键值上界的高键和指向同一 级别该节点的右兄弟(right sibling)节点的链指针。所有分裂均从 左向右进行，并且每个节点都加入了一个高键和一个链指针。节点 的高键表示该节点中键值的上界，而链指针为指向该节点同一级别 上的右节点的指针。链指针提供了到达一个节点的另外一条路径， 而高键确定了是否跟随该链指针。使用所述链指针，由于分裂从左 向右进行，且每一节点都有自己的高键和指向右节点的链指针，所 以从一个节点开始的所有节点分裂都可以从该节点到达，并且出现 节点并行分裂时，也可以到达正确的子节点。\n图7B显示了即使并行更新器将图7A中的n2 442分裂为(n2 和n11)，在该分裂后，通过n2 452的带有搜索键25的遍历，将由 链指针选路到n11 461，然后被正确地选路至n6 456。\n树遍历过程\n以下示出了找出与搜索键对应的叶节点的树遍历过程。\nprocedure traverse(root_node，search_key)\nbegin\n1.node:＝root_node；\n2.while(node is not a leaf node){\n3.    t:＝turn-off-LSB(node.ccinfo)；\n4.    next_node:＝find_next_node(node，seach_key)；\n5.    if(node.ccinfo＝t)node:＝next_node；\n6.}\n7.return node；\nend\n在遍历过程中，find_next_node(node，search_key)为找出要遍 历的下一节点的操作。如果search_key比所述节点的高键大，则此 操作返回链指针；否则，将指针转向要向下遍历的适合子节点。\nread_node过程被嵌入到了所述遍历过程。只有当next_node的 值从一致状态中的某一节点计算得到，next_node的值才被分配到 可变节点。\n节点删除处理\n由于并行更新器能够分裂正在被读取的节点，所以如果节点为 空的话，更新器也能够删除正在被读取的节点。为处理这一情况， 当某一节点为空时，更新器只删除指向该节点的链接，并将该节点 寄存到无用节点收集器中。直到该节点确实被释放，空节点中的链 指针才被删除。当没有能够读取该节点的索引操作时，无用节点收 集器才真正释放所寄存的节点。为了判断是否有任何能读取该节点 的索引操作，要使用一个带有物理版本的相同的无用节点收集，但 所用开销大不相同，这是因为物理版本使用每次更新的无用节点收 集器，但它只有在更新器从树索引删除一个空节点时才被用到。\n使用附在每一线程上的全局时间戳以及专用时间戳。注意：假 设线程执行事务。全局时间戳初始化为0，而专用时间戳初始化为 ∞。当开始索引操作时，每一线程均将全局时间戳的值复制到其无 锁存的专用时间戳中；而当结构索引操作时，则将其专用时间戳重 置为∞。在线程删除一个节点后，线程便将带有所述全局时间戳当 前值的节点寄存到无用节点收集器中，并将持有与该全局时间戳相 关的锁存的全局时间戳加1。无用节点收集器周期性地扫描所有线 程的专用时间戳，并实际释放所寄存的时间戳小于专用时间戳当前 最小值的节点。由于在删除节点无法到达而专用时间戳被设置为开 始遍历前的全局时间戳的值之后，带有全局时间戳的值的删除节点 才被寄存，所以任何索引操作均无法到达带有的时间戳小于专用时 间戳当前最小值的寄存节点。\n虽然已经说过Read Node和Update Node原语用于保证节点存 取之间的一致性，也可以用一个使用这些原语的变量，来保证索引 存取之间一致性。此类变量的实例如下，具体为，Update Index原 语和Read Index原语。\nUpdate Index(更新索引)原语\nU1.取得一个独占模式锁存。\nU2.更新索引。\nU3.将版本号加1。\nU4.释放锁存。\nRead Index(读取索引)原语\nR1.将版本号复制到寄存器X中。\nR2.读取索引。\nR3.如果锁存被锁定，转到R1(在选择延迟后)。\nR4.如果当前版本号与X中复制的值不同，转到R1(在选择延 迟后)。\n事务周期锁定\n本发明可以与记录上的处理周期锁定一起支持事务的可串行 性。使用Find_First，Find_GE，Find_GT，Scan_Next，Insert，and Delete 原语可以描述这种结合的一个实例。假定在索引中索引的项目以降 序从左向右排序。Find_First为查找索引中最左端项目并初始化迭 代器的操作。Find_GE为查找键值大于或等于索引中搜索键值并初 始化迭代器的操作。Find_GT与Find_GE相似，除了Find_GT查找 键值大于搜索键值的项目。Scan_next为查找由Find_First，Find_GE， Find_GT，或Scan_Next找到的项目的下一项目。Insert(插入)是 将一个项目添加入索引的操作，而Delete(删除)为从索引删除一 个项目的操作。\n以下为Find_GE的过程。\nprocedure find_GE(root_node，search_key)\nbegin\n1.node:＝traverse(root_node，search_key)\n2.while (node is not null){\n3.    t:＝turn-off-LSB(node.ccinfo)；\n4.    pos:＝find_position_GE(node，seach_key)；\n5.if(pos＞node.size){\n6.    next_node:＝node.link_ptr；\n7.    if(t＝node.ccinfo)node:＝next_node；\n8.}\n9else{\n10.record:＝get_record(node，pos)；\n11.lock(record，SHARED_MODE)；\n12.if(t＝node.ccinfo)\n13.    return iterator(search_key，node，pos，ccinfo，record)；\n14.else unlock(record)；\n15.}\n16.}\n17.return iterator(search_key，NULL，0，0，NULL)；\nend\n在Find_GE过程中，Find_position_GE(node，search_key)为 返回其键值大于或等于节点中search_key的最左边记录的位置的操 作。该操作返回一个比节点尺寸大的值。Get_record(node，position) 是一项将指针返回到处在节点位置的记录的操作。Lock(record， mode)为一种以指定模式持有记录处理周期锁的操作，unlock (record)为释放记录处理周期锁的操作。\nread_node过程被嵌入到Find_GE过程，用于向右遍历以及锁 定记录。\n虽然所述实例针对Find_GE，对于本领域有经验的人士来说， 其它原语Find_First，Find_GT，Scan_next，Insert和Delete也可以以相 同方式实现。\nII.对CSR+-TREE的修改\n图8A和8B显示了为OLFIT而对CSB+-Tree进行调整的节点 和节点组。图8A显示了无叶节点500的节点结构。对于CSB+tree， 具有同一父节点的节点都集中在称作节点组508的相邻空间内，节 点组508包括仅储存指向子节点组的指针(而不是所以指向子节点 的指针)的CSB+-tree的非叶节点500。由于这一原因，如果右兄弟 节点的父节点与所述节点的父节点相同，则没有指向兄弟节点指 针，也能够查找出所述节点的右节点。由于同一节点组中的右节点 没有指针也能够定位，所以用于OLFIT的CSB+-tree节点仅储存高 键507，而无任何链指针。如图8A所示，每个节点组仅储存一个 指向右节点组的链指针，以定位其它节点组中的右兄弟节点。由于 链指针512不属于所述节点组中的任何节点，所以链指针512具有 其本身的锁存510以及版本号511。\n类似地，图8B显示了叶节点的节点结构。此处，CSB+-tree代 表完全的CSB+-tree，CSB+-tree的一种变体。对于本领域技术人员 而言，很明显可以扩展到CSB+-tree的其它变体。\nCSB+-tree的分裂操作与B+-tree的分裂操作不同。由于具有同 一父节点的节点集中在一个节点组中，当某一节点分裂时，如果节 点组不满的话，节点组中的所有右兄弟节点均向右移位为该分裂腾 出空间。如果节点组满了，节点组则分成两个节点组。当一个节点 分裂时没有产生节点组的分裂，则要分裂的节点、所有移位的右兄 弟节点以及父节点都要在分裂前锁存起来。当节点组由于组内节点 的分裂而被分裂，则要分裂的节点、移动到新节点组中的节点、指 向右节点组的链指针以及父节点都要在分裂前锁存起来。\nIII.试验结果\n通过实现本发明，证明了本发明具有优越的可扩展性。对 B+-tree和完全CSB+-tree，OLFIT方案与四种其它的索引并行控制 方案的性能做了比较：(1)带有节点锁存的锁耦合(″LC″)；(2) 带有树锁存的树级锁定(″TL″)；(3)带有节点锁存的物理版本 (″VN″)；以及(4)带有树锁存的物理版本(″VT″)。对于100％ 搜索和单一线程实验，也测量了无任何并行控制(″NO″)的索引操 作的性能。对于物理版本方案VN和VT，用于T-tree的版本方案被 调整以用于B+-tree和完全CSB+-tree。\n实验是在运行Solaris 2.7操作系统的带有八个CPU(UltraSparc II 400MHz)的Sun Enterprise 5500服务器上进行的。每个CPU具 有一个高速缓存行大小为64字节的8MB L2高速缓存。在下述四 种工作载荷条件下，运行每一种并行控制方案：(1)100％搜索操作； (2)100％插入操作；(3)50％插入和50％删除操作的混合操作； 以及(4)具有变化更新率的搜索、插入和删除操作所组成的混合 操作。\n为了与要求用于更新操作的实际内存分配的物理版本方案的 公平对比，使用了存储池以减小调用内存分配的系统开销。按照系 统中处理器的数量创建了同样数量的存储池，并且给每个线程分配 一个存储池以将内存分配争夺降到最小。\n对于每个实验，使用了允许复制键值的非唯一索引，其中索引 通过插入10兆均匀分布的4字节整数键和相关指针进行初始化。 因为实验在32位寻址模式中运行，所以每个指针的大小为4字节。 初始化后，B+-tree的高度为7，而完全CSB+-tree的高度为6。B+-tree 的大小约为140MB，而完全CSB+-tree的大小约190MB。由于 B+-tree和完全CSB+-tree利用插入操作进行初始化，所以它们充满 程度约为70％。由于当索引通过插入操作建立时，128字节的节点 具有最佳性能，所以索引节点的大小选择了128字节。\n图9A和9B显示了随节点大小的变化，使用OLFIT方案的性 能曲线。如图所示，128字节的节点大小具有最佳性能。当索引由 插入操作建立时，B+-tree和完全CSB+-tree的充满程度约为70％。 对于70％满的节点，仅存取128字节节点的前64字节块的概率很 高。\n表1为采用每个并行控制方案时，节点扇出的最大数量。TL 和VT具有最大的扇出数量，这是因为该方案不需要节点的并行控 制信息。LC和VN具有较小的扇出数量，这是因为方案在每个节 点上都需要一个锁存。OL具有最小的扇出数量，这是因为该方案 在每个节点上需要锁存、版本号、高键、以及链指针。\n  OL   LC   TL   VN   VT   B+-tree   叶   14   15   15   15   15   非叶   14   15   16   15   16   CSB+-tree   叶   14   15   15   15   15   非叶   28   29   30   29   30\n[表1]\n单纯搜索性能\n图10A和10B分别显示了将各种并行控制方案应用于B+-tree 和完全CSB+-tree的单纯搜索性能。通过改变执行搜索操作的线程 数来测量精确匹配搜索操作的吞吐量。x-轴代表执行搜索操作的线 程数量，而y-轴代表集合吞吐量。\nOLFIT(OL)方案和物理版本方案(VN，VT)的性能与无任 何并行控制(NO)的情况相似。物理版本和无并行控制之间的间 隙代表了为无用节点收集器设置专用时间戳的成本。当开始遍历 时，OL、VN、和VT将全局时间戳的值复制到专用时间戳；而当 完成遍历时，将专用时间戳的值重置为∞。\n图10B中使用CSB+-Tree的OL和NO之间的间隙要比图10A 中使用B+-tree的间隙宽，这是因为校验高键的成本不同。采用 B+-tree，由于遍历右兄弟节点和向下遍历一个子节点是相同的，所 以高键不需对非叶节点进行特殊处理。而使用CSB+-trees时，遍历 右兄弟节点和向下遍历是不同的。子节点的位置是由指向子节点组 的指针计算得出的，而右兄弟节点的位置是从当前节点的位置计算 得出的。对高键的这种特殊处理需要稍稍多花费一点时间，而使得 与物理版本方案有一段很小的间隙。\n由于对树锁存的争用，以及由持有树锁存和释放树锁存还会多 生产出两个一致锁存丢失，树级锁(TL)会随着线程数目的增大而 恶化。锁耦合(LC)的性能最差。因为要锁存多个节点，锁耦合会 生成许多一致高速缓存丢失，与无并行控制之间的间隙随线程数量 而成接近线性地变宽。\n单纯更新性能\n图11A和11B分别显示了将各种并行控制方案应用于B+-tree 和完全CSB+-tree的单纯更新性能。更新操作的吞吐量通过改变执 行更新操作的线程数目来测量。x-轴代表执行更新操作的线程数量， 而y-轴代表集合吞吐量。其中，一半操作为插入，另一半为删除。\n图11A和11B表明只有OLFIT方案(OL)显示出了可扩展性 能。由于版本的代价很高，特别是对于每次更新都必须变换整个节 点组版本的CSB+-tree，物理版本方案(VT，VN)表现出较差的更 新性能。性能结果表明：VN的更新性能略优于VT，这是因为最初 为T-tree提出的VN方案在将使其适合于B+-tree的过程中作了改 动。如果发生结构改动，VN持有一个树锁存。由于B+-tree的分裂 不同于T-tree的旋转且结构修改不需要集中的树锁存，所以消除了 VN对集中树锁存的需要。随着线程数量的增加，集中树锁存大大 降低了更新性能。\n虽然带有节点锁存(VN)和锁耦合(LC)的物理版本没有产 生优良的性能，它们的性能会随线程的增加而缓慢增加。但是，由 于存在集中树锁存的争用，随着线程数目的增加，带有树锁存(VT) 和树级锁(TL)的物理版本的性能会下降。\n不同更新率的性能\n图12A和12B显示了不同更新率的条件下，利用各种并行控 制方案，使用单线程的性能结果曲线。x轴代表执行更新操作的线 程数量，而y轴代表集合吞吐量。\n在不使用并行控制(NO)的情况下，OLFIT(OL)和树级锁 方案(TL)的性能相似。由于锁闭的开销，锁耦合(LC)显示的 性能要比OL和TL差。当更新率接近0时，两个物理版本方案(VN， VT)显示出了较好的性能，但随着更新率的增长，由于物理版本的 高开销，它们的吞吐量都会急剧下降。如图10B所示，对于 CSB+-tree，其同一父节点的各节点集中在一个连续空间中，这样版 本创建在节点组的基础上，所以其版本开销甚至更大。\n图13A和13B显示了在多处理环境中使用8个线程的性能结 果。当更新率接近0时，物理版本方案(VN，VT)的性能与OLFIT 方案(OL)的性能相当。而随着更新率的增加，OL的性能显著优 于其它并行控制方案。\n使用8个线程时，OL与其它方案的性能差距要比使用单线程 时更大。差距变大的部分原因在于其它方案产生出大量相关高速缓 存丢失，部分原因在于在TL和VT的情况中，集中的树锁存发生 争用。注意：VT的性能略优于TL的性能，但随着更新率的进一步 增加，其性能开始与TL的性能接近，并最终由于版本的高昂代价 而与TL的性能相交。\n随着更新率的增加，由于CSB+-tree具有更高的分裂代价，所 以CSB+-tree的性能比B+-tree的性能下降得更剧烈。在CSB+-tree 中，当节点分裂时，如果包括所述节点的节点组不满，则所述节点 在同一节点组中的所有右兄弟节点均向右移动，而如果节点组满 时，所述组中的一半节点被移到一个新节点组中。注意：当更新率 超过20％，由于版本的高昂代价，VN和VT的性能甚至比TL更差。\n总之，在8个CPU的多处理系统上，OLFIT几乎具有线性的 可扩展性，其中读取的可扩展性与无并行控制以及通过索引节点的 物理版本也提供无锁存遍历的现有技术的主存索引并发控制的性 能相当。\n本发明能够适用于其它的B+-tree变体，例如B-tree，B*-tree， 以及pkB-tree。虽然显示的优选实施例是针对B+-tree的变体的，但 本领域技术人员将理解：本发明的OLFIT方案可以很容易地进行调 整而适用于其它索引结构，例如T-tree、一个节点中具有许多元素 的平衡二叉树、多维索引的R-tree、CR-tree、R-tree的缓存意识版 本，和GiST(广义搜索树)，以及允许用户对任何类型数据的索引 进行开发并允许用户将其定制以表示它们本身索引结构的可扩展 数据结构。\n本发明是参照优选实施例进行描述的，但这些实施例并不会限 制本发明。本领域中的普通技术人员将理解，所述实施例的结构与 形式可以进行许多修改，而不偏离本发明的精神和范围。