数组树数据储存方法、快速查找方法及可读储存介质

摘要

本发明公开了数组树数据储存方法、快速查找方法及可读储存介质。该数组树数据储存方法，包括如下步骤，获取关键字和关键字的数字排列特征，对关键字进行预处理；根据数字排列特征，将关键字映射成数组与树形结构结合表示的链路，建立树形数据结构；将储存数据的内存地址储存至树形数据结构的叶节点；将树形数据结构的叶节点链接。本发明的技术方案中，数组树数据储存方法利用关键字中数字的排列特性，映射成数组与树形结构结合表示的数组树存储链路，以形成检索数据的数据储存方式，数组树数据储存方法索引小于B树索引占用的内存空间，因其查找复杂度只于关键字长度有关，所以较B树、B+树算法有着更高的检索效率。

权利要求

1.一种数组树数据储存方法，其特征在于，包括如下步骤：获取关键字和所述关键字的数字排列特征，对所述关键字进行长度一致的预处理；

根据所述数字排列特征，所述数字排列特征中数字的排列次序对应树形结构中的层级，所述关键字的数字对应树形结构中本级数组的下标，将所述关键字映射成数组与树形结构结合表示的链路，建立树形数据结构；

根据储存数据的所述关键字的数字排列特性形成的链路，将所述储存数据的内存地址储存至所述树形数据结构的叶节点；

将所述树形数据结构的叶节点链接。

2.根据权利要求1所述的一种数组树数据储存方法，其特征在于，所述链路为根据所述关键字的所述数字排列特征所形成的或经过的所述树形结构中的数组指针及数组下标组成的顺序记录。

3.根据权利要求1所述的一种数组树数据储存方法，其特征在于，所述对所述关键字进行长度一致的预处理的步骤，包括如下步骤：获取系统内对所述关键字的预设长度；

根据所述预设长度，对所述关键字进行长度一致的预处理。

4.根据权利要求1所述的一种数组树数据储存方法，其特征在于，所述根据储存数据的所述关键字的数字排列特性形成的链路，将所述储存数据的内存地址储存至所述树形数据结构的叶节点的步骤，包括如下步骤：顺序读取所述关键字数组的下标，获取与所述下标对应的结构数组指针，返回链路记录；

判断所述结构数组是否为最后一级所述树形数据结构的叶节点数组；

若是，则更新叶节点数组链接，将储存数据的内存地址储存至所述树形数据结构的叶节点数组。

5.根据权利要求4所述的一种数组树数据储存方法，其特征在于，所述顺序读取所述关键字数组的下标，保存链路记录的步骤，包括如下步骤：顺序读取所述关键字中数组的下标；

根据所述关键字中数组的下标查找对应所述树形数据结构的结构数组，并存储所述数组指针及所述数组下标；

判断所述结构数组是否为叶节点数组；

若是，则返回链路记录。

6.根据权利要求5所述的一种数组树数据储存方法，其特征在于，所述结构数组包括相邻数组指针、数组长度和次级数组指针，所述相邻数组指针为所述树形数据结构的所述叶节点间的连接指针，所述次级数组指针为所述树形数据结构的次级节点的连接指针。

7.根据权利要求1-6中任一项所述的一种数组树数据储存方法，其特征在于，所述将多个所述树形数据结构的叶节点顺序链接的步骤，包括如下步骤：从所述关键字对应的当前叶节点开始，根据链路记录，不断在所述当前叶节点的父节点的结构数组中寻找指向左相邻叶节点的左次级数组指针和指向右相邻叶节点的右次级数组指针；

判断所述左次级数组指针和所述右次级数组指针是否有效；

若否，继续在所述当前叶节点的父节点的结构数组继续寻找；

若是，根据找到的所述左次级数组指针和链路记录，不断在所述左次级数组指针的次级节点数组中寻找所述左相邻叶节点，根据找到的所述右次级数组指针和链路记录，不断在所述右次级数组指针的次级节点数组中寻找所述右相邻叶节点；

