[發明專利]一種面向云存儲的分層索引方法與檢索方法

在審

• 申請號: 201610975816.5
• 申請日: 2016-11-07
• 公開（公告）號: CN106599040A
• 公開（公告）日: 2017-04-26
• 發明（設計）人: 郭皓明;王之欣;魏閆艷;龐廓;田霂;焉麗
• 申請（專利權）人: 中國科學院軟件研究所
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 北京君尚知識產權代理事務所(普通合伙)11200
• 代理人: 邱曉鋒

1.一種面向云存儲的分層索引方法，其步驟包括：

第一步：在master節點建立全局索引，在worker節點建立局部分頁索引；在全局索引中記錄各數據存儲分頁與數據屬性取值之間的映射關系；在數據分頁索引中記錄數據存儲分頁中IO指針與數據屬性取值之間的映射關系；

第二步：數據記錄D在寫入過程中，根據兩層索引之間的組織關系進行索引內容的維護與更新：首先根據分發策略以及數據記錄D中主鍵的取值選擇對應的worker節點，worker節點完成本地數據記錄寫入后，維護本地分頁索引信息并將其返回給master節點；master節點根據數據在worker節點中分頁存儲的信息維護全局索引中的內容。

2.如權利要求1所述的方法，其特征在于，所述全局索引由屬性散列-屬性取值散列-節點映射表三個層次構成；所述局部分頁索引由屬性散列-屬性取值散列-倒排位圖索引三個層次構成。

3.如權利要求1所述的方法，其特征在于，通過全局索引與局部分頁索引兩個層次的索引來存儲屬性取值與存儲位置的映射關系信息；在全局索引與局部索引中根據屬性取值的范圍建立區間，將數據記錄的屬性取值對應在某一個特定的區間，該區間包含該取值；同時，將取值區間與存儲映射信息建立散列對關系。

4.如權利要求1所述的方法，其特征在于，所述全局索引將屬性取值區間與存儲分頁建立散列對關系，一個特定屬性取值區間與一個節點映射表對應；節點映射表由一組節點和對應的分頁計數隊列構成；通過全局索引，快速定位到數據的存儲worker節點和分頁位置。

5.如權利要求1所述的方法，其特征在于，所述局部分頁索引將屬性取值區間與數據記錄在分頁存儲中的行號rowId建立對應關系；同時屬性取值區間中將rowId轉化為以位圖的方式記錄，以提高檢索效率；該位圖為一個二進制字節流，其中第i個位為1時，表示在當前存儲分頁中rowId為i行的數據記錄的屬性取值命中當前取值區間。

6.如權利要求1所述的方法，其特征在于，數據記錄D的寫入過程包括以下步驟：

第一步：在數據記錄D寫入過程中，master節點接收到請求，首先提取數據記錄D主鍵對應的屬性取值，根據分發策略為當前數據記錄D選擇一個對應的worker節點，并將寫入請求發送給該worker節點；

第二步：worker節點接收到該寫入請求后，在本地存儲分頁中寫入該數據記錄并獲得其行號rowId，而后打開局部分頁索引；局部分頁索引提取D中的屬性，將其取值與對應的取值區間range對比，選擇命中的取值區間；然后打開其中的位圖bitmap，將bitmap中與rowId對應的位置為1；完成全部屬性索引處理后，將存儲分頁與worker節點信息返回給master節點；

第三步：master節點接收到返回的存儲信息后，提取D中的屬性，并打開全局索引，依次將屬性取值與對應的取值區間range對比，選擇命中的取值區間，打開其中的節點映射表；在節點映射表中選擇與前述worker對應的分頁計數隊列；從分頁計數隊列中提取與返回信息中存儲分頁對應的分頁計數對象；將其計數器加1；完成全部屬性索引處理后，實現數據寫入過程中的索引更新，并返回操作結果。

7.如權利要求1所述的方法，其特征在于，在數據記錄D更新過程中索引維護的步驟如下：

第一步：master節點接收到數據更新操作請求，根據D中主鍵取值綁定其存儲worker節點，并將請求發送給該worker節點；

第二步：worker節點接收到請求，根據數據記錄局部分頁索引中的內容提取原始數據記錄D，根據請求內容將其變更為D’；變更完畢后，首先在局部分頁索引中D對應的屬性取值區間中的位圖進行修改；將該位圖中與D存儲行號對應的位置為0；而后，將D’對應的取值區間位圖進行修改，將該位圖中與D’存儲行號對應的位置為1；完成上述操作后，將D與D’的存儲分頁信息，返回給master節點；

第三步：master節點接收到返回的存儲分頁信息后，首先在全局索引中將D對應的取值區間中的節點映射表打開。從其中分頁計數隊列中提取與D所屬分頁對應的計數器，將其減1；而后將D’對應的取值區間中的節點映射表打開，從其中分頁計數隊列中提取與D’所屬分頁對應的計數器，將其加1；完成上述操作后，返回操作信息。