(57)【要約】【課題】本発明によれば、インデックスツリーを用いたレコードの検索及び挿入にかかる時間を短くする技術が提供される。【解決手段】エントリ２００は、ノード１００に含まれており、インデックス情報２２０を固有に示す。インデックス情報２２０は、そのインデックス情報２２０に対応する全体キー４１２のうち、１つ前のエントリ２００に対応する全体キー４１２との差分である部分キー２２２を有する。部分キー２２２が第１サイズより大きい場合、インデックス情報２２０はエントリ２００の外部に格納され、それ以外の場合、インデックス情報２２０はエントリ２００の内部に格納される。エントリ処理装置２０００は、エントリ２００からインデックス情報２２０がエントリ２００の内部と外部のどちらに格納されているかを判別するための領域識別情報２１０を取得し、取得した情報に応じてエントリ２００の内部又は外部からインデックス情報２２０を取得する。【選択図】図１
2014235450.tif 000002
【特許請求の範囲】
【請求項１】
検索対象のレコードのインデックス情報が格納されているインデックスツリーについて、そのインデックスツリーを構成するノードに格納されているエントリを処理するエントリ処理装置であって、
前記ノードは、前記インデックス情報を固有に示す前記エントリを、順位付けて格納しており、
前記インデックス情報は、
前記レコードを識別する値列である全体キーの一部を表す値列である部分キーと、その全体キーにおけるその部分キーの開始位置である開始オフセットとを有し、
そのインデックス情報を示す前記エントリの内部に格納されているか、又はそのエントリの外部にある外部領域に格納されており、
前記エントリは、
前記エントリの内部に格納されている場合、前記部分キーのサイズは所定の第１サイズであり、
前記インデックス情報が前記エントリの内部と外部のどちらに格納しているかを判別する領域識別情報を格納しており、
前記インデックス情報が前記外部領域に格納されている場合、そのインデックス情報へのポインタを格納しており、
前記インデックス情報が有する前記開始オフセットは、そのインデックス情報が有する前記部分キーの元である前記全体キーと、前記ノード内においてそのインデックス情報を示す前記エントリより順位が１つ前の前記エントリによって示される前記インデックス情報が有する前記部分キーの元である前記全体キーとの間において、同一位置における値が異なる最前の位置を示し、
前記ノードを格納する領域及び前記外部領域は、前記全体キーを含む前記レコードを格納する格納手段とは異なる格納手段に設けられており、
当該エントリ処理装置は、
前記領域識別情報を取得する領域識別情報取得手段と、
前記領域識別情報により、前記インデックス情報が前記エントリの内部に格納されていることが示されている場合、前記エントリから前記インデックス情報を取得し、前記領域識別情報により、前記インデックス情報が前記外部領域に格納されていることが示されている場合、そのエントリに格納されている前記ポインタによって示されている前記インデックス情報を取得するインデックス情報取得手段と、
を有するエントリ処理装置。
【請求項２】
検索対象の前記全体キーである検索キーを取得する検索キー取得手段と、
同一の前記ノードに含まれる前記エントリが示す前記インデックス情報の中から、前記部分キーが前記検索キー以下である前記インデックス情報のうち、前記部分キーが最大である前記インデックス情報を特定するインデックス情報特定手段と、
を有する請求項１に記載のエントリ処理装置。
【請求項３】
前記インデックス情報を取得し、そのインデックス情報が有する前記部分キーの大きさが前記第１サイズ以下である場合、そのインデックス情報を、生成する前記エントリの内部に格納し、そのインデックス情報が有する前記部分キーの大きさが前記第１サイズより大きい場合、そのインデックス情報を前記外部領域に格納した上で、その外部領域へのポインタを、生成する前記エントリの内部に格納するエントリ生成手段を有する請求項２に記載のエントリ処理装置。
【請求項４】
前記ノードに挿入する挿入エントリに対応付ける全体キーである挿入キーを取得する挿入キー取得手段と、
前記ノードにおいて前記挿入エントリを挿入する挿入順位を算出する挿入順位算出手段と、
前記挿入キーと、前記挿入順位より１つ前の順位にある直前エントリによって示される前記インデックス情報とを比較することで、前記直前エントリに対応する前記全体キーと前記挿入キーとの間において、同一位置における値が異なる最前の位置である第１最前位置を算出する第１最前位置算出手段と、
前記挿入キーと、前記挿入順位より１つ後の順位にある直後エントリによって示される前記インデックス情報とを比較することで、前記直後エントリに対応する前記全体キーと前記挿入キーとの間において、同一位置における値が異なる最前の位置である第２最前位置を算出する第２最前位置算出手段と、
前記挿入エントリが示す前記インデックス情報の前記部分キーに、前記挿入キーに含まれる値列であり、開始位置が、前記第１最前位置であり、終了位置が、前記第２最前位置と、前記第１最前位置に前記第１サイズを足した値から１を引いた値とのうち、大きい方の値である値列を設定し、前記挿入エントリが示す前記インデックス情報の前記開始オフセットに前記第１最前位置を設定するインデックス情報生成手段と、を有し、
前記エントリ生成手段は、前記インデックス情報生成手段によって生成された前記インデックス情報を取得する、
請求項３に記載のエントリ処理装置。
【請求項５】
前記第１最前位置算出手段は、前記直前エントリによって示される前記インデックス情報が有する前記部分キーと、前記挿入キーのうち、前記直前エントリによって示される前記インデックス情報が有する前記開始オフセットが開始位置であり、前記部分キーと同一のサイズである値列とを比較し、この２つが等しい場合、前記部分キーの元となる前記全体キーを取得し、取得した前記全体キーと前記挿入キーとを比較することで前記第１最前位置を算出し、
前記第２最前位置算出手段は、前記直後エントリによって示される前記インデックス情報が有する前記部分キーと、前記挿入キーのうち、前記直後エントリによって示される前記インデックス情報が有する前記開始オフセットが開始位置であり、前記部分キーと同一のサイズである値列とを比較し、この２つが等しい場合、前記部分キーの元となる前記全体キーを取得し、取得した前記全体キーと前記挿入キーとを比較することで前記第２最前位置を算出し、
前記第１最前位置算出手段及び前記第２最前位置算出手段は、前記エントリに対応する前記全体キーを取得する場合、前記インデックスツリーを、そのエントリを含む前記ノードを始点として下位に辿ることで取得する請求項４に記載のエントリ処理装置。
【請求項６】
前記第１最前位置と、前記直前エントリよって示される前記インデックス情報が有する前記開始オフセットとの差に１を加算した値が、そのインデックス情報が有する前記部分キーのサイズより大きい場合、その部分キーを、前記直前エントリに対応する前記全体キーのうち、開始位置が、更新前の前記直前エントリよって示される前記インデックス情報が有する前記開始オフセットであり、終了位置が、前記第１最前位置である値列に更新する直前エントリ更新手段と、
前記直後エントリによって示される前記インデックス情報の前記部分キーのサイズが前記第１サイズより大きく、かつ前記第２最前位置と前記直後エントリによって示される前記インデックス情報が有する前記開始オフセットとの差に１を加算した値が、そのインデックス情報が有する前記部分キーのサイズより小さい場合、その部分キーを、前記直後エントリに対応する前記全体キーのうち、開始位置が、更新前の前記直後エントリによって示される前記インデックス情報が有する前記開始オフセットであり、終了位置が、前記第２最前位置である値列に更新する直後エントリ更新手段と、を有し、
前記直前エントリ更新手段は、更新前の前記部分キーのサイズが前記第１サイズ以下であり、かつ更新後の前記部分キーのサイズが前記第１サイズより大きい場合、インデックス情報更新する前記インデックス情報を前記外部領域に格納した上で、そのインデックス情報を示す前記直前エントリの内部に、そのインデックス情報へのポインタを格納し、
前記直後エントリ更新手段は、更新前の前記部分キーのサイズが前記第１サイズより大きく、かつ更新後の前記部分キーのサイズが前記第１サイズ以下である場合、更新する前記インデックス情報を、そのインデックス情報を示す前記直後エントリの内部に格納する、
請求項４又は５に記載のエントリ処理装置。
【請求項７】
前記ノードを分割する順位である分割順位を取得する分割順位取得手段と、
前記分割順位を基準として、前記ノードを２つに分割する分割手段と、
前記分割順位にある前記エントリが示す前記インデックス情報と前記挿入キーとを比較することで、２つに分割された前記ノードのどちらに前記挿入エントリを挿入するかを決定する挿入ノード決定手段と、
を有する請求項４乃至６いずれか一項に記載のエントリ処理装置。
【請求項８】
コンピュータによって実行される制御方法であり、検索対象のレコードのインデックス情報が格納されているインデックスツリーについて、そのインデックスツリーを構成するノードに格納されているエントリを処理する制御方法であって、
前記ノードは、前記インデックス情報を固有に示す前記エントリを、順位付けて格納しており、
前記インデックス情報は、
前記レコードを識別する値列である全体キーの一部を表す値列である部分キーと、その全体キーにおけるその部分キーの開始位置である開始オフセットとを有し、
そのインデックス情報を示す前記エントリの内部に格納されているか、又はそのエントリの外部にある外部領域に格納されており、
前記エントリは、
前記エントリの内部に格納されている場合、前記部分キーのサイズは所定の第１サイズであり、
前記インデックス情報が前記エントリの内部と外部のどちらに格納しているかを判別する領域識別情報を格納しており、
前記インデックス情報が前記外部領域に格納されている場合、そのインデックス情報へのポインタを格納しており、
前記インデックス情報が有する前記開始オフセットは、そのインデックス情報が有する前記部分キーの元である前記全体キーと、前記ノード内においてそのインデックス情報を示す前記エントリより順位が１つ前の前記エントリによって示される前記インデックス情報が有する前記部分キーの元である前記全体キーとの間において、同一位置における値が異なる最前の位置を示し、
前記ノードを格納する領域及び前記外部領域は、前記全体キーを含む前記レコードを格納する格納手段とは異なる格納手段に設けられており、
当該制御方法は、
前記領域識別情報を取得する領域識別情報取得ステップと、
前記領域識別情報により、前記インデックス情報が前記エントリの内部に格納されていることが示されている場合、前記エントリから前記インデックス情報を取得し、前記領域識別情報により、前記インデックス情報が前記外部領域に格納されていることが示されている場合、そのエントリに格納されている前記ポインタによって示されている前記インデックス情報を取得するインデックス情報取得ステップと、
を有する制御方法。
【請求項９】
検索対象のレコードのインデックス情報が格納されているインデックスツリーについて、そのインデックスツリーを構成するノードに格納されているエントリを処理する機能をコンピュータに持たせるプログラムであって、
前記ノードは、前記インデックス情報を固有に示す前記エントリを、順位付けて格納しており、
前記インデックス情報は、
前記レコードを識別する値列である全体キーの一部を表す値列である部分キーと、その全体キーにおけるその部分キーの開始位置である開始オフセットとを有し、
そのインデックス情報を示す前記エントリの内部に格納されているか、又はそのエントリの外部にある外部領域に格納されており、
前記エントリは、
前記エントリの内部に格納されている場合、前記部分キーのサイズは所定の第１サイズであり、
前記インデックス情報が前記エントリの内部と外部のどちらに格納しているかを判別する領域識別情報を格納しており、
前記インデックス情報が前記外部領域に格納されている場合、そのインデックス情報へのポインタを格納しており、
前記インデックス情報が有する前記開始オフセットは、そのインデックス情報が有する前記部分キーの元である前記全体キーと、前記ノード内においてそのインデックス情報を示す前記エントリより順位が１つ前の前記エントリによって示される前記インデックス情報が有する前記部分キーの元である前記全体キーとの間において、同一位置における値が異なる最前の位置を示し、
前記ノードを格納する領域及び前記外部領域は、前記全体キーを含む前記レコードを格納する格納手段とは異なる格納手段に設けられており、
当該プログラムは、前記コンピュータに、
前記領域識別情報を取得する領域識別情報取得機能と、
前記領域識別情報により、前記インデックス情報が前記エントリの内部に格納されていることが示されている場合、前記エントリから前記インデックス情報を取得し、前記領域識別情報により、前記インデックス情報が前記外部領域に格納されていることが示されている場合、そのエントリに格納されている前記ポインタによって示されている前記インデックス情報を取得するインデックス情報取得機能と、
を持たせるプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、エントリ処理装置、制御方法、及びプログラムに関する。
【背景技術】
【０００２】
レコードの検索を高速に行えるようにするために、インデックスツリーが用いられている。ここで、レコードとは、検索対象のデータである。インデックスツリーは、ノードを階層的に連結した木構造のデータ構造である。ノードはエントリを格納しており、そのエントリは、キーと、そのキーに対応する下位のノードへのポインタとを格納する。ただし、インデックスツリーにおける葉に当たるノード（リーフノード）は、下位のノードへのポインタを持たない。リーフノードは、キーに対応付けて、そのキーに対応するレコードへのポインタを格納している。
【０００３】
インデックスツリーを用いてあるレコードを検索する場合、そのレコードに対応するキーを用いてインデックスツリーを辿る。以下、検索対象のレコードに対応するキーを検索キーと表記する。まず、ルートノードが有する各エントリの中から、検索キーに対応するキーを有するエントリを検索する。そして、検索して得られたエントリに格納されているポインタが示すノードを対象として、検索キーに対応するエントリの検索をさらに行う。このように下位に向けてノードを辿る処理を、リーフノードに到達するまで繰り返す。前述したように、リーフノードには、検索キーに対応するレコードへのポインタが格納されている。したがって、検索キーに対応するエントリを持つノードをルートノードからリーフノードまで順に辿ることで、リーフノードが有するポインタによって示されているレコードを取得できる。
【０００４】
上述したように、インデックスツリーを用いてレコードを検索する際、エントリの検索が行われる。そのため、検索対象のエントリを記憶領域から取得するためにかかる時間を短くすることで、レコードの検索処理にかかる時間を短くすることができる。したがって、エントリは、アクセス速度が速い記憶装置に格納されていることが望ましい。例えばエントリは、ハードディスク等の二次記憶装置よりも、メモリ等の一次記憶装置に格納されていることが望ましい。ただし一般に、アクセス速度が速い記憶装置ほど、記憶容量は小さい。例えば、メモリの記憶容量は、ハードディスクの記憶容量よりも小さい。そこで、エントリをより高速な記憶装置に格納できるようにするためには、エントリのサイズを小さくする必要がある。
【０００５】
ここで、エントリに持たせるキーは、キーによってサイズが異なる可変長キーである場合がある。そして、インデックスツリーを検索する際、この可変長キー全体ではなく、可変長キーの一部を用いれば十分であることが多い。キー同士を区別できれば、ノードに含まれるエントリの中から、検索キーに対応するエントリを特定できるためである。
【０００６】
そこで、このようにキーが可変長キーである場合、その可変長キー全体ではなく、その可変長キーの一部である部分キーをエントリに格納することが望ましい。こうすることで、エントリのサイズを小さくすることができる。さらに、部分キーは固定長であることが望ましい。部分キーが固定長であると、その部分キーを格納するエントリのサイズを固定長にできるため、記憶領域内のどこにエントリが格納されているかの特定（位置決め）が容易になる。
【０００７】
非特許文献１〜４は、インデックスツリーにおいて可変長キーを扱う技術を開示している。非特許文献１は、Prefix B-tree と呼ばれるデータ構造を開示している。Prefix B-tree は、あるノードのキーと他のノードのキーを区別するために必要なプリフィックスのみを、親ノードに登録する。
【０００８】
非特許文献２は、Prefix key vector というデータ構造を開示している。Prefix key vector では、キーの固定長の先頭部分と残りの可変長部分をわけて記録する。具体的には、ノード内の複数のキーから共通するプリフィックスを特定する。そして、各キーについて、特定したプリフィックスを含む固定サイズの先頭部分を記録する。
【０００９】
非特許文献３は、インメモリ環境を想定したPartial keyと呼ばれる方法を開示している。Partial key の場合における各エントリは、キー全体へのポインタと、キーの一部、そのオフセットの３つを持つ。
【００１０】
非特許文献４は、Fast Architecture Sensitive Tree Search (FAST)というインデックスツリーを開示している。FASTにおける可変長キーは、キーの一部を複数切り出し、組み合わせたものとして表現される。
【００１１】
特許文献においては、可変長キーに関する以下の技術が開示されている。特許文献１記載の技術は、ノード長より長いキーに対する記憶割り当てを可能にすることを目的としている。そのために、B+-treeのノード中の固定長領域に格納できないキーに対しては、オーバーフローした部分を入出力ブロックの可変長領域に格納する。
【００１２】
特許文献２記載の技術は、フレーズ検索を可能にすると逆インデックスが大きくなって性能が低下するので、キーを圧縮して逆インデックスのサイズを縮小することを目的としている。そのために、ドキュメントの差分をハフマン符号化で圧縮する。
【００１３】
以上のように、それぞれの目的と実行環境に合わせて、可変長キーの挿入および検索のための技術が開示されている。
【先行技術文献】
【特許文献】
【００１４】
【特許文献１】特許第２８７４８１０号公報
【特許文献２】特表２０１１−５２３１５２号公報
【非特許文献】
【００１５】
【非特許文献１】R. Bayer and K. Unterauer、「Prefix B-trees」、ACM Transactions on Database Systems、2(1)、pp.11 - 26、1977年
【非特許文献２】David B. Lomet、「The Evolution of Effective B-tree: Page Organization and Techniques」、A Personal Account、SIGMOD Record、30(3)、pp. 64-69、2001年
【非特許文献３】P. Bohannon、外２名、「Main-Memory Index Structures with Fixed-Size Partial Keys」、In SIGMOD、pp. 163-174,、２００１年
【非特許文献４】C. Kim、外８名、「FAST: Fast Architecture Sensitive Tree Search on Modern CPUs and GPUs」、In SIGMOD、pp.339 - 350、２０１０年
【発明の概要】
【発明が解決しようとする課題】
【００１６】
本発明者は、インデックスツリーを用いたレコードの検索及び挿入にかかる時間をさらに短くすることを検討した。まず、非特許文献１のPrefix B-tree では、プリフィックスが可変長であるため、記憶領域内のどこにキーが記憶されているかを特定するための処理が必要となる。そのため、検索にかかる時間が長い。
【００１７】
また、非特許文献２や非特許文献３の技術の場合、インデックスツリーを小規模化することが難しい。まず、非特許文献２の技術では、各キーのうち、他のキーと共通するプリフィックス以外の可変長部分はそのまま格納される。そのため、格納されるキーの大きさが大きい。非特許文献３では、各エントリは、キー全体へのポインタを持つ。そのため、エントリのサイズが大きくなる。
【００１８】
さらに、非特許文献３では、複数のエントリがそれぞれ有する「キーの一部」が同一になる可能性がある。そしてこの場合、各キーの全体を取得して比較を行う。そのため、非特許文献３では、検索の際にキー全体へのアクセスが発生するため、検索速度が遅くなる。
【００１９】
非特許文献４の技術の場合、新たなエントリをノードに挿入する際に、各エントリに持たせるキーを更新する必要がある。したがって、非特許文献４の技術は、新たなレコードをインデックスツリーに登録するためにかかる時間が長い。
【００２０】
本発明は以上の課題に鑑みてなされたものである。本発明の目的は、インデックスツリーを用いたレコードの検索及び挿入にかかる時間を短くする技術を提供することである。
【課題を解決するための手段】
【００２１】
本発明が提供するエントリ処理装置は、検索対象のレコードのインデックス情報が格納されているインデックスツリーについて、そのインデックスツリーを構成するノードに格納されているエントリを処理するエントリ処理装置である。前記ノードは、前記インデックス情報を固有に示す前記エントリを、順位付けて格納している。前記インデックス情報は、前記レコードを識別する値列である全体キーの一部を表す値列である部分キーと、その全体キーにおけるその部分キーの開始位置である開始オフセットとを有し、そのインデックス情報を示す前記エントリの内部に格納されているか、又はそのエントリの外部にある外部領域に格納されている。前記エントリは、前記エントリの内部に格納されている場合、前記部分キーのサイズは所定の第１サイズであり、前記インデックス情報が前記エントリの内部と外部のどちらに格納しているかを判別する領域識別情報を格納しており、前記インデックス情報が前記外部領域に格納されている場合、そのインデックス情報へのポインタを格納しており、前記インデックス情報が有する前記開始オフセットは、そのインデックス情報が有する前記部分キーの元である前記全体キーと、前記ノード内においてそのインデックス情報を示す前記エントリより順位が１つ前の前記エントリによって示される前記インデックス情報が有する前記部分キーの元である前記全体キーとの間において、同一位置における値が異なる最前の位置を示す。前記ノードを格納する領域及び前記外部領域は、前記全体キーを含む前記レコードを格納する格納手段とは異なる格納手段に設けられている。当該エントリ処理装置は、前記領域識別情報を取得する領域識別情報取得手段と、前記領域識別情報により、前記インデックス情報が前記エントリの内部に格納されていることが示されている場合、前記エントリから前記インデックス情報を取得し、前記領域識別情報により、前記インデックス情報が前記外部領域に格納されていることが示されている場合、そのエントリに格納されている前記ポインタによって示されている前記インデックス情報を取得するインデックス情報取得手段と、を有する。
【００２２】
本発明が提供する制御方法は、コンピュータによって実行される制御方法である。このコンピュータは、当該制御方法を実行することで、本発明が提供するエントリ処理装置として動作する。当該制御方法は、前記領域識別情報を取得する領域識別情報取得ステップと、前記領域識別情報により、前記インデックス情報が前記エントリの内部に格納されていることが示されている場合、前記エントリから前記インデックス情報を取得し、前記領域識別情報により、前記インデックス情報が前記外部領域に格納されていることが示されている場合、そのエントリに格納されている前記ポインタによって示されている前記インデックス情報を取得するインデックス情報取得ステップと、を有する。
【００２３】
本発明が提供するプログラムは、コンピュータに、本願発明が提供するエントリ処理装置として動作する機能を持たせる。当該プログラムは、前記コンピュータに、本発明が提供するエントリ処理装置が有する各機能構成の機能を持たせる。
【発明の効果】
【００２４】
本発明によれば、インデックスツリーを用いたレコードの検索及び挿入にかかる時間を短くする技術が提供される。
【図面の簡単な説明】
【００２５】
【図１】実施形態１に係るエントリ処理装置を示すブロック図である。
【図２】インデックスツリーを構成する各種データのデータ構造を示す図である。
【図３】実施形態１に係るエントリ処理装置のハードウエア構成を例示するブロック図である。
【図４】実施形態１に係るエントリ処理装置によって行われる処理の流れを例示するフローチャートである。
【図５】実施形態２に係るエントリ処理装置を示すブロック図である。
【図６】実施形態２のエントリ処理装置によって実行される処理の流れを示すフローチャートである。
【図７】実施形態３に係るエントリ処理装置を示すブロック図である。
【図８】実施形態３のエントリ処理装置によって実行される処理の流れを示すフローチャートである。
【図９】実施形態４に係るエントリ処理装置を示すブロック図である。
【図１０】実施形態４のエントリ処理装置によって実行される処理の流れを示すフローチャートである。
【図１１】実施形態５に係るエントリ処理装置を示すブロック図である。
【図１２】実施形態６に係るエントリ処理装置を示すブロック図である。
【図１３】実施形態６のエントリ処理装置によって実行される処理の流れを示すフローチャートである。
【発明を実施するための形態】
【００２６】
以下、本発明の実施の形態について、図面を用いて説明する。尚、すべての図面において、同様な構成要素には同様の符号を付し、適宜説明を省略する。
【００２７】
[実施形態１]
図１は、実施形態１に係るエントリ処理装置２０００を示すブロック図である。図１において、矢印は情報の流れを表している。さらに、図１において、各ブロックは、ハードウエア単位の構成ではなく、機能単位の構成を表している。
【００２８】
エントリ処理装置２０００は、インデックスツリーを構成するノードに格納されているエントリを処理する。このインデックスツリーは、検索対象のレコードのインデックス情報を持つ。
【００２９】
図２は、上記インデックスツリーを構成する各種データのデータ構造を示す図である。ノード１００は、エントリ２００を順位付けて格納している。以下、ノード１００における順位がｉ番目であるエントリ２００を、エントリ２００−ｉと表記する。例えば図２の場合、エントリ２００−２の順位は、エントリ２００−１の順位の次である。以下、各エントリ２００−ｉを区別せずに説明する場合は、「−ｉ」の部分を省略して、エントリ２００と表記する。この点については、エントリ２００以外の各データについても同様である。
【００３０】
エントリ２００は、インデックス情報２２０を固有に示す。ここで、エントリ２００−ｉによって示されているインデックス情報２２０を、インデックス情報２２０−ｉと表記する。インデックス情報２２０−ｉは、エントリ２００−ｉの内部にある領域か、又はエントリ２００−ｉの外部にある外部領域３００に格納されている。エントリ２００−ｉは、インデックス情報２２０−ｉがエントリ２００−ｉの内部と外部のどちらに格納されているかを示す領域識別情報２１０を格納している。ここで、エントリ２００−ｉが格納している領域識別情報２１０を、領域識別情報２１０−ｉと表記する。
【００３１】
また、エントリ２００−ｉは、インデックス情報２２０−ｉが外部領域３００に格納されている場合、外部ポインタ２３０を格納する。エントリ２００−ｉが格納する外部ポインタ２３０を、外部ポインタ２３０−ｉと表記する。外部ポインタ２３０−ｉは、外部領域３００に格納されているインデックス情報２２０−ｉへのポインタである。図２において、点線の矢印は、矢印の始点にある外部ポインタ２３０−２が、矢印の終点にあるインデックス情報２２０−２を指していることを表す。
【００３２】
領域識別情報２１０は、例えば１ビットの情報である。例えば領域識別情報２１０−ｉは、インデックス情報２２０−ｉがエントリ２００−ｉの内部に格納されている場合に１を示し、インデックス情報２２０−ｉがエントリ２００−ｉの外部に格納されている場合に０を示す。ただし、領域識別情報２１０は、２ビット以上の情報であってもよい。
【００３３】
インデックス情報２２０は、部分キー２２２及び開始オフセット２２４を有する。ここで、インデックス情報２２０−ｉが有する部分キー２２２を部分キー２２２−ｉと表記し、インデックス情報２２０−ｉが有する開始オフセット２２４を開始オフセット２２４−ｉと表記する。部分キー２２２は、レコードを識別する値列である全体キー４１２の一部を表す値列である。ここで、部分キー２２２−ｉの元となる全体キー４１２を、全体キー４１２−ｉと表記する。
【００３４】
インデックス情報２２０−ｉがエントリ２００−ｉの内部に格納されている場合、部分キー２２２−ｉの大きさは、所定の第１サイズである。つまり、インデックス情報２２０−ｉがエントリ２００−ｉの内部に格納されている場合、部分キー２２２−ｉの大きさは固定長である。一方、インデックス情報２２０−ｉが外部領域３００に格納されている場合、部分キー２２２−ｉの大きさは、第１サイズより大きい任意の大きさである。つまり、インデックス情報２２０−ｉが外部領域３００に格納されている場合、部分キー２２２−ｉの大きさは可変長である。
【００３５】
開始オフセット２２４−ｉは、全体キー４１２−ｉにおける部分キー２２２−ｉの開始位置を示す。例えば、全体キー４１２−ｉが「abcdef」であり、部分キー２２２−ｉが「bc」である場合、開始オフセット２２４−ｉは２である。この例では、全体キー４１２における最小の順位を１としている。ただし、全体キー４１２における最小の順位は１に限らない。例えば、全体キー４１２における最小の順位は、０でもよい。この場合、上述の例において、開始オフセット２２４−ｉは３となる。以降では、全体キー４１２における最小の順位が１であるとして説明をする。
【００３６】
開始オフセット２２４−ｉは、インデックス情報２２０−ｉと、エントリ２００−ｉの１つ前の順位にあるエントリ２００−（ｉ−１）によって示されるインデックス情報２２０−（ｉ−１）との比較によって定まる。より具体的には、開始オフセット２２４−ｉは、全体キー４１２−ｉと全体キー４１２−（ｉ−１）との間において、同一位置における値が異なる最前の位置を示す。ただし、エントリ２００−ｉが先頭のエントリである場合（ｉが１の場合）、開始オフセット２２４−ｉは最小の位置（例：１）を示す。
【００３７】
例えば、全体キー４１２−（ｉ−１）が「abcdef」であり、全体キー４１２−ｉが「abcegb」であるとする。この２つの全体キー４１２の間において、同一位置における値が異なる最前の位置は４である。
【００３８】
そして、部分キー２２２−ｉの大きさは、インデックス情報２２０−ｉと、エントリ２００−ｉの１つ後ろに位置するエントリ２００−（ｉ＋１）によって示されるインデックス情報２２０−（ｉ＋１）との比較、及び開始オフセット２２４−ｉによって決まる。より具体的には、部分キー２２２−ｉのサイズは、全体キー４１２−ｉと全体キー４１２−（ｉ＋１）との間において、同一位置における値が異なる最前の位置（以下、終了オフセット）から、開始オフセット２２４−ｉを引いた値に依存する。「終了オフセット−（開始オフセット２２４−ｉ）＋１」が第１サイズ以上の場合、部分キー２２２−ｉのサイズは、「終了オフセット−（開始オフセット２２４−ｉ）＋１」となる。つまり、部分キー２２２−ｉは、全体キー４１２−ｉのうち、全体キー４１２−ｉと全体キー４１２−（ｉ−１）との間において同一位置における値が異なる最前の位置から始まり、全体キー４１２−ｉと全体キー４１２−（ｉ＋１）との間において同一位置における値が異なる最前の位置で終わる値列である。
【００３９】
一方、「終了オフセット−（開始オフセット２２４−ｉ）＋１」が第１サイズより小さい場合、部分キー２２２−ｉのサイズは第１サイズとなる。つまり、部分キー２２２−ｉは、全体キー４１２−ｉのうち、全体キー４１２−ｉと全体キー４１２−（ｉ−１）との間において同一位置における値が異なる最前の位置から始まり、大きさが第１サイズの値列である。
【００４０】
例えば、全体キー４１２−（ｉ−１）が「dfacb」、全体キー４１２−ｉが「dfebcag」、全体キー４１２−（ｉ＋１）が「dfebdag」であるとする。そして第１サイズは２であるとする。この場合、開始オフセット２２４−ｉは、３である。また、終了オフセットは、５である。したがって、「終了オフセット−（開始オフセット２２４−ｉ）＋１」は３であり、第１サイズよりも大きい。したがって、部分キー２２２−ｉは、全体キー４１２−ｉのうち、開始位置が３であり、終了位置が５である「ebc」となる。
【００４１】
また例えば、全体キー４１２−（ｉ−１）が「dfacb」、全体キー４１２−ｉが「dfacd」、全体キー４１２−（ｉ＋１）が「dface」であるとする。そして第１サイズは２であるとする。この場合、開始オフセット２２４−ｉは、３である。また、終了オフセットは、３である。したがって、「終了オフセット−（開始オフセット２２４−ｉ）＋１」は１であり、第１サイズよりも小さい。したがって、部分キー２２２−ｉは、全体キー４１２−ｉのうち、開始位置が３であり、大きさが２である「cd」となる。
【００４２】
ノード１００を格納する領域及び外部領域３００は、全体キー４１２を含むレコード４１０を格納するレコード格納部４００とは異なる格納領域である。したがって、部分キー２２２を格納する格納領域は、その部分キー２２２の元になる全体キー４１２が格納されている格納領域と異なる。レコード４１０は、レコード４１０を識別する全体キー４１２、及びデータ４１４を格納している。
【００４３】
ノード１００に含まれる各エントリ２００の順位は、エントリ２００に対応する全体キー４１２の大きさに基づいてソートした場合における順位によって定まる。ここで、全体キー４１２の大小関係は、全体キー４１２が示す値列を辞書式順序で並べた場合における位置の差異によって定まる。例えば、値列は、辞書式順序で並べた場合の位置が前であるほど小さいとする。逆に、値列は、辞書式順序で並べた場合の位置が前であるほど大きいとしてもよい。さらに、２つの値列は、辞書式順序で並べた場合の位置が同一である場合、等しい値列であるとする。なお、部分キー２２２の大小関係、及び部分キー２２２と全体キー４１２の大小関係についても、全体キー４１２の大小関係と同様である。
【００４４】
エントリ処理装置２０００は、上述のように定義される各データ構造を持つエントリを処理する。そのために、エントリ処理装置２０００は、領域識別情報取得部２０２０及びインデックス情報取得部２０４０を有する。以下、それぞれについて説明する。
【００４５】
＜領域識別情報取得部２０２０＞
領域識別情報取得部２０２０は、エントリ２００から領域識別情報２１０を取得する。以下では、領域識別情報取得部２０２０が、エントリ２００−ｉから領域識別情報２１０−ｉを取得したとして、インデックス情報取得部２０４０について説明をする。
【００４６】
＜インデックス情報取得部２０４０＞
インデックス情報取得部２０４０は、領域識別情報取得部２０２０によって取得された領域識別情報２１０−ｉを用いて、インデックス情報２２０−ｉがエントリ２００の内部と外部のどちらに格納されているのかを判定する。上記インデックス情報２２０−ｉがエントリ２００−ｉの内部に格納されている場合、インデックス情報取得部２０４０は、エントリ２００−ｉの内部からインデックス情報２２０−ｉを取得する。一方、インデックス情報２２０−ｉがエントリ２００−ｉの外部に格納されている場合、インデックス情報取得部２０４０は、まずエントリ２００−ｉに格納されている外部ポインタ２３０−ｉを取得する。そして、インデックス情報取得部２０４０は、外部ポインタ２３０−ｉによって示されているインデックス情報２２０−ｉを、外部領域３００から取得する。
【００４７】
ここで、前述した通り、外部領域３００に格納されるインデックス情報２２０は可変長である。そのためインデックス情報取得部２０４０は、外部ポインタ２３０によって示されているインデックス情報２２０を取得するために、そのインデックス情報２２０のサイズを把握する必要がある。そこで、例えば外部領域３００に格納されているインデックス情報２２０は、そのインデックス情報２２０のサイズをさらに示す。例えば外部ポインタ２３０によって示されている領域の先頭に、インデックス情報２２０のサイズが、所定サイズで格納されているとする。この場合、まずインデックス情報取得部２０４０は、外部ポインタ２３０によって示されている領域の先頭から、所定サイズのデータを取得することで、インデックス情報２２０のサイズを把握する。そして、インデックス情報取得部２０４０は、インデックス情報２２０のサイズが格納されている領域に隣接する領域から、把握したサイズのデータを取得することで、インデックス情報２２０を取得する。
【００４８】
また、例えばインデックス情報２２０のサイズは、外部ポインタ２３０と共にエントリ２００に格納されていてもよい。この場合、インデックス情報取得部２０４０は、まずエントリ２００に格納されているインデックス情報２２０のサイズを取得することで、インデックス情報２２０のサイズを把握する。その後、インデックス情報取得部２０４０は、外部ポインタ２３０によって示されている領域から、把握したサイズのデータを取得することで、インデックス情報２２０を取得する。
【００４９】
なお、上述したインデックス情報２２０やエントリ２００に格納されているのは、インデックス情報２２０のサイズではなく、部分キー２２２のサイズでもよい。開始オフセット２２４は、部分キー２２２のサイズに関わらず固定長でよいため、部分キー２２２のサイズが分かれば、インデックス情報２２０のサイズが分かるためである。
【００５０】
＜ハードウエア構成＞
エントリ処理装置２０００が有する各機能構成部は、例えば、個々に又は複数組み合わせられた状態で、少なくとも１つのハードウエア構成要素として実現される。その他にも例えば、各機能構成部は、少なくとも１つのソフトウエア構成要素として実現される。その他にも例えば、各機能構成部は、ハードウエア構成要素とソフトウエア構成要素の組み合わせにより実現される。
【００５１】
図３は、実施形態１に係るエントリ処理装置２０００のハードウエア構成を例示するブロック図である。図３において、エントリ処理装置２０００は、バス１０２０、プロセッサ１０４０、メモリ１０６０、及びストレージ１０８０を有する。
【００５２】
バス１０２０は、プロセッサ１０４０、メモリ１０６０、及びストレージ１０８０が、相互にデータを送受信するためのデータ伝送路である。プロセッサ１０４０は、例えば CPU (Central Processing Unit) や GPU (Graphics Processing Unit) などの演算処理装置である。メモリ１０６０は、例えば RAM (Random Access Memory) や ROM (Read Only Memory) などのメモリである。ストレージ１０８０は、例えばメモリカード、ハードディスク、又は SSD (Solid State Drive) などの記憶装置である。また、ストレージ１０８０は、RAM や ROM 等のメモリであってもよい。ただし、メモリ１０６０のデータ伝送速度は、ストレージ１０８０のデータ伝送速度よりも速い。
【００５３】
領域識別情報取得モジュール１２２０は、エントリ処理装置２０００に、領域識別情報取得部２０２０の機能を持たせるためのプログラムである。プロセッサ１０４０は、領域識別情報取得モジュール１２２０を実行することで、領域識別情報取得部２０２０の機能を実現する。
【００５４】
インデックス情報取得モジュール１２４０は、エントリ処理装置２０００に、インデックス情報取得部２０４０の機能を持たせるためのプログラムである。プロセッサ１０４０は、インデックス情報取得モジュール１２４０を実行することで、インデックス情報取得部２０４０の機能を実現する。
【００５５】
メモリ１０６０はノード１００を格納する。また、メモリ１０６０は、ノード１００の外部にインデックス情報２２０を格納することで、外部領域３００として機能する。
【００５６】
ストレージ１０８０は、上記各モジュールを格納する。また、ストレージ１０８０は、全体キー４１２及びデータ４１４を含むレコード４１０を格納することで、レコード格納部４００として機能する。
【００５７】
エントリ処理装置２０００のハードウエア構成は、図３に示した構成に限定されない。例えば、エントリ処理装置２０００は別のメモリ１０６０をさらに有し、ノード１００を格納するメモリ１０６０と、外部領域３００として機能するメモリ１０６０とが異なるようにしてもよい。
【００５８】
また、上記各モジュールは、メモリ１０６０に格納されてもよい。
【００５９】
＜処理の流れ＞
図４は、実施形態１に係るエントリ処理装置２０００によって行われる処理の流れを例示するフローチャートである。図４のフローチャートは、領域識別情報取得部２０２０が領域識別情報２１０−ｉを取得する場合におけるエントリ処理装置２０００の処理を示す。
【００６０】
ステップＳ１０２において、領域識別情報取得部２０２０は、領域識別情報２１０−ｉを取得する。ステップＳ１０４において、インデックス情報取得部２０４０は、上記領域識別情報２１０−ｉを用いて、インデックス情報２２０−ｉがエントリ２００−ｉの内部と外部のどちらに格納されているかを判定する。インデックス情報２２０−ｉがエントリ２００−ｉの内部に格納されている場合、図４の処理は、ステップＳ１０６に進む。一方、インデックス情報２２０−ｉがエントリ２００−ｉの外部に格納されている場合、図４の処理は、ステップＳ１０８に進む。
【００６１】
ステップＳ１０６において、インデックス情報取得部２０４０は、エントリ２００−ｉの内部からインデックス情報２２０−ｉを取得する。
【００６２】
ステップＳ１０８において、インデックス情報取得部２０４０は、エントリ２００−ｉの内部から外部ポインタ２３０−ｉを取得する。ステップＳ１１０において、インデックス情報取得部２０４０は、外部ポインタ２３０−ｉによって示されているインデックス情報２２０−ｉを取得する。
【００６３】
＜作用・効果＞
以上により、本実施形態のエントリ処理装置２０００によれば、インデックス情報２２０に格納されている部分キー２２２の大きさが固定長である。また、領域識別情報２１０や開始オフセット２２４も、各エントリ２００に共通の大きさとすることができる。例えば領域識別情報２１０は、前述したように、１ビットにすることができる。また、開始オフセット２２４の大きさは、エントリ処理装置２０００が想定するキーの長さに合わせて予め定めておくことが可能である。このように、実施形態１のエントリ処理装置２０００によれば、エントリ２００を固定長にすることができる。そのため、インデックス情報２２０が格納されている場所を容易に割り出すことができる。例えば、エントリ２００のサイズがＡという固定サイズであり、ノード１００に含まれる全てのエントリ２００が連続したメモリ領域に格納されているとする。この場合、例えば順位がｉであるエントリ２００−ｉが格納されている位置は、エントリ２００を格納している連続したメモリ領域の先頭アドレスに、Ａ×（ｉ−１）を足すことで求めることができる。したがって、インデックス情報２２０が格納されている場所を割り出す処理にかかる時間が短い。
【００６４】
また、本実施形態によれば、部分キー２２２の大きさが第１サイズより大きい場合、部分キー２２２をレコード格納部４００と異なる格納部に設けられている外部領域３００に格納する。こうすることで、部分キー２２２のうち、エントリ２００に収まる部分だけを切り出してエントリ２００に格納するということはしないため、エントリ２００の間で部分キー２２２が重複することはない。よって、検索対象のキーに対応するエントリ２００を検索する際に、部分キー２２２によってエントリ２００を区別することが可能であり、部分キー２２２の元となる全体キー４１２を取得する必要がない。よって、検索の際に全体キー４１２が必要な場合と比較し、検索にかかる時間が短い。また、挿入の際に必要な検索処理（例：挿入位置を決定するための検索）についても同様に所用時間が短くなるため、挿入にかかる時間も短い。
【００６５】
また、実施形態１のエントリ処理装置２０００によれば、各エントリ２００によって示されるインデックス情報２２０が有する部分キー２２２は、そのエントリ２００の前後のエントリにそれぞれ対応する全体キー４１２によって決まる。したがって、あるエントリ２００が挿入された場合でも、そのエントリ２００が挿入された位置の前後のエントリ２００のみを更新すればよい。したがって、実施形態１のエントリ処理装置２０００は、エントリ２００を挿入した際に、ノード１００に含まれる全てのエントリ２００を更新する場合と比較し、挿入処理にかかる時間が短い。
【００６６】
以上により、本実施形態によれば、エントリ２００の検索及び挿入にかかる時間が短くなる。
【００６７】
なお、エントリ２００のサイズは、４バイトの倍数であることが望ましい。これは、CPU のレジスタやキャッシュラインのサイズが、４バイトの倍数であることが多いためである。CPU のレジスタやキャッシュラインのサイズに合うようにすることで、CPU のレジスタやキャッシュラインの利用効率が高まる。そのため、部分キー２２２の読み込みなど、エントリの処理にかかる時間がさらに短くなる。
【００６８】
[実施形態２]
図５は、実施形態２に係るエントリ処理装置２０００を示すブロック図である。図５において、矢印は情報の流れを表している。さらに、図５において、各ブロックは、ハードウエア単位の構成ではなく、機能単位の構成を表している。以下で説明する点を除き、実施形態２のエントリ処理装置２０００は、実施形態１のエントリ処理装置２０００と同様である。
【００６９】
エントリ処理装置２０００は、検索キー取得部２０６０及びインデックス情報特定部２０８０を有する。検索キー取得部２０６０は、検索対象の全体キー４１２を取得する。以下、検索対象の全体キー４１２を、検索キーと表記する。インデックス情報特定部２０８０は、同一のノード１００に含まれる各エントリ２００が示すインデックス情報２２０の部分キー２２２の中から、検索キー以下である最大の部分キー２２２を特定する。こうすることで、インデックス情報特定部２０８０は、同一のノード１００に含まれる各エントリ２００が示すインデックス情報２２０の中から、検索キー以下である最大の部分キー２２２を有するインデックス情報２２０を特定する。
【００７０】
インデックス情報特定部２０８０は、インデックス情報２２０−ｉと検索キーとを比較することで、全体キー４１２−ｉと検索キーの大小関係を判定する。まず、インデックス情報特定部２０８０は、検索キーのうち、開始位置が開始オフセット２２４−ｉであり、大きさが部分キー２２２−ｉと同一である部分と、部分キー２２２−ｉとを比較することで行う。
【００７１】
＜処理の流れ＞
図６は、実施形態２のエントリ処理装置２０００によって実行される処理の流れを示すフローチャートである。ステップＳ２０２において、検索キー取得部２０６０は、検索キーを取得する。ステップＳ２０４において、インデックス情報特定部２０８０は、カウンタｉを０に初期化する。
【００７２】
ステップＳ２０４〜Ｓ２１０は、対象のノード１００に含まれる各エントリ２００を対象として順次実行されるループ処理Ａである。なお、各エントリ２００は、エントリ２００に対応する全体キー４１２の大きさの昇順にソートされているとする。また、ループ処理Ａにおいて、カウンタｉの初期値は１である。そして、ループ処理Ａを一回実行するたびに、カウンタｉの値は１増加する。ステップＳ２０４において、インデックス情報特定部２０８０は、ｉが、対象のノード１００に含まれるエントリ２００の総数Ｎ以下であるか否かを判定する。ｉがＮ以下である場合、図６の処理はステップＳ２０６に進む。一方、ｉがＮより大きい場合、図６の処理はステップＳ２１４に進む。
【００７３】
ステップＳ２０６において、インデックス情報取得部２０４０は、インデックス情報２２０−ｉを取得する。ステップＳ２０８において、インデックス情報特定部２０８０は、インデックス情報取得部２０４０によって取得されたインデックス情報２２０−ｉの部分キー２２２−ｉと、検索キーとの大きさを比較する。なお、ステップＳ２０８における部分キー２２２−ｉと検索キーとの比較は、検索キーのうち、開始位置が開始オフセット２２４−ｉであり、大きさが部分キー２２２−ｉと同一である部分（以下、比較対象部分）と、部分キー２２２−ｉとを比較することで行う。
【００７４】
部分キー２２２−ｉと検索キーの比較対象部分とが等しい場合、図６の処理は、ステップＳ２１４に進む。部分キー２２２−ｉが検索キーの比較対象部分より小さい場合、図６の処理は、ステップＳ２１０に進む。ステップＳ２１０はループ処理Ａの終端であるため、図６の処理は、ステップＳ２１０からステップＳ２０４に進む。部分キー２２２−ｉが検索キーの比較対象部分より大きい場合、図６の処理は、ステップＳ２１２に進む。ステップＳ２１２において、インデックス情報特定部２０８０は、ｉから１を減算する。
【００７５】
ステップＳ２１４において、インデックス情報特定部２０８０は、部分キー２２２−ｉを、検索キー以下である最大の部分キー２２２として特定する。
【００７６】
なお、ステップＳ２０８における部分キー２２２−ｉと検索キーとの比較は、次のように行うこともできる。まず、検索キーと、比較済みの各部分キー２２２との間において、値が異なる最小の位置を格納する変数ｕを用意する。まず、ｕを０に初期化する。そして、ステップＳ２０８において、インデックス情報特定部２０８０は、まずｕの値と、開始オフセット２２４−ｉとを比較する。ここで、開始オフセット２２４−ｉの方がｕより大きければ、ステップＳ２０８の処理を終えた後に、ｕの値を、開始オフセット２２４−ｉの値で更新する。
【００７７】
ステップＳ２０８において、インデックス情報特定部２０８０は、開始オフセット２２４−ｉがｕよりも小さい場合、部分キー２２２−ｉが検索キーよりも大きいと判断する。一方、インデックス情報特定部２０８０は、開始オフセット２２４−ｉがｕよりも大きい場合、部分キー２２２−ｉが検索キーよりも小さいと判断する。したがって、これらの場合、部分キー２２２−ｉと検索キーとの間で値列の比較を行わなくても、部分キー２２２−ｉと検索キーとの大小関係が分かる。そのため、インデックス情報特定部２０８０による処理にかかる時間が短くなる。
【００７８】
開始オフセット２２４−ｉとｕとが等しい場合については、インデックス情報特定部２０８０は、部分キー２２２−ｉと検索キーとの間で、値列の比較を行う。
【００７９】
＜作用・効果＞
本実施形態によれば、検索キーに対応する部分キー２２２を特定することができる。例えば、ある検索キーに対応するレコードを取得するためにインデックスツリーを辿る際、実施形態２のエントリ処理装置２０００を利用することで、現在検索対象としているノード１００の次に検索対象とすべきノード１００を割り出すことができる。
【００８０】
[実施形態３]
図７は、実施形態３に係るエントリ処理装置２０００を示すブロック図である。図７において、矢印は情報の流れを表している。さらに、図７において、各ブロックは、ハードウエア単位の構成ではなく、機能単位の構成を表している。以下で説明する点を除き、実施形態３のエントリ処理装置２０００は、上述したいずれかの実施形態のエントリ処理装置２０００と同様である。
【００８１】
実施形態３のエントリ処理装置２０００は、生成するエントリ２００によって示されるインデックス情報２２０を、生成するエントリ２００の内部又は外部に格納する処理を行う。そのために、エントリ処理装置２０００は、エントリ生成部２０９０を有する。エントリ生成部２０９０は、インデックス情報２２０を取得する。そして、取得したインデックス情報２２０が有する部分キー２２２の大きさが第１サイズ以下の場合、そのインデックス情報２２０を、生成するエントリ２００の内部に格納する。
【００８２】
一方、エントリ生成部２０９０は、取得したインデックス情報２２０が有する部分キー２２２の大きさが第１サイズより大きい場合、そのインデックス情報２２０を外部領域３００に格納する。さらに、エントリ生成部２０９０は、インデックス情報２２０へのポインタである外部ポインタ２３０を、生成するエントリ２００の内部に格納する。
【００８３】
＜処理の流れ＞
図８は、実施形態３のエントリ処理装置２０００によって実行される処理の流れを示すフローチャートである。ステップＳ３０２において、エントリ生成部２０９０は、インデックス情報２２０を取得する。ステップＳ３０４において、エントリ生成部２０９０は、取得したインデックス情報２２０が有する部分キー２２２の大きさが第１サイズ以下であるか否かを判定する。部分キー２２２の大きさが第１サイズ以下である場合、図８の処理は、ステップＳ３０６に進む。一方、部分キー２２２の大きさが第１サイズより大きい場合、図８の処理は、ステップＳ３０８に進む。
【００８４】
ステップＳ３０６において、エントリ生成部２０９０は、インデックス情報２２０を、生成するエントリ２００の内部に格納する。
【００８５】
ステップＳ３０８において、エントリ生成部２０９０は、インデックス情報２２０を外部領域３００に格納する。ステップＳ３１０において、エントリ生成部２０９０は、インデックス情報２２０へのポインタである外部ポインタ２３０を、生成するエントリ２００の内部に格納する。
【００８６】
＜作用・効果＞
実施形態３のエントリ処理装置２０００によれば、取得したインデックス情報２２０を示すエントリを生成することができる。なお、部分キー２２２の大きさが第１サイズより大きい場合、エントリ生成部２０９０は、エントリ２００の外部に部分キー２２２を格納する。このようにすることで、エントリ２００のサイズが固定長であっても、可変長の部分キー２２２を扱うことができる。したがって、インデックスツリーの検索や挿入に全体キー４１２を使う頻度が少なくなるため、インデックスツリーの挿入や検索にかかる時間が短くなる。
【００８７】
[実施形態４]
図９は、実施形態４に係るエントリ処理装置２０００を示すブロック図である。図９において、矢印は情報の流れを表している。さらに、図９において、各ブロックは、ハードウエア単位の構成ではなく、機能単位の構成を表している。以下で説明する点を除き、実施形態４のエントリ処理装置２０００は、実施形態３のエントリ処理装置２０００と同様である。
【００８８】
実施形態４のエントリ処理装置２０００は、ノード１００にエントリ２００を挿入する。ここで、ノード１００に挿入するエントリ２００を、挿入エントリと表記する。そのために、実施形態４のエントリ処理装置２０００は、挿入キー取得部２１００、挿入順位算出部２１１０、第１最前位置算出部２１２０、第２最前位置算出部２１３０、及びインデックス情報生成部２１４０を有する。
【００８９】
＜挿入キー取得部２１００＞
挿入キー取得部２１００は、挿入エントリに対応付ける全体キー４１２を取得する。以下、この全体キー４１２を挿入キーと表記する。
【００９０】
＜挿入順位算出部２１１０＞
挿入順位算出部２１１０は、挿入エントリが挿入されるノード１００において、挿入エントリを挿入する順位（以下、挿入順位）を算出する。具体的には、挿入順位算出部２１１０は、挿入キーを用いて、ノード１００に含まれる各エントリ２００のうち、エントリ２００によって示されるインデックス情報２２０が有する部分キー２２２が、挿入キー以下である最大の部分キー２２２であるエントリ２００を特定する。この特定は、検索キー取得部２０６０に対し、検索キーとして挿入キーを入力することで、インデックス情報特定部２０８０によって行われる。そして、挿入順位算出部２１１０は、挿入順位を、挿入キー取得部２１００によって特定されたインデックス情報を示すエントリ２００の順位より１つ後の順位とする。以下、挿入順位がｉであるとして説明する。
【００９１】
＜第１最前位置算出部２１２０＞
第１最前位置算出部２１２０は、挿入順位の一つ前の順位（ｉ−１）にあるエントリ２００−（ｉ−１）が示すインデックス情報２２０−（ｉ−１）と、挿入キーとを比較する。ここで、エントリ２００−（ｉ−１）を、直前エントリとも表記する。この比較を行うことで、第１最前位置算出部２１２０は、部分キー２２２−（ｉ−１）の元である全体キー４１２−（ｉ−１）と挿入キーとの間において、同一位置における値が異なる最前の位置を算出する。ここで、算出された最前の位置を、第１最前位置と表記する。
【００９２】
第１最前位置算出部２１２０は、まず、挿入キーのうち、開始オフセット２２４−（ｉ−１）が開始位置であり、かつ大きさが部分キー２２２−（ｉ−１）と同じサイズの値列と、部分キー２２２−（ｉ−１）とを比較する。そして、この２つの値列の間において同一の位置に異なる値がある場合は、値が異なる位置のうち最前の位置を、第１最前位置とする。一方、これら２つの値列が同一である場合、第１最前位置算出部２１２０は、全体キー４１２−（ｉ−１）を取得する。そして、取得した全体キー４１２−（ｉ−１）と挿入キーとを比較することで、第１最前位置を算出する。具体的には、全体キー４１２−（ｉ−１）と挿入キーとの間において、同一の位置における値が異なる最前の位置を、第１最前位置とする。
【００９３】
なお、第１最前位置算出部２１２０は、全体キー４１２−（ｉ−１）を、ノード１００によって構成されるインデックスツリーのうち、ノード１００−ｉを始点とする部分木を辿ることによって取得する。ここで、リーフノード以外のノード１００に格納されているエントリ２００は、そのエントリ２００を示すノード１００の下位にあるノードのうち、そのエントリ２００と同一の全体キー４１２に対応するノードへのポインタ（以下、ノードポインタ）を有する。そして、リーフノードは、レコードへのポインタを有している。したがって、全体キー４１２−（ｉ−１）は、ノード１００−ｉを始点とする部分木を次のように辿ることで取得することができる。まず、エントリ２００−（ｉ−１）が有するノードポインタによって示されるノード１００を取得する。このノード１００がリーフノードでなければ、このノード１００に格納されているエントリ２００のうち、順位が最小であるエントリ２００に格納されているノードポインタによって示されているノード１００をさらに取得する。以降、リーフノードに到達するまで、ノード１００に格納されているエントリ２００のうち、順位が最小であるエントリ２００に格納されているノードポインタを辿る。そして、リーフノードによって示されているレコード４１０を取得することで、全体キー４１２−（ｉ−１）を取得する。
【００９４】
＜第２最前位置算出部２１３０＞
第２最前位置算出部２１３０は、挿入順位の一つ前の順位（ｉ＋１）にあるエントリ２００−（ｉ＋１）が示すインデックス情報２２０−（ｉ＋１）と挿入キーとを比較する。ここで、エントリ２００−（ｉ＋１）を直後エントリとも表記する。こうすることで、第２最前位置算出部２１３０は、部分キー２２２−（ｉ＋１）の元である全体キー４１２−（ｉ＋１）と挿入キーとの間において、同一位置における値が異なる最前の位置を算出する。ここで、算出された最前の位置を、第２最前位置と表記する。
【００９５】
第２最前位置算出部２１３０は、まず、挿入キーのうち、開始オフセット２２４−（ｉ＋１）が開始位置であり、かつ大きさが部分キー２２２−（ｉ＋１）と同じである値列と、部分キー２２２−（ｉ＋１）とを比較する。そして、この２つの値列の間において同一の位置に異なる値がある場合は、値が異なる位置のうち最前の位置を、第２最前位置とする。一方、これら２つの値列が同一である場合、最前位置算出部２１２０は、全体キー４１２−（ｉ＋１）を取得する。そして、取得した全体キー４１２−（ｉ＋１）と挿入キーとを比較することで、第２最前位置を算出する。具体的には、全体キー４１２−（ｉ＋１）と挿入キーとの間において、同一の位置における値が異なる最前の位置を、第２最前位置とする。
【００９６】
なお、第２最前位置算出部２１３０は、第１最前位置算出部２１２０が全体キー４１２−（ｉ−１）を取得する方法と同様にインデックスツリーの部分木を辿ることで、全体キー４１２−（ｉ＋１）を取得する。
【００９７】
＜インデックス情報生成部２１４０＞
インデックス情報生成部２１４０は、挿入エントリによって示されるインデックス情報２２０を生成する。インデックス情報生成部２１４０は、挿入エントリによって示されるインデックス情報２２０が有する開始オフセット２２４に、第１最前位置算出部２１２０によって算出された第１最前位置を設定する。また、インデックス情報生成部２１４０は、挿入エントリによって示されるインデックス情報２２０が有する部分キー２２２に、挿入キーの一部である値列を設定する。この値列は、開始位置が第１最前位置である。また、この値列の終了位置は、第２最前位置と、第１最前位置に第１サイズを足した値から１を引いた値とのうち、大きい方の値である。両者が等しい場合は、その値を終了位置とする。
【００９８】
ここで、開始位置が第１最前位置であり、終了位置が「第１最前位置に第１サイズを足した値から１を引いた値」である場合、部分キー２２２の大きさは第１サイズとなる。したがって、第２最前位置が「第１最前位置に第１サイズを足した値から１を引いた値」より小さい場合、開始位置が第１最前位置であり、終了位置が第２最前位置である値列の大きさは、第１サイズより小さくなる。そこで、インデックス情報生成部２１４０は、部分キー２２２の大きさを少なくとも第１サイズ以上にするために、第２最前位置が「第１最前位置に第１サイズを足した値から１を引いた値」より小さい場合は、「第１最前位置に第１サイズを足した値から１を引いた値」を終了位置とする。
【００９９】
＜エントリ生成部２０９０＞
実施形態４のエントリ生成部２０９０は、インデックス情報生成部２１４０によって生成されたインデックス情報２２０を取得する。これにより、エントリ生成部２０９０は、挿入キーに基づいて生成されたインデックス情報２２０を示すエントリ２００を生成する。
【０１００】
＜処理の流れ＞
図１０は、実施形態４のエントリ処理装置２０００によって実行される処理の流れを示すフローチャートである。なお、記載を簡潔にするため、第１最前順位をＭ１、第２最前順位をＭ２、第１サイズをＷとも表記する。
【０１０１】
ステップＳ４０２において、挿入キー取得部２１００は、挿入キーを取得する。ステップＳ４０４において、挿入順位算出部２１１０は、挿入順位を算出する。ステップＳ４０６において、第１最前位置算出部２１２０は第１最前順位Ｍ１を算出する。ステップＳ４０８において、第２最前位置算出部２１３０は、第２最前順位Ｍ２を算出する。ステップＳ４１０において、インデックス情報生成部２１４０は、挿入エントリによって示されるインデックス情報２２０の開始オフセット２２４にＭ１を設定する。
【０１０２】
ステップＳ４１２において、インデックス情報生成部２１４０は、「（Ｍ１＋Ｗ−１）≧Ｍ２」であるか否かを判定する。「（Ｍ１＋Ｗ−１）≧Ｍ２」である場合（ステップＳ４１２：ＹＥＳ）、図１０の処理はステップＳ４１４に進む。一方、「（Ｍ１＋Ｗ−１）≧Ｍ２」でない場合（ステップＳ４１２：ＮＯ）、図１０の処理はステップＳ４１６に進む。
【０１０３】
ステップＳ４１４において、インデックス情報生成部２１４０は、終了位置Ｘに、「Ｍ１＋Ｗ−１」を代入する。
【０１０４】
ステップＳ４１６において、インデックス情報生成部２１４０は、終了位置ＸにＭ２を代入する。
【０１０５】
ステップＳ４１８において、インデックス情報生成部２１４０は、挿入エントリによって示されるインデックス情報２２０の部分キー２２２に、挿入キーのうち、開始位置がＭ１であり、終了位置がＸである値列を設定する。
【０１０６】
＜作用・効果＞
実施形態４によれば、エントリ処理装置２０００は、挿入キーに対応するエントリ２００を生成する。ここで、エントリ処理装置２０００は、挿入キーに対応するエントリ２００を生成する際、そのエントリ２００と、そのエントリ２００を挿入する順位の前後にあるエントリ２００との比較を行うことで、挿入キーに対応するエントリ２００を生成することができる。したがって、挿入キーに対応するエントリ２００を生成する際に、比較するエントリ２００の数が少ないため、エントリ２００の挿入にかかる時間が短い。
【０１０７】
[実施形態５]
図１１は、実施形態５に係るエントリ処理装置２０００を示すブロック図である。図１１において、矢印は情報の流れを表している。さらに、図１１において、各ブロックは、ハードウエア単位の構成ではなく、機能単位の構成を表している。以下で説明する点を除き、実施形態５のエントリ処理装置２０００は、実施形態４のエントリ処理装置２０００と同様である。
【０１０８】
実施形態５のエントリ処理装置２０００は、挿入順位の一つ前の順位にある直前エントリと、挿入順位の一つ後の順位にある直後エントリを更新する機能を有する。そのために、実施形態５のエントリ処理装置２０００は、直前エントリ更新部２１６０及び直後エントリ更新部２１８０を有する。
【０１０９】
＜直前エントリ更新部２１６０＞
直前エントリ更新部２１６０は、直前エントリの更新を行う。まず、直前エントリ更新部２１６０は、第１最前位置から直前エントリが示すインデックス情報２２０の開始オフセット２２４を引いた値に１を加えた値と、直前エントリが示すインデックス情報２２０の部分キー２２２の大きさとを比較する。第１最前位置から直前エントリが示すインデックス情報２２０の開始オフセット２２４を引いた値に１を加えた値の方が大きい場合、直前エントリ更新部２１６０は、直前エントリが示すインデックス情報２２０の部分キー２２２を更新する。
【０１１０】
具体的には、この部分キー２２２に、直前エントリに対応する全体キー４１２のうち、直前エントリが示すインデックス情報２２０の開始オフセット２２４が開始位置であり、かつ大きさが、第１最前位置から直前エントリによって示されるインデックス情報２２０の開始オフセット２２４を引いた値に１を加えた値である値列を設定する。言い換えると、この部分キー２２２に設定される値列は、直前エントリに対応する全体キー４１２のうち、直前エントリが示すインデックス情報２２０の開始オフセット２２４が開始位置であり、第１最前位置が終了位置である。つまり、直前エントリ更新部２１６０は、直前エントリに対応する全体キー４１２における部分キー２２２の終了位置を第１最前位置に変更することで部分キー２２２の大きさが大きくなる場合に、その部分キー２２２の終了位置が第１最前位置になるように、その部分キー２２２を更新する。
【０１１１】
さらに、直前エントリ更新部２１６０は、更新前の部分キー２２２のサイズが第１サイズ以下であり、更新後の部分キー２２２のサイズが第１サイズより大きい場合、直前エントリの内部に格納されていたインデックス情報２２０を、外部領域３００へ格納する。そして、直前エントリ更新部２１６０は、直前エントリの内部に、外部領域３００に格納した上記インデックス情報２２０へのポインタである外部ポインタ２３０を格納する。
【０１１２】
＜直後エントリ更新部２１８０＞
直後エントリ更新部２１８０は、直後エントリによって示される開始オフセット２２４と第２最前位置とが異なる場合に、直後エントリを更新する。まず、直後エントリ更新部２１８０は、直後エントリによって示される開始オフセット２２４に、第２最前位置を設定する。
【０１１３】
また、直後エントリ更新部２１８０は、「更新前の直後エントリに対応する全体キー４１２における部分キー２２２の終了位置から第２最前位置を引いた値に１を加算した値」を算出する。この値は、開始位置が第２最前位置であり、終了位置が更新前の部分キー２２２と同一である値列のサイズを表す。そして、「更新前の直後エントリに対応する全体キー４１２における部分キー２２２の終了位置から第２最前位置を引いた値に１を加算した値」が第１サイズ以上の場合、直後エントリ更新部２１８０は、直後エントリによって示されるエントリ２００の部分キー２２２に、直後エントリに対応する全体キー４１２のうち、開始位置が第２最前位置であり、終了位置が更新前の部分キー２２２と同一である値列を設定する。
【０１１４】
一方、「直後エントリに対応する全体キー４１２における部分キー２２２の終了位置から第２最前位置を引いた値に１を加算した値」が第１サイズより小さい場合、部分キー２２２の終了位置を更新しないと、部分キー２２２の大きさが第１サイズより小さくなってしまう。そこで、直後エントリ更新部２１８０は、直後エントリによって示されるエントリ２００の部分キー２２２に、直後エントリに対応する全体キー４１２のうち、開始位置が第２最前位置であり、大きさが第１サイズである値列を設定する。
【０１１５】
ここで、更新前の部分キー２２２の大きさが第１サイズより大きく、更新後の部分キー２２２の大きさが第１サイズ以下であるとする。この場合、更新前のインデックス情報２２０は外部領域３００に格納されているものの、更新後のインデックス情報２２０はエントリ２００に格納される必要がある。そこで、直後エントリ更新部２１８０は、更新前の部分キー２２２の大きさが第１サイズより大きく、更新後の部分キー２２２の大きさが第１サイズ以下である場合、外部領域３００に格納されていたインデックス情報２２０を、エントリ２００の内部に格納する。この際、直後エントリ更新部２１８０は、エントリ２００に格納されていたエントリ２００へのポインタを削除する。
【０１１６】
＜作用・効果＞
実施形態５のエントリ処理装置２０００によれば、挿入順位の１つ前にある直前エントリ、及び挿入順位の１つ後にある直後エントリの更新が行われる。ここで、実施形態５のエントリ処理装置２０００によれば、挿入エントリを挿入した際に更新されるのは、多くても直前エントリと直後エントリの２つだけである。そのため、挿入エントリの挿入に伴って更新されるエントリ２００が少ないため、例えば挿入エントリを挿入する際に同じノード１００に含まれる全てのエントリ２００を更新しなければいけない場合と比較し、エントリの更新にかかる時間が短い。
【０１１７】
[実施形態６]
図１２は、実施形態６に係るエントリ処理装置２０００を示すブロック図である。図１２において、矢印は情報の流れを表している。さらに、図１２において、各ブロックは、ハードウエア単位の構成ではなく、機能単位の構成を表している。以下で説明する点を除き、実施形態６のエントリ処理装置２０００は、実施形態４又は５のエントリ処理装置２０００と同様である。
【０１１８】
実施形態６のエントリ処理装置２０００は、挿入エントリをノード１００に挿入する前に、ノード１００を分割する機能を有する。ここで、ノード１００を分割するとは、１つのノード１００に含まれている複数のエントリ２００を、２つのノード１００に分けることを意味する。
【０１１９】
実施形態６のエントリ処理装置２０００は、分割順位取得部２２００、分割部２２２０、及び挿入ノード決定部２２４０を有する。
【０１２０】
＜分割順位取得部２２００＞
分割順位取得部２２００は、ノード１００を分割する順位である分割順位を取得する。以下、分割順位にあるエントリ２００を、基準エントリと表記する。ここで、分割順位の値は様々である。例えば分割順位は、ノード１００が有するエントリ２００の数の半分である。こうすることで、ノード１００が２つに等分割される。ただし、分割順位は、ノード１００が有するエントリ２００の数の半分でなくてもよい。
【０１２１】
＜分割部２２２０＞
分割部２２２０は、分割順位を基準として、ノード１００を分割する。例えば分割順位取得部２２００は、ノード１００に含まれるエントリ２００のうち、分割順位より大きい順位にあるエントリ２００、又は分割順位以上の順位にあるエントリ２００を、新たに生成した別のノード１００に移動する。
【０１２２】
なお、新しいノード１００に移動したエントリ２００のうち、そのノード１００の先頭になるエントリ２００については、更新が必要な場合がある。具体的には、そのエントリ２００が示すインデックス情報２２０の開始オフセット２２４が１でない場合、その開始オフセット２２４に１を設定する。そして、そのエントリ２００が示すインデックス情報２２０の部分キー２２２を、更新された開始オフセット２２４が開始位置であり、終了位置は更新前の部分キー２２２と同一となるように、部分キー２２２を更新する。
【０１２３】
＜挿入ノード決定部２２４０＞
挿入ノード決定部２２４０は、分割前のノード１００において分割順位にあったエントリ２００（以下、基準エントリ）が示すインデックス情報２２０と挿入キーとを比較することで、挿入エントリを、分割された２つのノードのどちらに挿入するかを決定する。例えば、分割部２２２０が、ノード１００に含まれるエントリ２００のうち、分割順位より大きい順位にあるエントリ２００を新たに生成した別のノード１００に移動したとする。この場合、挿入ノード決定部２２４０は、基準エントリに対応する全体キー４１２が挿入キーより小さければ、挿入エントリを、基準エントリを含まないノードに挿入することを決定する。一方、挿入ノード決定部２２４０は、基準エントリに対応する全体キー４１２が挿入キー以上ならば、挿入エントリを、基準エントリを含むノードに挿入することを決定する。
【０１２４】
なお、挿入エントリをノードに挿入する処理は、実施形態５のエントリ処理装置２０００が有する各機能構成部によって行われる。例えば、挿入エントリを、挿入先のノードにおけるどの順位に挿入するのかは、挿入順位算出部２１１０によって算出される。
【０１２５】
＜処理の流れ＞
図１３は、実施形態６のエントリ処理装置２０００によって実行される処理の流れを示すフローチャートである。ステップＳ５０２において、分割順位取得部２２００は、分割順位を取得する。ステップＳ５０４において、分割部２２２０は、ノードを分割する。ステップＳ５０６において、挿入ノード決定部２２４０は、分割された２つのノードのどちらに挿入エントリを挿入するかを決定する。
【０１２６】
なお、ノード１００の分割を行う場合、そのノード１００の上位にあるノード１００に、分割して新たに生成したノード１００に格納されている先頭のエントリ２００に対応する全体キー４１２を挿入する。つまり、分割されたノード１００の上位にあるノード１００を挿入先として、挿入キー取得部２１００に、分割して新たに生成したノード１００に格納されている先頭のエントリ２００に対応する全体キー４１２を入力する。なお、この挿入によってノード１００が分割する必要が生じた場合、このノード１００も分割する。このように、下位のノードから上位のノードに向かって、分割の必要がなくなるまで、順にノードを分割していく。
【０１２７】
＜作用・効果＞
実施形態６のエントリ２００によれば、ノード１００を分割することができる。ここで、例えばノード１００の分割は、新たなエントリ２００をノード１００に挿入しようとした時に、そのノード１００の内部にある領域が不足している場合に実行される。これにより、ノード１００の内部にエントリ２００を格納しきれなくなった場合でも、そのノード１００を分割することで、新たなエントリ２００をノード１００に格納できるようになる。
【０１２８】
以上、図面を参照して本発明の実施形態について述べたが、これらは本発明の例示であり、上記実施形態の組み合わせ、及び上記実施形態以外の様々な構成を採用することもできる。 
【０１２９】
以下、参考形態の例を付記する。
１．  検索対象のレコードのインデックス情報が格納されているインデックスツリーについて、そのインデックスツリーを構成するノードに格納されているエントリを処理するエントリ処理装置であって、
前記ノードは、前記インデックス情報を固有に示す前記エントリを、順位付けて格納しており、
前記インデックス情報は、
前記レコードを識別する値列である全体キーの一部を表す値列である部分キーと、その全体キーにおけるその部分キーの開始位置である開始オフセットとを有し、
そのインデックス情報を示す前記エントリの内部に格納されているか、又はそのエントリの外部にある外部領域に格納されており、
前記エントリは、
前記エントリの内部に格納されている場合、前記部分キーのサイズは所定の第１サイズであり、
前記インデックス情報が前記エントリの内部と外部のどちらに格納しているかを判別する領域識別情報を格納しており、
前記インデックス情報が前記外部領域に格納されている場合、そのインデックス情報へのポインタを格納しており、
前記インデックス情報が有する前記開始オフセットは、そのインデックス情報が有する前記部分キーの元である前記全体キーと、前記ノード内においてそのインデックス情報を示す前記エントリより順位が１つ前の前記エントリによって示される前記インデックス情報が有する前記部分キーの元である前記全体キーとの間において、同一位置における値が異なる最前の位置を示し、
前記ノードを格納する領域及び前記外部領域は、前記全体キーを含む前記レコードを格納する格納手段とは異なる格納手段に設けられており、
当該エントリ処理装置は、
前記領域識別情報を取得する領域識別情報取得手段と、
前記領域識別情報により、前記インデックス情報が前記エントリの内部に格納されていることが示されている場合、前記エントリから前記インデックス情報を取得し、前記領域識別情報により、前記インデックス情報が前記外部領域に格納されていることが示されている場合、そのエントリに格納されている前記ポインタによって示されている前記インデックス情報を取得するインデックス情報取得手段と、
を有するエントリ処理装置。
２．  検索対象の全体キーである検索キーを取得する検索キー取得手段と、
同一の前記ノードに含まれる前記エントリが示す前記インデックス情報の中から、前記部分キーが前記検索キー以下である前記インデックス情報のうち、前記部分キーが最大である前記インデックス情報を特定するインデックス情報特定手段と、
を有する１．に記載のエントリ処理装置。
３．  前記インデックス情報を取得し、そのインデックス情報が有する前記部分キーの大きさが前記第１サイズ以下である場合、そのインデックス情報を、生成する前記エントリの内部に格納し、そのインデックス情報が有する前記部分キーの大きさが前記第１サイズより大きい場合、そのインデックス情報を前記外部領域に格納した上で、その外部領域へのポインタを、生成する前記エントリの内部に格納するエントリ生成手段を有する２．に記載のエントリ処理装置。
４．  前記ノードに挿入する挿入エントリに対応付ける全体キーである挿入キーを取得する挿入キー取得手段と、
前記ノードにおいて前記挿入エントリを挿入する挿入順位を算出する挿入順位算出手段と、
前記挿入キーと、前記挿入順位より１つ前の順位にある直前エントリによって示される前記インデックス情報とを比較することで、前記直前エントリに対応する前記全体キーと前記挿入キーとの間において、同一位置における値が異なる最前の位置である第１最前位置を算出する第１最前位置算出手段と、
前記挿入キーと、前記挿入順位より１つ後の順位にある直後エントリによって示される前記インデックス情報とを比較することで、前記直後エントリに対応する前記全体キーと前記挿入キーとの間において、同一位置における値が異なる最前の位置である第２最前位置を算出する第２最前位置算出手段と、
前記挿入エントリが示す前記インデックス情報の前記部分キーに、前記挿入キーに含まれる値列であり、開始位置が、前記第１最前位置であり、終了位置が、前記第２最前位置と、前記第１最前位置に前記第１サイズを足した値から１を引いた値とのうち、大きい方の値である値列を設定し、前記挿入エントリが示す前記インデックス情報の前記開始オフセットに前記第１最前位置を設定するインデックス情報生成手段と、を有し、
前記エントリ生成手段は、前記インデックス情報生成手段によって生成された前記インデックス情報を取得する、
３．に記載のエントリ処理装置。
５．  前記第１最前位置算出手段は、前記直前エントリによって示される前記インデックス情報が有する前記部分キーと、前記挿入キーのうち、前記直前エントリによって示される前記インデックス情報が有する前記開始オフセットが開始位置であり、前記部分キーと同一のサイズである値列とを比較し、この２つが等しい場合、前記部分キーの元となる前記全体キーを取得し、取得した前記全体キーと前記挿入キーとを比較することで前記第１最前位置を算出し、
前記第２最前位置算出手段は、前記直後エントリによって示される前記インデックス情報が有する前記部分キーと、前記挿入キーのうち、前記直後エントリによって示される前記インデックス情報が有する前記開始オフセットが開始位置であり、前記部分キーと同一のサイズである値列とを比較し、この２つが等しい場合、前記部分キーの元となる前記全体キーを取得し、取得した前記全体キーと前記挿入キーとを比較することで前記第２最前位置を算出し、
前記第１最前位置算出手段及び前記第２最前位置算出手段は、前記エントリに対応する前記全体キーを取得する場合、前記インデックスツリーを、そのエントリを含む前記ノードを始点として下位に辿ることで取得する４．に記載のエントリ処理装置。
６．  前記第１最前位置と、前記直前エントリよって示される前記インデックス情報が有する前記開始オフセットとの差に１を加算した値が、そのインデックス情報が有する前記部分キーのサイズより大きい場合、その部分キーを、前記直前エントリに対応する前記全体キーのうち、開始位置が、更新前の前記直前エントリよって示される前記インデックス情報が有する前記開始オフセットであり、終了位置が、前記第１最前位置である値列に更新する直前エントリ更新手段と、
前記直後エントリによって示される前記インデックス情報の前記部分キーのサイズが前記第１サイズより大きく、かつ前記第２最前位置と前記直後エントリによって示される前記インデックス情報が有する前記開始オフセットとの差に１を加算した値が、そのインデックス情報が有する前記部分キーのサイズより小さい場合、その部分キーを、前記直後エントリに対応する前記全体キーのうち、開始位置が、更新前の前記直後エントリによって示される前記インデックス情報が有する前記開始オフセットであり、終了位置が、前記第２最前位置である値列に更新する直後エントリ更新手段と、を有し、
前記直前エントリ更新手段は、更新前の前記部分キーのサイズが前記第１サイズ以下であり、かつ更新後の前記部分キーのサイズが前記第１サイズより大きい場合、インデックス情報更新する前記インデックス情報を前記外部領域に格納した上で、そのインデックス情報を示す前記直前エントリの内部に、そのインデックス情報へのポインタを格納し、
前記直後エントリ更新手段は、更新前の前記部分キーのサイズが前記第１サイズより大きく、かつ更新後の前記部分キーのサイズが前記第１サイズ以下である場合、更新する前記インデックス情報を、そのインデックス情報を示す前記直後エントリの内部に格納する、
４．又は５．に記載のエントリ処理装置。
７．  前記ノードを分割する順位である分割順位を取得する分割順位取得手段と、
前記分割順位を基準として、前記ノードを２つに分割する分割手段と、
前記分割順位にある前記エントリが示す前記インデックス情報と前記挿入キーとを比較することで、２つに分割された前記ノードのどちらに前記挿入エントリを挿入するかを決定する挿入ノード決定手段と、
を有する４．乃至６．いずれか一項に記載のエントリ処理装置。
８．  コンピュータによって実行される制御方法であり、検索対象のレコードのインデックス情報が格納されているインデックスツリーについて、そのインデックスツリーを構成するノードに格納されているエントリを処理する制御方法であって、
前記ノードは、前記インデックス情報を固有に示す前記エントリを、順位付けて格納しており、
前記インデックス情報は、
前記レコードを識別する値列である全体キーの一部を表す値列である部分キーと、その全体キーにおけるその部分キーの開始位置である開始オフセットとを有し、
そのインデックス情報を示す前記エントリの内部に格納されているか、又はそのエントリの外部にある外部領域に格納されており、
前記エントリは、
前記エントリの内部に格納されている場合、前記部分キーのサイズは所定の第１サイズであり、
前記インデックス情報が前記エントリの内部と外部のどちらに格納しているかを判別する領域識別情報を格納しており、
前記インデックス情報が前記外部領域に格納されている場合、そのインデックス情報へのポインタを格納しており、
前記インデックス情報が有する前記開始オフセットは、そのインデックス情報が有する前記部分キーの元である前記全体キーと、前記ノード内においてそのインデックス情報を示す前記エントリより順位が１つ前の前記エントリによって示される前記インデックス情報が有する前記部分キーの元である前記全体キーとの間において、同一位置における値が異なる最前の位置を示し、
前記ノードを格納する領域及び前記外部領域は、前記全体キーを含む前記レコードを格納する格納手段とは異なる格納手段に設けられており、
当該制御方法は、
前記領域識別情報を取得する領域識別情報取得ステップと、
前記領域識別情報により、前記インデックス情報が前記エントリの内部に格納されていることが示されている場合、前記エントリから前記インデックス情報を取得し、前記領域識別情報により、前記インデックス情報が前記外部領域に格納されていることが示されている場合、そのエントリに格納されている前記ポインタによって示されている前記インデックス情報を取得するインデックス情報取得ステップと、
を有する制御方法。
９．  検索対象の全体キーである検索キーを取得する検索キー取得ステップと、
同一の前記ノードに含まれる前記エントリが示す前記インデックス情報の中から、前記部分キーが前記検索キー以下である前記インデックス情報のうち、前記部分キーが最大である前記インデックス情報を特定するインデックス情報特定ステップと、
を有する８．に記載の制御方法。
１０．  前記インデックス情報を取得し、そのインデックス情報が有する前記部分キーの大きさが前記第１サイズ以下である場合、そのインデックス情報を、生成する前記エントリの内部に格納し、そのインデックス情報が有する前記部分キーの大きさが前記第１サイズより大きい場合、そのインデックス情報を前記外部領域に格納した上で、その外部領域へのポインタを、生成する前記エントリの内部に格納するエントリ生成ステップを有する９．に記載の制御方法。
１１．  前記ノードに挿入する挿入エントリに対応付ける全体キーである挿入キーを取得する挿入キー取得ステップと、
前記ノードにおいて前記挿入エントリを挿入する挿入順位を算出する挿入順位算出ステップと、
前記挿入キーと、前記挿入順位より１つ前の順位にある直前エントリによって示される前記インデックス情報とを比較することで、前記直前エントリに対応する前記全体キーと前記挿入キーとの間において、同一位置における値が異なる最前の位置である第１最前位置を算出する第１最前位置算出ステップと、
前記挿入キーと、前記挿入順位より１つ後の順位にある直後エントリによって示される前記インデックス情報とを比較することで、前記直後エントリに対応する前記全体キーと前記挿入キーとの間において、同一位置における値が異なる最前の位置である第２最前位置を算出する第２最前位置算出ステップと、
前記挿入エントリが示す前記インデックス情報の前記部分キーに、前記挿入キーに含まれる値列であり、開始位置が、前記第１最前位置であり、終了位置が、前記第２最前位置と、前記第１最前位置に前記第１サイズを足した値から１を引いた値とのうち、大きい方の値である値列を設定し、前記挿入エントリが示す前記インデックス情報の前記開始オフセットに前記第１最前位置を設定するインデックス情報生成ステップと、を有し、
前記エントリ生成ステップは、前記インデックス情報生成ステップによって生成された前記インデックス情報を取得する、
１０．に記載の制御方法。
１２．  前記第１最前位置算出ステップは、前記直前エントリによって示される前記インデックス情報が有する前記部分キーと、前記挿入キーのうち、前記直前エントリによって示される前記インデックス情報が有する前記開始オフセットが開始位置であり、前記部分キーと同一のサイズである値列とを比較し、この２つが等しい場合、前記部分キーの元となる前記全体キーを取得し、取得した前記全体キーと前記挿入キーとを比較することで前記第１最前位置を算出し、
前記第２最前位置算出ステップは、前記直後エントリによって示される前記インデックス情報が有する前記部分キーと、前記挿入キーのうち、前記直後エントリによって示される前記インデックス情報が有する前記開始オフセットが開始位置であり、前記部分キーと同一のサイズである値列とを比較し、この２つが等しい場合、前記部分キーの元となる前記全体キーを取得し、取得した前記全体キーと前記挿入キーとを比較することで前記第２最前位置を算出し、
前記第１最前位置算出ステップ及び前記第２最前位置算出ステップは、前記エントリに対応する前記全体キーを取得する場合、前記インデックスツリーを、そのエントリを含む前記ノードを始点として下位に辿ることで取得する１１．に記載の制御方法。
１３．  前記第１最前位置と、前記直前エントリよって示される前記インデックス情報が有する前記開始オフセットとの差に１を加算した値が、そのインデックス情報が有する前記部分キーのサイズより大きい場合、その部分キーを、前記直前エントリに対応する前記全体キーのうち、開始位置が、更新前の前記直前エントリよって示される前記インデックス情報が有する前記開始オフセットであり、終了位置が、前記第１最前位置である値列に更新する直前エントリ更新ステップと、
前記直後エントリによって示される前記インデックス情報の前記部分キーのサイズが前記第１サイズより大きく、かつ前記第２最前位置と前記直後エントリによって示される前記インデックス情報が有する前記開始オフセットとの差に１を加算した値が、そのインデックス情報が有する前記部分キーのサイズより小さい場合、その部分キーを、前記直後エントリに対応する前記全体キーのうち、開始位置が、更新前の前記直後エントリによって示される前記インデックス情報が有する前記開始オフセットであり、終了位置が、前記第２最前位置である値列に更新する直後エントリ更新ステップと、を有し、
前記直前エントリ更新ステップは、更新前の前記部分キーのサイズが前記第１サイズ以下であり、かつ更新後の前記部分キーのサイズが前記第１サイズより大きい場合、インデックス情報更新する前記インデックス情報を前記外部領域に格納した上で、そのインデックス情報を示す前記直前エントリの内部に、そのインデックス情報へのポインタを格納し、
前記直後エントリ更新ステップは、更新前の前記部分キーのサイズが前記第１サイズより大きく、かつ更新後の前記部分キーのサイズが前記第１サイズ以下である場合、更新する前記インデックス情報を、そのインデックス情報を示す前記直後エントリの内部に格納する、
１１．又は１２．に記載の制御方法。
１４．  前記ノードを分割する順位である分割順位を取得する分割順位取得ステップと、
前記分割順位を基準として、前記ノードを２つに分割する分割ステップと、
前記分割順位にある前記エントリが示す前記インデックス情報と前記挿入キーとを比較することで、２つに分割された前記ノードのどちらに前記挿入エントリを挿入するかを決定する挿入ノード決定ステップと、
を有する１１．乃至１３．いずれか一項に記載の制御方法。
１５．  検索対象のレコードのインデックス情報が格納されているインデックスツリーについて、そのインデックスツリーを構成するノードに格納されているエントリを処理する機能をコンピュータに持たせるプログラムであって、
前記ノードは、前記インデックス情報を固有に示す前記エントリを、順位付けて格納しており、
前記インデックス情報は、
前記レコードを識別する値列である全体キーの一部を表す値列である部分キーと、その全体キーにおけるその部分キーの開始位置である開始オフセットとを有し、
そのインデックス情報を示す前記エントリの内部に格納されているか、又はそのエントリの外部にある外部領域に格納されており、
前記エントリは、
前記エントリの内部に格納されている場合、前記部分キーのサイズは所定の第１サイズであり、
前記インデックス情報が前記エントリの内部と外部のどちらに格納しているかを判別する領域識別情報を格納しており、
前記インデックス情報が前記外部領域に格納されている場合、そのインデックス情報へのポインタを格納しており、
前記インデックス情報が有する前記開始オフセットは、そのインデックス情報が有する前記部分キーの元である前記全体キーと、前記ノード内においてそのインデックス情報を示す前記エントリより順位が１つ前の前記エントリによって示される前記インデックス情報が有する前記部分キーの元である前記全体キーとの間において、同一位置における値が異なる最前の位置を示し、
前記ノードを格納する領域及び前記外部領域は、前記全体キーを含む前記レコードを格納する格納手段とは異なる格納手段に設けられており、
当該プログラムは、前記コンピュータに、
前記領域識別情報を取得する領域識別情報取得機能と、
前記領域識別情報により、前記インデックス情報が前記エントリの内部に格納されていることが示されている場合、前記エントリから前記インデックス情報を取得し、前記領域識別情報により、前記インデックス情報が前記外部領域に格納されていることが示されている場合、そのエントリに格納されている前記ポインタによって示されている前記インデックス情報を取得するインデックス情報取得機能と、
を持たせるプログラム。
１６．    検索対象の全体キーである検索キーを取得する検索キー取得機能と、
同一の前記ノードに含まれる前記エントリが示す前記インデックス情報の中から、前記部分キーが前記検索キー以下である前記インデックス情報のうち、前記部分キーが最大である前記インデックス情報を特定するインデックス情報特定機能と、
を前記コンピュータに持たせる１５．に記載のプログラム。
１７．  前記インデックス情報を取得し、そのインデックス情報が有する前記部分キーの大きさが前記第１サイズ以下である場合、そのインデックス情報を、生成する前記エントリの内部に格納し、そのインデックス情報が有する前記部分キーの大きさが前記第１サイズより大きい場合、そのインデックス情報を前記外部領域に格納した上で、その外部領域へのポインタを、生成する前記エントリの内部に格納するエントリ生成機能を前記コンピュータに持たせる１６．に記載のプログラム。
１８．  前記ノードに挿入する挿入エントリに対応付ける全体キーである挿入キーを取得する挿入キー取得機能と、
前記ノードにおいて前記挿入エントリを挿入する挿入順位を算出する挿入順位算出機能と、
前記挿入キーと、前記挿入順位より１つ前の順位にある直前エントリによって示される前記インデックス情報とを比較することで、前記直前エントリに対応する前記全体キーと前記挿入キーとの間において、同一位置における値が異なる最前の位置である第１最前位置を算出する第１最前位置算出機能と、
前記挿入キーと、前記挿入順位より１つ後の順位にある直後エントリによって示される前記インデックス情報とを比較することで、前記直後エントリに対応する前記全体キーと前記挿入キーとの間において、同一位置における値が異なる最前の位置である第２最前位置を算出する第２最前位置算出機能と、
前記挿入エントリが示す前記インデックス情報の前記部分キーに、前記挿入キーに含まれる値列であり、開始位置が、前記第１最前位置であり、終了位置が、前記第２最前位置と、前記第１最前位置に前記第１サイズを足した値から１を引いた値とのうち、大きい方の値である値列を設定し、前記挿入エントリが示す前記インデックス情報の前記開始オフセットに前記第１最前位置を設定するインデックス情報生成機能と、を前記コンピュータに持たせ、
前記エントリ生成機能は、前記インデックス情報生成機能によって生成された前記インデックス情報を取得する、
１７．に記載のプログラム。
１９．  前記第１最前位置算出機能は、前記直前エントリによって示される前記インデックス情報が有する前記部分キーと、前記挿入キーのうち、前記直前エントリによって示される前記インデックス情報が有する前記開始オフセットが開始位置であり、前記部分キーと同一のサイズである値列とを比較し、この２つが等しい場合、前記部分キーの元となる前記全体キーを取得し、取得した前記全体キーと前記挿入キーとを比較することで前記第１最前位置を算出し、
前記第２最前位置算出機能は、前記直後エントリによって示される前記インデックス情報が有する前記部分キーと、前記挿入キーのうち、前記直後エントリによって示される前記インデックス情報が有する前記開始オフセットが開始位置であり、前記部分キーと同一のサイズである値列とを比較し、この２つが等しい場合、前記部分キーの元となる前記全体キーを取得し、取得した前記全体キーと前記挿入キーとを比較することで前記第２最前位置を算出し、
前記第１最前位置算出機能及び前記第２最前位置算出機能は、前記エントリに対応する前記全体キーを取得する場合、前記インデックスツリーを、そのエントリを含む前記ノードを始点として下位に辿ることで取得する１８．に記載のプログラム。
２０．  前記第１最前位置と、前記直前エントリよって示される前記インデックス情報が有する前記開始オフセットとの差に１を加算した値が、そのインデックス情報が有する前記部分キーのサイズより大きい場合、その部分キーを、前記直前エントリに対応する前記全体キーのうち、開始位置が、更新前の前記直前エントリよって示される前記インデックス情報が有する前記開始オフセットであり、終了位置が、前記第１最前位置である値列に更新する直前エントリ更新機能と、
前記直後エントリによって示される前記インデックス情報の前記部分キーのサイズが前記第１サイズより大きく、かつ前記第２最前位置と前記直後エントリによって示される前記インデックス情報が有する前記開始オフセットとの差に１を加算した値が、そのインデックス情報が有する前記部分キーのサイズより小さい場合、その部分キーを、前記直後エントリに対応する前記全体キーのうち、開始位置が、更新前の前記直後エントリによって示される前記インデックス情報が有する前記開始オフセットであり、終了位置が、前記第２最前位置である値列に更新する直後エントリ更新機能と、前記コンピュータに持たせ、
前記直前エントリ更新機能は、更新前の前記部分キーのサイズが前記第１サイズ以下であり、かつ更新後の前記部分キーのサイズが前記第１サイズより大きい場合、インデックス情報更新する前記インデックス情報を前記外部領域に格納した上で、そのインデックス情報を示す前記直前エントリの内部に、そのインデックス情報へのポインタを格納し、
前記直後エントリ更新機能は、更新前の前記部分キーのサイズが前記第１サイズより大きく、かつ更新後の前記部分キーのサイズが前記第１サイズ以下である場合、更新する前記インデックス情報を、そのインデックス情報を示す前記直後エントリの内部に格納する、
１８．又は１９．に記載のプログラム。
２１．  前記ノードを分割する順位である分割順位を取得する分割順位取得機能と、
前記分割順位を基準として、前記ノードを２つに分割する分割機能と、
前記分割順位にある前記エントリが示す前記インデックス情報と前記挿入キーとを比較することで、２つに分割された前記ノードのどちらに前記挿入エントリを挿入するかを決定する挿入ノード決定機能と、
を前記コンピュータに持たせる１８．乃至２０．いずれか一項に記載のプログラム。
【符号の説明】
【０１３０】
１００ ノード
２００ エントリ
２１０ 領域識別情報
２２０ インデックス情報
２２２ 部分キー
２２４ 開始オフセット
２３０ 外部ポインタ
３００ 外部領域
４００ レコード格納部
４１０ レコード
４１２ 全体キー
４１４ データ
１０２０ バス
１０４０ プロセッサ
１０６０ メモリ
１０８０ ストレージ
１２２０ 領域識別情報取得モジュール
１２４０ インデックス情報取得モジュール
２０００ エントリ処理装置
２０２０ 領域識別情報取得部
２０４０ インデックス情報取得部
２０６０ 検索キー取得部
２０８０ インデックス情報特定部
２０９０ エントリ生成部
２１００ 挿入キー取得部
２１１０ 挿入順位算出部
２１２０ 第１最前位置算出部
２１３０ 第２最前位置算出部
２１４０ インデックス情報生成部
２１６０ 直前エントリ更新部
２１８０ 直後エントリ更新部
２２００ 分割順位取得部
２２２０ 分割部
２２４０ 挿入ノード決定部
【図１】
2014235450.tif 000003
【図２】
2014235450.tif 000004
【図３】
2014235450.tif 000005
【図４】
2014235450.tif 000006
【図５】
2014235450.tif 000007
【図６】
2014235450.tif 000008
【図７】
2014235450.tif 000009
【図８】
2014235450.tif 000010
【図９】
2014235450.tif 000011
【図１０】
2014235450.tif 000012
【図１１】
2014235450.tif 000013
【図１２】
2014235450.tif 000014
【図１３】
2014235450.tif 000015