进行所述当前叶节点的左链接和右链接；所述左链接为将所述当前叶节点的数组指针写入所述当前叶节点的左相邻叶节点的数组头部；所述右链接为将所述当前叶节点的右相邻叶节点的数组指针写入所述当前叶节点的数组头部。

8.一种数组树数据快速查找方法，其特征在于，用于查找数据库，所述数据库采用如权利要求1-7中任一项所述的数组树数据储存方法进行数据存储，所述数组树数据快速查找方法，包括如下步骤：获取储存数据的关键字，对所述关键字进行长度一致预处理；

按照数字排列特征和关键字数组所对应的树形结构链路依次检索结构数组内的次级数组指针；

判断当前结构数组内的次级数组指针是否为空；

若是，返回空值；

判断所述当前结构数组的长度是否小于所述关键字中的数字；

若是，返回空值；

判断所述当前结构数组是否为叶节点数组；

若是，返回所述当前结构数组内的数据地址指针及数组下标作为查找结果。

9.根据权利要求8所述的一种数组树数据快速查找方法，其特征在于，所述关键字包括开始关键字和结束关键字，所述返回所述当前结构数组内的数据地址指针及数组下标作为查找结果的步骤，包括如下步骤：返回所述开始关键字和所述结束关键字分别对应的叶节点数组指针及叶节点数组下标；

从所述开始关键字对应的叶节点数组下标开始，依次读取所述开始关键字对应的叶节点数组内的有效数据地址指针；

在所述开始关键字对应的叶节点数组读取完毕后，根据所述开始关键字对应的叶节点数组头部的相邻叶节点数组指针，继续读取相邻叶节点数组中有效数据地址指针，直至读取到所述结束关键字对应的叶节点数组中所述结束关键字对应的叶节点数组下标；

返回所有读取的有效数据地址指针作为查找结果。

10.一种计算机可读储存介质，其特征在于，所述计算机可读存储介质上存储有计算机程序，所述计算机程序被处理器执行时实现如权利要求1至7中任一项所述的一种数组树数据储存方法或如权利要求8至9中任一项所述的一种数组树数据快速查找方法。

说明书

数组树数据储存方法、快速查找方法及可读储存介质

技术领域

[0001] 本发明涉及计算机技术领域，具体涉及一种数组树数据储存方法、一种数组树数据快速查找方法及一种计算机可读储存介质。

背景技术

[0002] 在数据查找算法中，哈希(hash)查找算法虽然等值查找效率极高，但哈希查找算法却同时存在范围查找功能的不足及磁盘IO效率低等问题，使哈希查找算法应用的场景较少。应用较为广泛的是以分治管理思想为代表的B树(balanced tree oforder m)和B+树算法，B树和B+树算法高效的检索效率和完善的功能而被各大数据库厂商采用。但因B树和B+树算法数据结构的限制，存在着索引占用内存资源较高和检索数据集记录数大于10000000后，性能下降较明显的问题。所以，B树和B+树并不适合海量数据的数据检索。随着大数据应用的不断深化，对查找算法的数据存储结构也提出了更高的要求，亟需提出一数据存储方法，以提高检索效率的同时降低数据结构中索引占用的内存资源。

发明内容

[0003] 本发明的主要目的是提供一种数组树数据储存方法，旨在提高查找效率的同时，解决数据结构中索引占用的内存资源多的问题。

[0004] 为实现上述目的，本发明提出的一种数组树数据储存方法，包括如下步骤：获取关键字和所述关键字的数字排列特征，对所述关键字进行预处理；

[0005] 根据所述数字排列特征，所述数字排列特征中数字的排列次序对应树形结构中的层级，所述关键字的数字对应树形结构中本级数组的下标，将所述关键字映射成数组与树形结构结合表示的链路，建立树形数据结构；

[0006] 根据储存数据的所述关键字的数字排列特性形成的链路，将所述储存数据的内存地址储存至所述树形数据结构的叶节点；

[0007] 将所述树形数据结构的叶节点链接。

