TWI646461B

TWI646461B - 資料儲存裝置及其資料維護方法

Info

Publication number: TWI646461B
Application number: TW105132831A
Authority: TW
Inventors: 柯冠宇
Original assignee: 慧榮科技股份有限公司
Priority date: 2016-10-12
Filing date: 2016-10-12
Publication date: 2019-01-01
Also published as: CN107943711B; CN107943711A; TW201814490A

Abstract

本發明提供一種資料儲存裝置包括一隨機存取記憶體以及一控制器。隨機存取記憶體具有一預取區域。控制器將資料鏈結關係表中部分之複數資料鏈結關係集合載入該預取區域中之複數區段，其中該等資料鏈結關係集合中，被讀取次數小於一既定值之資料鏈結關係集合屬於複數非頻繁資料鏈結關係集合中之一者，且被讀取次數到達該既定值之資料鏈結關係集合，屬於複數頻繁資料鏈結關係集合中之一者。

Description

資料儲存裝置及其資料維護方法

本發明係關於一種資料儲存裝置，特別係關於以特定方式維護預取區域中之資料的資料儲存裝置。

快閃記憶體為一種普遍的非揮發性資料儲存裝置，係以電性方式抹除與程式化。以非及閘型的快閃記憶體(即NAND FLASH)為例，常用作記憶卡(memory card)、通用序列匯流排閃存裝置(USB flash device)、固態硬碟(SSD)、嵌入式快閃記憶體模組(eMMC)…等使用。

快閃記憶體(如，NAND FLASH)的儲存陣列包括複數個區塊(blocks)，其中浮置閘極電晶體可用以構成快閃記憶體。浮置閘極電晶體中之浮置閘極，可捕捉的電荷以儲存資料。另外，快閃記憶體中之實體頁面與主機裝置所指定之邏輯頁面的轉換關係需要一個實體轉邏輯表紀錄。然而，需要很大的容量才可以將全部的實體邏輯表載入隨機存取記憶體中。如何有效更新管理隨機記憶體中所載入之資料是一個重要的課題。

本發明所提供之資料儲存裝置以及資料維護方法可藉由三種表來維護儲存於隨機記憶體中之資料。

在一實施例中，控制器更建立一非頻繁指標組以維護該等非頻繁資料鏈結關係集合，並且建立一頻繁指標組以維護該等頻繁資料鏈結關係集合，其中非頻繁指標組係由一非頻繁頭指標以及一非頻繁尾指標所構成，並且頻繁指標組係由一頻繁頭指標以及一頻繁尾指標所構成。區段依序具有複數共用指標，非頻繁頭指標為用以儲存最後一個被讀取之非頻繁資料鏈結關係集合之區段的共用指標，非頻繁尾指標為用以儲存最久未被讀取之非頻繁資料鏈結關係集合之區段的共用指標，頻繁頭指標為用以儲存最後一個被讀取之頻繁資料鏈結關係集合之區段的共用指標，頻繁尾指標為用以儲存最久未被讀取之頻繁資料鏈結關係集合之區段的共用指標。

本發明亦提供一種資料儲存裝置包括具有一預取區域之一隨機存取記憶體以及一控制器。控制器用以將一資料鏈結關係表所儲存之複數資料鏈結關係集合的一部分載入預取區域中之複數區段，其中當預取區域之複數區段皆已被寫滿並且一第一資料鏈結關係集合需要被載入預取區域時，控制器更用以根據一非頻繁指標組選擇區段中之一第一區段，以載入第一資料鏈結關係集合，其中當非頻繁指標組不具有對應之區段中之一者時，控制器更用將一頻繁指標組轉換為非頻繁指標組，並根據轉換後之非頻繁指標組選擇第一區段。

本發明另提供一種資料維護方法適用於具有一快閃記憶體之一資料儲存裝置。快閃記憶體包括複數頁面，其中每一頁面具有一邏輯位址以及一實體位址。資料維護方法包括：在快閃記憶體被上電時，根據至少一讀取命令或者至少一寫入命令，在一隨機記憶體中之一預取區域之複數區段中，載入一資料鏈結關係表中之複數資料鏈結關係集合的一部份，其中每一資料鏈結關係集合具有頁面中之至少一者之邏輯位址以及實體位址的對應關係，並且每一資料鏈結關係集合相應於一集合指標，其中預取區域所儲存之資料鏈結關係集合中被讀取之次數小於一既定值之資料鏈結關係集合屬於非頻繁資料鏈結關係集合，以及預取區域所儲存之資料鏈結關係集合中被讀取到達既定值之資料鏈結關係集合屬於頻繁資料鏈結關係集合。

在一實施例中，資料維護方法更包括建立一非頻繁指標組，以維護複數非頻繁資料鏈結關係集合；以及建立一頻繁指標組，以維護被複數頻繁資料鏈結關係集合，其中預取區域所儲存之資料鏈結關係集合中被讀取到達既定值之資料鏈結關係集合屬於頻繁資料鏈結關係集合。

在一實施例中，資料維護方法更包括：建立一預取區域對應表，以在預取區域對應表中之複數區段對應欄紀錄相應於預取區域中之資料鏈結關係集合的集合指標；建立一順序表，以分別紀錄頻繁資料鏈結關係集合自預取區域中被讀取之順序以及非頻繁資料鏈結關係集合自域取區域中被讀取之順序；以及建立一反序表，以分別紀錄頻繁資料鏈結關係集合自預取區域中被讀取之反向的順序以及非頻繁資料鏈結關係集合自預取區域中被讀取之反向的順序。

又另一實施例中，資料維護方法更包括：當預取區域已被寫滿並且需要載入新的資料鏈結關係集合時，判斷非頻繁尾指標是否為共用指標中之任一者；當非頻繁尾指標為共用指標中之任一者時，根據非頻繁尾指標判斷非頻繁資料鏈結關係集合中最久未被讀取之非頻繁資料鏈結關係集合；將第一資料鏈結關係集合的資料寫入非頻繁資料鏈結關係集合中最久未被讀取之非頻繁資料鏈結關係集合所屬的區段；當非頻繁尾指標不是共用指標中之任一者時，將頻繁尾指標中所儲存之共用指標寫入非頻繁尾指標，將頻繁頭指標中所儲存之共用指標寫入非頻繁頭指標，並且刪除頻繁尾指標以及非頻繁尾指標中所儲存之共用指標。

100‧‧‧電子系統

120‧‧‧主機

140‧‧‧資料儲存裝置

160‧‧‧控制器

162‧‧‧運算單元

164‧‧‧永久記憶體

166‧‧‧隨機存取記憶體

180‧‧‧快閃記憶體

TB1‧‧‧資料鏈結關係表

MR_0~MR_MX‧‧‧對應關係

TS_0~TS_M‧‧‧資料鏈結關係集合

CIX_0~CIX_N‧‧‧共用指標

CA‧‧‧預取區域

S_0~S_N‧‧‧區段

SE_TB‧‧‧順序表

SE_0~SE_N‧‧‧順序欄

SMR_TB‧‧‧預取區域對應表

SMR_0~SMR_N‧‧‧區段對應欄

RSE_TB‧‧‧反序表

RSE_0~RSE_N‧‧‧反序欄

HIX‧‧‧頭指標

TIX‧‧‧尾指標

FR_HIX‧‧‧頻繁頭指標

FR_TIX‧‧‧頻繁尾指標

LRU_HIX‧‧‧非頻繁頭指標

LRU_TIX‧‧‧非頻繁尾指標

S900~S902、S1000~S1090、S2100~S2102、S2200~S2299‧‧‧步驟

第1圖為本發明所提供之一電子系統之一種實施例的方塊圖。

第2圖為本發明所提供之一資料鏈結關係表之一種實施例的方塊圖。

第3圖為本發明所提供之一隨機存取記憶體中之複數表之一種實施例的示意圖。

第4圖為本發明所提供之一隨機存取記憶體中之複數表之另一種實施例的示意圖。

第5圖為本發明所提供之一隨機存取記憶體中之複數表之另一種實施例的示意圖。

第6圖為本發明所提供之一隨機存取記憶體中之複數表之另一種實施例的示意圖。

第7A圖為本發明所提供之一隨機存取記憶體中之複數表之另一種實施例的示意圖。

第7B圖為本發明所提供之一隨機存取記憶體中之複數表之另一種實施例的示意圖。

第8圖為本發明所提供之一隨機存取記憶體中之複數表之另一種實施例的示意圖。

第9圖為本發明所提供之一資料維護方法之一種實施例的流程圖。

第10A~10F圖為本發明所提供之一資料維護方法之另一種實施例的流程圖。

第11~20圖為本發明所提供之一隨機存取記憶體中之表之另一種實施例的方塊圖。

第21圖為本發明所提供之一資料維護方法之另一種實施例的流程圖。

第22A~22H圖為本發明所提供之一資料維護方法之另一種實施例的流程圖。

以下將詳細討論本發明各種實施例之裝置及使用方法。然而值得注意的是，本發明所提供之許多可行的發明概念可實施在各種特定範圍中。這些特定實施例僅用於舉例說明本發明之裝置及使用方法，但非用於限定本發明之範圍。

第1圖為本發明所提供之一電子系統之一種實施例的方塊圖。電子系統100包括一主機120以及一資料儲存裝置140。資料儲存裝置140包括一快閃記憶體180以及一控制器160，且可根據主機120所下達的命令操作。控制器160包括一運算單元162、一永久記憶體(如，唯讀記憶體ROM)164以及隨機存取記憶體(RAM)166。永久記憶體164與所載之程式碼、資料組成韌體(firmware)，由運算單元162執行，使控制器160基於該韌體控制該快閃記憶體180。隨機存取記憶體(RAM)166用以載入程式碼與參數以提供控制器160根據所載入的程式碼與參數動作。快閃記憶體180包括複數區塊，每一區塊包括複數頁面，每一頁面具有一邏輯位址以及一實體位址，其中實體位址為頁面在快閃記憶體180中固定的位址，邏輯位址為主機120以及控制器160給頁面定義之位址。另外，快閃記憶體180中更包括可由控制器160動態更新之一資料鏈結關係表TB1，其中資料鏈結關係表TB1用以紀錄所有頁面之邏輯位址以及實體位址的複數對應關係。值得注意的是，快閃記憶體180以區塊為最小單位進行抹除，並且頁面為最小單位進行寫入。

第2圖為本發明所提供之一資料鏈結關係表之一種實施例的方塊圖。如第2圖所示，資料鏈結關係表TB1中包括所有頁面之邏輯位址以及實體位址的對應關係MR_P0~MR_PMX，其中每一對應關係MR_P0~MR_PMX分別對應到快閃記憶體180中之一頁面，並且對應關係 MR_P0~MR_PMX中之任兩者不對應到同一個頁面。另外，資料鏈結關係表TB1被分割為複數資料鏈結關係集合TS_0~TS_M，每一資料鏈結關係集合TS_0~TS_M具有多於一個對應關係。舉例而言，資料鏈結關係集合TS_0具有對應關係MR_P0~MR_PX、資料鏈結關係集合TS_1具有對應關係MR_P0~MR_P2X，依此類推。在本實施例中，每一資料鏈結關係集合TS_0~TS_M具有X+1個對應關係，但本發明不限於此。在其他實施例中，每一資料鏈結關係集合可具有不同數量之對應關係，並且資料鏈結關係集合所具有之鏈結關係的數量可由開發者自行決定或者由控制器160動態調整。值得注意的是，每一資料鏈結關係集合TS_0~TS_M相應於一集合指標。在一實施例中，集合指標可為0xAA、0xBB、0xCC、0x128等16進制數值。

當資料儲存裝置140被上電後，控制器160可將資料鏈結關係表TB1載入隨機存取記憶體166中之一預取區域，以進行讀取以及更新。然而，隨著快閃記憶體180之記憶體容量的增加，資料鏈結關係表TB1也越來越大。在隨機存取記憶體166中所規劃的預取區域不夠儲存整個資料鏈結關係表TB1的情況下，控制器160則根據目前所需的資料將資料鏈結關係表TB1中之部分資料鏈結關係集合載入預取區域中。詳細而言，當預取區域CA還有空間可以載入資料鏈結關係集合TS_0~TS_M中之至少一者時，控制器160進行一載入程序，以將所需之資料鏈結關係集合載入預取區域的空白處。當預取區域已被寫滿並且需要載入新的資料鏈結關係集合TS_0~TS_M 時，控制器160進行一取代程序，以找出最久未被讀取之資料鏈結關係集合，以將新的資料鏈結關係集合覆蓋在最久未被讀取之資料鏈結關係集合上。當控制器160所需要的資料鏈結關係集合已存在在預取區域中時，控制器160則進行一更新程序，以更新最新的讀取狀態。

第3圖為本發明所提供之一隨機存取記憶體中之表之一種實施例的方塊圖。如第3圖所示，當資料儲存裝置140被上電後，控制器160在隨機存取記憶體166中建立空白之一預取區域對應表SMR_TB、一反序表RSE_TB以及一順序表SE_TB，以記錄預取區域CA中資料的狀態。

預取區域CA具有複數區段S_0~S_N用以儲存資料鏈結關係表TB1中部分之資料鏈結關係集合，其中一個區段用以儲存一個資料鏈結關係集合。換言之，區段S_0~S_N的數量小於資料鏈結關係集合TS_0~TS_M之數量，也就是N<M。

預取區域對應表SMR_TB具有複數區段對應欄SMR_0~SMR_N用以紀錄相應於預取區域CA中之資料鏈結關係集合TS_0~TS_M的集合指標，其中預取區域對應表SMR_TB中之區段對應欄SMR_0~SMR_N依序相應於預取區域CA中之區段S_0~S_N。值得注意的是，預取區域對應表SMR_TB中每一區段對應欄SMR_0~SMR_N的初始值皆為一特定值。在本實施例中，特定值為0xFFFF，但本發明不限於此。另外，資料鏈結關係集合TS_0~TS_M的集合指標皆不等於特定值。

順序表SE_TB用以紀錄資料鏈結關係集合TS_0~TS_M自預取區域CA中被讀取之順序，其中順序表SE_TB 具有複數順序欄SE_0~SE_N依序相應於預取區域CA中之區段S_0~S_N。順序表SE_TB中之每一順序欄SE_0~SE_N係用以儲存另一順序欄的共用指標，以分別指向在相應於順序欄之區段之前上一個被讀取之資料鏈結關係集合之區段所相應之順序欄。值得注意的是，順序表SE_TB中每一順序欄SE_0~SE_N的初始值皆為一特定值。在本實施例中，特定值為0xFFFF，但本發明不限於此。

反序表RSE_TB用以紀錄資料鏈結關係集合TS_0~TS_M自預取區域CA中被讀取之反向的順序，其中反序表RSE_TB具有複數反序欄RSE_0~RSE_N依序相應於預取區域CA中之區段S_0~S_N。反序表RSE_TB中之每一反序欄RSE_0~RSE_N係用以儲存另一反序欄的共用指標，以分別指向在相應於反序欄之區段之後下一個被讀取之資料鏈結關係集合之區段所相應之反序欄。值得注意的是，反序表RSE_TB中每一反序欄RSE_0~RSE_N的初始值皆為一特定值。在本實施例中，特定值為0xFFFF，但本發明不限於此。

值得注意的是，在一實施例中，區段S_0~S_N依序具有特定之共用指標CIX_0~CIX_N。區段對應欄SMR_0~SMR_N與其相應之區段S_0~S_N具有相同之共用指標CIX_0~CIX_N。順序欄SE_0~SE_N與其相應之區段S_0~S_N具有相同之共用指標CIX_0~CIX_N。反序欄RSE_0~RSE_N與其相應之區段S_0~S_N具有相同之共用指標CIX_0~CIX_N。詳細而言，區段S_0、順序欄SE_0、區段對應欄SMR_0以及反序欄RSE_0之共用指標皆為CIX_0。區段S_1、順序欄SE_1、區段對應欄SMR_1以及反序欄RSE_1之共用指標皆為CIX_1。區段S_2、順序欄SE_2、區段對應欄SMR_2以及反序欄RSE_2之共用指標皆為CIX_2，依此類推。值得注意的是，每一共用指標CIX_0~CIX_N皆不等於特定值。在一實施例中，共用指標CIX_0~CIX_N依序為0x0、0x1、0x2、0x3等十六進位數值，但本發明不限於此。

