[發(fā)明專利]使用頁(yè)結(jié)構(gòu)的數(shù)據(jù)樹存儲(chǔ)方法、系統(tǒng)和計(jì)算機(jī)程序產(chǎn)品

有效

• 申請(qǐng)?zhí)枺?/td>: 200810131986.0
• 申請(qǐng)日: 2008-07-04
• 公開（公告）號(hào): CN101339538A
• 公開（公告）日: 2009-01-07
• 發(fā)明（設(shè)計(jì)）人: 姜東阮;康貞旭;金珍洙;樸贊益
• 申請(qǐng)（專利權(quán)）人: 三星電子株式會(huì)社;韓國(guó)科學(xué)技術(shù)院
• 主分類號(hào): G06F12/02
• 分類號(hào): G06F12/02;G06F17/30
• 代理公司: 北京銘碩知識(shí)產(chǎn)權(quán)代理有限公司
• 代理人: 韓明星;羅延紅

本申請(qǐng)要求在2007年7月4日提交到韓國(guó)知識(shí)產(chǎn)權(quán)局的第 10-2007-0067129號(hào)韓國(guó)專利申請(qǐng)的優(yōu)先權(quán)，該申請(qǐng)全部公開于此以資參考。

技術(shù)領(lǐng)域

本申請(qǐng)涉及閃存裝置及其操作方法，更具體地講，涉及閃存裝置的數(shù)據(jù) 存儲(chǔ)方法、系統(tǒng)和計(jì)算機(jī)程序產(chǎn)品。

背景技術(shù)

閃存裝置是即使在沒(méi)有電源的情況下也能在存儲(chǔ)芯片上保留數(shù)據(jù)的非易 失性存儲(chǔ)裝置。盡管閃存裝置通常比例如用作個(gè)人計(jì)算機(jī)(PC)的主存儲(chǔ)器 的動(dòng)態(tài)隨機(jī)存取存儲(chǔ)器(DRAM)慢，但是通常比硬盤讀的速度要高并且更 能抵抗沖擊。另外，閃存裝置通常能夠抵抗來(lái)自周圍的沖擊，比如高的壓力 和沸騰的水。因?yàn)檫@些特性，閃存裝置被廣泛用作用電池操作的裝置中的存 儲(chǔ)單元。

閃存裝置是電可擦除可編程非易失性存儲(chǔ)裝置。通常的閃存裝置可按塊 被擦除和被編程。因?yàn)橥ǔｉW存裝置相對(duì)便宜，所以它們被廣泛用作高容量 固態(tài)非易失性存儲(chǔ)器。使用閃存的典型實(shí)例是在數(shù)字音樂(lè)播放器、數(shù)字相機(jī) 和蜂窩電話中。閃存裝置還用作通用串行總線(USB)驅(qū)動(dòng)器，所述USB存 儲(chǔ)器被廣泛用于在計(jì)算機(jī)之間存儲(chǔ)和傳送數(shù)據(jù)。

因?yàn)橛脖P驅(qū)動(dòng)器機(jī)械地驅(qū)動(dòng)磁盤以讀/寫數(shù)據(jù)，通常在結(jié)構(gòu)上限制了硬盤 的操作速度上的增加。為此，已經(jīng)試圖使用用于高容量存儲(chǔ)器的閃存來(lái)替換 硬盤驅(qū)動(dòng)器。例如，在閃存中存儲(chǔ)啟動(dòng)代碼時(shí)可增加系統(tǒng)啟動(dòng)速度。

發(fā)明內(nèi)容

本發(fā)明的一些實(shí)施例提供一種用于閃存的索引方案。

本發(fā)明的實(shí)施例提供基于包括多頁(yè)的閃存的樹結(jié)構(gòu)的索引方法，所述索 引方法包括：將葉節(jié)點(diǎn)和與葉節(jié)點(diǎn)相關(guān)的索引節(jié)點(diǎn)存儲(chǔ)在閃存的同一頁(yè)中。

在一些實(shí)施例中，每頁(yè)存儲(chǔ)高達(dá)k個(gè)葉節(jié)點(diǎn)和/或索引節(jié)點(diǎn)，k為正數(shù)。

在其他實(shí)施例中，以頁(yè)為基礎(chǔ)對(duì)閃存裝置進(jìn)行讀或?qū)懖僮鳌?

在一些實(shí)施例中，存儲(chǔ)在頁(yè)中的葉節(jié)點(diǎn)或索引節(jié)點(diǎn)的數(shù)量取決于樹的高 度。

在一些實(shí)施例中，索引節(jié)點(diǎn)中的最高索引節(jié)點(diǎn)是根節(jié)點(diǎn)。