[0008] 优选地，所述链路为根据所述关键字的所述数字排列特征所形成的或经过的所述树形结构中的数组指针及数组下标组成的顺序记录。

[0009] 优选地，所述对所述关键字进行预处理的步骤，包括如下步骤：

[0010] 获取系统内对所述关键字的预设长度；

[0011] 根据所述预设长度，对所述关键字进行长度一致的预处理。

[0012] 优选地，所述根据储存数据的所述关键字的数字排列特性形成的链路，将所述储存数据的内存地址储存至所述树形数据结构的叶节点的步骤，包括如下步骤：

[0013] 顺序读取所述关键字数组的下标，获取与所述下标对应的结构数组指针，返回链路记录；

[0014] 判断所述结构数组是否为最后一级所述树形数据结构的叶节点数组；

[0015] 若是，则更新叶节点数组链接，将储存数据的内存地址储存至所述树形数据结构的叶节点数组。

[0016] 优选地，所述顺序读取所述关键字数组的下标，保存链路记录的步骤，包括如下步骤：

[0017] 顺序读取所述关键字中数组的下标；

[0018] 根据所述关键字中数组的下标查找对应所述树形数据结构的结构数组，并存储所述数组指针及所述数组下标；

[0019] 判断所述结构数组是否为叶节点数组；

[0020] 若是，则返回链路记录。

[0021] 优选地，所述结构数组包括相邻数组指针、数组长度和次级数组指针，所述相邻数组指针为所述树形数据结构的所述叶节点间的连接指针，所述次级数组指针为所述树形数据结构的次级节点的连接指针。

[0022] 优选地，所述将多个所述树形数据结构的叶节点顺序链接的步骤，包括如下步骤：

[0023] 从所述关键字对应的当前叶节点开始，根据链路记录，不断在所述当前叶节点的父节点的结构数组中寻找指向左相邻叶节点的左次级数组指针和指向右相邻叶节点的右次级数组指针；

[0024] 判断所述左次级数组指针和所述右次级数组指针是否有效；

[0025] 若否，继续在所述当前叶节点的父节点的结构数组继续寻找；

[0026] 若是，根据找到的所述左次级数组指针和链路记录，不断在所述左次级数组指针的次级节点数组中寻找所述左相邻叶节点，根据找到的所述右次级数组指针和链路记录，不断在所述右次级数组指针的次级节点数组中寻找所述右相邻叶节点；

[0027] 进行所述当前叶节点的左链接和右链接；所述左链接为将所述当前叶节点的数组指针写入所述当前叶节点的左相邻叶节点的数组头部；所述右链接为将所述当前叶节点的右相邻叶节点的数组指针写入所述当前叶节点的数组头部。

[0028] 本发明还提供一种数组树数据快速查找方法，提高了检索效率，用于查找数据库，所述数据库采用如上述任一项所述的数组树数据储存方法进行数据存储，所述数组树数据快速查找方法，包括如下步骤：

[0029] 获取储存数据的关键字，对所述关键字进行长度一致预处理；

[0030] 按照数字排列特征和关键字数组所对应的树形结构链路依次检索结构数组内的次级数组指针；

[0031] 判断当前结构数组内的次级数组指针是否为空；

[0032] 若是，返回空值；

[0033] 判断所述当前结构数组的长度是否小于所述关键字中的数字；

[0034] 若是，返回空值；

[0035] 判断所述当前结构数组是否为叶节点数组；

[0036] 若是，返回所述当前结构数组内的数据地址指针及数组下标作为查找结果。

[0037] 优选地，所述关键字包括开始关键字和结束关键字，所述返回所述当前结构数组内的数据地址指针及数组下标作为查找结果的步骤，包括如下步骤：

[0038] 返回所述开始关键字和所述结束关键字分别对应的叶节点数组指针及叶节点数组下标；

[0039] 从所述开始关键字对应的叶节点数组下标开始，依次读取所述开始关键字对应的叶节点数组内的有效数据地址指针；

