内存数据库系统及实现内存数据库的方法和装置

摘要

本发明公开了一种内存数据库系统，包括通信接口、创建装置、写操作装置、查询操作装置和释放操作装置；所述创建装置用于在共享内存中建立存储数据库的描述信息的第一存储区、存储用于定位表记录的索引信息的第二存储区和存储表记录的第三存储区，以及将数据库的描述信息保存到所述第一存储区；所述第三存储区包括与表记录大小匹配的存储单元，每个存储单元存储一条数据库表记录，相同大小并且在物理空间上连续的存储单元构成一个物理块，一个物理块或多个相同的物理块关联成一个逻辑块。本发明还公开了创建内存数据库的方法、建立多索引的方法及其装置。本发明实现了内存数据库表结构与数据存储结构的松耦合，能灵活创建和管理内存数据库。

说明书

技术领域

本发明涉及计算机及通信领域的数据库技术，特别涉及一种内存数据库技术。

背景技术

目前的内存数据库是通过将系统中常用数据库表中的数据全部映射到主机共享内存中，通过使用一个固定的数据结构数组将每个固定的数据库表保存在共享内存中，也就是将内存中的一个存储区作为一个数据库表的表空间，根据表记录的实际大小将该存储区划分为多个内存块来保存数据库表中的数据；在数据库表中的关键字段上建立内存索引，通过该内存索引对关键数据进行实时访问。内存系统提供用于对内存数据库表中的数据进行修改和检索的应用编程接口API(Application Programming Interface)接口，应用程序在访问这些数据库表时，通过调用内存数据库的API来访问共享内存中的数据，而不是直接访问物理数据库表中的数据，因此，能够提高系统对关键数据的实时访问性能。

由于通过使用一个固定的数据结构数组将每个固定的数据库表保存在共享内存中，所述数据的存储和数据库表记录的结构之间耦合度较大，导致不能灵活创建和管理数据库表。例如，在内存数据库中增加数据库表时，必须修改内存数据库的底层(即需要重新编写或修改代码)；又如，在对数据库的表结构进行变更时，也需要修改内存数据库的底层。因此，现有内存数据库存储方式难以实现数据表空间的动态扩充；另外，由于采用固定的数据结构保存表记录，所以对于带有变长字段的数据库表的表空间浪费也比较严重。

发明内容

本发明实施例提供一种内存数据库系统及实现内存数据库的方法和装置，以降低内存数据库中数据存储与内存数据库的表结构之间的耦合度提高创建、管理数据库的灵活性。

一种内存数据库系统，包括：

通信接口，用于接收请求操作数据库的各种消息和输出操作结果；

创建装置，用于在共享内存中建立存储数据库的描述信息的第一存储区、存储用于定位表记录的索引信息的第二存储区和存储表记录的第三存储区，以及将数据库的描述信息保存到所述第一存储区，其中，所述第三存储区包括与表记录大小匹配的存储单元，每个存储单元存储一条数据库表记录，相同大小并且在物理空间上连续的存储单元构成一个物理块，一个物理块或多个相同的物理块关联成一个逻辑块；

写操作装置，用于在所述操作需要向数据库表中添加表记录时，查询所述描述信息以选择包含的存储单元大小与所述表记录的大小匹配的一个逻辑块，以及将表记录写入选择的逻辑块中空闲的存储单元内，并将表记录的位置信息写入到所述索引信息中；

查询操作装置，用于在所述操作需要从数据库查询表记录时，查询所述索引信息和根据查询结果从第三存储区中相应的存储单元读取表记录，并选择满足查询条件的表记录；

释放操作装置，用于在所述操作需要从数据库表删除指定的表记录时，从第三存储区释放存储所述指定的表记录的存储单元，并从第二存储区中删除所述与指定的表记录相关的索引信息。

一种创建内存数据库的方法，包括步骤：

确定数据库表结构及各数据库表中表记录的大小；

在共享内存中建立存储数据库的描述信息的第一存储区、存储用于定位表记录的索引信息的第二存储区和存储表记录的第三存储区，其中，所述第三存储区包括与表记录大小匹配的存储单元，每个存储单元存储一条数据库表记录，相同大小并且在物理空间上连续的存储单元构成一个物理块，一个物理块或多个相同的物理块关联成一个逻辑块；

将数据库的描述信息保存到所述第一存储区，所述数据库的描述信息包括各数据库表的描述信息，所述数据库表的描述信息包括各数据库表关联的所述逻辑块和各逻辑块中存储单元大小。

一种创建内存数据库的装置，包括：

确定单元，用于确定数据库表结构及各数据库表中表记录的大小；

创建单元，在共享内存中建立存储数据库的描述信息的第一存储区、存储用于定位表记录的索引信息的第二存储区和存储表记录的第三存储区，其中，所述第三存储区包括与表记录大小匹配的存储单元，每个存储单元存储一条数据库表记录，相同大小并且在物理空间上连续的存储单元构成一个物理块，一个物理块或多个相同的物理块关联成一个逻辑块；

