[發明專利]索引機制合并方法、搜索方法、裝置及設備

有效

• 申請號: 201310367741.9
• 申請日: 2013-08-21
• 公開（公告）號: CN104424204B
• 公開（公告）日: 2017-08-11
• 發明（設計）人: 朱俊華;楊俊;羅瓊;王偉松
• 申請（專利權）人: 華為技術有限公司
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 北京三高永信知識產權代理有限責任公司11138
• 代理人: 黃厚剛

1.一種存儲裝置，其特征在于，所述存儲裝置包括至少三層存儲單元，第0層存儲單元位于內存中，第i層存儲單元位于閃存中，每層存儲單元包括主數據區，其中：

所述第0層存儲單元中的主數據區為有序搜索樹，當所述第0層存儲單元中存在從數據區時，所述從數據區為有序搜索樹，所述有序搜索樹包括數據記錄和/或頁面記錄；

所述第i層存儲單元中的主數據區為有序搜索樹或有序數組，當所述第i層存儲單元中存在從數據區時，所述從數據區為有序數組，所述有序搜索樹包括頁面記錄，所述有序數組包括數據記錄和/或頁面記錄；

所述數據記錄包括鍵值和記錄值，所述頁面記錄包括鍵值和頁面地址；

當所述第i層存儲單元中存在從數據區L_i’時，所述L_i’為所述第i層存儲單元的第一搜索數據區，所述第i層存儲單元中的主數據區L_i為所述第i層存儲單元的第二搜索數據區；當所述第i層存儲單元中不存在所述L_i’時，所述L_i為所述第i層存儲單元的所述第一搜索數據區；

所述L_i按序保存指向第i+1層存儲單元中的第一搜索數據區的所有頁面對應的頁面記錄；當所述第i+1層存儲單元中的第一搜索數據區為有序搜索樹時，則所述L_i的頁面記錄是無效記錄；

所述L_i’按序保存指向所述L_i的所有頁面對應的頁面記錄；當所述L_i為有序搜索樹時，則所述L_i’的頁面記錄為無效記錄，

其中，所述i為大于0的自然數。

2.一種索引機制合并方法，其特征在于，用于包括有權利要求1所述的存儲裝置的設備中，所述方法，包括：

在所述第i層存儲單元的主數據區L_i達到容量上限后，檢測第i+1層存儲單元的主數據區L_i+1是否正在合并；

若檢測結果為所述L_i+1正在合并，則檢測所述第i+1層存儲單元的從數據區L_i+1’是否已經達到容量上限；

若檢測結果為所述L_i+1’未達到容量上限，則將所述L_i中的數據記錄添加至所述L_i+1’中，將所述L_i+1’中的所有頁面所對應的頁面記錄添加至所述L_i中，合并后的所述L_i為包含有用于指向合并后的所述L_i+1’中的所有頁面所對應的頁面記錄的有序搜索樹，

其中，所述i為大于0的自然數。

3.根據權利要求2所述的方法，其特征在于，在所述檢測L_i+1是否正在合并之前，還包括：

判斷所述L_i+1是否為有序搜索樹以及所述第i+1層存儲單元是否存在從數據區L_i+1’；

若判斷結果為所述L_i+1為有序搜索樹且所述第i+1層存儲單元存在L_i+1’時，則將所述L_i和所述L_i+1’中的數據記錄添加至所述L_i+1中，將所述L_i+1中所有頁面所對應的頁面記錄添加至所述L_i中，合并后的所述L_i為包含有用于指向合并后的所述L_i+1中的所有頁面所對應的頁面記錄的有序搜索樹；

若判斷結果為所述L_i+1不為有序搜索樹時，則執行所述檢測L_i+1是否正在合并的步驟；

在所述檢測L_i+1是否正在合并之后，還包括：

若檢測結果為所述L_i+1未在合并，則將所述L_i中的數據記錄添加至所述L_i+1中，將所述L_i+1中的所有頁面所對應的頁面記錄添加至所述L_i中，合并后的所述L_i為包含有用于指向合并后的所述L_i+1中的所有頁面所對應的頁面記錄的有序搜索樹。