[0040] 在所述开始关键字对应的叶节点数组读取完毕后，根据所述开始关键字对应的叶节点数组头部的相邻叶节点数组指针，继续读取相邻叶节点数组中有效数据地址指针，直至读取到所述结束关键字对应的叶节点数组中所述结束关键字对应的叶节点数组下标；

[0041] 返回所有读取的有效数据地址指针作为查找结果。

[0042] 本发明还提供了一种计算机可读储存介质，所述计算机可读存储介质上存储有计算机程序，所述计算机程序被处理器执行时实现如上述任一项所述的一种数组树数据储存方法或如上述任一项所述的一种数组树数据快速查找方法。

[0043] 本发明的技术方案中，数组树数据储存方法利用关键字中数字的排列特性，映射成数组与树形结构结合表示的数组树存储链路，以形成便于检索数据的数据储存方式，数组树数据储存方法中每个节点都是一个数组，每个数组最多能生成10个指针，每个数组指针占用4个字节，B树算法中每个树节点至少定义两个指针、一个关键字及数据地址，因此数组树数据储存方法索引小于B树索引占用的内存空间。

附图说明

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

[0045] 图1为本发明数组树数据储存方法第一实施例的流程示意图；

[0046] 图2为本发明数据关键字的数字排列特征与内存地址之间的对应关系示意图；

[0047] 图3为本发明的数据排列特征示意图；

[0048] 图4为本发明的数字排列特征与数组树(A树)链路示意图；

[0049] 图5为本发明的数组树(A树)结构数组的结构示意图；

[0050] 图6为本发明的数组树(A树)树叶节点链接示意图；

[0051] 图7为本发明的数组树(A树)创建索引流程图；

[0052] 图8为本发明的数组树(A树)叶节点数组与左右相邻叶节点链接示意图；

[0053] 图9为本发明的数组树算法等值检索流程图；

[0054] 图10为本发明的数组树算法范围查询流程图；

[0055] 图11为本发明的数组树算法与二分算法100000循环检索效率对比图；

[0056] 图12为本发明的数组树算法与二分算法1000000次循环检索效率对比图；

[0057] 本发明目的的实现、功能特点及优点将结合实施例，参照附图做进一步说明。

具体实施方式

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

[0059] 需要说明，本发明实施例中所有方向性指示(诸如上、下、左、右、前、后……)仅用于解释在某一特定姿态(如附图所示)下各部件之间的相对位置关系、运动情况等，如果该特定姿态发生改变时，则该方向性指示也相应地随之改变。

[0060] 另外，在本发明中如涉及“第一”、“第二”等的描述仅用于描述目的，而不能理解为指示或暗示其相对重要性或者隐含指明所指示的技术特征的数量。由此，限定有“第一”、“第二”的特征可以明示或者隐含地包括至少一个该特征。在本发明的描述中，“多个”的含义是至少两个，例如两个，三个等，除非另有明确具体的限定。

[0061] 在本发明中，除非另有明确的规定和限定，术语“连接”、“固定”等应做广义理解，例如，“固定”可以是固定连接，也可以是可拆卸连接，或成一体；可以是机械连接，也可以是电连接；可以是直接相连，也可以通过中间媒介间接相连，可以是两个元件内部的连通或两个元件的相互作用关系，除非另有明确的限定。对于本领域的普通技术人员而言，可以根据具体情况理解上述术语在本发明中的具体含义。

[0062] 另外，本发明各个实施例之间的技术方案可以相互结合，但是必须是以本领域普通技术人员能够实现为基础，当技术方案的结合出现相互矛盾或无法实现时应当认为这种技术方案的结合不存在，也不在本发明要求的保护范围之内。

[0063] 请参照图1-图12，具体请参照图1，为实现上述目的，本发明提出的一种数组树数据储存方法，其包括如下步骤：

[0064] S100，获取关键字和所述关键字的数字排列特征，对所述关键字进行预处理；

