(57)【要約】  エントリ挿入装置（２０００）は、Ｗ個（Ｗは２以上の正の整数）以下のエントリを格納する部分領域（３０２０）を複数有するノード（３０００）に対し、エントリ挿入する。各エントリは、Ｗ個のエントリに対して並行に同一処理を実行するＳＩＭＤ命令を用いて検索されることができる。エントリ挿入装置（２０００）は、新規エントリを、複数の部分領域（３０２０）うち、格納されているエントリの個数が１個以上かつＷ個未満である部分領域（３０２０）に挿入する挿入部（２０２０）、及び新規エントリが挿入された部分領域（３０２０）に格納されているエントリの個数がＷ個である場合は、その部分領域（３０２０）に格納されているエントリをソートするソート部（２０４０）を有する。
2014061305.tif 000002
【特許請求の範囲】
【請求項１】
格納できるエントリの個数がそれぞれＷ個（Ｗは２以上の正の整数）である複数の部分領域を含み、なおかつ、Ｗ個のエントリに対して並行に同一処理を実行するＳＩＭＤ（Ｓｉｎｇｌｅ  Ｉｎｓｔｒｕｃｔｉｏｎ  Ｍｕｌｔｉｐｌｅ  Ｄａｔａ）命令を利用することで、前記複数の部分領域に格納されているエントリを検索できるノードに対し、エントリを挿入するエントリ挿入装置であって、
新規エントリを、前記複数の部分領域のうち、格納されているエントリの個数が１以上かつＷ個未満である不飽和領域に対して挿入する挿入手段と、
前記新規エントリが挿入された部分領域が、格納されているエントリの個数がＷ個である飽和領域である場合は、該部分領域に格納されているエントリをソートし、
前記新規エントリが挿入された部分領域が、前記飽和領域でない場合は、該部分領域に格納されているエントリをソートしないソート手段と、
を有するエントリ挿入装置。
【請求項２】
前記ソート手段は、前記ＳＩＭＤ命令を用いて前記飽和領域をソートする請求項１記載のエントリ挿入装置。
【請求項３】
前記ソート手段は、個々にソートされている複数の前記飽和領域を連結した領域をソートする請求項１又は２記載のエントリ挿入装置。
【請求項４】
前記ソート手段は、個々にソートされている複数の前記飽和領域について、前記ＳＩＭＤ命令を用いて各飽和領域間でエントリを比較し、エントリを比較した結果に基づいて、該複数の飽和領域を連結した領域をソートする請求項３記載のエントリ挿入装置。
【請求項５】
前記飽和領域からエントリを検索する場合と、前記不飽和領域からエントリを検索する場合とで、異なった方法で検索を行う検索手段をさらに有する請求項１乃至４いずれか一項に記載のエントリ挿入装置。
【請求項６】
前記検索手段は、前記飽和領域の中にある、所定の条件を満たす複数のエントリの中から、該複数のエントリそれぞれが格納されている位置に基づいて、最大の値を示すエントリ又は最小の値を示すエントリを特定する請求項５記載のエントリ挿入装置。
【請求項７】
前記飽和領域に格納されている削除対象のエントリを、前記不飽和領域に格納されているエントリで上書きして削除する削除手段を有する請求項１乃至６いずれか一項に記載のエントリ挿入装置。
【請求項８】
前記削除手段に、各部分領域から、所定の条件を満たすエントリを削除させ、エントリが削除された部分領域が前記飽和領域である場合、前記ソート手段に、該部分領域をソートさせる分割手段を有する請求項７に記載のエントリ挿入装置。
【請求項９】
コンピュータを、格納できるエントリの個数がそれぞれＷ個（Ｗは２以上の正の整数）である複数の部分領域を含み、なおかつ、Ｗ個のエントリに対して並行に同一処理を実行するＳＩＭＤ（Ｓｉｎｇｌｅ  Ｉｎｓｔｒｕｃｔｉｏｎ  Ｍｕｌｔｉｐｌｅ  Ｄａｔａ）命令を利用することで、前記複数の部分領域に格納されているエントリを検索できるノードに対し、エントリを挿入するエントリ挿入装置として機能させるプログラムであって、前記コンピュータに、
新規エントリを、前記複数の部分領域のうち、格納されているエントリの個数が１以上かつＷ個未満である不飽和領域に対して挿入する挿入機能と、
前記新規エントリが挿入された部分領域が、格納されているエントリの個数がＷ個である飽和領域である場合は、該部分領域に格納されているエントリをソートし、
前記新規エントリが挿入された部分領域が、前記飽和領域でない場合は、該部分領域に格納されているエントリをソートしないソート機能と、
を持たせるプログラム。
【請求項１０】
格納できるエントリの個数がそれぞれＷ個（Ｗは２以上の正の整数）である複数の部分領域を含み、なおかつ、Ｗ個のエントリに対して並行に同一処理を実行するＳＩＭＤ（Ｓｉｎｇｌｅ  Ｉｎｓｔｒｕｃｔｉｏｎ  Ｍｕｌｔｉｐｌｅ  Ｄａｔａ）命令を利用することで、前記複数の部分領域に格納されているエントリを検索できるノードに対し、エントリを挿入するコンピュータによって実行される方法であって、
新規エントリを、前記複数の部分領域のうち、格納されているエントリの個数が１以上かつＷ個未満である不飽和領域に対して挿入する挿入ステップと、
前記新規エントリが挿入された部分領域が、格納されているエントリの個数がＷ個である飽和領域である場合は、該部分領域に格納されているエントリをソートし、前記新規エントリが挿入された部分領域が、前記飽和領域でない場合は、該部分領域に格納されているエントリをソートしないソートステップと、
を有する方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、エントリ挿入装置、方法、及びプログラムに関する。
【背景技術】
【０００２】
検索対象の各データにインデックスを付与し、インデックスツリーを構成しておくことで、データの検索にかかる時間を短くすることができる。具体的には、データを検索する場合に、データを直接検索する代わりに、インデックスツリーの中からそのデータに付与されているインデックスを検索する。データは、検索結果として取得したインデックスに基づいて取得することができる。【０００３】
インデックスツリーは、複数のエントリを含むデータ構造であるノードを連結した、ツリー構造のデータ構造である。エントリは、インデックス又はインデックスを探索するために用いられる指標値である。【０００４】
インデックスツリーには様々な種類がある。例えば非特許文献１や２には、B+-treeと呼ばれるインデックスツリーが記載されている。非特許文献３には、T-treeと呼ばれるインデックスツリーが記載されている。非特許文献４には、CSB+-treeと呼ばれるインデックスツリーが記載されている。【０００５】
非特許文献５は、インデックスを付与されたノードの探索に、ＳＩＭＤ命令（Ｓｉｎｇｌｅ  Ｉｎｓｔｒｕｃｔｉｏｎ  Ｍｕｌｔｉｐｌｅ  Ｄａｔａ命令）を利用する方法を開示している。ＳＩＭＤ命令は、複数のデータを対象に、同一の処理を並行に実行する命令である。【０００６】
非特許文献６は、ＳＩＭＤ命令を利用したインデックスの検索を高速にする方法を開示している。具体的には、上記方法は、ノード内に、そのノード内に含まれるエントリで構成されるサブツリーを構成する。さらに上記方法は、サブツリー内にも、サブツリー内に含まれるエントリで構成される小さなツリーを構成する。そして、上記方法は、ノードのサイズをＯＳ（Ｏｐｅｒａｔｉｎｇ  Ｓｙｓｔｅｍ）で管理されるページサイズと等しくする。また、上記方法は、サブツリーのサイズをＣＰＵのキャッシュラインサイズと等しくする。さらに上記方法は、サブツリー内に構成される小さなツリーのサイズを、ＳＩＭＤ命令が一度に対象に出来るデータの数と等しくする。
【先行技術文献】
【非特許文献】
【０００７】
【非特許文献１】R. Bayer and E. McCreight、「Organization and Maintenance of Large Ordered Indexes」、Acta Infomatica、Volume 1、No.3、pp. 173 - 189、1972年
【非特許文献２】D. Comer、「The Ubiquitous B-tree」、ACM、Computing Surveys、Volume 11, No. 2、pp. 121 - 137、1979年
【非特許文献３】T. J. Lehman and M. J. Carey、「A Study of Index Structures for Main Memory Database Management Systems」、International Conference on Very Large Data Bases、pp. 294 - 303、1986年
【非特許文献４】J. Rao and K. A. Ross、「Making B+-Trees Cache Conscious in Main Memory」、ACM、ACM SIGMOD International Conference on Management of Data、pp. 475 - 486、2000年
【非特許文献５】J. Zhou and K. A. Ross、「Implementing Database Operations Using SIMD Instructions」、ACM、ACM SIGMOD International Conference on Management of Data、pp. 145 - 156、2002年
【非特許文献６】C. Kim, J. Chhugani, N. Stish, E. Sedlar, A. D. Nguyen, T. Kaldewey, V. W. Lee, S. A. Brandt, and P. Dubey、「FAST: Fast Architecture Sensitive Tree Search on Modern CPUs and GPUs」、ACM、ACM SIGMOD International Conference on Management of Data、pp. 339 - 350、2010年
【発明の概要】
【発明が解決しようとする課題】
【０００８】
本発明者は、ＳＩＭＤ命令を利用してエントリの検索を行えるデータ構造において、データ構造に対するエントリの挿入にかかる時間を短くすることを検討した。非特許文献６は、エントリの挿入にかかる時間を短くする方法は開示していない。【０００９】
本発明の目的は、ＳＩＭＤ命令を利用してエントリの検索を行えるデータ構造において、データ構造に対するエントリの挿入にかかる時間を短くするエントリ挿入装置、方法、及びプログラムを提供することである。
【課題を解決するための手段】
【００１０】
本発明が提供するエントリ挿入装置は、格納できるエントリの個数がそれぞれＷ個（Ｗは２以上の正の整数）である複数の部分領域を含み、なおかつ、Ｗ個のエントリに対して並行に同一処理を実行するＳＩＭＤ（Ｓｉｎｇｌｅ  Ｉｎｓｔｒｕｃｔｉｏｎ  Ｍｕｌｔｉｐｌｅ  Ｄａｔａ）命令を利用することで、前記複数の部分領域に格納されているエントリを検索できるノードに対し、エントリを挿入するエントリ挿入装置である。当該エントリ挿入装置は、新規エントリを、前記複数の部分領域のうち、格納されているエントリの個数が１以上かつＷ個未満である不飽和領域に対して挿入する挿入手段と、前記新規エントリが挿入された部分領域が、格納されているエントリの個数がＷ個である飽和領域である場合は、該部分領域に格納されているエントリをソートし、前記新規エントリが挿入された部分領域が、前記飽和領域でない場合は、該部分領域に格納されているエントリをソートしないソート手段とを有する。【００１１】
本発明が提供するプログラムは、コンピュータを、上述したエントリ挿入装置として機能させるプログラムである。当該プログラムは、上述したエントリ挿入装置の各機能構成部が有する機能をコンピュータに持たせる。【００１２】
本発明が提供する方法は、格納できるエントリの個数がそれぞれＷ個（Ｗは２以上の正の整数）である複数の部分領域を含み、なおかつ、Ｗ個のエントリに対して並行に同一処理を実行するＳＩＭＤ（Ｓｉｎｇｌｅ  Ｉｎｓｔｒｕｃｔｉｏｎ  Ｍｕｌｔｉｐｌｅ  Ｄａｔａ）命令を利用することで、前記複数の部分領域に格納されているエントリを検索できるノードに対し、エントリを挿入するコンピュータによって実行される方法である。当該方法は、新規エントリを、前記複数の部分領域のうち、格納されているエントリの個数が１以上かつＷ個未満である不飽和領域に対して挿入する挿入ステップと、前記新規エントリが挿入された部分領域が、格納されているエントリの個数がＷ個である飽和領域である場合は、該部分領域に格納されているエントリをソートし、前記新規エントリが挿入された部分領域が、前記飽和領域でない場合は、該部分領域に格納されているエントリをソートしないソートステップとを有する。
【発明の効果】
【００１３】
本発明によれば、ＳＩＭＤ命令を利用してエントリの検索を行えるデータ構造において、データ構造に対するエントリの挿入にかかる時間を短くするエントリ挿入装置、方法、及びプログラムを提供できる。
【図面の簡単な説明】
【００１４】
上述した目的、およびその他の目的、特徴および利点は、以下に述べる好適な実施の形態、およびそれに付随する以下の図面によってさらに明らかになる。【００１５】
【図１】実施形態１に係るエントリ挿入装置をその使用環境と共に示すブロック図である。
【図２】挿入部の動作を概念的に示す図である。
【図３】実施形態１に係るエントリ挿入装置のハードウエア構成の一例を示すブロック図である。
【図４】実施形態１に係るエントリ挿入装置によるエントリ挿入処理の流れの一例を示すフローチャートである。
【図５】変形例１のソート部が、ＳＩＭＤ命令を用いてエントリ同士の比較を行う方法の一例を示した図である。
【図６】ソートテーブルの構成を示す図である。
【図７】実施形態２に係るエントリ挿入装置を、その使用環境と共に示すブロック図である。
【図８】検索部が飽和領域に対して行う検索の動作を概念的に示す図である。
【図９】実施形態３に係るエントリ挿入装置を、その使用環境と共に示すブロック図である。
【図１０】削除部の動作を概念的に示す図である。
【図１１】実施形態４に係るエントリ挿入装置を、その使用環境と共に示すブロック図である。
【図１２】分割部が行う分割処理の流れの一例を示すフローチャートである。
【発明を実施するための形態】
【００１６】
以下、本発明の実施の形態について、図面を用いて説明する。尚、すべての図面において、同様な構成要素には同様の符号を付し、適宜説明を省略する。
【００１７】
[実施形態１]
図１は、本実施形態に係るエントリ挿入装置２０００を、その使用環境と共に示すブロック図である。図１において、矢印の流れは情報の流れを示す。また、図１において、各機能構成部は、ハードウエア単位の構成ではなく、機能単位の構成を示している。
【００１８】
エントリ挿入装置２０００は、ノード３０００に対してエントリを挿入する。ノード３０００は、複数の部分領域３０２０を有する。部分領域３０２０は、複数のデータを格納する。以下、部分領域３０２０が格納するデータを、エントリと表記する。部分領域３０２０が格納できるエントリの個数はＷ個（Ｗは２以上の正の整数）である。
【００１９】
ノード３０００に格納されているエントリは、Ｗ個のエントリに対して並行に同一処理を実行するＳＩＭＤ命令を利用して検索されることができる。
【００２０】
エントリ挿入装置２０００は、挿入部２０２０を有する。挿入部２０２０は、新規エントリを、複数の部分領域３０２０うち、格納されているエントリの個数が、１個以上かつＷ個未満である部分領域３０２０に挿入する。以下、格納されているエントリの個数が１個以上かつＷ個未満である部分領域３０２０を、不飽和領域と表記する。
【００２１】
ソート部２０４０は、新規エントリが挿入された部分領域３０２０に格納されているエントリの個数がＷ個である場合は、その部分領域３０２０に格納されているエントリをソートする。ここで、格納されているエントリの個数がＷ個である部分領域３０２０を、飽和領域と表記する。また、ソート部２０４０は、新規エントリが挿入された部分領域３０２０が飽和領域でない場合は、その部分領域３０２０に格納されているエントリをソートしない。
【００２２】
＜具体的な動作の説明＞
図２は、挿入部２０２０の動作を概念的に示す図である。図２において、エントリは、３４、５５等の数値である。また図２において、部分領域３０２０が格納できるエントリの個数を表すＷは４である。
【００２３】
図２（ａ）において、部分領域１及び２は飽和領域であり、部分領域３は不飽和領域である。図２（ａ）において、挿入部２０２０は、不飽和領域である部分領域３に新規エントリである１０を挿入する。この場合、新規エントリが挿入された部分領域３は、飽和領域となる。そこで、図２（ｂ）において、ソート部２０４０は、部分領域３をソートする。図２（ｂ）では例として、ソート部２０４０は、部分領域３を、エントリの数値の昇順にソートしている。ただし、ソート部２０４０が行うソートは、昇順に並び替えるソートに限られない。
【００２４】
図２（ｃ）において、部分領域１及び２は飽和領域であり、部分領域３は不飽和領域である。図２（ｃ）において、挿入部２０２０は、不飽和領域である部分領域３に新規エントリである１０を挿入する。しかしこの場合、新規エントリが挿入された部分領域３は、飽和領域にならない。したがって、図２（ｄ）において、ソート部２０４０は、部分領域３をソートしない。
【００２５】
＜ノード３０００の詳細＞
部分領域３０２０が格納するエントリは様々である。例えばエントリは、数値や文字を示すデータである。その他にも例えば、エントリは、数値や文字等を示すデータの組み合わせであってもよい。この場合、例えばエントリは、検索やソートに利用されるキーと、キーに対応する値の組み合わせである。
【００２６】
ノード３０００は、例えばインデックスツリーの構成要素であるノードである。この場合、ノード３０００に格納されるエントリは、例えばインデックスと、インデックスを付与されたデータの組み合わせである。
【００２７】
部分領域３０２０の実装方法は様々である。例えば部分領域３０２０は１次元配列として実装される。その他にも例えば、部分領域３０２０は、リスト構造などで実装されてもよい。
【００２８】
ノード３０００の実装方法は様々である。例えばノード３０００は、１次元配列として実装される。この場合、例えばノード３０００を実現する１次元配列の一部が、部分領域３０２０となる。その他にも例えば、ノード３０００は、部分領域３０２０を連結した２次元配列やリスト構造などで実装される。
【００２９】
＜エントリ挿入装置２０００のハードウエア構成＞
図３は、実施形態１に係るエントリ挿入装置２０００のハードウエア構成の一例を示すブロック図である。図３において、エントリ挿入装置２０００は、バス１０２０、ＣＰＵ１０４０、ＲＡＭ１０６０、及びストレージ１０８０を有する。
【００３０】
バス１０２０は、ＣＰＵ１０４０、ＲＡＭ１０６０、及びストレージ１０８０の各ハードウエア間で情報を送受信するための伝送経路である。
【００３１】
ＣＰＵ１０４０は、挿入部２０２０の機能を実現する挿入プログラム１１００を実行することで、挿入部２０２０の機能を実現する。また、ＣＰＵ１０４０は、ソート部２０４０の機能を実現するソートプログラム１１２０を実行することで、ソート部２０４０の機能を実現する。
【００３２】
挿入プログラム１１００及びソートプログラム１１２０は、例えばストレージ１０８０に格納されている。そして、挿入プログラム１１００及びソートプログラム１１２０は、ＣＰＵ１０４０によって、例えばＲＡＭ１０６０に読み出される。挿入プログラム１１００やソートプログラム１１２０は、ＲＡＭ１０６０に格納されていてもよい。また、エントリ挿入装置２０００がＲＯＭを有する場合、挿入プログラム１１００やソートプログラム１１２０はそのＲＯＭに格納されていてもよい。
【００３３】
ストレージ１０８０は、例えばハードディスク、ＵＳＢメモリ、又はＳＳＤ（Ｓｏｌｉｄ  Ｓｔａｔｅ  Ｄｒｉｖｅ）などの記憶装置である。また、ストレージ１０８０は、ＲＡＭやＲＯＭ等の記憶装置であってもよい。
【００３４】
＜エントリ挿入処理の流れ＞
図４は、本実施形態のエントリ挿入装置２０００が、ノード３０００にエントリを挿入するエントリ挿入処理の流れの一例を示すフローチャートである。
【００３５】
ステップＳ１０２において、挿入部２０２０は、不飽和領域である部分領域３０２０に、新規エントリを挿入する。
【００３６】
ステップＳ１０４において、ソート部２０４０は、新規エントリが挿入された部分領域３０２０が、飽和領域になったか否かを判定する。新規エントリが挿入された部分領域３０２０が飽和領域である場合、エントリ挿入処理は、ステップＳ１０６に進む。新規エントリが挿入された部分領域３０２０が飽和領域でない場合、エントリ挿入処理は終了する。
【００３７】
ステップＳ１０６において、ソート部２０４０は、新規エントリが挿入された部分領域３０２０に格納されているエントリをソートする。
【００３８】
＜作用・効果＞
以上により、本実施形態によれば、エントリ挿入装置２０００は、不飽和領域である部分領域３０２０に対して新規エントリを挿入する。そして、エントリ挿入装置２０００は、新規エントリが挿入された部分領域３０２０が飽和領域になった場合、新規エントリが挿入された部分領域３０２０をソートする。このように、エントリ挿入装置２０００は、新規エントリを挿入する度にエントリをソートしないため、エントリの挿入にかかる時間を短くすることができる。また、エントリ挿入装置２０００は、ＳＩＭＤ命令を効率的に利用できるため、ソートを短い時間で行うことができる。
【００３９】
また、エントリ数が、ＳＩＭＤ命令により一括処理できる数である飽和領域はソートされるため、ノード３０００からエントリを検索する装置は、ＳＩＭＤ命令を使って効率よくエントリの検索を行うことができる。
【００４０】
＜変形例１＞
実施形態１のエントリ挿入装置２０００のソート部２０４０は、ＳＩＭＤ命令を用いて飽和領域をソートする機能を有してもよい。以下、ソート部２０４０がＳＩＭＤ命令を用いて飽和領域をソートする機能を有するエントリ挿入装置２０００を、変形例１のエントリ挿入装置２０００と表記する。
【００４１】
例えば変形例１のソート部２０４０は、ＳＩＭＤ命令を用いて、ソートする飽和領域に格納されているエントリ同士を比較する。そして、この比較結果を利用して、飽和領域に格納されているエントリをソートする。
【００４２】
図５は、変形例１のソート部２０４０が、ＳＩＭＤ命令を用いてエントリ同士の比較を行う方法の一例を示した図である。まず、ソート部２０４０は、第１のレジスタに、飽和領域に格納されているエントリを格納する。そして、ソート部２０４０は、第１のレジスタに格納されているデータ列に含まれる１つ以上のデータを用いて、新たなデータ列を生成するＳＩＭＤ命令を実行する。これにより、ソート部２０４０は、データ列１を生成する。一般に、あるデータ列に含まれる１つ以上のデータを用いて、新たなデータ列を生成するＳＩＭＤ命令は、シャッフル命令と呼ばれる。
【００４３】
図５の例では、飽和領域に、「ａ、ｂ、ｃ、ｄ」というエントリが格納されている。そして、図５（ａ）において、ソート部２０４０は、上記シャッフル命令を利用して、「ｄ、ａ、ｂ、ｃ」という新たなデータ列１を生成している。
【００４４】
図５（ｂ）において、ソート部２０４０は、第２のレジスタに、新たに生成したデータ列１を格納する。そして、ソート部２０４０は、第１のレジスタに格納されている各データと、第２のレジスタに格納されている各データとを比較するＳＩＭＤ命令を実行する。ソート部２０４０は、このＳＩＭＤ命令により、エントリの各組み合わせのうち、「ａ、ｄ」、「ａ、ｂ」、「ｂ、ｃ」、及び「ｃ、ｄ」という、４つの組み合わせの比較を１つの命令で行うことができる。
【００４５】
ここで、エントリを４つ格納している飽和領域において、２つのエントリの組み合わせは６通りある。そのため、２つのエントリの組み合わせ全てについて比較を行うためには、６通りの比較が必要である。上述したように、ソート部２０４０は、比較を行うＳＩＭＤ命令を１回実行することで、４通りの比較を行うことができる。したがって、ソート部２０４０は、エントリを４つ格納している飽和領域について、比較を行うＳＩＭＤ命令を２回実行することで、２つのエントリの組み合わせ全てについて、比較を行うことができる。
【００４６】
ソート部２０４０は、ＳＩＭＤ命令を用いて飽和領域に格納されているエントリ同士を比較した結果を利用して、飽和領域に格納されているエントリをソートする。そのために例えば、ソート部２０４０は、飽和領域部に格納されているエントリ同士を比較した結果と、エントリのソート方法との対応付けを示す情報を記憶しておく。以下、この情報をソート情報と表記する。ソート部２０４０は、ＳＩＭＤ命令を使って飽和領域に格納されているエントリ同士を比較した結果に基づいて、ソート情報を読み出す。そして、ソート部２０４０は、ソート情報に示されている方法に従って、飽和領域に格納されているエントリを並べ替える。
【００４７】
ソート情報は、例えば図６に示すソートテーブル１００で表される。ソートテーブル１００は、比較結果１０２と、ソート方法１０４を有する。ここで、図６のソートテーブル１００は、飽和領域が有するエントリの個数が４であり、ソート前の飽和領域が、「ａ、ｂ、ｃ、ｄ」という４つのエントリをこの順番で有していることを仮定している。また、ソート方法１０４は、エントリを昇順に並び替える方法を示している。
【００４８】
例えば各エントリの比較結果が「ａ＞ｂ、かつａ＞ｃ、かつａ＞ｄ、かつｂ＞ｃ、かつｂ＞ｄ、かつｃ＜ｄ」ならば、「ａ、ｂ、ｃ、ｄ」の大小関係は、「ａ＞ｂ＞ｄ＞ｃ」であると一意に定まる。そこで、ソートテーブル１００は、レコード２において、「ａ＞ｂ、かつａ＞ｃ、かつａ＞ｄ、かつｂ＞ｃ、かつｂ＞ｄ、かつｃ＜ｄ」という比較結果１０２に対し、「ａ、ｂ、ｄ、ｃ」というソート方法１０４を対応づけている。
【００４９】
レコード２のソート方法１０４は、飽和領域に格納されている「ａ、ｂ、ｃ、ｄ」を、「ａ、ｂ、ｄ、ｃ」という順に並べ替えることで昇順にソートできることを示している。この場合、ソート部２０４０は、飽和領域に格納されているエントリのうち、ｃとｄを入れ替えることで、飽和領域を昇順にソートできる。
【００５０】
＜作用・効果＞
以上により、変形例１のエントリ挿入装置２０００は、ＳＩＭＤ命令を使って、飽和領域をソートする。こうすることで、エントリ挿入装置２０００は、短い時間で飽和領域をソートすることができる。
【００５１】
＜変形例２＞
実施形態１のエントリ挿入装置２０００のソート部２０４０は、個々にソートされている複数の飽和領域を連結した領域を、さらにソートする機能を有してもよい。ソート部２０４０が、複数の飽和領域を連結した領域をソートする機能を有するエントリ挿入装置２０００を、変形例２のエントリ挿入装置２０００と表記する。
【００５２】
例えば、ノード３０００が、２つの飽和領域１及び２を有しているとする。そして、飽和領域１は、「３５、５５、６１、９６」という順にエントリを有しており、飽和領域２は、「１０、２３、５８、７５」という順にエントリを有しているとする。
【００５３】
この場合は、ソート部２０４０は、この２つの飽和領域を連結した領域である「３５、５５、６１、９６、１０、２３、５８、７５」という領域をソートする。例えば、ソート部２０４０は、エントリを昇順にソートするとする。この場合、上記連結した領域に格納されているエントリは、「１０、２３、３５、５５、５８、６１、７５、９６」という順になる。この結果、飽和領域１は、「１０、２３、３５、５５」という順にエントリを有する飽和領域となり、飽和領域２は、「５８、６１、７５、９６」という順にエントリを有する飽和領域となる。
【００５４】
＜作用・効果＞
以上により、変形例２のエントリ挿入装置２０００は、個々にソートされている複数の飽和領域を連結した領域を、さらにソートする。こうすることで、エントリ挿入装置２０００は、ノード３０００に格納されているエントリの検索にかかる時間を短くすることができる。
【００５５】
例えば、ノード３０００からエントリを検索する装置（以下、検索装置）が、上述した２つの飽和領域１及び２を有するノード３０００から、最大のエントリを検索する場合を考える。まず、エントリ挿入装置２０００が飽和領域１及び２を連結してソートしない場合を考える。この場合、検索装置はまず、飽和領域１の末尾に格納されている９６と、飽和領域２の末尾に格納されている７５とをそれぞれ取得する。その後、検索装置は、この２つのエントリを比較することで、９６が最大のエントリであることを割り出す。
【００５６】
一方、変形例２のエントリ挿入装置２０００により、上記飽和領域１と飽和領域２を連結した領域が予めソートされていたとする。この場合、検索装置は、飽和領域１と２からそれぞれ最大のエントリを取り出さなくても、飽和領域２の末尾のエントリである９６が最大のエントリであると分かる。このように、変形例２のエントリ挿入装置２０００により、複数の飽和領域を連結した領域をソートすることで、ノード３０００に格納されているエントリの検索にかかる時間を短くできる。
【００５７】
＜変形例３＞
さらに、変形例２のエントリ挿入装置２０００のソート部２０４０は、個々にソートされている複数の飽和領域について、複数の飽和領域を連結した領域を、ＳＩＭＤ命令を用いてソートする機能を有してもよい。ソート部２０４０が、ＳＩＭＤ命令を使って、複数の飽和領域を連結した領域をソートする機能を有するエントリ挿入装置２０００を、変形例３のエントリ挿入装置２０００と表記する。この場合、ソート部２０４０は、各飽和領域間でエントリを比較し、エントリを比較した結果に基づいて、複数の飽和領域を連結した領域をソートする。なお、ソート部２０４０が連結してソートする飽和領域の個数は、２のべき乗の倍数であることが好ましい。
【００５８】
例えば、ソート部２０４０が、「ａ、ｂ、ｃ、ｄ」という、昇順にソートされたエントリを有する飽和領域１と、「ｅ、ｆ、ｇ、ｈ」という、昇順にソートされたエントリを有する飽和領域２を連結した領域をソートするとする。この場合、例えばソート部２０４０は、ＳＩＭＤ命令を用いて、飽和領域１の中の１つのエントリと、飽和領域２の中の１つのエントリとの各組み合わせにおける比較を行う。そして、ソート部２０４０は、飽和領域１と飽和領域２のエントリを比較した結果に基づいて、２つの飽和領域を連結した領域をソートする。
【００５９】
本変形例のソート部２０４０は、例えば変形例１のソート部２０４０と同様の方法で、ＳＩＭＤ命令を用いた２つのエントリの比較を行う。また、本変形例のソート部２０４０は、例えば変形例１のソート部２０４０と同様に、エントリ同士の比較結果に基づいてソート情報を読み出すことでソートを行う。
【００６０】
ソート部２０４０は、各飽和領域に格納されているエントリをそれぞれソートしてから、複数の飽和領域を連結した領域に含まれるエントリをソートすることで、飽和領域を連結した領域に含まれるエントリのソートに必要な処理を少なくすることができる。例えば、上述の飽和領域１と２は、それぞれ予め昇順にソートされている。そのため、「ａ＜ｂ＜ｃ＜ｄ」、及び「ｅ＜ｆ＜ｇ＜ｈ」という大小関係が成り立っている。この場合、例えば、「ｄ＜ｅ」ならば必ず「ｃ＜ｅ」という大小関係が成り立つ。したがって、飽和領域を連結した領域に格納されているエントリをソートする際に、ソート部２０４０が行う必要があるエントリ同士の比較の回数は少なくなる。また、ソート情報に格納する比較結果のパターンが少なくなるため、ソート情報を小さくすることができる。
【００６１】
＜作用・効果＞
以上により、変形例３のエントリ挿入装置２０００は、ＳＩＭＤ命令を用いて、個々にソートされている複数の飽和領域を連結した領域に格納されているエントリをソートすることで、複数の飽和領域を連結した領域に格納されているエントリを短い時間でソートすることができる。
【００６２】
[実施形態２]
図７は、本実施形態に係るエントリ挿入装置２０００を、その使用環境と共に示すブロック図である。図７に示す機能構成部のうち、図１に同符号の機能構成部があるものは、図１に示す同符号の機能構成部と同じ機能を有するとする。また、図７において、各機能構成部は、ハードウエア単位の構成ではなく、機能単位の構成を示している。
【００６３】
本実施形態のエントリ挿入装置２０００は、検索部２０８０をさらに有する。検索部２０８０は、ノード３０００からエントリを検索する。その際、検索部２０８０は、飽和領域に対する検索と、不飽和領域に対する検索を異なる方法で行う。
【００６４】
＜具体的な動作の説明＞
ここで、具体例を用いて、エントリ挿入装置２０００の動作を概念的に説明する。本例において、検索部２０８０は、ノード３０００から、６０より大きいエントリを検索する。
【００６５】
図８は、検索部２０８０が飽和領域に対して行う検索の動作を概念的に示す図である。図８において、検索部２０８０は、２つのレジスタに格納されている値を比較して結果を出力するＳＩＭＤ命令を利用する。具体的にはまず、第１のレジスタに飽和領域のエントリを投入する。そして、第２のレジスタに検索条件を表す値を投入する。そして、「第１のレジスタに投入されている各値を、第２のレジスタにおいて同じ位置に投入されている値と比較し、第１のレジスタに投入されている値の方が大きければ１、そうでなければ０を出力する」というＳＩＭＤ命令を実行する。
【００６６】
ＳＩＭＤ命令を用いた比較の結果、３４については０を、６１、７５、及び９６については１が出力される。そして検索部２０８０は、出力結果が１である「６１、７５、９６」という３つのエントリを、検索条件を満たすエントリとして抽出する。このようにすることで、検索部２０８０は、飽和領域に格納されているエントリの中から、「６０より大きい」という検索条件を満たすエントリを、一度のＳＩＭＤ命令で抽出する。
【００６７】
一方検索部２０８０は、不飽和領域に対しては、例えばＳＩＭＤ命令を使わずに検索を行う。この場合、例えば検索部２０８０は、一度に１つのデータを扱うＳＩＳＤ（Ｓｉｎｇｌｅ  Ｉｎｓｔｒｕｃｔｉｏｎ  Ｓｉｎｇｌｅ  Ｄａｔａ）命令を使い、各エントリと、検索条件の表す６０との比較を個別に行う。
【００６８】
そして、検索部２０８０は、飽和領域に対する検索で抽出したエントリと、不飽和領域に対する検索で抽出したエントリとを合わせて検索結果とする。
【００６９】
＜作用・効果＞
以上により、本実施形態によれば、エントリ挿入装置２０００は、飽和領域に対する検索と、不飽和領域に対する検索を異なる方法で行うことで、ノード３０００に対するエントリの検索を行う。こうすることで、エントリ挿入装置２０００は、飽和領域に対しては飽和領域に適した方法で検索を行い、不飽和領域に対しては不飽和領域に適した方法で検索を行うことができる。これにより、エントリ挿入装置２０００は、飽和領域と不飽和領域に対して同じ方法で検索を行う場合と比較し、検索にかかる時間を短くすることができる。
【００７０】
例えば検索部２０８０は、飽和領域に対し、ＳＩＭＤ命令を使って検索を行う。一方、例えば検索部２０８０は、不飽和領域に対し、ＳＩＳＤ命令を使って検索を行う。一般に、ＳＩＭＤ命令は、ＳＩＳＤ命令と比較して、処理時間が長い。そのため、処理したいエントリの数が少ない場合は、ＳＩＳＤ命令を使って個別に処理を行った方が、ＳＩＭＤ命令を使ってまとめて処理を行うよりも、処理時間の合計が短い場合がある。そこで、検索部２０８０は、不飽和領域に対しては、例えばＳＩＳＤ命令を用いて検索を行う。
【００７１】
＜変形例４＞
本実施形態のエントリ挿入装置２０００には、例えば次に示す変形例がある。ここで、次に示す本実施形態のエントリ挿入装置２０００の変形例を、変形例４のエントリ挿入装置２０００と表記する。
【００７２】
変形例４のエントリ挿入装置２０００の検索部２０８０は、飽和領域の中にある、所定の条件を満たす複数のエントリの中から、各エントリが格納されている位置に基づいて、最大の値を示すエントリ又は最小の値を示すエントリを特定する。
【００７３】
ここで、各エントリが格納されている位置とは、エントリが格納されている記憶装置等のハードウエア上における物理的な位置に限定されない。例えば、部分領域３０２０が１次元配列で実現されている場合、エントリの位置は、例えば配列の添え字で表される。
【００７４】
＜具体的な動作の説明＞
図８を用いた上述の例で、変形例４の検索部２０８０の動作を説明する。前述した通り、図８に示す飽和領域に含まれるエントリのうち、図８が示す「エントリが６０より大きい」という所定の条件を満たすエントリは、「６１、７５、９６」の３つである。
【００７５】
変形例４の検索部２０８０が、「６１、７５、９６」という３つのエントリから、最大の値を示すエントリを特定する方法を説明する。ここで、図８における飽和領域は、値の昇順にソートされている。したがって、上記飽和領域に格納されているエントリは、後ろの位置に格納されているエントリほど大きい値を示す。したがって、検索部２０８０は、所定の条件を満たすエントリのうち、最も後ろの位置に格納されている９６が、最大の値を示すエントリであると特定することができる。
【００７６】
次に、変形例４の検索部２０８０が、上記３つのエントリから、最小の値を示すエントリを特定する方法を説明する。上述したように、図８に示す飽和領域は、値の昇順にソートされている。したがって、上記飽和領域に格納されているエントリは、前の位置に格納されているエントリほど小さい値を示す。したがって、検索部２０８０は、最も前の位置に格納されている６１が、最小の値を示すエントリであると特定することができる。
【００７７】
＜作用・効果＞
変形例４のエントリ挿入装置２０００において、検索部２０８０は、飽和領域の中にある、所定の条件を満たす複数のエントリの中から、最大の値を示すエントリ又は最小の値を示すエントリを特定する。この際、エントリ挿入装置２０００は、所定の条件を満たす各エントリが格納されている位置に基づいて、最大の値又は最小の値を示すエントリを特定する。そのため、エントリ挿入装置２０００は、所定の条件を満たす各エントリの比較は行わない。これにより、エントリ挿入装置２０００は、飽和領域の中にある、所定の条件を満たす複数のエントリから、最大の値を示すエントリ又は最小の値を示すエントリを特定する処理にかかる時間を短くすることができる。
【００７８】
[実施形態３]
図９は、本実施形態に係るエントリ挿入装置２０００を、その使用環境と共に示すブロック図である。図９に示す機能構成部のうち、図１に同符号の機能構成部があるものは、図１に示す同符号の機能構成部と同じ機能を有するとする。また、図９において、各機能構成部は、ハードウエア単位の構成ではなく、機能単位の構成を示している。
【００７９】
本実施形態のエントリ挿入装置２０００は、削除部２０６０をさらに有する。削除部２０６０は、飽和領域に格納されている削除対象のエントリを、不飽和領域に格納されているいずれかのエントリで上書きする。これにより、検索部２０８０は、削除対象のエントリを削除する。
【００８０】
＜具体的な動作の説明＞
図１０は、削除部２０６０の動作を概念的に示す図である。図１０において、部分領域１は飽和領域であり、部分領域２は不飽和領域である。図１０において、部分領域１に格納されている５８というエントリが、削除対象のエントリであるとする。図１０（ａ）は、削除部２０６０が削除対象のエントリを削除する前のノード３０００を示す図である。
【００８１】
図１０（ｂ）は、削除部２０６０が削除対象のエントリを削除する動作を示す図である。削除部２０６０は、不飽和領域である部分領域２に格納されている５３というエントリで、削除対象のエントリを上書きする。
【００８２】
＜作用・効果＞
以上により、本実施形態によれば、エントリ挿入装置２０００は、飽和領域に格納されている削除対象のエントリを削除する際、不飽和領域に格納されているエントリで上書きして削除する。これにより、削除対象のエントリが格納されていた飽和領域は、そのエントリを削除した後も、飽和領域のままとなる。したがって、エントリ挿入装置２０００は、エントリが削除された場合に、飽和領域が不飽和領域になることを防ぐことができる。こうすることで、エントリ挿入装置２０００は、ノード３０００に格納されているエントリの検索にかかる時間が長くなることを防ぐことができる。
【００８３】
[実施形態４]
図１１は、本実施形態に係るエントリ挿入装置２０００を、その使用環境と共に示すブロック図である。図１１に示す機能構成部のうち、図９に同符号の機能構成部があるものは、図９に示す同符号の機能構成部と同じ機能を有するとする。また、図１１において、各機能構成部は、ハードウエア単位の構成ではなく、機能単位の構成を示している。
【００８４】
本実施形態のエントリ挿入装置２０００は、分割部２０７０を有する。分割部２０７０は、削除部２０６０に、各部分領域３０２０から、所定の条件を満たすエントリを削除させる。また、分割部２０７０は、エントリが削除された部分領域３０２０が飽和領域である場合、ソート部２０４０に、その部分領域３０２０をソートさせる。こうすることで、分割部２０７０は、ノード３０００を分割する。
【００８５】
分割部２０７０がソート部２０４０に飽和領域をソートさせるタイミングは様々である。例えば分割部２０７０は、１つの部分領域３０２０についてエントリの削除を全て終えた後、その部分領域３０２０が飽和領域である場合に、その部分領域３０２０をソート部２０４０にソートさせる。その他にも例えば分割部２０７０は、全ての部分領域３０２０についてエントリの削除を全て終えた後、各飽和領域をソート部２０４０にソートさせてもよい。
【００８６】
削除部２０６０が不飽和領域に格納されている削除対象のエントリを削除する場合、例えば削除部２０６０は、削除対象のエントリを消去する。
【００８７】
エントリ挿入装置２０００は、例えば所定の条件を満たすエントリを、他のノード３０００に移動する。これにより、元のノード３０００には、所定の条件を満たさないノードのみが残る。例えば、エントリ挿入装置２０００は、新規のノード３０００を用意し、所定の条件を満たすエントリを、新規のノード３０００へ移動する。こうすることで、エントリ挿入装置２０００は、所定の条件を満たすエントリと、所定の条件を満たさないエントリとを、別々のノード３０００に分けることができる。また、エントリ挿入装置２０００は、所定の条件を満たすエントリを、他のノード３０００に移動しなくてもよい。
【００８８】
＜分割処理の流れ＞
図１２は、分割部２０７０が行う分割処理の流れの一例を示すフローチャートである。
【００８９】
ステップＳ２０２〜ステップＳ２１６は、ノード３０００に含まれる各部分領域３０２０について行うループ処理Ａである。ステップＳ２０２において、分割部２０７０は、ノード３０００に含まれる全ての部分領域３０２０を対象にループ処理Ａを行ったか否かを判定する。すでに、ノード３０００に含まれる全ての部分領域３０２０を対象にループ処理Ａを行った場合、分割処理は終了する。
【００９０】
一方、ノード３０００の中に、まだループ処理Ａの対象としていない部分領域３０２０がある場合、分割部２０７０は、まだループ処理Ａの対象としていない部分領域３０２０から１つを選択する。以下、ステップＳ２０２で選択された部分領域３０２０を、部分領域ｉと表記する。そして、分割処理はステップＳ２０４に進む。
【００９１】
ステップＳ２０４〜ステップＳ２１０は、部分領域ｉに格納されている各エントリについて行うループ処理Ｂである。ステップＳ２０４において、分割部２０７０は、部分領域ｉに格納されている全てのエントリを対象にループ処理Ｂを行ったか否かを判定する。すでに、部分領域ｉに格納されている全てのエントリを対象にループ処理Ｂを行った場合、分割処理はステップＳ２１２に進む。
【００９２】
一方、部分領域ｉの中に、まだループ処理Ｂの対象としていないエントリがある場合、分割部２０７０は、まだループ処理Ａの対象としていないエントリから１つを選択する。以下、ステップＳ２０４で選択されたエントリを、エントリｊと表記する。そして、分割処理はステップＳ２０６に進む。
【００９３】
ステップＳ２０６において、分割部２０７０は、エントリｊが、所定の条件を満たすか否かを判定する。エントリｊが所定の条件を満たす場合、分割処理は、ステップＳ２０８に進む。エントリｊが所定の条件を満たさない場合、分割処理は、ステップＳ２１０に進む。
【００９４】
ステップＳ２０８において、削除部２０６０は、エントリｊを削除する。
【００９５】
ステップＳ２１０は、ループ処理Ｂの終端である。分割処理は、ステップＳ２０４に戻る。
【００９６】
ステップＳ２１２において、分割部２０７０は、部分領域ｉが飽和領域であるか否かを判定する。部分領域ｉが飽和領域である場合、分割処理は、ステップＳ２１４に進む。一方、部分領域ｉが飽和領域でない場合、分割処理は、ステップＳ２１６に進む。
【００９７】
ステップＳ２１４において、ソート部２０４０は、部分領域ｉをソートする。
【００９８】
ステップＳ２１６は、ループ処理Ａの終端である。分割処理は、ステップＳ２０２に戻る。
【００９９】
＜作用・効果＞
以上の構成により、本実施形態によれば、エントリ挿入装置２０００は、削除部２０６０により、各部分領域３０２０から、所定の条件を満たすエントリを削除する。削除部２０６０によってエントリを削除することで、エントリ挿入装置２０００は、エントリを削除した後に飽和領域が不飽和領域になることを防ぐ。
【０１００】
また、エントリが削除された部分領域３０２０が飽和領域である場合、エントリ挿入装置２０００は、ソート部２０４０により、エントリが削除された部分領域３０２０をソートする。こうすることで、エントリ挿入装置２０００は、飽和領域がソートされた状態を保つ。
【０１０１】
以上のようにすることで、エントリ挿入装置２０００は、ノード３０００を分割した後に、ノード３０００からエントリを検索する時間が長くなることを防ぐことができる。
【０１０２】
以上、図面を参照して本発明の実施形態について述べたが、これらは本発明の例示であり、上記実施形態の組み合わせ、及び上記実施形態以外の様々な構成を採用することもできる。
【０１０３】
以下、参考形態の例を付記する。
１．  格納できるエントリの個数がそれぞれＷ個（Ｗは２以上の正の整数）である複数の部分領域を含み、なおかつ、Ｗ個のエントリに対して並行に同一処理を実行するＳＩＭＤ（Ｓｉｎｇｌｅ  Ｉｎｓｔｒｕｃｔｉｏｎ  Ｍｕｌｔｉｐｌｅ  Ｄａｔａ）命令を利用することで、前記複数の部分領域に格納されているエントリを検索できるノードに対し、エントリを挿入するエントリ挿入装置であって、
新規エントリを、前記複数の部分領域のうち、格納されているエントリの個数が１以上かつＷ個未満である不飽和領域に対して挿入する挿入手段と、
前記新規エントリが挿入された部分領域が、格納されているエントリの個数がＷ個である飽和領域である場合は、該部分領域に格納されているエントリをソートし、
前記新規エントリが挿入された部分領域が、前記飽和領域でない場合は、該部分領域に格納されているエントリをソートしないソート手段と、
を有するエントリ挿入装置。
２．  前記ソート手段は、前記ＳＩＭＤ命令を用いて前記飽和領域をソートする１．に記載のエントリ挿入装置。
３．  前記ソート手段は、個々にソートされている複数の前記飽和領域を連結した領域をソートする１．又は２．に記載のエントリ挿入装置。
４．  前記ソート手段は、個々にソートされている複数の前記飽和領域について、前記ＳＩＭＤ命令を用いて各飽和領域間でエントリを比較し、エントリを比較した結果に基づいて、該複数の飽和領域を連結した領域をソートする３．に記載のエントリ挿入装置。
５．  前記飽和領域からエントリを検索する場合と、前記不飽和領域からエントリを検索する場合とで、異なった方法で検索を行う検索手段をさらに有する１．乃至４．いずれか１つに記載のエントリ挿入装置。
６．  前記検索手段は、前記飽和領域の中にある、所定の条件を満たす複数のエントリの中から、該複数のエントリそれぞれが格納されている位置に基づいて、最大の値を示すエントリ又は最小の値を示すエントリを特定する５．に記載のエントリ挿入装置。
７．  前記飽和領域に格納されている削除対象のエントリを、前記不飽和領域に格納されているエントリで上書きして削除する削除手段を有する１．乃至６．いずれか１つに記載のエントリ挿入装置。
８．  前記削除手段に、各部分領域から、所定の条件を満たすエントリを削除させ、エントリが削除された部分領域が前記飽和領域である場合、前記ソート手段に、該部分領域をソートさせる分割手段を有する７．に記載のエントリ挿入装置。
９．  コンピュータを、格納できるエントリの個数がそれぞれＷ個（Ｗは２以上の正の整数）である複数の部分領域を含み、なおかつ、Ｗ個のエントリに対して並行に同一処理を実行するＳＩＭＤ（Ｓｉｎｇｌｅ  Ｉｎｓｔｒｕｃｔｉｏｎ  Ｍｕｌｔｉｐｌｅ  Ｄａｔａ）命令を利用することで、前記複数の部分領域に格納されているエントリを検索できるノードに対し、エントリを挿入するエントリ挿入装置として機能させるプログラムであって、前記コンピュータに、
新規エントリを、前記複数の部分領域のうち、格納されているエントリの個数が１以上かつＷ個未満である不飽和領域に対して挿入する挿入機能と、
前記新規エントリが挿入された部分領域が、格納されているエントリの個数がＷ個である飽和領域である場合は、該部分領域に格納されているエントリをソートし、
前記新規エントリが挿入された部分領域が、前記飽和領域でない場合は、該部分領域に格納されているエントリをソートしないソート機能と、
を持たせるプログラム。
１０．  前記ソート機能は、前記ＳＩＭＤ命令を用いて前記飽和領域をソートする９．に記載のプログラム。
１１．  前記ソート機能は、個々にソートされている複数の前記飽和領域を連結した領域をソートする９．又は１０．に記載のプログラム。
１２．  前記ソート機能は、個々にソートされている複数の前記飽和領域について、前記ＳＩＭＤ命令を用いて各飽和領域間でエントリを比較し、エントリを比較した結果に基づいて、該複数の飽和領域を連結した領域をソートする１１．に記載のプログラム。
１３．  前記コンピュータに、前記飽和領域からエントリを検索する場合と、前記不飽和領域からエントリを検索する場合とで、異なった方法で検索を行う検索機能をさらに持たせる９．乃至１２．いずれか１つに記載のプログラム。
１４．  前記検索機能は、前記飽和領域の中にある、所定の条件を満たす複数のエントリの中から、該複数のエントリそれぞれが格納されている位置に基づいて、最大の値を示すエントリ又は最小の値を示すエントリを特定する１３．に記載のプログラム。
１５．  前記コンピュータに、前記飽和領域に格納されている削除対象のエントリを、前記不飽和領域に格納されているエントリで上書きして削除する削除機能を持たせる９．乃至１４．いずれか１つに記載のプログラム。
１６．  前記コンピュータに、前記削除機能に、各部分領域から、所定の条件を満たすエントリを削除させ、エントリが削除された部分領域が前記飽和領域である場合、前記ソート機能に、該部分領域をソートさせる分割機能を持たせる１５．に記載のプログラム。
１７．  格納できるエントリの個数がそれぞれＷ個（Ｗは２以上の正の整数）である複数の部分領域を含み、なおかつ、Ｗ個のエントリに対して並行に同一処理を実行するＳＩＭＤ（Ｓｉｎｇｌｅ  Ｉｎｓｔｒｕｃｔｉｏｎ  Ｍｕｌｔｉｐｌｅ  Ｄａｔａ）命令を利用することで、前記複数の部分領域に格納されているエントリを検索できるノードに対し、エントリを挿入するコンピュータによって実行される方法であって、
新規エントリを、前記複数の部分領域のうち、格納されているエントリの個数が１以上かつＷ個未満である不飽和領域に対して挿入する挿入ステップと、
前記新規エントリが挿入された部分領域が、格納されているエントリの個数がＷ個である飽和領域である場合は、該部分領域に格納されているエントリをソートし、前記新規エントリが挿入された部分領域が、前記飽和領域でない場合は、該部分領域に格納されているエントリをソートしないソートステップと、
を有する方法。
１８．  前記ソートステップは、前記ＳＩＭＤ命令を用いて前記飽和領域をソートする１７．に記載の方法。
１９．  前記ソートステップは、個々にソートされている複数の前記飽和領域を連結した領域をソートする１７．又は１８．に記載の方法。
２０．  前記ソートステップは、個々にソートされている複数の前記飽和領域について、前記ＳＩＭＤ命令を用いて各飽和領域間でエントリを比較し、エントリを比較した結果に基づいて、該複数の飽和領域を連結した領域をソートする１９．に記載の方法。
２１．  前記飽和領域からエントリを検索する場合と、前記不飽和領域からエントリを検索する場合とで、異なった方法で検索を行う検索ステップをさらに有する１７．乃至２０．いずれか１つに記載の方法。
２２．  前記検索ステップは、前記飽和領域の中にある、所定の条件を満たす複数のエントリの中から、該複数のエントリそれぞれが格納されている位置に基づいて、最大の値を示すエントリ又は最小の値を示すエントリを特定する２１．に記載の方法。
２３．  前記飽和領域に格納されている削除対象のエントリを、前記不飽和領域に格納されているエントリで上書きして削除する削除ステップを有する１７．乃至２２．いずれか１つに記載の方法。
２４．  前記削除ステップに、各部分領域から、所定の条件を満たすエントリを削除させ、エントリが削除された部分領域が前記飽和領域である場合、前記ソートステップに、該部分領域をソートさせる分割ステップを有する２３．に記載の方法。
【０１０４】
この出願は、２０１２年１０月１６日に出願された日本出願特願２０１２−２２９０６０号を基礎とする優先権を主張し、その開示の全てをここに取り込む。
【図１】
2014061305.tif 000003
【図２】
2014061305.tif 000004
【図３】
2014061305.tif 000005
【図４】
2014061305.tif 000006
【図５】
2014061305.tif 000007
【図６】
2014061305.tif 000008
【図７】
2014061305.tif 000009
【図８】
2014061305.tif 000010
【図９】
2014061305.tif 000011
【図１０】
2014061305.tif 000012
【図１１】
2014061305.tif 000013
【図１２】
2014061305.tif 000014
【国際調査報告】
2014061305.tif 000015
2014061305.tif 000016