保存单元，用于将数据库的描述信息保存到所述第一存储区，所述数据库的描述信息包括各数据库表的描述信息，所述数据库表的描述信息包括各数据库表关联的所述逻辑块和各逻辑块中存储单元大小。

一种访问内存数据库系统的方法，包括步骤：

接收操作内存数据库的请求消息；

当所述操作需要向数据库表中添加表记录时，根据该数据库表查询所述第一存储区中的描述信息以选择一个逻辑块，该逻辑块包含的存储单元大小与所述表记录的大小相匹配，并且，将所述表记录写入选择的逻辑块中空闲的存储单元内，以及在第二存储区中保存表记录的位置信息；

或者，当所述操作需要从数据库查询表记录时，根据该数据库表和查询条件中的字段查询第一存储区中的描述信息确定对应的索引信息，并且，从第二存储区查询确定的索引信息和根据查询结果从第三存储区中相应的存储单元读取表记录，选择满足所述查询条件的表记录；

或者，当所述操作需要从数据库表删除指定的表记录时，从第三存储区释放存储所述指定的表记录的存储单元，并从第二存储区中删除所述与指定的表记录相关的索引信息。

一种访问内存数据库系统的装置，所述装置包括：

逻辑块选择单元，用于在访问内存数据库系统的操作需要向数据库表中添加表记录时，根据该数据库表查询第一存储区中数据库的描述信息以选择一个逻辑块，该逻辑块包含的存储单元大小与所述表记录的大小相匹配；

写操作单元，用于将表记录写入选择的逻辑块中空闲的存储单元内，以及将存储表记录的位置信息写入到第二存储区的索引信息中。

索引信息查询单元，用于在访问内存数据库系统的操作需要从数据库查询表记录时，根据该数据库表和查询条件中的字段查询第一存储区中的描述信息确定对应的索引信息；

索引单元，用于从第二存储区查询所述索引信息查询单元确定的索引信息和根据查询结果从第三存储区中相应的存储单元读取表记录，并选择满足所述查询条件的表记录；

释放单元，用于在所述操作需要从数据库表删除指定的表记录时，从第三存储区释放存储所述指定的表记录的存储单元，并从第二存储区中删除所述与指定的表记录相关的索引信息。

一种内存数据库中建立多索引的方法，所述方法包括步骤：

在数据库表中定义多个索引字段，并在第二存储区中建立各索引字段对应的特征值表；

将数据库表的表记录存储到存储单元后，在该数据库表的各索引字段下获取所述表记录中对应的键值，并根据所述键值得到相应的特征值；

利用各特征值分别查询相应的索引字段所关联的特征值表，若特征值表中存在该特征值，则在该特征值关联的索引树上增加包含表记录位置信息的节点，否则，将所述特征值加入特征值表并创建与该特征值关联的并包含表记录位置信息的节点。

一种在内存数据库中建立多索引的装置，所述装置包括：

定义模块，用于在数据库表中定义多个索引字段，并在第二存储区中建立各索引字段对应的特征值表；

第一模块，用于根据表记录所在数据库表查询第一存储区中相应的描述信息，获得该数据库表预先定义的多个索引字段；

第二模块，用于从所述表记录中提取各索引字段对应的键值，并获得各键值对应的特征值；

第三模块，用于根据各特征值分别查询第二存储区中相应的特征值表，若特征值表中存在该特征值，则在该特征值关联的索引树上增加包含表记录位置信息的节点，否则，将特征值加入特征值表和创建与该特征值关联的包含表记录位置信息的节点。

一种利用多索引查询表记录的方法，包括步骤：

根据需要操作的数据库表和索引字段查询数据库表的描述信息确定需要查询的特征值表；

根据查询条件中的键值获得对应的特征值并查询确定的特征值表，得到该特征值关联的索引树；

搜索所述索引树中的节点和从节点关联的存储单元读取表记录，并将表记录中对应于索引字段的键值与所述查询条件比较，得到满足所述查询条件的表记录。

一种利用多索引查询表记录的装置，包括：

特征值表确定模块，用于根据需要操作的数据库表和字段查询第一存储区确定需要在第二存储区中查询的特征值表；

特征值表查询模块，用于根据查询条件中的键值获得对应的特征值并查询确定的特征值表，得到该特征值关联的索引树；

索引模块，用于搜索所述索引树中的节点和从第三存储区读取节点关联的表记录，将表记录中对应于索引字段的键值与所述查询条件比较，得到满足所述查询条件的表记录。

本发明实施例中，在共享内存中建立存储数据库的描述信息的第一存储区、存储用于定位表记录的索引信息的第二存储区和存储表记录的第三存储区，通过描述信息确定索引信息，通过索引信息确定表记录，因而实现了内存数据库表结构与数据存储结构的松耦合，可以灵活创建和管理内存数据库。在第三存储区分配与数据库表中表记录的大小相匹配的存储单元，因此，可以实现不同长度的表记录的灵活存储，从而降低共享内存的资源占用。

