(57)【要約】【課題】線形リストを用いた共有メモリテーブルキューの検索にあたり、データ量の増大に伴う検索速度のばらつき及び低下を防止する。【解決手段】線形リストを用いた共有メモリテーブルキューの検索処理装置１０であって、データを記憶するデータ管理部１１ｂと、データの各グループにおける先頭データのオフセット、先頭データのキー値及びデータ数を有するグループ管理情報を記憶するグループ管理部１１ｃと、検索を実行する検索処理部１２とを有し、検索処理部１２が、データの検索にあたり、先頭データのキー値と、検索対象データのキー値にもとづいて、この検索対象データを有するグループを決定し、その後、当該グループ内を検索して、検索対象データを取得する検索処理装置。【選択図】　　　図１
2004078536.tif 000002
【特許請求の範囲】
【請求項１】
検索処理装置による線形リストを用いた共有メモリテーブルキューの検索処理方法であって、
前記検索処理装置が、
複数のデータを複数のグループに分けて管理し、
前記データの検索にあたり、検索対象データを有するグループを決定し、その後、当該グループ内を検索して、前記検索対象データを取得する
ことを特徴とする検索処理方法。
【請求項２】
前記検索処理装置が、
前記グループ内のデータを、さらに１又は２以上のグループに分けて管理し、
前記データの検索にあたり、前記検索対象データを有するグループを決定し、当該グループ内にさらにグループがある場合には、これらのグループから前記検索対象データを有するグループを決定し、このグループの決定を、決定されたグループ内に他のグループが存在しなくなるまで繰り返した後、最後に決定されたグループ内を検索して、前記検索対象データを取得する
ことを特徴とする請求項１記載の検索処理方法。
【請求項３】
前記データの検索にあたり、前記検索対象データを有するグループを、このグループの先頭データの識別キーと、前記検索対象データの識別キーにもとづいて決定する
ことを特徴とする請求項１又は２記載の検索処理方法。
【請求項４】
前記データの検索にあたり、前記検索対象データを有するグループを、このグループを識別する識別キーと、前記検索対象データの識別キーにもとづいて決定する
ことを特徴とする請求項１又は２記載の検索処理方法。
【請求項５】
線形リストを用いた共有メモリテーブルキューの検索処理装置であって、
データを記憶するデータ管理部と、
前記データの各グループにおける先頭データのオフセット、先頭データのキー値及びデータ数を有するグループ管理情報を記憶するグループ管理部と、
検索を実行する検索処理部とを有し、
前記検索処理部が、
前記データの検索にあたり、前記先頭データのキー値と、検索対象データのキー値にもとづいて、この検索対象データを有するグループを決定し、その後、当該グループ内を検索して、前記検索対象データを取得する
ことを特徴とする検索処理装置。
【請求項６】
前記グループ管理部が、前記グループ内に、さらにグループを有するとともに、これらのグループについての先頭データのオフセット、先頭データのキー値及びデータ数を記憶し、
前記検索処理部が、
前記データの検索にあたり、検索対象データを有するグループを決定し、当該グループ内にさらにグループがある場合には、これらのグループについての先頭データのキー値と、前記検索対象データのキー値にもとづいて、前記検索対象データを有するグループを決定し、このグループの決定を、決定されたグループ内に他のグループが存在しなくなるまで繰り返した後、最後に決定されたグループ内を検索して、前記検索対象データを取得する
ことを特徴とする請求項５記載の検索処理装置。
【請求項７】
検索処理装置に、線形リストを用いた共有メモリテーブルキューに対する検索を行わせる検索処理プログラムであって、
前記検索処理装置に、
それぞれにキー値が設定された複数のデータを、複数のグループに分けて管理させ、
前記データの検索にあたり、検索対象データを有するグループを、このグループの先頭データのキー値、又はこのグループを識別するキー値と、前記検索対象データのキー値にもとづいて決定させ、その後、当該グループ内を検索させて、前記検索対象データを取得させる
ことを実行させるための検索処理プログラム。
【請求項８】
前記検索処理装置に、
前記データの検索にあたり、前記検索対象データを有するグループを決定させ、当該グループ内にさらにグループがある場合には、これらのグループについての先頭データのキー値、又はこのグループを識別するキー値と、前記検索対象データのキー値にもとづいて、前記検索対象データを有するグループを決定させ、このグループの決定を、決定されたグループ内に他のグループが存在しなくなるまで繰り返させた後、最後に決定されたグループ内を検索させて、前記検索対象データを取得させる
ことを実行させるための請求項７記載の検索処理プログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、線形リストを用いた共有メモリテーブルキューの検索処理方法、検索処理装置及び検索処理プログラムに関する。
【０００２】
【従来の技術】
従来、線形リストを用いた共有メモリテーブルキューを検索するにあたっては、テーブルキューの先頭から順次シーケンシャルに読み込む処理が行われていた。
しかしながら、このような検索方法によれば、データ数が増大することに伴って、対象となるデータの格納位置によっては、テーブルキューのアクセス回数が増大し、その結果、検索速度の低下を引き起こすという問題があった。
また、データの格納位置による検索速度のばらつきが発生するという問題もあった。
【０００３】
検索処理を短縮することを目的とする発明としては、例えば、特開平４−１４０８２５号公報に開示のものを挙げることができる。
この発明は、光ディスク装置のアクセス速度を向上させるものであり、多数のレコードを有する順編成ファイルの検索にあたり、レコード番号管理テーブルを磁気ディスク装置に保有させ、これを用いて検索速度の向上を図るものである。
すなわち、同発明によれば、上記順編成ファイルにおけるレコードのうち、特定のキー情報に対応するレコード番号を磁気ディスク装置にて管理し、そのキー情報にもとづく検索にあたり、レコード番号を用いることによって、光ディスク装置における対象データを直接アクセスすることによって、アクセス時間を短縮するものであった。
【０００４】
【発明が解決しようとする課題】
しかしながら、このような従来の検索方法は、作成された順編成ファイルにもとづいて、レコード番号管理テーブルを作成する必要のあるものであった。
また、特定のキー情報に対しては、直接対象レコードにアクセスすることが可能であるが、レコード番号管理テーブルに登録されていないキー情報については、従来通り先頭データからアクセスする必要のあるものであった。
このため、レコード番号管理テーブルに登録されていないレコードについては、検索速度の向上が図れないという問題があった。
【０００５】
また、全てのレコードの検索速度を向上させるために、レコード番号管理テーブルに全てのレコードを登録すれば、このレコード番号管理テーブルからレコード番号を検索すること自体に時間がかかり、全体としての処理速度の向上が図れないという問題があった。
さらに、この従来の検索方法は、光ディスク装置における順編成ファイルに対するものであり、上述した線形リストを用いた共有メモリテーブルキューの検索に関する従来の課題を解決できるものではなかった。
【０００６】
本発明は、上記の事情にかんがみなされたものであり、線形リスト型で管理されている共有メモリテーブルキューの中から、対象となるデータを検索する際のアクセス回数を、任意のグループに分割して検索することにより減少させるとともに、データの格納位置に影響されることなく平均化させることを可能とする検索処理方法、検索処理装置及び検索処理プログラムの提供を目的とする。
【０００７】
【課題を解決するための手段】
上記目的を達成するため、本発明の請求項１記載の検索処理方法は、検索処理装置による線形リストを用いた共有メモリテーブルキューの検索処理方法であって、検索処理装置が、複数のデータを複数のグループに分けて管理し、データの検索にあたり、検索対象データを有するグループを決定し、その後、当該グループ内を検索して、検索対象データを取得する方法としてある。
【０００８】
検索処理方法をこのような方法にすれば、データの検索要求に対して、線形リスト型で管理されている全てのデータを検索する必要がない。
すなわち、まず、そのデータがどのグループに所属するかを求め、その後求められたグループ内でシーケンシャル読みを行うという２段階の検索手法を用いることにより、平均アクセス回数を減少させることが可能となる。
また、データの格納位置による検索速度の低下を軽微なものとすることができるとともに、データ数が増大しても、これによる検索速度の低下をも軽微なものとすることが可能となる。
【０００９】
これによって、例えば、要求されたデータが線形リストの最後に格納されている様な場合は、従来からのシーケンシャル読みでは全データ数分のアクセス回数が必要となるが、本発明の場合は、全グループ数＋最終グループ内の格納データ数分で済み、検索処理の高速化を図ることが可能となる。
【００１０】
本発明の請求項２記載の検索処理方法は、検索処理装置が、グループ内のデータを、さらに１又は２以上のグループに分けて管理し、データの検索にあたり、検索対象データを有するグループを決定し、当該グループ内にさらにグループがある場合には、これらのグループから検索対象データを有するグループを決定し、このグループの決定を、決定されたグループ内に他のグループが存在しなくなるまで繰り返した後、最後に決定されたグループ内を検索して、検索対象データを取得する方法としてある。
【００１１】
検索処理方法をこのような方法にすれば、データ量が極めて大きくなったような場合であっても、多段階の検索方法により検索処理速度の低減を最小限に抑えることが可能となる。
すなわち、データ量が極めて大きくなると、２段階による検索を行っても、検索対象データが所属するグループの決定、又は、そのグループ内における検索に時間がかかるようになる。
このため、データ量に応じて、グループ内のデータをさらに複数のグループに分けて管理する多段階の検索手法を用いることにより、検索対象データへのアクセス回数を減少させることが可能となる。
【００１２】
本発明の請求項３記載の検索処理方法は、データの検索にあたり、検索対象データを有するグループを、このグループの先頭データの識別キーと、検索対象データの識別キーにもとづいて決定する方法としてある。
【００１３】
検索処理方法をこのような方法にすれば、検索対象データを有するグループの決定にあたり、このグループの先頭データの識別キーと、検索対象データの識別キーのそれぞれに含まれるグループを識別する部分にもとづいて、その決定を行うことが可能となる。
【００１４】
本発明の請求項４記載の検索処理方法は、データの検索にあたり、検索対象データを有するグループを、このグループを識別する識別キーと、検索対象データの識別キーにもとづいて決定する方法としてある。
【００１５】
検索処理方法をこのような方法にすれば、検索対象データを有するグループの決定にあたり、このグループを識別するためキーと、検索対象データの識別キーに含まれるグループを識別する部分にもとづいて、その決定を行うことが可能となる。
【００１６】
本発明の請求項５記載の検索処理装置は、線形リストを用いた共有メモリテーブルキューの検索処理装置であって、データを記憶するデータ管理部と、データの各グループにおける先頭データのオフセット、先頭データのキー値及びデータ数を有するグループ管理情報を記憶するグループ管理部と、検索を実行する検索処理部とを有し、検索処理部が、データの検索にあたり、先頭データのキー値と、検索対象データのキー値にもとづいて、この検索対象データを有するグループを決定し、その後、当該グループ内を検索して、検索対象データを取得する構成としてある。
【００１７】
検索処理装置をこのような構成にすれば、線形リスト型で管理されている共有メモリにおけるテーブルキューのデータを、２段階による検索を行うことによって、その検索速度を向上させることが可能となる。
すなわち、検索処理装置に、データのグループ管理情報を記憶するグループ管理部をもたせ、そのグループ管理情報の先頭データのキー値にもとづいて、検索対象データのグループを決定し、そのグループ内をシーケンシャル検索することによって、検索のためアクセス回数を減少させることが可能となる。
【００１８】
本発明の請求項６記載の検索処理装置は、グループ管理部が、グループ内に、さらにグループを有するとともに、これらのグループについての先頭データのオフセット、先頭データのキー値及びデータ数を記憶し、検索処理部が、データの検索にあたり、検索対象データを有するグループを決定し、当該グループ内にさらにグループがある場合には、これらのグループについての先頭データのキー値と、検索対象データのキー値にもとづいて、検索対象データを有するグループを決定し、このグループの決定を、決定されたグループ内に他のグループが存在しなくなるまで繰り返した後、最後に決定されたグループ内を検索して、検索対象データを取得する構成としてある。
【００１９】
検索処理装置をこのような構成にすれば、そのグループ管理部におけるグループ管理情報内に、必要に応じて、さらに複数の段階のグループ管理情報を保有させることにより、データ検索速度を向上させることができる。
すなわち、あるグループ内にデータ数を多く保有させる場合は、そのグループをさらに複数のグループに分割することによって、このデータ数の多いグループ内の検索速度を向上させることが可能となる。
これによって、データ量が極めて大きい場合にも、高い検索速度を実現することができるとともに、データの管理の自由度も向上することとなる。
【００２０】
本発明の請求項７記載の検索処理プログラムは、検索処理装置に、線形リストを用いた共有メモリテーブルキューに対する検索を行わせる検索処理プログラムであって、検索処理装置に、それぞれにキー値が設定された複数のデータを、複数のグループに分けて管理させ、データの検索にあたり、検索対象データを有するグループを、このグループの先頭データのキー値、又はこのグループを識別するキー値と、検索対象データのキー値にもとづいて決定させ、その後、当該グループ内を検索させて、検索対象データを取得させる構成としてある。
【００２１】
検索処理プログラムをこのような構成にすれば、検索処理装置に、データの検索を任意のグループ単位で行わせることができるため、データの格納位置に対する検索アクセス回数の平均化を図ることができるとともに、データ量の増加に伴う検索速度の低減を防止することが可能となる。
【００２２】
本発明の請求項８記載の検索処理プログラムは、検索処理装置に、データの検索にあたり、検索対象データを有するグループを決定させ、当該グループ内にさらにグループがある場合には、これらのグループについての先頭データのキー値、又はこのグループを識別するキー値と、検索対象データのキー値にもとづいて、検索対象データを有するグループを決定させ、このグループの決定を、決定されたグループ内に他のグループが存在しなくなるまで繰り返させた後、最後に決定されたグループ内を検索させて、検索対象データを取得させる構成としてある。
【００２３】
検索処理プログラムをこのような構成にすれば、データ量が極めて大きいような場合でも、検索処理装置に最小限のアクセス回数で、検索を実行させることが可能となる。
【００２４】
【発明の実施の形態】
以下、本発明の実施形態につき、図面を参照して説明する。
［第一実施形態］
まず、本発明の第一実施形態について、図１を参照して説明する。図１は、本発明の第一実施形態の検索処理装置の構成を示すブロック図である。
同図に示すように、本実施形態の検索処理装置１０は、共有メモリ１１及び検索処理部１２を有している。
共有メモリ１１は、共有データを格納するための記憶装置であり、共通管理部１１ａ、データ管理部１１ｂ及びグループ管理部１１ｃを有している。
【００２５】
共通管理部１１ａは、データ管理部のアドレス１１ａ−１、空きテーブルキューの先頭オフセット（ｏｆｆｓｅｔ）１１ａ−２、使用中テーブルキューの先頭オフセット１１ａ−３及びグループ管理部のアドレス１１ａ−４をそれぞれ管理している。
データ管理部のアドレス１１ａ−１は、データ管理部１１ｂのはじまりのアドレスを示すものである。
【００２６】
空きテーブルキューの先頭オフセット１１ａ−２は、データ管理部１１ｂのテーブルキューにおける空きテーブルキューの先頭の位置を示すものである。
ここで、オフセットとは、そのデータのロケーションカウンタである。
使用中テーブルキューの先頭オフセット１１ａ−３は、データ管理部１１ｂのテーブルキューにおける使用中テーブルキューの先頭の位置を示すものである。
グループ管理部のアドレス１１ａ−４は、グループ管理部１１ｃのはじまりのアドレスを示すものである。
【００２７】
データ管理部１１ｂは、データを線形リスト型にて格納する記憶部である。このデータ管理部１１ｂに格納されているそれぞれのデータは、そのデータのオフセットと、次のデータのオフセット、及びそのデータのキー値を備えている。
例えば、図１のデータ管理部１１ｂの第２行左端のデータは、そのデータのオフセットとして「１６」を、次のデータのオフセットとして「３２」を、そのデータのキー値として「ＡＡＡ」を有している。
また、各データの本体は図示されていないが、同図における当該データの左下の空白に格納されていると考えることができる。
なお、キー値とは、データを識別するためのキー（識別キー）であり、各データを識別することのできるものであれば、特に限定されない。これは以下におけるキー値についても同様である。
【００２８】
グループ管理部１１ｃは、データ管理部１１ｂにおけるデータを複数のグループに分割した、それぞれのグループの管理情報を記憶している。
それぞれのグループの管理情報には、先頭データのオフセット、先頭データのキー値、及びデータ数が含まれている。
【００２９】
例えば、図１におけるグループ１の管理情報は、先頭データのオフセットとして１６、先頭データのキー値としてＡＡＡ、データ数として８が設定されており、これはグループ１が、図中のデータ管理部１１ｂの中央の行の８データであることを示している。
そして、グループ２の管理情報は、先頭データのオフセットが４０８、先頭データのキー値がＢＢＢであり、グループ２が、図中のデータ管理部１１ｂの再下段の行の先頭データからはじまることがわかる。同様にして、グループ３は、再下段の先頭データのオフセット４４８のデータからはじまることがわかる。
このように、データ管理部１１ｂにおけるデータを、任意のグループ単位で管理することができるため、データの検索にあたり、まず、検索対象データが、どのグループに所属しているのかを検索した後に、そのグループ内において、シーケンシャル検索を行うことができ、検索効率を向上させることが可能となる。
【００３０】
なお、図１においては、各キー値は３文字で構成され、第１文字目がグループを識別している。
グループ管理部１１ｃの各グループ管理情報は、先頭データのキー値を有しているが、本実施形態においては、各グループがキー値の第一文字によって識別されているため、グループを識別するためのキー値として、この文字分のみ、例えば、「Ａ」をグループ管理情報にもたせて、グループを識別するようにすることもできる。
このキー値及びグループを識別するための文字数は、任意に設定することが可能である。
【００３１】
さらに、本実施形態において、キー値にグループを識別するための情報を保有させることなく検索を行わせるようにすることも可能である。
その方法としては、例えば、検索要求時に、検索処理部１２に対して検索対象データのキー値とともに、その検索対象データの所属するグループの先頭データのキー値を併せて入力し、これにもとづきグループを決定後、そのグループ内をシーケンシャル検索する方法を挙げることができる。
【００３２】
また、各グループに所属するデータのキー値とそのグループの先頭データのキー値とを対応させたテーブルを、検索処理装置１０に保有させ、このテーブルを参照することによって、検索対象データのキー値にもとづいて、その検索対象データが含まれるグループの先頭データのキー値を取得するようにすることができる。
これによって、上記の方法と同様に、そのグループの先頭データの位置からそのグループ内をシーケンシャル検索することによって、検索対象データを取得することができる。
ただし、これらのようにした場合は、余分な入力や検索が発生することから、図１の例のように、各キー値には、グループを識別するための情報を保有させることが好ましい。
検索処理部１２は、上記検索を実行するＣＰＵを示すものである。
【００３３】
次に、本実施形態の検索処理装置における処理手順について、図１及び図２を参照して説明する。
図２は、本実施形態の検索処理装置における検索処理手順を示すフローチャートである。
【００３４】
まず、キー値が「ＢＢＣ」のデータの検索要求があったとする（ステップ１０）。
検索処理部１２は、上記キー値にもとづいて、グループ管理部１１ｃの各グループの管理情報における先頭データのキー値を検索し、検索対象データが、どのグループに所属しているかを決定する（ステップ１１）。
この場合、検索対象データのキー値が、「ＢＢＣ」であり、各グループがキー値の第１文字目によって識別されているため、先頭データのキー値として「ＢＢＢ」を有するグループ２が、検索対象データの所属グループとして決定される。
【００３５】
次に、検索処理部１２は、グループ２の線形リストを先頭データのオフセット４０８からシーケンシャル検索し、キー値として「ＢＢＣ」を有するデータ１６ｂ−１を取得する（ステップ１２）。
したがって、キー値「ＢＢＣ」を有する検索対象データを検索するために、必要となるアクセス回数は、所属グループを求めるための２回と、グループ内で２番目に格納されているデータを求めるための２回の、合計４回となる。
単純に従来のシーケンシャル検索を行った場合、キー値「ＢＢＣ」を有する検索対象データは、線形リストの１０番目に格納されているため、合計１０回のアクセスが必要となる。
このことから、本実施形態により、データ検索におけるアクセス回数が、従来と比較して低減されていることがわかる。
【００３６】
次に、図３を用いて、本実施形態に示す２段階の検索方式により、データの格納位置による検索速度のばらつきが低減されること、及びデータが増加してもアクセス回数の増加が抑えられることを説明する。
図３は、本実施形態の検索処理装置におけるグループ検索処理と、従来の検索処理装置におけるシーケンシャル検索処理との平均アクセス回数及びその増加率の比較を示す図である。
【００３７】
同図は、それぞれ８つのデータを有するグループ１〜５における各データの検索に必要なアクセス回数を示す図である。
また、それぞれのデータの上段に、従来のシーケンシャル検索を用いた場合のアクセス回数を示しており、下段に、本実施形態の２段階グループ検索によるアクセス回数を示している。
「平均アクセス回数」は、それぞれのグループの最終データまでの各データを検索するために必要なアクセス数の平均値を算出したものである。
「グループ１に対する平均アクセス回数増加率」は、上記各グループの平均アクセス回数が、グループ１における平均アクセス回数に対して、どの程度増加しているかを示すものである。
【００３８】
図３の「平均アクセス回数」を参照すると、従来のシーケンシャル検索の場合は、グループ１〜５の順に、４．５→８．５→１２．５→１６．５→２０．５となっており、データの格納位置によって検索速度が急激に大きくことなることがわかる。
しかしながら、本実施形態の２段階グループ検索の場合は、順に、５．５→６．０→６．５→７．０→７．５となっており、データの格納位置による検索速度の増加が低減されていることがわかる。
【００３９】
さらに、同図の「グループ１に対する平均アクセス回数増加率」を参照すると、従来のシーケンシャル検索の場合は、グループ２〜５の順に、１．９→２．８→３．７→４．６となっており、データ量の増加に伴って、アクセス回数が大きく増大しており、検索速度が著しく低下することがわかる。
一方、本実施形態の２段階グループ検索の場合は、順に、１．１→１．２→１．３→１．４となっており、データ量の増加に伴う検索速度の低下を軽微にすることが可能となっている。
【００４０】
以上説明したように、本実施形態の検索処理装置によれば、線形リストを用いた共有メモリテーブルキューの検索において、データを任意のグループに分割して検索することができるため、検索対象データの格納位置に影響されることなく、検索速度を平均化することができるとともに、データ量が増加しても検索速度の増加を抑えることが可能となる。
【００４１】
［第二実施形態］
次に、本発明の第二実施形態について、図４及び図５を参照して説明する。図４は、本実施形態の検索処理装置における多段階グループの例を示す図であり、図５は、同装置における検索処理手順を示すフローチャートである。
【００４２】
本実施形態は、グループ内にさらにグループ（サブグループ）が存在する点で第一実施形態と異なる。
すなわち、本実施形態は、例えば、図４に示すように各グループをさらに複数のサブグループに分割して構成する場合を想定している。
それ以外の点については、第一実施形態と同様であり、本実施形態のブロック図も、図１のグループ管理部１１ｃにおける各グループ管理情報に、さらにそのグループ内におけるグループについての管理情報を、同様にしてもたせることを想定し、その他の構成については、同様のものを用いることができる。
【００４３】
まず、図４を参照して、本実施形態のデータ構成について説明する。
同図には、グループ１〜３のグループが示されており、それぞれのグループが、２６個のサブグループを有している。また、各サブグループは、それぞれ２６個のデータを有している。
【００４４】
次に、図５を参照して、本実施形態の検索処理手順について説明する。
まず、検索処理部１２が、キー値「ＣＺＺ」である検索対象データの検索要求を受ける（ステップ２０）。
これに対して、検索処理部１２は、検索対象データが所属するグループの決定を行う（ステップ２１）。
【００４５】
図４に示すように、本実施形態のデータ構造は、キー値の第１文字目がグループを識別し、第２文字目がサブグループを識別している。
このため、検索対象データのキー値が、「ＣＺＺ」であることから、グループとして、グループ３が決定される。
次に、このグループ３内において、さらにサブグループの決定が行われる（ステップ２２）。
【００４６】
この場合、検索対象データのキー値が、「ＣＺＺ」であることから、サブグループ３２６が決定され、さらにそのサブグループ内において、シーケンシャル検索が行われ、そのサブグループ内の２６番目のデータである検索対象データが取得される（ステップ２３）。
【００４７】
ここで、同一の検索を従来のシーケンシャル検索によって行った場合のアクセス回数を計算すると、キー値「ＣＺＺ」を有する検索対象データは、２０２８番目のデータであるため、これを検索するためには、２０２８回のアクセスを必要とする。
また、第一実施形態における２段階グループ検索を行ったとすると、グループ３を決定するために３回、グループ３内で検索対象データまでシーケンシャル検索を行うために、６７６回のアクセスを必要とするため、合計６７９回のアクセスを必要とする。
【００４８】
これに対して、本実施形態における３段階グループ検索によれば、グループ３を決定するために３回、サブグループ３２６を決定するまでに２６回、サブグループ３２６をシーケンシャル検索して検索対象データを取得するまでに２６回の合計５５回のアクセス回数で済むこととなり、大幅に検索速度が向上することがわかる。
【００４９】
すなわち、第一実施形態のような２段階検索を用いた場合であっても、データ量が増加すると、グループの決定や、あるいは、グループ内のシーケンシャル検索のためのアクセス回数が増加することとなり、その結果、検索処理速度が低下する。
したがって、このような場合には、グループ内のデータをさらにグループに分割して検索を行うことによって、データ量の増加に伴う検索処理速度の低減を最小限に抑えることが可能となる。
また、必要に応じて、同様にしてさらに４段階、５段階等の多段階検索方式をとるようにすることも好ましい。
【００５０】
以上説明したように、本実施形態の検索処理装置によれば、データ量に応じて、データを複数の階層にグループ化することにより、さらに検索処理速度の低減を効果的に防止することが可能となる。
【００５１】
上記の実施形態におけるグループの決定や、グループ内における検索対象データの取得等は、検索処理プログラムにより実行される。
この検索処理プログラムは、コンピュータの各構成要素に指令を送り、所定の処理、例えば、グループの決定処理や、グループ内における検索対象データの取得処理等を行わせる。
これによって、これらの処理は、検索処理プログラムとコンピュータとが協働した検索処理装置により実現される。
【００５２】
なお、検索処理プログラムは、コンピュータのＲＯＭやハードディスクに記憶させる他、コンピュータ読み取り可能な記憶媒体、たとえば、外部記憶装置及び可搬記憶媒体等に格納することができる。
外部記憶装置とは、磁気ディスク等の記憶媒体を内蔵し、例えば検索処理装置などに外部接続される記憶増設装置をいう。一方、可搬記憶媒体とは、記憶媒体駆動装置（ドライブ装置）に装着でき、かつ、持ち運び可能な記憶媒体であって、たとえば、ＣＤ−ＲＯＭ、フレキシブルディスク、メモリカード、光磁気ディスク等をいう。
【００５３】
そして、記憶媒体に記憶されたプログラムは、コンピュータのＲＡＭにロードされて、ＣＰＵにより実行される。この実行により、上述した各実施形態の検索処理装置の機能が実現される。
さらに、コンピュータで検索処理プログラムをロードする場合、他のコンピュータで保有された検索処理プログラムを、通信回線を利用して自己の有するＲＡＭや外部記憶装置にダウンロードすることもできる。
このダウンロードされた検索処理プログラムも、ＣＰＵにより実行され、上記実施形態のグループの決定処理や、グループ内における検索対象データの取得処理等を実現する。
【００５４】
なお、本発明は以上の実施形態に限定されるものではなく、本発明の範囲内において、種々の変更実施が可能であることは言うまでもない。
例えば、共通管理部１１ａにおける空きテーブルキューの先頭オフセットや使用中テーブルキューの先頭オフセットをそれぞれ複数もたせるようにして、より柔軟で汎用性、拡張性の高い利用を可能とするなど適宜設計変更できるものである。
【００５５】
【発明の効果】
以上のように、本発明によれば、線形リストを用いた共有メモリテーブルキューの検索において、データを任意のグループに分割して検索することができる。
このため、検索対象データの格納位置に影響されることなく、検索速度を平均化し、検索速度のばらつきを低減することができるとともに、データ量が増加しても検索速度の増加を抑えることが可能となる。
また、データ量に応じて、データを複数の階層にグループ化することにより、さらに検索処理速度の低減を効果的に防止することも可能となる。
【００５６】
さらに、検索処理プログラムは、コンピュータの各構成要素へ所定の指令を送ることにより、このグループの決定機能や、グループ内における検索対象データの取得機能等を実現させることができる。
これによって、これらの機能等は、検索処理プログラムとコンピュータとが協働した検索処理装置により実現可能である。
【図面の簡単な説明】
【図１】本発明の第一実施形態の検索処理装置の構成を示すブロック図である。
【図２】本発明の第一実施形態の検索処理装置における検索処理手順を示すフローチャートである。
【図３】本発明の第一実施形態の検索処理装置におけるグループ検索処理と、従来の検索処理装置におけるシーケンシャル検索処理との平均アクセス回数及びその増加率の比較を示す図である。
【図４】本発明の第二実施形態の検索処理装置における多段階グループの例を示す図である。
【図５】本発明の第二実施形態の検索処理装置における検索処理手順を示すフローチャートである。
【符号の説明】
１０　検索処理装置
１１　共有メモリ
１１ａ　共通管理部
１１ａ−１　データ管理部のアドレス
１１ａ−２　空きテーブルキューの先頭オフセット
１１ａ−３　使用中テーブルキューの先頭オフセット
１１ａ−４　グループ管理部のアドレス
１１ｂ　データ管理部
１１ｂ−１　第一実施形態における検索対象データ
１１ｃ　グループ管理部
１２　検索処理部
【図１】
2004078536.tif 000003
【図２】
2004078536.tif 000004
【図３】
2004078536.tif 000005
【図４】
2004078536.tif 000006
【図５】
2004078536.tif 000007