(57)【特許請求の範囲】
【請求項１】
挿入処理部、累積移動平均計算部、および分割処理部を含む記憶装置が実行する多重検索ツリーのノード分割方法であって、
前記挿入処理部が、第１ノードにレコードを挿入するステップ、
前記累積移動平均計算部が、前記レコードの前記第１ノード内の位置値に基づいて前記第１ノードの累積移動平均を計算するステップ、
前記分割処理部が、前記累積移動平均に基づいて前記第１ノードの分割位置を計算するステップ、および前記分割位置を基準として前記第１ノードを第２ノードおよび第３ノードに分割するステップ
を含む、多重検索ツリーのノード分割方法。
【請求項２】
前記位置の値は、前記レコードが挿入されたスロットの番号を前記第１ノード内のレコードの数で割った値である、請求項１に記載の多重検索ツリーのノード分割方法。
【請求項３】
前記第１ノードの累積移動平均を計算するステップは、
前記レコードが挿入されたスロットの番号を前記第１ノード内のレコードの数で割った値、前記累積移動平均、前記第１ノード内のレコードの数、および前記第１ノードに任意のレコードが挿入されるたびに１ずつ増加する定数に基づいて前記累積移動平均を更新するステップ
を含む、請求項１に記載の多重検索ツリーのノード分割方法。
【請求項４】
前記累積移動平均は、下記の数式（１）に基づいて計算される、請求項３に記載の多重検索ツリーのノード分割方法。
【数１】
0005774213.tif 000004
ＣＡｉ−１は、前記レコードが挿入される前の前記第１ノードの累積移動平均である。ＣＡｉは、前記レコードが挿入された後に更新された前記累積移動平均である。Ｉは、ｉおよび前記第１ノード内のレコードの数のうちの最小値である。ｘｉは、前記レコードが挿入されたスロットの番号を前記第１ノード内のレコードの数で割った値である。ｉは前記第１ノードに任意のレコードが挿入されるたびに１ずつ増加する定数である。
【請求項５】
前記累積移動平均が指定された範囲内の値である場合、前記分割位置は、昇順に整列した分割対象レコードの全体の長さの中間である、請求項１に記載の多重検索ツリーのノード分割方法。
【請求項６】
前記累積移動平均が指定された範囲内の値である場合、前記分割位置は、昇順に整列した分割対象レコードの全体の長さを予め指定された割合で割る位置である、請求項１に記載の多重検索ツリーのノード分割方法。
【請求項７】
前記累積移動平均が指定された範囲内の値である場合、前記分割位置は、昇順に整列した分割対象レコードの全体の長さを前記累積移動平均の割合で分割する位置である、請求項１に記載の多重検索ツリーのノード分割方法。
【請求項８】
前記多重検索ツリーのレコードの長さは可変である、請求項１に記載の多重検索ツリーのノード分割方法。
【請求項９】
前記レコードはデータベースのインデックスである、請求項１に記載の多重検索ツリーのノード分割方法。
【請求項１０】
前記多重検索ツリーはＢツリーまたはＢ＋ツリーである、請求項１に記載の多重検索ツリーのノード分割方法。
【請求項１１】
記憶装置に、請求項１乃至１０のいずれか一項に記載の多重検索ツリーのノード分割方法を実行させるためのプログラムを記録した、コンピュータ読み取り可能な記録媒体。
【請求項１２】
多重検索ツリーの第１ノードにレコードを挿入する挿入処理部、
前記レコードの前記第１ノード内の位置値に基づいて前記第１ノードの累積移動平均を計算する累積移動平均計算部、および
前記累積移動平均に基づいて前記第１ノードの分割位置を計算し、前記分割位置を基準として前記第１ノードを第２ノードおよび第３ノードに分割する分割処理部
を含む、記憶装置。
【請求項１３】
前記位置の値は、前記レコードが挿入されたスロットの番号を前記第１ノード内のレコードの数で割った値である、請求項１２に記載の記憶装置。
【請求項１４】
前記累積移動平均計算部は、前記レコードが挿入されたスロットの番号を前記第１ノード内のレコードの数で割った値で、前記累積移動平均、前記第１ノード内のレコードの数、および前記第１ノードに任意のレコードが挿入されるたびに１ずつ増加する定数に基づいて前記累積移動平均を更新することにより、前記第１ノードの累積移動平均を計算する、請求項１２に記載の記憶装置。
【請求項１５】
前記累積移動平均計算部は、下記の数式（２）に基づいて前記累積移動平均を計算する、請求項１２に記載の記憶装置。
【数２】
0005774213.tif 000005
ＣＡｉ−１は、前記レコードが挿入される前の前記第１ノードの累積移動平均である。ＣＡｉは、前記レコードが挿入された後に更新された前記累積移動平均である。Ｉは、ｉおよび前記第１ノード内のレコードの数のうちの最小値である。ｘｉは、前記レコードが挿入されたスロットの番号を前記第１ノード内のレコードの数で割った値である。ｉは、前記第１ノードに任意のレコードが挿入されるたびに１ずつ増加する定数である。
【請求項１６】
前記分割処理部は、前記累積移動平均が指定された範囲内の値である場合、昇順に整列した分割対象レコードの全体の長さの中間を前記分割位置として決める、請求項１２に記載の記憶装置。
【請求項１７】
前記分割処理部は、前記累積移動平均が指定された範囲内の値である場合、昇順に整列した分割対象レコードの全体の長さを予め指定された割合で割る位置を前記分割位置として決める、請求項１２に記載の記憶装置。
【請求項１８】
前記分割処理部は、前記累積移動平均が指定された範囲内の値である場合、昇順に整列した分割対象レコードの全体の長さを前記累積移動平均の割合で割る位置を前記分割位置として決める、請求項１２に記載の記憶装置。
【請求項１９】
前記多重検索ツリーのレコードの長さは可変である、請求項１２に記載の記憶装置。
【発明の詳細な説明】
【技術分野】
【０００１】
以下に示される実施形態は、多重検索ツリーを提供するための方法および装置に関する。
【０００２】
累積移動平均に基づいて多重検索ツリーのノードを分割する方法と、この方法を使用する多重検索ツリーを提供する記憶装置が開示される。
【背景技術】
【０００３】
多重検索ツリーとは、次数（ｄｅｇｒｅｅ）が２よりも大きい探索ツリーを意味する。
【０００４】
多重検索ツリーは、同じ数のレコードを含む二分木に比べ、その高さがさらに低くなる。
【０００５】
ツリーの高さが低くなれば、ツリー内で特定のレコードを探索するために記憶装置にアクセスする回数を減らすことができ、探索、挿入、および削除などのような多重検索ツリーの演算速度がより速くなる。
【０００６】
高さを低くするために、多重検索ツリーはバランスを維持する。バランスを維持するために、多重検索ツリーにレコードが挿入されたり、多重検索ツリー内のレコードが削除されたりするとき、レコードが挿入または削除されるノードまたは前記ノードと関連するノードは分割または回転することがある。
【０００７】
一般的に、ノードが分割されるとき、分割されるノード内に格納されたレコードは、分割によって生成された２つのノードにそれぞれ同数個が分配される。
【発明の概要】
【発明が解決しようとする課題】
【０００８】
本発明の一実施形態は、ノードの累積移動平均に基づいてノードを分割する多重検索ツリーのノード分割方法を提供することができる。
【０００９】
本発明の一実施形態は、累積移動平均に基づいて多重検索ツリーのノードを分割する記憶装置を提供することができる。
【課題を解決するための手段】
【００１０】
本発明の一側によれば、第１ノードにレコードを挿入するステップ、レコードの第１ノード内の位置値に基づいて第１ノードの累積移動平均を計算するステップ、累積移動平均に基づいて第１ノードの分割位置を計算するステップ、および分割位置を基準として第１ノードを第２ノードおよび第３ノードに分割するステップを含む、多重検索ツリーのノード分割方法が提供される。
【００１１】
位置値は、レコードが挿入されたスロットの番号を第１ノード内のレコードの数で割った値であってもよい。
【００１２】
第１ノードの累積移動平均を計算するステップは、レコードが挿入されたスロットの番号を第１ノード内のレコードの数で割った値、累積移動平均、第１ノード内のレコードの数、および第１ノードに任意のレコードが挿入されるたびに１ずつ増加する定数に基づいて累積移動平均を更新するステップを含んでもよい。
【００１３】
累積移動平均が指定された範囲内の値である場合、分割位置は、昇順に整列した分割対象レコード全体の長さの中間であってもよい。
【００１４】
累積移動平均が指定された範囲内の値である場合、分割位置は、昇順に整列した分割対象レコード全体の長さを予め指定された割合で割った位置であってもよい。
【００１５】
累積移動平均が指定された範囲内の値である場合、分割位置は、昇順に整列した分割対象レコード全体の長さを累積移動平均の割合で割った位置であってもよい。
【００１６】
多重検索ツリーのレコードの長さは、可変であってもよい。
【００１７】
レコードは、データベースのインデックスであってもよい。
【００１８】
多重検索ツリーは、ＢツリーまたはＢ＋ツリーであってもよい。
【００１９】
本発明の他の一側によれば、多重検索ツリーの第１ノードにレコードを挿入する挿入処理部、レコードの第１ノード内の位置値に基づいて第１ノードの累積移動平均を計算する累積移動平均計算部、および累積移動平均に基づいて第１ノードの分割位置を計算し、分割位置を基準として第１ノードを第２ノードおよび第３ノードに分割する分割処理部を含む、記憶装置が提供される。
【００２０】
累積移動平均計算部は、レコードが挿入されたスロットの番号を第１ノード内のレコードの数で割った値、累積移動平均、第１ノード内のレコードの数、および第１ノードに任意のレコードが挿入されるたびに１ずつ増加する定数に基づいて累積移動平均を更新することにより、第１ノードの累積移動平均を計算してもよい。
【００２１】
分割処理部は、累積移動平均が指定された範囲内の値である場合、昇順に整列した分割対象レコード全体の長さの中間を分割位置として決めてもよい。
【００２２】
分割処理部は、累積移動平均が指定された範囲内の値である場合、昇順に整列した分割対象レコード全体の長さを予め指定された割合で割った位置を分割位置として決めてもよい。
【００２３】
分割処理部は、累積移動平均が指定された範囲内の値である場合、昇順に整列した分割対象レコード全体の長さを累積移動平均の割合で割った位置を分割位置として決めてもよい。
【発明の効果】
【００２４】
累積移動平均に基づいて多重検索ツリーのノードを分割することにより、多重検索ツリーに割り当てられた記憶容量を効率的に活用する方法および装置が提供される。
【００２５】
累積移動平均に基づいて多重検索ツリーのノードの分割位置を決めることにより、ノードに挿入されたレコードの値のパターンに応じてノードを分割する多重検索ツリーの分割方法およびこの分割方法を使用する装置が提供される。
【図面の簡単な説明】
【００２６】
【図１】多重検索ツリーに順にレコードが挿入される過程を示す図である。
【図２】多重検索ツリーに順にレコードが挿入される過程を示す図である。
【図３】多重検索ツリーのノードに値が順に増加するレコードが挿入される場合の問題点を示す図である。
【図４】本発明の一実施形態に係る多重検索ツリーにレコードを挿入する方法を示すフローチャートである。
【図５】本発明の一例に係る累積移動平均を計算する方法を説明する。
【図６】本発明の一例に係るノードの累積移動平均に基づいてノードの分割位置を決める方法を説明する。
【図７】本発明の一例に係る固定長さレコードがＳＰによって分割される方法を説明する。
【図８】本発明の一例に係る可変長さレコードがＳＰによって分割される方法を説明する。
【図９】本発明の一例に係る記憶装置９００の構造図である。
【発明を実施するための形態】
【００２７】
以下、本発明の一実施形態について、添付の図面を参照しながら詳細に説明する。しかし、本発明は、実施形態によって制限され、限定されるものではない。なお、各図面に提示された同じ参照符号は同じ部材を示す。
【００２８】
本発明の実施形態および実施例において、多重検索ツリーは、Ｂ−ツリー、Ｂ＋ツリー、またはその他のＢ−ツリーに基づいたツリーであってもよい。
【００２９】
多重検索ツリーがＢ＋ツリーである場合、本発明の実施形態および実施例において説明された多重検索ツリーは、データノードを省略し、インデックスノードのみを示したツリーであってもよい。例えば、多重検索ツリーに特定のレコードを連続的に挿入する動作は、多重検索ツリーのインデックスノードにレコードが挿入される場合のみを示したものであってもよい。
【００３０】
また、多重検索ツリーのルート（ｒｏｏｔ）ノードは、レコードを含んでもよく、含まなくてもよい。ルートノードがレコードを含まない場合、ルートノードは空のままで、ルートノードの下位ノードにのみレコードが挿入されてもよい。
【００３１】
本発明の実施形態および実施例において、レコードは、鍵を含んだ全体データを意味してもよい。また、レコードは、全体データのうちで鍵のみを意味してもよい。すなわち、本発明の実施形態および実施例のレコードは、鍵に代替されてもよい。また、ノードに格納されるレコードが鍵のみを意味する場合、鍵に対応する全体データは、ポインタなどを通じて鍵からリンクされてもよく、鍵を通じてアクセスされてもよい。
【００３２】
本発明の実施形態および実施例において、レコードまたは鍵は、データベースのインデックス（ｉｎｄｅｘ）であってもよい。この場合、多重検索ツリーは、データベースの特定のインデックスを管理するためのものであってもよい。
【００３３】
図１および図２は、本発明の一実施例に係る多重検索ツリーに順にレコードが挿入される過程を示している。
【００３４】
レコードが多重検索ツリーに挿入されるために、レコードの値は、多重検索ツリーのノード内に挿入されたレコードの値と比較される。図１および図２において、挿入されるレコードの値は順に増加している。
【００３５】
図１および図２の多重検索ツリーの次数（ｄｅｇｒｅｅ）は３である。すなわち、多重検索ツリーのノード内には、最大で２つのレコードが挿入されるようになる。多重検索ツリーのノードは、多重検索ツリーの次数がｎであるとき、ｎ−１個のスロットを有する。レコードはスロットのうちの１つに挿入される。
【００３６】
図１の第１ツリー１１０は、空の多重検索ツリーにレコード「１０」が挿入されたものである。
【００３７】
図１の第２ツリー１２０は、第１ツリー１１０にレコード「２０」が追加で挿入された結果を示している。
【００３８】
図１の第３ツリー１３０は、第２ツリー１２０にレコード「３０」が追加で挿入されたものである。
【００３９】
第２ツリー１２０のノード１２２内には、これ以上のレコードが挿入される容量（すなわち、スロット）がない。したがって、第２ツリー１２０のノード１２２は、２つのノード（１３４および１３６）に分割される。また、分割された２つのノード（１３４および１３６）の親ノードとして、新たなルートノード１３２が生成される。
【００４０】
このとき、第３ツリー１３０の３つのノード（１３２、１３４、および１３６）は、それぞれ１つのレコードのみを含む。すなわち、第３ツリー１３０は、第３ツリー１３０が含むことができるレコードの最大数の半分だけのレコードのみを含んでいる。したがって、第３ツリー１３０のために割り当てられた記憶容量が無駄になる。
【００４１】
図１の第４ツリー１４０は、第３ツリー１３０にレコード「４０」が追加で挿入されたものである。
【００４２】
多重検索ツリーの特性上、ツリー内のどのレコードよりも大きい値を有するレコードは、多重検索ツリーの最右側の末端ノードに挿入される。
【００４３】
図２の第１ツリー２１０は、図１に示す第４ツリー１４０にレコード「５０」が追加で挿入されたものである。
【００４４】
レコード「５０」は、第４ツリー１４０の最右側の末端ノード１４２に挿入されなければならないが、最右側の末端ノード１４２内には空き容量がない。したがって、最右側の末端ノード１４２は、図２の第１ツリー２１０において２つのノード（２１４および２１６）に分割される。
【００４５】
分割された２つのノード（２１４および２１６）はそれぞれ１つのレコードを含み、中間値を有するレコード「４０」は、分割された２つのノード（２１４および２１６）の親ノード２１２に伝達される。親ノード２１２内には空き容量があるため、レコード「４０」は親ノード２１２内に挿入される。
【００４６】
図２の第２ツリー２２０は、図２の第１ツリー２１０にレコード「６０」が追加で挿入されたものである。
【００４７】
第１ツリー２１０の最右側の末端ノード２１６内には空き容量があるため、レコード「６０」は第２ツリー２２０の最右側の末端ノード２２４に挿入される。
【００４８】
図２の第３ツリー２３０は、図２の第２ツリー２２０にレコード「７０」が追加で挿入されたものである。
【００４９】
第２ツリー２２０の最右側の末端ノード２２４内には空き容量がない。
【００５０】
したがって、最右側の末端ノード２２４は、２つのノード（２３８および２４０）に分割される。
【００５１】
分割された２つのノード（２３８および２４０）はそれぞれ１つのレコードを含み、中間値を有するレコード「６０」は、第２ツリー２２０の最右側の末端ノード２２４の親ノード２２２に挿入されなければならない。しかし、親ノード２２２内には空き容量がないため、親ノード２２２は２つのノード（２３４および２３６）に再分割される。
【００５２】
親ノード２２２はルートノードであるため、親ノード２２２が分割しながら新たなルートノード２３２が生成される。
【００５３】
新たなルートノード２３２は、親ノード２２２が分割されることによって生成された２つのノード（２３４および２３６）を子ノードとして有する。
【００５４】
２つのノード（２３４および２３６）はそれぞれ１つのレコードを含み、親ノード２２０が含んでいた１）レコード「２０」、および２）レコード「４０」と、最右側の末端ノード２２４の分割によって親ノード２２０に伝達された、３）レコード「６０」のうちで中間値を有するレコード「４０」は、新たなルートノード２３２に挿入される。
【００５５】
第３ツリー２３０のノードはそれぞれ１つのレコードのみを含む。すなわち、第３ツリー２３０は、第３ツリー２３０が含むことができるレコードの最大数の半分だけのレコードのみを含んでいる。したがって、第３ツリー２３０のために割り当てられた記憶容量が無駄になる。
【００５６】
また、この後、第３ツリー２３０に挿入されるレコードの値が増加し続ければ、多重検索ツリーの特性上、１）第３ツリー２３０のそれぞれの高さにおける最右側ノード（２３２、２３６、および２４０）、および２）、最右側ノード（２３２、２３６、および２４０）の分割によって生成されたノードにのみレコードが挿入され、その他のノード（例えば、ノード２３４）にはこれ以上のレコードが挿入されない。
【００５７】
したがって、例えば、多重検索ツリーのノードが分割されるとき、分割によって生成された２つのノードが常に同じ数のレコードを有する場合（または、分割によって生成された２つのノードが有するレコードの数に常に１だけの差がある場合）、特定のパターンを有するレコード（例えば、値が増加し続けるレコードまたは値が減少し続けるレコード）が多重検索ツリーに挿入されるとき、多重検索ツリーに割り当てられた記憶容量が無駄になり、多重検索ツリーの高さが必要以上に高くなることがある。
【００５８】
図３は、本発明の一例に係る多重検索ツリーのノードに値が順に増加するレコードが挿入される場合の問題点を示している。
【００５９】
第１ツリー３１０のノード３３０内にはレコードが挿入されている。ノード３３０内には空き容量がない。
【００６０】
第２ツリー３５０は、第１ツリー３１０のノード３３０内に新たなレコード「９０」が挿入された結果を示している。
【００６１】
ノード３３０内には空き容量がないため、新たなレコード「９０」が挿入されるためには、ノード３３０が分割されなければならない。
【００６２】
ノード３３０内のレコードおよび新たなレコード「９０」の中間値は、レコード「５０」である。
【００６３】
したがって、レコード「５０」を基準として、ノード３３０は、第１分割されたノード３６０および第２分割されたノード３７０に分割される。すなわち、第１分割されたノード３６０は、ノード３３０内のレコードおよび新たなレコード「９０」のうちの中間値以下の値を有するノードを含む。また、第２分割されたノード３７０は、ノード３３０内のレコードおよび新たなレコード「９０」のうちの中間値以上の値を有するノードを含む。
【００６４】
多重検索ツリーの次数がｎ＋１であるとき、第１分割されたノード３６０および第２分割されたノード３７０は、それぞれｎ／２つのレコードを有してもよい。
【００６５】
中間値であるレコード「５０」は、ノード３３０の親ノード３２０に挿入のために伝達される。親ノード３２０も空き容量を有していない場合、上述したように親ノード３２０も分割される。
【００６６】
この後、多重検索ツリーに挿入されるレコードの値が増加し続ける場合、多重検索ツリーの特性上、第１分割されたノード３６０にはこれ以上レコードが挿入されない。したがって、第１分割されたノード３６０のために割り当てられた記憶容量が無駄になる。
【００６７】
したがって、多重検索ツリーのノードが分割されるとき、ノードに挿入されてきたレコードがなす特定のパターンに基づいてノードを分割する基準となるレコードを決める方法が求められる。
【００６８】
図４は、本発明の一実施形態に係る多重検索ツリーにレコードを挿入する方法を示すフローチャートである。
【００６９】
多重検索ツリーに挿入されるレコードを追加レコードと命名する。
【００７０】
ステップ４１０で、追加レコードが挿入されるノードが検索される。検索されたノードを対象ノードと命名する。
【００７１】
ステップ４２０で、対象ノード内に追加レコードを挿入する空き容量があるか否かが検査される。すなわち、対象ノード内のレコードの数がノードに割り当てられたスロットの数よりも小さいか否かが検査される。
【００７２】
対象ノード内に追加レコードを挿入する空き容量があれば、対象ノードに追加レコードを挿入し、対象ノードの累積移動平均を計算するステップ（４３０、４４０、および４５０）が実行される。
【００７３】
対象ノード内に追加レコードを挿入する空き容量がなければ、追加レコードを多重検索ツリーに挿入するために、対象ノードを分割するステップ（４６０、４７０、および４８０）が実行される。
【００７４】
まず、対象ノード内に追加レコードを挿入する空き容量がある場合に実行されるステップ（４３０、４４０、および４５０）について説明する。
【００７５】
レコード挿入ステップ４３０で、対象ノードに追加レコードが挿入される。
【００７６】
追加レコードの挿入後、下記のステップ（４４０および４５０）で、追加レコードの対象ノード内の位置値に基づいて対象ノードの累積移動平均（ｃｕｍｕｌａｔｉｖｅ  ｍｏｖｉｎｇ  ａｖｅｒａｇｅ）（または、移動平均（ｒｕｎｎｉｎｇ  ａｖｅｒａｇｅ））が計算される。
【００７７】
挿入位置計算ステップ４４０で、追加レコードが対象ノード内に挿入された位置に基づいて追加レコードの対象ノード内の位置値が計算される。
【００７８】
追加レコードの位置値は、０以上１以下の値であってもよい。
【００７９】
追加レコードの位置値は、追加レコードが挿入されたスロットの番号（ｉｎｄｅｘ）を対象ノード内のレコード（すなわち、対象ノード内に格納されたレコード）の数で割った値であってもよい。
【００８０】
スロットの番号は０または１から始まってもよい。下記の実施形態では、スロットの番号が１から始まるものと見なす。
【００８１】
累積移動平均計算ステップ４５０で、追加レコードの位置値に基づいて対象ノードの累積移動平均が計算される。
【００８２】
レコードを含まないノードの累積移動平均は、０または１に初期化されてもよい。
【００８３】
累積移動平均は、下記の数式（１）に基づいて計算されてもよい。
【００８４】
【数１】
0005774213.tif 000002
【００８５】
ここで、ＣＡｉ−１は、追加レコードが挿入される前の対象ノードの累積移動平均である。また、ＣＡｉは、追加レコードが挿入された後に更新された累積移動平均である。
【００８６】
ｉはシーケンス（ｓｅｑｕｅｎｃｅ）である。すなわち、対象ノードに任意のレコードが挿入されるたびに１ずつ増加する定数である。ｉは１から始まってもよい。
【００８７】
ｘｉは追加レコードの位置値である。ｘｉにおいて、ｉはｘｉが対象ノードにｉ番目に挿入されたレコードの位置値であることを示す。すなわち、対象ノードの累積移動平均を計算するために使用された位置値は、順にｘ１、ｘ２、ｘ３、・・・、ｘｎである。
【００８８】
削除（ｄｅｌｅｔｅ）、演算、または分割（ｓｐｌｉｔ）演算に基づいて対象ノード内のレコードの数が減ることがある。このような場合、増加し続ける変数であるｉが使用される場合、削除または分割後に対象ノードに挿入されるレコードの位置値が、累積移動平均の更新において過度に少なく反映されることがある。
【００８９】
したがって、ノード内のレコードの数を反映して累積移動平均を更新するために、下記の数式（２）に基づいて累積移動平均が計算されてもよい。
【００９０】
【数２】
0005774213.tif 000003
【００９１】
ここで、Ｉは、ｉおよび対象ノード内のレコードの数ｎのうちの最小値を意味する。すなわち、Ｉ＝ＭＩＮ（ｉ、ｎ）である。
【００９２】
数式（１）および数式（２）を参照しながら上述したように、対象ノードの累積移動平均は、追加レコードが挿入されたスロットの番号を対象ノード内のレコードの数ｎで割った値ｘｉ、累積移動平均ＣＡｉ−１、対象ノード内のレコードの数ｎ、および対象ノードに任意のレコードが挿入されるたびに１ずつ増加する定数ｉに基づいて計算されてもよい。
【００９３】
下記では、レコードの挿入によってノードの累積移動平均が計算される一例について、図５を参照しながら詳しく説明する。
【００９４】
累積移動平均は、ノードのヘッダ（ｈｅａｄｅｒ）に保存されてもよい。すなわち、対象ノードに対して計算された累積移動平均は、対象ノードのヘッダに保存されてもよく、以後には更新のために対象ノードのヘッダから抽出されてもよい。
【００９５】
次に、対象ノード内に追加レコードを挿入する空き容量がない場合に実行されるステップ（４６０、４７０、および４８０）について説明する。
【００９６】
分割位置計算ステップ４６０で、対象ノードの累積移動平均に基づいて分割対象レコードの分割位置が計算される。
【００９７】
分割対象レコードとは、対象ノードが分割されるとき、分割によって生成される２つのノードのうちの１つのノードに含まれるレコード、および対象ノードの親ノードに伝達されるレコードを意味してもよい。
【００９８】
すなわち、分割対象レコードとは、対象ノード内のレコードおよび追加レコードを意味してもよい。また、分割対象レコードは、対象ノード内のレコードを含んでもよい。
【００９９】
分割位置は、分割対象レコードが昇順に羅列した一連（ｓｅｒｉｅｓ）のうちで特定の位置を示してもよい。
【０１００】
対象ノードの分割位置は、対象ノード内のレコードおよび追加レコードのうち、対象ノードが分割されるときに対象ノードの親ノードに伝達されるレコードを示してもよい。すなわち、対象ノードの分割位置が計算されれば、計算された分割位置に対応するレコードが分割の基準となってもよく、分割の基準となったレコードが分割のために対象ノードの親ノードに伝達されてもよい。
【０１０１】
計算された分割位置に対応するレコードを基準レコードと命名する。
【０１０２】
ノードの累積移動平均に基づいてノードの分割位置を計算する具体的な方法については、図６〜図８を参照しながら詳しく後述する。
【０１０３】
ノード分割ステップ４７０で、分割位置を基準として、対象ノードは左側分割ノードおよび右側分割ノードに分割される。
【０１０４】
すなわち、基準レコードの値よりも小さな値を有するレコードは左側分割ノードに含まれてもよく、基準レコードの値よりも大きな値を有するレコードは右側分割ノードに含まれてもよい。
【０１０５】
また、分割対象レコードが昇順に整列したとき、分割対象レコードのうちで基準レコードよりも前に位置するレコードは左側分割ノードに含まれてもよく、分割対象レコードのうちで基準レコードよりも後ろに位置するレコードは右側分割ノードに含まれてもよい。
【０１０６】
この後、ステップ４１０が再実行されることにより、基準レコードは挿入のために対象ノードの親ノードに伝達されてもよい。
【０１０７】
分割されたノード初期化ステップ４８０で、左側分割ノードおよび右側分割ノードはそれぞれ初期化されてもよい。
【０１０８】
左側分割ノードの累積移動平均は、対象ノードの累積移動平均に初期化されてもよい。また、右側分割ノードの累積移動平均は、対象ノードの累積移動平均に初期化されてもよい。
【０１０９】
左側分割ノードのシーケンスｉは０に初期化されてもよい。このようなシーケンスｉの初期化は、左側分割ノードに新たに挿入されるレコードが左側分割ノードの累積移動平均に高い影響を与えるようにする。また、右側分割ノードのシーケンスｉは０に初期化されてもよい。
【０１１０】
ステップ（４６０、４７０、および４８０）が実行されれば、ステップ４１０が再実行される。
【０１１１】
再実行されるステップ４１０は、ステップ４７０で、左側分割ノードおよび右側分割ノードに含まれないレコード（すなわち、基準レコード）を対象ノードの親ノードに挿入するステップであってもよい。すなわち、追加レコードは、ステップ４７０の基準レコードに変更されてもよい。また、再実行されたステップ４１０で検索されたノードは、以前の対象ノードの親ノードであってもよい。
【０１１２】
上述されたステップ（４１０〜４８０）を含む多重検索ツリーにレコードを挿入する方法は、多重検索ツリーのノード分割方法として見なされてもよい。すなわち、ステップ（４３０〜４５０）は、分割対象ノードの累積移動平均を計算するステップとしてもよく、ステップ（４６０〜４８０）は、計算された累積移動平均に基づいて分割対象ノードを分割するステップとしてもよい。
【０１１３】
図５は、本発明の一例に係る累積移動平均を計算する方法を説明している。
【０１１４】
第１ノード５１０は空白ノードである。空白ノードのシーケンスｉの初期値は０であってもよい。また、空白ノードの初期累積移動平均ＣＡ０は、０または１であってもよい。
【０１１５】
第２ノード５２０は、第１ノード５１０にレコード「４０」が挿入されたノードである。
【０１１６】
新たなレコードが挿入されることにより、シーケンスｉは１増加する。したがって、このときのシーケンスｉの値は１である。
【０１１７】
レコード「４０」は、第２ノード５２０内の１つのレコードのうちで一番目の位置に挿入された。したがって、レコード「４０」の位置値ｘ１は１である。
【０１１８】
シーケンスｉの値は１であり、第２ノード５２０内に挿入されたレコードの数は１である。したがって、Ｉの値は１である。
【０１１９】
数式（２）により、第２ノード５２０の累積移動平均ＣＡ１は１である。
【０１２０】
第３ノード５３０は、第２ノード５２０にレコード「８０」が挿入されたノードである。
【０１２１】
新たなレコードが挿入されることにより、シーケンスｉは１増加する。したがって、このときのシーケンスｉの値は２である。
【０１２２】
レコード「８０」は、第３ノード５３０内の２つのレコードのうちで二番目の位置に挿入された。したがって、レコード「８０」の位置値ｘ２は２／２＝１である。
【０１２３】
シーケンスｉの値は２であり、第３ノード５３０内に挿入されたレコードの数は２である。したがって、Ｉの値は２である。
【０１２４】
数式（２）により、第３ノード５３０の累積移動平均ＣＡ２は１である。
【０１２５】
第２ノード５２０および第３ノード５３０を検討すれば、新たに挿入されたレコードがノード内のレコードのうちで最も後ろに位置すれば（すなわち、新たに挿入されたレコードの値がノード内のレコードそれぞれの値以上であれば）、ノードの累積移動平均は１に維持されることがあり、１により近い値に増加することが分かる。
【０１２６】
第４ノード５４０は、第２ノード５２０にレコード「２０」が挿入されたノードである。
【０１２７】
新たなレコードが挿入されることにより、シーケンスｉは１増加する。したがって、このときのシーケンスｉの値は２である。
【０１２８】
レコード「２０」は、第４ノード５４０内の２つのレコードのうちで一番目の位置に挿入された。したがって、レコード「２０」の位置値ｘ２は１／２である。
【０１２９】
シーケンスｉの値は２であり、第４ノード５４０内に挿入されたレコードの数は２である。したがって、Ｉの値は２である。
【０１３０】
数式（２）により、第４ノード５４０の累積移動平均ＣＡ２は３／４である。
【０１３１】
第５ノード５５０は、第４ノード５４０にレコード「１０」が挿入されたノードである。
【０１３２】
新たなレコードが挿入されることにより、シーケンスｉは１増加する。したがって、このときのシーケンスｉの値は３である。
【０１３３】
レコード「１０」は、第５ノード５５０内の３つのレコードのうちで一番目の位置に挿入された。したがって、レコード「１０」の位置値ｘ３は１／３である。
【０１３４】
シーケンスｉの値は３であり、第５ノード５５０内に挿入されたレコードの数は３である。したがって、Ｉの値は３である。
【０１３５】
数式（２）により、第５ノード５５０の累積移動平均ＣＡ３は２２／３６である。
【０１３６】
第２ノード５２０、第４ノード５４０、および第５ノード５５０を検討すれば、新たに挿入されたレコードがノード内のレコードのうちで最も前に位置すれば（すなわち、新たに挿入されたレコードの値がノード内のレコードそれぞれの値以下であれば）、ノードの累積移動平均は０により近い値に減少することが分かる。
【０１３７】
ノード内に挿入されるレコードの値が示すパターンが漸進的な増加に近いほど、ノードの累積移動平均が１に近くなってもよい。したがって、ノードの累積移動平均が１に近ければ、ノードを分割するとき、左側分割ノード（すなわち、低い値を有するレコードが挿入されるノード）に多くのレコードを保存し、右側分割ノード（すなわち、高い値を有するレコードが挿入されるノード）に少ないレコードを保存することにより、左側分割ノードおよび右側分割ノードに割り当てられた保存場所が効率的に使用されるようにできる。
【０１３８】
これとは反対に、ノードの累積移動平均が０に近ければ、ノードを分割するとき、左側分割ノードに少ないレコードを保存し、右側分割ノードに少ないレコードを保存することにより、左側分割ノードおよび右側分割ノードに割り当てられた保存場所が効率的に使用されるようにできる。
【０１３９】
すなわち、ノードの累積移動平均に基づいてノードを分割することにより、分割されたノードに割り当てられた保存場所を効率的に使用できるようになる。また、ノードの累積移動平均に基づいてノードを分割することにより、多重検索ツリーの高さをさらに低めることができる。
【０１４０】
図６は、本発明の一例に係るノードの累積移動平均に基づいてノードの分割位置を決める方法を説明している。
【０１４１】
ノードの分割位置は、ノードの累積移動平均に比例して決められてもよい。
【０１４２】
以下、ノードの累積移動平均をＣＡ（Ｃｕｍｕｌａｔｉｖｅ  ｍｏｖｉｎｇ  ａｖｅｒａｇｅ）と略述し、ノードの分割位置をＳＰ（ｓｐｌｉｔ  ｐｏｉｎｔ）と略述する。昇順に整列した分割対象レコードの全体の長さをＴＲＬ（ｔｏｔａｌ  ｒｅｃｏｒｄ  ｌｅｎｇｔｈ）と略述する。
【０１４３】
例えば、ＣＡの値が１であれば、ＳＰはＴＲＬの終端となってもよい。
【０１４４】
ここで、分割対象レコードは、図４を参照しながら上述した分割対象レコードを示してもよい。すなわち、分割対象レコードは、ノード（すなわち、図４の対象ノード）内に既に挿入されたレコード、およびノード内に新たに挿入されるレコード（すなわち、図４の追加レコード）を意味してもよい。
【０１４５】
すなわち、ＣＡの値が１であれば、分割対象レコードはすべて左側分割ノードに含まれてもよく、右側分割ノードは空のノードであってもよい。
【０１４６】
例えば、ＣＡ値が０または０に極めて近い値であれば、ＳＰはＴＲＬの始め（すなわち、０）であってもよい。
【０１４７】
すなわち、ＣＡの値が０であれば、分割対象レコードはすべて右側分割ノードに含まれてもよく、左側分割ノードは空のノードであってもよい。
【０１４８】
または、ＣＡに比例して昇順に整列した分割対象レコードのうち、基準レコードが決められてもよい。このとき、ＳＰは、決められた基準レコードを示す値を有してもよい。
【０１４９】
例えば、ＣＡが０．５であれば、ＳＰは昇順に整列した分割対象レコードのうちで中間値（すなわち、上位５０％の値）を有するレコードを示す値を有してもよい。
【０１５０】
図６に示すように、ＳＰは、ＣＡが属する範囲に基づいて決められてもよい。
【０１５１】
図６のグラフ６１０は、ＣＡの分布を示している。
【０１５２】
ＣＡが第１指定された範囲（例えば、ｔ２以上またはｔ３以下）内の値である場合、ＳＰはＴＲＬの中間を示してもよい。すなわち、ＳＰの値は、ＴＲＬに０．５を掛けた値であってもよい。
【０１５３】
ＣＡが第２指定された範囲（例えば、ｔ１以上またはｔ２以下、またはｔ３以上またはｔ４以下）内の値である場合、ＳＰは、ＴＲＬをＣＡの割合で割った位置を示してもよい。すなわち、ＳＰの値は、ＴＲＬにＣＡを掛けた値であってもよい。
【０１５４】
ＣＡが第３指定された範囲（例えば、ｔ１以下またはｔ４以上）内の値である場合、ＳＰは、ＴＲＬを予め指定された割合（例えば、Ｐ１％またはＰ２％）で割った位置を示してもよい。ＳＰの値は、ＴＲＬにＰ１／１００（または、Ｐ２／１００）を掛けた値であってもよい。前記のＰ１およびＰ２は例示的なものである。すなわち、ＳＰの値は、ＴＲＬにＰ３を掛けた値であってもよい。Ｐ３は、０以上１以下の自然数であってもよい。
【０１５５】
上述したｔ１、ｔ２、ｔ３、およびｔ４は、特定の値であってもよい。例えば、ｔ１の値は０．０５であってもよい。ｔ２の値は０．２であってもよい。ｔ３の値は０．８であってもよい。ｔ４の値は０．９５であってもよい。
【０１５６】
図７は、本発明の一例に係る固定長さレコードがＳＰによって分割される方法を説明している。
【０１５７】
対象ノード７１０は、４つのレコード（７１２、７１４、７１６、および７１８）を含んでいる。
【０１５８】
対象ノード７１０にレコード「４０」７２０が挿入されれば、分割対象レコード（７１２、７１４、７１６、７１８、および７２０）は、昇順に整列する場合、レコード「１０」７１２、レコード「２０」７１４、レコード「３０」７１６、レコード「４０」７２０、およびレコード「５０」７１８の順になる。
【０１５９】
ＳＰがＴＲＬの中間である場合、ＳＰが示すレコードはレコード「３０」７１６である。したがって、レコード「３０」７１６が基準レコードとして決まる。
【０１６０】
対象ノード７１０が分割されれば、左側分割ノード７４０は基準レコード７１６よりも前に位置したレコード（７１２および７１４）を含み、右側分割ノード７５０は基準レコード７１６よりも後ろに位置したレコード（７２０および７１８）を含む。
【０１６１】
基準レコード７１６は、対象ノード７１０の親ノード７３０に挿入される。
【０１６２】
図８は、本発明の一例に係る可変長さレコードがＳＰによって分割される方法を説明している。
【０１６３】
対象ノード８１０は、４つのレコード（８１２、８１４、８１６、および７１８）を含む。レコード「ＡＡ」８１２の長さは２である。レコード「ＢＢＢＢ」８１４の長さは４である。レコード「Ｃ」８１６の長さは１である。レコード「ＤＤ」８１８の長さは２である。
【０１６４】
対象ノード８１０に長さが２であるレコード「ＥＥ」８２０が挿入されれば、分割対象レコード（８１２、８１４、８１６、８１８、および８２０）は、昇順に整列する場合、レコード「ＡＡ」８１２、レコード「ＢＢＢＢ」８１４、レコード「Ｃ」８１６、レコード「ＤＤ」７１８、およびレコード「ＥＥ」８２０の順となる。このとき、ＴＲＬは１１である。
【０１６５】
ＳＰがＴＲＬの中間である場合、ＳＰの値は６である。したがって、分割対象レコードの一連のうち、前から６だけ離れた位置がＳＰになってもよい。
【０１６６】
これは、分割対象レコードが占める記憶領域のうち、前から６番目の記憶単位（例えば、バイト（ｂｙｔｅ）、ワード（ｗｏｒｄ）、またはフィールド（ｆｉｅｌｄ）を示してもよい。
【０１６７】
分割対象レコードのうちでＳＰの値に対応する位置を占めるレコードは、レコード「ＢＢＢＢ」８１４である。したがって、レコード「ＢＢＢＢ」８１４が基準レコードとして決まる。
【０１６８】
対象ノード８１０が分割されれば、左側分割ノード８４０は基準レコード８１４よりも前に位置したレコード８１２を含み、右側分割ノード８５０は基準レコード８１４よりも後ろに位置したレコード（８１６、８１８、および８２０）を含む。
【０１６９】
図９は、本発明の一例に係る記憶装置９００の構造図である。
【０１７０】
記憶装置９００は、挿入処理部９１０、累積移動平均計算部９２０、分割処理部９３０、および格納部９４０を含んでもよい。
【０１７１】
挿入処理部９１０は、ステップ（４１０、４２０、および４３０）を実行してもよい。
【０１７２】
例えば、挿入処理部９１０は、多重検索ツリーの第１ノードにレコードを挿入してもよい。
【０１７３】
累積移動平均計算部９２０は、ステップ（４４０および４５０）を実行してもよい。
【０１７４】
例えば、累積移動平均計算部９２０は、挿入されたレコードの第１ノード内の位置値に基づいて第１ノードの累積移動平均を計算してもよい。
【０１７５】
位置値は、レコードが挿入されたスロットの番号を第１ノード内のレコードの数で割った値であってもよい。
【０１７６】
また、累積移動平均計算部９２０は、１）レコードが挿入されたスロットの番号を第１ノード内のレコードの数で割った値、２）累積移動平均、３）第１ノード内のレコードの数、および４）第１ノードに任意のレコードが挿入されるたびに１ずつ増加する定数に基づいて累積移動平均を更新することにより、第１ノードの累積移動平均を計算してもよい。
【０１７７】
累積移動平均計算部９２０は、上述した数式（１）または数式（２）に基づいて累積移動平均を計算してもよい。
【０１７８】
分割処理部９３０は、ステップ（４６０、４７０、および４８０）を実行してもよい。
【０１７９】
例えば、分割処理部９３０は、累積移動平均に基づいて第１ノードの分割位置を計算してもよく、計算された分割位置を基準として第１ノードを第２ノードおよび第３ノードに分割してもよい。
【０１８０】
分割処理部９３０は、累積移動平均が指定された範囲内の値である場合、昇順に整列した分割対象レコードの全体の長さの中間を分割位置として決めてもよい。
【０１８１】
分割処理部９３０は、累積移動平均が指定された範囲内の値である場合、昇順に整列した分割対象レコードの全体の長さを予め指定された割合で割る位置を分割位置として決めてもよい。
【０１８２】
分割処理部９３０は、累積移動平均が指定された範囲内の値である場合、昇順に整列した分割対象レコードの全体の長さを累積移動平均の割合で割る位置を分割位置として決めてもよい。
【０１８３】
記憶部９４０は、多重検索ツリーを格納してもよい。
【０１８４】
記憶部９４０は、多重検索ツリーを構成するノードを格納してもよい。
【０１８５】
記憶部９４０は、ノードのヘッダにノードの累積移動平均およびシーケンスを格納してもよい。
【０１８６】
図１〜図８を参照しながら上述した本発明の一実施形態に係る技術的内容は、本実施例にそのまま適用されてもよい。したがって、より詳細な説明は、以下では省略する。
【０１８７】
構成要素（９１０、９２０、および９３０）の機能は、単一な制御部（図示せず）で実行されてもよい。このとき、制御部は、単一（ｓｉｎｇｌｅ）または複数（ｍｕｌｔｉ）チップ（ｃｈｉｐ）、プロセッサ（ｐｒｏｃｅｓｓｏｒ）、またはコア（ｃｏｒｅ）を示してもよい。構成要素（９１０、９２０、および９３０）それぞれは、制御部で実行される関数（ｆｕｎｃｔｉｏｎ）、ライブラリ（ｌｉｂｒａｒｙ）、サービス（ｓｅｒｖｉｃｅ）、プロセス（ｐｒｏｃｅｓｓ）、スレッド（ｔｈｒｅａｄ）、またはモジュール（ｍｏｄｕｌｅ）を示してもよい。
【０１８８】
本発明の一実施形態に係る方法は、多様なコンピュータ手段によって実行が可能なプログラム命令形態で実現されてコンピュータで読み取り可能な媒体に記録されてもよい。コンピュータで読み取り可能な媒体は、プログラム命令、データファイル、データ構造などを単独または組み合わせて含んでもよい。媒体に記録されるプログラム命令は、実施形態のために特別に設計されて構成されたものであってもよく、コンピュータソフトウェアの当業者に公知されて使用可能なものであってもよい。コンピュータで読み取り可能な記録媒体の例としては、ハードディスク、フロッピー（登録商標）ディスク、および磁気テープのような磁気媒体（ｍａｇｎｅｔｉｃ  ｍｅｄｉａ）、ＣＤ−ＲＯＭ、ＤＶＤのような光記録媒体（ｏｐｔｉｃａｌ  ｍｅｄｉａ）、フロプティカルディスク（ｆｌｏｐｔｉｃａｌ  ｄｉｓｋ）のような磁気−光媒体（ｍａｇｎｅｔｏ−ｏｐｔｉｃａｌ  ｍｅｄｉａ）、およびＲＯＭ、ＲＡＭ、フラッシュメモリなどのようなプログラム命令を格納して実行するように特別に構成されたハードウェア装置が含まれる。プログラム命令の例としては、コンパイラによって生成されるもののような機械語コードだけではなく、インタプリタなどを使用してコンピュータによって実行される高級言語コードを含む。上述したハードウェア装置は、実施形態の動作を実行するために１つ以上のソフトウェアモジュールとして作動するように構成されてもよく、その逆も同じである。
【０１８９】
以上のように、本発明は限定された実施例と図面に基づいて説明されたが、本発明は前記の実施例に限定されるものではなく、本発明が属する分野において通常の知識を有する者であれば、このような記載から多様な修正および変形が可能である。
【０１９０】
したがって、本発明の範囲は、説明された実施例に限定されて定められてはならず、添付の特許請求の範囲だけではなく、この特許請求の範囲と均等なものに基づいて定められなければならない。
【図１】
0005774213.tif 000006
【図２】
0005774213.tif 000007
【図３】
0005774213.tif 000008
【図４】
0005774213.tif 000009
【図５】
0005774213.tif 000010
【図６】
0005774213.tif 000011
【図７】
0005774213.tif 000012
【図８】
0005774213.tif 000013
【図９】
0005774213.tif 000014