一种数据缓存系统中的数据查询系统和数据查询方法

摘要

本发明涉及缓存技术，针对现有Memcached系统不支持多索引等缺陷，提供一种数据缓存系统和数据查询方法。数据缓存系统包括虚拟存储模块，设置在共享内存中；转发模块，用于接收搜索请求并判断其所属类型，然后转发该搜索请求；散列搜索模块，用于接收单值搜索类型的搜索请求，提取关键字，依据该关键字的类型在元数据表中查找对应的索引信息，并依据该索引信息在索引区中查找对应的散列索引链表；依据所述散列计算结果在所述子链表中查找匹配的索引，据此查找匹配的数据记录。本发明还提供了一种数据查询方法。本发明提供的技术方案支持多索引，且采用共享内存方式存储数据记录，可有效克服现有Memcached系统中存在的缺陷。

权利要求

1.一种数据缓存系统中的数据查询系统，其特征在于，用于在设置在共享内存中的虚拟存储模块中查找对应的数据记录，其中，所述虚拟存储模块包括元数据区和表数据区，所述元数据区中存储有元数据表，所述表数据区中设置有索引区和记录区，所述索引区中存储有至少一个散列索引链表和至少一个T型索引树，每一散列索引链表包含至少一个子链表，所述记录区中存储有至少一条数据记录，所述数据查询系统包括：转发模块，用于接收搜索请求并判断其所属操作类型，然后依据该搜索请求的类型转发该搜索请求；

散列搜索模块，用于：

接收转发模块转发的单值搜索类型的搜索请求，提取其中包含的关键字，依据该关键字的类型在元数据表中查找对应的索引信息，并依据该索引信息在索引区中查找对应的散列索引链表；

对关键字进行散列计算并依据找到的散列索引链表中子链表的数量对散列计算结果进行取余计算，在所述散列索引链表中查找取余计算结果对应的子链表；

依据所述散列计算结果在所述子链表中查找匹配的索引；

依据所述索引在记录区中查找匹配的数据记录并返回；

T树搜索模块，用于：

接收转发模块转发的范围搜索类型的搜索请求，提取其中包含的搜索范围；

依据所述搜索范围对应的类型在元数据表中查找对应的索引信息，并依据该索引信息在索引区中查找对应的T型索引树；

依据所述搜索范围的上边界值和下边界值在T型索引树中查找匹配的索引；

依据找到的索引在记录区中查找匹配的数据记录并返回。

2.根据权利要求1所述的数据查询系统，其特征在于，还包括：初始化模块，用于在启动时读取配置文件，据此基于共享内存创建所述虚拟存储模块。

3.根据权利要求2所述的数据查询系统，其特征在于，所述配置文件采用XML格式。

4.根据权利要求3所述的数据查询系统，其特征在于，所述散列计算为CRC 32计算。

5.一种数据缓存系统中的数据查询方法，其特征在于，用于在设置在共享内存中的虚拟存储模块中查找对应的数据记录，其中，所述虚拟存储模块包括元数据区和表数据区，所述元数据区中存储有元数据表，所述表数据区中设置有索引区和记录区，所述索引区中存储有至少一个散列索引链表和至少一个T型索引树，每一散列索引链表包含至少一个子链表，所述记录区中存储有至少一条数据记录，所述方法包括：转发步骤，包括接收搜索请求并判断其所属类型，然后依据该搜索请求的类型转发该搜索请求；

散列搜索步骤，包括：

接收转发的单值搜索类型的搜索请求，提取其中包含的关键字，依据该关键字的类型在元数据表中查找对应的索引信息，并依据该索引信息在索引区中查找对应的散列索引链表；

对关键字进行散列计算并依据找到的散列索引链表中子链表的数量对散列计算结果进行取余计算，在所述散列索引链表中查找取余计算结果对应的子链表；

依据所述散列计算结果在所述子链表中查找匹配的索引；

依据所述索引在记录区中查找匹配的数据记录并返回；

T树搜索步骤，包括：

接收转发的范围搜索类型的搜索请求，提取其中包含的搜索范围；

依据所述搜索范围对应的类型在元数据表中查找对应的索引信息，并依据该索引信息在索引区中查找对应的T型索引树；

依据所述搜索范围的上边界值和下边界值在T型索引树中查找匹配的索引；

