CN104424222B - 数据库索引方法及装置 - Google Patents

Abstract

本发明实施例提供一种数据库索引方法及装置，该数据库索引方法，包括通过数据库接收数据库操作请求，并根据数据库操作请求，在数据库中对待操作关键值进行索引操作，其中，该数据库采用T‑Tree数据结构，并且T‑Tree中的每个节点采用二叉树结构存储各关键值，从而在对数据库中对待操作关键值进行索引操作时，可以根据数据库采用的T‑Tree数据结构、以及T‑Tree中的每个节点的二叉树结构，进行索引操作，进而提高数据库中进行索引的效率。

Description

数据库索引方法及装置

技术领域

本发明涉及计算机技术，尤其涉及一种数据库索引方法及装置。

背景技术

内存数据库中的工作数据是常驻内存的数据，处理前不需要从磁盘读取数据，处理后也不需要将结果写回磁盘，从而节省了磁盘输入输出I/O的时间。

在内存数据库中，使用比较广泛的是T-Tree算法，其中，T-Tree节点的数据都是紧密存储的，可以保存在一个数组中。当在中间插入一个新的数据时，必须将数组中的多个数据进行连续搬移，为新的数据腾出空间。并且，当向一个已满的节点中插入新的数据时，如果数据要插入中间位置，必须先将节点中最小的数据插入当前节点的左分支，即前溢；或者将节点中最大的数据插入当前节点的右分支中，即后溢。

然而，T-Tree算法中插入数据时，通常采用递归操作，需要进行大量数据的搬移，从而造成在数据库中索引的效率不高。

发明内容

本发明提供一种数据库索引方法及装置，用以提高数据库中索引的效率。

本发明的第一个方面是提供一种数据库索引方法，包括：

接收数据库操作请求；

根据所述数据库操作请求，在数据库中对待操作关键值进行索引操作，其中，所述数据库采用T-Tree数据结构，且所述T-Tree中的每个节点采用二叉树结构存储各所述关键值，所述二叉树的每个键值点至多连接一个左孩子键值点和一个右孩子键值点，所述左孩子键值点中存储的关键值小于所述右孩子键值点中存储的关键值。

在第一种可能的实现方式中，所述T-Tree中的每个节点分别设置有一个前键值指针和一个后键值指针，所述前键值指针用于指向所述节点中最小关键值的位于前邻居节点中的前邻居键值点，所述后键值指针用于指向所述节点中最大关键值的位于后邻居节点中的后邻居键值点。

结合第一个方面的第一种可能的实现方式，在第二种可能的实现方式中，所述T-Tree每个节点分别设置有一个左孩子指针和一个右孩子指针，所述左孩子指针用于指向所述节点的左孩子节点，所述右孩子指针用于指向所述节点的右孩子节点。

结合第一个方面的第二种可能的实现方式，在第三种可能的实现方式中，所述T-Tree每个节点的所述前键值指针和所述左孩子指针复用相同的第一比特位，且节点中还设置有第一指针标志位，用于标识所述第一比特位当前为前键值指针或左孩子节点；

所述T-Tree每个节点的所述后键值指针和所述右孩子指针复用相同的第二比特位，且节点中还设置有第二指针标志位，用于标识所述第二比特位当前为后键值指针或右孩子节点。

结合第一个方面至第一个方面的第三种可能的实现方式中的任意一种实现方式中，在第四种可能的实现方式中，根据所述数据库操作请求，在索引数据库中对待操作关键值进行索引操作包括：

当所述数据库操作请求为数据库插入请求时，根据待操作关键值查找对应的插入位置，并在插入位置存在关键值时，通过搬移关键值将所述待操作关键值插入所述插入位置。

结合第一个方面的第四种可能的实现方式，在第五种可能的实现方式中，当所述数据库操作请求为数据库插入请求时，根据待操作关键值查找对应的插入位置，并在插入位置存在关键值时，通过搬移关键值将所述待操作关键值插入所述插入位置包括：

步骤11、根据数据库插入请求确定待操作关键值，并确定所述T-Tree的根节点为待插入的当前节点；

步骤12、比较所述待操作关键值是否小于所述当前节点的最小关键值，若是，则执行步骤21，若否，则执行步骤13；

步骤13、比较所述待操作关键值是否大于所述当前节点的最大关键值，若是，则执行步骤31，若否，则执行步骤14；

步骤14、在所述当前节点中查找所述待操作关键值对应的插入位置；

步骤15、判断所述当前节点是否为满节点，若否，则通过搬移所述当前节点内的键值将待操作关键值插入所述插入位置，结束操作，若是，则执行步骤16；

步骤16、将当前节点的最小关键值搬移到所述前键值指针指向的所述前邻居键值点，或将最大关键值搬移到所述后键值指针指向的所述后邻居键值点，通过搬移当前节点内的所述最小关键值或是所述最小关键值将所述待操作关键值插入所述插入位置，且将搬移的所述最小关键值或最大关键值作为新的待操作关键值，将所述前邻居键值点或所述后邻居键值点更新为当前节点，返回执行步骤12；

步骤21、判断当前节点的所述左孩子指针的指向是否为空，若是，则执行步骤23，若否，则执行步骤22；

步骤22、将所述当前节点的左孩子节点作为当前节点，返回执行步骤12；

步骤23、判断所述当前节点存储的关键值个数是否小于预设值，若是，则执行步骤25，若否，则执行步骤24；

步骤24、创建所述当前节点的所述前键值指针指向的所述前邻居键值点为左孩子节点，并将所述左孩子节点插入所述当前节点的双向链表中，将所述左孩子节点作为当前节点；

步骤25、将所述待操作关键值插入所述当前节点中的空键值点，结束操作；

步骤31、判断当前节点的所述右孩子指针的指向是否为空，若是，则执行步骤33，若否，则执行步骤32。

步骤32、将所述当前节点的右孩子节点作为当前节点，返回执行步骤12；

步骤33、判断所述当前节点存储的关键值个数是否小于所述预设值，若是，则执行步骤35，若否，则执行步骤34；