[0065] S200，根据所述数字排列特征，所述数字排列特征中数字的排列次序对应树形结构中的层级，所述关键字的数字对应树形结构中本级数组的下标，将所述关键字映射成数组与树形结构结合表示的链路，建立树形数据结构；

[0066] S300，根据储存数据的所述关键字的数字排列特性形成的链路，将所述储存数据的内存地址储存至所述树形数据结构的叶节点；

[0067] S400，将所述树形数据结构的叶节点顺序链接。

[0068] 本发明的技术方案中，数组树数据储存方法利用关键字中数字的排列特性，映射成数组与树形结构结合表示的数组树存储链路，以形成便于检索数据的数据储存方式，数组树数据储存方法中每个节点都是一个数组，每个数组最多能生成10个指针，每个数组指针占用4个字节，B树算法中每个树节点至少定义两个指针、一个关键字及数据地址，因此数组树数据储存方法索引小于B树索引占用的内存空间。

[0069] 将数据关键字Key中的数字排列特征转换成树形结构中的不同链路，并在链路末端存储该数据的内存地址(或数据集索引)，其中，每个树节点又对应一个数组。检索时，则依据关键字中的数字排列特性快速通过树形链路找到对应的数据地址，从而实现数据高效检索。本发明是将数组和树型结构结合来实现数据快速查找的算法，即：数组树算法(Array Tree简称A树算法)。而数据关键字的数字排列特征与内存地址之间的对应关系如图2所示。

[0070] 数字排列特征：指关键字中数字从左至右的顺序(或从右至左)，每一个数字代表树结构相应级别数组的下标，关键字的长度可描述为树的高度。

[0071] 树型结构中的节点(数组)：为长度不超过10的指针数组，每个指针都指向下一级(次级)数组(节点)，依此形成链表树结构。而每条链路末端的数组内，存储着数据内存地址，数据关键字Key的每位数字则代表数组的下标，不同的下标组合成不同的数组树(A树)链路。例如任意关键字Key，ID＝81628，其数字排列特征可描述如图3所示，其在数组树(A树)中的链路如图4所示。

[0072] 数组：(以Pascal语言描述)；

[0073] TLinkList＝array[0..9]ofPLinkList；

[0074] //动态数组，每个数组单元存储指向下一级(次级)数组的指针；

[0075] 数组指针：PLinkList＝^TLinkList；//指向次级链表指针。

[0076] 请参照图4，基于本发明的一种数组树数据储存方法的第一实施例，所述链路为根据所述关键字的所述数字排列特征所形成的或经过的所述树形结构中的数组指针及数组下标组成的顺序记录。

[0077] 请参照图5和图7，基于本发明的一种数组树数据储存方法的第一实施例，本发明的一种数组树数据储存方法的第二实施例中，所述步骤S100中的对所述关键字进行预处理的步骤，包括如下步骤：

[0078] S110，获取系统内对所述关键字的预设长度；

[0079] S120，根据所述预设长度，对所述关键字进行长度一致的预处理。

[0080] 具体的，本发明在对数据进行检索时，建议关键字Key最大长度固定，这样有利于减少系统存储空间。对于关键字长度有不一致，可进行长度一致的补位预处理，如关键字为9176，预处理后变为00009176(检索数据集的中关键字最大长度为8位，系统预设长度为8位)，系统预设长度由系统的应用场景确定。

[0081] 请参照图4和图7，基于本发明的一种数组树数据储存方法的第一实施例，本发明的一种数组树数据储存方法的第三实施例中，所述步骤S200，包括如下步骤：

[0082] S210，顺序读取所述关键字数组的下标，获取与所述下标对应的结构数组，返回链路记录；

[0083] S220，判断所述结构数组是否为最后一级所述树形数据结构的叶节点数组；

[0084] 若是，则执行步骤S230，更新叶节点数组链接，将储存数据的内存地址储存至所述树形数据结构的叶节点数组。

[0085] 具体的，在系统初始化载入检索数据集时，根据每一条数据的关键字Key，将其映射成树形结构的链路来表示。