依据找到的索引在记录区中查找匹配的数据记录并返回。

6.根据权利要求5所述的数据查询方法，其特征在于，还包括：初始化步骤，包括在启动时读取配置文件，据此基于共享内存创建所述虚拟存储模块。

7.根据权利要求6所述的数据查询方法，其特征在于，所述配置文件采用XML格式。

8.根据权利要求7所述的数据查询方法，其特征在于，所述散列计算为CRC 32计算。

说明书

一种数据缓存系统中的数据查询系统和数据查询方法

技术领域

[0001] 本发明涉及缓存技术，更具体地说，涉及一种数据缓存系统中的数据查询系统和数据查询方法。

背景技术

[0002] 为减轻数据库服务器的访问压力，大多数数据库服务器都设置有数据缓存系统。这种数据缓存系统的作用是临时存储用户经常访问的数据。如此一来，当用户再次访问已经进行了临时存储的数据时便可直接返回该数据，而无需再从数据库服务器中获取该数据，由此降低数据库服务器的负担。

[0003] 目前最为常用的一种网络数据缓存系统为Memcached系统。Memcached系统是一种分布式内存缓存系统，其采用Client/Server（客户端/服务器）结构，基于socket进行通信。Memcached系统采用键（key）、值（value）方式进行数据的缓存，不存在逻辑表的概念，所有数据均共享同一存储空间。Memcached系统使用进程内存来存储缓存的数据，如此一来，当Memcached系统的关键进程发生异常导致Memcached系统重启时，通过Memcached系统缓存的数据将会丢失。此外，Memcached没有数据表的概念，所有缓存数据共享同一存储空间，缺少逻辑上的划分，不便于数据的管理和使用。此外，Memcached系统不支持多索引，因此若希望为同一数据记录设置多个索引，则需要为该数据记录准备多个副本，存储空间浪费严重。

[0004] 因此，需要一种数据缓存系统，能够有效克服现有Memcached系统存在的上述缺陷。

发明内容

[0005] 本发明要解决的技术问题在于，针对现有Memcached系统不支持多索引等缺陷，提供一种数据缓存系统中的数据查询系统和数据查询方法。

[0006] 本发明解决其技术问题所采用的技术方案是：

[0007] 构造一种数据缓存系统中的数据查询系统，用于在设置在共享内存中的虚拟存储模块中查找对应的数据记录，其中，所述虚拟存储模块包括元数据区和表数据区，所述元数据区中存储有元数据表，所述表数据区中设置有索引区和记录区，所述索引区中存储有至少一个散列索引链表和至少一个T型索引树，每一散列索引链表包含至少一个子链表，所述记录区中存储有至少一条数据记录，所述数据查询系统包括：

[0008] 转发模块，用于接收搜索请求并判断其所属类型，然后依据该搜索请求的类型转发该搜索请求；

[0009] 散列搜索模块，用于：

[0010] 接收转发模块转发的单值搜索类型的搜索请求，提取其中包含的关键字，依据该关键字的类型在元数据表中查找对应的索引信息，并依据该索引信息在索引区中查找对应的散列索引链表；

[0011] 对关键字进行散列计算并依据找到的散列索引链表中子链表的数量对散列计算结果进行取余计算，在所述散列索引链表中查找取余计算结果对应的子链表；

[0012] 依据所述散列计算结果在所述子链表中查找匹配的索引；

[0013] 依据所述索引在记录区中查找匹配的数据记录并返回；

[0014] T树搜索模块，用于：

[0015] 接收转发模块转发的范围搜索类型的搜索请求，提取其中包含的搜索范围；

[0016] 依据所述搜索范围对应的类型在元数据表中查找对应的索引信息，并依据该索引信息在索引区中查找对应的T型索引树；

[0017] 依据所述搜索范围的上边界值和下边界值在T型索引树中查找匹配的索引；

[0018] 依据找到的索引在记录区中查找匹配的数据记录并返回。

[0019] 在本发明提供的数据查询系统中，还包括：

[0020] 初始化模块，用于在启动时读取配置文件，据此基于共享内存创建所述虚拟存储模块。

[0021] 在本发明提供的数据查询系统中，所述配置文件采用XML格式。

[0022] 在本发明提供的数据查询系统中，所述散列计算为CRC 32计算。

