[發明專利]使用頁結構的數據樹存儲方法、系統和計算機程序產品

有效

• 申請號: 200810131986.0
• 申請日: 2008-07-04
• 公開（公告）號: CN101339538A
• 公開（公告）日: 2009-01-07
• 發明（設計）人: 姜東阮;康貞旭;金珍洙;樸贊益
• 申請（專利權）人: 三星電子株式會社;韓國科學技術院
• 主分類號: G06F12/02
• 分類號: G06F12/02;G06F17/30
• 代理公司: 北京銘碩知識產權代理有限公司
• 代理人: 韓明星;羅延紅

1.一種在閃存裝置中存儲樹數據結構的方法，所述方法包括：

將葉節點和包括指向所述葉節點的指針的索引節點存儲在閃存裝置的同 一頁中，

將葉節點的修改版本和索引節點的修改版本存儲在閃存裝置的新的頁 中，

其中，索引節點的修改版本包括指向所述新的頁的指針，并且修改的葉 節點包括新的鍵值。

2.如權利要求1所述的方法，還包括：以每頁為基礎對閃存裝置進行讀 操作。

3.如權利要求1所述的方法，其中，可存儲在閃存裝置的一頁中的樹結 構的節點的最大數量取決于樹數據結構的高度。

4.如權利要求3所述的方法，其中，樹數據結構的節點的最大大小取決 于樹數據結構中的節點的層次。

5.如權利要求1所述的方法，其中，將葉節點的修改版本和索引節點的 修改版本存儲在閃存裝置的新的頁的方法包括：

如果葉節點滿，則將葉節點劃分為第一葉節點和第二葉節點；

將新的鍵值插入到第一葉節點和第二葉節點中的一個葉節點中；

將第一葉節點和第二葉節點存儲在閃存裝置的各自的新的頁中。

6.如權利要求5所述的方法，其中，將葉節點的修改版本和索引節點的 修改版本存儲在閃存裝置的新的頁中的步驟還包括：

如果索引節點滿，則將索引節點劃分為第一索引節點和第二索引節點；

產生指向第一索引節點和第二索引節點的高層索引節點；

將第一索引節點存儲在新的頁的第一頁中；

將第二索引節點和高層索引節點存儲在新的頁的第二頁中。

7.如權利要求1所述的方法，其中，葉節點的修改版本缺少在原始葉節 點中存在的鍵值。

8.如權利要求1所述的方法，其中，索引節點和葉節點包括來自高層節 點的第一分支的第一索引節點和第一葉節點，其中，包括第二索引節點和第 二葉節點的第二分支與所述第一分支共享所述高層節點；

其中，將葉節點和包括指向葉節點的指針的索引節點存儲在閃存中的同 一頁中的步驟包括：將高層節點、第一葉節點和第一索引節點存儲在第一頁 中；

其中，所述方法還包括：

將所述高層節點、第二葉節點和第二索引節點存儲在第二頁中，并使第 一頁中的高層節點無效。

9.如權利要求8所述的方法，還包括：

將第一頁節點的修改版本存儲在第三頁中，并使第二頁中的高層節點無 效。