(57)【要約】【課題】昇順又は降順にデータを格納したデータベース検索方法及び検索プログラムに関し、検索所要時間を短縮する。【課題】データベースに昇順又は降順に格納したデータの総数をＹ、複数のグループに分割した時のグループ内のデータ数をＸ、単一又は複数の階層をＮとして、Ｘ＝Ｙ１／ｎ  ＞２（但し、ｎ＝２Ｎ  ）の条件を満足するように、階層毎に複数のグループに分割したデータベースとし、検索データと上位の階層のグループのそれぞれの先頭ポインタに従って読出したデータと比較して、検索データが属するグループを判定し、この検索データが属するグループ内の下位の階層のグループのそれぞれ先頭ポインタに従って読出したデータと検索データとを比較して、検索データが属する下位の階層のグループを判定し、最下位の階層のグループ内のポインタに従って読出したデータと検索データとを比較する過程を含むものである。【選択図】      図１
2004287689.tif 000002
【特許請求の範囲】
【請求項１】
複数の値の異なるデータを昇順又は降順で格納したデータベースを検索する検索方法に於いて、
前記データの総数をＹ、グループ内のデータ数をＸとし、単一又は複数の階層をＮとした時に、Ｘ＝Ｙ１／ｎ  ＞２（但し、ｎ＝２Ｎ  ）の条件を満足するように、階層毎に複数のグループに分割し、検索データと上位の階層のグループのそれぞれの先頭ポインタに従って読出したデータと比較して、前記検索データが属するグループを判定し、該検索データが属するグループ内の下位の階層のグループのそれぞれ先頭ポインタに従って読出したデータと前記検索データとを比較して、該検索データが属する前記下位の階層のグループを判定し、最下位の階層のグループ内のポインタに従って読出したデータと前記検索データとを比較する過程を含む
ことを特徴とするデータベース検索方法。
【請求項２】
前記各階層について全グループの先頭ポインタに従って読出したデータと前記検索データとの比較処理を並列的に行い、最下位の階層の前記検索データが属するグループ内の全ポインタに従って読出したデータと前記検索データとの比較処理を並列的に行う過程を含むことを特徴とする請求項１記載のデータベース検索方法。
【請求項３】
複数の値の異なるデータを昇順又は降順で格納したデータベースに対する検索プログラムに於いて、
前記データの総数をＹ、グループ内のデータ数をＸとし、単一又は複数の階層をＮとした時に、Ｘ＝Ｙ１／ｎ  ＞２（但し、ｎ＝２Ｎ  ）の条件を満足するように、階層毎に複数のグループに分割するステップと、
上位の階層のグループのそれぞれの先頭ポインタを設定して、該ポインタに従って読出したデータと検索データとを比較して、該検索データが属するグループを判定し、前記検索データが属するグループ内の下位の階層のグループのそれぞれ先頭ポインタを設定し、該ポインタに従って読出したデータと前記検索データとを比較し、該検索データが属する前記下位の階層のグループを判定するステップと、
最下位の階層のグループ内のポインタを設定して、該ポインタに従って読出したデータと前記検索データとを比較するステップと
を含むことを特徴とする検索プログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、多数のデータを格納したデータベースに対して、所望のデータを検索するデータベース検索方法及びその為の検索プログラムに関する。
【０００２】
【従来の技術】
多数のデータを磁気ディスク装置等の記録装置に格納してデータベースを構築し、プロセッサ等の処理により検索する方法として、格納されているデータの種類等に対応して各種提案されている。又それぞれ値の異なるデータを格納したデータベースに於いては、昇順又は降順にデータを配列し、検索データと一致するデータを検索する場合、例えば、図１２に示すような処理により行うものであった。この場合のデータベースは、例えば、値が昇順となるように配列されてデータが格納され、それぞれのデータの格納アドレスに対応してポインタが付与されている。なお、データベースに格納されたデータには、それぞれに対応する変換データ等のデータを格納しているものである。
【０００３】
図１２に於いて、検索開始により、ポインタの初期化を行う（ｉｎｉｔｉａｌｉｚｅ  ｐｏｉｎｔｅｒ）（Ｄ１）。この初期化は、検索を開始するポインタを決定する為の処理であり、通常は、データベースの先頭アドレスを示すポインタ１に設定する。そして、このポインタにより指示されたアドレスのデータを読出し（Ｄ２）、この読出したデータと検索データとを比較し（ｒｅａｄ  ｄａｔａ＝ｓｅａｒｃｈ  ｄａｔａ）（Ｄ３）、比較一致の場合は、検索処理終了となり、比較不一致の場合は、ポインタに１を加算し（ｐｏｉｎｔｅｒ＋＋）（Ｄ４）、このポインタにより指示されたアドレスのデータを読出すステップ（Ｄ２）に移行する。ステップ（Ｄ３）に於いて比較一致しない場合は、ステップ（Ｄ４），（Ｄ２），（Ｄ３）の処理を繰り返す。
【０００４】
このデータベース検索方法は、ポインタ１から順にデータを読出して検索データと比較するものであるから、この検索データと比較一致するデータが、ポインタ値の大きい領域に格納されている場合、検索に要する時間が長くなる。そこで、データベースのポインタを前半と後半とに２分し、分割した境界のデータと検索データとを比較して、検索データと比較一致するデータが前半か後半かの何れの領域に格納されているかを判定する２分探索法が知られている。
【０００５】
図１３は、前述の２分探索法のフローチャートを示し、データベースのポインタ数を１／２とした値をポインタ値とし（Ｅ１）、このポインタ値により指示されたアドレスからデータを読出し（Ｅ２）、この読出したデータと検索データとを比較し（Ｅ３）、比較一致の場合は、ポインタ値を０として（Ｅ４）、前半のデータを検索し、比較不一致の場合は、後半のデータを検索する。従って、全体のデータベースのデータ数の半分について検索することになるから、図１２に示す場合よりも検索時間を短縮することができる。
【０００６】
図１４は、昇順又は降順に配列したデータの総数１００００のデータベースに対して、２分探索法を繰り返す従来のデータベース検索方法を示すフローチャートであり、先ず、パラメータ初期化として、データ数１００００の１／２の５０００をアドレス値（ポインタ値）とし、このアドレス値に従った領域のデータを読出し、検索データと比較し、大小関係により２分したデータベース領域の前半の領域又は後半の領域の何れに検索データが存在するかを判定する。
【０００７】
次に、検索データが存在する領域側に対するバッファ作成を行うもので、前回のアドレス値、即ち、５０００に対して、±２５００の処理によるパラメータ作成を行い、それによるアドレス値に従って読出したデータと検索データとを比較して、その大小関係により何れの領域に存在するかを判定し、次に、前回のアドレス値、即ち、５０００±２５００に対して、±１２５０の処理によるパラメータ作成を行い、それによるアドレス値に従って読出したデータと検索データとを比較して、その大小関係により何れの領域に存在するかを判定する。このような処理を順次繰り返す。
【０００８】
そして、パラメータ作成として前回のアドレス値に対して、±３としたアドレス値に従って読出したデータと検索データとを比較し、次に前回のアドレス値に対して、±２又は±１としたアドレス値の何れから読出したデータが検索データと一致することになる。
【０００９】
図１５は、図１４の２分探索方法を適用して、昇順又は降順に配列したデータの総数１００００のデータベースに対して、検索データ７６４３が格納されているアドレス値を７６４３と場合のフローチャートを示す。最初は、図１４に示す場合と同様に、パラメータ初期化としてアドレス値をデータ数１００００の１／２の５０００とする。このアドレス値に従って読出したデータと検索データ７６４３とを比較する。この場合、読出したデータが検索データ７６４３より小さいとすると、後半の領域に存在すると判定して、前回のアドレス値の５０００に２５００を加算した７５００を次のアドレス値とし、そのアドレス値に従ってデータを読出し、そのデータと検索データとを比較する。この場合、読出したデータが検索データ７６４３より小さいとすると、前回のアドレス値の７５００に１２５０を加算した８７５０を次のアドレス値とし、そのアドレス値に従ってデータを読出す。
【００１０】
又アドレス値８７５０により読出したデータが検索データ７６４３より大きい場合、前回のアドレス値の８７５０から６２５を減算した８１２５を次のアドレス値とする。このアドレス値８１２５により読出したデータが検索データ７６４３より大きい場合、前回のアドレス値８１２５から３１３を減算した７８１２を次のアドレス値とする。以下同様にアドレス値を更新して読出したデータと検索データとを比較し、比較結果の大小関係により、前回の加減算の値の１／２を加減算して次のアドレス値とし、最終的には、アドレス値７６４４により読出したデータが検索データより小さいとすると、アドレス値７６４４に対して−２又は−１としたアドレス値７６４４又はアドレス７６４３の何れかから読出したデータと検索データとが比較一致する。
【００１１】
前述の検索方法に於いては、アドレス値（ポインタ）の設定回数が１３回、参照・比較処理の回数が１３回となり、例えば、参照・比較処理を３サイクルとし、その他を１サイクルとすると、１３＋１３×３＝５２（サイクル）を要するものとなる。
【００１２】
又２分探索法を適用し、過去の探索頻度の高い検索キーを記憶しておき、この記憶した検索キーと、データベース検索時の検索キーとを比較し、比較一致により直ちに検索することを可能として、検索所要時間の短縮を図る方法が知られている（例えば、特許文献１参照）。
【００１３】
又検索キーにより検索したデータに関連するデータを、検索キーと共に関連キーとして格納し、順次、複数の関連したデータを検索する時に、関連キーを参照して検索する方法も知られている（例えば、特許文献２参照）。又昇順或いは降順にソートされているデータを前述の２分探索法を適用して探索する方法に於いて、分割数を２より大きくし、探索値（検索データ）と同じ値（データ）が含まれている可能性の高い方の検索領域に対して検索する方法も知られている（例えば、特許文献３参照）。
【００１４】
【特許文献１】
特開平５−１６５８９４号公報
【特許文献２】
特開平９−１０１９６８号公報
【特許文献３】
特開平８−３３０３７４号公報
【００１５】
【発明が解決しようとする課題】
値の異なる複数のデータと、そのデータに対応した値の変換データとをデータベースに格納し、検索データによってデータを検索し、検索データと一致したデータに対応する変換データを読出す手段、例えば、角θについて、ｓｉｎθからａｒｃ  ｓｉｎ（Ｘ）の近似解Φを求める手段が知られている。この場合、近似解Φの精度を高くする為には、角θを細かい間隔としたｓｉｎθと、それに対応するａｒｃ  ｓｉｎ（Ｘ）とを格納する必要がある。このように変換精度を高くすると、ｓｉｎθのデータ個数が増加することになるから、検索所要時間が長くなる。
【００１６】
このような多数のデータを格納したデータベースを検索する方法として、２分探索法を適用することが考えられる。その場合、２分割ではなく、更に多数に分割することも前述のように知られている。しかし、単純に分割数を増加しても、探索回数が増加するだけとなるから、探索所要時間を短縮することができない問題がある。
【００１７】
本発明は、多数のデータを格納したデータベースに対する検索所要時間の短縮を図ることを目的とする。
【００１８】
【課題を解決するための手段】
本発明のデータベース探索方法は、複数の値の異なるデータを昇順又は降順で格納したデータベースを検索する検索方法に於いて、データの総数をＹ、グループ内のデータ数をＸとし、単一又は複数の階層をＮとした時に、Ｘ＝Ｙ１／ｎ  ＞２（但し、ｎ＝２Ｎ  ）の条件を満足するように、階層毎に複数のグループに分割し、検索データと上位の階層のグループのそれぞれの先頭ポインタに従って読出したデータと比較して、検索データが属するグループを判定する。次に、検索データが属するグループ内の下位の階層のグループのそれぞれ先頭ポインタに従って読出したデータと検索データとを比較して、この検索データが属する下位の階層のグループを判定する。そして、最下位の階層のグループ内のポインタに従って読出したデータと検索データとを比較する過程を含むものである。
【００１９】
又各階層について全グループの先頭ポインタに従って読出したデータと検索データとの比較処理を並列的に行い、最下位の階層の検索データが属するグループ内の全ポインタに従って読出したデータと検索データとの比較処理を並列的に行う過程を含むことができる。
【００２０】
又本発明の検索プログラムは、複数の値の異なるデータを昇順又は降順で格納したデータベースに対する検索プログラムであって、データの総数をＹ、グループ内のデータ数をＸとし、単一又は複数の階層をＮとした時に、Ｘ＝Ｙ１／ｎ  ＞２（但し、ｎ＝２Ｎ  ）の条件を満足するように、階層毎に複数のグループに分割するステップと、上位の階層のグループのそれぞれの先頭ポインタを設定して、このポインタに従って読出したデータと検索データとを比較して、検索データが属するグループを判定し、検索データが属するグループ内の下位の階層のグループのそれぞれ先頭ポインタを設定し、このポインタに従って読出したデータと検索データとを比較し、検索データが属する下位の階層のグループを判定するステップと、最下位の階層のグループ内のポインタを設定して、このポインタに従って読出したデータと検索データとを比較するステップとを含むものである。
【００２１】
【発明の実施の形態】
図１は、データベースの階層構成を示すもので、磁気ディスク装置や光ディスク装置等により構成されたデータベース１に、昇順又は降順に配列した複数のデータを格納し、各データの格納アドレス領域を示すポインタを付与する。この複数のデータを、本発明に於いては、階層構造的に分割する。図１に於いては、最上位の階層１を複数のグループに分割し、各グループの例えばグループ１ｋを複数のグループに分割して階層２とし、更に、階層２の各グループの例えばグループ２ｋを複数のグループに分割して階層３とする。３ｋは、階層３の一つのグループを示す。以下同様にして複数階層についてそれぞれ複数のグループに分割する。この場合、全体のデータ数をＹ、グループ数をＸ、グループに属するデータ数をＺ、階層数をＮ、検索の所要時間をＴ、Ｎ＝１とした時、即ち、最上位の階層１とした時の検索所要時間は、１検索処理当たり１サイクルとすると、
Ｔ＝Ｘ＋Ｙ／Ｘ−１                                          …（１）
と表すことができる。
【００２２】
この検索所要時間Ｔが最小となる条件は、
Ｘ＝√Ｙ                                                    …（２）
の場合であり、従って、最小検索所要時間Ｔｍｉｎは、
Ｔｍｉｎ＝√Ｙ＋Ｙ／√Ｙ−１＝２√Ｙ−１                    …（３）
となる。
【００２３】
又グループ数Ｘの場合の各グループ内のデータ数Ｚは、
Ｚ＝Ｙ／Ｘ                                                  …（４）
であり、最小検索所要時間Ｔｍｉｎとなる条件を考慮すると、
Ｚ＝Ｙ／√Ｙ＝√Ｙ                                          …（５）
となる。√Ｙ＝Ｙ’とすると、２階層構成とした場合の最小検索所要時間Ｔｍｉｎは、
2004287689.tif 000003
となる。
【００２４】
又階層数Ｎは、グループ内のデータ数が２以上となる条件を満たせば良く、従って、階層数Ｎの最大値Ｎｍａｘは、
Ｙ１／ｎ  （但し、ｎ＝２Ｎ  ）＞２                                …（７）
の条件を満足するように分割できる階層数となる。
【００２５】
図１に示すデータベース１に対しては、先ず階層１、即ち、Ｎ＝１のグループ数Ｘは、Ｘ＝Ｙ１／２  ＞２の条件を満足するように分割する。又階層２、即ち、Ｎ＝２に於いては、階層１の各グループについて分割するもので、階層１の各グループについて、グループ数Ｘは、Ｘ＝Ｙ１／４  ＞２の条件を満足するように分割する。同様に、階層３、即ち、Ｎ＝３に於いては、階層２の各グループを更に分割するもので、階層２の各グループについて、グループ数Ｘは、Ｘ＝Ｙ１／８  ＞２の条件を満足するように分割する。以下同様にして複数階層構成とするものである。又（４）式に従ったグループのデータ数Ｚは、端数となる場合、何れかのグループに付加すれば良いことになる。
【００２６】
図２は、データベースの階層構成の一例と検索方法とを示すもので、データ数１００の場合に、データを昇順に配列してそれぞにポインタ１〜１００を付与した構成に於いて、階層１として、１００１／２  ＝１０＞２の条件を満足する１０グループＡ〜Ｊに分割し、更に、各グループＡ〜Ｊを、階層２として、１００１／４  ＝３．１６＞２を満足する３グループに分割する。即ち、階層２のグループはＡ１，Ａ２，Ａ３，Ｂ１，Ｂ２，Ｂ３，・・・Ｊ１，Ｊ２，Ｊ３の合計３０グループとする。この場合、１０個のデータ数の階層１のグループを３個に分割するから、端数が生じることになり、階層２のグループの例えば最後のグループＡ３，Ｂ３，・・・Ｊ３は４個のデータを含むグループとする。更に、階層３については、１００１／８  ＝１．７８＜２の条件となるから、（７）式の条件を満足しないことになる。従って、この場合のデータベースは階層１，２の２階層構成のグループに分割することになる。
【００２７】
例えば、検索データ１０８０を検索する場合、階層１のグループＢの先頭のポインタ１１により読出したデータ２１０と検索データ１０８０とを比較すると、２１０＜１０８０となる。そこで、次のグループＣの先頭のポインタ２１により読出したデータ３１０と検索データ１０８０とを比較する。この場合も、３１０＜１０８０となるから、次のグループＤの先頭ポインタ３１により読出したデータと検索データとを比較する。
【００２８】
同様にして、グループＪの先頭ポインタ９１により読出したデータ１０１０と検索データ１０８０と比較すると、１０１０＜１０８０となり、最終のグループであるから、次は、階層２のグループＪ２の先頭ポインタ９４により読出したデータ１０４０と検索データ１０８０とを比較する。この場合も、１０４０＜１０８０となるから、次のグループＪ３の先頭ポインタ９７により読出したデータ１０７０と検索データ１０８０とを比較する。この場合、１０７０＜１０８０であるから、次のポインタ９７＋１＝９８により読出したデータ１０８０と検索データ１０８０とを比較すると、１０８０＝１０８０となり、目的のデータを検索することができる。この場合、階層１のグループＢ〜Ｊのそれぞれの先頭ポインタにより読出したデータと検索データとを並列的に比較する手段を設けることにより、検索時間を短縮することができる。
【００２９】
又データ数１００００のデータベースに対しては、前述の（７）式のＹ１／ｎ  ＞２の条件により、階層１（Ｎ＝１）については、１００００１／２  ＝１００＞２の条件となり、１００個のグループに分割する。又階層２（Ｎ＝２）として、１００００１／４  ＝１０＞２の条件となるから、階層１の各グループをそれぞれ１０個のグループに分割する。又階層３（Ｎ＝３）として、１００００１／８  ＝３．１６＞２の条件となるから、階層２の各グループを３個のグループに分割する。
【００３０】
又階層４（Ｎ＝４）については、１００００１／１６＝１．７８＜２となるから、（７）式の条件を満足しないことになる。従って、１００００のデータ数のデータベースに対しては、階層１，２，３の３階層構成のグループに分割する。例えば、図２に示すポインタ１〜１００のデータベースの構成は、データ数１００００のデータベースの階層２の１グループについて、階層３のグループに分割した場合に相当するものとなる。
【００３１】
図３は検索処理の機能ブロック図を示し、初期値（入力値）１１を前述の検索データとすると、参照部１２は、パラメータ（ポインタ）生成部１４からのポインタに従ってデータを読出し、比較部（判定部）１３に於いて読出したデータと入力された検索データとを比較し、その比較結果に対応してパラメータ（ポインタ）生成部１４を制御して、ポインタの更新を行い、そのポインタに従って読出したデータと、入力された検索データとを比較し、比較一致により期待値１５を出力することになる。
【００３２】
図４は本発明の実施の形態のフローチャートを示し、データが昇順に格納されたデータベースに対して、前述のように、階層構成とした階層１，２，・・・ｎに対する検索方法を示す。即ち、データベースの階層１に対しては、階層１のグループの先頭を示すポインタの初期化を行い（Ａ１１）、このポインタに従ってデータを読出し（Ａ１２）、この読出したデータと検索データとを比較して、このグループに属するか否かを判定し（Ａ１３）、属さない場合は、次のグループの先頭を示すポインタとする為の加算処理を行い（Ａ１４）、ステップ（Ａ１２）へ移行し、ステップ（Ａ１３），（Ａ１４）の処理を繰り返す。
【００３３】
又階層１の或るグループに属す場合は、そのグループの階層２のグループに対して、先頭を示すポインタの初期化を行い（Ａ２１）、このポインタに従ってデータを読出し（Ａ２２）、この読出したデータと検索データとを比較し、このグループに属するか否かを判定し（Ａ２３）、属されない場合は、次のグループの先頭の位置を示すポインタとする為の加算処理を行い（Ａ２４）、ステップ（Ａ２２）へ移行し、ステップ（Ａ２３），（Ａ２４）の処理を繰り返す。
【００３４】
同様にして、階層ｎに於いては、ポインタを初期化し（Ａｎ１）、このポインタに従ってデータを読出し（Ａｎ２）、この読出したデータと検索データとを比較し（Ａｎ３）、比較一致により目的のデータが得られるが、比較不一致の場合は、ポインタを加算処理し（Ａｎ４）、それにより更新したポインタに従ってデータを読出して、検索データとの比較処理を行う。
【００３５】
図５は並列処理を可能とした検索処理の機能ブロック図であり、参照・比較部２２−１〜２２−ｍは、階層対応のグループ数ｍに従って並列的に読出したデータと検索データとを並列的に比較処理する機能を有し、初期値（入力値）２１を検索データとすると、パラメータ（ポインタ）生成部２４によるグループ対応のポインタに従って読出したデータとをそれぞれ並列的に比較する。判定部２３は、比較結果に応じて、検索データが属するグループか否かを判定し、検索データが属するグループの次の階層のグループに対するポインタを生成するようにパラメータ（ポインタ）生成部２４に指示する。又は検索データが属する最下位グループに対しては、順次ポインタを＋１又は−１とする処理によりポインタを更新し、そのポインタに従って読出したデータと検索データとの比較を行い、比較一致により目的のデータを出力することになる。
【００３６】
図６及び図７は、本発明の実施の形態の並列処理によるフローチャートを示し、データを昇順に配列したデータ数１００００のデータベースに対して、階層１，２，３の３階層構成とし、各階層をそれぞれ１０グループに分割し、全体では１０００グループの構成の場合を示す。又ポインタ（アドレス）７６４３に対応したデータを同一の値の７６４３とし、検索データ７６４３を用いて検索する場合を示す。
【００３７】
なお、図６及び図７に於いては、ポインタをアドレスとして表示し、且つアドレス値とデータとを同一の値とした場合を示す。又各階層に於いて、何れのグループに属するかを判定する場合、グループの境界のアドレスを用いてデータを読出し、読出したデータと検索データとを比較するものであるから、１０グループの何れに属するかを判定する場合、例えば、図５に於ける参照・比較部は１０個ではなく、９個で済むことになる。即ち、１０個の中の１個を未使用とすることができる。図６及び図７に於ける未使用は、この未使用の参照・比較部に対応するものである。
【００３８】
先ず、パラメータ（アドレス）初期化により（Ｂ１）、階層１の１０個のグループの２番目のグループから１０番目のグループまでのそれぞれの先頭アドレス１０００，２０００，・・・９０００を設定して、データベースからデータを読出して、検索データ７６４３と比較し（Ｂ２）、その比較結果を判定部に於いて判定する（Ｂ３）。この場合、参照・比較結果により、アドレス７００１〜８０００に含まれると判定することができる。即ち、判定部は、階層１の７番目のグループに属すると判定する。
【００３９】
この判定部による判定結果に応じて、パラメータ（アドレス）作成（Ｂ４）として、階層１の７番目のグループについて、階層２の１０個のグループの２番目から１０番目のグループの先頭アドレス７１００，７２００，・・・７９００を設定して、データベースからデータを読出し、検索データと比較する（Ｂ５）。この場合、アドレス７６０１〜７７００に含まれると判定することになる。即ち、判定部は、階層２の７番目のグループに属すると判定する（Ｂ６）。
【００４０】
この判定部による判定結果に応じて、パラメータ（アドレス）作成（Ｂ７）として、階層２の７番目のグループについて、階層３の１０個のグループの２番目から１０番目の先頭アドレス７６１０，７６２０，・・・７６９０を設定して  データベースからデータを読出し、検索データと比較する（Ｂ８）。この場合、判定部は、アドレス７６４１〜７６５０に含まれると判定することになる。即ち、判定部は、階層３の４番目のグループに属すると判定する（Ｂ９）。
【００４１】
この判定部による判定結果に応じて、パラメータ（アドレス）作成（Ｂ１０）として、階層３の４番目のグループに対するアドレス７６４１〜７６５０を設定してデータベースからデータを読出し、検索データ７６４３と比較し（Ｂ１１）、階層３の４番目のグループのアドレス７６４３によるデータ７６４３と、検索データとが比較一致したと判定部は判定する（Ｂ１２）。
【００４２】
前述の場合、アドレス設定は４回、参照・比較は４回、判定は４回であり、参照・比較に３サイクルを要し、他のは１サイクルを要するとすると、合計で、４＋４＋４×３＝２０（サイクル）となる。従って、従来の例えば図１５を参照して説明した２分探索法を適用した場合には、前述のように、５２サイクルを要したものが、本発明の実施の形態によれば、２０サイクルで済み、約６２％の検索処理時間の短縮を図ることができる。
【００４３】
図８は、ポインタをジャンプして設定する場合の機能ブロック図を示し、初期値（入力値）３１として検索データを入力し、参照部３２は、ポインタに従ってデータを読出し、比較部（判定部）３３に於いて読出したデータと検索データとを比較判定する。その判定結果に応じて、差分によるパラメータ（ポインタ）の重み生成部３４に於いて、検索値と参照値の差分に対する閾値３５に従って、ポインタがジャンプするように重み付けを行う。
【００４４】
例えば、図２に示すデータベースと同様に階層構成としたデータベースを図９に示し、階層１を１０グループに分割し、階層２を３グループに分割し、階層１のグループＡの先頭のポインタ１、グループＢの先頭のポインタ１１、・・・グループＨの先頭のポインタ８１、グループＪの先頭のポインタ９１とし、検索データ１０８０を入力値とし、検索値と参照値との差分に対する閾値３５を、例えば、３９０とすると、図２及び図３を参照して説明したように、先ず、ポインタ１１を設定してデータを読出す。この時のデータが２１０で、検索データとの差分は、１０８０＞２１０、且つ、１０８０−２１０＝８７０＞２１０となるから、次のポインタをジャンプさせる。このジャンプ先は、例えば、１０グループの場合に、後半の５グループの先頭のポインタとすることができる。
【００４５】
差分によるパラメータ（ポインタ）の重み作成部３４は、読出したデータと検索データとの差分が閾値以上であるから、次のグループの先頭のポインタではなく、例えば、１０グループの後半の５グループの先頭のポインタにジャンプさせる重み付けを行う。それにより、次のポインタは６１となり、このポインタ６１により読出したデータが７１０であると、１０８０＞７１０、且つ、１０８０−７１０＝３７０＜３９０であるから、ポインタのジャンプは行わないで、次のグループの先頭を示すポインタとする。以下同様にして、グループＪの中のポインタ９８のデータ１０８０を読出した時に、検索データ１０８０と比較一致することにより目的のデータを検索することができる。この場合、図２及び図３に示す場合に比較して検索処理時間を短縮することができる。
【００４６】
図１０はデータをランダム的に配列して格納しデータベースの説明図であり、ポインタ１〜４０により示す領域に、大小不順でデータが格納されている場合、検索データにより検索する為には、先頭のポインタ１から順に検索する必要がある。そこで、データを昇順又は降順に配列し直し、ポインタの付け替えを行う。その結果を図１１に示し、且つ１０個のデータ数毎にグループに分割し、図２について説明したように、グループ２，３，・・・の先頭のポインタを順次設定して、又は図６及び図７に示すように、同一階層の全グループの先頭のポインタを設定して検索し、検索データが何れのグループに属するかを判定し、検索データが属するグループ内を順次検索することにより、例えば、検索データ４６３２について、ランダム配列の場合に比較して約半分の検索処理ステップで済むことになる。
【００４７】
本発明は、前述の各実施の形態にのみ限定されるものではなく、種々付加変更することも可能であり、又検索プログラムは、磁気記録媒体や光記録媒体等の記録媒体に記録して、データベースの検索時にロードすることも可能である。この場合、データペースに格納されたデータ数Ｙを入力することが必要となる。又階層数Ｎや、グループ数Ｘを制限するように設定することも可能である。
【００４８】
【発明の効果】
以上説明したように、本発明は、データベースに昇順又は降順に格納したデータの総数をＹ、複数のグループに分割した時のグループ内のデータ数をＸ、単一又は複数の階層をＮとした時に、Ｘ＝Ｙ１／ｎ  ＞２（但し、ｎ＝２Ｎ  ）の条件を満足するように、階層毎に複数のグループに分割し、検索データと上位の階層のグループのそれぞれの先頭ポインタに従って読出したデータと比較して、検索データが属するグループを判定し、この検索データが属するグループ内の下位の階層のグループのそれぞれ先頭ポインタに従って読出したデータと検索データとを比較して、検索データが属する下位の階層のグループを判定し、最下位の階層のグループ内のポインタに従って読出したデータと検索データとを比較する過程を含むものであり、データの総数Ｙが多い程、従来の２分探索法等に比較して、検索ステップ数の削減が可能となり、短時間で所望のデータを検索することができる利点がある。
【図面の簡単な説明】
【図１】データベースの階層構成の説明図である。
【図２】階層構成及び検索方法の説明図である。
【図３】検索処理の機能ブロック図である。
【図４】本発明の実施の形態のフローチャートである。
【図５】検索処理の機能ブロック図である。
【図６】本発明の実施の形態の並列処理によるフローチャートである。
【図７】本発明の実施の形態の並列処理によるフローチャートである。
【図８】検索処理の機能ブロック図である。
【図９】ポインタのジャンプ処理の説明図である。
【図１０】ランダム的配列のデータベースの説明図である。
【図１１】昇順に配列したデータベースの説明図である。
【図１２】従来の検索方法のフローチャートである。
【図１３】従来の２分検索法のフローチャートである。
【図１４】２分検索法を順次繰り返す従来のフローチャートである。
【図１５】２分検索法を順次繰り返す従来のフローチャートである。
【符号の説明】
１  データベース
１ｋ  階層１のグループ
２ｋ  階層２のグループ
３ｋ  階層３のグループ
【図１】
2004287689.tif 000004
【図２】
2004287689.tif 000005
【図３】
2004287689.tif 000006
【図４】
2004287689.tif 000007
【図５】
2004287689.tif 000008
【図６】
2004287689.tif 000009
【図７】
2004287689.tif 000010
【図８】
2004287689.tif 000011
【図９】
2004287689.tif 000012
【図１０】
2004287689.tif 000013
【図１１】
2004287689.tif 000014
【図１２】
2004287689.tif 000015
【図１３】
2004287689.tif 000016
【図１４】
2004287689.tif 000017
【図１５】
2004287689.tif 000018