步骤34、创建所述当前节点的所述后键值指针指向的所述后邻居键值点为右孩子节点，并将所述右孩子节点插入所述当前节点的双向链表中，将所述右孩子节点作为当前节点；

步骤35、将待操作关键值插入当前节点中的空键值点，结束操作。

结合第一个方面的第一种可能的实现方式至第一个方面的第三种可能的实现方式的任意一种实现方式中，在第六种可能的实现方式中，根据所述数据库操作请求，在索引数据库中对待操作关键值进行索引操作包括：

当所述数据库操作请求为数据库删除请求时，根据待操作关键值查找对应的删除位置；

将删除位置的关键值删除，且通过搬移所述当前节点内的关键值更新所述当前节点的二叉树；

当判断所述当前节点更新后的二叉树各键值点均为空时，删除所述当前节点；

根据更新后的二叉树，更新当前节点的前邻居节点中的后键值指针或后邻居节点中的前键值指针。

结合第一个方面的第一种可能的实现方式至第一个方面的第三种可能的实现方式的任意一种实现方式中，在第七种可能的实现方式中，根据所述数据库操作请求，在索引数据库中对待操作关键值进行索引操作包括：

当所述数据库操作请求为数据库查找请求时，根据所述待操作关键值中的查找下限值和查找上限值分别查找对应的下限值位置和上限值位置；

根据所述节点中的所述前键值指针和所述后键值指针，读取所述上限值和下限值之间的所有关键值。

第二个方面，本发明实施例提供一种数据库索引装置，包括：

接收模块，用于接收数据库操作请求；

处理模块，用于根据所述数据库操作请求，在数据库中对待操作关键值进行索引操作，其中，所述数据库采用T-Tree数据结构，且所述T-Tree中的每个节点采用二叉树结构存储各所述关键值，所述二叉树的每个键值点至多连接一个左孩子键值点和一个右孩子键值点，所述左孩子键值点中存储的关键值小于所述右孩子键值点中存储的关键值。

在第一种可能的实现方式中，所述T-Tree每个节点分别设置有一个前键值指针和一个后键值指针，所述前键值指针用于指向所述节点中最小关键值的位于前邻居节点中的前邻居键值点，所述后键值指针用于指向所述节点中最大关键值的位于后邻居节点中的后邻居键值点。

结合第二个方面的第一种可能的实现方式，在第二种可能的实现方式中，所述T-Tree每个节点分别设置有一个左孩子指针和一个右孩子指针，所述左孩子指针用于指向所述节点的左孩子节点，所述右孩子指针用于指向所述节点的右孩子节点。

结合第一个方面的第二种可能的实现方式，在第三种可能的实现方式中，所述T-Tree每个节点的所述前键值指针和所述左孩子指针复用相同的第一比特位，且节点中还设置有第一指针标志位，用于标识所述第一比特位当前为前键值指针或左孩子节点；

所述T-Tree每个节点的所述后键值指针和所述右孩子指针复用相同的第二比特位，且节点中还设置有第二指针标志位，用于标识所述第二比特位当前为后键值指针或右孩子节点。

结合第二个方面至第二个方面的第三种可能的实现方式中的任意一种实现方式中，在第四种可能的实现方式中，当所述数据库操作请求为数据库插入请求时，

所述处理模块，具体用于根据待操作关键值查找对应的插入位置，并在插入位置存在关键值时，通过搬移关键值将所述待操作关键值插入所述插入位置。

结合第二个方面的第四种可能的实现方式，在第五种可能的实现方式中，当所述数据库操作请求为数据库插入请求时，

所述处理模块，具体用于根据待操作关键值查找对应的插入位置，并在插入位置存在关键值时，通过搬移关键值将所述待操作关键值插入所述插入位置包括：

步骤11、根据数据库插入请求确定待操作关键值，并确定所述T-Tree的根节点为待插入的当前节点；

步骤12、比较所述待操作关键值是否小于所述当前节点的最小关键值，若是，则执行步骤21，若否，则执行步骤13；

步骤13、比较所述待操作关键值是否大于所述当前节点的最大关键值，若是，则执行步骤31，若否，则执行步骤14；

步骤14、在所述当前节点中查找所述待操作关键值对应的插入位置；

步骤15、判断所述当前节点是否为满节点，若否，则通过搬移所述当前节点内的键值将待操作关键值插入所述插入位置，结束操作，若是，则执行步骤16；

步骤16、将当前节点的最小关键值搬移到所述前键值指针指向的所述前邻居键值点，或将最大关键值搬移到所述后键值指针指向的所述后邻居键值点，通过搬移当前节点内的所述最小关键值或是所述最小关键值将所述待操作关键值插入所述插入位置，且将搬移的所述最小关键值或最大关键值作为新的待操作关键值，将所述前邻居键值点或所述后邻居键值点更新为当前节点，返回执行步骤12；

步骤21、判断当前节点的所述左孩子指针的指向是否为空，若是，则执行步骤23，若否，则执行步骤22；

步骤22、将所述当前节点的左孩子节点作为当前节点，返回执行步骤12；

步骤23、判断所述当前节点存储的关键值个数是否小于预设值，若是，则执行步骤25，若否，则执行步骤24；

步骤24、创建所述当前节点的所述前键值指针指向的所述前邻居键值点为左孩子节点，并将所述左孩子节点插入所述当前节点的双向链表中，将所述左孩子节点作为当前节点；

步骤25、将所述待操作关键值插入所述当前节点中的空键值点，结束操作；

步骤31、判断当前节点的所述右孩子指针的指向是否为空，若是，则执行步骤33，若否，则执行步骤32。

步骤32、将所述当前节点的右孩子节点作为当前节点，返回执行步骤12；

步骤33、判断所述当前节点存储的关键值个数是否小于所述预设值，若是，则执行步骤35，若否，则执行步骤34；

步骤34、创建所述当前节点的所述后键值指针指向的所述后邻居键值点为右孩子节点，并将所述右孩子节点插入所述当前节点的双向链表中，将所述右孩子节点作为当前节点；