綜上所述，控制器160建立預取區域對應表SMR_TB，以紀錄相應於預取區域CA中之資料鏈結關係集合TS_0~TS_M的集合指標。控制器160建立反序表RSE_TB，以紀錄資料鏈結關係集合TS_0~TS_M自預取區域CA中被讀取之反向的順序。控制器160建立順序表SE_TB，以紀錄資料鏈結關係集合TS_0~TS_M自預取區域CA中被讀取之順序。在一實施例中，控制器160更用以在隨機存取記憶體166中建立一頭指標HIX以及一尾指標TIX，其中頭指標HIX以及尾指標TIX也可以建立於其他記憶體或者電路中，本發明不限於此。頭指標HIX為預取區域CA中最後一個被讀取之區段S_0~S_N之共用指標CIX_0~CIX_N，以指向預取區域CA中最後一個被讀取之區段S_0~S_N。尾指標TIX為預取區域CA中最久未被讀取之區段S_0~S_N之共用指標CIX_0~CIX_N，以指向預取區域CA中最久未被讀取之區段S_0~S_N。值得注意的是，由於彼此相應之區段、順序欄、區段對應欄以及反序欄具有相同之共用指標，故頭指標HIX以及尾指標TIX同時也指向相應之順序欄、區段對應欄以及反序欄。在本實施例中，控制器160可根據尾指標TIX，選擇預取區域CA中之複數區段S_0~S_N中之一者。換言之，控制器160可根據尾指標TIX選擇預取區域CA中最久未被讀取之區段(最久未被讀取之資料鏈結關係集合)，以將新的資料鏈結關係集合載入所選擇之區段。另外，控制器160可根據一頭指標HIX、反序表RSE_TB中之資料以及順序表SE_TB中之資料，更新反序表RSE_TB以及順序表SE_TB。接著，以下段落將自第3圖至第8圖依序說明預取區域CA、預取區域對應表SMR_TB、反序表RSE_TB以及順序表SE_TB之間的關係。

在第3圖初始狀態的實施例中，當控制器160接收到一讀取命令或者一寫入命令時，控制器160根據所接收之讀取命令或者寫入命令，找出包括讀取命令或者寫入命令所指定之頁面之一第一對應關係的一第一資料鏈結關係集合。舉例而言，讀取命令或者寫入命令指示之頁面的邏輯位址與實體位址的對應關係是儲存於資料鏈結關係集合TS_2，控制器160則根據所接收之讀取命令或者寫入命令得知所指定之頁面，並找到對應的資料鏈結關係集合TS_2。接著，控制器160根據預取區域對應表SMR_TB中是否存在相應於第一資料鏈結關係集合TS_2的集合指標，判斷資料鏈結關係集合TS_2是否已被載入預取區域CA。舉例而言，資料鏈結關係集合TS_2的集合指標為0xAA。如第3圖所示，若預取區域CA皆未寫入任何資料鏈結關係集合時，預取區域對應表SMR_TB中所有區段對應欄SMR_0~SMR_N皆為0xFFFF。因此，在本實施例中，控制器160判斷資料鏈結關係集合TS_2的集合指標0xAA不存在於預取區域對應表SMR_TB中。換言之，控制器160根據資料鏈結關係集合TS_2的集合指標0xAA不存在於預取區域對應表SMR_TB 中，判斷預取區域CA中不具有資料鏈結關係集合TS_2。接著，控制器160判斷預取區域CA是否具有空白之區段S_0~S_N。如第3圖所示，預取區域CA之區段S_0~S_N皆是空白的，控制器160選擇一空白之區段。在本實施例中，控制器160從最底部的區段開始選擇，故控制器160選擇區段S_N。接著，控制器160自快閃記憶體180中之資料鏈結關係表TB1讀取資料鏈結關係集合TS_2，以將資料鏈結關係集合TS_2載入所選擇之空白的區段S_N。接著，控制器160更新預取區域對應表SMR_TB、順序表SE_TB、反序表RSE_TB、頭指標HIX以及尾指標TIX，以記錄目前預取區域CA的狀態。如第4圖所示，控制器160將資料鏈結關係集合TS_2的集合指標0xAA寫入區段S_N所相應之區段對應欄SMR_N，將頭指標HIX以及尾指標TIX同時定義為區段S_N之共用指標CIX_N。值得注意的是，在本實施例中，順序表SE_TB以及反序表RSE_TB中相應於區段S_N之順序欄SE_N以及反序欄RSE_N維持特定值0xFFFF。最後，控制器160讀取儲存於預取區域CA之資料鏈結關係集合TS_2以執行所接收到之寫入命令以及讀取命令。

接著，在第4圖的實施例中，當控制器160接收到一讀取命令或者一寫入命令時，控制器160同樣地根據所接收之讀取命令或者寫入命令，找出包括讀取命令或者寫入命令所指定之頁面之一對應關係的一資料鏈結關係集合。舉例而言，在本實施例中，讀取命令或者寫入命令所指定之頁面之一對應關係的一資料鏈結關係集合為TS_8。接著，控制器160根據預取區域對應表SMR_TB中是否存在相應於資料鏈結關係集合 TS_8的集合指標，判斷資料鏈結關係集合TS_8是否已被載入預取區域CA。舉例而言，資料鏈結關係集合TS_8的集合指標為0xBB。如第4圖所示，預取區域CA只被寫入了資料鏈結關係集合TS_2，預取區域對應表SMR_TB中只有區段對應欄SMR_N為0xAA，其他皆為0xFFFF。因此，在本實施例中，控制器160判斷資料鏈結關係集合TS_8的集合指標0xBB不存在於預取區域對應表SMR_TB中。換言之，控制器160根據資料鏈結關係集合TS_8的集合指標0xBB不存在於預取區域對應表SMR_TB中，判斷預取區域CA中不具有資料鏈結關係集合TS_8。接著，控制器160判斷預取區域CA是否具有空白之區段。如第4圖所示，預取區域CA之區段S_0~S_N-1皆是空白的，控制器160選擇一空白之區段。在本實施例中，控制器160選擇區段S_N-1。接著，控制器160自快閃記憶體180中之資料鏈結關係表TB1讀取資料鏈結關係集合TS_8，以將資料鏈結關係集合TS_8載入所選擇之空白的區段S_N-1。接著，控制器160更新預取區域對應表SMR_TB、順序表SE_TB、反序表RSE_TB、頭指標HIX以及尾指標TIX，以記錄目前預取區域CA的狀態。如第4圖所示，控制器160根據頭指標HIX，獲得在預取區域CA中最後一個被讀取之資料鏈結關係集合TS_2所屬之一區段S_N，並且將區段S_N所相應之順序欄SE_N的共用指標CIX_N，寫入相應於目前之區段S_N-1的順序欄SE_N-1。接著，控制器160將相應於目前之區段S_N-1的反序欄RSE_N-1之共用指標CIX_N-1，寫入區段S_N所相應之反序欄RSE_N。接著，控制器160將頭指標HIX定義為目前區段S_N-1之共用指標CIX_N-1，並且將尾指標TIX維持在共用指標CIX_N。更新後之預取區域對應表SMR_TB、順序表SE_TB、反序表RSE_TB、頭指標HIX以及尾指標TIX如第5圖所示。最後，控制器160讀取儲存於預取區域CA之資料鏈結關係集合TS_8以執行所接收到之寫入命令以及讀取命令。

假設控制器160陸續接收到相應於不同之資料鏈結關係集合的寫入命令以及讀取命令，控制器160則重複上述第4圖轉換到第5圖的步驟，將資料鏈結關係集合依序寫入S_N-2~S_0中，如第6圖所示。換言之，控制器160重複執行載入程序，並且寫滿所有預取區域CA。值得注意的是，在本實施例中，由於順序表SE_TB以及反序表RSE_TB的初始值即為特定值(0xFFFF)，因此在載入程序中不需要再將特定值寫入目前區段所相應之反序欄以及預取區域CA中最久未被讀取之區段所相應之順序欄中。在其他實施例中，若順序表SE_TB以及反序表RSE_TB的與所設定之特定值不同，控制器160則需要在載入程序的最後一個步驟裡將特定值寫入目前區段所相應之反序欄以及預取區域CA中最久未被讀取之區段所相應之順序欄中。

接著，以下為更新程序的說明。在第6圖的實施例中，當控制器160接收到一讀取命令或者一寫入命令時，控制器160同樣地根據所接收之讀取命令或者寫入命令，找出包括讀取命令或者寫入命令所指定之頁面之一對應關係的一資料鏈結關係集合。舉例而言，在本實施例中，讀取命令或者寫入命令所指定之頁面之一對應關係的一資料鏈結關係集合為TS_0。接著，控制器160根據預取區域對應表SMR_TB中是否存在相應於資料鏈結關係集合TS_0的集合指標0x5，判斷資料鏈結關係集合TS_0是否已被載入預取區域CA。在本實施例中，如第6圖所示，資料鏈結關係集合TS_0之集合指標0x5已存在於預取區域對應表SMR_TB中之區域對應欄SMR_2之中。因此，在本實施例中，控制器160判斷資料鏈結關係集合TS_0的集合指標0x5存在於預取區域對應表SMR_TB中。換言之，控制器160根據資料鏈結關係集合TS_0的集合指標0x5存在於預取區域對應表SMR_TB中，判斷預取區域CA中已具有資料鏈結關係集合TS_0的資料。接著，控制器160更新預取區域對應表SMR_TB、順序表SE_TB、反序表RSE_TB、頭指標HIX以及尾指標TIX，以記錄目前預取區域CA的狀態。如第6圖所示，控制器160讀取目前區段S_2之順序欄SE_2，以獲得相應於在目前區段S_2之前一個被寫入之區段為區段S_3。接著，控制器160將相應於目前區段S_2之反序欄RSE_2中所儲存之共用指標CIX_1，寫入相應於區段S_3之反序欄RSE_3。換言之，控制器160將原本指向反序欄RSE_2之反序欄RSE_3，改指向反序欄RSE_1。接著，控制器160根據目前區段S_2之共用指標CIX_2，讀取反序表RSE_TB中相應於目前區段S_2之反序欄RSE_2中的值，並且根據反序欄RSE_2中之共用指標CIX_1找到在目前區段S_2之後下一個被讀取之區段S_1之共用指標CIX_1。接著，控制器160在相應於區段S_1之順序欄SE_1中寫入目前區段S_2所相應之順序欄SE_2中所儲存之共用指標CIX_3。換言之，控制器160將原本指向順序欄SE_2之順序欄SE_1，改指向順序欄SE_3。接著，控制器160根據頭指標HIX，獲得在預取區域CA中最後一個被讀取之資料鏈結關係集合TS_1所屬之一區段S_0，並且將區段S_0所相應之順序欄SE_0的共用指標CIX_0，寫入相應於目前之區段S_2的順序欄SE_2。接著，控制器160將相應於目前之區段S_2的反序欄RSE_2之共用指標CIX_2，寫入區段S_0所相應之反序欄RSE_0。最後控制器160，將頭指標HIX定義為目前區段S_2之共用指標CIX_2，將尾指標TIX維持在共用指標CIX_N，並且將一特定值寫入目前區段S_2所相應之反序欄RSE_2中。更新後之預取區域對應表SMR_TB、順序表SE_TB、反序表RSE_TB、頭指標HIX以及尾指標TIX如第7A圖所示。接著，控制器160根據用以儲存集合指標0x5的區段對應欄SMR_2之共用指標CIX_2，讀取預取區域CA中所相應之區段S_2，以獲得資料鏈結關係集合TS_0。換言之，控制器160讀取儲存於預取區域CA之資料鏈結關係集合TS_0以執行所接收到之寫入命令以及讀取命令。

值得注意的是，在更新程序的另一個實施例中，當寫入命令以及讀取命令所相應之資料鏈結關係集合為預取區域CA中最久為被讀取之資料鏈結關係集合時，控制器160的動作則與上述第7A圖所示之操作不同。舉例而言，在本實施例中，讀取命令或者寫入命令所指定之頁面之一對應關係的一資料鏈結關係集合為TS_2。接著，控制器160根據預取區域對應表SMR_TB中是否存在相應於資料鏈結關係集合TS_2的集合指標0xAA，判斷資料鏈結關係集合TS_2是否已被載入預取區域CA。在本實施例中，如第6圖所示，資料鏈結關係集合TS_2之集合指標0xAA已存在於預取區域對應表SMR_TB中之區域對應欄SMR_N之中。因此，在本實施例中，控制器160判斷資料鏈結關係集合TS_2的集合指標0xAA存在於預取區域對應表SMR_TB中。換言之，控制器160根據資料鏈結關係集合TS_2的集合指標0xAA存在於預取區域對應表SMR_TB中，判斷預取區域CA中已具有資料鏈結關係集合TS_2的資料。值得注意的是，在本實施例中，由第6圖之尾指標TIX可知，資料鏈結關係集合為TS_2為預取區域CA中最久為被讀取之資料鏈結關係集合。接著，控制器160更新預取區域對應表SMR_TB、順序表SE_TB、反序表RSE_TB、頭指標HIX以及尾指標TIX，以記錄目前預取區域CA的狀態。如第6圖所示，控制器160根據目前區段S_N之共用指標CIX_N，讀取反序表RSE_TB中相應於目前區段S_N之反序欄RSE_N中的值，並且根據反序欄RSE_N中之共用指標CIX_N-1找到在目前區段S_N之後下一個被讀取之區段S_N-1之共用指標CIX_N-1。接著，控制器160在相應於區段S_N-1之順序欄SE_N-1中寫入目前區段S_N所相應之順序欄SE_N中所儲存之值，其中由於目前區段S_N係為最久未被讀取之區段，故其順序欄SE_N中所儲存之值為特定值。接著，控制器160根據頭指標HIX，獲得在預取區域CA中最後一個被讀取之資料鏈結關係集合TS_1所屬之一區段S_0，並且將區段S_0所相應之順序欄SE_0的共用指標CIX_0，寫入相應於目前之區段S_N的順序欄SE_N。接著，控制器160將相應於目前之區段S_N的反序欄RSE_N之共用指標CIX_N，寫入區段S_0所相應之反序欄RSE_0。最後控制器160，將頭指標HIX定義為目前區段S_N之共用指標CIX_N，將尾指標TIX定義為在目前區段S_N之後下一個被讀取之區段S_N-1之共用指標CIX_N-1，並且將特定值寫入目前頭指標所指之共用指標CIX_N所相應的反序欄RSE_N中。更新後之預取區域對應表SMR_TB、順序表SE_TB、反序表RSE_TB、頭指標HIX以及尾指標TIX如第7B圖所示。接著，控制器160根據用以儲存集合指標0xAA的區段對應欄SMR_N之共用指標CIX_N，讀取預取區域CA中所相應之區段S_N，以獲得資料鏈結關係集合TS_2。換言之，控制器160讀取儲存於預取區域CA之資料鏈結關係集合TS_2以執行所接收到之寫入命令以及讀取命令。

