暂无图片
暂无图片
暂无图片
暂无图片
暂无图片
文档 / 一种基于bw树的超长字符串跨页索引方法_CN117453853A_南大通用.pdf
一种基于bw树的超长字符串跨页索引方法_CN117453853A_南大通用.pdf
刺史武都
43
12页
1次
2024-06-11
免费下载
(19)国家知识产权局
(12)发明专利申请
(10)申请公布号
(43)申请公布日
(21)申请号 202311800100 .8
(22)申请日 2023 .12.26
(71)申请人 天津南大通用数据技术股份有限公
司
地址 300384 天津市滨海新区华苑产业区
海泰发展六道6号海泰绿色产业基地J
座
(72)发明人 邰超　单槱　
(74)专利代理机构 天津企兴智财知识产权代理
有限公司 12226
专利代理师 石倩倩
(51)Int.Cl .
G06F
16/31
(2019 .01)
G06F
16/33
(2019 .01)
(54)发明名称
一种基于BW树的超长字符串跨页索引方法
(57)摘要
本发明提供了一种基于BW树的超长字符串
跨页索引方法，索引方法包括，分割超长字符串
并存储在单个索引页内；检查索引页的当前状
态，判断是否存在插入、修改或删除的需求；创建
增量节点记录所需的更改信息，将增量节点安全
集成到索引结构中，并确保更新的原子性；接收
查询请求后进行数据搜索查询，优先检查增量节
点，随后根据数据量的变化动态调整索引结构，
同时进行并发控制与范围搜索优化；直到所有字
符串部分完成索引并更新相关索引页，同时保持
整个索引结构的一致性和准确性，展示整个字符
串的内容。本发明有益效果：提高索引命中率和
数据库系统的吞吐量，同时防止检索时发生死锁
或过度的性能开销。
权利要求书2页 说明书6页 附图3页
CN 117453853 A
2024.01.26
CN 117453853 A
1 .一种基于BW树的超长字符串跨页索引方法，其特征在于：索引对象设备包括原子记
录存储、面向多核CPU、面向新型储存设备flash，超长字符串超过单页大小限制将触发索
引，索引方法包括以下步骤：
T1、索引初始化：分割超长字符串并存储在单个索引页内；
T2、判断更新需求：检查索引页的当前状态，判断是否存在插入、修改或删除的需求，若
存在需求则转到T3，否则转到T4；
T3、页的更新：创建增量节点记录所需的更改信息，将增量节点安全集成到索引结构
中，并确保更新的原子性；
T4、页的搜索、导航和结构调整：接收查询请求后进行数据搜索查询，优先检查增量节
点，随后根据数据量的变化动态调整索引结构，同时进行并发控制与范围搜索优化；
T5、索引完成：直到所有字符串部分完成索引并更新相关索引页，同时保持整个索引结
构的一致性和准确性，展示整个字符串的内容。
2 .根据权利要求1所述的一种基于BW树的超长字符串跨页索引方法，其特征在于：所述
T3具体包括以下步骤：
T31、创建一个新的增量节点，该增量节点类型为“插入”，“修改”，“删除”三种类型之
一；
T32、将该增量节点的下一节点指向被修改的基页；
T33、通过原子比较交换指令，更新映射表中基页所在PID的值。
3 .根据权利要求1所述的一种基于BW树的超长字符串跨页索引方法，其特征在于：所述
T4包括以下步骤：
T41、通过索引树查询，遍历所有增量节点是否包含相关数据，若包含则转到T43，否则
转到T42；
T42、在基页中搜索，同时根据数据量的增减，适时执行页分裂或页合并操作；
T43、结束搜索并返回找到的数据。
4 .根据权利要求3所述的一种基于BW树的超长字符串跨页索引方法，其特征在于：所述
T41中当增量节点过多时需合并增量节点，合并增量节点包括以下步骤：
S1、申请新的页空间记为新页；
S2、遍历原页，将原页中所有索引项，最大键值和最小键值，以及右兄弟节点信息写入
新页；
S3、通过原子比较交换指令，更新映射表中原页所在PID的值；
S4、释放原页空间。
5 .根据权利要求3所述的一种基于BW树的超长字符串跨页索引方法，其特征在于：所述
T42中的搜索包括范围搜索，通过相连兄弟指针实现范围搜索。
6 .根据权利要求3所述的一种基于BW树的超长字符串跨页索引方法，其特征在于：所述
T42中的页分裂包括以下步骤：
A1、申请新的页空间记新页；
A2、从被分裂页中选取一个合适的键值作为分裂键值，将所有大于该分裂键值的索引
项复制到新页，新页的右兄弟页指向被分裂页的右兄弟页，并将新页添加到映射表；
A3、创建“分裂增量节点”，通过追加的方式，更新被分裂的页；
权　利　要　求　书
1/2 页
2
CN 117453853 A
2
A4、创建“索引增量节点”，通过追加的方式，更新被分裂页的父页。
7 .根据权利要求3所述的一种基于BW树的超长字符串跨页索引方法，其特征在于：所述
T42中的页合并包括以下步骤：
H1、创建“删除增量节点”，通过追加的方式，更新被合并的页；
H2、创建“合并增量节点”，通过追加的方式，更新被合并页的左页；
H3、创建“索引删除增量节点”，通过追加的方式，更新被合并页的父页。
8 .根据权利要求5所述的一种基于BW树的超长字符串跨页索引方法，其特征在于：在所
述T4中，并发控制通过序列化原子比较交换指令操作处理增量节点的添加、页分裂和页合
并，以管理并发和冲突；
在索引页中记录最小和最大键值以及指向右兄弟页的指针实现范围搜索优化。
9 .根据权利要求8所述的一种基于BW树的超长字符串跨页索引方法，其特征在于：在并
发控制的环境下，当多个原子比较交换指令需要被序列化处理时，包括以下步骤被采用以
确保操作的一致性和完整性：
W1、所有线程在执行自己的操作之前，检查是否存在待完成的序列化原子比较交换指
令，若存在转到W2，否则转到W3；
W2、线程优先执行这些序列化指令；
W3、系统确保所有的序列化原子比较交换指令已被成功执行并完成后，所有线程继续
执行它们各自的操作。
10 .一种计算机可读取存储介质，存储有计算机程序，其特征在于：所述计算机程序被
处理器执行时实现权利要求1‑9任一项所述的一种基于BW树的超长字符串跨页索引方法。
权　利　要　求　书
2/2 页
3
CN 117453853 A
3
of 12
免费下载
gbasepatent南大通用
【版权声明】本文为墨天轮用户原创内容，转载时必须标注文档的来源（墨天轮），文档链接，文档作者等基本信息，否则作者和墨天轮有权追究责任。如果您发现墨天轮中有涉嫌抄袭或者侵权的内容，欢迎发送邮件至：contact@modb.pro进行举报，并提供相关证据，一经查实，墨天轮将立刻删除相关内容。

评论