[0023] 本发明还提供了一种数据缓存系统中的数据查询方法，用于在设置在共享内存中的虚拟存储模块中查找对应的数据记录，其中，所述虚拟存储模块包括元数据区和表数据区，所述元数据区中存储有元数据表，所述表数据区中设置有索引区和记录区，所述索引区中存储有至少一个散列索引链表和至少一个T型索引树，每一散列索引链表包含至少一个子链表，所述记录区中存储有至少一条数据记录，所述方法包括：

[0024] 转发步骤，包括接收搜索请求并判断其所属类型，然后依据该搜索请求的类型转发该搜索请求；

[0025] 散列搜索步骤，包括：

[0026] 接收转发的单值搜索类型的搜索请求，提取其中包含的关键字，依据该关键字的类型在元数据表中查找对应的索引信息，并依据该索引信息在索引区中查找对应的散列索引链表；

[0027] 对关键字进行散列计算并依据找到的散列索引链表中子链表的数量对散列计算结果进行取余计算，在所述散列索引链表中查找取余计算结果对应的子链表；

[0028] 依据所述散列计算结果在所述子链表中查找匹配的索引；

[0029] 依据所述索引在记录区中查找匹配的数据记录并返回；

[0030] T树搜索步骤，包括：

[0031] 接收转发的范围搜索类型的搜索请求，提取其中包含的搜索范围；

[0032] 依据所述搜索范围对应的类型在元数据表中查找对应的索引信息，并依据该索引信息在索引区中查找对应的T型索引树；

[0033] 依据所述搜索范围的上边界值和下边界值在T型索引树中查找匹配的索引；

[0034] 依据找到的索引在记录区中查找匹配的数据记录并返回。

[0035] 在本发明提供的数据查询方法中，还包括：

[0036] 初始化步骤，包括在启动时读取配置文件，据此基于共享内存创建所述虚拟存储模块。

[0037] 在本发明提供的数据查询方法中，所述配置文件采用XML格式。

[0038] 在本发明提供的数据查询方法中，所述散列计算为CRC 32计算。

[0039] 实施本发明的技术方案，具有以下有益效果：在本发明提供的数据缓存系统中的数据查询系统和数据查询方法中，缓存的数据记录存储在共享内存中。如此一来，当缓存系统的关键进程发生异常导致进程重启时，存储在共享内存中的数据记录仍然可用。此外，本发明提供的技术方案将共享内存划分为元数据区和表数据区，元数据区中存储有元数据表，表数据区中设置有索引区和记录区，索引区中存储有多个散列索引链表，每一散列索引链表包含多个子链表，记录区中存储有多条数据记录，如此一来便可方便进行数据的管理和使用。同时，索引区中存储有多个散列索引链表，由此便可实现通过多种索引对同一数据记录进行查询。同理，索引区中还存储有多个T型索引树，如此一来便可实现范围搜索。同时，T型索引树可依据索引的类型来设置，由此便可实现通过多种索引对同一数据记录进行查询。

附图说明

[0040] 下面将结合附图及实施例对本发明作进一步说明，附图中：

[0041] 图1是依据本发明一较佳实施例的数据缓存系统的逻辑结构示意图；

[0042] 图2是依据本发明一较佳实施例的虚拟存储模块的逻辑结构示意图。

具体实施方式

[0043] 为了使本发明的目的、技术方案及优点更加清楚明白，以下结合附图及实施例，对本发明进行进一步详细说明。应当理解，此处所描述的具体实施例仅仅用以解释本发明，并不用于限定本发明。

[0044] 本发明提供了一种数据缓存系统中的数据查询系统和数据查询方法。在本发明提供的技术方案中，缓存的数据记录存储在共享内存中。如此一来，当缓存系统的关键进程发生异常导致进程重启时，存储在共享内存中的数据记录仍然可用。此外，本发明提供的技术方案将共享内存划分为元数据区和表数据区，元数据区中存储有元数据表，表数据区中设置有索引区和记录区，索引区中存储有多个散列索引链表，每一散列索引链表包含多个子链表，记录区中存储有多条数据记录，如此一来便可方便进行数据的管理和使用。同时，索引区中存储有多个散列索引链表，由此便可实现通过多种索引对同一数据记录进行查询。同理，索引区中还存储有多个T型索引树，如此一来便可实现范围搜索。同时，T型索引树可依据索引的类型来设置，由此便可实现通过多种索引对同一数据记录进行查询。下面就结合附图和具体实施例来对本发明的技术方案进行详细描述。