接著，以下為取代程序的說明。在第7A圖的實施例中，當控制器160接收到一讀取命令或者一寫入命令時，控制器160同樣地根據所接收之讀取命令或者寫入命令，找出包括讀取命令或者寫入命令所指定之頁面之一對應關係的一資料鏈結關係集合。舉例而言，在本實施例中，讀取命令或者寫入命令所指定之頁面之一對應關係的一資料鏈結關係集合為TS_77。接著，控制器160根據預取區域對應表SMR_TB中是否存在相應於資料鏈結關係集合TS_77的集合指標0x333，判斷資料鏈結關係集合TS_77是否已被載入預取區域CA。在本實施例中，假設預取區域CA並沒有資料鏈結關係集合TS_77之資料，故集合指標0x333也不存在於預取區域對應表SMR_TB中之任何一個區域對應欄SMR_0~SMR_N之中。控制器160根據資料鏈結關係集合TS_77的集合指標0x333不存在於預取區域對應表SMR_TB中，判斷預取區域CA中不具有資料鏈結關係集合TS_77。接著，控制器160判斷預取區域CA是否具有空白之區段。如第7A圖所示，預取區域CA之區段S_0~S_N皆不是空白的。接著，控制器160根據尾指標TIX判斷預取區域CA中最久未被讀取之資料鏈結關係集合，以將資料鏈結關係集合TS_77的資料寫入預取區域CA中最久未被讀取之資料鏈結關係集合所屬的區段。如第7A圖所示，控制器160根據尾指標TIX中之共用指標CIX_N，判斷預取區域CA中最久未被讀取之資料鏈結關係集合為資料鏈結關係集合TS_2，並且根據共用指標CIX_N獲得具有最久未被讀取之的區段為區段S_N。接著，控制器160自快閃記憶體180中之資料鏈結關係表TB1讀取資料鏈結關係集合TS_77，以將資料鏈結關係集合TS_77載入所獲得之區段S_N，以取代原本很久未被讀取之資料鏈結關係集合TS_2。接著，控制器160更新預取區域對應表SMR_TB、順序表SE_TB、反序表RSE_TB、頭指標HIX以及尾指標TIX，以記錄目前預取區域CA的狀態。首先，控制器160將相應於資料鏈結關係集合TS_77之集合指標0x333，寫入預取區域對應表SMR_TB中相應於區段S_N的區段對應欄SMR_N。如第7A圖所示，控制器160根據頭指標HIX，獲得在預取區域CA中最後一個被讀取之資料鏈結關係集合TS_0所屬之一區段S_2，並且將區段S_2所相應之順序欄SE_2的共用指標CIX_2，寫入相應於目前之區段S_N的順序欄SE_N。接著，控制器160將相應於目前之區段S_N的反序欄RSE_N之共用指標CIX_N，寫入區段S_2所相應之反序欄RSE_2。接著，控制器160讀取目前之區段S_N的反序欄RSE_N，以獲得在目前之區段S_N之後下一個被讀取之區段S_N-1的共用指標CIX_N-1。接著，控制器160將頭指標HIX定義為目前區段S_N之共用指標CIX_N，並且將尾指標TIX定義為在目前之區段S_N之後下一個被讀取之區段S_N-1的共用指標CIX_N-1。最後，控制器160將特定值寫入在目前之區段S_N之後下一個被讀取之區段S_N-1所相應的順序欄SE_N-1中，以及將特定值寫入相應於目前區段S_N之反序欄RSE_N中。更新後之預取區域對應表SMR_TB、順序表SE_TB、反序表RSE_TB、頭指標HIX以及尾指標TIX如第8圖所示。最後，控制器160讀取儲存於預取區域CA之資料鏈結關係集合TS_8以執行所接收到之寫入命令以及讀取命令。

第9圖為本發明所提供之一資料維護方法之一種實施例的流程圖。第9圖所示之資料維護方法適用於第1圖所示之資料儲存裝置140。流程開始於步驟S900。

在步驟S900中，在快閃記憶體160被上電後，控制器160根據所接收之至少一讀取命令或者至少一寫入命令，在隨機記憶體166中之一預取區域CA中，載入一資料鏈結關係表TB1中之複數資料鏈結關係集合TS_0~TS_N的一部份。

接著，在步驟S902中，控制器160根據所載入之資料鏈結關係表TB1的被讀取的順序，在隨機記憶體166中建立一預取區域對應表SMR_TB、一反序表RSE_TB以及一順序表SE_TB。詳細而言，控制器160在隨機記憶體166中建立預取區域對應表SMR_TB，以紀錄相應於預取區域CA中之資料鏈結關係集合的集合指標。控制器160在隨機記憶體166中建立反序表RSE_TB，以紀錄在預取區域CA中之資料鏈結關係集合自預取區域CA中被讀取之反向的順序。控制器160在隨機記憶體166 中建立順序表SE_TB，以紀錄在預取區域CA中之資料鏈結關係集合自預取區域CA中被讀取之順序。值得注意的是，在步驟S902中所述之被讀取的順序係指資料鏈結關係表TB1自預取區域CA中被控制器160讀取以執行寫入命令以及讀取命令之順序。另外，在另一實施例中，控制器160亦可根據所載入之資料鏈結關係表TB1的被讀取的順序，設置一頭指標HIX以及一尾指標TIX。當預取區域CA已被寫滿並且需要載入新的資料鏈結關係集合時，根據尾指標TIX，選擇預取區域CA中之區段S_0~S_N中之一者，以將新的資料鏈結關係集合載入所選擇之區段。在新的上述資料鏈結關係集合載入所選擇之上述區段後，控制器160可根據頭指標、反序表中之資料以及順序表SE_TB中之資料，更新上序表以及順序表。

第10圖為本發明所提供之一資料維護方法之一種實施例的流程圖。第10圖所示之資料維護方法適用於第1圖所示之資料儲存裝置140。流程開始於步驟S1000。

在步驟S1000中，控制器160接收一讀取命令或者一寫入命令。讀取命令以及寫入命令係用以對快閃記憶體180中之特定的頁面進行讀取或者寫入，讀取命令以及寫入命令可為自主機120所接收之命令或者由控制器160本身維護資料所需要的讀取以及寫入動作所產生的寫入命令以及讀取命令。

接著，在步驟S1002中，控制器160根據在步驟S1000中所接收之讀取命令或者寫入命令，判斷包括讀取命令或者寫入命令所指定之頁面的一第一對應關係之一第一資料鏈結關係集合。舉例而言，讀取命令或者寫入命令指示之頁面的邏輯位址與實體位址的對應關係是儲存於資料鏈結關係集合TS_2，控制器160則根據所接收之讀取命令或者寫入命令得知所指定之頁面，並找到對應的資料鏈結關係集合TS_2。

接著，在步驟S1004中，控制器160根據預取區域對應表SMR_TB中是否存在相應於第一資料鏈結關係集合的一第一集合指標，判斷第一資料鏈結關係集合是否已被載入預取區域CA中。當第一資料鏈結關係集合未被載入預取區域CA時，流程進行至步驟S1006；否則，流程進行至步驟S1060，以進行一更新程序。

在步驟S1006中，控制器160判斷預取區域CA中是否具有空白之區段。值得注意的是，在本實施例中，空白的區段表示在預取區域CA中尚未被載入任何資料鏈結關係集合的區段。當預取區域CA中具有空白之區段時，流程進行至步驟S1008以執行一載入程序；否則，流程進行至步驟S1030，以執行一取代程序。

在步驟S1008中，控制器160自快閃記憶體180中之一資料鏈結關係表TB1讀取第一資料鏈結關係集合，以將第一資料鏈結關係集合載入所選擇之空白的一第一區段。舉例而言，如第3圖所示，預取區域CA之區段S_0~S_N皆是空白的，控制器160選擇一空白之區段。在本實施例中，控制器160從最底部的區段開始選擇，故控制器160選擇區段S_N。接著，控制器160自快閃記憶體180中之資料鏈結關係表TB1讀取資料鏈結關係集合TS_2，以將資料鏈結關係集合TS_2載入所選擇之空白的區段S_N。在另一實施例中，如第4圖所示，預取區域CA之區段S_0~S_N-1皆是空白的，控制器160則自區段S_0~S_N-1中選擇一空白之區段。在本實施例中，由於控制器160係用以從最底部的區段開始選擇，故控制器160選擇區段S_N，控制器160選擇區段S_N-1，但本發明不限於此。接著，控制器160自快閃記憶體180中之資料鏈結關係表TB1讀取資料鏈結關係集合TS_8，以將資料鏈結關係集合TS_8載入所選擇之空白的區段S_N-1。

接著，在步驟S1010中，控制器160將相應於第一資料鏈結關係集合之第一集合指標，寫入預取區域對應表SMR_TB中相應於第一區段的區段對應欄。舉例而言，在第4圖之實施例中，控制器160係將集合指標為0xAA的資料鏈結關係集合TS_2寫入區段S_N。因此，控制器160則在步驟S1010中將資料鏈結關係集合TS_2的集合指標0xAA寫入區段S_N所相應之區段對應欄SMR_N。在第5圖之實施例中，控制器160係將集合指標為0xBB的資料鏈結關係集合TS_8寫入區段S_N-1。因此，控制器160則在步驟S1010中將資料鏈結關係集合TS_8的集合指標0xBB寫入區段S_N-1所相應之區段對應欄SMR_N-1。

接著，在步驟S1012中，控制器160判斷第一區段是否為預取區域CA中第一個被載入的資料鏈結關係集合。換言之，控制器160判斷預取區域CA中之其他區段是否皆為空白。當預取區域CA中第一個被載入的資料鏈結關係集合時，流程進行至步驟S1014；否則，流程進行至步驟S1018。值得注意的是，控制器160亦可在步驟S1006中判斷是否有空白之區段的過程中進行判斷第一區段是否為預取區域CA中第一個被載入的資料鏈結關係集合的步驟。

在步驟S1014中，控制器160將一頭指標HIX以及一尾指標TIX同時定義為第一區之一第一共用指標。舉例而言，在第4圖的實施例中，資料鏈結關係集合TS_2係第一個被寫入預取區域CA的資料鏈結關係集合，其中資料鏈結關係集合TS_2係被寫入區段S_N。因此，在步驟S1014中，控制器160將將頭指標HIX以及尾指標TIX同時定義為區段S_N之共用指標CIX_N。接著，流程進行至步驟S1090。

在步驟S1018中，控制器160根據頭指標HIX，獲得在預取區域CA中最後一個被讀取之資料鏈結關係集合所屬之一第二區段。值得注意的是，在本實施例中，預取區域CA最後一個被讀取之資料鏈結關係集合指的是，目前之預取區域CA中最後一個被控制器160自預取區域CA中讀取以進行所接收之讀取命令或者寫入命令之資料鏈結關係集合。

接著，在步驟S1020中，控制器160將順序表SE_TB中相應於第二區段所相應之一第二順序欄的共用指標，寫入相應於第一區段的第一順序欄。舉例而言，在第五圖的實施例中，資料鏈結關係集合TS_8不係第一個被寫入預取區域CA的資料鏈結關係集合，其中資料鏈結關係集合TS_8係被寫入區段S_N-1(第一區段)。在更新隨機存取記憶體166中之表前，控制器160在步驟S1018中，根據目前頭指標HIX(如第4圖所示)，獲得在預取區域CA中最後一個被讀取之資料鏈結關係集合TS_2所屬之一區段S_N(第二區段)。接著，在步驟S1020中，控制器160將區段S_N(第二區段)所相應之順序欄SE_N(第二順序欄) 的共用指標CIX_N，寫入相應於目前之區段S_N-1(第一區段)的順序欄SE_N-1(第一順序爛)。

接著，在步驟S1022中，控制器160將反序表RSE_TB中相應於第一區段之第一反序欄的共用指標，寫入第二區段所相應之一第二反序欄。舉例而言，在第五圖的實施例中，控制器160在步驟S1022中將相應於目前之區段S_N-1(第一區段)的反序欄RSE_N-1(第一反序欄)之共用指標CIX_N-1，寫入區段S_N(第二區段)所相應之反序欄RSE_N中。

接著，在步驟S1024中，控制器160將頭指標HIX定義為第一區段之一第一共用指標。舉例而言，在第五圖的實施例中，控制器160在步驟S1024中，將頭指標HIX定義為目前區段S_N-1(第一區段)之共用指標CIX_N-1(第一共用指標)，並且將尾指標TIX維持在共用指標CIX_N(第二共用指標)。接著，流程進行至步驟S1090。

在步驟S1030中，控制器160根據尾指標TIX判斷預取區域CA中最久未被讀取之資料鏈結關係集合所屬的一第三區段。值得注意的是，在本實施例中，預取區域CA中最久未被讀取之資料鏈結關係集合指的是，目前之預取區域CA中最久未被控制器160自預取區域CA中讀取以進行所接收之讀取命令或者寫入命令之資料鏈結關係集合。

接著，在步驟S1032中，控制器160將第一資料鏈結關係集合的資料寫入第三區段。舉例而言，在第8圖之實施例中，讀取命令或者寫入命令所指定之頁面之一對應關係包括於資料鏈結關係集合TS_77(第一資料鏈結關係集合)。控制器 160在步驟S1004中已判斷預取區域對應表SMR_TB中不存在相應於資料鏈結關係集合TS_77的集合指標0x333，並且控制器160在步驟S1006中已判斷預取區域CA中已不具有空白之區段。因此，在步驟S1030中，控制器160根據更動前之第7A圖所示之尾指標TIX判斷預取區域CA中最久未被讀取之資料鏈結關係集合為資料鏈結關係集合TS_2，並且資料鏈結關係集合TS_2所相應之區段為區段S_N(第三區段)。因此，在步驟S1032中，控制器160自快閃記憶體180中之資料鏈結關係表TB1讀取資料鏈結關係集合TS_77(第一資料鏈結關係集合)，以將資料鏈結關係集合TS_77載入所獲得之區段S_N(第三區段)，以取代原本很久未被讀取之資料鏈結關係集合TS_2。。

接著，在步驟S1034中，控制器160將相應於第一資料鏈結關係集合之第一集合指標，寫入預取區域對應表SMR_TB中相應於第三區段的區段對應欄。在第8圖之實施例中，控制器160接著在步驟S1034中將相應於資料鏈結關係集合TS_77(第一資料鏈結關係集合)之集合指標0x333(第一集合指標)，寫入預取區域對應表SMR_TB中相應於區段S_N(第三區段)的區段對應欄SMR_N。

接著，在步驟S1036中，控制器160根據頭指標HIX，獲得在預取區域CA中最後一個被讀取之資料鏈結關係集合所屬之一第四區段。

接著，在步驟S1038中，控制器160將順序表SE_TB中之相應於第四區段之一第四順序欄的共用指標，寫入順序表SE_TB中相應於第三區段之一第三順序欄。舉例而言，在第8 圖之實施例中，控制器160在步驟S1036中根據更動前第7A圖所示之頭指標HIX，獲得在預取區域CA中最後一個被讀取之資料鏈結關係集合TS_0係屬於之區段S_2(第四區段)。接著，在步驟S1038中，控制器160將區段S_2(第四區段)所相應之順序欄SE_2(第四順序欄)的共用指標CIX_2，寫入相應於目前之區段S_N(第三區段)的順序欄SE_N(第三順序欄)。

接著，在步驟S1040中，控制器160將反序表RSE_TB中相應於第三區段之一第三反序欄的共用指標，寫入反序表RSE_TB中相應於第四區段之一第四反序欄。舉例而言，在第8圖之實施例中，控制器160將相應於目前之區段S_N(第三區段)的反序欄RSE_N(第三反敘欄)之共用指標CIX_N，寫入區段S_2(第四區段)所相應之反序欄RSE_2(第四反序欄)。

接著，在步驟S1044中，控制器160讀取第三反序欄，以獲得反序欄RSE_0~RSE_N中一第五反序欄RSE_0~RSE_N之共用指標。換言之，控制器160讀取目前被寫入之第三區段所相應之第三反序欄，以獲得原本在目前之第三區段之後下一個被讀取之一第五區段。

接著，在步驟S1044中，控制器160將尾指標TIX定義為相應於第五反序欄之一第五共用指標以及將頭指標HIX定義為第三順序欄之一第三共用指標。舉例而言，在第8圖之實施例中，控制器160在步驟S1044中讀取目前之區段S_N(第三區段)的反序欄RSE_N(第三反序欄)，以獲得原本在目前之區段S_N(第三區段)之後下一個被讀取之區段S_N-1的共用指標 CIX_N-1(第五反序欄的共用指標)。接著，控制器160將頭指標HIX定義為目前區段S_N(第三區段)之共用指標CIX_N，並且將尾指標TIX定義為原本在目前之區段S_N之後下一個被讀取之區段S_N-1(第五區段)的共用指標CIX_N-1(第五共用指標)。