附图说明

图1A为本发明实施例中内存数据库的存储空间示意图；

图1B为本发明实施例中内存数据库系统的结构示意图；

图2为本发明实施例中存储单元与物理块的关系示意图；

图3A为本发明实施例中存储单元的存储结格式意图；

图3B为本发明实施例中空闲存储单元的链表结构示意图；

图4A为本发明实施例中创建内存数据库的流程图；

图4B为本发明实施例中创建内存数据库的装置结构示意图；

图4C为本发明实施例中内存数据库访问共享内存空间的关系示意；

图5A为本发明实施例中访问内存数据库的流程图；

图5B为本发明实施例中动态扩充物理块的示意图；

图6为本发明实施例中多索引结构的示意图；

图7为本发明实施例中叶子节点树的结构示意图；

图8A、图8B、图8C为本发明实施例中访问内存数据库的装置的相关结构示意图；

图9为本发明实施例中创建多索引的流程图；

图10为本发明实施例中利用多索引查询表记录的流程图；

图11为本发明实施例中创建多索引的装置的结构示意图；

图12为本发明实施例中利用多索引查询表记录的装置的结构示意图。

具体实施方式

在本发明实施例中，根据内存数据库在共享内存中的存储空间的功能，将所述存储空间划分为第一存储区、第二存储区和第三存储区，如图1A所示。其中，第一存储区存储数据库的描述信息(或称数据库系统定义信息)，第二存储区存储用于定位表记录的索引信息，第三存储区用于存储数据库表的表记录。第一存储区、第二存储区和第三存储区在物理空间上可以连续分布，也可以是非连续分布；同样的，第一存储区、第二存储区和第三存储区中的每个存储区在物理空间上可以是连续分布的，也可以是非连续分布的。

本实施例中一种内存数据库系统的结构如图1B所示，包括：通信接口10、创建装置11、写操作装置12、查询操作装置13和释放操作装置14；为了能够动态的扩充存储空间，内存数据库系统还进一步包括一个扫描装置15。

通信接口10作为数据库与外部应用进程之间的接口，用于接收访问数据库的各种消息和输出操作结果，通信接口可以包括操作界面和/或应用编程接口API；所述的操作包括增加记录、删除记录、查询记录和编辑记录等；创建装置11在共享内存中建立存储数据库的描述信息的第一存储区、存储用于定位表记录的索引信息的第二存储区和存储表记录的第三存储区，以及将数据库的描述信息保存到所述第一存储区；写操作装置12在访问数据库的操作需要向数据库表中添加表记录时，查询第一存储区中的描述信息以选择包含的存储单元大小与所述表记录的大小匹配的一个逻辑块，然后将表记录写入选择的逻辑块中空闲的存储单元内，以及将表记录的位置信息写入到第二存储区的索引信息中；查询操作装置13在访问数据库的操作需要从数据库查询表记录时，查询第二存储区的索引信息和根据查询结果从第三存储区中相应的存储单元读取表记录，并选择满足查询条件的表记录；释放操作装置14在访问数据库的操作需要删除表记录时，通过查询操作装置13定位到第三存储区中存储指定的表记录的存储单元，释放该存储单元并从第二存储区中删除该表记录的索引信息；扫描装置15扫描逻辑块中空闲的存储单元，如果发现逻辑块中空闲的存储单元小于阈值时，产生提示信息，由网管通过手动方式为逻辑块分配物理块，以保证内存数据库需要的存储空间；在保证扫描装置15能够获得共享内存空间的场景下，也可以由扫描装置15为该逻辑块分配一个物理块并将其关联到所述逻辑块。

参阅图2所示，第三存储区中包括与数据库表的表记录大小匹配的存储单元Slot，该存储单元是内存数据库的最小存储单元，每个存储单元存储一条数据库表记录。大小(即存储容量)相同并且在物理空间上连续的存储单元构成一个物理块Extent，每个物理块包含的存储单元数量可以不同；一个物理块Extent或多个相同的物理块Extent关联(或称绑定)成一个逻辑块Chunk。在本实施例中，物理块是绑定到逻辑块的基本单元。

在一个实例中，第二存储区中也可以采用类似于第三存储区的存储结构，大小(即存储容量)相同并且在物理空间上连续的存储单元构成一个物理块Extent，每个物理块包含的存储单元数量可以不同；一个物理块Extent或多个相同的物理块Extent关联(或称绑定)成一个逻辑块Chunk。这样，一个表记录的位置信息即可存储在一个存储单元Slot中。将第二存储区和第三存储区域的存储结构统一，可以简化管理和维护。在另一实例中，第二存储区域采用普通的存储结构，即按现有存储方式存储信息，例如，分配在物理空间上连续并且大小统一的存储单元存储表记录的位置信息。

