一种基于两层art树的数据存储方法_CN113626433B_上海沄熹科技有限公司.pdf
免费下载
(19)国家知识产权局
(12)发明专利
(10)授权公告号
(45)授权公告日
(21)申请号 202110884247 .4
(22)申请日 2021 .08 .03
(65)同一申请的已公布的文献号
申请公布号 CN 113626433 A
(43)申请公布日 2021 .11 .09
(73)专利权人 上海沄熹科技有限公司
地址 200120 上海市浦东新区中国（上海）
自由贸易试验区张东路1158号、丹桂
路1059号2幢305-22室
(72)发明人 梁波 张炜刚 贾德星
(74)专利代理机构 济南信达专利事务所有限公
司 37100
专利代理师 郗艳荣
(51)Int.Cl .
G06F
16/22
(2019 .01)
G06F
16/2453
(2019 .01)
(56)对比文件
CN 101567003 A ,2009 .10 .28
CN 107807932 A,2018 .03 .16
CN 110888886 A ,2020 .03 .17
CN 112269786 A ,2021 .01 .26
CN 112765181 A ,2021 .05 .07
CN 112784120 A ,2021 .05 .11
审查员 肖敬伟
(54)发明名称
一种基于两层ART树的数据存储方法
(57)摘要
本发明特别涉及一种基于两层ART树的数据
存储方法。该基于两层ART树的数据存储方法，按
Key值范围分区的方式拆分数据，使用两级ART树
索引结构，第一级ART索引用于Key值范围分区，
第二级ART索引用于索引范围分区内的数据。该
基于两层ART树的数据存储方法，通过优化存储
引擎的索引结构，提升了存储引擎的性能，解决
了使用原始的一层ART树索引结构带来的索引结
构查询性能随着数据量增大而大幅降低的问题。
权利要求书2页 说明书5页 附图2页
CN 113626433 B
2024.01.19
CN 113626433 B
1 .一种基于两层ART树的数据存储方法，其特征在于：按Key值范围分区的方式拆分数
据，使用两级ART树索引结构，第一级ART索引用于Key值范围分区，第二级ART索引用于索引
范围分区内的数据；
所述范围分区内的数据集是真实的数据集或数据的指针形成的数据集；
包括以下步骤：
第一步，数据库存储引擎刚启动时，创建第一个范围分区，其存储Key值的范围为(MIN，
MAX)，并且使用该范围分区最大值MAX作为Key值，将范围分区挂载到第一层ART树上，
第二步，将待插入的数据挂载到范围分区的第二层ART树上，启动待拆分队列处理线程
作为后台线程，异步优化索引结构；
数据插入流程如下：
S1 .1：查询第一层的ART树，找到大于等于待插入的Key值对应的范围分区，存入变量
curRangeArea中；
S1 .2：判断范围分区curRangeArea的状态，如果状态为“待删除”，则返回S1 .1；
S1 .3：将待插入的数据挂载到范围分区curRangeArea的第二层ART树上；
S1 .4：判断范围分区curRangeArea的状态，如果状态为“正在拆分”，则将数据放入该范
围分区curRangeArea的增量数据队列中，结束并退出，否则跳转到S1 .5；
S1 .5：判断范围分区curRangeArea中数据量是否大于设置的范围分区最大数据量阈值
RANGE_AREA_MAX_KVS，如果不大于，则结束并退出；如果大于，则将范围分区curRangeArea
放入待拆分队列中，结束并退出；
待拆分队列处理线程处理流程如下：
S2 .1：判断当前程序是否正在关闭，如果是，则退出线程；
S2 .2：判断待拆分队列长度，如果长度为0，则沉睡特定时间，然后重新跳转到S2 .2；
S2 .3：从待拆分队列中弹出一个范围分区存储到变量curRangeArea中，修改该范围分
区的状态为“正在拆分”；
S2 .4：遍历范围分区curRangeArea的ART树，并将数据按照Key值的字节序升序存储到
队列Q中，统计队列中数据量存储到变量S中；
S2 .5：计算拆分成的新的范围分区的数量以及每个范围分区的数据量；
新的范围分区的数量N的计算公式如下：
第i个新的范围分区的分配到的数据量Di计算公式如下：
公式中，变量S为范围分区curRangeArea的数据量；变量M为全局参数范围分区最大数
据量RANGE_AREA_MAX_KVS；变量P为每个分区分得的数据量比例；
每个分区分得的数据量比例P的计算公式如下：
权 利 要 求 书
1/2 页
2
CN 113626433 B
2
公式中，变量S指范围分区curRangeArea的数据量；变量M指全局参数范围分区最大数
据量RANGE_AREA_MAX_KVS；变量τ为衰减因子，控制衰减速度，默认配置为10；e为自然常数；
S2 .6：将队列Q中的数据按照顺序插入新的范围分区中；
当第i个新范围分区的数据量等于Di时，将第i个新范围分区最后插入的Key值作为该
范围分区的Key值，将该新范围分区挂载到第一层ART树上，并且停止第i个新范围分区插入
数据，改为向第i+1个新范围分区插入；
S2 .7：将范围分区curRangeArea的状态置为“待删除”；
S2 .8：处理范围分区curRangeArea增量数据队列，对于增量数据队列中的每条记录，首
先判断记录是否在队列Q中，如果存在则跳过，如果不存在，则使用数据插入流程将数据插
入到索引结构中；
S2 .9：删除范围分区curRangeArea，释放该范围分区的空间，跳转到S2.1。
2 .根据权利要求1所述的基于两层ART树的数据存储方法，其特征在于：所述第二步中，
设置作为全局参数RANGE_AREA_MAX_KVS，即范围分区最大数据量阈值；当某个范围分区数
据量超过范围分区最大数据量阈值时，将该范围分区拆解成两个。
权 利 要 求 书
2/2 页
3
CN 113626433 B
3
of 10
免费下载
【版权声明】本文为墨天轮用户原创内容，转载时必须标注文档的来源（墨天轮），文档链接，文档作者等基本信息，否则作者和墨天轮有权追究责任。如果您发现墨天轮中有涉嫌抄袭或者侵权的内容，欢迎发送邮件至：contact@modb.pro进行举报，并提供相关证据，一经查实，墨天轮将立刻删除相关内容。
评论