接著，在步驟S1046中，控制器160將一特定值寫入第三反序欄以及相應於第五共用指標之一第五順序欄。換言之，控制器160將特定值寫入目前頭指標所指向之共用指標所相應的反序欄中，並且將特定值寫入目前尾指標所指向之共用指標所相應的順序欄中。如第8圖所示，控制器160將特定值寫入相應於目前區段S_N(第三區段)之反序欄RSE_N以及共用指標CIX_N-1(第五反序欄的共用指標)所相應之順序欄SE_N-1(第五順序欄)。接著，流程進行至步驟S1090。

在步驟S1060中，控制器160讀取相應於儲存第一資料鏈結關係集合之一第六區段所相應的一第六反序欄，以獲得在第一資料鏈結關係集合之後下一個被讀取之第七區段。換言之，控制器160讀取在一反序表RSE_TB中一第六區段所相應之一第六反序欄，以獲得在第六區段之後下一個被讀取之一第七區段。舉例而言，在第7A圖的實施例中，讀取命令或者寫入命令所指定之頁面之一對應關係包括於資料鏈結關係集合為TS_0。如更動前的第6圖所示，資料鏈結關係集合TS_0之集合指標0x5已存在於預取區域對應表SMR_TB中之區域對應欄SMR_2之中。因此，控制器160在步驟S1004中已根據預取區域對應表SMR_TB存在相應於資料鏈結關係集合TS_0的集合指標0x5，判斷資料鏈結關係集合TS_0已被載入預取區域CA。接著，控制器160在步驟S1060中根據目前區段S_2(第六區段)之共用指標CIX_2，讀取反序表RSE_TB中相應於目前區段S_2(第六區段)之反序欄RSE_2(第六反序欄)中的值，並且根據反序欄RSE_2(第六反序欄)中之共用指標CIX_1找到在目前區段S_2(第六區段)之後下一個被讀取之區段為區段S_1。在第7B圖的實施例中，讀取命令或者寫入命令所指定之頁面之一對應關係包括於資料鏈結關係集合為TS_2。如更動前的第6圖所示，資料鏈結關係集合TS_2之集合指標0xAA已存在於預取區域對應表SMR_TB中之區域對應欄SMR_N之中。因此，控制器160在步驟S1004中已根據預取區域對應表SMR_TB存在相應於資料鏈結關係集合TS_N的集合指標0xAA，判斷資料鏈結關係集合TS_2已被載入預取區域CA。接著，控制器160在步驟S1060中根據目前區段S_N(第六區段)之共用指標CIX_N，讀取反序表RSE_TB中相應於目前區段S_N(第六區段)之反序欄RSE_N(第六反序欄)中的值，並且根據反序欄RSE_N(第六反序欄)中之共用指標CIX_N-1找到在目前區段S_N(第六區段)之後下一個被讀取之區段為區段S_N-1。

接著，在步驟S1062中，控制器160在順序表SE_TB中相應於第七區段之一第七順序欄中，寫入第六區段所相應之一第六順序欄中所儲存之共用指標。舉例而言，在第7A圖的實施例中，控制器160在步驟S1060中已獲得在目前區段S_2(第六區段)之後下一個被讀取之區段為區段S_1(第七區段)。因此，在步驟S1062中，控制器160在相應於區段S_1(第七區段)之順序欄SE_1(第七順序欄)中寫入目前區段S_2(第六區段)所相應之順序欄SE_2(第六順序欄)中所儲存之共用指標CIX_3。換言之，控制器160將原本指向順序欄SE_2(第六順序欄)之順序欄SE_1(第七順序欄)，改指向在第一資料鏈結關係集合之前上一個被讀取之區段S_3所相應之順序欄SE_3。在第7B圖的實施例中，控制器160在步驟S1060中已獲得在目前區段S_N(第六區段)之後下一個被讀取之區段為區段S_N-1(第七區段)。因此，在步驟S1062中，控制器160在相應於區段S_N-1(第七區段)之順序欄SE_N-1(第七順序欄)中寫入目前區段S_N(第六區段)所相應之順序欄SE_N(第六順序欄)中所儲存之值。

接著，在步驟S1064中，控制器160根據頭指標HIX，獲得在預取區域CA中最後一個被讀取之資料鏈結關係集合所屬之一第八區段。

接著，在步驟S1065中，控制器160根據尾指標TIX，判斷預取區域CA中最久未被讀取之資料鏈結關係集合所屬的區段是否為第六區段。當最久未被讀取之資料鏈結關係集合所屬的區段為第六區段時，流程進行至步驟S1080；否則，流程進行至步驟S1066。換言之，控制器160在本步驟中判斷目前所要讀取之資料鏈結關係集合是否為預取區域CA中最久未被讀取的資料鏈結關係集合。

在步驟S1066中，控制器160讀取相應於第六區段之第六順序欄，以獲得相應於在第六區段之前一個被寫入之一第九區段之一第九共用指標。在第7A圖之實施例中，控制器160在步驟S1065中，根據尾指標TIX判斷目前區段S_2(第六區段)所儲存之資料鏈結關係集合TS_0不是預取區域CA中最久未被讀取之資料鏈結關係集合。接著，控制器160在步驟S1066中讀取相應於目前區段S_2(第六區段)之順序欄SE_2(第六順序欄)，以獲得相應於在目前區段S_2(第六區段)之前一個被寫入之區段為區段S_3(第九區段)。

接著，在步驟S1068中，控制器160將第六反序欄中所儲存之共用指標，寫入相應於第九共用指標之一第九反序欄。舉例而言，在第7A圖的實施例中，控制器160在步驟S1068中將相應於目前區段S_2(第六區段)之反序欄RSE_2(第六反序欄)中所儲存之共用指標CIX_1，寫入相應於區段S_3(第九區段)之反序欄RSE_3(第九反序欄)。

接著，在步驟S1070中，控制器160在順序欄SE_0~SE_N中相應於第六區段之第六順序欄中，寫入順序表SE_TB中第八區段所相應之一第八順序欄的共用指標。舉例而言，在第7A圖的實施例中，控制器160在步驟S1064中根據第6圖中之頭指標HIX，獲得在預取區域CA中最後一個被讀取之資料鏈結關係集合TS_1所屬之一區段S_0(第八區段)，並且將區段S_0(第八區段)所相應之順序欄SE_0(第八順序欄)的共用指標CIX_0，寫入相應於目前之區段S_2(第六區段)的順序欄SE_2(第六順序欄)。

接著，在步驟S1072中，控制器160將反序表RSE_TB中相應於第六區段之第六反序欄的共用指標，寫入反序表RSE_TB中相應於最後一個被讀取之第八區段之一第八反序欄。舉例而言，在第7A圖的實施例中，控制器160在步驟S1072中將相應於目前之區段S_2(第六區段)的反序欄RSE_2(第六反序欄)之共用指標CIX_2，寫入區段S_0(第八區段)所相應之反序欄RSE_0(第八反序欄)。

接著，在步驟S1074中，控制器160將頭指標HIX定義為第六順序欄之一第六共用指標。舉例而言，在第7A圖的實施例中，控制器160在步驟S1074中將頭指標HIX定義為目前區段S_2之共用指標CIX_2，並且將尾指標TIX維持在共用指標CIX_N。

接著，在步驟S1076中，控制器160將一特定值寫入第六反序欄。舉例而言，在第7A圖的實施例中，控制器160在步驟S1076中，將一特定值寫入目前區段S_2(第六區段)所相應之反序欄RSE_2(第六反序欄)中。接著，流程進行值步驟S1090。

在步驟S1080中，控制器160在相應於第六區段之第六順序欄中，寫入順序表SE_TB中第八區段所相應之一第八順序欄的共用指標。在第7B圖之實施例中，控制器160在步驟S1065中，根據尾指標TIX判斷目前區段S_N(第六區段)所儲存之資料鏈結關係集合TS_2不是預取區域CA中最久未被讀取之資料鏈結關係集合。接著，控制器160在步驟S1080中讀取相應於目前區段S_2(第六區段)之順序欄SE_2(第六順序欄)，以獲得相應於在目前區段S_2(第六區段)之前一個被寫入之區段為區段S_3(第九區段)。

接著，在步驟S1082中，控制器160將反序表RSE_TB中相應於第六區段之第六反序欄的共用指標，寫入反序表RSE_TB中相應於最後一個被讀取之第八區段之一第八反序欄。舉例而言，在第7B圖之實施例中，控制器160已在步驟S1064中獲得最後一個被讀取之區段為區段S_0(第八區段)。因此，控制器160在步驟S1082中將相應於目前之區段S_N(第六區段)的反序欄RSE_N(第六反序欄)之共用指標CIX_N，寫入區段S_0(第八區段)所相應之反序欄RSE_0(第八反序欄)。

接著，在步驟S1084中，控制器160將頭指標HIX定義為第六順序欄之一第六共用指標，並且將尾指標TIX定義為第七區段之一第七共用指標。舉例而言，在第7B圖之實施例中，控制器160在步驟S1084中將頭指標HIX定義為目前區段S_2(第六區段)之共用指標CIX_2，將尾指標TIX維持在共用指標CIX_N。

接著，步驟S1086中，控制器160將一特定值寫入第六反序欄。換言之，控制器160將特定值寫入目前頭指標所指之共用指標CIX_N所相應的反序欄RSE_N中。接著，流程進行至步驟S1090。

在步驟S1090中，控制器160自預取區域CA讀取第一資料鏈結關係集合中之資料，以執行在步驟S1000中所接收之寫入命令或者讀取命令。流程結束於步驟S1090。

值得注意的是，通常對儲存於快閃記憶體180中之一個檔案進行讀寫會導致相關的資料鏈結關係集合被重複地讀取。換言之，通常某些與對讀寫檔案無關的命令所相關之資料鏈結關係集合僅會被讀取一次。有鑑於此，本發明另提供一實施例，用以將被頻繁讀取之資料鏈結關係集合以及沒有被頻繁讀取之資料鏈結關係集合分為兩個系統進行維護，其中預取區域CA所儲存之資料鏈結關係集合中被讀取之次數小於一既定值之資料鏈結關係集合屬於非頻繁資料鏈結關係集合，並且預取區域CA所儲存之資料鏈結關係集合中被讀取到達既定值之資料鏈結關係集合屬於頻繁資料鏈結關係集合。在一實施例中，既定值為1，但本發明不限於此。在其他實施例中，既定值亦可為2、3、4、5、6、7、或8，其中開發者可基於在不同情況下對快閃記憶體180進行讀取或者寫入的模式設計既定值。

第11圖為本發明所提供之一隨機存取記憶體中之表之另一種實施例的方塊圖。如第11圖所示，當資料儲存裝置140被上電後，控制器160在隨機存取記憶體166中建立空白之一預取區域對應表SMR_TB、一反序表RSE_TB以及一順序表SE_TB，以記錄預取區域CA中資料的狀態。

順序表SE_TB用以分別紀錄頻繁資料鏈結關係集合自預取區域CA中被讀取之順序以及非頻繁資料鏈結關係集合自域取區域中被讀取之順序，其中順序表SE_TB具有複數順序欄SE_0~SE_N依序相應於預取區域CA中之區段S_0~S_N。值得注意的是，在本實施例中，順序表SE_TB中之順序欄SE_0~SE_N可記錄兩種順序(頻繁資料鏈結關係集合自預取區域CA中被讀取之順序以及非頻繁資料鏈結關係集合自域取區域中被讀取之順序)。詳細而言，與頻繁資料鏈結關係集合所屬之區段具有相同之共用指標之順序欄屬於頻繁順序欄，與非頻繁資料鏈結關係集合所屬之區段具有相同之共用指標之順序欄屬於非頻繁順序欄。換言之，順序欄之屬性是動態根據所相應之區段中所儲存之繁資料鏈結關係集合的態樣(頻繁或者非頻繁)而決定的。每一頻繁順序欄係用以儲存另一頻繁順序欄的共用指標，以分別指向在相應於頻繁順序欄之區段之前上一個被讀取之頻繁資料鏈結關係集合之區段所相應之頻繁順序欄。每一非頻繁順序欄係用以儲存另一非頻繁順序欄的共用指標，以分別指向在相應於非頻繁順序欄之區段之前上一個被讀取之非頻繁資料鏈結關係集合之區段所相應之非頻繁順序欄。值得注意的是，順序表SE_TB中每一順序欄SE_0~SE_N的初始值皆為-特定值。在本實施例中，特定值為0xFFFF，但本發明不限於此。

反序表RSE_TB用以分別紀錄頻繁資料鏈結關係集合自預取區域CA中被讀取之反向的順序以及非頻繁資料鏈結關係集合自預取區域CA中被讀取之反向的順序，其中反序表RSE_TB具有複數反序欄RSE_0~RSE_N依序相應於預取區域CA中之區段S_0~S_N。值得注意的是，在本實施例中，反序表RSE_TB中之反序欄RSE_0~RSE_N可記錄兩種順序(頻繁資料鏈結關係集合自預取區域CA中被讀取之反向的順序以及非頻繁資料鏈結關係集合自域取區域中被讀取之反向的順序)。詳細而言，與頻繁資料鏈結關係集合所屬之區段具有相同之共用指標之反序欄屬於頻繁反序欄，與非頻繁資料鏈結關係集合所屬之區段具有相同之共用指標之反序欄屬於非頻繁反序欄。換言之，反序欄RSE_0~RSE_N之屬性是動態根據所相應之區段中所儲存之繁資料鏈結關係集合的態樣(頻繁或者非頻繁)而決定的。每一頻繁反序欄RSE_0~RSE_N係用以儲存另一頻繁反序欄的共用指標，以分別指向在相應於頻繁反序欄之區段之後下一個被讀取之頻繁資料鏈結關係集合之區段所相應之頻繁反序欄。每一非頻繁反序欄RSE_0~RSE_N係用以儲存另一非頻繁反序欄的共用指標，以分別指向在相應於非頻繁反序欄之區段之後下一個被讀取之非頻繁資料鏈結關係集合之區段所相應之非頻繁反序欄。值得注意的是，反序表RSE_TB中每一反序欄RSE_0~RSE_N的初始值皆為一特定值。在本實施例中，特定值為0xFFFF，但本發明不限於此。

綜上所述，控制器160建立預取區域對應表SMR_TB，以紀錄相應於預取區域CA中之資料鏈結關係集合TS_0~TS_M的集合指標。控制器160建立反序表RSE_TB，以分別紀錄頻繁資料鏈結關係集合自預取區域CA中被讀取之反向的順序以及非頻繁資料鏈結關係集合自預取區域CA中被讀取之反向的順序。控制器160建立順序表SE_TB，以分別紀錄頻繁資料鏈結關係集合自預取區域CA中被讀取之順序以及非頻繁資料鏈結關係集合自域取區域中被讀取之順序。在一實施例中，控制器160更用以在隨機存取記憶體166中建立一非頻繁指標組以及一頻繁指標組，其中非頻繁指標組用以維護非頻繁資料鏈結關係集合，並且頻繁指標組用以維護被頻繁資料鏈結關係集合。在一實施例中，非頻繁指標組係由一非頻繁頭指標LRU_HIX以及一非頻繁尾指標LRU_TIX所構成，並且頻繁指標組係由一頻繁頭指標FR_HIX以及一頻繁尾指標FR_TIX所構成。在其他實施例中，非頻繁頭指標LRU_HIX、非頻繁尾指標LRU_TIX、頻繁頭指標FR_HIX以及頻繁尾指標FR_TIX也可以建立於其他記憶體或者電路中，本發明不限於此。非頻繁頭指標LRU_HIX為用以儲存最後一個被讀取之非頻繁資料鏈結關係集合之區段的共用指標，以指向預取區域CA中最後一個被讀取之非頻繁資料鏈結關係集合。非頻繁尾指標LRU_TIX為用以儲存最久未被讀取之非頻繁資料鏈結關係集合之區段的共用指標，以指向預取區域CA中最久未被讀取之非頻繁資料鏈結關係集合。頻繁頭指標FR_HIX為用以儲存最後一個被讀取之頻繁資料鏈結關係集合之區段的共用指標，以指向預取區域CA中最後一個被讀取之頻繁資料鏈結關係集合。頻繁尾指標FR_TIX為用以儲存最久未被讀取之頻繁資料鏈結關係集合之區段的共用指標，以指向預取區域CA中最久未被讀取之頻繁資料鏈結關係集合。值得注意的是，由於彼此相應之區段、順序欄、區段對應欄以及反序欄具有相同之共用指標，故非頻繁頭指標LRU_HIX、非頻繁尾指標LRU_TIX、頻繁頭指標FR_HIX以及頻繁尾指標FR_TIX同時也指向相應之順序欄、區段對應欄以及反序欄。值得注意的是，在一實施例中，非頻繁頭指標LRU_HIX以及非頻繁尾指標LRU_TIX的初始值可為共用指標CIX_N，並且頻繁頭指標FR_HIX以及頻繁尾指標FR_TIX之初始值可為一特定值，該特定值與所有共用指標CIX_0~CIX_N不同。在另一實施例中，非頻繁頭指標LRU_HIX、非頻繁尾指標LRU_TIX、頻繁頭指標FR_HIX以及頻繁尾指標FR_TIX之初始值皆為一特定值，該特定值與所有共用指標CIX_0~CIX_N不同。