在本实施例中，根据实际需要可以限定组成一个逻辑块的最大物理块数量，例如，一个逻辑块最多关联40个物理块。相应的，也可以设置物理块支持的寻址位数，以确定每个物理块包含存储单元的最大数量；例如，每个物理块支持24位寻址空间，则每个物理块最多包括16777216个(2²⁴)存储单元。

第一存储区中的数据库的描述信息包含了实现数据库功能需要的信息，例如，系统锁、存储空间的描述信息、数据库表的描述信息等；其中，系统锁在使用数据库维护进程对数据库中的数据库表进行调整(如备份和恢复表记录过程或调整表记录间的关联关系)时加载到相应的数据库表中，以防止其他应用进程访问该数据库表。存储空间的描述信息包含逻辑块的数量、各逻辑块包含的物理块数量、物理块包含的存储单元数量和存储单元的大小(即存储容量)；数据库表的描述信息包含表锁、表索引定义信息等，表索引定义信息包含构成索引的字段，各索引在第二存储区中对应的索引信息和索引锁等，其中的表锁用于防止两个进程同时对同一条记录进行修改，表索引锁可防止索引不被其他进程操作。

第二存储区中的索引信息可以采用多种索引类型，例如，数组、索引树等。索引树也可以采用多种树结构，例如，二叉树，平衡树，以及特征值表与叶子节点树。在特征值与叶子节点树结构中，索引字段对应的键值的特征值构成特征值表(特征值表中的特征值不同)，每个特征值对应一个叶子节点树，叶子节点树由存储表记录位置信息的叶子节点构成，通过遍历树上的叶子节点定位到相应的存储单元。所述特征值可以根据需要选择各种算法得到，典型的，采用哈希Hash运算。

通过数组类型组织索引信息时，可采用直线整数线性索引方式，该索引方式下索引字段采用4字节大小的整数(索引字段的键值连续并唯一)，并提供两个整数型的参数，第一个整数代表索引字段键值的最小值，第二个整数代表索引字段键值的最大值；内存数据库系统创建索引时直接把索引字段建成一个没有哈希冲突的整数数组，数据组中的每个元素指向一个存储表记录的存储单元。由于各键值是唯一的，所以可以通过直接访问函数进行快速存取。通过哈希表与叶子节点树组织索引信息时，可采用二进制字节串索引方式，该方式将被索引字段当成一个二进制字节串，并对该二进制字节串进行哈希Hash运算，该索引方式提供一个表示表大小的整数，该整数影响着哈希表中哈希值散列的效果。在本实施例中以哈希表与叶子节点树记录表记录位置信息的结构为例进行说明。

第三存储中的存储单元为内存数据库中的最小存储单位，为了方便维护和管理，一个存储单元存储的信息可由多个字段构成。如图3A所示，一个存储单元包括头信息字段和数据字段。当存储单元存储表记录后，数据字段则存储表记录内容，头信息字段可以描述表记录的所属数据库表的信息和该表记录的实际长度等。头信息字段占用的字节数根据需要存储的信息量预先确定，例如，头信息字段占用8个字节。当存储单元为空闲时，头信息可以用于存放当前逻辑块中另一个空闲存储单元的位置信息，该位置信息可以包括逻辑块标识、物理块标识和存储单元标识；这样，一个逻辑块内所有空闲存储单元通过自身的头信息连接成一个空闲链表。当需要从逻辑块中申请存储单元时，则从该空闲链表中的表头位置取出一个存储单元；当释放一个表记录时，就将对应的存储单元添加到空闲链表的尾部。在这种空闲链表结构中，指向空闲存储单元的指针始终指向链表的表头位置的空闲存储单元，由于访问和释放存储单元的时间和周期不同，所以该空闲链表在物理空间上可能不是连续的。如图3B所示的一实例中，一个逻辑块Chunk中的物理块有n个物理块Extent 1至Extent n，物理块Extent 1和物理块Extent n中有空闲存储单元，这些空闲存储单元形成空闲链表。

在第三存储区采用逻辑块、物理块和存储单元存储结构后，内存数据库的数据库表存储区域的分配可以采用多种方式。在一个实施例中，采用表绑定逻辑块方式分配数据库表的存储区域，即，将一个数据库表映射到指定的一个或多个逻辑块中，当在数据库表中增加表记录时，每次在该数据库表绑定的逻辑块中寻找空闲并且大小与表记录匹配的存储单元以存放指定的表记录。在另一个实施例中，通过表动态分配逻辑块方式分配数据库表的存储区域，即，不固定数据库表绑定的逻辑块，当在数据库表中增加表记录时，根据待存储表记录的大小选择包含的存储单元大小与表记录大小匹配的逻辑块，然后在逻辑块中选择存储单元存储表记录；如果存在多个逻辑块可供选择时，则从这些逻辑块中选择空闲空间最大的一个逻辑块存储表记录，以平衡使这些逻辑块中被占用的存储单元的数量。

