[發明專利]對具有非易失性存儲器的系統的較快樹扁平化

有效

• 申請號: 201210438667.0
• 申請日: 2012-09-14
• 公開（公告）號: CN102999429A
• 公開（公告）日: 2013-03-27
• 發明（設計）人: D·J·波斯特;V·科麥爾尼斯基
• 申請（專利權）人: 蘋果公司
• 主分類號: G06F12/02
• 分類號: G06F12/02;G06F3/06
• 代理公司: 中國國際貿易促進委員會專利商標事務所 11038
• 代理人: 宋海寧

1.一種用于較快樹扁平化的方法，所述方法包括：

檢測樹目前可用的存儲量低于預定閾值，其中所述樹存儲非易失存儲器(“NVM”)的邏輯空間和物理地址之間的邏輯至物理映射；

在所述樹上移動至少兩個滑動窗口；

當所述至少兩個滑動窗口在所述樹上移動時，保持對應于所述至少兩個滑動窗口的至少兩個最小跨度；

確定所述至少兩個滑動窗口已在所述樹上完成移動；以及

至少部分地基于所述至少兩個最小跨度之間的比較，選擇扁平化所述樹的條目集合。

2.如權利要求1所述的方法，其中所述至少兩個滑動窗口各自包含不同數量的樹的條目。

3.如權利要求1或2所述的方法，其中所述條目集合包括邏輯上相鄰的條目。

4.如權利要求1或2所述的方法，其中維護所述至少兩個最小跨度，包括：

對于所述至少兩個滑動窗口的每一個，向運行計數器添加由所述滑動窗口新包含的條目的跨度；以及

從所述運行計數器減去不再由所述滑動窗口包含的條目的跨度。

5.如權利要求4所述的方法，進一步包括：

比較所述運行計散器和在易失性存儲器中保存的最小跨度；以及

確定所述運行計數器是否低于所述最小跨度；

響應于確定所述運行計數器低于所述最小跨度，將所述運行計數器替換為所述最小跨度。

6.如權利要求5所述的方法，進一步包括：響應于確定所述運行計時器大于所述最小跨度，保持所述最小跨度。

7.如權利要求1或2所述的方法，其中所述選擇包括：確定所述至少兩個最小跨度的哪一個具有較小值。

8.如權利要求1或2所述的方法，其中所述至少兩個滑動窗口是在所述樹上并行移動以及在所述樹上順序地移動中的至少一個。

9.一種系統，包括：

非易失存儲器(“NVM”)；

用于存儲包括多個條目的樹的易失性存儲器，其中所述樹提供所述NVM的邏輯空間和物理地址之間的邏輯至物理映射；以及

包括控制電路的存儲器接口，該控制電路經操作以：

檢測樹目前可用的存儲量低于預定閾值；

移動滑動窗口經過樹的多個條目，其中所述滑動窗口包括預定數量的樹的條目；

確定所述滑動窗口包含的條目集合具有等于所述條目集合中條目數量的跨度；

擴展由所述滑動窗口包含的預定數量的條目，以產生擴展滑動窗口；以及

向所述多個樹條目的至少一部分應用所述擴展滑動窗口。

10.如權利要求9所述的系統，其中所述控制電路可操作以NVM條帶大小的倍數來擴展滑動窗口的所述預定數量的條目。

11.如權利要求9或10所述的系統，其中所述控制電路可操作以擴展所述滑動窗口以對準條帶邊界。

12.如權利要求9或10所述的系統，其中所述控制電路可操作以：

確定由所述擴展滑動窗口產生的運行計數器的值是否等于預定值；以及

響應于確定由所述擴展滑動窗口產生的運行計數器的值等于預定值，選擇由所述擴展滑動窗口產生的樹的條目集合以用于樹扁平化。

13.如權利要求12所述的系統，其中響應于確定由所述擴展滑動窗口產生的運行計數器的值不等于預定值，所述控制電路可操作以選擇由所述滑動窗口產生的樹的條目集合以用于樹扁平化。

14.如權利要求13所述的系統，進一步包括總線控制器，用于和所述NVM通信，以及其中所述控制電路可操作以：

指引所述總線控制器從NVM讀取對應于所述條目集合的數據；

在易失存儲器中保存所述數據；以及

指引所述總線控制器將所述數據依次編入到NVM的超級塊。

15.一種用于訪問非易失存儲器(“NVM”)的存儲器接口，所述存儲器接口包括：

第一檢測器，用于檢測易失存儲器中存儲的樹的當前可用的存儲量低于預定閾值；

第二檢測器，用于檢測匹配滑動窗口的樹的第一多個條目；

插入器，用于在優先級隊列中嘗試插入和所述第一多個條目相關的參數；以及

移動器，用于在所述樹中將所述滑動窗口向前移動多個條目，其中所述多個條目的數量至少部分地基于所述優先級隊列的當前狀態。