在本實施例中，任何資料鏈結關係集合TS_0~TS_M被上載至預取區域CA後，都屬於非頻繁資料鏈結關係集合，直到另一命令致使控制器160對已上載至預取區域CA之非頻繁資料鏈結關係集合進行讀取，被讀取之非頻繁資料鏈結關係集合則屬於頻繁資料鏈結關係集合。另外，控制器160可根據非頻繁尾指標LRU_TIX，選擇預取區域CA中之複數區段S_0~S_N中之一者。換言之，控制器160可根據非頻繁尾指標LRU_TIX選擇預取區域CA中最久未被讀取之非頻繁資料鏈結關係集合，以將新的資料鏈結關係集合載入用以儲存所選擇之非頻繁資料鏈結關係集合的區段。當預取區域CA中之所有資料鏈結關係集合皆屬於頻繁資料鏈結關係集合並且控制器160需要上載其他新的資料鏈結關係集合時，代表控制器160開始對另一個檔案進行讀取。因此，當非頻繁尾指標LRU_TIX並未指向任何一個共用指標時，控制器160會將頻繁指標組轉移為非頻繁指標組，並且刪除頻繁指標組中之數值。

詳細而言，當預取區域對應表SMR_TB中不存在控制器160目前需要讀取之一第一資料鏈結關係集合的第一集合指標時，控制器160判斷預取區域CA是否具有空白之區段。當控制器160判斷預取區域CA之區段S_0~S_N具有空白之一第一區段時，控制器160自快閃記憶體180中之資料鏈結關係表TB1讀取第一資料鏈結關係集合，將第一資料鏈結關係集合載入空白之第一區段。當控制器160判斷預取區域CA不具有空白之區段時，控制器160判斷非頻繁尾指標LRU_TIX是否為共用指標中之任一者。當非頻繁尾指標LRU_TIX為共用指標中之任一者時，控制器160根據非頻繁尾指標LRU_TIX判斷非頻繁資料鏈結關係集合中最久未被讀取之非頻繁資料鏈結關係集合，以將第一資料鏈結關係集合的資料寫入非頻繁資料鏈結關係集合中最久未被讀取之非頻繁資料鏈結關係集合所屬的區段。當非頻繁尾指標LRU_TIX不是共用指標中之任一者時，控制器160將頻繁尾指標FR_TIX中所儲存之共用指標寫入非頻繁尾指標LRU_TIX，將頻繁頭指標FR_HIX中所儲存之共用指標寫入非頻繁頭指標LRU_HIX，並且刪除頻繁尾指標FR_TIX以及非頻繁尾指標LRU_TIX中的共用指標。在另一實施例中，控制器160亦可在將頻繁頭指標FR_HIX中所儲存之共用指標寫入非頻繁頭指標LRU_HIX後，將與共用指標不同之一特定值寫入頻繁尾指標FR_TIX以及非頻繁尾指標LRU_TIX。另外，控制器160更用以根據非頻繁指標組以及頻繁指標組更新順序表SE_TB以及反序表RSE_TB。

在第11圖初始狀態的實施例中，當控制器160接收到一讀取命令或者一寫入命令時，控制器160根據所接收之讀取命令或者寫入命令，找出包括讀取命令或者寫入命令所指定之頁面之一第一對應關係的一第一資料鏈結關係集合。舉例而言，讀取命令或者寫入命令指示之頁面的邏輯位址與實體位址的對應關係是儲存於資料鏈結關係集合TS_2，控制器160則根據所接收之讀取命令或者寫入命令得知所指定之頁面，並找到對應的資料鏈結關係集合TS_2。接著，控制器160根據預取區域對應表SMR_TB中是否存在相應於第一資料鏈結關係集合 TS_2的集合指標，判斷資料鏈結關係集合TS_2是否已被載入預取區域CA。相似於第4圖之實施例，舉例而言，資料鏈結關係集合TS_2的集合指標為0xAA。如第11圖所示，若預取區域CA皆未寫入任何資料鏈結關係集合時，預取區域對應表SMR_TB中所有區段對應欄SMR_0~SMR_N皆為0xFFFF。因此，在本實施例中，控制器160判斷資料鏈結關係集合TS_2的集合指標0xAA不存在於預取區域對應表SMR_TB中。換言之，控制器160根據資料鏈結關係集合TS_2的集合指標0xAA不存在於預取區域對應表SMR_TB中，判斷預取區域CA中不具有資料鏈結關係集合TS_2。接著，相似於第4圖之實施例，控制器160在判斷預取區域CA具有空白之區段S_0~S_N後，選擇一空白之區段S_N，並自快閃記憶體180中之資料鏈結關係表TB1讀取資料鏈結關係集合TS_2，以將資料鏈結關係集合TS_2載入所選擇之空白的區段S_N。接著，控制器160更新預取區域對應表SMR_TB、順序表SE_TB、反序表RSE_TB、非頻繁指標組以及頻繁指標組，以記錄目前預取區域CA的狀態。如第12圖所示，控制器160將資料鏈結關係集合TS_2的集合指標0xAA寫入區段S_N所相應之區段對應欄SMR_N。值得注意的是，由於資料鏈結關係集合TS_2是新載入之資料，故資料鏈結關係集合TS_2屬於非頻繁資料鏈結關係集合。因此，控制器160將非頻繁頭指標LRU_HIX以及非頻繁尾指標LRU_TIX同時定義為區段S_N之共用指標CIX_N。值得注意的是，在本實施例中，順序表SE_TB以及反序表RSE_TB中相應於區段S_N之順序欄SE_N以及反序欄RSE_N維持特定值0xFFFF，並且頻繁頭指標 FR_HIX以及頻繁尾指標FR_TIX維持原本之狀態。最後，控制器160讀取儲存於預取區域CA之資料鏈結關係集合TS_2以執行所接收到之寫入命令以及讀取命令。值得注意的是，由於順序欄SE_N以及反序欄RSE_N與具有非頻繁資料鏈結關係集合TS_2之區段S_N具有相同之共用指標CIX_N。因此，在本實施例中，順序欄SE_N屬於非頻繁順序欄，反序欄RSE_N屬於非頻繁反序欄。

接著，在第12圖的實施例中，當控制器160接收到一讀取命令或者一寫入命令時，控制器160同樣地根據所接收之讀取命令或者寫入命令，找出包括讀取命令或者寫入命令所指定之頁面之一對應關係的一資料鏈結關係集合。舉例而言，在本實施例中，讀取命令或者寫入命令所指定之頁面之一對應關係的一資料鏈結關係集合為TS_8。接著，控制器160根據預取區域對應表SMR_TB中是否存在相應於資料鏈結關係集合TS_8的集合指標，判斷資料鏈結關係集合TS_8是否已被載入預取區域CA。舉例而言，資料鏈結關係集合TS_8的集合指標為0xBB。如第12圖所示，預取區域CA只被寫入了資料鏈結關係集合TS_2，預取區域對應表SMR_TB中只有區段對應欄SMR_N為0xAA，其他皆為0xFFFF。相似於第5圖之實施例，控制器160判斷資料鏈結關係集合TS_8的集合指標0xBB不存在於預取區域對應表SMR_TB中，並且選擇一空白之區段S_N-1。接著，控制器160自快閃記憶體180中之資料鏈結關係表TB1讀取資料鏈結關係集合TS_8，以將資料鏈結關係集合TS_8載入所選擇之空白的區段S_N-1。接著，控制器160更新預取區域對應表 SMR_TB、順序表SE_TB、反序表RSE_TB、非頻繁指標組以及頻繁指標組，以記錄目前預取區域CA的狀態。值得注意的是，由於資料鏈結關係集合TS_8是新載入之資料，故資料鏈結關係集合TS_8屬於非頻繁資料鏈結關係集合。因此，如第12圖所示，控制器160根據非頻繁頭指標LRU_HIX，獲得在預取區域CA中最後一個被讀取之非頻繁資料鏈結關係集合TS_2所屬之一區段S_N，並且將區段S_N所相應之順序欄SE_N的共用指標CIX_N，寫入相應於目前之區段S_N-1的順序欄SE_N-1。接著，控制器160將相應於目前之區段S_N-1的反序欄RSE_N-1之共用指標CIX_N-1，寫入區段S_N所相應之反序欄RSE_N。接著，控制器160將非頻繁頭指標LRU_HIX定義為目前區段S_N-1之共用指標CIX_N-1，將非頻繁尾指標LRU_TIX維持在共用指標CIX_N，並且維持頻繁頭指標FR_HIX與頻繁尾指標FR_TIX之值。更新後之預取區域對應表SMR_TB、順序表SE_TB、反序表RSE_TB、非頻繁頭指標LRU_HIX以及非頻繁尾指標LRU_TIX如第13圖所示。最後，控制器160讀取儲存於預取區域CA之資料鏈結關係集合TS_8以執行所接收到之寫入命令以及讀取命令。值得注意的是，由於順序欄SE_N-1以及反序欄RSE_N-1與具有非頻繁資料鏈結關係集合TS_8之區段S_N-1具有相同之共用指標CIX_N-1。因此，在本實施例中，順序欄SE_N-1屬於非頻繁順序欄，反序欄RSE_N-1屬於非頻繁反序欄。

假設控制器160陸續接收到相應於新的資料鏈結關係集合的寫入命令以及讀取命令，控制器160則重複上述第 12圖轉換到第13圖的步驟，將資料鏈結關係集合依序寫入S_N-2~S_0中，如第14圖所示。換言之，控制器160重複執行載入程序，並且寫滿所有預取區域CA。值得注意的是，在本實施例中，由於順序表SE_TB以及反序表RSE_TB的初始值即為特定值(0xFFFF)，因此在載入程序中不需要再將特定值寫入目前區段所相應之反序欄以及預取區域CA中最久未被讀取之區段所相應之順序欄中。在其他實施例中，若順序表SE_TB以及反序表RSE_TB的與所設定之特定值不同，控制器160則需要在載入程序的最後一個步驟裡將特定值寫入目前區段所相應之反序欄以及預取區域CA中最久未被讀取之區段所相應之順序欄中。值得注意的是，在上述過程中，由於都沒有接收到任何需要讀取已上載至預取區域CA中之資料鏈結關係集合，故頻繁頭指標FR_HIX以及頻繁尾指標FR_TIX皆維持不變。另外，在第14圖之實施例中，所有之順序欄SE_0~SE_N皆屬於非頻繁順序欄，所有反序欄RSE_0~RSE_N皆屬於非頻繁反序欄。關於頻繁資料鏈結集合之方法，請參考下述之說明。另外，關於非頻繁資料鏈結集合之更新程序，可將非頻繁頭指標LRU_HIX視作頭指標HIX並將非頻繁尾指標LRU_TIX視作尾指標TIX後參考第7A~8圖之說明，其中頻繁頭指標FR_HIX以及頻繁尾指標FR_TIX維持不變。

接著，以下為更新程序的說明。在第14圖的實施例中，當控制器160接收到一讀取命令或者一寫入命令時，控制器160同樣地根據所接收之讀取命令或者寫入命令，找出包括讀取命令或者寫入命令所指定之頁面之一對應關係的一資料鏈結關係集合。舉例而言，在本實施例中，讀取命令或者寫入命令所指定之頁面之一對應關係的一資料鏈結關係集合為TS_12。接著，控制器160根據預取區域對應表SMR_TB中是否存在相應於資料鏈結關係集合TS_12的集合指標0xABC，判斷資料鏈結關係集合TS_12是否已被載入預取區域CA。在本實施例中，如第14圖所示，資料鏈結關係集合TS_12之集合指標0xABC已存在於預取區域對應表SMR_TB中之區域對應欄SMR_3之中。因此，在本實施例中，控制器160判斷資料鏈結關係集合TS_12的集合指標0xABC存在於預取區域對應表SMR_TB中。換言之，控制器160根據資料鏈結關係集合TS_12的集合指標0xABC存在於預取區域對應表SMR_TB中，判斷預取區域CA中已具有資料鏈結關係集合TS_12的資料，其中具有資料鏈結關係集合TS_12之區段S_3為目前區段。由於資料鏈結關係集合TS_12已被上載至預取區域CA。換言之，在預取區域CA中之資料鏈結關係集合TS_12被讀取之次數已達到既定值”1”。因此，在本實施例中，資料鏈結關係集合TS_12屬於頻率資料鏈結關係集合。接著，控制器160更新預取區域對應表SMR_TB、順序表SE_TB、反序表RSE_TB、非頻率指標組以及頻率指標組，以記錄目前預取區域CA的狀態。如第14圖所示，控制器160讀取目前區段S_3之順序欄SE_3，以獲得相應於在目前區段S_3之前一個被寫入之區段為區段S_4。接著，控制器160將相應於目前區段S_3之反序欄RSE_3中所儲存之共用指標CIX_2，寫入相應於區段S_4之反序欄RSE_4。換言之，控制器160將原本指向反序欄RSE_3之反序欄RSE_4，改指向反序欄 RSE_2。接著，控制器160根據目前區段S_3之共用指標CIX_3，讀取反序表RSE_TB中相應於目前區段S_3之反序欄RSE_3中的值，並且根據反序欄RSE_3中之共用指標CIX_2找到在目前區段S_3之後下一個被讀取之區段S_2之共用指標CIX_2。接著，控制器160在相應於區段S_2之順序欄SE_2中寫入目前區段S_2所相應之順序欄SE_2中所儲存之共用指標CIX_4。換言之，控制器160將原本指向順序欄SE_3之順序欄SE_2，改指向順序欄SE_4。值得注意的是，藉由將原本指向順序欄SE_3之順序欄SE_2改指向順序欄SE_4以及將原本指向反序欄RSE_3之反序欄RSE_4改指向反序欄RSE_2的步驟，順序欄SE_3以及反序欄RSE_3已脫離了非頻繁之系統。換言之，順序表SE_TB以及反序表RSE_TB中所紀錄之非頻繁資料鏈結關係集合被讀取的順序已不包括順序欄SE_3以及反序欄RSE_3所相應之資料鏈結關係集合TS_12。接著，控制器160將特定值(0xFFFF)寫入與目前區段S_3具有相同共用指標CIX_3之順序欄SE_3，以作為順序表SE_TB中頻繁順序欄之起始，並且將特定值(0xFFFF)寫入與目前區段S_3具有相同共用指標CIX_3之反序欄RSE_3，以作為順序表RSE_TB中頻繁順序欄之起始。最後控制器160，將頻繁頭指標FR_HIX定義為目前區段S_3之共用指標CIX_3，將頻繁尾指標FR_TIX定義為目前區段S_3之共用指標CIX_3並且維持非頻繁指標組之數值。更新後之預取區域對應表SMR_TB、順序表SE_TB、反序表RSE_TB、頻繁指標組以及非頻繁指標組，如第15圖所示。接著，控制器160根據用以儲存集合指標0xABC的區段對應欄SMR_3之共用指標CIX_3，讀取預取區域CA中所相應之區段S_3，以獲得資料鏈結關係集合TS_12。換言之，控制器160讀取儲存於預取區域CA之資料鏈結關係集合TS_12以執行所接收到之寫入命令以及讀取命令。值得注意的是，由於順序欄SE_3以及反序欄RSE_3與具有非頻繁資料鏈結關係集合TS_12之區段S_3具有相同之共用指標CIX_3。因此，在本實施例中，順序欄SE_3屬於非頻繁順序欄，反序欄RSE_3屬於非頻繁反序欄。