[0086] 请参照图10，基于本发明的一种数组树数据储存方法的第三实施例，本发明的一种数组树数据储存方法的第四实施例中，所述S220的步骤，包括：

[0087] S221，顺序读取所述关键字中数组的下标；

[0088] S222，根据所述关键字中数组的下标查找对应所述树形数据结构的结构数组，并存储所述数组指针及所述数组下标；

[0089] S223，判断所述结构数组是否为叶节点数组；

[0090] 若否，则执行步骤S224，则返回链路记录。

[0091] 具体的，如关键字Key为81628，则映射成树形结构链路步骤(关键字Key从左至右循环取数)；

[0092] 第一位8：在当前数组中(根数组)确认其长度是否小于8，否则将该数组长度扩展为8；接着判断该链表数组下标为8个的次级链表指针不为空？否则，创建一个新的数组(次级数组)，并将该次级数组地址写入当前数组下标8的单元内。接着读取关键字Key第二位：1，依据上述过程，完成数字“1”的映射，直至完成关键字Key最后一位8的映射，结束时，则将数据的内存指针(数据集索引号)写入当前数组下标为8的单元内。至此，一条数据记录的A树索引创建完成，逻辑图如图7。

[0093] 请参照图5，基于本发明的一种数组树数据储存方法的第四实施例，进一步的，所述结构数组包括相邻数组指针、数组长度和次级数组指针，所述相邻数组指针为所述树形数据结构的所述叶节点间的连接指针，所述次级数组指针为所述树形数据结构的次级节点的连接指针。

[0094] 具体的，相邻数组指针：指树形结构叶节点(A树末端数组)间的链接指针，由于A树结构中，叶节点数组中对应的数据关键字为顺序排列(升或降)，所以，将A树结构中的叶节点链接后，能够进行范围查询和遍历。

[0095] 请参照图6和图8，基于本发明的一种数组树数据储存方法的第四实施例，本发明的一种数组树数据储存方法的第五实施例中，所述S400的步骤，包括如下步骤：

[0096] S410，从所述关键字对应的当前叶节点开始，根据链路记录，不断在所述当前叶节点的父节点的结构数组中寻找指向左相邻叶节点的左次级数组指针和指向右相邻叶节点的右次级数组指针；

[0097] S420，判断所述左次级数组指针和所述右次级数组指针是否有效；

[0098] 若否，则执行步骤S430，继续在所述当前叶节点的父节点的结构数组继续寻找；

[0099] 若是，则执行步骤S440，根据找到的所述左次级数组指针和链路记录，不断在所述左次级数组指针的次级节点数组中寻找所述左相邻叶节点，根据找到的所述右次级数组指针和链路记录，不断在所述右次级数组指针的次级节点数组中寻找所述右相邻叶节点；

[0100] S450，进行所述当前叶节点的左链接和右链接；所述左链接为将所述当前叶节点的数组指针写入所述当前叶节点的左相邻叶节点的数组头部；所述右链接为将所述当前叶节点的右相邻叶节点的数组指针写入所述当前叶节点的数组头部。

[0101] 具体的，如图6所示，一条数据的数组树(A树)链路创建完成后，将进行该叶节点(数组树A树末端数组)链接，即将相邻叶节点从一个方向进行链接(单向，叶节点之间的链接方向与关键字的数字的读取顺序有关)。而寻找相邻叶节点则采用回逆的方法：

[0102] 1、从叶节点开始，根据链路记录(LinkPath)，在其父节点中寻找有效的左右相邻数组指针(以当前下标为准，右邻：下标递增；左邻：下标递减)，若未找到，则继续向上的父节点寻找，直至找到为止，否则返回空。

[0103] 2、找到相邻的父节点后，从该节点向下寻找相邻的有效数组指针(右邻：0下标递增；左邻：最大下标递减)，直至链接到叶节点为止，然后，将叶节点的内存地址写入数组的头部(如图：B数组的地址写入A(C)数组头部，C(A)数组的地址写入B数组的头部)。

