[發明專利]資料索引搜尋存取管理方法

無效

• 申請號: 00133553.7
• 申請日: 2000-11-10
• 公開（公告）號: CN1353364A
• 公開（公告）日: 2002-06-12
• 發明（設計）人: 林圣富
• 申請（專利權）人: 林圣富
• 主分類號: G06F12/04
• 分類號: G06F12/04;G06F17/30
• 代理公司: 上海智信專利代理有限公司
• 代理人: 李柏

本發明是指一種混合式資料索引、存取及/或搜尋方法，尤指一種利用循序檔/隨機檔混合資料結構，進行資料索引、存取/搜尋的方法。

傳統的資料檔案為了配合索引/搜尋方法，大致上可分為循序檔(Sequential?File)和隨機檔(Random?File)兩類；循序檔每一筆記錄(Record)儲存在資料儲存裝置時，是依序逐筆存入，因此將來取出時，也要依序取出，例如要取得第20筆資料，必須先依序取出第1、2、3......19、20筆資料，因此，工作效率差，但因各筆資料間只需加一區隔符號(例如ASCII碼為13的字元)，即可一筆資料接一筆資料地儲存，因此，其儲存空間較經濟；而隨機檔是每一筆記錄都是以固定長度儲存在資料儲存裝置中，因此儲存空間不經濟，但存取資料時，只要指明第幾筆資料，即可直接存取，例如要存取第8筆資料，則其邏輯位址在7N+1～8N，其中N為每筆資料的固定長度。對于資料量龐大的資料庫而言，采用隨機檔，將使資料庫的儲存空間大幅上升，例如對記錄長度為2至90個字元，平均長度約16個字元的檔案而言，隨機檔的檔案大小，大約是存相同資料的循序檔的5.3倍----90/(16+1)。基于上述原因，目前的資料結構，大致上是采取變動長度(Variablelength)的資料記錄儲存方法，再利用索引表(lndex?table)取得某筆資料在資料庫的位址。即使如此，對于索引表的存檔方式，仍然遇到該選擇循序檔儲存方式還是隨機檔儲存方式，目前最常見的方式是利用B型樹(B-tree)的索引方法來解決，例如參見美國4945475、5010478、5058002、5204958、5218696、5261088、5265244、5283894、531779、5418947、5430869、5446887、5475837、5522068、5560007、5568638專利。對于索引表隨時變動的資料庫而言，B型樹確有其優點，但對索引表不常變動的資料庫而言，除了順序集(Sequential?set)以外，還要有索引(lndex?set)，參見Donald?E.Knuth.，The?Art?of?ComPuterProgramming.VolIII：Sorting?and?Searching.Reading，Mass：Addison-Welsley(1973).，因此，其檔案大小仍比循序擋多出索引集部份的資料內容。此外，其除非該B型樹為完全B-型樹(Complete?B-tree)，否則其搜尋次數大于log₂N(N為記錄數)，亦即其搜尋效率低于隨機檔的搜尋方法(搜尋次數為log₂N)。因此，B-型樹可視為資料結構大于循序檔，搜尋效率稍遜于隨機檔的二元搜尋法(Binary?search)的索引/搜尋方法。

以資料搜尋而言，無論是B-型樹的索引搜尋方法，或隨機檔的二元搜尋法，每搜尋一次，必須對資料儲存裝置進行一次存取動作，而“存取”的機械動作，經常是最耗時的動作，因此，如何減少搜尋過程中的存取動作，乃是使搜尋效率提高的重要關鍵。

基于上述原因，發明人提出一種在搜尋程序中，可減少資料存取次數的搜尋方法，因此，該方法具有提高資料存效率的優點。再者，由于該方法配合特殊的混合式資料結構，因此，兼具有降低資料儲存空間的優點。

本發明之一目的，在于提供一種資料存取方法。

本發明之另一目的，在于提供一種資料搜尋方法。

本發明之又另一目的，在于提供一種資料存取索引搜尋方法。

本發明之再另一目的，在于提供一種混合式資料索引、存取及/或搜尋方法。

本發明的資料索引管理方法，其包括：

(1)將待索引的欄位排序，使其依序為I₁，I₂，I₃......I₁分別計算其字串長，并依序以代碼L₁，L₂，L₃，......L₁表示；