(57)【要約】【課題】検索対象キー列に含まれている同一キー値を有する検索キーの数にかかわらず、検索対象キー値を有する検索キーの内の、先頭の検索キーを高速に検索する。【解決手段】利用者によって、検索対象キー値を含む検索指示が入力されると、先ず、キー検索部ＳＫが、配列型インデックスＡから、上記検索対象キー値を有する検索キーを二分検索法によって検索する。その後、境界検索部１１が、重複度決定部Ｄで算出された重複度と、線形検索法と二分検索法の平均コストの比に応じて決まる閾値とに基づいて、線形検索法または二分検索法の内の一方を選択する。その際、重複度が閾値未満の場合は、線形検索法を選択し、閾値以上の場合は、二分検索法を選択する。その後、選択した検索方法により、検索対象キー値を有する検索キーの内の、先頭の検索キーを検索する。【選択図】図１
2007249369.tif 000002
【特許請求の範囲】
【請求項１】
複数の検索キーが昇順または降順に並び、且つキー値が同一の検索キーを含んだ検索対象キー列の中から、指示された検索対象キー値を有し且つ前記検索対象キー値とは異なるキー値を有する検索キーとの境界となる検索キーを検索するキー検索装置であって、
前記検索対象キー列から、前記検索対象キー値を有する検索キーを二分検索法によって検索するキー検索部と、
前記検索対象キー列の検索キーの重複度と、線形検索法と二分検索法の平均コストの比とに基づいて、線形検索法または二分検索法の内の一方を選択し、該選択した検索方法により、前記キー検索部で検索された検索キーを検索開始キーにして、前記検索対象キー値を有し且つ前記検索対象キー値とは異なるキー値を有する検索キーとの境界となる検索キーを検索する境界検索部とを備えたことを特徴とするキー検索装置。
【請求項２】
請求項１記載のキー検索装置において、
前記境界検索部が、
前記キー検索部で検索された検索キーを検索開始キーにして、前記検索対象キー値を有し且つ前記検索対象キー値とは異なるキー値を有する検索キーとの境界となる検索キーを、線形検索法によって検索する第１の重複キー境界検索部と、
前記キー検索部で検索された検索キーを検索開始キーにして、前記検索対象キー値を有し且つ前記検索対象キー値とは異なるキー値を有する検索キーとの境界となる検索キーを、二分検索法によって検索する第２の重複キー境界検索部と、
前記検索対象キー列の検索キーの重複度と、線形検索法と二分検索法の平均コストの比とに基づいて、前記第１の重複キー境界検索部または前記第２の重複キー境界検索部を動作させる検索法決定部を備えたことを特徴とするキー検索装置。
【請求項３】
請求項１または２記載のキー検索装置において、
前記重複度が、同一キー値を有する検索キーのキー数が多くなるほど、大きな値となることを特徴とするキー検索装置。
【請求項４】
請求項３記載のキー検索装置において、
前記検索対象キー列中の各キー値毎に、そのキー値を有する検索キーのキー数が登録された重複度管理表と、
前記検索対象キー列に検索キーが追加された場合および前記検索対象キー列から検索キーが削除された場合、前記重複度管理表を更新し、更新後の前記重複度管理表の内容に基づいて、キー値毎のキー数の平均値を求め、該平均値を重複度とする重複度決定部とを備えたことを特徴とするキー検索装置。
【請求項５】
複数の検索キーが昇順または降順に並び、且つキー値が同一の検索キーを含んだ検索対象キー列の中から、指示された検索対象キー値を有し且つ前記検索対象キー値とは異なるキー値を有する検索キーとの境界となる検索キーを検索するキー検索方法であって、
前記検索対象キー列から、前記検索対象キー値を有する検索キーを二分検索法によって検索するキー検索ステップと、
前記検索対象キー列の検索キーの重複度と、線形検索法と二分検索法の平均コストの比とに基づいて、線形検索法または二分検索法の内の一方を選択し、該選択した検索方法により、前記キー検索部で検索された検索キーを検索開始キーにして、前記検索対象キー値を有し且つ前記検索対象キー値とは異なるキー値を有する検索キーとの境界となる検索キーを検索する境界検索ステップとを含むことを特徴とするキー検索方法。
【請求項６】
請求項５記載のキー検索方法において、
前記境界検索ステップが、
前記キー検索部で検索された検索キーを検索開始キーにして、前記検索対象キー値を有し且つ前記検索対象キー値とは異なるキー値を有する検索キーとの境界となる検索キーを、線形検索法によって検索する第１の重複キー境界検索ステップと、
前記キー検索部で検索された検索キーを検索開始キーにして、前記検索対象キー値を有し且つ前記検索対象キー値とは異なるキー値を有する検索キーとの境界となる検索キーを、二分検索法によって検索する第２の重複キー境界検索ステップと、
前記検索対象キー列の検索キーの重複度と、線形検索法と二分検索法の平均コストの比とに基づいて、前記第１の重複キー境界検索ステップまたは前記第２の重複キー境界検索ステップを起動させる検索法決定ステップとを含むことを特徴とするキー検索方法。
【請求項７】
請求項５または６記載のキー検索方法において、
前記重複度が、同一キー値を有する検索キーのキー数が多くなるほど、大きな値となることを特徴とするキー検索方法。
【請求項８】
請求項７記載のキー検索方法において、
前記検索対象キー列に検索キーが追加された場合および前記検索対象キー列から検索キーが削除された場合、前記検索対象キー列中の各キー値毎に、そのキー値を有する検索キーのキー数が登録された重複度管理表を更新し、更新後の前記重複度管理表の内容に基づいて、キー値毎のキー数の平均値を求め、該平均値を重複度とする重複度決定ステップを含むことを特徴とするキー検索方法。
【請求項９】
コンピュータを、複数の検索キーが昇順または降順に並び、且つキー値が同一の検索キーを含んだ検索対象キー列の中から、指示された検索対象キー値を有し且つ前記検索対象キー値とは異なるキー値を有する検索キーとの境界となる検索キーを検索するキー検索装置として機能させるためのプログラムであって、
前記コンピュータを、
前記検索対象キー列から、前記検索対象キー値を有する検索キーを二分検索法によって検索するキー検索部、
前記検索対象キー列の検索キーの重複度と、線形検索法と二分検索法の平均コストの比とに基づいて、線形検索法または二分検索法の内の一方を選択し、該選択した検索方法により、前記キー検索部で検索された検索キーを検索開始キーにして、前記検索対象キー値を有し且つ前記検索対象キー値とは異なるキー値を有する検索キーとの境界となる検索キーを検索する境界検索部として機能させるためのプログラム。
【請求項１０】
請求項９記載のプログラムにおいて、
前記境界検索部が、
前記キー検索部で検索された検索キーを検索開始キーにして、前記検索対象キー値を有し且つ前記検索対象キー値とは異なるキー値を有する検索キーとの境界となる検索キーを、線形検索法によって検索する第１の重複キー境界検索部と、
前記キー検索部で検索された検索キーを検索開始キーにして、前記検索対象キー値を有し且つ前記検索対象キー値とは異なるキー値を有する検索キーとの境界となる検索キーを、二分検索法によって検索する第２の重複キー境界検索部と、
前記検索対象キー列の検索キーの重複度と、線形検索法と二分検索法の平均コストの比とに基づいて、前記第１の重複キー境界検索部または前記第２の重複キー境界検索部を動作させる検索法決定部を備えたことを特徴とするプログラム。
【請求項１１】
請求項９または１０記載のプログラムにおいて、
前記重複度が、同一キー値を有する検索キーのキー数が多くなるほど、大きな値となることを特徴とするプログラム。
【請求項１２】
請求項１１記載のプログラムにおいて、
前記コンピュータを、
前記検索対象キー列に検索キーが追加された場合および前記検索対象キー列から検索キーが削除された場合、前記検索対象キー列中の各キー値毎に、そのキー値を有する検索キーのキー数が登録された重複度管理表を更新し、更新後の前記重複度管理表の内容に基づいて、キー値毎のキー数の平均値を求め、該平均値を重複度とする重複度決定部として機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、重複を許す検索キーを持つ配列型インデックスなどのように、複数の検索キーが昇順あるいは降順に並び、且つキー値が同一の検索キーを含んだキー列を検索対象キー列にするキー検索技術に関し、特に、指示された検索対象キー値を有する検索キーの内の先頭あるいは末尾の検索キーを検索するキー検索技術に関する。
【背景技術】
【０００２】
重複を許す検索キーを持つ配列型インデックスやファイル等を検索する場合、利用者によって指示されたキー値（検索対象キー値）を持つ検索キーの内の、先頭の検索キーを検索するということが従来から行われている。検索対象キー値を持つ先頭の検索キーを検索するのは、その後の処理を効率的に行えるようにするためである。例えば、図１６に示すような配列型インデックス１０１において、利用者が検索対象キー値として「ｄ」を指定した場合、キー値「ｄ」を有する検索キーｋ３〜ｋ１０の内の、先頭の検索キーが検索されれば、利用者は、次レコードを要求するボタンのみを操作するだけで、キー値「ｄ」を有するキーｋ３〜ｋ１０によってポイントされるレコードを全て参照することが可能になり、操作性が向上する。
【０００３】
ところで、従来のこの種の技術としては、次のような技術が知られている（例えば、特許文献１参照）。この特許文献１に記載されている従来の情報検索装置は、時刻が検索キーとなっているログファイルを検索対象にしており、利用者によって検索対象にする時刻が入力されると、先ず、二分検索法によって上記時刻を検索キーとして含んだレコードを検索する。その後、二分検索法で検索したレコードを検索開始レコードにして、線形検索法でログファイルを降順方向に検索し、利用者によって指示された時刻を含んだレコードの内の先頭のレコードを検索する。
【０００４】
【特許文献１】特開２００１−１６７０９４号公報
【発明の開示】
【発明が解決しようとする課題】
【０００５】
上述した従来の技術は、先ず、二分検索法により利用者によって指示された時刻を含むレコードの内の１つを検索し、その後、上記検索したレコードを検索開始レコードにして線形検索法で降順方向にログファイルを検索するようにしているので、全ての検索を線形検索法によって行う場合に比較して、検索処理を高速化することができる。しかしながら、上述した従来の技術では、二分検索法によって利用者が指示した時刻を含むレコードを検索した後は、常に線形検索法によって先頭のレコードを検索するようにしているため、同一キー値を含むレコードが多数存在する場合、検索処理を充分に高速化することができないという問題があった。
【０００６】
なお、二分検索法によって先頭レコードを検索するようにすることも考えられるが、このようにした場合は、同一キー値を含むレコードが少ないと、非効率的になってしまうという問題がある。
【０００７】
〔発明の目的〕
そこで、本発明の目的は、検索対象キー列に含まれている同一キー値を有する検索キーの数にかかわらず、検索対象キー値を有する検索キーの内の、先頭または末尾の検索キーを高速に検索できるようにすることにある。
【課題を解決するための手段】
【０００８】
本発明にかかる第１のキー検索装置は、
複数の検索キーが昇順または降順に並び、且つキー値が同一の検索キーを含んだ検索対象キー列の中から、指示された検索対象キー値を有し且つ前記検索対象キー値とは異なるキー値を有する検索キーとの境界となる検索キーを検索するキー検索装置であって、
前記検索対象キー列から、前記検索対象キー値を有する検索キーを二分検索法によって検索するキー検索部と、
前記検索対象キー列の検索キーの重複度と、線形検索法と二分検索法の平均コストの比とに基づいて、線形検索法または二分検索法の内の一方を選択し、該選択した検索方法により、前記キー検索部で検索された検索キーを検索開始キーにして、前記検索対象キー値を有し且つ前記検索対象キー値とは異なるキー値を有する検索キーとの境界となる検索キーを検索する境界検索部とを備えたことを特徴とする。
【０００９】
本発明にかかる第２のキー検索装置は、第１のキー検索装置において、
前記境界検索部が、
前記キー検索部で検索された検索キーを検索開始キーにして、前記検索対象キー値を有し且つ前記検索対象キー値とは異なるキー値を有する検索キーとの境界となる検索キーを、線形検索法によって検索する第１の重複キー境界検索部と、
前記キー検索部で検索された検索キーを検索開始キーにして、前記検索対象キー値を有し且つ前記検索対象キー値とは異なるキー値を有する検索キーとの境界となる検索キーを、二分検索法によって検索する第２の重複キー境界検索部と、
前記検索対象キー列の検索キーの重複度と、線形検索法と二分検索法の平均コストの比とに基づいて、前記第１の重複キー境界検索部または前記第２の重複キー境界検索部を動作させる検索法決定部を備えたことを特徴とする。
【００１０】
本発明にかかる第３のキー検索装置は、第１または第２のキー検索装置において、
前記重複度が、同一キー値を有する検索キーのキー数が多くなるほど、大きな値となることを特徴とする。
【００１１】
本発明にかかる第４のキー検索装置は、第３のキー検索装置において、
前記検索対象キー列中の各キー値毎に、そのキー値を有する検索キーのキー数が登録された重複度管理表と、
前記検索対象キー列に検索キーが追加された場合および前記検索対象キー列から検索キーが削除された場合、前記重複度管理表を更新し、更新後の前記重複度管理表の内容に基づいて、キー値毎のキー数の平均値を求め、該平均値を重複度とする重複度決定部とを備えたことを特徴とする。
【００１２】
本発明にかかる第１のキー検索方法は、
複数の検索キーが昇順または降順に並び、且つキー値が同一の検索キーを含んだ検索対象キー列の中から、指示された検索対象キー値を有し且つ前記検索対象キー値とは異なるキー値を有する検索キーとの境界となる検索キーを検索するキー検索方法であって、
前記検索対象キー列から、前記検索対象キー値を有する検索キーを二分検索法によって検索するキー検索ステップと、
前記検索対象キー列の検索キーの重複度と、線形検索法と二分検索法の平均コストの比とに基づいて、線形検索法または二分検索法の内の一方を選択し、該選択した検索方法により、前記キー検索部で検索された検索キーを検索開始キーにして、前記検索対象キー値を有し且つ前記検索対象キー値とは異なるキー値を有する検索キーとの境界となる検索キーを検索する境界検索ステップとを含むことを特徴とする。
【００１３】
本発明にかかる第２のキー検索方法は、第１のキー検索方法において、
前記境界検索ステップが、
前記キー検索部で検索された検索キーを検索開始キーにして、前記検索対象キー値を有し且つ前記検索対象キー値とは異なるキー値を有する検索キーとの境界となる検索キーを、線形検索法によって検索する第１の重複キー境界検索ステップと、
前記キー検索部で検索された検索キーを検索開始キーにして、前記検索対象キー値を有し且つ前記検索対象キー値とは異なるキー値を有する検索キーとの境界となる検索キーを、二分検索法によって検索する第２の重複キー境界検索ステップと、
前記検索対象キー列の検索キーの重複度と、線形検索法と二分検索法の平均コストの比とに基づいて、前記第１の重複キー境界検索ステップまたは前記第２の重複キー境界検索ステップを起動させる検索法決定ステップとを含むことを特徴とする。
【００１４】
本発明にかかる第３のキー検索方法は、第１または第２のキー検索方法において、
前記重複度が、同一キー値を有する検索キーのキー数が多くなるほど、大きな値となることを特徴とする。
【００１５】
本発明にかかる第４のキー検索方法は、第３のキー検索方法において、
前記検索対象キー列に検索キーが追加された場合および前記検索対象キー列から検索キーが削除された場合、前記検索対象キー列中の各キー値毎に、そのキー値を有する検索キーのキー数が登録された重複度管理表を更新し、更新後の前記重複度管理表の内容に基づいて、キー値毎のキー数の平均値を求め、該平均値を重複度とする重複度決定ステップを含むことを特徴とする。
【００１６】
本発明にかかる第１のプログラムは、
コンピュータを、複数の検索キーが昇順または降順に並び、且つキー値が同一の検索キーを含んだ検索対象キー列の中から、指示された検索対象キー値を有し且つ前記検索対象キー値とは異なるキー値を有する検索キーとの境界となる検索キーを検索するキー検索装置として機能させるためのプログラムであって、
前記コンピュータを、
前記検索対象キー列から、前記検索対象キー値を有する検索キーを二分検索法によって検索するキー検索部、
前記検索対象キー列の検索キーの重複度と、線形検索法と二分検索法の平均コストの比とに基づいて、線形検索法または二分検索法の内の一方を選択し、該選択した検索方法により、前記キー検索部で検索された検索キーを検索開始キーにして、前記検索対象キー値を有し且つ前記検索対象キー値とは異なるキー値を有する検索キーとの境界となる検索キーを検索する境界検索部として機能させる。
【００１７】
本発明にかかる第２のプログラムは、第１のプログラムにおいて、
前記境界検索部が、
前記キー検索部で検索された検索キーを検索開始キーにして、前記検索対象キー値を有し且つ前記検索対象キー値とは異なるキー値を有する検索キーとの境界となる検索キーを、線形検索法によって検索する第１の重複キー境界検索部と、
前記キー検索部で検索された検索キーを検索開始キーにして、前記検索対象キー値を有し且つ前記検索対象キー値とは異なるキー値を有する検索キーとの境界となる検索キーを、二分検索法によって検索する第２の重複キー境界検索部と、
前記検索対象キー列の検索キーの重複度と、線形検索法と二分検索法の平均コストの比とに基づいて、前記第１の重複キー境界検索部または前記第２の重複キー境界検索部を動作させる検索法決定部を備えたことを特徴とする。
【００１８】
本発明にかかる第３のプログラムは、第１または第２のプログラムにおいて、
前記重複度が、同一キー値を有する検索キーのキー数が多くなるほど、大きな値となることを特徴とする。
【００１９】
本発明にかかる第４のプログラムは、第３のプログラムにおいて、
前記コンピュータを、
前記検索対象キー列に検索キーが追加された場合および前記検索対象キー列から検索キーが削除された場合、前記検索対象キー列中の各キー値毎に、そのキー値を有する検索キーのキー数が登録された重複度管理表を更新し、更新後の前記重複度管理表の内容に基づいて、キー値毎のキー数の平均値を求め、該平均値を重複度とする重複度決定部として機能させる。
【００２０】
〔作用〕
検索対象キー列に検索キーが追加された場合および検索対象キー列から検索キーが削除された場合、重複度決定部が、上記検索対象キー列の重複度を算出し直す。重複度は、同一キー値を有する検索キーの数が多くなるほど大きな値となるものであり、例えば、各キー値毎のキー数の平均値を採用することができる。
【００２１】
利用者によって、検索対象キー値が指定された場合は、先ず、キー検索部が、検索対象キー列から、上記検索対象キー値を有する検索キーを二分検索法によって検索する。その後、境界検索部が、重複度決定部で算出された重複度と、線形検索法と二分検索法の平均コストの比とに基づいて、線形検索法または二分検索法の内の一方を選択し、選択した検索方法により、キー検索部で検索された検索キーを検索開始キーにして、上記検索対象キー値を有し且つ上記検索対象キー値とは異なるキー値を有する検索キーとの境界となる検索キーを検索する。
【発明の効果】
【００２２】
本発明によれば、検索対象キー列に含まれている同一キー値を有する検索キーの数にかかわらず、検索対象キー値を有する検索キーの内の、先頭または末尾の検索キーを高速に検索できるという効果を得ることができる。その理由は、検索対象キー列の検索キーの重複度と、線形検索法と二分検索法の平均コストの比とに基づいて、線形検索法または二分検索法の内の一方を選択し、選択した検索方法により、キー検索部で検索された検索キーを検索開始キーにして、検索対象キー値を有し且つ検索対象キー値とは異なるキー値を有する検索キーとの境界となる検索キーを検索する境界検索部を備えているからである。
【発明を実施するための最良の形態】
【００２３】
次に、発明を実施するための最良の形態について図面を参照して詳細に説明する。
【００２４】
〔本発明の原理〕
先ず、本発明の実施の形態を説明する前に、本発明の原理について説明しておく。
【００２５】
配列型インデックスにおいて、Ｎ個のデータから１つのキーを検索する場合、キーの重複を許さないインデックスに二分検索法を使うと最大(log2Ｎ＋１)回の比較で検索が終了する。キーの重複を許す配列型インデックスの場合、この処理に加えて「同一のキー値を有する同一検索キー群の先頭の位置を検出する」処理が必要となる。
【００２６】
この処理は、一般的には２つの方法が考えられる。 
【００２７】
第１の方法は、線形検索法により、配列型インデックスを逆順に比較しながら、同一検索キー群の先頭位置を検出する方法である。第２の方法は、二分検索法により、検索範囲を絞り込みながら、同一検索キー群の先頭位置を検出する方法である。
【００２８】
Ｎ個のデータから１つのキーを検索する場合の最大比較回数は、線形検索法ではＮ回、二分検索法では(log2Ｎ＋１)回である。図１３にデータ数Ｎを１〜１０としたときの線形検索法および二分検索法の最大比較回数を示す。
【００２９】
また、ｎ回の比較処理によって同一検索キー群の先頭位置を検出できた場合の、線形検索法および二分検索法それぞれの処理内容とその平均コスト（アセンブラレベルでの平均処理ステップ数）は、図１４に示すものとなる。なお、線形検索法の処理内容におけるＳＬ４等は、図１１のフローチャートにおけるステップ番号を示し、二分検索法の処理内容におけるＳＢ２等は、図１２のフローチャートにおけるステップ番号を示している。図１４に示すように、二分検索法の平均コストは、線形検索法の平均コストの１．５倍となっている。
【００３０】
図１３に示した線形検索法および二分検索法の最大検索回数と、図１４に示した線形検索法および二分検索法の平均コストとを考慮して、データ数Ｎが１〜１０のときの、線形検索法および二分検索法のコストを算出すると、図１５に示すようになる。
【００３１】
図１５を参照して分かるように、データ数Ｎが小さい場合には線形検索法の方が効率がよく、データ数が大きい場合には二分検索法の方が効率がよいと言える。そして、その境界値は、この例の場合「６」となる。
【００３２】
従って、検索キーが重複しているレコード数の期待値「６」より小さい場合には線形検索法を、「６」より大きい場合には二分検索法を用いることで高速化を図ることができる。 実際には両方法ともに付加的な処理があるために、前出の期待値が「６」の場合には、合計コストは、線形検索法で「36+6α」、二分検索法で「36+4α」（αは１回の比較にかかる付加的な処理のコスト）となるので、二分検索法を用いるようにする。
【００３３】
〔実施の形態の構成の説明〕
次に、本発明にかかるキー検索装置の実施の形態の構成について説明する。
【００３４】
図１に示す通り、本実施の形態のキー検索装置１には、ハードディスク等の記憶装置２が接続されると共に、キーボード等の入力装置３が接続されている。
【００３５】
記憶装置２には、キー検索装置１が検索対象にする配列型インデックスＡが登録されている。配列型インデックスＡは、検索キーの重複を許すものであり、複数の検索キーが昇順に並んでいる。図１の例では、検索キーｋ３〜ｋ１０のキー値が全て「ｄ」となっており、また、検索キーｋ１１，ｋ１２のキー値が「ｅ」となっている。なお、図１では、図示を省略したが、記憶装置２には、検索キーｋ１、ｋ２、…によってポイントされるレコード（データ）も登録されている。また、本実施の形態では、配列型インデックスＡとして検索キーが昇順に並んでいるものを例に挙げて説明するが、検索キーが降順に並んでいるものであっても、本発明を適用することができる。
【００３６】
キー検索装置１は、キー検索部ＳＫと、検索法決定部ＳＭ、第１の重複キー境界検索部ＳＬおよび第２の重複キー境界検索部ＳＢから構成される境界検索部１１と、重複度決定部Ｄと、重複度管理表ＤＴとから構成されている。
【００３７】
キー検索部ＳＫは、入力装置３を介して利用者から検索指示が入力されたとき、配列型インデックスＡを二分検索法で検索する機能を有する。図２にキー検索部ＳＫが行う処理の概要を示す。なお、検索指示には、検索対象にするキー値（検索対象キー値）が含まれている。
【００３８】
重複度管理表ＤＴには、配列型インデックスＡ中の各キー値ｂ，ｃ，ｄ，…毎に、そのキー値を有する検索キーのキー数（重複キー数）および重複キー数の平均値が登録されている。本実施の形態では、図３に示すように、項目「キー値」，「重複キー数」を有するレコードが登録されると共に、重複キー数の平均値が重複度として登録されている。同図の例は、キー値ｂ，ｃ，ｄ，…を有する検索キーの重複キー数がそれぞれ２，１，８，…であることを示すと共に、重複キー数の平均値（重複度）が５．８であることを示している。
【００３９】
重複度決定部Ｄは、配列型インデックスＡが更新される毎に、重複度管理表ＤＴを参照・更新し、重複度（重複キー数の平均値）を算出し直す機能を有する。図３に重複度決定部Ｄが行う処理の概要を示す。なお、配列型インデックスＡが更新されないものである場合には、重複度決定部Ｄおよび重複度管理表ＤＴは不要になり、その代わりに、配列型インデックスＡの重複度が登録されたメモリなどを用意しておけば良い。
【００４０】
境界検出部１１は、重複度決定部Ｄが決定した重複度と、予め定められている閾値Thとに基づいて線形検索法または二分検索法の一方を選択し、選択した検索方法により、キー検索部ＳＫで検索された検索キーを検索開始キーにして、検索対象キー値を有するキーの内の先頭の検索キーを検索する機能を有する。なお、閾値Thは、線形検索法と二分検索法の平均コストの比に基づいて予め決められている値である。
【００４１】
境界検索部１１内の検索法決定部ＳＭは、キー検索部ＳＫの処理が終わった後、重複度決定部Ｄの算出した重複度と、予め定められている閾値Thとを基に、第１，第２の重複キー境界検索部ＳＬ，ＳＢの内のどちらを動作させるか決定する機能を有する。
【００４２】
第１の重複キー境界検索部ＳＬは、キー検索部ＳＫの検出したキー位置から、線形検索法により同一検索キー群の先頭位置を検出する機能を有する。図４に第１の重複キー境界検索部ＳＬが行う処理の概要を示す。
【００４３】
第２の重複キー境界検索部ＳＢは、キー検索部ＳＫの検出したキー位置から、二分検索法により同一検索キー群の先頭位置を検出する機能を有する。図５に第２の重複キー境界検索部ＳＢが行う処理の概要を示す。
【００４４】
なお、本実施の形態では、第１，第２の重複キー境界検索部ＳＬ，ＳＢが同一検索キー群の先頭位置を検出するようにしたが、末尾位置を検出するようにしても良い。また、キー検索装置１は、コンピュータによって実現可能なものであり、コンピュータによって実現する場合は、例えば、次のようにする。コンピュータをキー検索装置１として機能させるためのプログラムを記録したディスク、半導体メモリ、その他の記録媒体を用意し、コンピュータに上記プログラムを読み取らせる。コンピュータは、読み取ったプログラムに従って自身の動作を制御することにより、自コンピュータ上に、キー検索部ＳＫ、検索法決定部ＳＭ、第１の重複キー境界検索部ＳＬ、第２の重複キー境界検索部ＳＢおよび重複度決定部Ｄを実現する。
【００４５】
〔実施の形態の動作の説明〕
次に、各図を参照して本実施の形態の動作について詳細に説明する。
【００４６】
先ず、配列型インデックスＡの更新時に、重複度決定部Ｄによって行われる重複度決定処理について図６のフローチャートを参照して説明する。
【００４７】
配列型インデックスＡの要素の更新（追加・削除を含む）処理が行われると（図６のステップＤ０）、重複度決定部Ｄは、配列型インデックスＡに対して検索キーの追加または削除のイベントが発生したかどうかを判定する（ステップＤ１）。
【００４８】
ステップＤ１において、追加のイベントが発生したと判定した場合には、重複度管理表加算処理ＤＡを実行し、イベントループの終端であるステップＤ４に進む（ステップＤ２→Ｄ４）。なお、重複度管理表加算処理ＤＡについては、後で図７のフローチャートを参照して詳しく説明する。
【００４９】
また、ステップＤ１において、削除のイベントが発生したと判定した場合には、重複度管理表減算処理ＤＳを実行し、イベントループの終端であるステップＤ４に進む（ステップＤ３→Ｄ４）。なお、重複度管理表減算処理ＤＳについては、後で図８のフローチャートを参照して詳しく説明する。
【００５０】
また、ステップＤ１において、追加のイベントも削除のイベントも発生していないと判定した場合には、イベントループの終端であるステップＤ４に進む（ステップＤ１→Ｄ４）。
【００５１】
ステップＤ４において、残りのイベントが存在すると判定した場合（判定結果がｙｅｓの場合）は、ステップＤ１に戻る。これに対して、ステップＤ４において、残りのイベントが存在しないと判定した場合（判定結果がｎｏの場合）は、ステップＤ５に進む。
【００５２】
ステップＤ５では、重複度管理表ＤＴを参照し、各キー値に対応付けて登録されている重複キー数の平均値を重複度として算出する。これにより、重複度決定部Ｄは、その処理を終了する。
【００５３】
次に、図６のステップＤ２で行う重複度管理表加算処理ＤＡについて、図７のフローチャートを参照して詳細に説明する。
【００５４】
先ず、二分検索法により重複度管理表ＤＴを検索し、目的の検索キー（追加された検索キー）のキー値ｋと同一のキー値を有するレコードを探し出す（ステップＤＡ１）。
【００５５】
そして、該当レコードが存在しなければ（ステップＤＡ２がｎｏ）、キー値「ｋ」、重複キー数「０」を持つレコードを重複度管理表ＤＴに追加し、更に、当該キーにおいて重複度管理表ＤＴ中の各レコードを昇順ソートした後（ステップＤＡ３）、ステップＤＡ４へ進む。これに対して、該当レコードが存在する場合（ステップＤＡ２がｙｅｓ）は、直ちにステップＤＡ４へ進む。
【００５６】
ステップＤＡ４では、重複度管理表ＤＴ中のキー値ｋを持つレコードの重複キー数を１インクリメントする。以上が、図６のステップＤ２で行う重複度管理表加算処理ＤＡの詳細である。
【００５７】
次に、図６のステップＤ３で行う重複度管理表減算処理ＤＳについて図８のフローチャートを参照して詳細に説明する。
【００５８】
先ず、二分検索法により重複度管理表ＤＴを検索し、目的の検索キー（削除された検索キー）のキー値ｋと同一のキー値を有するレコードを探し出す（ステップＤＳ１）。次いで、探し出したレコード中の重複キー数を１デクリメントする（ステップＤＳ２）。
【００５９】
そして、上記レコード中の重複キー数が「０」になったなら（ステップＤＳ３がｙｅｓ）、上記レコードを重複度管理表ＤＴから削除した後、当該キーにより重複度管理表ＤＴ中のレコードを昇順ソートし（ステップＤＳ４）、重複度管理表減算処理ＤＳを終了する。これに対して、上記レコード中の重複キー数が「０」にならなかったら（ステップＤＳ３がｎｏ）、直ちに、重複度管理表減算処理ＤＳを終了する。以上が、図６のステップＤ３で行う重複度管理表減算処理の詳細である。
【００６０】
次に、配列型インデックスＡを検索する場合の動作について説明する。
【００６１】
利用者は、配列型インデックスＡを検索する場合、入力装置３から検索指示を入力する。この検索指示には、検索対象にする検索キーのキー値ｋが含まれている。
【００６２】
検索指示が入力されると、先ず、キー検索部ＳＫによって図９のフローチャートに示すキー検索処理が行われる。
【００６３】
先ず、キー検索部ＳＫは、配列型インデックスＡの上限位置（配列の添え字）を上限ポインタｕに、下限位置を下限ポインタｌに設定する（ステップＳＫ１）。
【００６４】
次いで、上限ポインタｕに設定されている上限位置と、下限ポインタｌに設定されている下限位置との中間位置を求め、検索ポインタｍに設定する（ステップＳＫ２）。ここで、中間位置は、｛(l+u)+1}/2となる。ただし、ｍが小数になる場合には、小数点以下を切り捨てる。
【００６５】
そして、検索ポインタｍで示される検索位置のキー値Ａ[m]（配列型インデックスＡの第ｍ番目のキー値）が検索対象キー値ｋと等しければ（ステップＳＫ３がｙｅｓ）、ｍを検出位置ポインタk0に、ｌを検索下限ポインタklに設定し、更に、検索法決定部ＳＭを起動した後（ステップＳＫ８）、キー検索処理を終了する。これに対して、Ａ[m]≠ｋならば（ステップＳＫ３がｎｏ）、Ａ[m]＞ｋであるか否かを調べる（ステップＳＫ４）。
【００６６】
そして、Ａ[m]＞ｋならば（ステップＳＫ４がｙｅｓ）、上限ポインタｕをｍ−１で更新し（ステップＳＫ５）、ステップＳＫ７に進む。これに対して、Ａ[m]≦Ｋならば（ステップＳＫ４がｎｏ）、下限ポインタｌをｍ＋１で更新し（ステップＳＫ６）、ステップＳＫ７に進む。
【００６７】
ステップＳＫ７において、ｌ＞ｕならば（判定結果がｙｅｓ）、該当データなしとしてキー検索処理を終了する。その際、図示を省略した表示装置に該当データがない旨を表示するようにしても良い。これに対して、ｌ≦ｕならば（ステップＳＫ７がｎｏ）、ステップＳＫ２に戻る。
【００６８】
次に、検索法決定部ＳＭで行う検索法決定処理を、図１０のフローチャートを参照して説明する。
【００６９】
検索法決定部ＳＭは、キー検索部ＳＫから起動されると、先ず、重複度決定部Ｄによって決定されている重複度ｄと、予め定められている閾値Thとを比較する（ステップＳＭ１）。ここで、上記閾値Thは、前述したように、線形検索法の平均コストと二分検索法の平均コストとの比に応じて予め決めておくものであり、線形検索法および二分検索法のコストが図１５に示すものである場合には、上記閾値Thは前述したように「６」となる。
【００７０】
そして、重複度ｄが閾値未満Thならば（ステップＳＭ１がｙｅｓ）、線形検索法により検索を行う第１の重複キー境界検索部ＳＬを起動し（ステップＳＭ２）、検索法決定処理を終了する。これに対して、重複度ｄが閾値Th以上である場合（ステップＳＭ１がｎｏ）は、二分検索法により検索を行う第２の重複キー境界検索部ＳＢを起動し（ステップＳＭ３）、検索法決定処理を終了する。
【００７１】
次に、第１の重複キー境界検索部ＳＬの動作を説明する。重複キー境界検索部ＳＬは、検索法決定部ＳＭから起動されると、図１１のフローチャートに示す線形検索法を用いた重複キー境界検索処理を行う。
【００７２】
重複キー境界検索部ＳＬは、先ず、キー検索部ＳＫによって検出位置ポインタk0に設定されている値を検索ポインタｍに、検索下限ポインタklに設定されている値を下限ポインタｌに設定する（ステップＳＬ１）。
【００７３】
その後、検索ポインタｍによって示される検索位置よりも１つ前の要素のキー値Ａ[m-1]が、検索対象キー値ｋと一致しているか否かを調べる（ステップＳＬ２）。
【００７４】
そして、キー値Ａ [m-1]が検索対象キー値ｋでない場合（ステップＳＬ２がｎｏ）は、ｍが目的キーの先頭位置になるので、ｍを検出位置ポインタk0に設定し（ステップＳＬ５）、重複キー境界検索処理（線形検索用）を終了する。これに対して、キー値Ａ[m-1]が検索対象キー値ｋである場合（ステップＳＬ２がｙｅｓ）は、検索下限の判定を行うためにステップＳＬ３に進む。
【００７５】
ステップＳＬ３では、検索ポインタｍと下限ポインタｌが等しいか否かを調べる。そして、ｍ＝ｌの場合（ステップＳＬ３がｙｅｓ）は、検索下限まで全て検索したことになるので、ｍを検出位置ポインタk0に設定し（ステップＳＬ５）、重複キー境界検索処理を終了する。これに対して、ｍ＝ｌでない場合（ステップＳＬ３がｎｏ）は、検索位置を更新するために、検索ポインタｍをデクリメントし（ステップＳＬ４）、ステップＳＬ２に戻る。
【００７６】
次に、第２の重複キー境界検索部ＳＢの動作について説明する。重複キー境界検索部ＳＢは、検索法決定部ＳＭから起動されると、図１２のフローチャートに示す二分検索法を用いた重複キー境界検索処理を行う。
【００７７】
先ず、重複キー境界検索部ＳＢは、キー検索部ＳＫが検出位置ポインタk0，検索下限ポインタklに設定した値をそれぞれ上限ポインタｕ,下限ポインタｌに設定する（ステップＳＢ１）。
【００７８】
次いで、上限ポインタｕに設定されている上限位置と、下限ポインタｌに設定されている下限位置との中間位置を求め、検索ポインタｍに設定する（ステップＳＢ２）。ここで、中間位置は、｛(l+u)+1}/2となる。ただし、ｍが小数になる場合には、小数点以下を切り捨てる。
【００７９】
その後、検索ポインタｍの値と上限ポインタｕの値が同じであるか否かを調べる（ステップＳＢ３）。
【００８０】
そして、ｍ＝ｕである場合（ステップＳＢ３がｙｅｓ）は、u-l≦1であり、実質的に検索終了であるので、ステップＳＢ８に進む。これに対して、ｍ＝ｕでない場合（ステップＳＢ３がｎｏ）は、、ステップＳＢ４に進む。
【００８１】
ステップＳＢ４では、検索ポインタｍによって示されるキー値Ａ[m]が検索対象キー値ｋと等しいか否かを調べる。
【００８２】
そして、Ａ[m]＝ｋの場合（ステップＳＢ４がｙｅｓ）は、目的キーの先頭位置判定を行うためにステップＳＢ６に進む。これに対して、Ａ[m]≠ｋの場合（ステップＳＢ４がｎｏ）は、ｍ＋１を下限ポインタｌに設定し（ステップＳＢ５）、ステップＳＢ２に戻る。
【００８３】
ステップＳＢ６では、Ａ[m-1]＝ｋであるか否かを調べる。
【００８４】
そして、Ａ[m-1]＝ｋである場合（ステップＳＢ６がｙｅｓ）は、ｍ−１を上限ポインタｕに設定し（ステップＳＢ７）、ステップＳＢ２に戻る。これに対して、Ａ[m-1]≠ｋの場合（ステップＳＢ６がｎｏ）は、ｍが目的キーの先頭位置になるので、ｍを検出位置ポインタk0に設定し（ステップＳＢ１０）、重複キー先頭検索処理を終了する。
【００８５】
また、ステップＳＢ８では、Ａ[l]＝ｋであるか否かを調べる。
【００８６】
そして、Ａ[l]＝ｋの場合（ステップＳＢ８がｙｅｓ）は、ｌが目的キーの先頭位置になるので、ｌを検出位置ポインタk0に設定し（ステップＳＢ９）、重複キー先頭検索処理ＳＢを終了する。これに対して、Ａ[l]≠ｋの場合（ステップＳＢ８がｎｏ）は、ｍが目的キーの先頭位置になるので、ｍを検索位置ポインタk0に設定し（ステップＳＢ１０）、重複キー先頭検索処理（二分検索用）を終了する。
【００８７】
〔実施の形態の効果〕
本実施の形態によれば、配列型インデックスＡに含まれている同一キー値を有する検索キーの数にかかわらず、検索対象キー値を有する検索キーの内の、先頭の検索キーを高速に検索できるという効果を得ることができる。その理由は、配列型インデックスＡの検索キーの重複度と、線形検索法と二分検索法の平均コストの比とに基づいて、線形検索法または二分検索法の内の一方を選択し、選択した検索方法により、キー検索部ＳＫで検索された検索キーを検索開始キーにして、検索対象キー値を有する検索キーの内の、先頭の検索キーを検索する境界検索部１１を備えているからである。
【００８８】
また、本実施の形態は、配列型インデックスＡに検索キーが追加された場合や、配列型インデックスＡから検索キーが削除された場合であっても、検索対象キー値を有する検索キーの内の、先頭の検索キーを高速に検索することができるという効果を得ることができる。その理由は、配列型インデックスＡに検索キーが追加された場合および配列型インデックスＡから検索キーが削除された場合、重複度管理表ＤＴを更新し、更新後の重複度管理表ＤＴの内容に基づいて、キー値毎のキー数の平均値を重複度として算出する重複度決定部Ｄを備えているからである。
【産業上の利用可能性】
【００８９】
本発明によれば、配列型インデックスをはじめ、重複するキーをもつデータ列の検索全般に適用できる。
【図面の簡単な説明】
【００９０】
【図１】本発明にかかるキー検索装置１の実施の形態の構成例を示すブロック図である。
【図２】キー検索部ＳＫが行う処理の概要を示す図である。
【図３】重複度管理表ＤＴの内容例を示すと共に、重複度決定部Ｄが行う処理の概要を示す図である。
【図４】第１の重複キー境界検索部ＳＬが行う処理の概要を示す図である。
【図５】第２の重複キー境界検索部ＳＢが行う処理の概要を示す図である。
【図６】重複度決定部Ｄの処理例を示すフローチャートである。
【図７】図６のフローチャートのステップＤ２の詳細を示すフローチャートである。
【図８】図６のフローチャートのステップＤ３の詳細を示すフローチャートである。
【図９】キー検索部ＳＫの処理例を示すフローチャートである。
【図１０】検索法決定部ＳＭの処理例を示すフローチャートである。
【図１１】第１の重複キー境界検索部ＳＬの処理例を示すフローチャートである。
【図１２】第２の重複キー境界検索部ＳＢの処理例を示すフローチャートである。
【図１３】データ数が１〜１０のときの、線形検索法および二分検索法の最大比較回数を示す図である。
【図１４】線形検索法と二分検索法の平均コストの一例を示す図である。
【図１５】データ数が１〜１０のときの、線形検索法および二分検索法のコストを示す図である。
【図１６】配列型インデックスの一例を示す図である。
【符号の説明】
【００９１】
１…キー検索装置
Ｄ…重複度決定部
ＤＴ…重複度管理表
ＳＫ…キー検索部
１１…境界検索部
ＳＭ…検索法決定部
ＳＬ…第１の重複キー境界検索部（線形検索法）
ＳＢ…第２の重複キー境界検索部（二分検索法）
２…記憶装置
Ａ…配列型インデックス
３…入力装置
【図１】
2007249369.tif 000003
【図２】
2007249369.tif 000004
【図３】
2007249369.tif 000005
【図４】
2007249369.tif 000006
【図５】
2007249369.tif 000007
【図６】
2007249369.tif 000008
【図７】
2007249369.tif 000009
【図８】
2007249369.tif 000010
【図９】
2007249369.tif 000011
【図１０】
2007249369.tif 000012
【図１１】
2007249369.tif 000013
【図１２】
2007249369.tif 000014
【図１３】
2007249369.tif 000015
【図１４】
2007249369.tif 000016
【図１５】
2007249369.tif 000017
【図１６】
2007249369.tif 000018