[發明專利]一種基于雙層列表結構的容量擴充方法及系統

有效

• 申請號: 201810111712.9
• 申請日: 2018-02-05
• 公開（公告）號: CN108256103B
• 公開（公告）日: 2019-02-05
• 發明（設計）人: 王建民;黃向東;張金瑞;劉昆;曹高飛;王晨
• 申請（專利權）人: 清華大學
• 主分類號: G06F16/22
• 分類號: G06F16/22
• 代理公司: 北京路浩知識產權代理有限公司 11002
• 代理人: 王瑩;吳歡燕

本發明提供一種基于雙層列表結構的容量擴充方法及系統，雙層列表結構的第一層列表為第一數組，第一數組中存儲至少一個數組標識，第二層列表包括至少一個第二數組，每個第二數組用于存儲待存儲的數據，每個第二數組僅與一個數組標識對應，所述方法包括：當每個數組標識對應的第二數組中存儲的數據數量均達到最大值時，則創建一個新的第一數組，新的第一數組的大小大于當前第一數組的大小，并增加第二數組的數量；將當前第一數組中存儲的數組標識拷貝到新的第一數組中，并將當前第一數組替換為新的第一數組，能夠有效減少數據在內存中的拷貝次數，有利于提高容量擴充速度；同時能夠有效減少內存空間的浪費，一定程度上提高了內存空間的利用率。

技術領域

本發明涉及數據管理技術領域，更具體地，涉及一種基于雙層列表結構的容量擴充方法及系統。

背景技術

隨著云計算、互聯網、物聯網等現代技術的不斷發展和成熟，數據的存儲和使用受到了越來越多的關注。數據來源于生活的方方面面，并正在迅速地膨脹變大——企業的生產交易數據、互聯網中人與人的交互信息、物聯網中傳感器回傳的監測數據等等。當前，數據的產生速度越來越快，數據的量也越來越大。

流式計算、數據存儲、數據分析等都是計算機數據管理技術領域的重要技術。隨著數據量的增大，相關技術平臺的研發難度也在不斷上升。其中，列表結構(List)是最常用的一種數據結構。

在多數編程語言中，內存中的列表結構均支持動態容量擴充。但由于擴充算法的局限性，傳統的支持動態容量擴充的內存列表結構在保存海量數據時，會存在擴充速度慢、內存空間浪費的問題。例如，在Java語言中，ArrayList是一種典型的內存列表結構的實現，其在每次容量擴充時都需要對已有數據進行一次復制。此外，其擴充后的容量與當前列表的大小相關，當前列表越大，新擴充的容量就越大。所以，在存儲海量數據時，將會存在較為嚴重的容量擴充速度慢以及內存空間浪費的問題。

有鑒于此，亟需提供一種能夠支持快速容量擴充并能夠有效提高空間利用率的容量擴充方法及系統，以提高數據處理平臺的運行效率。

發明內容

本發明為了克服現有技術中列表結構的容量擴充速度慢且存在嚴重的內存空間浪費的問題，提供一種基于雙層列表結構的容量擴充方法及系統。

一方面，本發明提供一種基于雙層列表結構的容量擴充方法，所述雙層列表結構的第一層列表為第一數組，所述第一數組中存儲至少一個數組標識，所述雙層列表結構的第二層列表包括至少一個第二數組，每個所述第二數組用于存儲待存儲的數據，每個所述第二數組與且僅與一個所述數組標識對應，所述方法包括：

S1，當每個所述數組標識對應的第二數組中存儲的數據數量均達到最大值時，則創建一個新的第一數組，所述新的第一數組的大小大于當前所述第一數組的大小，并增加所述第二數組的數量；

S2，將當前所述第一數組中存儲的數組標識拷貝到所述新的第一數組中，并將當前所述第一數組替換為所述新的第一數組。

優選地，步驟S1中所述當每個所述數組標識對應的第二數組中存儲的數據數量均達到最大值時，則創建一個新的第一數組具體包括：

若當前所述第一數組的大小為n，則所述新的第一數組的大小為n+d，所述d為預設的大小增量；

相應地，新增一個所述第二數組，新增的所述第二數組與所述新的第一數組中的第n+1個數組標識對應。

優選地，所述步驟S1之后還包括：當新增的所述第二數組中存儲的數據數量達到所述最大值時，繼續增加所述第二數組的數量，直至所述第二數組的數量與所述數組標識的數量相等。

優選地，新增的所述第二數組的大小為所述最大值。