步骤35、将待操作关键值插入当前节点中的空键值点，结束操作。

结合第二个方面的第一种可能的实现方式至第二个方面的第三种可能的实现方式的任意一种实现方式中，在第六种可能的实现方式中，当所述数据库操作请求为数据库删除请求时，

所述处理模块，具体用于根据待操作关键值查找对应的删除位置；将删除位置的关键值删除，且通过搬移所述当前节点内的关键值更新所述当前节点的二叉树；当判断所述当前节点更新后的二叉树各键值点均为空时，删除所述当前节点；根据更新后的二叉树，更新当前节点的前邻居节点中的后键值指针或后邻居节点中的前键值指针。

结合第二个方面的第一种可能的实现方式至第二个方面的第三种可能的实现方式的任意一种实现方式中，在第七种可能的实现方式中，当所述数据库操作请求为数据库查找请求时，

所述处理模块，具体用于根据所述待操作关键值中的查找下限值和查找上限值分别查找对应的下限值位置和上限值位置；根据所述节点中的所述前键值指针和所述后键值指针，读取所述上限值和下限值之间的所有关键值。

本发明实施例提供一种数据库索引方法及装置，该数据库索引方法，包括通过数据库接收数据库操作请求，并根据数据库操作请求，在数据库中对待操作关键值进行索引操作，其中，该数据库采用T-Tree数据结构，并且T-Tree中的每个节点采用二叉树结构存储各关键值，从而在对数据库中对待操作关键值进行索引操作时，可以根据数据库采用的T-Tree数据结构、以及T-Tree中的每个节点的二叉树结构，进行索引操作，进而提高数据库中进行索引的效率。

附图说明

为了更清楚地说明本发明实施例或现有技术中的技术方案，下面将对实施例或现有技术描述中所需要使用的附图作一简单地介绍，显而易见地，下面描述中的附图是本发明的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动性的前提下，还可以根据这些附图获得其他的附图。

图1为本发明一实施例提供的数据库索引方法的流程图；

图2为本发明一实施例提供的数据库中节点的结构示意图；

图3为本发明另一实施例提供的数据库索引方法的流程图。

图4为本发明再一实施例提供的数据库索引方法的流程图；

图5为本发明再一实施例提供的数据库索引方法的流程图；

图6为本发明一实施例提供的数据库索引装置的结构示意图。

具体实施方式

为使本发明实施例的目的、技术方案和优点更加清楚，下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有作出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。

本发明实施例提供的数据库索引方法及装置可以应用于对数据库进行索引时。本实施例提供的数据库索引方法具体可以通过数据库索引装置来执行，该数据库索引装置可以集成在数据库中，该数据库索引装置可以采用软件和/或硬件的方式来实现。以下对本实施例提供的数据库索引方法及装置进行详细地说明。

图1为本发明一实施例提供的数据库索引方法的流程图。如图1所示，该数据库索引方法，包括：

步骤101、接收数据库操作请求。

在本实施例中，数据库可以接收数据库操作请求，该数据库操作请求可以包括有操作指令与待操作关键值，其中，该操作指令可以为插入操作指令、查找操作指令或者删除操作指令。

步骤102、根据数据库操作请求，在数据库中对待操作关键值进行索引操作，其中，数据库采用T-Tree数据结构，并且T-Tree中的每个节点采用二叉树结构存储各关键值。

具体的，T-Tree中的每个节点采用二叉树结构，其中，该二叉树的每个键值点至多连接一个左孩子键值点和一个右孩子键值点，且左孩子键值点中存储的关键值小于右孩子键值点中存储的关键值。

在本实施例中，根据数据库操作请求，在数据库中对待操作关键值进行索引操作的实现方式至少可以包括三种：

第一种实现方式，当数据库操作请求为数据库插入请求时，根据待操作关键值查找对应的插入位置，并在插入位置存在关键值时，通过搬移关键值将待操作关键值插入该插入位置，其中，该关键值可以是一个关键值，也可以是多个关键值。

第二种实现方式，当数据库操作请求为数据库删除请求时，根据待操作关键值查找对应的删除位置，接着，将删除位置的关键值删除，且通过搬移当前节点内的关键值更新二叉树。

进一步的，当判断当前节点更新后的二叉树各键值点均为空时，删除当前节点；并根据更新后的二叉树，更新当前节点的前邻居节点中的后键值指针或后邻居节点中的前键值指针。

第三种实现方式，当数据库操作请求为数据库查找请求时，根据待操作关键值中的查找下限值和查找上限值分别查找对应的下限值位置和上限值位置；接着，根据各节点中的前键值指针和后键值指针，读取上限值和下限值之间的所有关键值。

本发明实施例提供的数据库索引方法，通过数据库接收数据库操作请求，并根据数据库操作请求，在数据库中对待操作关键值进行索引操作，其中，该数据库采用T-Tree数据结构，并且T-Tree中的每个节点采用二叉树结构存储各关键值，从而在对数据库中对待操作关键值进行索引操作时，可以根据数据库采用的T-Tree数据结构、以及T-Tree中的每个节点的二叉树结构，进行索引操作，进而提高数据库中进行索引的效率。

在上述实施例的基础上，该T-Tree每个节点分别设置有一个前键值指针和一个后键值指针，其中，该前键值指针用于指向该节点中最小关键值的位于前邻居节点中的前邻居键值点，该后键值指针用于指向该节点中最大关键值的位于后邻居节点中的后邻居键值点。

进一步的，在上述实施例的基础上，该T-Tree每个节点可以分别设置有一个左孩子指针和一个右孩子指针，其中，该左孩子指针用于指向该节点的左孩子节点，该右孩子指针用于指向该节点的右孩子节点。