由于一个数据库表可以关联到多个逻辑块，而且不同的逻辑块包含的存储单元大小可以不相同，例如，绑定在同一数据库表上的逻辑块A、B；其中逻辑块A包含的存储单元的大小为20字节，而逻辑块B包含的存储单元大小为25字节，因此，对于带有变长字段的表记录可以根据实际大小选择匹配的逻辑块，从而能够实现按表记录大小分配表存储空间，节约共享内存中数据库表的存储资源。

参阅图4A所示，本实施例中创建内存数据库的处理流程如下：

步骤400、确定数据库表结构(如，数据库表包括的字段)及各数据库表中表记录的大小。

步骤401、在共享内存中申请存储区，并在申请到的存储区中建立存储数据库的描述信息的第一存储区、存储用于定位表记录的索引信息的第二存储区和存储表记录的第三存储区。

步骤402、将数据库的描述信息保存到所述第一存储区。所述数据库的描述信息包括各数据库表的描述信息，所述数据库表的描述信息包括各数据库表关联的所述逻辑块和各逻辑块中存储单元大小。

相应的，一种创建内存数据库的装置如图4B所示，包括：确定单元40、创建单元41和保存单元42；其中，确定单元40确定数据库表结构及各数据库表中表记录的大小；创建单元41根据所述确定单元40的得到的结果，在共享内存中建立所述第一存储区、第二存储区和第三存储区；保存单元42将数据库的描述信息保存到所述第一存储区。

内存数据库创建后，内存数据库应用编程接口API实例化时会产生一个进程内的内存数据库地址映射数据结构ChunkMap，用于保存所有物理块映射到本进程后的虚拟内存地址BaseAddr，同时也记录下与逻辑块的对应关系。当内存数据库API需要定位指定的表记录或空闲的存储单元时，通过逻辑块标识ChunkId和物理块标识ExtentId，查找到物理块映射到本进行的虚拟内存地址BaseAddr，然后根据存储单元的标识Slot Id结合存储单元大小SlotSize计算出相对于虚拟内存地址BaseAddr的偏移量Offset，然后得到存储单元真实的进程虚拟内存地址RecPtr，进行数据访问。这样，实现了内存数据库程序对共享内存的访问，其关系如图4C所示。

本实施例中，每个逻辑块具有一个时间戳，逻辑块中增加物理块时更新该时间戳。内存数据库的应用进程根据逻辑块的时间戳确定已映射到本应用进程的逻辑块与第三存储区中相应的逻辑块是否同步，如果不同步则重新进行映射，以保证每个应用进程都可以访问到最新的内存数据库的存储空间。

访问内存数据库的操作类型包括对表记录的查询操作、修改(更新)操作、添加操作和删除操作，这些操作可归结为查询表记录、添加表记录和删除表记录三种操作中的一种操作或多种操作。例如，删除操作和修改操作均要先查询相应的表记录，然后再执行后续的操作。为了防止数据库的应用进程读到脏数据，对于修改表记录操作，可以在查询到相应的表记录后，先添加修改后的表记录，然后再删除原来的表记录。

参阅图5A所示，本实施例中，访问内存共享数据库的主要流程如下：

步骤500、内存数据库接收访问内存数据库的请求消息。

步骤501、确定所述访问的操作类型，若该操作需要向数据库表中添加表记录，则进行步骤502、若该操作需要定位表记录，则进行步骤504，若该操作需要删除指定的表记录，则进行步骤506。

步骤502、根据需要操作的数据库表查询所述第一存储区中的描述信息，选择包含的存储单元大小与所述表记录的大小匹配的一个逻辑块。

步骤503、将所述表记录写入选择的逻辑块中空闲的存储单元内，以及将存储表记录的位置信息记录到所述第二存储区的索引信息中，并结构该写入处理。

步骤504、根据需要操作的数据库表和查询条件中的字段查询第一存储区中的描述信息确定对应的索引信息。

步骤505、从第二存储区查询确定的索引信息和根据查询结果从第三存储区中相应的存储单元读取表记录，选择满足所述查询条件的表记录，并结束该次查询处理。

步骤506、释第三存储区中存储表记录的单元和从第二存储区中删除该表记录的索引信息，并结束该删除处理。

在步骤502中，如果逻辑块中没有空闲的存储单元，则可以进行动态扩充，即申请分配一个物理块。一个动态扩充空间的处理流程如图5B所示：

步骤550、根据物理块的大小从操作系统申请相应大小的共享内存空间。

步骤551、将申请到的物理块绑定到相应的逻辑块。

步骤552、更新第一存储区中存储空间的描述信息，如，该逻辑块的时间戳，物理块信息和存储单元信息等。

步骤553、构建逻辑块中存储单元的空闲链表。

