一种内存数据库KV存储引擎索引的创建方法.pdf

(19)中华人民共和国国家知识产权局(12)发明专利申请(10)申请公布号CN112269786A(43)申请公布日2021.01.26(21)申请号202011201566.2(22)申请日2020.11.02(71)申请人浪潮云信息技术股份公司地址250100山东省济南市高新区浪潮路1036号浪潮科技园S01号楼(72)发明人梁波孙思清张炜刚贾德星张晖高传集(74)专利代理机构济南信达专利事务所有限公司37100代理人郗艳荣(51)Int.Cl.G06F16/22(2019.01)G06F16/23(2019.01)G06F16/2458(2019.01)G06F16/27(2019.01)权利要求书3页说明书7页附图1页(54)发明名称一种内存数据库KV存储引擎索引的创建方法(57)摘要本发明特别涉及一种内存数据库KV存储引擎索引的创建方法。该内存数据库KV存储引擎索引的创建方法，首先在CockroachDB数据库插入ART树，并在ART树的叶子节点增加双向链表，然后基于ART树获取大于某key的节点，并计算出待插入key值对应的插入位置，将待插入key值对应的节点插入到双向链表中，最后遍历Key值范围即可。该内存数据库KV存储引擎索引的创建方法，通过在ART树的叶子节点增加双向链表，实现了key值范围遍历的快速响应以及对CockroachDB的排序规则的支持；通过ART树使用乐观锁机制、双向链表使用CAS无锁算法的方式保证了插入/查询操作时的高性能以及数据的一致性。CN112269786ACN112269786A权利要求书1/3页1.一种内存数据库KV存储引擎索引的创建方法，其特征在于：首先在CockroachDB数据库插入ART树，并在ART树的叶子节点增加双向链表，然后基于ART树获取大于某key的节点，并计算出待插入key值对应的插入位置，将待插入key值对应的节点插入到双向链表中，最后遍历Key值范围即可。2.根据权利要求1所述的内存数据库KV存储引擎索引的创建方法，其特征在于：所述双向链表按照CockroachDB定义的key排序规则进行排序，而不是基于字节序的排序规则。3.根据权利要求1所述的内存数据库KV存储引擎索引的创建方法，其特征在于：用curnode变量表示当前处理节点，用leaf表示记录封装到新建的叶子节点，所述ART树插入流程，包括以下步骤：第一步，将curnode变量设为ART树根节点；第二步，将curnode变量指向节点加锁，判断curnode变量指向节点中是否存在key值的相应子节点，即curnode变量指向节点所在层数作为key值的byte数组下缀，得到的byte值在该节点是否有指针；第三步，如果curnode变量指向节点所在层数与key值byte数组长度一致，先将curnode变量指向节点加锁，将leaf挂载到curnode变量指向节点相应的子节点指针位置，最后将curnode变量指向节点解锁，跳转到第六步；第四步，如果curnode变量指向节点存在相应子节点，将curnode变量指向节点解锁的同时将curnode变量设为curnode变量指向节点对应的子节点，返回第二步；第五步，如果curnode变量指向节点不存在相应子节点，先将curnode变量指向节点加锁，创建内部节点inode，并将inode节点挂载到curnode变量指向节点相应子节点指针位置，最后将curnode变量指向节点解锁的同时将curnode变量指向节点置为inode节点，返回第二步；第六步，结束并返回。4.根据权利要求3所述的内存数据库KV存储引擎索引的创建方法，其特征在于：所述ART树插入是在ART树上创建该记录对应的叶子节点，且ART树使用乐观锁机制，每次curnode变量指向节点解锁失败都返回第一步开始重新执行。5.根据权利要求4所述的内存数据库KV存储引擎索引的创建方法，其特征在于：用curnode变量表示当前处理节点，ART树获取大于某key的节点算法，包括以下步骤：第一步，将curnode变量设为ART树根节点；第二步，将curnode变量指向节点以及curnode变量指向节点所在层数作为key值的byte数组下缀得到的byte值存入栈中，并将curnode变量指向节点加锁；第三步，如果curnode变量指向节点为叶子节点，比较叶子节点key值与查询key值的大小，如果叶子节点key值大于查询key值，则解锁curnode变量指向节点并返回该叶子节点，流程结束；否则，跳转到第六步；第四步，如果curnode变量指向节点所在层数与key值byte数组长度一致，则跳转到第六步；第五步，判断curnode变量指向节点中是否存在key值的相应前缀，即curnode变量指向节点所在层数作为key值的byte数组