图2为本发明一实施例提供的数据库中节点的结构示意图。如图2所示，该数据库采用T-Tree数据结构，其中，该T-Tree中的每个节点可以采用二叉树结构存储各关键值，在该节点上设置有双向链表，即在该节点上分别设置有一个前键值指针1和一个后键值指针2，其中，该前键值指针用于指向节点中最小关键值的位于前邻居节点中的前邻居键值点，该后键值指针用于指向该节点中最大关键值的位于后邻居节点中的后邻居键值点。因此，可以根据前键值指针和后键值指针，将大小相邻的节点组成双向链表的结构，从而可以在数据库中的一个节点中的最大关键值和最小关键值发生溢出时，迅速找到相邻的节点。同时T-Tree每个节点还可以分别设置有一个左孩子指针3和一个右孩子指针4，其中，左孩子指针3用于指向该节点的左孩子节点，该右孩子指针4用于指向该节点的右孩子节点。

需要说明的是，该T-Tree每个节点的前键值指针1和左孩子指针3可以复用相同的第一比特位，且节点中还可以设置有第一指针标志位，用于标识该第一比特位当前为前键值指针或左孩子节点；

进一步的，在上述实施例的基础上，该T-Tree每个节点的后键值指针2和右孩子指针4可以复用相同的第二比特位，且节点中还可以设置有第二指针标志位，用于标识该第二比特位当前为后键值指针或右孩子节点。

具体的，第一种实现方式，在每个节点的二叉树结构中存在叶子节点，该叶子节点没有子节点，因此可以将左孩子节点指针与前键值指针复用相同的第一比特位，将右孩子节点指针与后键值指针复用相同的第二比特位，即将左孩子节点指针和右孩子节点指针分别用作前键值指针和后键值指针。

第二种实现方式，在数据库T-Tree结构的中间节点中，可以将前键值指针和后键值指针分别设置在存储数据的位置，即该中间节点将减少保存关键值的数量。

第三种实现方式，在数据库T-Tree结构中，存在只有一个子节点的节点，具体的，若该节点的左孩子指针的指向为空，则将该左孩子指针与前键值指针进行复用，并且在该节点中还可以设置有第一指针标志位，用于标识该第一比特位当前为前键值指针；若该节点的右孩子节点指针的指向为空，则将右孩子节点指针与后键值指针进行复用，并且在该节点中还可以设置有第二指针标志位，用于标识该第二比特位当前为后键值指针。

在本实施例中，将数据库T-Tree结构中节点的左孩子节点指针、右孩子节点指针分别与前键值指针、后键值指针进行复用，可以节省存储空间，并提高内存利用率。

图3为本发明另一实施例提供的数据库索引流程图。如图3所示，该数据库的插入方法可以包括：

步骤301、接收数据库插入请求。

步骤302、根据数据库插入请求确定待操作关键值，并确定该T-Tree的根节点为待插入的当前节点。

在本实施例中，该数据库插入请求中至少携带有插入操作指令，以及待操作关键值。

步骤303、比较待操作关键值是否小于当前节点的最小关键值，若是，则执行步骤311，若否，则执行步骤304；

步骤304、比较待操作关键值是否大于当前节点的最大关键值，若是，则执行步骤321，若否，则执行步骤305；

步骤305、在当前节点中查找该待操作关键值对应的插入位置。

具体的，经过步骤303与步骤304，可以确定待操作关键值处于当前节点的最大关键值与最小关键值之间，接着，可以在当前节点中查找该待操作关键值对应的插入位置。

步骤306、判断当前节点是否为满节点，若否，则执行步骤308，若是，则执行步骤307。

在本实施例中，判断当前节点是否为满节点，也就是说，判断当前节点的所有存储关键值的空间是否均存储有关键值，若否，则可以根据该节点的二叉树结构，通过搬移当前节点内的键值点将待操作关键值插入所述插入位置，并结束操作；若是，则执行步骤307。

步骤307、将当前节点的最小关键值搬移到前键值指针指向的前邻居键值点，或将最大关键值搬移到后键值指针指向的后邻居键值点。

在本实施例中，若待操作关键值准备插入的当前节点为满时，需要通过该节点的双向链表移动该当前节点的最小关键值或是最大关键值，即，将当前节点的最小关键值搬移到前键值指针指向的前邻居键值点，或者将最大关键值搬移到后键值指针指向的后邻居键值点，并在通过搬移当前节点内的该最小关键值或是该最大关键值之后，预留出可以插入待操作关键值的插入位置，接着，根据当前节点的二叉树结构将待操作关键值插入插入位置。接着，将搬移的最小关键值或最大关键值作为新的待操作关键值，将前邻居键值点或后邻居键值点更新为当前节点，进行新的待操作关键值插入的过程，返回执行步骤302。

步骤308、通过搬移当前节点内的键值点将待操作关键值插入所述插入位置，结束操作。

步骤311、判断当前节点的孩子指针的指向是否为空，若是，则执行步骤313，若否，则执行步骤312。

在本实施例中，判断当前节点的左孩子指针的指向是否为空，若是，则当前节点在整个T-Tree的叶子节点上，则可以执行步骤313；若否，则当前节点在整个T-Tree的中间节点或是根节点上，则可以执行步骤312。

步骤312、将当前节点的左孩子节点作为当前节点，返回执行步骤302。

在本实施例中，若判断当前节点的最小关键值的左孩子指针的指向不为空，则可以将当前节点的左孩子指针指向的左孩子节点，即一个新二叉树的根节点作为新的当前节点，其中，该新二叉树为整个数据库T-Tree中的一个节点，并返回步骤302重新进行操作。

步骤313、判断当前节点存储的关键值个数是否小于预设值，若是，则执行步骤315，若否，则执行步骤314。

在本实施例中，若判断当前节点的左孩子节点指针的指向为空，则该当前节点位于数据库中的T-Tree的叶子节点上，接着，需要判断当前节点存储的关键值个数是否小于预设值，该预设值可以由本领域相关技术人员根据该T-Tree最多可以存储键值的个数进行设置，例如，该预设值可以为该二叉树中存储最大关键值点的序号，若否，则执行步骤314，若是，则执行步骤315。

