[發明專利]排序數組元素以優化數組修改的計算機系統及方法

無效

• 申請號: 01125741.5
• 申請日: 1998-01-06
• 公開（公告）號: CN1339744A
• 公開（公告）日: 2002-03-13
• 發明（設計）人: R·E·約翰森
• 申請（專利權）人: 國際商業機器公司
• 主分類號: G06F12/06
• 分類號: G06F12/06
• 代理公司: 中國專利代理(香港)有限公司
• 代理人: 王勇,王忠忠

本發明總的來說涉及計算機與數據處理系統中實現的數組數據結構，特別是涉及在諸如存儲器壓縮的應用中對數據結構的操作。

數組是一種常見的數據結構，在計算機或其它數據處理系統中用來存儲數據。在數組數據結構中通常把多個數組元素放到一個列表中，通過一個唯一的索引訪問每個數組元素。例如，許多計算機存儲器系統都以數組來管理，各個存儲器單元或一組存儲器單元都可被作為數組元素，每一元素都有對之索引的唯一的一個存儲器地址。

使用數組數據結構的最主要的優點是它能隨機訪問，比如能通過指向元素的指針或索引快速訪問每一元素。但其缺點是很難有一種高效的方法對改變整個數組大小的修改進行處理。特別是人們希望能對任一數據結構進行緊致存放，只利用所必須的存儲器空間。所以，一旦數組被修改，如刪除或增加元素，或者是對支持可變大小的數組元素的數組進行修改，改變元素的大小，跟在被修改元素后的每一個元素通常也要修改或移動其在內存的位置。但是移動數組元素是一個費時的內存傳輸操作，從而降低存儲器系統的效率。

另外，每一個數組元素可以用未使用過的存儲單元來“填充”，因此可以在不影響數組中隨后元素的起始元素地址的情況下，允許元素“變大”或“縮小”。但是這種技術會由于數組中存在尚未使用的存儲器而極其浪費。而且這種技術既無法適應數組元素的刪除與增加，也無法對溢出了可用填充的較大的數組元素進行修改。

數組一個重要的應用是存儲器壓縮，這種應用需要高存儲密度及快速的存儲器傳送操作。在一些存儲器壓縮應用中，數據頁被安排成塊的數組，然后把塊壓縮成幀，以減少內存占用量，在對壓縮的數據進行修改后，再次對它們進行壓縮。不論幀中的數據何時被修改，幀必須重新壓縮，這通常改變了幀大小及/或幀中存儲的信息量。該頁中跟在重新壓縮的幀之后的每一幀也通常被更新，例如移動或重壓縮，從而優化該頁的壓縮。當存儲在靠近一頁的開始的幀中的數據被修改時，通常該頁中絕大部分或所有幀都被更新，這對該存儲器系統中的總的性能有很顯著的影響。

因此減小修改數組中的元素所引起的性能降低是一個實際的問題，特別是在存儲器壓縮或其它類似應用中。

本發明解決現有技術中在提供維護數組的方式方面有關的這些以及其它問題，該數組通常由一種排序算法對其元素進行排序，該算法至少部分依賴于那些元素有可能被修改的所預測的頻率。具有較高修改頻率的數組元素放在靠近數組尾部的地方，以便響應對這些元素的修改將通常需要更新的數組元素數減至最小。對于那些具有較小修改可能性的數組元素，保留了需要更新較多數組元素的數組元素修改。這樣，響應任一數組元素的修改需要更新的數組元素的平均數目，對于該數組在整體上減少了，從而減少了數組修改的整體性能影響。

本發明還不限于此，它的一個特殊的有益的應用是在存儲器壓縮領域，這是因為鄰近內存邏輯頁開始位置的數據要比鄰近該頁末端位置的數據改變得頻繁。對于一個給定頁將數據塊以倒序排列，無論一個數據塊何時被修改，必須要被更新的塊的平均數減至最小。

突出本發明特征的這些以及其它優點與特點在隨后的 提出，并作為其中的一部分。但為了更好地理解本發明及其通過其應用所帶來的優點及其特色，將參照附圖及說明來描述本發明，其中描述了本發明的實施例。

圖1為描述一個數組中對元素進行各種修改時的框圖。

圖2為一個計算機系統的框圖，它與本發明的原則相一致。

圖3是圖2中計算機系統的內存映象框圖。

圖4是描述圖2計算機系統的內存邏輯頁的框圖。

圖5是描述圖1中計算機系統的一個建立表的項與一個邏輯塊數組之間的映射框圖。

圖6是顯示對圖5中邏輯塊數組進行了一種示例的數據修改后所得的結果的框圖。

本發明示意性實施例通常是通過對數值元素進行排序來操作的，這種排序是根據預測的數組元素被修改的有關頻率進行的，它允許修改數組元素，這種修改影響到數組尾部的后續元素，從而減少了由于修改數組中的任一給定元素而影響到的數組元素的平均數。特別是最好經常維護在連續內存空間的數組元素，在元素之間很少或幾乎沒有未使用的空間。從而減小數組占用的存儲量。應該可以理解，一個數組的連續存儲空間在一定程度上可以是非連續的，即邏輯存儲位置可以被映射到固定大小的分區上，比如在隨后結合所示意的實施例所討論的壓縮數據分區所示出的。

對可以影響隨后數組元素的數組元素修改操作一般包括刪除數組元素及增加新的數組元素。而且，對于支持可變長數組元素的數組來說，另一種修改操作還包括改變數組元素的大小。