接著，在第15圖的實施例中，當控制器160接收到一讀取命令或者一寫入命令時，控制器160同樣地根據所接收之讀取命令或者寫入命令，找出包括讀取命令或者寫入命令所指定之頁面之一對應關係的一資料鏈結關係集合。舉例而言，在本實施例中，讀取命令或者寫入命令所指定之頁面之一對應關係的一資料鏈結關係集合為TS_10。接著，控制器160根據預取區域對應表SMR_TB中是否存在相應於資料鏈結關係集合TS_10的集合指標0xCC，判斷資料鏈結關係集合TS_10是否已被載入預取區域CA。在本實施例中，如第15圖所示，資料鏈結關係集合TS_10之集合指標0xCC已存在於預取區域對應表SMR_TB中之區域對應欄SMR_N-2之中。因此，在本實施例中，控制器160判斷資料鏈結關係集合TS_10的集合指標0xCC存在於預取區域對應表SMR_TB中。換言之，控制器160根據資料鏈結關係集合TS_10的集合指標0xCC存在於預取區域對應表SMR_TB中，判斷預取區域CA中已具有資料鏈結關係集合TS_10的資料，其中具有資料鏈結關係集合TS_10之區段S_N-2為目前區段。由於資料鏈結關係集合TS_10已被上載至預取區域CA。換言之，在預取區域CA中之資料鏈結關係集合TS_10被讀取之次數已達到既定值”1”。因此，在本實施例中，資料鏈結關係集合TS_10屬於頻率資料鏈結關係集合。接著，控制器160更新預取區域對應表SMR_TB、順序表SE_TB、反序表RSE_TB、非頻率指標組以及頻率指標組，以記錄目前預取區域CA的狀態。如第15圖所示，控制器160讀取目前區段S_N-2之順序欄SE_N-2，以獲得相應於在目前區段S_N-2之前一個被寫入之區段為區段S_N-1。接著，控制器160將相應於目前區段S_N-2之反序欄RSE_N-2中所儲存之共用指標CIX_N-3，寫入相應於區段S_N-1之反序欄RSE_N-1。換言之，控制器160將原本指向反序欄RSE_N-2之反序欄RSE_N-1，改指向反序欄RSE_N-3。接著，控制器160根據目前區段S_N-2之共用指標CIX_N-2，讀取反序表RSE_TB中相應於目前區段S_N-2之反序欄RSE_N-2中的值，並且根據反序欄RSE_N-2中之共用指標CIX_N-3找到在目前區段S_N-2之後下一個被讀取之區段S_N-3之共用指標CIX_N-3。接著，控制器160在相應於區段S_N-3之順序欄SE_N-3中寫入目前區段S_N-2所相應之順序欄SE_N-2中所儲存之共用指標CIX_N-1。換言之，控制器160將原本指向順序欄SE_N-2之順序欄SE_N-3，改指向順序欄SE_N-1。值得注意的是，藉由將原本指向順序欄SE_N-2之順序欄SE_N-3改指向順序欄SE_N-1以及將原本指向反序欄RSE_N-2之反序欄RSE_N-1改指向反序欄RSE_N-3的步驟，順序欄SE_N-2以及反序欄RSE_N-2已脫離了非頻繁之系統。換言之，順序表SE_TB以及反序表RSE_TB中所紀錄之非頻繁資料鏈結關係集合被讀取的順序已不包括順序欄SE_3以及反序欄RSE_3所相應之資料鏈結關係集合TS_12。接著，控制器160根據頻繁頭指標FR_HIX，獲得在預取區域CA中最後一個被讀取之頻繁資料鏈結關係集合TS_12所屬之一區段S_3，並且將區段S_3所相應之順序欄SE_3的共用指標CIX_3，寫入相應於目前之區段S_N-2的順序欄SE_N-2。接著，控制器160根據頻繁尾指標FR_TIX，獲得在預取區域CA中最久未被讀取之頻繁資料鏈結關係集合TS_12所屬之一區段S_3，並將相應於目前之區段S_N-2的反序欄RSE_N-2之共用指標CIX_N-2，寫入區段S_3所相應之反序欄RSE_3中。值得注意的是，在本實施例中，預取區域CA裡只有一個頻繁資料鏈結關係TS_12，故頻繁資料鏈結關係TS_12為最後一個也是最久未被讀取之頻繁資料鏈結關係。最後控制器160，將頻繁頭指標FR_HIX定義為目前區段S_N-2之共用指標CIX_N-2，將頻繁尾指標TIX維持在共用指標CIX_3，並且將一特定值寫入目前區段S_N-2所相應之反序欄RSE_N-2中。另外，控制器160亦維持非頻繁指標組中之數值。更新後之預取區域對應表SMR_TB、順序表SE_TB、反序表RSE_TB、頻繁指標組以及非頻繁指標組，如第16圖所示。接著，控制器160根據用以儲存集合指標0xCC的區段對應欄SMR_N-2之共用指標CIX_N-2，讀取預取區域CA中所相應之區段S_N-2，以獲得資料鏈結關係集合TS_10。換言之，控制器160讀取儲存於預取區域CA之資料鏈結關係集合TS_10以執行所接收到之寫入命令以及讀取命令。值得注意的是，由於順序欄SE_N-2以及反序欄RSE_N-2與具有非頻繁資料鏈結關係集合 TS_10之區段S_N-2具有相同之共用指標CIX_N-2。因此，在本實施例中，順序欄SE_N-2屬於非頻繁順序欄，反序欄RSE_N-2屬於非頻繁反序欄。

接著，在第16圖的實施例中，當控制器160接收到一讀取命令或者一寫入命令時，控制器160同樣地根據所接收之讀取命令或者寫入命令，找出包括讀取命令或者寫入命令所指定之頁面之一對應關係的一資料鏈結關係集合。舉例而言，在本實施例中，讀取命令或者寫入命令所指定之頁面之一對應關係的一資料鏈結關係集合為TS_77。接著，控制器160根據預取區域對應表SMR_TB中是否存在相應於資料鏈結關係集合TS_77的集合指標0x333，判斷資料鏈結關係集合TS_77是否已被載入預取區域CA。在本實施例中，假設預取區域CA並沒有資料鏈結關係集合TS_77之資料，故集合指標0x333也不存在於預取區域對應表SMR_TB中之任何一個區域對應欄SMR_0~SMR_N之中。控制器160根據資料鏈結關係集合TS_77的集合指標0x333不存在於預取區域對應表SMR_TB中，判斷預取區域CA中不具有資料鏈結關係集合TS_77。接著，控制器160判斷預取區域CA是否具有空白之區段。如第16圖所示，預取區域CA之區段S_0~S_N皆不是空白的。接著，控制器160判斷非頻繁尾指標LRU_TIX是否為共用指標CIX_0~CIX_N中之任一者。如第16圖所示，非頻繁尾指標LRU_TIX為共用指標CIX_N。接著，控制器160根據非頻繁尾指標LRU_TIX判斷預取區域CA中最久未被讀取之非頻繁資料鏈結關係集合，以將資料鏈結關係集合TS_77的資料寫入預取區域CA中最久未被讀取之非頻繁資料鏈結關係集合所屬的區段。如第16圖所示，控制器160根據非頻繁尾指標LRU_TIX中之共用指標CIX_N，判斷預取區域CA中最久未被讀取之非頻繁資料鏈結關係集合為資料鏈結關係集合TS_2，並且根據共用指標CIX_N獲得具有最久未被讀取之非頻繁資料鏈結關係集合的區段為區段S_N。接著，控制器160自快閃記憶體180中之資料鏈結關係表TB1讀取資料鏈結關係集合TS_77，以將資料鏈結關係集合TS_77載入所獲得之區段S_N，以取代原本很久未被讀取之非頻繁資料鏈結關係集合TS_2。接著，控制器160更新預取區域對應表SMR_TB、順序表SE_TB、反序表RSE_TB、頻繁指標組以及非頻繁指標組，以記錄目前預取區域CA的狀態。首先，控制器160將相應於資料鏈結關係集合TS_77之集合指標0x333，寫入預取區域對應表SMR_TB中相應於區段S_N的區段對應欄SMR_N。如第16圖所示，控制器160根據非頻繁頭指標LRU_HIX，獲得在預取區域CA中最後一個被讀取之非頻繁資料鏈結關係集合TS_1所屬之一區段S_0，並且將區段S_0所相應之順序欄SE_0的共用指標CIX_0，寫入相應於目前之區段S_N的順序欄SE_N。接著，控制器160將相應於目前之區段S_N的反序欄RSE_N之共用指標CIX_N，寫入區段S_0所相應之反序欄RSE_0。接著，控制器160讀取目前之區段S_N的反序欄RSE_N，以獲得在目前之區段S_N之後下一個被讀取之區段S_N-1的共用指標CIX_N-1。接著，控制器160將非頻繁頭指標LRU_HIX定義為目前區段S_N之共用指標CIX_N，將非頻繁尾指標LRU_TIX定義為在目前之區段S_N之後下一個被讀取之區段S_N-1的共用指標CIX_N-1，並且維持頻繁指標組之數值。最後，控制器160將特定值寫入在目前之區段S_N之後下一個被讀取之區段S_N-1所相應的順序欄SE_N-1中，以及將特定值寫入相應於目前區段S_N之反序欄RSE_N中。更新後之預取區域對應表SMR_TB、順序表SE_TB、反序表RSE_TB、非頻繁指標組以及頻繁指標組如第17圖所示。最後，控制器160讀取儲存於預取區域CA之資料鏈結關係集合TS_77以執行所接收到之寫入命令以及讀取命令。

假設控制器160陸續接收到相應於已上載於預取區域CA的頻繁資料鏈結關係集合的寫入命令以及讀取命令，控制器160則重複上述第15圖轉換到第16圖的步驟，以更新順序表SE_TB、反序表RSE_TB以及頻繁指標組，直到預取區域CA中所有之資料皆為頻繁資料鏈結關係集合，如第18圖所示。值得注意的是，在預取區域CA僅剩下最後一個非頻繁資料鏈結關係集合TS_8時，非頻繁資料鏈結關係集合TS_8所相應之順序欄SE_N-1以及反敘欄RSE_N-1皆會為特定值(0xFFFF)。換言之，當控制器160要對非頻繁資料鏈結關係集合TS_8進行讀取並且發現其所相應之順序欄SE_N-1以及反敘欄RSE_N-1皆為特定值(0xFFFF)時，控制器160判斷即將轉換為頻繁資料鏈結關係集合之非頻繁資料鏈結關係集合TS_8為最後一個非頻繁資料鏈結關係集合。因此，控制器160會在資料鏈結關係集合TS_8所相應之資料更新至頻繁資料系統後，將非頻繁頭指標LRU_HIX以及非頻繁尾指標LRU_TIX中之共用指標刪除，如第18圖所示。

接著，在第18圖的實施例中，當控制器160接收到一讀取命令或者一寫入命令時，控制器160同樣地根據所接收之讀取命令或者寫入命令，找出包括讀取命令或者寫入命令所指定之頁面之一對應關係的一資料鏈結關係集合。舉例而言，在本實施例中，讀取命令或者寫入命令所指定之頁面之一對應關係的一資料鏈結關係集合為TS_88。接著，控制器160根據預取區域對應表SMR_TB中是否存在相應於資料鏈結關係集合TS_88的集合指標0x444，判斷資料鏈結關係集合TS_88是否已被載入預取區域CA。在本實施例中，預取區域CA並沒有資料鏈結關係集合TS_88之資料，故集合指標0x444也不存在於預取區域對應表SMR_TB中之任何一個區域對應欄SMR_0~SMR_N之中。控制器160根據資料鏈結關係集合TS_88的集合指標0x444不存在於預取區域對應表SMR_TB中，判斷預取區域CA中不具有資料鏈結關係集合TS_88。接著，控制器160判斷預取區域CA是否具有空白之區段。如第18圖所示，預取區域CA之區段S_0~S_N皆不是空白的。接著，控制器160判斷非頻繁尾指標LRU_TIX是否為共用指標CIX_0~CIX_N中之任一者。如第18圖所示，非頻繁尾指標LRU_TIX為空白或者預設值。因此，控制器160將頻繁尾指標FR_TIX中之共用指標CIX_N-1寫入非頻繁尾指標LRU_TIX中，將頻繁頭指標FR_HIX中之共用指標CIX_N-2寫入頻繁尾指標LRU_HIX中，並且刪除頻繁尾指標FR_TIX以及頻繁頭指標FR_HIX中之共用指標，如第19圖所示。接著，控制器160根據非頻繁尾指標LRU_TIX判斷預取區域CA中最久未被讀取之非頻繁資料鏈結關係集合，以將資料鏈結關係集合TS_88的資料寫入預取區域CA中最久未被讀取之非頻繁資料鏈結關係集合所屬的區段。如第19圖所示，控制器160根據非頻繁尾指標LRU_TIX中之共用指標CIX_N-1，判斷預取區域CA中最久未被讀取之非頻繁資料鏈結關係集合為資料鏈結關係集合TS_8，並且根據共用指標CIX_N-1獲得具有最久未被讀取之非頻繁資料鏈結關係集合的區段為區段S_N-1。接著，控制器160自快閃記憶體180中之資料鏈結關係表TB1讀取資料鏈結關係集合TS_88，以將資料鏈結關係集合TS_88載入所獲得之區段S_N-1，以取代原本很久未被讀取之非頻繁資料鏈結關係集合TS_8。接著，控制器160更新預取區域對應表SMR_TB、順序表SE_TB、反序表RSE_TB、頻繁指標組以及非頻繁指標組，以記錄目前預取區域CA的狀態。詳細步驟可參考第16圖以及第17圖之實施例，在此不再贅述。更新後之預取區域對應表SMR_TB、順序表SE_TB、反序表RSE_TB、非頻繁指標組以及頻繁指標組如第20圖所示。最後，控制器160讀取儲存於預取區域CA之資料鏈結關係集合TS_88以執行所接收到之寫入命令以及讀取命令。

第21圖為本發明所提供之一資料維護方法之一種實施例的流程圖。第21圖所示之資料維護方法適用於第1圖所示之資料儲存裝置140。流程開始於步驟S2100。

在步驟S2100中，在快閃記憶體160被上電後，控制器160根據所接收之至少一讀取命令或者至少一寫入命令，在隨機記憶體166中之一預取區域CA中，載入一資料鏈結關係表TB1中之複數資料鏈結關係集合TS_0~TS_N的一部份。

接著，在步驟S2102中，控制器160根據所載入之資料鏈結關係集合的被讀取的順序以及次數，在隨機記憶體166中建立一頻率指標組以及一非頻率指標組，以維護預取區域CA中之資料。詳細而言，控制器160在隨機存取記憶體166中建立一非頻繁指標組以及一頻繁指標組，其中非頻繁指標組用以維護非頻繁資料鏈結關係集合，並且頻繁指標組用以維護被頻繁資料鏈結關係集合。在一實施例中，非頻繁指標組係由一非頻繁頭指標LRU_HIX以及一非頻繁尾指標LRU_TIX所構成，並且頻繁指標組係由一頻繁頭指標FR_HIX以及一頻繁尾指標FR_TIX所構成。非頻繁頭指標LRU_HIX為用以儲存最後一個被讀取之非頻繁資料鏈結關係集合之區段的共用指標，以指向預取區域CA中最後一個被讀取之非頻繁資料鏈結關係集合。非頻繁尾指標LRU_TIX為用以儲存最久未被讀取之非頻繁資料鏈結關係集合之區段的共用指標，以指向預取區域CA中最久未被讀取之非頻繁資料鏈結關係集合。頻繁頭指標FR_HIX為用以儲存最後一個被讀取之頻繁資料鏈結關係集合之區段的共用指標，以指向預取區域CA中最後一個被讀取之頻繁資料鏈結關係集合。頻繁尾指標FR_TIX為用以儲存最久未被讀取之頻繁資料鏈結關係集合之區段的共用指標，以指向預取區域CA中最久未被讀取之頻繁資料鏈結關係集合。