需要说明的是，在本实施例中，可以通过调节该预设值的大小，减少插入是的搬移次数，从而提高插入速度。

步骤314、创建当前节点的前键值指针指向的前邻居键值点为左孩子节点，并将左孩子节点插入所述当前节点的双向链表中，将该左孩子节点作为当前节点。

在本实施例中，可以创建当前节点的前键值指针指向的前邻居键值点为左孩子节点，即将该前邻居键值点为左孩子节点，将左孩子节点插入当前节点的双向链表中，并在当前节点中添加左孩子节点指针。从而在发生前溢操作时，可以根据前键值指针指向的前邻居键值点，找到相邻的节点，从而避免了在T-Tree中逐级访问，提高了待操作键值的插入速度。

步骤315、将待操作关键值插入当前节点中的空键值点，结束操作。

具体的，在该当前节点的二叉树中，根据二叉树结构对当前节点的所有键值进行查找、以及搬移，从而形成空键值点，并将待操作关键值插入当前节点中的空键值点。

需要说明的是，若步骤314中将左孩子节点作为当前节点之后，确定该当前节点为满节点时，可以返回执行步骤314。

步骤321、判断当前节点的右孩子指针指向是否为空，若是，则执行步骤323，若否，则执行步骤322；

在本实施例中，判断当前节点的右孩子指针的指向是否为空，若是，则当前节点在整个T-Tree的叶子节点上，则可以执行步骤313；若否，则当前节点没有在整个T-Tree的叶子节点上，则可以执行步骤312。

步骤322、将当前节点的右孩子节点作为当前节点，返回执行步骤302；

步骤323、判断当前节点存储的关键值个数是否小于预设值，若是，则执行步骤325，若否，则执行步骤324。

在本实施例中，若判断当前节点的左孩子节点指针的指向为空，则该当前节点位于数据库中的T-Tree的叶子节点上，接着，需要判断当前节点存储的关键值个数是否小于预设值，该预设值可以根据本领域相关技术人员根据该T-Tree最多可以存储键值的个数进行设置，例如，该预设值可以为该二叉树中可以存储最大关键值的序号，若是，则执行步骤325。若否，则执行步骤324，

步骤324、创建当前节点的后键值指针指向的后邻居键值点为右孩子节点，并将所述右孩子节点插入所述当前节点的双向链表中，将右孩子节点作为当前节点。

在本实施例中，可以将当前节点的后键值指针指向的后邻居键值点作为右孩子节点，将右孩子节点插入当前节点的双向链表中，并在当前节点中添加右孩子节点指针。从而在发生后溢操作时，可以根据后键值指针指向的后邻居键值点，找到相邻的节点，从而避免了T-Tree的逐级访问，提高了待操作键值的插入速度。

步骤325、将待操作关键值插入当前节点中的空键值点，结束操作。

在本实施例中，步骤325与步骤315的实现原理与技术效果类似，在此不再赘述。

在本实施例中，在该数据库中准备插入关键值时，可以根据该数据库中T-Tree的每个节点内部为二叉树的结构，从而减少搬移次数，并根据该数据库中的前键值指针和后键值指针快速的进行前溢操作和后溢操作。

图4为本发明再一实施例提供的数据库索引方法的流程图。如图4所示，在上述实施例的基础上，该数据库的删除方法可以包括：

步骤401、接收数据库操作请求。

步骤402、当该数据库操作请求为数据库删除请求时，根据待操作关键值查找对应的删除位置。

步骤403、将删除位置的关键值删除，且通过搬移当前节点内的关键值更新二叉树。

在本实施例中，步骤402与步骤403的实现方式与现有技术中对二叉树中的节点进行删除的实现方式基本类似，在此不再赘述。

需要说明的是，该数据库删除请求中至少携带有删除操作指令，以及待操作关键值。

步骤404、当判断当前节点更新后的二叉树各键值点均为空时，删除当前节点；

步骤405、根据更新后的二叉树，更新当前节点的前邻居节点中的后键值指针或后邻居节点中的前键值指针。

在本实施例中，由于该数据库采用的T-Tree中的每个节点均采用二叉树结构，因此在删除关键值之后，只需要移动与被删除关键值相邻的关键值，减少了搬移次数，并可以通过实现判断搬移次数来。并由于在每个节点上设置有前键值指针和后键值指针，可以比较方便地进行相邻节点的合并或拆分，从而改善内存利用率。

图5为本发明再一实施例提供的数据库索引方法的流程图。如图5所示，在上述实施例的基础上，该数据库的查找方法可以包括：

步骤501、接收数据库查找请求。

步骤502、当该数据库操作请求为数据库查找请求时，根据待操作关键值中的查找下限值和查找上限值分别查找对应的下限值位置和上限值位置。

在本实施例中，该数据库查找请求中至少携带有查找操作指令，以及待操作关键值。

具体的，根据当前节点的二叉树结构，以及待操作关键值中的查找下限值和查找上限值分别查找对应的下限值位置和上限值位置，可以有至少两种实现方式：

第一种实现方式，若待操作关键值是一个关键值时，可以将该二叉树的根节点作为当前开始查找的第一节点，并按照二叉树结构的特性进行查找，若第一节点中存储的键值大于待操作关键值时，则可以向该二叉树的左孩子方向进行查找，若第一节点中存储的键值小于待操作关键值时，则可以向该二叉树的右孩子方向进行查找，不论查找是向着二叉树的左孩子方向还是右孩子方向，在查找到的键值与待操作关键值相同时，可以首先默认继续向存储该键值节点的左边方向进行查找，查找的键值与待操作关键值不相同时，用前键值指针指向该位置，接着，继续向与待操作关键值相同的键值的右边方向进行查找，查找的键值与待操作关键值不相同时，用后键值指针指向该位置。

第二种实现方式，若待操作关键值是一个范围的关键值时，即该待操作关键值包括有最大待操作关键值与最小待操作关键值。