[0104] 请参照图9和图10，本发明还提供包括一种数组树数据快速查找方法(用于查找数据库，所述数据库采用如上所述的数组树数据储存方法进行数据存储)，所述一种数组树数据快速查找方法的步骤包括：

[0105] S510，获取储存数据的关键字，对所述关键字进行长度一致预处理，设置所述关键字的关键字数组；

[0106] S520，按照数字排列特征和关键字数组所对应的树形结构链路依次检索结构数组内的次级数组指针；

[0107] S530，判断所述当前结构数组内的次级数组指针是否为空；

[0108] 若是，则执行步骤S540，返回空值；

[0109] S550，判断所述当前结构数组的长度是否小于所述关键字中的数字；

[0110] 若是，则执行步骤S560，返回空值；

[0111] S570，判断所述当前结构数组是否为叶节点数组；

[0112] 若是，则执行步骤S580，返回所述当前结构数组内的数据地址指针及数组下标作为查找结果。

[0113] 具体的，根据关键字和关键字的数字排列特征，获取关键字数组，A树算法中，索引占用内存：每个数组指针占用4个字节，B树算法中，该算法每个树节点至少定义两个指针(左树和右树)、一个关键字及数据地址，A树算法中索引占用的内存空间约为A树算法中索引占用的内存空间的1/3。A树算法的检索效率只与关键字的长度L有关，即O(L)，且A树算法的检索效率大幅优于二分算法(8～10倍效率)。数据地址只存在于叶节点数组中，非叶节点的逻辑运算均在内存中实现，所以能够大幅减少磁盘的IO操作，提高检索效率。在A树结构中，非叶节点是单向顺序链接，所以能够方便的实现范围查找、数据遍历、数据分页等功能。更具体的，当检索到数组指针为空或当前数组长度小于指定的长度时，会被认为没有检索到，将返回空值。若检索到ID最后一位数字且数组内的指针不为空，则返回该指针，即数据的内存地址(或数据集编号)。本技术方案仅就基本的数据结构和功能进行了基本的描述和论证，在实际应用中，可根据需要进行优化和完善。

[0114] 请参照图9和图10，基于本发明的一种数组树数据快速查找方法的第一实施例，进一步的，所述关键字包括开始关键字和结束关键字；本发明的一种数组树数据快速查找方法的第二实施例中，

[0115] 所述S560的步骤，包括如下步骤：

[0116] S561，返回所述开始关键字和所述结束关键字分别对应的叶节点数组指针及叶节点数组下标；

[0117] S562，从所述开始关键字对应的叶节点数组下标开始，依次读取所述开始关键字对应的叶节点数组内的有效数据地址指针；

[0118] S563，在所述开始关键字对应的叶节点数组读取完毕后，根据所述开始关键字对应的叶节点数组头部的相邻叶节点数组指针，继续读取相邻叶节点数组中有效数据地址指针，直至读取到所述结束关键字对应的叶节点数组中所述结束关键字对应的叶节点数组下标；

[0119] S564，返回所有读取的有效数据地址指针作为查找结果。

[0120] 具体的，由于数组树(A树)结构下的末端数组存储的是数据的内存地址，且按关键字Key顺序链接排列的，所以数组树(A树)算法可以进行范围查询，依次读取所述开始关键字对应的叶节点数组内的有效数据地址指针便是按照关键字中数字的读取顺序进行读取。查询的基本过程：查找到开始和结束关键字的数组树(A树)地址后，顺序获取它们之间的数组地址即可得到查询的结果，查询的流程如图10所示。

[0121] 本发明还包括一种计算机可读储存介质，所述计算机可读存储介质上存储有计算机程序，所述计算机程序被处理器执行时实现一种数组树数据储存方法或一种数组树数据快速查找方法。

[0122] 具体的，示意源代码(Pascal语言，在delphi7环境下测试通过)

[0123]

[0124]

[0125]

[0126]

[0127]

[0128]

[0129]

[0130]