在另一實施例中，在步驟S2102中，控制器160更根據所載入之資料鏈結關係集合，建立一預取區域對應表SMR_TB、一反序表RSE_TB以及一順序表SE_TB。詳細而言，控制器160在隨機記憶體166中建立預取區域對應表SMR_TB，以紀錄相應於預取區域CA中之資料鏈結關係集合的集合指標。控制器160在隨機記憶體166中建立反序表RSE_TB用以分別紀錄頻繁資料鏈結關係集合自預取區域CA中被讀取之反向的順序以及非頻繁資料鏈結關係集合自預取區域CA中被讀取之反向的順序。值得注意的是，在本實施例中，反序表RSE_TB中之反序欄RSE_0~RSE_N可記錄兩種順序(頻繁資料鏈結關係集合自預取區域CA中被讀取之反向的順序以及非頻繁資料鏈結關係集合自域取區域中被讀取之反向的順序)。相似地，控制器160在隨機記憶體166中建立順序表SE_TB，以分別紀錄頻繁資料鏈結關係集合自預取區域CA中被讀取之順序以及非頻繁資料鏈結關係集合自域取區域中被讀取之順序。當預取區域CA已被寫滿並且需要載入新的資料鏈結關係集合時，根據非頻繁尾指標LRU_TIX，選擇預取區域CA中之區段S_0~S_N中之一者，以將新的資料鏈結關係集合載入所選擇之區段。在新的上述資料鏈結關係集合載入所選擇之上述區段或者對舊的資料鏈結關係集合讀取後，控制器160可根據非頻繁指標組及/或頻繁指標組、反序表RSE_TB中之資料以及順序表SE_TB中之資料，更新隨機記憶體中之表以及指標，以紀錄預取區域CA中之資料狀態。

第22A~22H圖為本發明所提供之一資料維護方法之一種實施例的流程圖。第22A~22H圖所示之資料維護方法適用於第1圖所示之資料儲存裝置140。流程開始於步驟S2200。步驟S2200~S2212、S2260~S2262、S2266~S2272、S2276~S2282相似於第10圖之步驟S1000~S1012、S1060~S1062、 S1066~S1072、S1076~S1082，請參考第10圖之說明，在此不再贅述。

在步驟S2214中，控制器160將一非頻繁頭指標LRU_HIX以及一非頻繁尾指標LRU_TIX同時定義為第一區之一第一共用指標。舉例而言，在第12圖的實施例中，資料鏈結關係集合TS_2係第一個被寫入預取區域CA的資料鏈結關係集合，其中資料鏈結關係集合TS_2係被寫入區段S_N。因此，在步驟S2214中，控制器160將非頻繁頭指標LRU_HIX以及非頻繁尾指標LRU_TIX同時定義為區段S_N之共用指標CIX_N。接著，流程進行至步驟S2299。

在步驟S2218中，控制器160根據非頻繁頭指標LRU_HIX，獲得在預取區域CA中最後一個被讀取之非頻繁資料鏈結關係集合所屬之一第二區段。值得注意的是，在本實施例中，預取區域CA最後一個被讀取之資料鏈結關係集合指的是，目前之預取區域CA中最後一個被控制器160自預取區域CA中讀取以進行所接收之讀取命令或者寫入命令之非頻繁資料鏈結關係集合。

接著，在步驟S2220中，控制器160將順序表SE_TB中相應於第二區段所相應之一第二順序欄的共用指標，寫入相應於第一區段的第一順序欄。舉例而言，在第五圖的實施例中，資料鏈結關係集合TS_8不係第一個被寫入預取區域CA的資料鏈結關係集合，其中資料鏈結關係集合TS_8係被寫入區段S_N-1(第一區段)。在更新隨機存取記憶體166中之表前，控制器160在步驟S1018中，根據目前之非頻繁頭指標LRU_HIX(如第12圖所示)，獲得在預取區域CA中最後一個被讀取之非頻繁資料鏈結關係集合TS_2所屬之一區段S_N(第二區段)。接著，在步驟S2220中，控制器160將區段S_N(第二區段)所相應之順序欄SE_N(第二順序欄)的共用指標CIX_N，寫入相應於目前之區段S_N-1(第一區段)的順序欄SE_N-1(第一順序爛)。

接著，在步驟S2222中，控制器160將反序表RSE_TB中相應於第一區段之第一反序欄的共用指標，寫入第二區段所相應之一第二反序欄。舉例而言，在第13圖的實施例中，控制器160在步驟S2222中將相應於目前之區段S_N-1(第一區段)的反序欄RSE_N-1(第一反序欄)之共用指標CIX_N-1，寫入區段S_N(第二區段)所相應之反序欄RSE_N中。

接著，在步驟S2224中，控制器160將非頻繁頭指標LRU_HIX定義為第一區段之一第一共用指標。舉例而言，在第13圖的實施例中，控制器160在步驟S2224中，將非頻繁頭指標LRU_HIX定義為目前區段S_N-1(第一區段)之共用指標CIX_N-1(第一共用指標)，並且將非頻繁尾指標LRU_TIX維持在共用指標CIX_N(第二共用指標)，其中頻繁指標組亦維持在原本的數值。接著，流程進行至步驟S1090。

在步驟S2229中，控制器160判斷非頻繁尾指標LRU_TIX或者非頻繁頭指標LRU_HIX是否為共用指標CIX_0~CIX_N中之任一者。當非頻繁尾指標LRU_TIX或者非頻繁頭指標LRU_HIX為共用指標CIX_0~CIX_N中之一者時，流程進行至步驟S2230；否則，流程進行至步驟S2291。

在步驟S2230中，控制器160根據非頻繁尾指標 LRU_TIX判斷預取區域CA中最久未被讀取之非頻繁資料鏈結關係集合所屬的一第三區段。值得注意的是，在本實施例中，預取區域CA中最久未被讀取之非頻繁資料鏈結關係集合指的是，目前之預取區域CA中最久未被控制器160自預取區域CA中讀取以進行所接收之讀取命令或者寫入命令之非頻繁資料鏈結關係集合。

接著，在步驟S2232中，控制器160將第一資料鏈結關係集合的資料寫入第三區段。舉例而言，在第17圖之實施例中，讀取命令或者寫入命令所指定之頁面之一對應關係包括於資料鏈結關係集合TS_77(第一資料鏈結關係集合)。控制器160在步驟S2204中已判斷預取區域對應表SMR_TB中不存在相應於資料鏈結關係集合TS_77的集合指標0x333，並且控制器160在步驟S2206中已判斷預取區域CA中已不具有空白之區段。因此，在步驟S2230中，控制器160根據更動前之第16圖所示之非頻繁尾指標LRU_TIX判斷預取區域CA中最久未被讀取之非頻繁資料鏈結關係集合為資料鏈結關係集合TS_2，並且資料鏈結關係集合TS_2所相應之區段為區段S_N(第三區段)。因此，在步驟S2232中，控制器160自快閃記憶體180中之資料鏈結關係表TB1讀取資料鏈結關係集合TS_77(第一資料鏈結關係集合)，以將資料鏈結關係集合TS_77載入所獲得之區段S_N(第三區段)，以取代原本很久未被讀取之資料鏈結關係集合TS_2。

接著，在步驟S2234中，控制器160將相應於第一資料鏈結關係集合之第一集合指標，寫入預取區域對應表SMR_TB中相應於第三區段的區段對應欄。在第17圖之實施例中，控制器160接著在步驟S2234中將相應於資料鏈結關係集合TS_77(第一資料鏈結關係集合)之集合指標0x333(第一集合指標)，寫入預取區域對應表SMR_TB中相應於區段S_N(第三區段)的區段對應欄SMR_N。

接著，在步驟S2236中，控制器160根據非頻繁頭指標LRU_HIX，獲得在預取區域CA中最後一個被讀取之非頻繁資料鏈結關係集合所屬之一第四區段。

接著，在步驟S2238中，控制器160將順序表SE_TB中之相應於第四區段之一第四順序欄的共用指標，寫入順序表SE_TB中相應於第三區段之一第三順序欄。舉例而言，在第17圖之實施例中，控制器160在步驟S2236中根據更動前第16圖所示之非頻繁頭指標LRU_HIX，獲得在預取區域CA中最後一個被讀取之資料鏈結關係集合TS_0係屬於之區段S_2(第四區段)。接著，在步驟S1038中，控制器160將區段S_2(第四區段)所相應之順序欄SE_2(第四順序欄)的共用指標CIX_2，寫入相應於目前之區段S_N(第三區段)的順序欄SE_N(第三順序欄)。

接著，在步驟S2240中，控制器160將反序表RSE_TB中相應於第三區段之一第三反序欄的共用指標，寫入反序表RSE_TB中相應於第四區段之一第四反序欄。舉例而言，在第17圖之實施例中，控制器160將相應於目前之區段S_N(第三區段)的反序欄RSE_N(第三反敘欄)之共用指標CIX_N，寫入區段S_2(第四區段)所相應之反序欄RSE_2(第四反序欄)。

接著，在步驟S2242中，控制器160讀取第三反序欄，以獲得反序欄RSE_0~RSE_N中一第五反序欄RSE_0~RSE_N之共用指標。換言之，控制器160讀取目前被寫入之第三區段所相應之第三反序欄，以獲得原本在目前之第三區段之後下一個被讀取之一第五區段。

接著，在步驟S2244中，控制器160將非頻繁尾指標LRU_TIX定義為相應於第五反序欄之一第五共用指標以及將非頻繁頭指標LRU_HIX定義為第三順序欄之一第三共用指標。舉例而言，在第17圖之實施例中，控制器160在步驟S2244中讀取目前之區段S_N(第三區段)的反序欄RSE_N(第三反序欄)，以獲得原本在目前之區段S_N(第三區段)之後下一個被讀取之區段S_N-1的共用指標CIX_N-1(第五反序欄的共用指標)。接著，控制器160將非頻繁頭指標LRU_HIX定義為目前區段S_N(第三區段)之共用指標CIX_N，並且將非頻繁尾指標LRU_TIX定義為原本在目前之區段S_N之後下一個被讀取之區段S_N-1(第五區段)的共用指標CIX_N-1(第五共用指標)。

接著，在步驟S2246中，控制器160將一特定值寫入第三反序欄以及相應於第五共用指標之一第五順序欄。換言之，控制器160將特定值寫入目前頭指標所指向之共用指標所相應的反序欄中，並且將特定值寫入目前尾指標所指向之共用指標所相應的順序欄中。如第17圖所示，控制器160將特定值寫入相應於目前區段S_N(第三區段)之反序欄RSE_N以及共用指標CIX_N-1(第五反序欄的共用指標)所相應之順序欄SE_N-1(第五順序欄)。接著，流程進行至步驟S2299。

在步驟S2259中，控制器160判斷頻繁頭指標 FR_HIX或者頻繁尾指標FR_TIX是否為共用指標CIX_0~CIX_N中之任一者。當頻繁頭指標FR_HIX為共用指標CIX_0~CIX_N中之一者時，流程進行至步驟S2260；否則，流程進行至步驟S2293。

接著，在步驟S2264中，控制器160根據頻繁頭指標FR_HIX，獲得在預取區域CA中最後一個被讀取之頻繁資料鏈結關係集合所屬之一第八區段。

接著，在步驟S2265中，控制器160根據頻繁尾指標FR_TIX，判斷預取區域CA中最久未被讀取之資料鏈結關係集合所屬的區段是否為第六區段。當最久未被讀取之資料鏈結關係集合所屬的區段為第六區段時，流程進行至步驟S2280；否則，流程進行至步驟S2266。換言之，控制器160在本步驟中判斷目前所要讀取之資料鏈結關係集合是否為預取區域CA中最久未被讀取的資料鏈結關係集合。

接著，在步驟S2274中，控制器160將頻繁頭指標FR_HIX定義為第六順序欄之一第六共用指標。

接著，在步驟S2284中，控制器160將頻繁頭指標FR_HIX定義為第六順序欄之一第六共用指標，並且將頻繁尾指標FR_TIX定義為第七區段之一第七共用指標。

接著，步驟S2286中，控制器160將一特定值寫入第六反序欄。換言之，控制器160將特定值寫入目前頭指標所指之共用指標CIX_N所相應的反序欄RSE_N中。接著，流程進行至步驟S2299。

在步驟S2291中，控制器160將頻繁尾指標FR_TIX 中所儲存之共用指標寫入非頻繁尾指標LRU_TIX，將頻繁頭指標FR_HIX中所儲存之共用指標寫入非頻繁頭指標LRU_HIX。

接著，在步驟S2292中，控制器160刪除頻繁尾指標FR_TIX以及非頻繁尾指標LRU_TIX中的共用指標。在另一實施例中，控制器160亦可在將頻繁頭指標FR_HIX中所儲存之共用指標寫入非頻繁頭指標LRU_HIX後，將預設值寫入頻繁尾指標FR_TIX以及非頻繁尾指標LRU_TIX。舉例而言，在步驟S2229中，控制器160判斷非頻繁尾指標LRU_TIX或者非頻繁頭指標LRU_HIX皆非共用指標CIX_0~CIX_N中之任一者，如第18圖所示。接著，控制器160則在步驟S2291~S2292中，將頻繁尾指標FR_TIX中所儲存之共用指標CIX_N-1寫入非頻繁尾指標LRU_TIX，將頻繁頭指標FR_HIX中所儲存之共用指標CIX_N-2寫入非頻繁頭指標LRU_HIX，並且刪除頻繁尾指標FR_TIX以及非頻繁尾指標LRU_TIX中的共用指標。接著，流程進行至步驟S2230。

在步驟S2293中，控制器160讀取相應於儲存第一資料鏈結關係集合之一第六區段所相應的一第六反序欄，以獲得在第一資料鏈結關係集合之後下一個被讀取之第七區段。換言之，控制器160讀取在一反序表RSE_TB中一第六區段所相應之一第六反序欄，以獲得在第六區段之後下一個被讀取之一第七區段。舉例而言，在第15圖的實施例中，讀取命令或者寫入命令所指定之頁面之一對應關係包括於資料鏈結關係集合為TS_12。如更動前的第14圖所示，資料鏈結關係集合TS_12之集合指標0xABC已存在於預取區域對應表SMR_TB中之區域對應欄SMR_3之中。因此，控制器160在步驟S2204中已根據預取區域對應表SMR_TB存在相應於資料鏈結關係集合TS_3的集合指標0xABC，判斷資料鏈結關係集合TS_12已被載入預取區域CA。接著，控制器160在步驟S2293中根據目前區段S_3(第六區段)之共用指標CIX_3，讀取反序表RSE_TB中相應於目前區段S_3(第六區段)之反序欄RSE_3(第六反序欄)中的值，並且根據反序欄RSE_3(第六反序欄)中之共用指標CIX_2找到在目前區段S_3(第六區段)之後下一個被讀取之區段為區段S_2。

接著，在步驟S2294中，控制器160在順序表SE_TB中相應於第七區段之一第七順序欄中，寫入第六區段所相應之一第六順序欄中所儲存之共用指標。舉例而言，在第14圖的實施例中，控制器160在步驟S1093中已獲得在目前區段S_3(第六區段)之後下一個被讀取之區段為區段S_2(第七區段)。因此，在步驟S1094中，控制器160在相應於區段S_2(第七區段)之順序欄SE_2(第七順序欄)中寫入目前區段S_3(第六區段)所相應之順序欄SE_3(第六順序欄)中所儲存之共用指標CIX_4。換言之，控制器160將原本指向順序欄SE_3(第六順序欄)之順序欄SE_2(第七順序欄)，改指向在第一資料鏈結關係集合之前上一個被讀取之區段S_4所相應之順序欄SE_4。