[0045] 图1是依据本发明一较佳实施例的数据缓存系统100的逻辑结构示意图。如图1所示，数据缓存系统100包括虚拟存储模块102、转发模块104、散列搜索模块106、T树搜索模块108（可选的）和初始化模块110。

[0046] 虚拟存储模块102设置在共享内存中，其由共享内存构建，用于存储缓存的数据记录。通过采用共享内存构建虚拟存储模块，可在数据缓存系统100的关键进程出现异常导致进程重启时，达到缓存的数据不会丢失的目的。

[0047] 本发明提供的技术方案使用基于双向链表的内存管理技术，来管理进程间共享内存的动态分配和释放。初始进程根据内存表配置信息向系统申请指定大小共享内存，并创建内存分配逻辑单元，包括内存分配管理信息以及上下节点指针，内存管理单元以双向链表的形式进行链接，使系统在内存释放时可以快速释放并进行空闲内存合并。基于共享内存的缓存技术解除了数据与管理进程的捆绑关系，使内存数据可以独立于管理进程而存在，不会出现在进程退出而导致数据丢失的问题，同时共享内存允许多进程同时访问，为提高系统吞吐量提供了基础。

[0048] 虚拟存储模块102包括元数据区和表数据区，元数据区中存储有元数据表，表数据区中设置有索引区和记录区。索引区中存储有至少一个散列索引链表，每一散列索引链表包含至少一个子链表，记录区中存储有至少一条数据记录。虚拟存储模块102的构成如图2所示。

[0049] 在具体实现过程中，虚拟存储模块102由初始化模块110构建。

[0050] 初始化模块110用于在启动时读取配置文件，据此借助共享内存创建虚拟存储模块102。

[0051] 在具体实现过程中，上述配置文件采用XML格式。配置文件的具体实例如下：

[0052]

[0053]

[0054]

[0055]

[0056] 使用者可以定义表的名称（″table″）、类型（″type″）、存储所需共享内存大小（″storage″）、初始数据加载方式（″initloa d″）、列信息（″column″）、索引信息（″index″）以及记录淘汰机制(″aging″)等，内存表的初始化方法将解析此配置信息以创建虚拟存储模块102中的各种数据区和数据表。

[0057] 在本发明提供的技术方案中，对于记录区中存储的每一条数据记录，都可以为其建立多个索引。为便于描述，将这种索引定义为原始索引。例如，若数据记录为书目信息，则可分别依据书名、出版时间、价格、出版社等多种书目属性构建原始索引。在具体实现过程中，为便于进行匹配计算，需要对为每条数据记录构建的原始索引进行散列计算，以计算结果作为对应数据记录的索引。为便于描述，将这种经过散列计算得到的索引定义为散列索引。如此一来，便可依据为每条数据记录生成的散列索引构建散列索引链表。作为可选的，在散列索引链表中，各个数据记录的散列索引可依据散列结果的大小进行排序。

[0058] 当数据记录数量较多时，散列索引链表将十分庞大。为加快检索，可将散列索引链表划分为多个子链表（即散列桶）。这样一来，便可对关键字进行散列计算，并依据散列索引链表中子链表的数量对散列计算结果进行取余计算，确定所要查找的索引所在的子链表。

[0059] 在具体实现过程中，上述散列计算可以是例如但不限于CRC 32计算。

[0060] 本领域的技术人员应当明白，散列计算难免出现碰撞。例如，若对书目序号进行散列计算并以计算结果作为索引，则可能存在不同书目序号经散列计算得到同一散列计算结果的可能。如此一来，散列索引链表中将存在多个相同的索引，但这些相同的索引却对应不同的数据记录。在具体应用过程中，数据记录的数量越庞大，碰撞发生的可能性就越大。为解决这一问题，在本发明提供的技术方案中，在记录区中，每一数据条目中附加有上文所述的原始索引。以上述书目序号为例，每一数据条目中将附加有该书目的书目序号。这样一来，在通过散列索引查找到对应的多个数据记录后，便可通过将关键字与原始索引进行比较的方法，确定关键字对应的数据记录。