在本实施例中，内存数据库的数据库表采用多索引方式以提高查询速度和提高数据库的整体性能，每个索引采用哈希值表与叶子节点树方式(当然也可以采用其他运算得到的特征值表)。每个数据库表具有多个索引，数据库表的一个索引可以包含该数据库表中的一个索引字段，也可以包含多个索引字段。例如，对于一个具有A(如“姓名”字段)、B、C、D、E、F 6个字段的数据库表可以有3个索引，第一个索引包含A字段，第二个索引包含B、C、D字段，第三个索引包含E、F字段。当然，根据需要可以建立4个索引或更多索引；而根据需要，其中某些字段也可以不用于建立索引。在每个索引下，表记录对应于索引字段的键值Key(一个索引由多个索引字段组成时，键值是指各索引字段的键值按预定的顺序组合成的键值。)通过哈希运算后得到的哈希值构成一个哈希表，其中的每个哈希值关联到一个由存储表记录位置信息的叶子节点构成的叶子节点树，同一叶子节点树上各叶子节点对应的表记录在对应的索引字段下，其键值产生哈希碰撞，也就是说虽然其键值不同但其经哈希运算后得到相同的哈希值，参阅图6所示。

采用多索引方式后，第一存储区中表索引定义信息具体包括：使用一个名称描述一个字段或几个字段的索引名、索引标识(如一个表中所有索引的编号)、索引属性(如键值是否唯一、索引方法和重键排序方法等)、索引表大小、索引字段(包括字段在记录中的偏移量和长度的数组)、索引参数(如哈希Hash表长、最大值、该索引所在的位置信息)、重键排序字段和索引数据叶子节点所在逻辑块标识等。

在第二存储区中，一个哈希表可以保存在一个存储单元中，由于在同一个存储单元查询哈希值，能够进一步提高索引速度和数据库的整体性能。叶子节点树上的叶子节点可以采用相同大小的存储单元存储，一个索引树上的叶子节点可以存储于同一个逻辑块包含的存储单元中，也可以分别存储在多个逻辑块包含的存储单元中。

参阅图7所示，在一个哈希值关联到的一个叶子节点树上具有第一关联关系(图7中的横向叶子节点)和第二关联关系(图7中的纵向叶子节点)。在同一索引下，第一关联关系中的叶子节点所对应的表记录的键值不同，第二关联关系中的叶子节点所对应的表记录的键值相同，而哈希表中每个非零的哈希值指向叶子节点树上第一关联关系中的头叶子节点。在叶子节点树上，每个叶子节点可以有三个指针，其中，第一个指针用于指向第一关联关系中的后继叶子节点，以形成一个链表，第二个指针用地指向第二关联关系中的后继叶子节点，以形成另一个链表，第三个指针则用于指向第三存储区中存储表记录的存储单元(图7中仅示出了哈希值1和哈希值m关联的叶子节点树，其他哈希值关系的叶子节点树未示出)。

相应的，一种访问内存数据库的装置如图8A所示，包括：逻辑块选择单元81、写操作单元82、索引信息查询单元83、索引单元84和释放单元85。其中，逻辑块选择单元81在访问内存数据库系统的操作需要向数据库表中添加表记录时，根据数据库表查询第一存储区中的描述信息来选择一个逻辑块，该逻辑块包含的存储单元大小与待在座的表记录的大小相匹配；如，对于前述包括头信息字段和数据字段的存储单元，相匹配是指数据字段大小与表记录大小一致；写操作单元82将表记录写入逻辑块选择单元81选择的逻辑块中空闲的存储单元内，并将存储表记录的位置信息(即存储单元的地址)写入到所述第二存储区的索引信息中。索引信息查询单元83在访问内存数据库系统的操作需要从数据库查询表记录时，根据该数据库表和查询条件中的字段查询第一存储区中的描述信息来确定对应的索引信息；索引单元84从第二存储区查询所述索引信息查询单元83确定的索引信息和根据查询结果从第三存储区中相应的存储单元读取表记录，并选择满足所述查询条件的表记录；释放单元85在所述操作需要从数据库表删除指定的表记录时，从第三存储区释放存储所述指定的表记录的存储单元，并从第二存储区中删除所述与指定的表记录相关的索引信息；所述指定的表记录可以是访问操作请求消息中指定的记录，如果访问操作请求消息中是删除记录的条件，则先由索引信息查询单元83和索引单元84定位到满足条件的表记录，然后再删除。

写操作单元82可包括：第一存储操作模块820和第二存储操作模块821；第一存储操作模块820从选择的一个逻辑块中获取一个空闲的存储单元，并将待存储的表记录存储到该空闲的存储单元内；第二存储操作模块821将存储表记录的位置信息记录到第二存储区的索引信息中。

