[發明專利]一種內存數據庫KV存儲引擎索引的創建方法

有效

• 申請號: 202011201566.2
• 申請日: 2020-11-02
• 公開（公告）號: CN112269786B
• 公開（公告）日: 2023-02-03
• 發明（設計）人: 梁波;孫思清;張煒剛;賈德星;張暉;高傳集
• 申請（專利權）人: 浪潮云信息技術股份公司
• 主分類號: G06F16/22
• 分類號: G06F16/22;G06F16/23;G06F16/2458;G06F16/27
• 代理公司: 濟南信達專利事務所有限公司 37100
• 代理人: 郗艷榮

1.一種內存數據庫KV存儲引擎索引的創建方法，其特征在于：首先在CockroachDB數據庫插入ART樹，并在ART樹的葉子節點增加雙向鏈表，然后基于ART樹獲取大于某key的節點，并計算出待插入key值對應的插入位置，將待插入key值對應的節點插入到雙向鏈表中，最后遍歷Key值范圍即可；

用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節點，返回第二步；

第六步，結束并返回。

2.根據權利要求1所述的內存數據庫KV存儲引擎索引的創建方法，其特征在于：所述雙向鏈表按照CockroachDB定義的key排序規則進行排序，而不是基于字節序的排序規則。

3.根據權利要求1所述的內存數據庫KV存儲引擎索引的創建方法，其特征在于：所述ART樹插入是在ART樹上創建該記錄對應的葉子節點，且ART樹使用樂觀鎖機制，每次curnode變量指向節點解鎖失敗都返回第一步開始重新執行。

4.根據權利要求3所述的內存數據庫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數組下綴，得到的byte值；

如果curnode變量指向節點存在相應前綴，將curnode變量指向節點解鎖的同時將curnode變量設為curnode變量指向節點對應的子節點，返回第二步；

如果curnode變量指向節點不存在相應前綴，將curnode變量指向節點以及curnode變量指向節點所在層數作為key值的byte數組下綴得到的byte值存入棧中，解鎖curnode變量指向節點；

第六步，從棧中彈出curnode變量指向節點和byte值，并將curnode變量指向節點加鎖；

第七步，在curnode變量指向節點中查找大于該byte值的子節點，如果沒有找到，則curnode變量指向節點解鎖并返回第八步；如果找到，則curnode變量指向節點解鎖的同時將curnode變量設為curnode變量指向節點的該子節點；

第八步，判斷curnode變量指向節點是否為葉子節點，若是，則返回該葉子節點，流程結束；若不是，則返回第七步。