使用頁結構的數據樹存儲方法、系統和電腦程式產品的製作方法
2023-07-05 04:31:56 1
專利名稱：使用頁結構的數據樹存儲方法、系統和電腦程式產品的製作方法
技術領域：
本申請涉及快閃記憶體裝置及其操作方法，更具體地講，涉及快閃記憶體裝置的數據 存儲方法、系統和電腦程式產品。
背景技術：
快閃記憶體裝置是即使在沒有電源的情況下也能在存儲晶片上保留數據的非易 失性存儲裝置。儘管快閃記憶體裝置通常比例如用作個人計算機(PC)的主存儲器 的動態隨機存取存儲器(DRAM)慢，但是通常比硬碟讀的速度要高並且更 能抵抗衝擊。另外，快閃記憶體裝置通常能夠抵抗來自周圍的沖擊，比如高的壓力 和沸騰的水。因為這些特性，快閃記憶體裝置被廣泛用作用電池操作的裝置中的存 儲單元。
快閃記憶體裝置是電可擦除可編程非易失性存儲裝置。通常的快閃記憶體裝置可按塊 被擦除和被編程。因為通常快閃記憶體裝置相對便宜，所以它們被廣泛用作高容量 固態非易失性存儲器。使用快閃記憶體的典型實例是在數位音樂播放器、數字相機 和蜂窩電話中。快閃記憶體裝置還用作通用串行總線(USB)驅動器，所述USB存 儲器被廣泛用於在計算機之間存儲和傳送數據。
因為硬碟驅動器機械地驅動磁碟以讀/寫數據，通常在結構上限制了硬碟 的操作速度上的增加。為此，已經試圖使用用於高容量存儲器的快閃記憶體來替換 硬碟驅動器。例如，在快閃記憶體中存儲啟動代碼時可增加系統啟動速度。
發明內容
本發明的 一 些實施例提供 一 種用於快閃記憶體的索引方案。 本發明的實施例提供基於包括多頁的快閃記憶體的樹結構的索引方法，所述索 引方法包括將葉節點和與葉節點相關的索引節點存儲在快閃記憶體的同一頁中。
在一些實施例中，每頁存儲高達k個葉節點和/或索引節點，k為正數。
在其他實施例中，以頁為基礎對快閃記憶體裝置進行讀或寫操作。
在一些實施例中，存儲在頁中的葉節點或索引節點的數量取決於樹的高度。
在一些實施例中，索引節點中的最高索引節點是根節點。 在一些實施例中，索引方法還包括對葉節點進行修改。
在一些實施例中，對葉節點進行修改的步驟還包括改變與將被修改的 葉節點相關的索引節點的指針；並把將被修改的葉節點和修改的索引節點存 儲在新的一頁中。
在一些實施例中，索引方法還包括插入新的葉節點。
在一些實施例中，插入新的葉節點的步驟包括改變與新的葉節點相關 的索引節點的指針；並將新的葉節點和與所述新的葉節點相關的索引節點存 儲在新的頁中。
在一些實施例中，插入新的葉節點的步驟還包括確定與新的葉節點相 關的索引節點是否滿；如果與新的葉節點相關的索引節點滿，則將索引節點 劃分為第一索引節點和第二索引節點；產生第一索引節點和第二索引節點的 上層節點。
在一些實施例中，索引方法還包括將新的鍵值插入到葉節點。 在一些實施例中，插入新的鍵值的步驟包括確定將插入新的鍵值的葉 節點是否滿；如果將插入新的鍵值的葉節點滿，則將葉節點劃分為第一葉節 點和第二葉節點；並將新的鍵值插入到第 一葉節點和第二葉節點中的 一個節點中。
在一些實施例中，第 一葉節點和第二葉節點被分別存儲在快閃記憶體中的新的 頁中。
在一些實施例中，插入新的鍵值的步驟還包括確定與新的葉節點相關 的索引節點是否滿；如果與新的葉節點相關的索引節點滿，則將索引節點劃 分為第一索引節點和第二索引節點；產生第一索引節點和第二索引節點的上 層索引節點。
在 一 些實施例中，第 一 索引節點被存儲在與第 一 葉節點和第二葉節點中 的一個節點相同的頁中，第二索引節點與上層索引節點一起被存儲在新的頁 中。
在一些實施例中，索引方法還包括刪除葉節點。
在一些實施例中，刪除葉節點的步驟包括確定與刪除的葉節點相關的 索引節點是否指定另一葉節點；如果與刪除的葉節點相關的索引節點沒有指
定另一葉節點，則刪除索引節點。
在一些實施例中，刪除葉節點的步驟還包括如果樹的根節點具有一個 子節點，則將樹的高度減小l,並將根節點的子節點設置為新的根節點。
在一些實施例中，刪除葉節點的步驟還包括將新的根節點存儲在新的頁中。
在一些實施例中，索引方法基於p樹結構。
在本發明的其他實施例中，系統包括快閃記憶體，包括多頁；處理器，訪問 快閃記憶體，其中，處理器執行上述的索引方法。
本發明的一些實施例提供一種將樹數據結構存儲在快閃記憶體裝置中的方法， 其中，葉節點和包括指向葉節點的指針的索引節點被存儲在快閃記憶體裝置的同一 頁中。例如，當將鍵值添加到葉節點或者從葉節點刪除鍵值時，可將葉節點 的修改版本和索引節點的修改版本存儲在快閃記憶體裝置的新的頁中。索引節點的 修改版本可包括指向所述新的頁的指針。可存儲在快閃記憶體裝置的頁中的樹結構 的節點的最大數量可取決於樹數據結構的高度，並且樹數據結構的節點的最 大大小取決於樹數據結構中的節點的層次。
在一些實施例中，將葉節點的修改版本和索引節點的修改版本存儲在閃 存裝置的新的頁中的步驟可包括如果葉節點滿，則將葉節點劃分為第一葉 節點和第二葉節點；將新的鍵值插入到第 一葉節點和第二葉節點中的 一 個葉 節點中，並將第 一葉節點和第二葉節點存儲在快閃記憶體裝置的各自的新的頁中。 將葉節點的修改版本和索引節點的修改版本存儲在快閃記憶體裝置的新的頁中的步 驟還可包括如果索引節點滿，則將索引節點劃分為第一索引節點和第二索 引節點；產生指向第一索引節點和第二索引節點的高層索引節點；將第一索 引節點存儲在新的頁中的第一頁中；將第二索引節點和高層索引節點存儲在 新的頁中第二頁中。
在一些實施例中，索引節點和葉節點包括來自高層節點的第 一分支的第 一索引節點和第一葉節點，其中，第一分支與第二分支共享高層節點，所述
第二分支包括第二索引節點和第二葉節點。將葉節點和包括指向葉節點的指 針的索引節點存儲在快閃記憶體的同一頁中的步驟可包括將第一葉節點和第一索引
節點存儲在第一頁中。高層節點可被存儲在第一頁中，第二葉節點和第二索 引節點可被存儲在第二頁中。可檢測到從第一葉節點刪除鍵值將導致在第一 葉節點中沒有剩餘鍵值，並且第 一 索引節點不包括其他指向葉節點的指針。 作為響應，第二葉節點的修改版本可被存儲在第三頁中。這可從樹數據結構 刪除高層節點。
本發明的實施例可提供包括被構造為執行上述操作的處理器的系統。進 一步實施例可提供包括被構造為在計算機上執行的電腦程式代碼的計算機 可讀存儲介質，所述電腦程式代碼包括被構造為執行上述操作的計算機程
序代碼。
在另外的實施例中，系統包括快閃記憶體裝置，包含多頁；處理器，與快閃記憶體 裝置相關並被構造為將樹數據結構的葉節點和包括指向所述葉節點的指針的 索引節點存儲在快閃記憶體的同一頁中。處理器可被構造為操作作為固態盤(ssd) 的快閃記憶體裝置。
包括附圖以提供對本發明的進一步理解，並且附圖被包含在說明書的一 部分中並構成說明書的一部分。附圖和描述示出本發明的示例性實施例，並 用於解釋本發明的原理。在附圖中
圖1是示出典型的B+樹結構被存儲在快閃記憶體中的實例的示圖2是示出對B+樹結構中的任何葉節點進行修改然後改變的B+樹被存 儲在快閃記憶體中的實例的示圖3是示出根據本發明的一些實施例的在快閃記憶體中存儲/i-樹的方案的示
圖4是示出根據本發明的一些實施例的修改圖3所示的在快閃記憶體中存儲的 pt-樹的葉節點的方案的概念性示圖5是示出根據本發明的一些實施例的在圖3所述的快閃記憶體中存儲的/x-樹 中插入新的葉節點的方案的概念性示圖6是示出根據本發明的一些實施例的刪除圖3所示的快閃記憶體中存儲的m-樹的葉節點的方案的概念性示圖7是示出根據本發明一些實施例的刪除圖6所示的快閃記憶體中存儲的/x-樹 的葉節點的方案的概念性示圖8是示出存儲在一 頁中的葉節點/索引節點的最大可存儲大小的隨著高
度(H)的增加而改變的示圖9A是示出包括根節點和葉節點的^-樹的實例的示圖9B是示出將鍵值插入在圖9A所示的/x-樹的葉節點中的示例性處理的
示圖9C是示出由圖9B示出的鍵值插入處理導致的改變的y-樹的示圖； 圖10是示出在處理器的控制下將鍵值插入/x-樹的葉節點的處理的流程
圖11A是示出用於描述/x-樹的鍵值刪除方案的p樹的示例的示圖； 圖IIB是示出從圖11A所示的/i-樹的任何葉節點刪除鍵值的示例性處理 的示圖IIC是示出圖IIA所示的g-樹的鍵值刪除處理導致的改變的^-樹結 構的示圖12是示出在處理器的控制下從/x-樹的葉節點刪除鍵值的處理的流程 圖； .
圖13是使用根據本發明 一 些實施例的索引方案的電子裝置的框圖14是示出使用根據本發明一些實施例的索引方案的存儲器系統的框
圖15是使用根據本發明 一 些實施例的索引方案的另 一 電子裝置的框圖。
具體實施例方式
下面將參照附圖來更全面地描述本發明，其中，在附圖中顯示本發明的 實施例。然而，可以以多種不同形式實現本發明，並且不應該將本發明解釋 為限於這裡闡述的實施例。相反，提供這些實施例，從而使本公開徹底和完 整，並完全向對本領域的技術人員傳達本發明的範圍。
在附圖中，為了清楚起見，部件的大小或構造可被理想化或者被放大。 應該理解，當部件被稱作被"連接到"或"結合到"另一部件時，它可被直 接連接到或結合到另一部件或者可存在中間部件。相反，當部件被稱作被"直 接連接到"或"直接結合到"另一部件時，不存在中間部件。相同的標號始 終表示相同的部件。如這裡所使用的，術語"和/或"包括所列出的相關項的 一個或多個的任何和所有結合。應該理解，儘管術語第一、第二、第三等可在這裡被用於描述各種部件、 組件和/或部分，但是這些部件、組件和/或部分不應該限於這些術語。這些術 語僅用於區分一個部件、組件或部分和另一部件、區域或部分。因此，在不 脫離本發明的教導的情況下，下面討論的第一部件、組件或部分可以被稱作 第二部件、組件或部分。
這裡使用的術語僅為了描述具體實施例，而並不意圖限制本發明。如這 裡所使用的單數形式意圖包括複數形式，除非上下文清楚地做出不同的表示。 還應該理解在本說明書中使用的術語"包括"明確說明了存在所述特徵、整 數、步驟、操作、部件和/或組件，並不排除存在或添加一個或多個其他特徵、 整數、步驟、操作、部件、組件和/或其組合。
除非有不同的限定，這裡使用的所有術語(包括科技術語)具有與通常 本發明所屬領域的技術人員所理解的相同含義。還應該理解，比如在常用的 字典裡定義的術語，應該被解釋為與現有技術中的上下文中的含義一致，並 不應該被解釋為理想化的或者非正常的意義，除非在這裡清楚地定義。
貫穿說明書，術語"寫"和"編程"具有相同的含義。
下面將參照示出方法、設備(系統和/或裝置)和/或電腦程式產品的示 意圖來描述本發明的實施例。應該理解示圖的塊以及示圖中塊的結合可被計 算機程序指令實現。向通用計算機、專用計算機和/或其他可編程數據處理設 備的處理器提供這些電腦程式指令以產生機制，從而經過計算機和/或其他 可編程數據處理設備的處理器執行的指令創建用於實現在示圖中指定的功能
/動作的方法(功能性)和/或結構。這些電腦程式指令還可被存儲在知道計 算機或其他可編程數據處理設備以特定方式工作的計算機可讀存儲器中，從 而存儲在計算機可讀存儲器中的指令產生一項包括實現在示圖中指定的功能 和動作的指令的產品。電腦程式指令還可被加載到計算機或其他可編程的 數據處理設備中以使一系列的操作步驟在計算機或其他可編程設備上執行以 產生計算機實現的處理，從而在計算機或其他可編程設備上執行的指令提供 用於實現在示圖中指定的功能/動作的步驟。
因此，本發明可在硬體和/或軟體(包括固件、長駐軟體、微代碼等)中 實現本發明。此外，本發明可採用具有程序代碼(指令)的計算機可用或計 算機可讀存儲介質電腦程式產品的形式，所述程序代碼(指令)由指令執 行系統使用或結合所述指令執行系統使用而在計算機可讀存儲介質上實現。
在本文檔的上下文中，計算機可用或計算機可讀存儲介質可以是包含、存儲 或傳送由指令執行系統、設備或裝置使用或結合所述指令執行系統、設備或 裝置使用的程序。
計算機可用或計算機可讀存儲介質可以是，例如電、磁、光、電磁或半 導體系統、設備或裝置。計算機可讀存儲介質的更具體示例(非窮盡列表)
將包括如下內容可攜式計算機磁碟、隨機存取存儲器(RAM)、只讀存儲 器(ROM)、可擦除可編程只讀存儲器(EPROM或快閃記憶體)、可攜式光學和/或 磁介質(比如閃盤或CD-ROM )。
p樹是修改的B樹的樹結構，並包括葉節點和索引節點。葉節點包括按 升序排列的順序數據(sequential data),即鍵值。索引節點包括鍵值和用於搜 索葉節點中的鍵值的指針。與B樹不同，/x樹具有按順序構成鍊表的葉節點， 從而^樹的鍵值可被順序處理。m樹被廣泛用作訪問存儲在比如硬碟的存儲 介質中的數據或者資料庫的索引。本發明的一些實施例提供新的m樹結構。
圖1是示出在快閃記憶體中存儲典型的B+樹結構的示例。參照圖1， B+樹(a) 高度(H)為3,並具有3個葉節點和3個索引節點。也就是說，標號D、 E 和F表示葉節點，標號B、 C和A表示索引節點。索引節點中最上面的索引 節點A被稱作根節點。如果B+樹的高度是1，則'呀艮節點=葉節點"，如果 B+樹的高度是2或者更多，貝'j "根節點=索引節點"。
每個索引節點包括鍵值和指針。例如，索引節點A包括索引節點B和C 的頁地址P5和P4，索引節點B包括葉節點D和E的頁地址P3和P2。
按快閃記憶體(b )的頁分別將B+樹(a)的索引節點和葉節點進行存儲。通常， 以塊為基礎來擦除快閃記憶體，而以頁為基礎對快閃記憶體進行讀/寫。
圖2是示出對B+樹結構中的任何葉節點進行修改然後將改變的B+樹結 構存儲在快閃記憶體中的示例。通常，在快閃記憶體中，為了將新數據寫在已經寫有數據 的單元中必須執行擦除操作。如果不進行擦除操作而對新數據進行寫操作， 則新數據必須被寫在已經被擦除的新頁中。因此，為了將鍵值插入到B+樹(c ) 的葉節點F中或者從B+樹(c)的葉節點F刪除鍵值，必須在快閃記憶體(d)的新 頁P7中寫入修改的葉節點F，。索引節點C必須被修改為索引節點C，以指定 葉節點F，的頁P7，此外，索引節點A必須被修改為索引節點A，以指定已經 存儲索引節點C，的頁P8。以這種方式，葉節點F的修改導致與葉節點F相關 的索引節點C和A的修改。也就是說，為了修改/插入/刪除葉節點，寫操作
被執行至少B+樹的高度(H)次。
通常，在NAND快閃記憶體中，寫操作比讀操作需要更多時間，並且可在一塊 上形成的寫操作的次數有限。因此，可能需要大量時間來修改索引方案，並 且可能還會縮短NAND快閃記憶體的壽命。
圖3是示出才艮據本發明 一些示例性實施例的在快閃記憶體中存儲M-樹的方案的 示圖。參照圖3，在/x-樹(e)中，葉節點和與葉節點相關的索引節點被寫到 同一頁中。例如，葉節點F和作為葉節點F的父節點的索引節點C和A一皮存 儲在頁P1中。同樣，葉節點E以及索引節點B和A被存儲在頁P2中，葉節 點D和索引節點B和A被存儲在頁P3中。然而，當葉節點E和索引節點B 和A被存儲在頁P2中時，因為索引節點A指定存儲索引節點B和C的頁， 所以存儲在頁Pl中的索引節點A無效。同樣，當葉節點D和索引節點B和 A被存儲在頁P3中時，因為索引節點A的指針指定存儲索引節點C和B的 頁Pl和P2，並且索引節點B的指針指定存儲葉節點D和E的頁P3和P2, 所以存儲在頁P2中的索引節點B無效。例如，不能訪問存儲在頁P2中的索 引節點B。換句話說，因為按從索引節點A(即最後頁P3的根節點)到子節 點的順序來進行搜索，所以不能訪問存儲在頁Pl中的索引節點A和存儲在 頁P2中的索引節點A和B。
圖4是示出根據本發明一些實施例的修改圖3所示的快閃記憶體中存儲的/x-樹 的葉節點的方案的概念性示圖。參照圖4，不僅修改葉節點F，還修改索引節 點C和A,以對葉節點F進行修改。這樣做的原因在於如果在新頁P4中存 儲修改的葉節點F，，則指定葉節點F，的索引節點C被修改為索引節點C，，並 且修改的指針指定頁P4而非頁Pl。索引節點A被修改為具有指定索引節點 C，的修改的指針的索引節點A，。這裡，符號(，)是指葉節點/索引節點的鍵值/ 指針已經被修改。
修改的節點F，、 C，和A，被存儲在頁P4中。也就是說，只對一頁P4執行 寫操作以修改一個頁節點F。因此，可減少修改葉節點所花費的時間，並且 可減少快閃記憶體的使用。本發明的這種索引方案可減少對快閃記憶體進行寫操作的次數， 從而可延長快閃記憶體的壽命。
當對圖4所示的快閃記憶體(h)中的葉節點進行搜索時，按從存儲在最後頁 P4的根節點A，到子節點的順序來進行搜索。也就是說，根節點A，指定索引節 點B和C，，索引節點B指定葉節點D和E,並且索引節點C，指定葉節點F，。
這種索引方案適用於M-樹的搜索方案。
圖5是示出根據本發明一些實施例的在圖3所示的快閃記憶體中存儲的/x-樹中
插入新的葉節點的方案的概念性示圖。當將要插入葉節點G時，索引節點C 和A (即與葉節點G相關的父節點)必須被修改。參照圖5,修改的索引節 點C，和A，以及在)U-樹(i)中插入的葉節點G被存儲在快閃記憶體(j)的頁P4中。修改 的索引節點C，包括用於指定存儲葉節點G的頁P4和用於存儲葉節點F的頁 Pl。
從上面的描述可以看出，可通過一次寫操作插入新的葉節點。如果在插 入了新的葉節點G之後，索引節點C，變滿，則可分離索引節點C，。這將在 下面詳細描述。
圖6是示出根據本發明的一些實施例的刪除圖3所示的快閃記憶體中存儲的 樹的葉節點的方案的概念性示圖。參照圖6，當從r樹(k)中刪除葉節點E 時，修改索引節點B和A (即與葉節點E相關的父節點)。與從/x-樹刪除的 葉節點E相關的修改的索引節點B，和A，被存儲在頁P4中。修改的索引節點 B，指定存儲葉節點D的頁P3,修改的索引節點A，指定修改的索引節點B，和 索引節點C。修改的索引節點A，和B，被存儲在快閃記憶體(I)的頁P4中。
圖7是示出根據本發明一些實施例的刪除圖6中所示的快閃記憶體中存儲的/X-樹的葉節點的方案的概念性示圖。當將要從At-樹(m)刪除葉節點D時，修 改索引節點B和A(即與葉節點E相關的父節點)。參照圖6,如果從/x-樹(m) 刪除葉節點D，索引節點B不指定任何葉節點。因此，刪除沒有子節點的索 引節點B。因為索引節點A (即根節點)只指定存儲索引節點C的頁P5,所 以索引節點C可被修改為根節點。例如，索引節點C被修改為指向頁Pl和 P4中的葉節點F和G的#>節點。
如圖6和圖7所示，通過對快閃記憶體執行一次寫操作可實現刪除葉節點的操 作。可減少刪除葉節點所花費的時間，並且可減少快閃記憶體的使用。根據本發明 一些實施例的索引方案可減少快閃記憶體上寫操作的次數，這可延長快閃記憶體的壽命。
如上所述，按從葉節點到根節點的順序依次對M-樹的葉節點執行修改、 插入或刪除操作，並且在一頁中存儲索引節點(即與修改的、插入的或刪除 的葉節點相關的非葉節點)。因此，快閃記憶體的一頁必須被指定為能夠存儲從葉節 點到根節點的所有節點。
圖8是示出在本發明 一些實施例中存儲在一頁中的葉節點/索引節點的最
大可存儲大小隨著高度(H)增加而改變的示圖。參照圖8，當快閃記憶體的一頁具 有4096位元組大小時，如果高度(H)是1，則根節點811也具有4096位元組大 小。如果高度(H)是2，則根節點821具有2048位元組大小，葉節點822也 具有2048位元組大小。如果高度(H)是3，則根節點831和索引節點832中 的每一個都具有1024位元組大小，葉節點833具有2048位元組大小。如果高度 (H)是4，則根節點841和索引節點842中的每一個都具有512位元組大小， 索引節點843具有1024位元組大小，並且葉節點844具有2048位元組大小。
隨著高度(H)增加，葉節點822、 833和844的大小保持2048位元組， 而根節點811、 821和831的大小減小1/2。可以看出，當/x-樹被存儲在快閃記憶體 中時，通過根節點數據大小和快閃記憶體的一頁的大小來確定M-樹的最大高度。
索引節點/葉節點的最大大小根據樹的層次而變化。例如，如果高度(H) 是4，則第4層的葉節點844具有2048的最大大小，第3層的索引節點843 具有1024位元組的最大大小，第2層的索引節點842具有512位元組的最大大小， 第1層的根節點841具有512位元組的最大大小。
快閃記憶體可被內置在各種電子裝置(比如個人計算機、筆記本計算機、數字 音樂播放器、數字相機和手機)中或者連接到所述各種電子裝置上。內置或 連接到電子裝置中的快閃記憶體可被電子裝置中的處理器控制。
圖9A是示出包括根節點和葉節點的/x-樹的示例的示圖。圖9B是示出用 於在圖9A所示的p樹的葉節點中插入鍵值的示例性處理的示圖。在圖9B所 示的示例中，可被存儲在快閃記憶體的 一 頁中的根節點或葉節點的鍵值的數量高達 100。圖9C是示出在圖9B中所示的鍵值插入處理導致的改變的r樹的示圖。 圖10是示出在處理器的控制下在pt-樹的葉節點中插入鍵值的處理的流程圖。
參照圖9B和圖10,鍵值被插入到存儲在快閃記憶體的一頁Pll中的葉節點X2 中(操作1000)。因為鍵值將被插入的葉節點X2滿了 (存儲的鍵值的數量/ 可存儲的鍵值的最大數量=50/50),所以葉節點X2被劃分成兩個葉節點X21 和X22,並且這兩個葉節點X21和X22被臨時存儲在兩個緩沖器存儲器Mil 和M12中。這裡，新插入的葉節點被存儲在緩沖器存儲器Mil的葉節點X21 中，指定新葉節點X21和X22的根節點Xl，被存儲在緩沖器存儲器M12中。
包括在存儲在前一頁Pll中的根節點X1中的指針的數量是49/50。葉節 點X2被劃分為葉節點X21和X22,添加新的指針以指定葉節點X21。因此， 50/50指針被包括在根節點XI，中。
因為根節點xr滿(操作ioio),所以索引節點xr被劃分成兩個索引節
點Xll和X12 (操作1020)。 i(X-樹的高度(H)增加1 (操作1030)。指定葉 節點X21和X22的索引節點被存儲在快閃記憶體的頁P13中，索引節點X12被存 儲在頁P14中。產生新的根節點X0以指定索引節點X11和X12。根節點XO 被存儲在頁P14中。
以這種方式，如果在新鍵值被插入到葉節點中時葉節點滿，則通過劃分 操作對葉節點進行劃分。如果通過葉節點的劃分根節點滿，則根節點被劃分 為兩個索引節點，並且產生了新的根節點(操作1040)。即使當通過插入新 鍵值而使得葉節點或根節點滿時，根據本發明一些實施例的索引方案也可執 行最小寫操作。此外，可指定根據本發明一些實施例的索引方案，從而只有 直接分支的節點被存儲在快閃記憶體的一頁中。因此，可相對容易地執行比如拉圾 收集的操作。例如，通過只對一頁中最低層的節點(葉節點)執行有效性測 試，整頁的有效性可被驗證。
圖11A是示出用於描述用於/x-樹的鍵值刪除方案的g-樹的示例的示圖。 圖IIB是示出從圖11A所示的M-樹的任何葉節點刪除鍵值的示例性處理的示 圖。在圖11B所示的示例中，可被存儲在快閃記憶體的一頁中的根節點或葉節點的 鍵值數量高達IOO。圖IIC是示出圖IIA所示的/x-樹的鍵值刪除處理導致的 改變的iit-樹結構的示圖。圖12是示出在處理器的控制下從/A-樹的葉節點刪 除鍵值的處理的流程圖。
參照圖IIB和圖12,葉節點Y5被刪除(操作1200)。如果在從葉節點 Y5中刪除了鍵值之後在葉節點Y5中沒有鍵值，則刪除葉節點Y5。如果該葉 節點被刪除，則不存在索引節點Y3的子節點，並且根節點Yl只有一個子節 點，即索引節點Y2。被修改以只指定索引節點Y2的根節點Yl，被存儲在緩 沖器存儲器M21中。
當根節點Yl，有一個子節點(操作1210)時，/x-樹的高度(H)減小1。 在圖IIB所示的示例中，/x-樹的高度(H)從3減小到2(操作1220)。結果， 索引節點Y2被修改為根節點Y2'，並被存儲在快閃記憶體的頁P23中(操作1230)。 因此，葉節點Y2的4建值被刪除，圖IIA所示的M-樹被改變為如圖IIC所示 的具有葉節點Y4和根節點Y2。
如上所述，根據本發明一些實施例的索引方案可限制^-樹的索引節點/ 葉節點的大小，從而可將葉節點和與葉節點相關的父節點(例如索引節點和
根節點)存儲在快閃記憶體的一頁中。因此當M-樹的節點被修改、插入或刪除時可 減少對快閃記憶體的數據寫操作。因此，可延長快閃記憶體的壽命。當/X-樹的索引節點/ 葉節點的大小被限制時，可增加/x-樹的高度(H)。然而，因為快閃記憶體的讀操作 可比寫操作快，所以在各種工作量條件下也可增加索引方案的速度。
圖13是使用根據本發明 一些實施例的索引方案的電子裝置的框圖。參照 圖13，電子裝置1300包括與系統總線1301連接的處理器1310、顯示器1320、 小鍵盤1330、快閃記憶體1340、只讀存儲器(ROM) 1350和隨機存取存儲器(RAM) 1360。電子裝置1300將文件系統存儲在快閃記憶體1340中。這裡，快閃記憶體1340基於 p樹結構使用本發明的索引方案。電子裝置1300的示例包括數位音樂播放器、 數字相機、手機、可攜式多媒體播放器(PMP)和播放站。根據遵循上述概 念的索引方案，處理器1310可將/x-樹的葉節點和與所述葉節點相關的索引節 點存儲在快閃記憶體1340的一頁中，並且可對葉節點/索引節點執行修改、插入或 刪除操作。
圖14是使用根據本發明一些實施例的索引方案的存儲器系統的框圖。參 照圖14,存儲卡1420被連接到主機1410。存儲卡1420包括存儲器控制器 1422和快閃記憶體1424。存儲器控制器1422提供主機1410和快閃記憶體1424之間的接 口。存儲器控制器1422和快閃記憶體1424被構造在一個晶片中，並且可以以小型 快閃記憶體(compact flash )、智能介質、記憶棒、安全數字(SD)卡、多媒體卡等 來實現。在上述存儲器系統中，主機1410可根據遵循上述概念的索引方案來 "i方問快閃記憶體1424。
圖15是使用根據本發明 一些實施例的索引方案的另 一 電子裝置的框圖。 參照圖15,電子裝置1500包括固態盤(SSD) 1540，而非圖13所示的 電子裝置1300的快閃記憶體1340。電子裝置1500的其他結構和操作相似於電子裝 置1300的其他結構和操作。使用遵循上述概念的索引方案，電子裝置1500 的處理器1510可將/x-樹的葉節點和與葉節點相關的索引節點存儲在SSD 1540的一頁中，並可對葉節點/索引節點執行修改、插入或刪除操作。
上述內容是對本發明的說明，並不應該解釋為限制本發明。儘管已經描 述了本發明的一些示例性實施例，但是本領域的技術人員應該理解，在實質 上不脫離本發明新穎性教導和優點的情況下，可對這些示例性實施例進行很 多修改。因此，所有的這種修改被認為是包括在權利要求限定的本發明的範 圍中。因此，應該理解，上述內容只是對本發明的說明，而並不被理解為限
於公開的具體實施例，並且對公開的實施例的修改以及其他修改被認為是包 括在權利要求的範圍內。
權利要求
1、一種在快閃記憶體裝置中存儲樹數據結構的方法，所述方法包括將葉節點和包括指向所述葉節點的指針的索引節點存儲在快閃記憶體裝置的同一頁中。
2、 如權利要求l所述的方法，還包括以每頁為基礎對快閃記憶體裝置進行讀操作。
3、 如權利要求l所述的方法，其中，可存儲在快閃記憶體裝置的一頁中的樹結 構的節點的最大數量取決於樹數據結構的高度。
4、 如權利要求3所述的方法，其中，樹數據結構的節點的最大大小取決 於樹數據結構中的節點的層次。
5、 如權利要求l所述的方法，還包括將葉節點的修改版本和索引節點 的修改版本存儲在快閃記憶體裝置的新的頁中。
6、 如權利要求5所述的方法，其中，索引節點的修改版本包括指向所述 新的頁的指針。
7、 如權利要求5所述的方法，其中，修改的葉節點包括新的鍵值。
8、 如權利要求7所述的方法，其中，將葉節點的修改版本和索引節點的 修改版本存儲在快閃記憶體裝置的新的頁的方法包括如果葉節點滿，則將葉節點劃分為第 一葉節點和第二葉節點； 將新的4建值插入到第 一葉節點和第二葉節點中的 一個葉節點中；將第一葉節點和第二葉節點存儲在快閃記憶體裝置的各自的新的頁中。
9、 如權利要求8所述的方法，其中，將葉節點的修改版本和索引節點的 修改版本存儲在快閃記憶體裝置的新的頁中的步驟還包括如果索引節點滿，則將索引節點劃分為第一索引節點和第二索引節點；產生指向第一索引節點和第二索引節點的高層索引節點；將第一索引節點存儲在新的頁的第一頁中； 將第二索引節點和高層索引節點存儲在新的頁的第二頁中。
10、 如權利要求5所述的方法，其中，葉節點的修改版本缺少在原始葉 節點中存在的鍵值。
11、 如權利要求l所述的方法，其中，索引節點和葉節點包括來自高層 節點的第一分支的第一索引節點和第一葉節點，其中，包括第二索引節點和 第二葉節點的第二分支與所述第一分支共享所述高層節點；其中，將葉節點和包括指向葉節點的指針的索引節點存儲在快閃記憶體中的同一頁中的步驟包括將第 一葉節點和第 一 索引節點存儲在第 一頁中； 其中，所述方法還包括將高層節點存儲在第一頁中；將第二葉節點和第二索引節點存儲在第二頁中；檢測從第 一葉節點刪除鍵值的步驟將導致在第 一葉節點中沒有剩餘鍵值 並且第 一索引節點不包括指向葉節點的其他指針；響應地將第二索引節點的修改版本存儲在第三頁中。
12、 如權利要求11所述的方法，其中，將第二索引節點的修改版本存儲 在第三頁中的步驟從樹數據結構刪除高層節點。
13、 一種包括被構造為執行權利要求1所述方法的處理器的系統。
14、 一種包括被構造為在計算機上執行的電腦程式代碼的計算機可讀 存儲介質，所述電腦程式代碼包括被構造為執行權利要求1所述的方法。
15、 一種系統，包括 快閃記憶體裝置，包括多個頁；處理器，運行上與快閃記憶體裝置相關，並被構造為將樹數據結構的葉節點和 包括指向所述葉節點的指針的索引節點存儲在快閃記憶體中的同 一 頁中。
16、 如權利要求15所述的系統，其中，所述處理器被構造為操作作為固 態盤的快閃記憶體。
全文摘要
本發明提供一種使用頁結構的數據樹存儲方法、系統和電腦程式產品。通過將葉節點和包括指向葉節點的指針的索引節點存儲在以每頁為基礎讀的快閃記憶體裝置中的同一頁中來在快閃記憶體裝置中存儲樹數據結構。例如，當鍵值被添加到葉節點或者從葉節點刪除鍵值時，葉節點的修改版本和索引節點的修改版本可被存儲在快閃記憶體裝置的新的頁中。
文檔編號G06F12/02GK101339538SQ20081013198
公開日2009年1月7日 申請日期2008年7月4日 優先權日2007年7月4日
發明者姜東阮, 康貞旭, 樸贊益, 金珍洙 申請人:三星電子株式會社;韓國科學技術院