[0061] 转发模块104用于接收搜索请求并判断其所属类型，然后依据该搜索请求的类型转发该搜索请求。在本发明提供的技术方案中，不仅可以进行单值检索，也可进行范围检索。因此搜索请求可包括单值搜索类型和范围搜索类型。

[0062] 散列搜索模块106用于执行如下操作：

[0063] 接收转发模块104转发的单值搜索类型的搜索请求，提取其中包含的关键字（例如书目序号100019），依据该关键字的类型（即书目序号）在元数据表中查找对应的索引信息，并依据该索引信息在索引区中查找对应的散列索引链表。例如，若关键字的类型为上文所述的书目序号，则在元数据表中查找书目序号所对应的索引信息，然后依据该索引信息在索引区中查找书目序号对应的散列索引链表。

[0064] 对关键字进行散列计算并依据找到的散列索引链表中子链表的数量对散列计算结果进行取余计算，在所述散列索引链表中查找取余计算结果对应的子链表。

[0065] 依据散列计算结果在上述子链表中查找匹配的散列索引。

[0066] 依据找到的散列索引在记录区中查找匹配的数据记录并返回。如上文所述，当通过散列索引查找到的数据记录不止一条时，需要以关键字作为原始索引在找到的数据记录中查找包含该关键字的数据记录并返回。

[0067] 在本发明提供的技术方案中，输入的关键字还可不止一个。在这种情况下，可将这些关键字拼成一个字符串，各关键字之间以预先设置的分隔符例如‘|’分隔。在查找过程中，对于字符串中的每一关键字，散列搜索模块106都将执行上述操作。因此，对于每一关键字，都将得到由多条数据记录组成的记录集合。散列搜索模块106在对每一关键字都执行上述操作之后，通过计算所得到的各个记录集合的交集，便可得到想要的数据记录。

[0068] 在本发明提供的技术方案中，在插入数据记录时，需要依据待插入数据记录的散列索引的大小，将该散列索引插入对应散列索引链表中对应子链表中的适当位置。而对应的数据记录只需插入对应数据链表的尾部即可。

[0069] 而在删除操作时，需要同时更新对应的散列索引链表。

[0070] 在本发明提供的技术方案中，索引区中还存储有至少一个T型索引树，此时数据缓存系统100还包括：

[0071] T树搜索模块，用于：

[0072] 接收转发模块104转发的范围搜索类型的搜索请求，提取其中包含的搜索范围；

[0073] 依据所述搜索范围对应的类型在元数据表中查找对应的索引信息，并依据该索引信息在索引区中查找对应的T型索引树；

[0074] 依据所述搜索范围的上边界值和下边界值在T型索引树中查找匹配的索引；

[0075] 依据找到的索引在记录区中查找匹配的数据记录并返回。

[0076] T-Tree（T树）为一棵平衡二叉树，每个节点上保存多个元素（索引），因此比B-Tree（B树）树有更高的更新和存储效率。

[0077] 如上文所述，在具体实现过程中，对于记录区中存储的每一条数据记录，都可以为其建立多个索引。例如，若数据记录为书目信息，则可分别依据出版时间、价格等多种书目属性构建索引。各条数据记录的相同类型的索引构成一棵T型索引树，因此在为数据记录构建多个索引的情况下，索引区中可存在多棵T型索引树。由此一来，用户便可通过多种索引来查找想要的数据记录。T型索引树中的每个节点都包含从小到大排列的多个索引。每一索引都对应一个T链表，该T链表中的每个节点对应记录区中的一条数据记录，同一T链表中各节点所指向的数据记录的对应索引均相同。

[0078] T型索引树用于进行范围查找，也支持多列索引（可以根据部分列进行查找，比如索引列为C1、C2、C3，可以根据C1、C1和C2进行查找）。

[0079] 对于单列索引，T型索引树中每一节点中各索引所各自指向的T链表中的各个节点对应记录区中的具体数据记录。

[0080] 对于多列索引，T型索引树体现为多个T型索引树的级联。第一列树的节点指向以第二列索引建立的T型索引树，第二列树的节点又指向以下一列索引建立的T型索引树，这样直到最后一列，最后一列树的节点中各索引所各自指向的T链表中的各个节点对应记录区中的具体数据记录。

[0081] T型索引树的查找按照如下方式进行：

[0082] 单树的查找方法如下：

[0083] 1、查找总是从根节点开始。