在采用多索引方式的实施例中，写操作单元82中第二存储操作模块821如图8B所示，包括：第一模块8210、第二模块8211和第三模块8212；其中，第一模块8210根据表记录所在数据库表查询第一存储区中相应的描述信息，获得该数据库表预先定义的多个索引字段；第二模块8211从所述表记录中提取各索引字段对应的键值，并获得各键值对应的特征值；第三模块8212根据各哈希值分别查询第二存储区中相应的哈希值表，若特征值表中存在该哈希值，则在该哈希值关联的索引树上增加包含表记录位置信息的节点，否则，将哈希值加入哈希值表和创建与该哈希值关联的包含表记录位置信息的节点。其中，在包含第一关联关系和第二关联关系的叶子节点树上，所述第三模块8212在索引树上增加包含表记录位置信息的节点时，先在第一关联关系中搜索键值相同的表记录关联的节点，若未搜索到，则在第一关联关系上增加包含表记录位置信息的节点，若搜索到，则在该节点所在的第二关联关系上增加包含表记录位置信息的节点。

在第二关联关系上增加包含表记录位置信息的节点，可以按一定顺序进行排序插入节点，该一定顺序可以有多种，例如：按表记录插入的先后正序、按表记录插入的先后倒序、按当前索引的排序字段的大小正序或者按当前索引的排序字段的大小倒序。

在采用多索引方式时，图8A所示索引信息查询单元83和索引单元84的一种结构如图8C所示，索引信息查询单元83包括特征值表确定模块830，用于根据需要操作的数据库表和字段查询第一存储区确定需要在第二存储区中查询的哈希值表；索引单元84包括：特征值表查询模块840和索引模块841；其中，特征值表查询模块840根据所述查询条件中的键值获得对应的哈希值，并查询特征值表确定模块830确定的哈希值表，得到该哈希值关联的叶子节点树；索引模块841搜索所述索引树中的节点和从第三存储区读取节点关联的表记录，将表记录中对应于索引字段的键值与所述查询条件比较，得到满足查询条件的表记录。由于在表索引定义信息中包括索引字段在表记录中的偏移量，因此，索引模块841在选择满足查询条件的表记录时，根据所述偏移量从读取的记录中选择相应的键值与查询条件进行比较，其中的查询条件一般是该索引字段中健值需要满足的条件，如，对于一个数据库表，对于其中的索引字段“性别”而言，查询条件是：性别＝“男”，即键值为“男”；而对于其中的索引字段“员工号”而言，查询条件可以是：员工号＞123450。索引模块841在包含第一关联关系和第二关联关系的叶子节点树上搜索节点时，先在第一关联关系中搜索键值相同的表记录关联的节点，若未搜索到，则停止搜索，若搜索到，则在搜索到的节点所在的第二关联关系上依次遍历各节点。

在一个具体实例中，在第二存储区中创建多索引的主要处理流程如图9所示，包括步骤：

步骤900、在数据库表中定义多个索引字段，并在第二存储区中建立各索引字段对应的哈希值表。在初始创建时，哈希值表为空。

步骤901、将数据库表的表记录存储到存储单元后，在该数据库表的各索引字段下获取所述表记录中对应的键值。

步骤902、对各键值进行哈希运算，得到相应的哈希值。

步骤903、利用各特征值分别查询相应的索引字段所关联的哈希值表，若特征值表中存在相应的哈希值，则进行步骤904，否则，进行步骤905。

步骤904、在哈希值关联的索引树上增加包含表记录位置信息的节点，并结束该次操作。

步骤905、将哈希值加入哈希值表，创建与该哈希值关联的并包含表记录位置信息的节点。

步骤904中，在包含第一关联关系和第二关联关系的叶子节点树上搜索节点上增加包含表记录位置信息的节点时，先在第一关联关系中查询键值相同的表记录关联的节点，若未查询到，则在第一关联关系上增加包含表记录位置信息的节点，若查询到，则在该节点所在的第二关联关系上增加包含表记录位置信息的节点。

当索引字段对应的键值与叶子节点树中某节点关联的索引字段对应的键值相同时，可以按顺序在第二关联关系中进行排序插入节点，该顺序可以有多种，例如：按表记录插入的先后正序、按表记录插入的先后倒序、按当前索引的排序字段的大小正序或者按当前索引的排序字段的大小倒序。

根据第二存储区中建立的多索引查询表记录的处理流程如图10所示，包括步骤：

步骤1000、根据需要操作的数据库表和索引字段查询数据库表的描述信息确定需要查询的哈希值表。

步骤1001、对查询条件中的键值进行哈希运算获得对应的哈希值。

步骤1002、查询确定的哈希值表得到对应的索引树。

步骤1003、搜索所述索引树中的节点和从节点关联的存储单元读取表记录，并将表记录中对应于索引字段的键值与所述查询条件比较，得到满足所述查询条件的表记录。

在一个具体实例中创建多索引的装置如图11所示，包括：定义模块1100、第一模块1101、第二模块1102和第三模块1103，其中，定义模块1100在数据库表中定义多个索引字段，并在第二存储区中建立各索引字段对应的特征值表；第一模块1101根据表记录所在数据库表查询第一存储区中相应的描述信息，获得该数据库表预先定义的多个索引字段；第二模块1102从所述表记录中提取各索引字段对应的键值，并对各键值进行哈希运算获得各键值对应的哈希值；第三模块1103根据各哈希值分别查询第二存储区中相应的哈希值表，如果该哈希值表中存在相应的哈希值，则在该哈希值关联的索引树上增加包含表记录位置信息的节点，否则，将哈希值加入哈希值表和创建与该哈希值关联的包含表记录位置信息的节点。

