[發明專利]一種面向大規模數據的索引方法及其系統

有效

• 申請號: 201210526354.0
• 申請日: 2012-12-07
• 公開（公告）號: CN103870456B
• 公開（公告）日: 2017-03-29
• 發明（設計）人: 李春生;金澈清;周傲英
• 申請（專利權）人: 華東師范大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 上海麥其知識產權代理事務所(普通合伙)31257
• 代理人: 董紅曼

1.一種面向大規模數據的索引方法，其特征在于，包括構建索引結構階段與查詢階段；所述構建索引結構階段根據原始數據生成索引結構；所述查詢階段根據所述索引結構獲得相應的所述原始數據；

其中，所述原始數據至少包括一個由數據元組組成的數據塊；所述索引結構包括葉子層索引與根層索引；所述葉子層索引包含一層葉子層索引文件，所述葉子層索引文件中包含至少一個葉子層數據塊；所述根層索引位于葉子層索引之上，包括中間層索引，所述中間層索引包含至少一層中間層索引文件，所述中間層索引文件中包含至少一個中間層數據塊。

2.如權利要求1所述的面向大規模數據的索引方法，其特征在于，所述構建索引結構階段包括：

步驟一：對所述原始數據的所述數據塊中每一個數據元組排序，輸出至所述葉子層索引；

步驟二：在所述葉子層索引中劃分所述數據元組獲得所述葉子層數據塊，并生成所述葉子層索引文件作為所述葉子層索引，并將所述葉子層索引文件中的葉子層數據塊輸出至所述根層索引；

步驟三：在所述根層索引中根據所述葉子層數據塊獲得所述中間層數據塊，并生成所述中間層索引文件作為所述中間層索引。

3.如權利要求2所述的面向大規模數據的索引方法，其特征在于，所述步驟一中，所述數據元組排序及輸出的過程包括：

步驟A1：利用空間擬合曲線計算所述原始數據中的每一個數據元組的轉換值及所在數據塊的地址信息；

步驟A2：根據所述轉換值利用MapReduce框架對所述數據元組排序，所述排序后的數據元組結合所述地址信息發送至所述葉子層。

4.如權利要求2或3中任意一項或多項所述的面向大規模數據的索引方法，其特征在于，所述步驟三中生成所述中間層索引的過程包括：

步驟B1：獲取所述葉子層索引文件中的每一個所述葉子層數據塊的首個數據元組的所述轉換值及地址信息；

步驟B2：根據所述轉換值與所述地址信息生成所述中間層數據塊，組成所述中間層索引文件作為所述中間層索引。

5.如權利要求4所述的面向大規模數據的索引方法，其特征在于，所述步驟B2后進一步包括：

步驟B3：檢驗所述中間層數據塊的數量是否小于閾值；若小于閾值，則保留所述中間層數據塊并組成所述中間層索引文件，完成建立所述中間層索引；否則，以所述中間層索引文件代替所述步驟B1中的所述葉子層索引文件并重新執行所述步驟B1，生成更高層的中間層索引文件。

6.如權利要求1所述的面向大規模數據的索引方法，其特征在于，所述查詢階段包括：步驟三：獲取查詢條件，并根據所述查詢條件依次查詢所述中間層索引、葉子層索引，獲取所述原始數據的數據塊地址信息；

步驟四：根據所述查詢條件與所述原始數據的數據塊地址信息，獲取相應的數據元組。

7.如權利要求6所述的面向大規模數據的索引方法，其特征在于，所述步驟三中查詢所述索引結構的過程包括：

步驟C1：根據所述查詢條件計算待查詢的數據元組的轉換值范圍；

步驟C2：根據所述轉換值范圍查詢所述中間層索引文件，獲取所述葉子層索引文件的相關葉子層數據塊的地址信息；

步驟C3：根據所述查詢條件與所述葉子層數據塊的地址信息，獲取所述原始數據中相關的數據塊的地址信息；

步驟C4：根據所述查詢條件與所述數據塊的地址信息，獲取相應的數據元組。

8.一種面向大規模數據的索引系統，其特征在于，包括：

原始數據存儲單元(1)，其存儲所述原始數據；

葉子層存儲單元(2)，其與所述原始數據存儲單元(1)連接，存儲所述葉子層索引文件；

中間層存儲單元(3)，其與所述葉子層存儲單元(2)連接，存儲所述中間層索引文件；

葉子層構建單元(4)，其設置在所述原始數據存儲單元(1)與葉子層存儲單元(2)之間，用于讀取所述原始數據并構建所述葉子層索引文件；

中間層構建單元(5)，其設置在所述中間層存儲單元(3)與葉子層構建單元(4)之間，用于讀取所述葉子層索引文件并構建所述中間層索引文件；

查詢單元(6)，其與所述中間層存儲單元(3)連接，用于獲取查詢條件并查詢相應的數據元組。