在一些實(shí)施例中，索引方法還包括對(duì)葉節(jié)點(diǎn)進(jìn)行修改。

在一些實(shí)施例中，對(duì)葉節(jié)點(diǎn)進(jìn)行修改的步驟還包括：改變與將被修改的 葉節(jié)點(diǎn)相關(guān)的索引節(jié)點(diǎn)的指針；并把將被修改的葉節(jié)點(diǎn)和修改的索引節(jié)點(diǎn)存 儲(chǔ)在新的一頁(yè)中。

在一些實(shí)施例中，索引方法還包括插入新的葉節(jié)點(diǎn)。

在一些實(shí)施例中，插入新的葉節(jié)點(diǎn)的步驟包括：改變與新的葉節(jié)點(diǎn)相關(guān) 的索引節(jié)點(diǎn)的指針；并將新的葉節(jié)點(diǎn)和與所述新的葉節(jié)點(diǎn)相關(guān)的索引節(jié)點(diǎn)存 儲(chǔ)在新的頁(yè)中。

在一些實(shí)施例中，插入新的葉節(jié)點(diǎn)的步驟還包括：確定與新的葉節(jié)點(diǎn)相 關(guān)的索引節(jié)點(diǎn)是否滿；如果與新的葉節(jié)點(diǎn)相關(guān)的索引節(jié)點(diǎn)滿，則將索引節(jié)點(diǎn) 劃分為第一索引節(jié)點(diǎn)和第二索引節(jié)點(diǎn)；產(chǎn)生第一索引節(jié)點(diǎn)和第二索引節(jié)點(diǎn)的 上層節(jié)點(diǎn)。

在一些實(shí)施例中，索引方法還包括將新的鍵值插入到葉節(jié)點(diǎn)。

在一些實(shí)施例中，插入新的鍵值的步驟包括：確定將插入新的鍵值的葉 節(jié)點(diǎn)是否滿；如果將插入新的鍵值的葉節(jié)點(diǎn)滿，則將葉節(jié)點(diǎn)劃分為第一葉節(jié) 點(diǎn)和第二葉節(jié)點(diǎn)；并將新的鍵值插入到第一葉節(jié)點(diǎn)和第二葉節(jié)點(diǎn)中的一個(gè)節(jié) 點(diǎn)中。

在一些實(shí)施例中，第一葉節(jié)點(diǎn)和第二葉節(jié)點(diǎn)被分別存儲(chǔ)在閃存中的新的 頁(yè)中。

在一些實(shí)施例中，插入新的鍵值的步驟還包括：確定與新的葉節(jié)點(diǎn)相關(guān) 的索引節(jié)點(diǎn)是否滿；如果與新的葉節(jié)點(diǎn)相關(guān)的索引節(jié)點(diǎn)滿，則將索引節(jié)點(diǎn)劃 分為第一索引節(jié)點(diǎn)和第二索引節(jié)點(diǎn)；產(chǎn)生第一索引節(jié)點(diǎn)和第二索引節(jié)點(diǎn)的上 層索引節(jié)點(diǎn)。

在一些實(shí)施例中，第一索引節(jié)點(diǎn)被存儲(chǔ)在與第一葉節(jié)點(diǎn)和第二葉節(jié)點(diǎn)中 的一個(gè)節(jié)點(diǎn)相同的頁(yè)中，第二索引節(jié)點(diǎn)與上層索引節(jié)點(diǎn)一起被存儲(chǔ)在新的頁(yè) 中。

在一些實(shí)施例中，索引方法還包括刪除葉節(jié)點(diǎn)。

在一些實(shí)施例中，刪除葉節(jié)點(diǎn)的步驟包括：確定與刪除的葉節(jié)點(diǎn)相關(guān)的 索引節(jié)點(diǎn)是否指定另一葉節(jié)點(diǎn)；如果與刪除的葉節(jié)點(diǎn)相關(guān)的索引節(jié)點(diǎn)沒(méi)有指 定另一葉節(jié)點(diǎn)，則刪除索引節(jié)點(diǎn)。

在一些實(shí)施例中，刪除葉節(jié)點(diǎn)的步驟還包括：如果樹的根節(jié)點(diǎn)具有一個(gè) 子節(jié)點(diǎn)，則將樹的高度減小1，并將根節(jié)點(diǎn)的子節(jié)點(diǎn)設(shè)置為新的根節(jié)點(diǎn)。

在一些實(shí)施例中，刪除葉節(jié)點(diǎn)的步驟還包括將新的根節(jié)點(diǎn)存儲(chǔ)在新的頁(yè) 中。

在一些實(shí)施例中，索引方法基于μ-樹結(jié)構(gòu)。