相应的，利用多索引查询表记录的装置如图12所示，包括：特征值表确定模块1200、特征值表查询模块1201和索引模块1202，其中，特征值表确定模块1200根据需要操作的数据库表和字段查询第一存储区确定需要在第二存储区中查询的哈希值表；特征值表查询模块1201根据查询条件中的键值获得对应的特征值并查询确定的特征值表，得到该特征值关联的索引树；索引模块1202搜索所述索引树中的节点和从第三存储区读取节点关联的表记录，将表记录中对应于索引字段的键值与所述查询条件比较，得到满足所述查询条件的表记录。

本实施例中，表记录的查询功能借助于表的多索引结构实现，在通过多索引进行查询时可以保存一个游标结构到进程空间，该游标结构用于保存当前叶子节点的位置和当前叶子节点所在第二索引关系中第一个叶子节点的位置，采用游标方式实际上并没有取出全部数据，而是指向分支节点的标识指针，这样能够大幅度提高查询的速度。

在使用内存数据库应用编程接口API提供的查询函数查询表记录时，可以预先设置一个内部过滤条件对表记录进行过滤查询，该过滤条件可以采用一个三层数据结构，其中，最底层定义一个原子过滤条件，每个原子过滤条件通过记录中的偏移量和长度指定一个要判断的字段，然后指定一个运算符，再指定运算的参数，即指定一个Operator(field，para，[，para2])这样的判断条件；多个原子过滤条件进行“与”运算后组成一个第二层过滤条件；多个第二层过滤条件进行“或”运算后组成了第三层过滤条件。原子过滤条件和第二层过滤条件的最大数量可以进行限制，例如，原子过滤条件最多为8个，第二层过滤条件最多为8个。一个过滤条件的数据结构定义的实例如下：

typedef struct

{

    int or_item_num；//表示一个结构中有多少个“或”关系

    struct

    {

        int and_item_num；//表示一个结构中有多少个“与”关系

        struct

        {

            int field_offset；//定义字段偏移量

            int field_length；//定义字段长度

            int operator；//定义操作

            struct

            {

                int para_length；//参数长度

                void  *paraptr；//定义用于指向条件中的值的指针

            }op_para[2]；//定义保存运算参数值的数组

        }and_items[8]；//定义8个比较单元，比较单元之间的关系为“与”关系

    }or_items[8]；//定义8个比较单元，比较单元之间的关系为“与”关系

}t_Filter；

在本实施例中，可进一步对运算符和相应的参数进行定义，以使在进行条件判断时能够得到参数返回的值。例如：

大于运算：如果过滤条件的字段与参数进行二进制比较后，字段大于参数时返回真；

大于等于运算：如果过滤条件的字段与参数进行二进制比较后，字段大于等于参数时返回真；

等于运算：如果过滤条件的字段与参数进行二进制比较后，字段等于参数时返回真；

不等于运算：如果过滤条件的字段与参数进行二进制比较后，字段不等于参数时返回真；

小于等于运算：如果过滤条件的字段与参数进行二进制比较后，字段小于等于参数时返回真：

小于运算：如果过滤条件的字段与参数进行二进制比较后，字段小于参数时返回真：

between运算：如果过滤条件的字段与参数进行二进制比较后，字段大于等于参数1小于等于参数2时返回真。

本领域普通技术人员可以理解，实现上述实施例方法中的全部或部分步骤是可以通过程序指令相关的硬件来完成，所述的程序可以存储于一计算机可读取存储介质中，该程序在执行时，可执行图4A、图5A、图5B、图9和图10所示流程中包含的处理步骤。

本实施例中提供的内存数据库实现了内存数据库表结构与数据存储结构的松耦合，在存储表记录时，通过选取与表记录大小相匹配的逻辑块可以实现同一个表的变长记录的存储模式，降低了共享内存中表空间资源的占用；本实施例中动态扩充表空间的方式保证了内存数据库表结构与数据存储结构之间不存在耦合关系，并且，在系统通过一个内存数据库进程动态扩充表空间时，其他内存数据库应用进程更新本进程内逻辑块的时间戳与系统定义区中该逻辑志的时间戳一致，保证了内存空间映射的同步。

本实施例提供的内存数据库能够满足对数据进行大量访问的实时性要求，可应用在实时要求较高的系统中，例如，在一个实时计费系统中采用本实施例提供的内存数据库来提高系统的实时响应性能，数据库存储用户的相关信息及使用业务的计费信息。

显然，本领域的技术人员可以对本发明进行各种改动和变型而不脱离本发明的精神和范围。这样，倘若对本发明的这些修改和变型属于本发明权利要求及其等同技术的范围之内，则本发明也意图包含这些改动和变型在内。