[0131] 请参照图11和图12，在其中一个实施例中

[0132] 1、进行等值检索速度对比测试

[0133] 选择二分算法进行对比(二分算法代表了以分治算法的检测效率0(logn))。测试方法：分别在1000、10000、……、50000000条数据集中进行检索，检索数据为随机生成100000(或1000000)条数据(数组形式)

[0134] 10000次循环查找测试记录如下：

[0135]

[0136] (注：测试平台为CPU：Intel E2301 V3；内存：8GB；不同的平台可能测试记录会有略有不同)

[0137] 测试结论：10000次随机检索中，A树算法在不同的数据集中，效率较二分算法快8～10倍。

[0138] 2、索引内存空间消耗(理论计算，不包括堆栈空间)

[0139] A树算法中，索引占用内存：每个数组指针占用4个字节，

[0140] C＝(n×4+(n/10)×8)×(1+10+100+....+10L)/10L

[0141] C＜5n

[0142] 式中：C表示A树算法中索引占用的内存；n为记录数；n×4表示数据地址占用的内存；(n/10)×8表示数组头部内存空间；L表示关键字的长度。

[0143] B树算法中，该算法每个树节点至少定义两个指针(左树和右树)、一个关键字及数据地址，按32位操作系统计算，则B树索引占用的内存可计算为：

[0144] D＝n×4×4＝16n

[0145] 式中：D表示A树算法中索引占用的内存。

[0146] 因此：A树算法中索引占用的内存空间约为A树算法中索引占用的内存空间的1/3。

[0147] 在其中一个实施例中，数组树算法可以实现检索数据集的动态删除，即将ID检索数据指针清空，若该数组内指针均为空，则删除该树组，同时将相邻的数组进行链接。由于创建A树索引时，使用的是动态数组，导致创建索引时效率不高，当然，为追求A树索引创建效率，也可以使用静态数组。

[0148] 在其中一个实施例中，数组树算法同样可以适用于关键字ID重复的数据集，此时，需要定义以下数据结构即可，检索效率不变，但内存资源的消耗会对应增加。

[0149]

[0150] 通过以上的实施方式的描述，本领域的技术人员可以清楚地了解到上述实施例方法可借助软件加必需的通用硬件平台的方式来实现，当然也可以通过硬件，但很多情况下前者是更佳的实施方式。基于这样的理解，本发明的技术方案本质上或者说对现有技术做出贡献的部分可以以软件产品的形式体现出来，该计算机软件产品存储在如上所述的一个计算机可读存储介质(如ROM/RAM、磁碟、光盘)中，包括若干指令用以使得一台终端设备进入本发明各个实施例所述的方法。

[0151] 在本说明书的描述中，参考术语“一实施例”、“另一实施例”、“其他实施例”、或“第一实施例～第X实施例”等的描述意指结合该实施例或示例描述的具体特征、结构、材料或者特点包含于本发明的至少一个实施例或示例中。在本说明书中，对上述术语的示意性表述不一定指的是相同的实施例或示例。而且，描述的具体特征、结构、材料、方法步骤或者特点可以在任何的一个或多个实施例或示例中以合适的方式结合。

[0152] 需要说明的是，在本文中，术语“包括”、“包含”或者其任何其他变体意在涵盖非排他性的包含，从而使得包括一系列要素的过程、方法、物品或者系统不仅包括那些要素，而且还包括没有明确列出的其他要素，或者是还包括为这种过程、方法、物品或者系统所固有的要素。在没有更多限制的情况下，由语句“包括一个……”限定的要素，并不排除在包括该要素的过程、方法、物品或者系统中还存在另外的相同要素。

[0153] 上述本发明实施例序号仅仅为了描述，不代表实施例的优劣。

[0154] 以上仅为本发明的优选实施例，并非因此限制本发明的专利范围，凡是利用本发明说明书及附图内容所作的等效结构或等效流程变换，或直接或间接运用在其他相关的技术领域，均同理包括在本发明的专利保护范围内。