具体的，将该二叉树的根节点作为当前开始查找的第一节点，并按照二叉树结构的特性进行查找，首先查找最小待操作关键值，即若第一节点中存储的键值大于最小待操作关键值时，则可以向该二叉树的左孩子方向进行查找，若第一节点中存储的键值小于最小待操作关键值时，则可以向该二叉树的右孩子方向进行查找，不论查找是向着二叉树的左孩子方向还是右孩子方向，在查找到的键值与最小待操作关键值相同时，可以继续向存储该键值节点的左边方向进行查找，查找的键值与待操作关键值不相同时，用前键值指针指向该位置，接着，查找最大待操作关键值，查找方法与查找最小待操作关键值的方法相同，在查找到的键值与最大待操作关键值相同时，可以继续向存储该键值节点的右边方向进行查找，查找的键值与待操作关键值不相同时，用后键值指针指向该位置。

步骤503、根据节点中的前键值指针和后键值指针，读取上限值和下限值之间的所有关键值。

不论待操作关键值是一个关键值还是一个范围内的所有关键值，在执行步骤502之后，可以根据节点中的前键值指针和后键值指针，读取上限值和下限值之间的所有关键值

在本实施例中，待操作关键值是一个键值的查找，或者是一个范围的多个键值时，可以通过两次的查找，即分别查找当前节点的最大键值和最小键值，并使用前键值指针和后键值指针，读取上限值和下限值之间的所有关键值。

图6为本发明一实施例提供的数据库索引装置的结构示意图。如图6所示，该数据库索引装置，包括：

接收模块601，用于接收数据库操作请求；

处理模块602，用于根据数据库操作请求，在数据库中对待操作关键值进行索引操作，其中，数据库采用T-Tree数据结构，且T-Tree中的每个节点采用二叉树结构存储各关键值，二叉树的每个键值点至多连接一个左孩子键值点和一个右孩子键值点，左孩子键值点中存储的关键值小于右孩子键值点中存储的关键值。

在本实施例中，该T-Tree每个节点分别设置有一个前键值指针和一个后键值指针，前键值指针用于指向节点中最小关键值的位于前邻居节点中的前邻居键值点，后键值指针用于指向节点中最大关键值的位于后邻居节点中的后邻居键值点。

在上述实施例的基础上，该T-Tree每个节点可以分别设置有一个左孩子指针和一个右孩子指针，左孩子指针用于指向节点的左孩子节点，右孩子指针用于指向节点的右孩子节点。

进一步的，该T-Tree每个节点的前键值指针和左孩子指针复用相同的第一比特位，且节点中还设置有第一指针标志位，用于标识第一比特位当前为前键值指针或左孩子节点；

T-Tree每个节点的后键值指针和右孩子指针复用相同的第二比特位，且节点中还设置有第二指针标志位，用于标识第二比特位当前为后键值指针或右孩子节点。

在本实施例中，

在上述实施例的基础上，当数据库操作请求为数据库插入请求时，

该处理模块602，具体用于根据待操作关键值查找对应的插入位置，并在插入位置存在关键值时，通过搬移关键值将待操作关键值插入插入位置。

在上述实施例的基础上，当数据库操作请求为数据库插入请求时，

处理模块602，具体用于根据待操作关键值查找对应的插入位置，并在插入位置存在关键值时，通过搬移关键值将待操作关键值插入插入位置包括：

步骤11、根据数据库插入请求确定待操作关键值，并确定T-Tree的根节点为待插入的当前节点；

步骤12、比较待操作关键值是否小于当前节点的最小关键值，若是，则执行步骤21，若否，则执行步骤13；

步骤13、比较待操作关键值是否大于当前节点的最大关键值，若是，则执行步骤31，若否，则执行步骤14；

步骤14、在当前节点中查找待操作关键值对应的插入位置；

步骤15、判断当前节点是否为满节点，若否，则通过搬移当前节点内的键值将待操作关键值插入插入位置，结束操作，若是，则执行步骤16；

步骤16、将当前节点的最小关键值搬移到前键值指针指向的前邻居键值点，或将最大关键值搬移到后键值指针指向的后邻居键值点，通过搬移当前节点内的最小关键值或是最小关键值将待操作关键值插入插入位置，且将搬移的最小关键值或最大关键值作为新的待操作关键值，将前邻居键值点或后邻居键值点更新为当前节点，返回执行步骤12；

步骤21、判断当前节点的左孩子指针的指向是否为空，若是，则执行步骤23，若否，则执行步骤22；

步骤22、将当前节点的左孩子节点作为当前节点，返回执行步骤12；

步骤23、判断当前节点存储的关键值个数是否小于预设值，若是，则执行步骤25，若否，则执行步骤24；

步骤24、创建当前节点的前键值指针指向的前邻居键值点为左孩子节点，并将左孩子节点插入当前节点的双向链表中，将左孩子节点作为当前节点；

步骤25、将待操作关键值插入当前节点中的空键值点，结束操作；

步骤31、判断当前节点的右孩子指针的指向是否为空，若是，则执行步骤33，若否，则执行步骤32。

步骤32、将当前节点的右孩子节点作为当前节点，返回执行步骤12；

步骤33、判断当前节点存储的关键值个数是否小于预设值，若是，则执行步骤35，若否，则执行步骤34；

步骤34、创建当前节点的后键值指针指向的后邻居键值点为右孩子节点，并将右孩子节点插入当前节点的双向链表中，将右孩子节点作为当前节点；

步骤35、将待操作关键值插入当前节点中的空键值点，结束操作。

在上述实施例的基础上，当数据库操作请求为数据库删除请求时，

处理模块602，具体用于根据待操作关键值查找对应的删除位置；将删除位置的关键值删除，且通过搬移当前节点内的关键值更新当前节点的二叉树；当判断当前节点更新后的二叉树各键值点均为空时，删除当前节点；根据更新后的二叉树，更新当前节点的前邻居节点中的后键值指针或后邻居节点中的前键值指针。

在上述实施例的基础上，当数据库操作请求为数据库查找请求时，

