一种基于bw树的超长字符串跨页索引方法_CN117453853A_南大通用.pdf
免费下载
(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
of 12
免费下载
【版权声明】本文为墨天轮用户原创内容，转载时必须标注文档的来源（墨天轮），文档链接，文档作者等基本信息，否则作者和墨天轮有权追究责任。如果您发现墨天轮中有涉嫌抄袭或者侵权的内容，欢迎发送邮件至：contact@modb.pro进行举报，并提供相关证据，一经查实，墨天轮将立刻删除相关内容。
下载排行榜
评论