[0084] 2、如果输入关键字小于当前节点中包含的最小索引，则递归查询左子树；如果大于当前节点中包含的最大索引，则递归查询右子树；否则在当前节点中进行二分查找。

[0085] 3、遍历查找到的索引，其所指向的T链表中的各个节点所指向的数据记录作为一个列表返回。

[0086] 4、对于范围查找，分别基于搜索范围的上边界值和下边界值，依照步骤1至3查找对应的索引，并依据各条索引查找对应的数据记录。

[0087] 多列索引树的查找方法如下：

[0088] 1、根据第一索引列的关键字查找第二列索引树，如果查找到，则根据第二索引列的关键字在第二列索引树中查找第三列索引树，如此类推，直到找到最后一列索引树为止。

[0089] 2、如果在查找第N列索引树时失败，则返回失败。

[0090] 3、如果找到最后一列索引树，则使用最后一列索引列的关键字在最后一列索引树中查找，查找到后返回对应的数据记录列表。如果是使用部分索引列进行查找，则在最后一列索引树中查找到的节点仍然是索引树，需要遍历该索引树返回的所有数据记录。

[0091] T型索引树的插入按照如下方式进行：

[0092] 单树的插入算法如下：

[0093] 1、插入总是从根节点开始。

[0094] 2、如果输入关键字小于当前节点中包含的最小索引、当前节点没有左子树且当前节点没有满，则在当前节点中插入新索引（即该关键字）；如果输入关键字小于当前节点中包含的最小元素、当前节点有左子树且当前节点已满，则在左子树中递归插入新索引（即该关键字）（如果没有左子树，则创建左子树），并且进行平衡，平衡算法与AVL树相同。

[0095] 3、如果输入关键字大于当前节点中包含的最大索引、当前节点没有右子树且当前节点没有满，则在当前节点中插入新索引（即该关键字）；如果输入关键字大于当前节点中包含的最大索引、当前节点有右子树且当前节点已满，则在右子树中递归插入新索引（即该关键字）（如果没有右子树，则创建右子树），并且进行平衡，平衡算法跟AVL树相同。

[0096] 4、如果输入关键字大于等于当前节点中包含的最小索引且小于等于最大索引，则在当前节点中二分查找输入的关键字，如果存在，则在该关键字对应的T链表尾部增加新的节点，并将对应的数据记录插入记录区；如果不存在，则判断该节点上的索引数是否满，如果没满，则插入到该节点中；如果满了，则删除最小索引，将最小索引递归插入到当前子树中。

[0097] 多列索引树的插入算法如下：

[0098] 1、根据第一索引列的关键字查找第二列索引树，如果查找到，则根据第二索引列的关键字在第二列索引树中查找第三列索引树，如此类推，直到找到最后一列索引树为止。如果在查找第N列索引树时失败，则新建一棵索引树作为第N列索引树，并在前一列索引树中插入新节点，新节点指向新建索引树根节点，然后新建第N+1列索引树，直到新建最后一列索引树为止。

[0099] 2、在最后一列索引树上插入新节点，新节点指向新分配的数据节点。T型索引树的删除

[0100] 1、删除总是从根节点开始。

[0101] 2、如果输入关键字小于当前节点中包含的最小索引，则在左子树中递归删除，如果在左子树中删除了树节点，则需要重新平衡左子树。

[0102] 3、如果输入关键字大于当前节点中包含的最大索引，则在右子树中递归删除，如果在右子树中删除了树节点，则需要重新平衡右子树。

[0103] 4、如果输入关键字大于等于当前节点中包含的最小索引且小于等于最大索引，则在当前节点中二分查找输入关键字，如果不存在，则返回删除失败；如果存在，则删除该索引。

[0104] 5、删除索引后，如果当前节点为空，则删除当前节点。

[0105] 6、删除索引后，如果当前节点为half-leaf节点（左子树或右子树为叶子节点），则将叶子节点合并到当前节点，如果叶子节点合并后还有索引，则继续保留该叶子节点，否则删除叶子节点，重新平衡当前节点。

[0106] 7、删除索引后，如果当前节点不是half-leaf节点且当前节点中包含的索引数小于下限值，则将右子树中的最小叶子节点或half-leaf节点中包含的最小索引移到本节点中，重新平衡当前节点。