处理模块602，具体用于根据待操作关键值中的查找下限值和查找上限值分别查找对应的下限值位置和上限值位置；根据节点中的前键值指针和后键值指针，读取上限值和下限值之间的所有关键值。

本领域普通技术人员可以理解：实现上述各方法实施例的全部或部分步骤可以通过程序指令相关的硬件来完成。前述的程序可以存储于一计算机可读取存储介质中。该程序在执行时，执行包括上述各方法实施例的步骤；而前述的存储介质包括：ROM、RAM、磁碟或者光盘等各种可以存储程序代码的介质。

最后应说明的是：以上各实施例仅用以说明本发明的技术方案，而非对其限制；尽管参照前述各实施例对本发明进行了详细的说明，本领域的普通技术人员应当理解：其依然可以对前述各实施例所记载的技术方案进行修改，或者对其中部分或者全部技术特征进行等同替换；而这些修改或者替换，并不使相应技术方案的本质脱离本发明各实施例技术方案的范围。

Claims (14)

1.一种数据库索引方法，其特征在于，包括：

接收数据库操作请求；

根据所述数据库操作请求，在数据库中对待操作关键值进行索引操作，其中，所述数据库采用T-Tree数据结构，且所述T-Tree中的每个节点采用二叉树结构存储各所述关键值，所述二叉树的每个键值点至多连接一个左孩子键值点和一个右孩子键值点，所述左孩子键值点中存储的关键值小于所述右孩子键值点中存储的关键值；

所述T-Tree中的每个节点分别设置有一个前键值指针和一个后键值指针，所述前键值指针用于指向所述节点中最小关键值的位于前邻居节点中的前邻居键值点，所述后键值指针用于指向所述节点中最大关键值的位于后邻居节点中的后邻居键值点，所述前键值指针和所述后键值指针被用于进行相邻节点的合并。

2.根据权利要求1所述的数据库索引方法，其特征在于，所述T-Tree每个节点分别设置有一个左孩子指针和一个右孩子指针，所述左孩子指针用于指向所述节点的左孩子节点，所述右孩子指针用于指向所述节点的右孩子节点。

3.根据权利要求2所述的数据库索引方法，其特征在于：

所述T-Tree每个节点的所述前键值指针和所述左孩子指针复用相同的第一比特位，且节点中还设置有第一指针标志位，用于标识所述第一比特位当前为前键值指针或左孩子节点；

所述T-Tree每个节点的所述后键值指针和所述右孩子指针复用相同的第二比特位，且节点中还设置有第二指针标志位，用于标识所述第二比特位当前为后键值指针或右孩子节点。

4.根据权利要求1-3任一所述的数据库索引方法，其特征在于，根据所述数据库操作请求，在索引数据库中对待操作关键值进行索引操作包括：

当所述数据库操作请求为数据库插入请求时，根据待操作关键值查找对应的插入位置，并在插入位置存在关键值时，通过搬移关键值将所述待操作关键值插入所述插入位置。

5.根据权利要求4所述的数据库索引方法，其特征在于，当所述数据库操作请求为数据库插入请求时，根据待操作关键值查找对应的插入位置，并在插入位置存在关键值时，通过搬移关键值将所述待操作关键值插入所述插入位置包括：

步骤11、根据数据库插入请求确定待操作关键值，并确定所述T-Tree的根节点为待插入的当前节点；

步骤12、比较所述待操作关键值是否小于所述当前节点的最小关键值，若是，则执行步骤21，若否，则执行步骤13；

步骤13、比较所述待操作关键值是否大于所述当前节点的最大关键值，若是，则执行步骤31，若否，则执行步骤14；

步骤14、在所述当前节点中查找所述待操作关键值对应的插入位置；

步骤15、判断所述当前节点是否为满节点，若否，则通过搬移所述当前节点内的键值将待操作关键值插入所述插入位置，结束操作，若是，则执行步骤16；

步骤16、将当前节点的最小关键值搬移到所述前键值指针指向的所述前邻居键值点，或将最大关键值搬移到所述后键值指针指向的所述后邻居键值点，通过搬移当前节点内的所述最小关键值或是所述最大关键值将所述待操作关键值插入所述插入位置，且将搬移的所述最小关键值或最大关键值作为新的待操作关键值，将所述前邻居键值点或所述后邻居键值点更新为当前节点，返回执行步骤12；

步骤21、判断当前节点的所述左孩子指针的指向是否为空，若是，则执行步骤23，若否，则执行步骤22；

步骤22、将所述当前节点的左孩子节点作为当前节点，返回执行步骤12；

步骤23、判断所述当前节点存储的关键值个数是否小于预设值，若是，则执行步骤25，若否，则执行步骤24；

步骤24、创建所述当前节点的所述前键值指针指向的所述前邻居键值点为左孩子节点，并将所述左孩子节点插入所述当前节点的双向链表中，将所述左孩子节点作为当前节点；

步骤25、将所述待操作关键值插入所述当前节点中的空键值点，结束操作；

步骤31、判断当前节点的所述右孩子指针的指向是否为空，若是，则执行步骤33，若否，则执行步骤32；

步骤32、将所述当前节点的右孩子节点作为当前节点，返回执行步骤12；

步骤33、判断所述当前节点存储的关键值个数是否小于所述预设值，若是，则执行步骤35，若否，则执行步骤34；

步骤34、创建所述当前节点的所述后键值指针指向的所述后邻居键值点为右孩子节点，并将所述右孩子节点插入所述当前节点的双向链表中，将所述右孩子节点作为当前节点；

步骤35、将待操作关键值插入当前节点中的空键值点，结束操作。

6.根据权利要求1-3任一所述的数据库索引方法，其特征在于，根据所述数据库操作请求，在索引数据库中对待操作关键值进行索引操作包括：

当所述数据库操作请求为数据库删除请求时，根据待操作关键值查找对应的删除位置；

将删除位置的关键值删除，且通过搬移当前节点内的关键值更新所述当前节点的二叉树；

当判断所述当前节点更新后的二叉树各键值点均为空时，删除所述当前节点；

