一种数据索引构建方法、装置、电子设备及存储介质转让专利
申请号 : CN202110609042.5
文献号 : CN113254451B
文献日 : 2022-04-19
发明人 : 胡广银
申请人 : 北京城市网邻信息技术有限公司
摘要 :
权利要求 :
1.一种数据索引构建方法,其特征在于,包括:针对每个数据对象,获取每个所述数据对象的有效时间段和索引相关信息,所述索引相关信息至少包含所述数据对象的身份标识;
基于每个所述数据对象的索引相关信息,以及各个数据对象的有效时间段之间的占用关系,构建时间序列索引树;
其中,所述时间序列索引树包括二叉查找树、平衡二叉树、B+树中的任意一种,所述时间序列索引树中每个节点为一个时间段,且作为节点的各个时间段互不重叠,每个所述数据对象的有效时间段对应于至少一个节点;
所述构建时间序列索引树为平衡二叉树或者二叉查找树的情况下,基于每个所述数据对象的索引相关信息,以及各个数据对象的有效时间段之间的占用关系,构建时间序列索引树,包括:针对任一新增的目标数据对象,获取所述时间序列索引树中待分裂的目标节点,对所述目标节点进行分裂处理,得到多个分裂节点,并根据所述目标数据对象的索引相关信息更新每个第一节点的节点信息,在所述时间序列索引树中删除所述目标节点,并插入每个所述分裂节点。
2.根据权利要求1所述的方法,其特征在于,在所述时间序列索引树为平衡二叉树的情况下,所述基于每个所述数据对象的索引相关信息,以及各个数据对象的有效时间段之间的占用关系,构建时间序列索引树的步骤,还包括:对插入新节点的时间序列索引树进行平衡处理。
3.根据权利要求1所述的方法,其特征在于,所述目标节点包括在所述目标数据对象的有效时间段的开始时间占用的节点,和/或所述目标数据对象的有效时间段结束时间占用的节点;所述目标节点与所述目标数据对象的有效时间段之间的占用关系包括以下至少一种:目标节点左侧段被所述目标数据对象的有效时间段占用、目标节点右侧段被所述目标数据对象的有效时间段占用、目标节点中间段被所述目标数据对象的有效时间段占用。
4.根据权利要求3所述的方法,其特征在于,所述对所述目标节点进行分裂处理,得到多个分裂节点的步骤,包括:
针对任一目标节点,获取所述目标节点中被所述目标数据对象的有效时间段占用的目标时间段,以所述目标时间段作为冲突节点,并以所述冲突节点作为一个分裂节点;
获取所述目标节点中除所述目标时间段,且被所述目标时间段分割的每个其他时间段,分别作为一个分裂节点;
所述在所述时间序列索引树中删除所述目标节点,并插入每个所述分裂节点的步骤,包括:
以所述冲突节点继承所述目标节点在所述的时间序列索引树中的位置;
对于每个其他分裂节点,在所述时间序列索引树中选择所述其他分裂节点的插入位置,并插入所述其他分裂节点,所述其他分裂节点为除所述冲突节点之外的分裂节点。
5.根据权利要求4所述的方法,其特征在于,所述对于每个其他分裂节点,在所述时间序列索引树中选择所述其他分裂节点的插入位置,并插入所述其他分裂节点的步骤,包括:响应于所述占用关系为目标节点左侧段被所述目标数据对象的有效时间段占用,从所述目标节点或者所述目标节点的右侧相邻节点上选择所述其他分裂节点的插入位置,并插入所述其他分裂节点;
响应于所述占用关系为目标节点右侧段被所述目标数据对象的有效时间段占用,从所述目标节点或者所述目标节点的左侧相邻节点上选择所述其他分裂节点的插入位置,并插入所述其他分裂节点;
响应于所述占用关系为目标节点中间段被所述目标数据对象的有效时间段占用,对于所述冲突节点左侧的其他分裂节点,从所述目标节点或者所述目标节点的左侧相邻节点上选择所述其他分裂节点的插入位置,对于所述冲突节点右侧的其他分裂节点,从所述目标节点或者所述目标节点的右侧相邻节点上选择所述其他分裂节点的插入位置,并插入每个所述其他分裂节点。
6.根据权利要求1所述的方法,其特征在于,所述方法还包括:针对任一被取消的历史数据对象,在所述时间序列索引树中搜索包含所述历史数据对象的身份标识的节点,作为所述历史数据对象的分布节点;
在每个所述分布节点中,删除所述历史数据对象的索引相关信息;
在所述时间序列索引树中,对所述历史数据对象的开始时间节点以及结束时间节点进行消解合并处理,以减少所述时间序列索引树中非必要节点的数量;
其中,所述历史数据对象的开始时间节点为所述历史数据对象的开始时间所在的节点,所述历史数据对象的结束时间节点为所述历史数据对象的结束时间所在的节点。
7.根据权利要求6所述的方法,其特征在于,所述在所述时间序列索引树中,对所述历史数据对象的开始时间节点以及结束时间节点进行消解合并处理的步骤,包括:针对已删除所述索引相关信息的开始时间节点,响应于所述开始时间节点与其一左侧相邻节点所包含的信息一致,将所述开始时间节点与所述开始时间节点的左侧相邻节点合并,并将所述开始时间节点的右子树移动至合并后节点的右孩子上;
针对已删除所述索引相关信息的结束时间节点,响应于所述结束时间节点与其一右侧相邻节点所包含的信息一致,将所述结束时间节点与所述结束时间节点的右侧相邻节点合并,并将所述结束时间节点的左子树移动至合并后节点的左孩子上。
8.根据权利要求1所述的方法,其特征在于,所述方法还包括:响应于针对所述时间序列索引树中在指定时间节点之前的无效数据对象的删除请求,在所述时间序列索引树中搜索出全部所述无效数据对象涉及的节点,作为无效节点,并依次删除每个所述无效节点;
和/或,
响应于针对所述时间序列索引树中在指定时间节点之前的无效数据对象的删除请求,在所述时间序列索引树中搜索出全部所述无效数据对象涉及的节点,作为无效节点,并将全部无效节点作为整体完整删除;
其中,所述无效数据对象为有效时间段在所述指定时间节点之前,且至少覆盖一个节点的数据对象。
9.根据权利要求8所述的方法,其特征在于,所述在所述时间序列索引树中搜索出全部所述无效数据对象涉及的节点,作为无效节点,并将全部无效节点作为整体完整删除的步骤,包括:
按中序搜索在所述时间序列索引树中搜索所述无效节点;
响应于在所述时间序列索引树中的任一目标范围内,所述无效节点的分布满足第一分布条件,将所述目标范围内的全部无效节点合并为一个节点;
响应于在所述目标范围内,所述无效节点的分布满足第二分布条件,将所述目标范围内的全部无效节点合并为一个节点,并将第四部分移动至第二部分的最左子树上;
其中,所述目标范围包括所述时间序列索引树本身,或者所述时间序列索引树中的任一以第一部分的根节点为根节点的子树;所述第一分布条件包括所述目标范围内缺失第二部分、第三部分、第四部分中的任意至少一个;所述第二分布条件包括所述目标范围内同时包含第二部分、第三部分、第四部分;所述第一部分、第二部分、第三部分和第四部分按照从上到下的顺序依次连接,且所述第一部分和所述第三部分为无效节点区域,所述第二部分和所述第四部分为有效节点区域,所述无效节点区域中包含至少一个无效节点,所述有效节点区域中包含至少一个有效节点,所述有效节点为所述时间序列索引树中除所述无效节点之外的任一其他节点,如果所述第一部分的根节点为所述时间序列索引树的根节点,所述目标范围为所述时间序列索引树本身,如果所述第一部分的根节点不是所述时间序列索引树的根节点,所述目标范围为所述时间序列索引树中的任一以所述第一部分的根节点为根节点的子树。
10.根据权利要求1所述的方法,其特征在于,在所述时间序列索引树为B+树的情况下,所述基于每个所述数据对象的索引相关信息,以及各个数据对象的有效时间段之间的占用关系,构建时间序列索引树的步骤,包括:针对任一新增的目标数据对象,响应于所述目标数据对象的有效时间段与所述时间序列索引树中叶子节点包含的关键字不适配,根据目标数据对象的有效时间段,以及每个所述叶子节点的有效时间段,获取所述时间序列索引树中待分裂的目标节点,并在所述目标节点中获取需要分裂的目标关键字;
根据所述目标数据对象的有效时间段,将所述目标关键字分裂为冲突关键字和初始关键字并存储于所述目标节点中;
响应于所述目标节点大于B+树的阶数,则按照B+树的构造算法分裂所述目标节点。
11.根据权利要求10所述的方法,其特征在于,所述方法,还包括:针对任一被取消的历史数据对象,在所述时间序列索引树中搜索包含所述历史数据对象的身份标识的关键字;
针对任一所述关键字,删除所述关键字中包含的所述历史数据对象的索引相关信息。
12.根据权利要求11所述的方法,其特征在于,所述方法,还包括:针对任一已删除所述历史数据对象的索引相关信息的关键字,所述关键字与其相邻关键字中包含的信息一致,删除所述关键字;
针对删除所述关键字的节点,响应于所述节点小于B+树的阶数的一半,则按照B+树的构造算法合并所述节点。
13.一种数据索引构建装置,其特征在于,包括:基础数据获取模块,用于针对每个数据对象,获取每个所述数据对象的有效时间段和索引相关信息,所述索引相关信息至少包含所述数据对象的身份标识;
TSI树构建模块,用于基于每个所述数据对象的索引相关信息,以及各个数据对象的有效时间段之间的占用关系,构建时间序列索引树,构建时间序列索引树为平衡二叉树或者二叉查找树的情况下,包括:针对任一新增的目标数据对象,获取所述时间序列索引树中待分裂的目标节点,对所述目标节点进行分裂处理,得到多个分裂节点,并根据所述目标数据对象的索引相关信息更新每个第一节点的节点信息,在所述时间序列索引树中删除所述目标节点,并插入每个所述分裂节点;
其中,所述时间序列索引树包括二叉查找树、平衡二叉树、B+树中的任意一种,所述时间序列索引树中每个节点为一个时间段,且作为节点的各个时间段互不重叠,每个所述数据对象的有效时间段对应于至少一个节点。
14.一种电子设备,其特征在于,包括:处理器、存储器及存储在所述存储器上并可在所述处理器上运行的计算机程序,所述计算机程序被所述处理器执行时实现如权利要求1至
12中任一项所述的数据索引构建方法的步骤。
15.一种计算机可读存储介质,其特征在于,所述计算机可读存储介质上存储有计算机程序,所述计算机程序被处理器执行时实现如权利要求1至12中任一项所述的数据索引构建方法的步骤。
说明书 :
一种数据索引构建方法、装置、电子设备及存储介质
技术领域
背景技术
服务器)的实现。
数据,而库存系统相对来说一个写少读多的系统,聚合大量的数据可以来说非常影响搜索
的性能。而TSDB(Time Series Database,时间序列数据库)由于底层采用的是LSM(Log‑
Structured‑Merge,日志结构合并)树,适合写多读少的场景,不太适合进行实时搜索的读
多写少的应用场景。ES(Elasticsearch),弹性搜索(例如分布式搜索和数据分析引擎)是基
于Luence实现的倒排索引。Lucene在查询过程中是基于Segment (段),但是索引过程的文
档不会被立即合并到可供查询的Segment上,这对于库存检索的实时性有一定的阻碍。
发明内容
述数据对象的有效时间段对应于至少一个节点。
述数据对象的有效时间段对应于至少一个节点。
行时实现如第一方面所述的数据索引构建方法的步骤。
面所述的数据索引构建方法的步骤。
对象的索引相关信息,以及各个数据对象的有效时间段之间的占用关系,构建时间序列索
引树;其中,所述时间序列索引树包括二叉查找树、平衡二叉树、B+树中的任意一种,所述时
间序列索引树中每个节点为一个时间段,且作为节点的各个时间段互不重叠,每个所述数
据对象的有效时间段对应于至少一个节点。从而基于TSI实现时间序列搜索的高性能和实
时性。
附图说明
具体实施方式
明中的实施例,本领域普通技术人员在没有作出创造性劳动前提下所获得的所有其他实施
例,都属于本发明保护的范围。
衡二叉树、B+树中的任意一种,所述时间序列索引树中每个节点为一个时间段,且作为节点
的各个时间段互不重叠,每个所述数据对象的有效时间段对应于至少一个节点。
进行搜索。而且,通过TSI树在空间上实现了时间上的连续。
对象的索引相关信息,以及各个数据对象的有效时间段之间的占用关系,构建时间序列索
引树;其中,时间序列索引树可以包括但不限于二叉查找树(BST,Binary Search Tree)、平
衡二叉树(AVL)、 B+树中的任意一种。
点值不小于根节点的值。如下是一颗BST。当需要快速查找时,将数据存储在BST是一种常见
的选择,因为此时查询时间取决于树高,平均时间复杂度是O(lgn)。然而,BST可能长歪而变
得不平衡,此时 BST退化为链表,时间复杂度退化为O(n)。为了解决这个问题,引入了平衡
二叉树。
除可能破坏二叉树的平衡,此时需要通过一次或多次树旋转来重新平衡这个树。当插入数
据时,最多只需要1次旋转(单旋转或双旋转);但是当删除数据时,会导致树失衡,AVL需要
维护从被删除节点到根节点这条路径上所有节点的平衡,旋转的量级为O(lgn)。B+树也是
多路平衡查找树,B+树在B树的基础上,将非叶节点改造为不存储数据的纯索引节点,进一
步降低了树的高度;此外将叶节点使用指针连接成链表,范围查询更加高效。
么该人员针对某一任务的计划工作时间段则可以理解为相应人员针对该任务的数据对象
的有效时间,等等。
理解为一个时间段,而且节点数据结构,也即节点信息可以包括但不限于Eventid(数据对
象的身份标识/事件的身份标识,例如库存系统中的商品使用订单标识)列表、数据对象所
占用目标的数量(例如,该节点对应的每个订单所消耗的商品数量)、数据对象的有效时间
段(例如订单服务的时间段)以及摘要数据(业务的个性化数据,例如订单详情信息、订单发
起方的信息等)等部分。
构建时间序列索引树时,可以根据不同类型的时间序列索引树的构建规则,确定每个数据
对象所对应的节点,以及各个数据对象所对应的节点的节点类型(例如是根节点、叶子节
点,还是索引节点等),同时确定各个节点之间的连接关系,对此本发明实施例不加以限定。
树中待分裂的目标节点;
以及所述目标数据对象的有效时间段完全覆盖的各个节点;
作为数据对象的订单的有效时间段也具有任意性。因此,在构建时间序列索引树的过程中,
插入新的节点的有效时间段也具有任意性,也即后插入的节点的有效时间段可能会占用时
间序列索引树中已有节点的部分有效时间段,从而容易导致时间序列索引树的构建过程中
节点的分裂。
也即新增的目标数据对象的有效时间段占用时间序列索引树中部分已有节点的有效时间
段,那么为了避免多个各个节点之间存在冲突,则需要对已有节点进行分裂处理。
2021年4月26日至2021年4月28日,此时则可以将该已有节点的有效时间段拆分为2021年4
月26日至2021年4月 27日、2021年4月28日两个时间段,也即可以将时间序列索引树中该已
有节点分裂为两个节点,其中一个节点的有效时间段为2021年4月26日至 2021年4月27日,
另一个节点的有效时间段为2021年4月28日,相应地可以调整分裂后各个节点的节点信息,
保证有效时间段为2021年4月26日至2021年4月27日的节点的节点信息包含新增的租车订
单的索引相关信息、以及分裂前节点对应的订单的索引相关信息,而对于有效时间段为
2021年4 月28日的节点,其节点信息则可以包含分裂前节点对应的订单的索引相关信息。
占用关系,获取所述时间序列索引树中待分裂的目标节点,进而对每个目标节点进行分裂
处理,得到多个分裂节点,并根据所述目标数据对象的索引相关信息更新每个第一节点的
节点信息,所述第一节点包括所述分裂节点,以及所述目标数据对象的有效时间段完全覆
盖的各个节点,在分裂完成后则可以在所述时间序列索引树中删除所述目标节点,并插入
每个所述分裂节点;此后,为了保证平衡二叉树的平衡性,则可以进一步对插入新节点的时
间序列索引树进行平衡处理。
的时间序列索引树进行平衡处理,等等。
裂处理,而仅更新其节点信息即可,也即将新增的目标数据对象的索引相关信息更新至其
有效时间段完全覆盖的各个节点的节点信息中。而对于被目标数据对象的有效时间段部分
覆盖(也即目标数据对象的有效时间段占用节点的部分有效时间段)的各个节点而言,由于
其中不同时间段所对应的数据对象有所不同,也即其中部分时间段对应目标数据对象,而
另外一部分并不对应目标数据对象,因此则需要对相应节点进行分裂处理,以保证同一节
点中各个时间段所对应的数据节点一致。也即,在本发明实施例中,可以基于上述原则获取
针对当前的目标数据对象,时间序列索引树中待分裂的目标节点。
相应地将新增的目标数据对象的索引相关信息更新 (例如直接加入等)至相应分裂节点的
节点信息中。
此本发明实施例不加以限定。
树中待分裂的目标节点;
以及所述目标数据对象的有效时间段完全覆盖的各个节点;
发明实施例不加以限定。
述目标节点与所述目标数据对象的有效时间段之间的占用关系包括以下至少一种:目标节
点左侧段被所述目标数据对象的有效时间段占用、目标节点右侧段被所述目标数据对象的
有效时间段占用、目标节点中间段被所述目标数据对象的有效时间段占用。
可以看出,构建过程节点分裂的过程一般会发生在新增数据对象(例如新订单)的有效时间
段(例如新订单的服务时间段)的开始时间(startTime)所占用的节点,和/或结束时间
(endTime)占用的节点上,其余被该新增数据对象的有效时间段完全覆盖的节点均不会发
生节点分裂,而是仅更新相关的节点信息即可。
点。相应地,如果目标数据对象的有效时间段的结束时间刚好与某一已有节点的结束时间
一致,那么则可以不将该目标数据对象的有效时间段的结束时间占用的节点作为目标节
点。
对象的索引相关信息设置该节点的节点信息,而无需对其中已有节点进行分裂处理。而如
果目标数据对象的有效时间段刚好完全覆盖至少一个已有节点,那么则可以相应根据该目
标数据对象的索引相关信息更新其完全覆盖的各个已有节点的节点信息,也无需进行分裂
处理。
间段(例如目标数据对象的有效时间段)占用而冲突,故原有节点ab段需要分裂成ac段和(c
+1)b段。(2)目标节点右侧cb 段被新的有效时间段占用而冲突,故原有节点ab段需要分裂
成a(c‑1)段和cb 段。(3)目标节点中间cd段被新的有效时间段占用而冲突,故原有节点ab
段需要分裂成a(c‑1)段、cd段和(d+1)b段。另外,对于图2C中的(4)所示则为一种被新的有
效时间段完全覆盖的节点,此时该节点无需分裂,仅需进行节点信息的更新。
为2021年4月25日,那么此时2021 年4月20日至2021年4月30日则可以分裂为2021年4月20
日至2021年 4月25日、2021年4月26日至2021年4月30日两个时间段。
裂节点;
裂节点。
点的位置尽可能靠近树根,因为该节点被占用的次数较多,可能也是用户搜索的热点时间。
所以在本发明实施例中,可以将冲突节点继承原节点的位置,并且由原节点分裂出新的其
他分裂节点,并在时间序列索引树中选择每个新生成的其他分裂节点的合适的位置并插
入。
位置,并插入所述其他分裂节点;
位置,并插入所述其他分裂节点;
相邻节点上选择所述其他分裂节点的插入位置,对于所述冲突节点右侧的其他分裂节点,
从所述目标节点或者所述目标节点的右侧相邻节点上选择所述其他分裂节点的插入位置,
并插入每个所述其他分裂节点。
情况。从图2D所示的三种相对位置的分析中,不难看到一定可以从原节点或者原节点的左
侧相邻节点(Left Neighbor Node)上找到合适位置去存储新生成的其他分裂节点,从而达
到解决冲突的目的。
节点的左孩子节点或右孩子节点插入时间序列索引树,对于情况(3),则可以将新生成的其
他分裂节点作为左侧相邻节点的左孩子节点,或作为原节点的左孩子节点插入时间序列索
引树,等等。
TSI中的相对位置详细分析得到如图2E所示的三种情况。
决冲突的目的。
节点的左孩子节点或右孩子节点插入时间序列索引树,对于情况(3),则可以将新生成的其
他分裂节点作为右侧相邻节点的左孩子节点,或作为原节点的右孩子节点插入时间序列索
引树,等等。
插入位置,对于所述冲突节点右侧的其他分裂节点,则可以参照上述的图2E,从所述目标节
点或者所述目标节点的右侧相邻节点上选择所述其他分裂节点的插入位置,并插入每个所
述其他分裂节点。
发明实施例不加以限定。此外,对于其中的原节点也可以替换或经分裂为上述的冲突节点。
知道,虽然数据对象在TSI上是连续的,但其由于节点分裂可能分布在多个节点上。因此TSI
中的节点删除过程,也即从 TSI中删除某一历史数据对象的全部信息需要分成以下四步:
对象的相关信息删除之后,假设该历史数据对象的开始时间节点的节点信息与其一相邻节
点的节点信息完全一致,那么则可以将两者合并,而如果合并后的节点的节点信息由于其
一相邻节点的节点信息一致,那么则可以进一步将两者合并,直至不存在相邻节点与当前
合并后的节点的节点信息一致;当然,也可以仅在该历史数据对象的开始时间节点的节点
信息与其一相邻节点的节点信息完全一致的情况下,将两者合并,而不进一步判断合并后
的节点是否需要进一步合并,对此本发明实施例不加以限定。
侧相邻节点合并,并将所述开始时间节点的右子树移动至合并后节点的右孩子上;
侧相邻节点合并,并将所述结束时间节点的左子树移动至合并后节点的左孩子上。
程中并非完全实现节点分裂的逆即可。
节点(图2F中的Node)与其左侧相邻节点(图2F 中的LeftNeighborNode)在TSI的相对位置
分析可以包括三种情况,其中,在历史数据对象的索引相关信息从节点信息中删除后,该历
史数据对象的开始时间节点与相应左侧相邻节点的节点信息一致。
Node1的左侧相邻节点,Node2是Node1的右侧相邻节点。在实际的TSI结构中,
LeftNeighborNode会存在于Node的左子树或者Node是LeftNeighborNode的右子树上的最
左子树的叶子节点。也即,某一节点Node的LeftNeighborNode可能与该节点为父子关系、祖
孙关系,也可能间隔百辈或者千辈以上,对此本发明实施例不加以限定。
将right节点移动作为合并后节点的右孩子节点;对于图2F中的情况(3),可以将Node合并
至其LeftNeighborNode,并将 Node的右子树,也即right节点移动至合并后节点的右孩子
上,并连接在右子树之后。此外,在消解合并后,根据需求也可以对时间序列索引树进行平
衡处理,对此本发明实施例不加以限定。
侧相邻节点(也即与该结束时间节点的节点信息一致的右侧相邻节点)合并,并将所述开始
时间节点的左子树移动至合并后节点的左孩子上。
无效节点,并依次删除每个所述无效节点;
无效节点,并将全部无效节点作为整体完整删除;
上可能存在大量用户关注度较低的无效信息,即过去的一段时间的数据对象可能在接下来
的实时搜索过程中失去了意义。因此,基于系统优化和性能考虑,在本发明实施例中,还可
以进一步考虑选择基准时间对TSI树进行剪枝操作。
左子树上;
范围内缺失第二部分、第三部分、第四部分中的任意至少一个;所述第二分布条件包括所述
目标范围内同时包含第二部分、第三部分、第四部分;所述第一部分、第二部分、第三部分和
第四部分按照从上到下的顺序依次连接,所述第一部分的根节点为所述目标范围的根节
点,且所述第一部分和所述第三部分为无效节点区域,所述第二部分和所述第四部分为有
效节点区域,所述无效节点区域中包含至少一个无效节点,所述有效节点区域中包含至少
一个有效节点,所述有效节点为所述时间序列索引树中除所述无效节点之外的任一其他节
点,如果所述第一部分的根节点为所述时间序列索引树的根节点,所述目标范围为所述时
间序列索引树本身,如果所述第一部分的根节点不是所述时间序列索引树的根节点,所述
目标范围为所述时间序列索引树中以所述第一部分的根节点为根节点的子树。
为了避免上述问题优选地可以采用方案(2)中将全部无效节点作为整体完整删除的方式。
具体地,可以按中序搜索BaseTime时全部已完成的Event涉及的节点列表CoverNodes,其中
包含全部的无效节点,进而可以对CoverNodes进行剪枝合并操作。此外,根据需求也可以将
中序搜索替换为前序搜索或者后序搜索,对此本发明实施例不加以限定。
种情况:当TSI树中缺少第二部分、第三部分、第四部分(也即图2G中的2,3,4部分)其中任意
至少一个时,则可以将全部无效节点合并为一个节点即可;而当2,3,4均存在时,则只要将
全部无效节点合并为一个节点,并且将第4部分移到第2部分的最左子树上就可。
任意一个子树,且该子树的根节点为其中第1 部分的根节点。
以及每个所述叶子节点的有效时间段,获取所述时间序列索引树中待分裂的目标节点,并
在所述目标节点中获取需要分裂的目标关键字;
构建的TSI树的IO耗时会成为搜索过程的瓶颈,因此在本发明实施例中,可以进一步对TSI
树进行优化。
外部存储设备中。B+树结构较之于AVL,有以下优势:
裂。
要从原节点上分裂并存放在原节点上,再对该叶子节点做B+树进行阶数约束操作即可。
可以根据目标数据对象的有效时间段,以及每个所述叶子节点的有效时间段,获取所述时
间序列索引树中待分裂的目标节点,并在所述目标节点中获取需要分裂的目标关键字,进
而根据所述目标数据对象的有效时间段,将所述目标关键字分裂为冲突关键字和初始关键
字并存储于所述目标节点中,在节点分裂完成之后,进一步则可以根据B+树的阶数约束进
行调整操作。例如,当单节点的关键字数量大于B+树的阶数时,节点就需要分裂成两个节
点,并依次递归其父节点、祖辈节点直至整棵树重新满足B+树的定义,那么此时则可以检查
目标节点是否大于B+树的阶数,如果是则可以按照B+树的构造算法分裂目标节点,并且可
以依次递归其父节点、祖辈节点直至整棵树重新满足B+树的定义。
现。那么如何在一历史数据对象被取消时删除其在TSI上的数据呢?在本发明实施例中,受
益于B+树的存储结构,此时TSI 中索引相关信息的删除过程也是非常简单明了的。
份标识的关键字,删除该关键字中包含的该历史数据对象的索引相关信息。
取消历史数据对象后,该已删除相应历史数据对象的索引相关信息的Key与其相邻Key上的
信息是否完全一致。如果一致,则可以删除该关键字。而对于删除关键字的节点而言,则可
以进一步对其进行B+树的阶数约束操作。也即,此时可以检查相应节点是否小于B+树的阶
数的一半,如果是则可以按照B+树的构造算法合并相应节点,直至整棵树重新满足B+树的
定义,对此本发明实施例不加以限定。
以限定。
(13‑inch,2019,Four Thunderbolt 3 ports)
述数据对象的有效时间段对应于至少一个节点。
取所述时间序列索引树中待分裂的目标节点;
所述分裂节点,以及所述目标数据对象的有效时间段完全覆盖的各个节点;
取所述时间序列索引树中待分裂的目标节点;
所述分裂节点,以及所述目标数据对象的有效时间段完全覆盖的各个节点;
述目标节点与所述目标数据对象的有效时间段之间的占用关系包括以下至少一种:目标节
点左侧段被所述目标数据对象的有效时间段占用、目标节点右侧段被所述目标数据对象的
有效时间段占用、目标节点中间段被所述目标数据对象的有效时间段占用。
冲突节点作为一个分裂节点;
突节点之外的分裂节点。
并插入所述其他分裂节点;
并插入所述其他分裂节点;
点上选择所述其他分裂节点的插入位置,对于所述冲突节点右侧的其他分裂节点,从所述
目标节点或者所述目标节点的右侧相邻节点上选择所述其他分裂节点的插入位置,并插入
每个所述其他分裂节点。
的数量;
点合并,并将所述开始时间节点的右子树移动至合并后节点的右孩子上;
点合并,并将所述结束时间节点的左子树移动至合并后节点的左孩子上。
涉及的节点,作为无效节点,并依次删除每个所述无效节点;
涉及的节点,作为无效节点,并将全部无效节点作为整体完整删除;
上;
缺失第二部分、第三部分、第四部分中的任意至少一个;所述第二分布条件包括所述目标范
围内同时包含第二部分、第三部分、第四部分;所述第一部分、第二部分、第三部分和第四部
分按照从上到下的顺序依次连接,且所述第一部分和所述第三部分为无效节点区域,所述
第二部分和所述第四部分为有效节点区域,所述无效节点区域中包含至少一个无效节点,
所述有效节点区域中包含至少一个有效节点,所述有效节点为所述时间序列索引树中除所
述无效节点之外的任一其他节点,如果所述第一部分的根节点为所述时间序列索引树的根
节点,所述目标范围为所述时间序列索引树本身,如果所述第一部分的根节点不是所述时
间序列索引树的根节点,所述目标范围为所述时间序列索引树中的任一以所述第一部分的
根节点为根节点的子树。
数据对象的有效时间段,以及每个所述叶子节点的有效时间段,获取所述时间序列索引树
中待分裂的目标节点,并在所述目标节点中获取需要分裂的目标关键字;
方法实施例的各个过程,且能达到相同的技术效果,为避免重复,这里不再赘述。
达到相同的技术效果,为避免重复,这里不再赘述。其中,所述的计算机可读存储介质,如只
读存储器(Read‑Only Memory,简称ROM)、随机存取存储器(Random Access Memory,简称
RAM)、磁碟或者光盘等。
且还包括没有明确列出的其他要素,或者是还包括为这种过程、方法、物品或者装置所固有
的要素。在没有更多限制的情况下,由语句“包括一个……”限定的要素,并不排除在包括该
要素的过程、方法、物品或者装置中还存在另外的相同要素。
前者是更佳的实施方式。基于这样的理解,本发明的技术方案本质上或者说对现有技术做
出贡献的部分可以以软件产品的形式体现出来,该计算机软件产品存储在一个存储介质
(如ROM/RAM、磁碟、光盘)中,包括若干指令用以使得一台终端(可以是手机,计算机,服务
器,空调器,或者网络设备等)执行本发明各个实施例所述的方法。
在本发明的启示下,在不脱离本发明宗旨和权利要求所保护的范围情况下,还可做出很多
形式,均属于本发明的保护之内。
功能究竟以硬件还是软件方式来执行,取决于技术方案的特定应用和设计约束条件。专业
技术人员可以对每个特定的应用来使用不同方法来实现所描述的功能,但是这种实现不应
认为超出本发明的范围。
一种逻辑功能划分,实际实现时可以有另外的划分方式,例如多个单元或组件可以结合或
者可以集成到另一个系统,或一些特征可以忽略,或不执行。另一点,所显示或讨论的相互
之间的耦合或直接耦合或通信连接可以是通过一些接口,装置或单元的间接耦合或通信连
接,可以是电性,机械或其它的形式。
网络单元上。可以根据实际的需要选择其中的部分或者全部单元来实现本实施例方案的目
的。
对现有技术做出贡献的部分或者该技术方案的部分可以以软件产品的形式体现出来,该计
算机软件产品存储在一个存储介质中,包括若干指令用以使得一台计算机设备(可以是个
人计算机,服务器,或者网络设备等)执行本发明各个实施例所述方法的全部或部分步骤。
而前述的存储介质包括:U盘、移动硬盘、ROM、RAM、磁碟或者光盘等各种可以存储程序代码
的介质。
盖在本发明的保护范围之内。因此,本发明的保护范围应以权利要求的保护范围为准。