[發明專利]一種定位頁內存儲空間的方法和設備

在審

• 申請號: 201210395124.5
• 申請日: 2012-10-17
• 公開（公告）號: CN102929979A
• 公開（公告）日: 2013-02-13
• 發明（設計）人: 陳志標;叢強;張宇
• 申請（專利權）人: 華為技術有限公司
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 北京中博世達專利商標代理有限公司 11274
• 代理人: 申健

1.一種定位頁內存儲空間的方法，應用于空閑空間視圖構成的二叉樹結構的頁內存儲空間定位，其特征在于，包括：

在預定的時間周期內對所述空閑空間視圖對應的二叉樹結構中的所有節點進行清掃和更新；

在所述預定的時間周期之外，對經過節點清掃和更新的所述二叉樹結構從根節點開始進行遍歷，直至找到滿足大于或等于待添加字段所需空閑空間的葉節點。

2.根據權利要求1所述的方法，其特征在于，所述對所述空閑空間視圖對應的二叉樹結構中的所有節點進行清掃和更新，包括：

清掃所述空閑空間視圖中的所有節點中存儲內容中的垃圾信息和過期信息，并更新對應節點的空閑空間信息。

3.根據權利要求1所述的方法，其特征在于，所述對經過節點清掃和更新的所述二叉樹結構從根節點開始進行遍歷，包括：

生成與所述空閑空間視圖對應的完整二叉樹結構；

對所述完整二叉樹結構從根節點開始進行遍歷。

4.根據權利要求3所述的方法，其特征在于，所述生成與所述空閑空間視圖對應的完整二叉樹結構，具體包括：

根據公式N＝2^{(pagefactor-3)}，計算得到葉節點的個數，利用所述葉節點的個數生成與所述空閑空間視圖對應的完整二叉樹結構；

其中pagesize＝2^pagefactor，pagesize＝Ph+Pd＝2N+6N，其中，pagesize為內存頁的大小，Ph為頁頭的大小，且所述Ph預定義為2N，Pd為頁數據的大小；所述頁數據由頁視圖和空閑空間視圖構成，其中Pd≥N*sizeof(pageid)+(2*N-1)*1＝6N-1≈6N，其中sizeof(pageid)所占字節大小為4，N*sizeof(pageid)為頁視圖大小，所述頁視圖的大小為4N，(2*N-1)*1為空閑空間視圖大小，這里將Pd近似取值為6N。

5.根據權利要求1～4所述的任一方法，其特征在于，還包括：

生成新的空閑空間視圖；

將所述新的空閑空間視圖的二叉樹結構的根節點與所述空閑空間視圖的二叉樹結構的根節點對應的空閑空間進行比較，并將空閑空間較大的根節點作為所述新的空閑空間視圖的二叉樹結構與所述空閑空間視圖的二叉樹結構共同構成的二叉樹結構的根節點，其中所述新的空閑空間視圖的二叉樹結構的根節點與所述空閑空間視圖的二叉樹結構的根節點分別為所述新的根節點的兩個子節點。

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

在所述空閑空間視圖的空閑頁中添加字段，更新所述空閑頁對應的所述空閑空間視圖的二叉樹結構的葉節點，其中所述空閑頁的地址與所述葉節點的地址相關聯。

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

更新添加字段后的所述空閑空間視圖的二叉樹結構中的同一個父節點下的至少一個子節點，判斷所述父節點下的兩個子節點所指示的剩余空間的大小；

根據剩余空間較大的子節點更新所述父節點所指示的剩余空間。

8.一種頁內存儲空間定位設備，應用于空閑空間視圖構成的二叉樹結構的頁內存儲空間定位，其特征在于，包括：

節點管理單元，用于在預定的時間周期內對所述空閑空間視圖對應的二叉樹結構中的所有節點進行清掃和更新；

遍歷單元，用于在所述預定的時間周期之外，對經過節點清掃和更新的所述二叉樹結構從根節點開始進行遍歷，直至找到滿足大于或等于待添加字段所需空閑空間的葉節點。

9.根據權利要求8所述的設備，其特征在于，所述遍歷單元包括：

節點處理子單元，用于清掃所述空閑空間視圖中的所有節點中存儲內容中的垃圾信息和過期信息，并更新對應節點的空閑空間信息。

10.根據權利要求8所述的設備，其特征在于，所述遍歷單元還包括：

算法子單元，用于生成與所述空閑空間視圖對應的完整二叉樹結構；

遍歷子單元，用于對所述完整二叉樹結構從根節點開始進行遍歷。