接著，在步驟S2295中，控制器160讀取相應於第六區段之第六順序欄，以獲得相應於在第六區段之前一個被寫入之一第九區段之一第九共用指標。在第15圖之實施例中，控制器160在步驟S2295中讀取相應於目前區段S_3(第六區段)之順序欄SE_3(第六順序欄)，以獲得相應於在目前區段S_4(第六區段)之前一個被寫入之區段為區段S_4(第九區段)。

接著，在步驟S2296中，控制器160將第六反序欄中所儲存之共用指標，寫入相應於第九共用指標之一第九反序欄。舉例而言，在第15圖的實施例中，控制器160在步驟S2295中將相應於目前區段S_3(第六區段)之反序欄RSE_3(第六反序欄)中所儲存之共用指標CIX_2，寫入相應於區段S_4(第九區段)之反序欄RSE_4(第九反序欄)。

接著，在步驟S2297中，控制器160將特定值寫入第六順序欄以及第六反序欄。舉例而言，在第15圖的實施例中，控制器160在步驟S2297中將特定值0xFFFF寫入相應於目前區段S_3(第六區段)之反序欄RSE_3(第六反序欄)以及順序欄SE_3(第順反序欄)。

接著，在步驟S2298中，控制器160將頻繁頭指標FR_HIX以及頻繁尾指標FR_TIX定義為第六順序欄之一第六共用指標。舉例而言，在第15圖的實施例中，控制器160在步驟S2297中將頻繁頭指標FR_HIX以及頻繁尾指標FR_TIX定義為目前區段S_3之共用指標CIX_3。接著，流程進行至步驟S2299。

在步驟S2299中，控制器160自預取區域CA讀取第一資料鏈結關係集合中之資料，以執行在步驟S2200中所接收之寫入命令或者讀取命令。流程結束於步驟S2299。

本發明所提供之資料儲存裝置140以及資料維護方法可藉由指標、反序表、順序表以及一預取區域對應表紀錄預取區域中資料被讀取的狀態以更新預取區域中之資料，其中指標、反序表以及順序表可使得預取區域對應表在每次更新的過程中所需修正資料數不超五欄。

本發明之方法，或特定型態或其部份，可以以程式碼的型態存在。程式碼可儲存於實體媒體，如軟碟、光碟片、硬碟、或是任何其他機器可讀取(如電腦可讀取)儲存媒體，亦或不限於外在形式之電腦程式產品，其中，當程式碼被機器，如電腦載入且執行時，此機器變成用以參與本發明之裝置。程式碼也可透過一些傳送媒體，如電線或電纜、光纖、或是任何傳輸型態進行傳送，其中，當程式碼被機器，如電腦接收、載入且執行時，此機器變成用以參與本發明之裝置。當在一般用途處理單元實作時，程式碼結合處理單元提供一操作類似於應用特定邏輯電路之獨特裝置。

惟以上所述者，僅為本發明之較佳實施例而已，當不能以此限定本發明實施之範圍，即大凡依本發明申請專利範圍及發明說明內容所作之簡單的等效變化與修飾，皆仍屬本發明專利涵蓋之範圍內。另外本發明的任一實施例或申請專利範圍不須達成本發明所揭露之全部目的或優點或特點。此外，摘要部分和標題僅是用來輔助專利文件搜尋之用，並非用來限制本發明之權利範圍。

Claims

一種資料儲存裝置，包括：一隨機存取記憶體，具有一預取區域；一快閃記憶體，包括複數頁面，其中每一該等頁面具有一邏輯位址以及一實體位址，該快閃記憶體具有該資料鏈結關係表用以紀錄所有該等頁面之該等邏輯位址以及該等實體位址的複數對應關係，該資料鏈結關係表被分割為該等資料鏈結關係集合，每一該等資料鏈結關係集合具有該等對應關係中之至少一者，並且每一該資料鏈結關係集合相應於一集合指標；以及一控制器，用以將一資料鏈結關係表中部分之複數資料鏈結關係集合載入該預取區域中之複數區段，其中該等資料鏈結關係集合中，被讀取次數小於一既定值之資料鏈結關係集合屬於複數非頻繁資料鏈結關係集合，且被讀取次數到達該既定值之資料鏈結關係集合，屬於複數頻繁資料鏈結關係集合，其中該控制器更建立一非頻繁指標組以維護該等非頻繁資料鏈結關係集合，並且建立一頻繁指標組以維護該等頻繁資料鏈結關係集合，其中該非頻繁指標組係由一非頻繁頭指標以及一非頻繁尾指標所構成，並且該頻繁指標組係由一頻繁頭指標以及一頻繁尾指標所構成，其中該等區段依序具有複數共用指標，該非頻繁頭指標為用以儲存最後一個被讀取之該非頻繁資料鏈結關係集合之該區段的該共用指標，該非頻繁尾指標為用以儲存最久未被讀取之該非頻繁資料鏈結關係集合之該區段的該共用指標，該頻繁頭指標為用以儲存最後一個被讀取之該頻繁資料鏈結關係集合之該區段的該共用指標，該頻繁尾指標為用以儲存最久未被讀取之該頻繁資料鏈結關係集合之該區段的該共用指標，其中該隨機存取記憶體更包括一順序表、一反序表以及一預取區域對應表，其中該預取區域對應表具有複數區段對應欄用以紀錄相應於該預取區域中之該等資料鏈結關係集合的該等集合指標，該順序表用以分別紀錄該等頻繁資料鏈結關係集合自該預取區域中被讀取之順序以及該等非頻繁資料鏈結關係集合自該域取區域中被讀取之順序，並且該反序表分別用以紀錄該等頻繁資料鏈結關係集合自該預取區域中被讀取之反向的順序以及該等非頻繁資料鏈結關係集合自該預取區域中被讀取之反向的順序。
根據申請專利範圍第1項之資料儲存裝置，其中該預取區域對應表中之該等區段對應欄依序相應於該預取區域中之該等區段，該順序表具有複數順序欄依序相應於該預取區域中之該等區段，該反序表具有複數反序欄依序相應於該預取區域中之該等區段，並且該區段對應欄、該順序欄、該反序欄與其相應之該等區段具有相同之該等共用指標。
根據申請專利範圍第2項之資料儲存裝置，其中與該等頻繁資料鏈結關係集合所屬之該等區段具有相同之該等共用指標之該等順序欄屬於複數頻繁順序欄，與該等非頻繁資料鏈結關係集合所屬之該等區段具有相同之該等共用指標之該等順序欄屬於複數非頻繁順序欄，其中每一該等頻繁順序欄係用以儲存另一該頻繁順序欄的該共用指標，以分別指向在相應於該頻繁順序欄之該區段之前上一個被讀取之該頻繁資料鏈結關係集合之該區段所相應之該頻繁順序欄，其中每一該等非頻繁順序欄係用以儲存另一該非頻繁順序欄的該共用指標，以分別指向在相應於該非頻繁順序欄之該區段之前上一個被讀取之該非頻繁資料鏈結關係集合之該區段所相應之該非頻繁順序欄。
根據申請專利範圍第2項之資料儲存裝置，其中與該等頻繁資料鏈結關係集合所屬之該等區段具有相同之該等共用指標之該等反序欄屬於複數頻繁反序欄，與該等非頻繁資料鏈結關係集合所屬之該等區段具有相同之該等共用指標之該等反序欄屬於複數非頻繁反序欄，其中每一該等頻繁反序欄係用以儲存另一該頻繁反序欄的該共用指標，以分別指向在相應於該頻繁反序欄之該區段之後下一個被讀取之該頻繁資料鏈結關係集合之該區段所相應之該頻繁反序欄，每一該等非頻繁反序欄係用以儲存另一該非頻繁反序欄的該共用指標，以分別指向在相應於該非頻繁反序欄之該區段之後下一個被讀取之該非頻繁資料鏈結關係集合之該區段所相應之該非頻繁反序欄。
根據申請專利範圍第2項之資料儲存裝置，其中該控制器用以根據一讀取命令或者一寫入命令，找出包括該讀取命令或者該寫入命令所指定之上述頁面之一第一對應關係的一第一資料鏈結關係集合，並且根據該預取區域對應表中是否存在相應於該第一資料鏈結關係集合的一第一集合指標，判斷該第一資料鏈結關係集合是否已被載入該預取區域中，其中該第一資料鏈結關係集合為該等資料鏈結關係集合中之一者，該第一集合指標為該等集合指標中之一者，並且該第一對應關係為該等對應關係中之一者。
根據申請專利範圍第5項之資料儲存裝置，其中當該預取區域對應表中存在相應於該第一集合指標時，該控制器根據用以儲存該第一集合指標的該區段對應欄之該共用指標，讀取該預取區域中所相應之該區段，以獲得該第一資料鏈結關係集合，並且讀取儲存於該隨機存取記憶體中之該第一資料鏈結關係集合中之資料以進行該寫入命令或者該讀取命令。
根據申請專利範圍第6項之資料儲存裝置，其中當該預取區域對應表中不存在該第一集合指標時，該控制器判斷該預取區域是否具有空白之該區段，其中當該控制器判斷該預取區域之該區段具有空白之一第一區段時，該控制器自該快閃記憶體中之該資料鏈結關係表讀取該第一資料鏈結關係集合，將該第一資料鏈結關係集合載入空白之該第一區段。
根據申請專利範圍第7項之資料儲存裝置，其中當該控制器判斷該預取區域不具有空白之該區段時，該控制器判斷該非頻繁尾指標是否為該等共用指標中之任一者，其中當該非頻繁尾指標為該等共用指標中之任一者時，該控制器根據該非頻繁尾指標判斷該等非頻繁資料鏈結關係集合中最久未被讀取之該非頻繁資料鏈結關係集合，以將該第一資料鏈結關係集合的資料寫入該等非頻繁資料鏈結關係集合中最久未被讀取之該非頻繁資料鏈結關係集合所屬的該區段。
根據申請專利範圍第8項之資料儲存裝置，其中當該非頻繁尾指標不是該等共用指標中之任一者時，該控制器將該頻繁尾指標中所儲存之該共用指標寫入該非頻繁尾指標，將該頻繁頭指標中所儲存之該共用指標寫入該非頻繁頭指標，並且刪除該頻繁尾指標以及該非頻繁尾指標中所儲存之該等共用指標。
根據申請專利範圍第2項之資料儲存裝置，其中該控制器更用以根據該非頻繁指標組以及該頻繁指標組更新該順序表以及該反序表。
一種資料維護方法，適用於具有一快閃記憶體之一資料儲存裝置，其中該快閃記憶體包括複數頁面，其中每一該等頁面具有一邏輯位址以及一實體位址，並且該資料維護方法包括：在該快閃記憶體被上電時，根據至少一讀取命令或者至少一寫入命令，在一隨機記憶體中之一預取區域之複數區段中，載入一資料鏈結關係表中部份之複數資料鏈結關係集合，其中每一該等資料鏈結關係集合具有該等頁面中之至少一者之該邏輯位址以及該實體位址的對應關係，每一該等資料鏈結關係集合相應於一集合指標其中該等資料鏈結關係集合中被讀取之次數小於一既定值之該等資料鏈結關係集合屬於複數非頻繁資料鏈結關係集合，並且該等資料鏈結關係集合中被讀取到達該既定值之該等資料鏈結關係集合屬於複數頻繁資料鏈結關係集合；建立一非頻繁指標組，以維護該等非頻繁資料鏈結關係集合；建立一頻繁指標組，以維護該等頻繁資料鏈結關係集合，其中該非頻繁指標組係由一非頻繁頭指標以及一非頻繁尾指標所構成，並且該頻繁指標組係由一頻繁頭指標以及一頻繁尾指標所構成，其中該等區段依序具有複數共用指標，該非頻繁頭指標為用以儲存最後一個被讀取之該非頻繁資料鏈結關係集合之該區段的該共用指標，該非頻繁尾指標為用以儲存最久未被讀取之該非頻繁資料鏈結關係集合之該區段的該共用指標，該頻繁頭指標為用以儲存最後一個被讀取之該頻繁資料鏈結關係集合之該區段的該共用指標，該頻繁尾指標為用以儲存最久未被讀取之該頻繁資料鏈結關係集合之該區段的該共用指標；建立一預取區域對應表，以在該預取區域對應表中之複數區段對應欄紀錄相應於該預取區域中之該等資料鏈結關係集合的該等集合指標；建立一順序表，以分別紀錄該等頻繁資料鏈結關係集合自該預取區域中被讀取之順序以及該等非頻繁資料鏈結關係集合自該域取區域中被讀取之順序；以及建立一反序表，以分別紀錄該等頻繁資料鏈結關係集合自該預取區域中被讀取之反向的順序以及該等非頻繁資料鏈結關係集合自該預取區域中被讀取之反向的順序。
根據申請專利範圍第11項之資料維護方法，其中該預取區域對應表中之該等區段對應欄依序相應於該預取區域中之該等區段，該順序表具有複數順序欄依序相應於該預取區域中之該等區段，該反序表具有複數反序欄依序相應於該預取區域中之該等區段，並且該區段對應欄、該順序欄、該反序欄與其相應之該等區段具有相同之該等共用指標。
根據申請專利範圍第12項之資料維護方法，其中與該等頻繁資料鏈結關係集合所屬之該等區段具有相同之該等共用指標之該等順序欄屬於複數頻繁順序欄，與該等非頻繁資料鏈結關係集合所屬之該等區段具有相同之該等共用指標之該等順序欄屬於複數非頻繁順序欄，其中每一該等頻繁順序欄係用以儲存另一該頻繁順序欄的該共用指標，以分別指向在相應於該頻繁順序欄之該區段之前上一個被讀取之該頻繁資料鏈結關係集合之該區段所相應之該頻繁順序欄，其中每一該等非頻繁順序欄係用以儲存另一該非頻繁順序欄的該共用指標，以分別指向在相應於該非頻繁順序欄之該區段之前上一個被讀取之該非頻繁資料鏈結關係集合之該區段所相應之該非頻繁順序欄。
根據申請專利範圍第12項之資料維護方法，其中與該等頻繁資料鏈結關係集合所屬之該等區段具有相同之該等共用指標之該等反序欄屬於複數頻繁反序欄，與該等非頻繁資料鏈結關係集合所屬之該等區段具有相同之該等共用指標之該等反序欄屬於複數非頻繁反序欄，其中每一該等頻繁反序欄係用以儲存另一該頻繁反序欄的該共用指標，以分別指向在相應於該頻繁反序欄之該區段之後下一個被讀取之該頻繁資料鏈結關係集合之該區段所相應之該頻繁反序欄，每一該等非頻繁反序欄係用以儲存另一該非頻繁反序欄的該共用指標，以分別指向在相應於該非頻繁反序欄之該區段之後下一個被讀取之該非頻繁資料鏈結關係集合之該區段所相應之該非頻繁反序欄。
根據申請專利範圍第11項之資料維護方法，更包括：當該預取區域已被寫滿並且需要載入新的該等資料鏈結關係集合時，判斷該非頻繁尾指標是否為該等共用指標中之任一者；當該非頻繁尾指標為該等共用指標中之任一者時，根據該非頻繁尾指標判斷該等非頻繁資料鏈結關係集合中最久未被讀取之該非頻繁資料鏈結關係集合；以及將該第一資料鏈結關係集合的資料寫入該等非頻繁資料鏈結關係集合中最久未被讀取之該非頻繁資料鏈結關係集合所屬的該區段。
根據申請專利範圍第15項之資料維護方法，更包括：當該非頻繁尾指標不是該等共用指標中之任一者時，將該頻繁尾指標中所儲存之該共用指標寫入該非頻繁尾指標，將該頻繁頭指標中所儲存之該共用指標寫入該非頻繁頭指標，並且刪除該頻繁尾指標以及該非頻繁尾指標中所儲存之該等共用指標。