[0107] 8、返回删除元素指向的所有数据记录。

[0108] T型索引树的生成

[0109] 1、从待插入数据记录中取到索引列的值作为T型索引树的索引，利用Google protocol buffers对数据记录序列化，并在共享内存表记录区中分配数据节点，然后逐条记录插入到T型索引树中。

[0110] 2、如果为单列索引，则直接插入到T型索引树中，节点中的各个索引指向新分配的数据记录。

[0111] 3、如果为多列索引，则根据第一索引列的关键字查找第二列索引树，如果查找到，则根据第二索引列的关键字在第二列索引树中查找第三列索引树，如此类推，直到找到最后一列索引树为止。如果在查找第N列索引树时失败，则新建一棵索引树作为第N列索引树，并在前一列索引树中插入新节点，新value节点中的各个索引指向新建索引树根节点，然后新建第N+1列索引树，直到新建最后一列索引树为止。

[0112] 4、在最后一列索引树上插入新节点，新节点中的各个索引指向新分配的数据记录。

[0113] 由Google公司提供的开源工具protocol buffers是一个灵活、高效的对结构化数据进行序列化的自动化工具，相比xml，它更小、更灵活、更简单，在老的数据不做修改的前提下，可以对现有已经定义并使用的数据结构进行扩充，且不会影响现有数据。本发明使用protocal buffers的自解析以及编码功能保存内存表记录，在插入记录时，本发明首先从元数据区获取当前表的定义信息，然后根据定义信息对待插入数据记录进行protocol buffers编码，在查询返回结果集记录时，应用程序可以根据表定义信息对查询返回的记录集进行反序列化，由于protocol buffer编解码能力表现较好，且对数据有一定的压缩功能，使用它既不会对性能产生较大影响而且还节省内存空间。

[0114] 本发明还提供了一种数据查询方法，用于在设置在共享内存中的虚拟存储模块中查找对应的数据记录，其中，所述虚拟存储模块包括元数据区和表数据区，所述元数据区中存储有元数据表，所述表数据区中设置有索引区和记录区，所述索引区中存储有至少一个散列索引链表，每一散列索引链表包含至少一个子链表，所述记录区中存储有至少一条数据记录。上述虚拟存储模块在初始化步骤中构建，该初始化步骤包括在启动时读取配置文件，据此基于共享内存创建所述虚拟存储模块。如上文所述，配置文件可采用例如但不限于XML格式。有关配置文件的内容已经在前文做了清楚的描述，因此此处不再赘述。

[0115] 本发明提供的数据查询方法包括：

[0116] 转发步骤，包括接收搜索请求并判断其所属类型，然后依据该搜索请求的类型转发该搜索请求；

[0117] 散列搜索步骤，包括：

[0118] 接收转发的单值搜索类型的搜索请求，提取其中包含的关键字，依据该关键字的类型在元数据表中查找对应的索引信息，并依据该索引信息在索引区中查找对应的散列索引链表；

[0119] 对关键字进行散列计算并依据找到的散列索引链表中子链表的数量对散列计算结果进行取余计算，在所述散列索引链表中查找取余计算结果对应的子链表；在具体实现过程中，散列计算可采用例如但不限于CRC 32计算。

[0120] 依据所述散列计算结果在所述子链表中查找匹配的索引；

[0121] 依据所述索引在记录区中查找匹配的数据记录并返回。如上文所述，[0122] 当通过散列索引查找到的数据记录不止一条时，需要以关键字作为原始索引在找到的数据记录中查找包含该关键字的数据记录并返回。

[0123] 在具体实现过程中，索引区中还存储有至少一个T型索引树，所述方法还包括：

[0124] T树搜索步骤，包括：

[0125] 接收转发的范围搜索类型的搜索请求，提取其中包含的搜索范围；

[0126] 依据所述搜索范围对应的类型在元数据表中查找对应的索引信息，并依据该索引信息在索引区中查找对应的T型索引树；

[0127] 依据所述搜索范围的上边界值和下边界值在T型索引树中查找匹配的索引；

[0128] 依据找到的索引在记录区中查找匹配的数据记录并返回。

[0129] 以上所述仅为本发明的较佳实施例而已，并不用以限制本发明，凡在本发明的精神和原则之内所作的任何修改、等同替换和改进等，均应包含在本发明的保护范围之内。