根据更新后的二叉树，更新当前节点的前邻居节点中的后键值指针或后邻居节点中的前键值指针。

7.根据权利要求1-3任一所述的数据库索引方法，其特征在于，根据所述数据库操作请求，在索引数据库中对待操作关键值进行索引操作包括：

当所述数据库操作请求为数据库查找请求时，根据所述待操作关键值中的查找下限值和查找上限值分别查找对应的下限值位置和上限值位置；

根据所述节点中的所述前键值指针和所述后键值指针，读取所述上限值和下限值之间的所有关键值。

8.一种数据库索引装置，其特征在于，包括：

接收模块，用于接收数据库操作请求；

处理模块，用于根据所述数据库操作请求，在数据库中对待操作关键值进行索引操作，其中，所述数据库采用T-Tree数据结构，且所述T-Tree中的每个节点采用二叉树结构存储各所述关键值，所述二叉树的每个键值点至多连接一个左孩子键值点和一个右孩子键值点，所述左孩子键值点中存储的关键值小于所述右孩子键值点中存储的关键值；

所述T-Tree每个节点分别设置有一个前键值指针和一个后键值指针，所述前键值指针用于指向所述节点中最小关键值的位于前邻居节点中的前邻居键值点，所述后键值指针用于指向所述节点中最大关键值的位于后邻居节点中的后邻居键值点，所述前键值指针和所述后键值指针被用于进行相邻节点的合并。

9.根据权利要求8所述的数据库索引装置，其特征在于，所述T-Tree每个节点分别设置有一个左孩子指针和一个右孩子指针，所述左孩子指针用于指向所述节点的左孩子节点，所述右孩子指针用于指向所述节点的右孩子节点。

10.根据权利要求9所述的数据库索引装置，其特征在于：

所述T-Tree每个节点的所述前键值指针和所述左孩子指针复用相同的第一比特位，且节点中还设置有第一指针标志位，用于标识所述第一比特位当前为前键值指针或左孩子节点；

所述T-Tree每个节点的所述后键值指针和所述右孩子指针复用相同的第二比特位，且节点中还设置有第二指针标志位，用于标识所述第二比特位当前为后键值指针或右孩子节点。

11.根据权利要求8-10任一所述的数据库索引装置，其特征在于，当所述数据库操作请求为数据库插入请求时，

所述处理模块，具体用于根据待操作关键值查找对应的插入位置，并在插入位置存在关键值时，通过搬移关键值将所述待操作关键值插入所述插入位置。

12.根据权利要求11所述的数据库索引装置，其特征在于，当所述数据库操作请求为数据库插入请求时，

所述处理模块，具体用于根据待操作关键值查找对应的插入位置，并在插入位置存在关键值时，通过搬移关键值将所述待操作关键值插入所述插入位置包括：

步骤11、根据数据库插入请求确定待操作关键值，并确定所述T-Tree的根节点为待插入的当前节点；

步骤12、比较所述待操作关键值是否小于所述当前节点的最小关键值，若是，则执行步骤21，若否，则执行步骤13；

步骤13、比较所述待操作关键值是否大于所述当前节点的最大关键值，若是，则执行步骤31，若否，则执行步骤14；

步骤14、在所述当前节点中查找所述待操作关键值对应的插入位置；

步骤15、判断所述当前节点是否为满节点，若否，则通过搬移所述当前节点内的键值将待操作关键值插入所述插入位置，结束操作，若是，则执行步骤16；

步骤16、将当前节点的最小关键值搬移到所述前键值指针指向的所述前邻居键值点，或将最大关键值搬移到所述后键值指针指向的所述后邻居键值点，通过搬移当前节点内的所述最小关键值或是所述最大关键值将所述待操作关键值插入所述插入位置，且将搬移的所述最小关键值或最大关键值作为新的待操作关键值，将所述前邻居键值点或所述后邻居键值点更新为当前节点，返回执行步骤12；

步骤21、判断当前节点的所述左孩子指针的指向是否为空，若是，则执行步骤23，若否，则执行步骤22；

步骤22、将所述当前节点的左孩子节点作为当前节点，返回执行步骤12；

步骤23、判断所述当前节点存储的关键值个数是否小于预设值，若是，则执行步骤25，若否，则执行步骤24；

步骤24、创建所述当前节点的所述前键值指针指向的所述前邻居键值点为左孩子节点，并将所述左孩子节点插入所述当前节点的双向链表中，将所述左孩子节点作为当前节点；

步骤25、将所述待操作关键值插入所述当前节点中的空键值点，结束操作；

步骤31、判断当前节点的所述右孩子指针的指向是否为空，若是，则执行步骤33，若否，则执行步骤32；

步骤32、将所述当前节点的右孩子节点作为当前节点，返回执行步骤12；

步骤33、判断所述当前节点存储的关键值个数是否小于所述预设值，若是，则执行步骤35，若否，则执行步骤34；

步骤34、创建所述当前节点的所述后键值指针指向的所述后邻居键值点为右孩子节点，并将所述右孩子节点插入所述当前节点的双向链表中，将所述右孩子节点作为当前节点；

步骤35、将待操作关键值插入当前节点中的空键值点，结束操作。

13.根据权利要求8-10任一所述的数据库索引装置，其特征在于，当所述数据库操作请求为数据库删除请求时，

所述处理模块，具体用于根据待操作关键值查找对应的删除位置；将删除位置的关键值删除，且通过搬移当前节点内的关键值更新所述当前节点的二叉树；当判断所述当前节点更新后的二叉树各键值点均为空时，删除所述当前节点；根据更新后的二叉树，更新当前节点的前邻居节点中的后键值指针或后邻居节点中的前键值指针。

14.根据权利要求8-10任一所述的数据库索引装置，其特征在于，当所述数据库操作请求为数据库查找请求时，

所述处理模块，具体用于根据所述待操作关键值中的查找下限值和查找上限值分别查找对应的下限值位置和上限值位置；根据所述节点中的所述前键值指针和所述后键值指针，读取所述上限值和下限值之间的所有关键值。