[發明專利]一種基于T-樹的索引優化方法、裝置及存儲介質

有效

• 申請號: 201710548181.5
• 申請日: 2017-07-06
• 公開（公告）號: CN109254962B
• 公開（公告）日: 2020-10-16
• 發明（設計）人: 湯人杰;時家幸;張式勤;張勇;于祥兵;周勛;楊巧節
• 申請（專利權）人: 中國移動通信集團浙江有限公司;中移（蘇州）軟件技術有限公司;中國移動通信集團公司
• 主分類號: G06F16/22
• 分類號: G06F16/22
• 代理公司: 北京路浩知識產權代理有限公司 11002
• 代理人: 王瑩;曹杰

1.一種基于T-樹的索引優化方法，其特征在于，包括：

獲取包含有批量數據的數據塊，所述數據塊的數據量根據T-樹中的索引節點保存的數據量所確定，其中，所述索引節點的索引信息包括所述索引節點保存的數據量；

所述索引信息還包括批量數據緩沖區；根據所述數據塊的最大數值和最小數值與所述索引信息中的索引數值的最大值和最小值的比較結果、以及第一預設規則，生成新的索引節點，具體包括：

若所述最大數值和最小數值對應的取值范圍包含于所述索引數值的最大值和最小值對應的取值范圍之間，則將所述批量數據置于所述批量數據緩沖區中；

將所述批量數據緩沖區中的批量數據的數據數值和所述索引數值合并，并對合并后的數值進行排序；

將所述索引數值的最小值和所述最大數值之間排序后的第一數值作為生成新的索引節點的索引數值；相應的，將所述批量數據緩沖區中的第一數值復制到所述索引數值的存儲空間中；

根據所述新的索引節點和第二預設規則，將所述新的索引節點融入到原始索引中。

2.根據權利要求1所述的方法，其特征在于，所述根據所述數據塊的最大數值和最小數值與所述索引信息中的索引數值的最大值和最小值的比較結果、以及第一預設規則，生成新的索引節點，包括：

若所述最小數值大于所述索引數值的最小值、且所述最大數值大于所述索引數值的最大值，則獲取所述索引節點的右子樹鍵值；

若所述右子樹鍵值大于所述最大數值，將所述右子樹鍵值對應的索引節點作為第二索引節點，相應的，獲取所述第二索引節點的第二索引數值的最大值和最小值，并將所述索引數值的最小值和所述索引數值的最大值分別作為第一索引數值的最小值和最大值；

對所述批量數據進行排序，并將所述第一索引數值的最小值和最大值之間的排序后的批量數據作為第一批量數據，將所述第二索引數值的最小值和最大值之間的排序后的批量數據作為第二批量數據；

分別將所述第一批量數據和所述第二批量數據，作為生成新的第一索引節點的第一索引數值和新的第二索引節點的第二索引數值。

3.根據權利要求2所述的方法，其特征在于，所述方法還包括：

若所述索引節點不存在的右子樹，則獲取所述索引節點的父索引節點；

若所述父索引節點的右子樹鍵值大于所述最大數值，將父索引節點的右子樹對應的索引節點作為第二索引節點，相應的，繼續執行所述獲取所述第二索引節點的第二索引數值的最大值和最小值至所述作為生成新的第一索引節點的第一索引數值和新的第二索引節點的第二索引數值之間的步驟。

4.根據權利要求1所述的方法，其特征在于，所述根據所述新的索引節點和第二預設規則，將所述新的索引節點融入到原始索引中，包括：

將所述新的索引節點的右子樹指針指向所述索引節點的右子樹，將所述索引節點的右子樹指向所述新的索引節點，以將所述新的索引節點融入到原始索引中；

或，

在所述將所述索引節點的右子樹指向所述新的索引節點的步驟之后，若判斷獲知T-樹需要翻轉，則對所述T-樹進行翻轉，以將所述新的索引節點融入到原始索引中。

5.根據權利要求2所述的方法，其特征在于，所述方法還包括：

若所述最大數值和最小數值對應的取值范圍中包含x個索引節點對應的索引數值的取值范圍，且x大于等于預設閾值，則將所述數據塊中的批量數據逐一進行數據索引；

或，

若x小于所述預設閾值，則繼續執行所述則獲取所述索引節點的右子樹鍵值至所述作為生成新的第一索引節點的第一索引數值和新的第二索引節點的第二索引數值之間的步驟。