[發明專利]一種大數據索引的排序方法

有效

• 申請號: 201410040926.3
• 申請日: 2014-01-28
• 公開（公告）號: CN103745008A
• 公開（公告）日: 2014-04-23
• 發明（設計）人: 石冰;韓立新
• 申請（專利權）人: 河海大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 南京蘇高專利商標事務所(普通合伙) 32204
• 代理人: 柏尚春

1.一種大數據索引的排序方法,其特征在于：包括以下步驟：

步驟1：根據索引關鍵字的取值范圍將索引初始劃分為Size/Alpha個區間，其中，為規?？刂茀?，Alpha為分布密度差異系數，N為索引項的總數，同時根據索引項的取值范圍和劃分的區間數平均地設定每個區間索引關鍵字值的上限；

步驟2：根據步驟1中的每個區間索引關鍵字值的上限創建區間表，所述區間表管理區間的動態劃分，每個區間內索引項最多不超過Size個，在每個區間內建立一個用于存放區間內索引項的二叉排序樹，并設定二叉排序樹的索引項插入方法；

步驟3：在每個二叉排序樹中的每個結點中設定一個索引項數組，并設定索引項數組中存儲索引項的上限以及索引項存儲的順序，所述索引項存儲的順序按索引項關鍵字從小到大的順序從左至右依次存儲；

步驟4：讀取索引文件的數據，根據索引項關鍵字的值在區間表中查詢區間，將讀取的索引項按照步驟2中設定的二叉排序樹的索引項插入方法插入到對應區間的二叉排序樹上；

步驟5：按照區間的順序對每個區間中相應的二叉排序樹進行中序遍歷，同時對每個結點中的索引項數組順序讀取，并將讀取的結果保存在排序文件中。

2.根據權利要求1所述的一種大數據索引的排序方法,其特征在于：所述步驟2中二叉排序樹的索引項插入方法為：

步驟201：判斷查詢到的區間內是否已滿，如果區間已滿，在查詢到的區間的右側創建一個新的區間，將原區間中的二叉排序樹的右子樹從原二叉排序樹中分裂出來并移至新的區間中，同時將原二叉排序樹的樹根移至其左子樹的右脊梁的末端，并根據平衡要求調整二叉排序樹；如果查找到的區間未滿，則進行下一步操作；

步驟202：將讀取的索引項的索引關鍵字的值與二叉排序樹的樹根中存儲的索引關鍵字值進行比較，如果讀取的索引項的索引關鍵字值比二叉排序樹的樹根中的索引項數組中最左端的索引關鍵字的值小，則將讀取的索引項遞歸地插入到二叉排序樹的左子樹中；相反，如果讀取的索引關鍵字值比二叉排序樹的樹根中的索引項數組中最右端的索引關鍵字的值大，則將讀取的索引項值遞歸地插入到二叉排序樹的右子樹中；如果讀取的索引關鍵字的值介于索引項數組中最左端的索引關鍵字的值和最右端的索引關鍵字的值之間，查看二叉排序樹的樹根中設置的索引項數組中存儲的數據是否已滿，如果未滿，則按照索引項存儲的順序將讀取索引項插入到索引項數組中；如果已滿，則將二叉排序樹的樹根進行結點分裂，產生一個新結點，把索引項數組中左半邊索引項留在原結點，右半邊索引項存儲到新結點中；如果左子樹中存儲的索引項數多于右子樹中存儲的索引項數，則將新結點移至根的右子樹的左脊梁的末端，否則將原結點移至根的左子樹的右脊梁的末端。

3.根據權利要求2所述的一種大數據索引的排序方法,其特征在于：所述步驟201中根據平衡要求調整二叉排序樹的方法為：如果二叉排序樹的左子樹上存儲的索引項的數量大于二叉排序樹的右子樹存儲的索引項的數量與兩倍的索引項數組中存儲索引項的上限之和，就將二叉排序樹的左子樹的右脊梁末端結點做二叉排序樹的根，將原根移至其右子樹的左脊梁的末端；如果二叉排序樹的的右子樹上存儲的索引項的數量大于二叉排序樹的左子樹存儲的索引項的數量與兩倍的索引項數組中存儲索引項的上限之和，就將二叉排序樹的右子樹的左脊梁末端結點做二叉排序樹的根，將原根移至其左子樹的右脊梁的末端。