第1ノードにレコードを挿入するステップ、前記レコードの前記第1ノード内の位置値に基づいて前記第1ノードの累積移動平均を計算するステップ、前記累積移動平均に基づいて前記第1ノードの分割位置を計算するステップ、および前記分割位置を基準として前記第1ノードを第2ノードおよび第3ノードに分割するステップを含む、多重検索ツリーのノード分割方法。前記位置値は、前記レコードが挿入されたスロットの番号を前記第1ノード内のレコードの数で割った値である、請求項1に記載の多重検索ツリーのノード分割方法。前記第1ノードの累積移動平均を計算するステップは、前記レコードが挿入されたスロットの番号を前記第1ノード内のレコードの数で割った値、前記累積移動平均、前記第1ノード内のレコードの数、および前記第1ノードに任意のレコードが挿入されるたびに1ずつ増加する定数に基づいて前記累積移動平均を更新するステップを含む、請求項1に記載の多重検索ツリーのノード分割方法。前記累積移動平均は、下記の数式1に基づいて計算される、請求項3に記載の多重検索ツリーのノード分割方法。CAi-1は、前記レコードが挿入される前の前記第1ノードの累積移動平均である。CAiは、前記レコードが挿入された後に更新された前記累積移動平均である。Iは、iおよび前記第1ノード内のレコードの数のうちの最小値である。xiは、前記レコードが挿入されたスロットの番号を前記第1ノード内のレコードの数で割った値である。iは前記第1ノードに任意のレコードが挿入されるたびに1ずつ増加する定数である。前記累積移動平均が指定された範囲内の値である場合、前記分割位置は、昇順に整列した分割対象レコードの全体の長さの中間である、請求項1に記載の多重検索ツリーのノード分割方法。前記累積移動平均が指定された範囲内の値である場合、前記分割位置は、昇順に整列した分割対象レコードの全体の長さを予め指定された割合で割る位置である、請求項1に記載の多重検索ツリーのノード分割方法。前記累積移動平均が指定された範囲内の値である場合、前記分割位置は、昇順に整列した分割対象レコードの全体の長さを前記累積移動平均の割合で分割する位置である、請求項1に記載の多重検索ツリーのノード分割方法。前記多重検索ツリーのレコードの長さは可変である、請求項1に記載の多重検索ツリーのノード分割方法。前記レコードはデータベースのインデックスである、請求項1に記載の多重検索ツリーのノード分割方法。前記多重検索ツリーはBツリーまたはBツリーである、請求項1に記載の多重検索ツリーのノード分割方法。請求項1乃至10のいずれか一項に記載の多重検索ツリーのノード分割方法を実行するプログラムを記録した、コンピュータ読み取り可能な記録媒体。多重検索ツリーの第1ノードにレコードを挿入する挿入処理部、前記レコードの前記第1ノード内の位置値に基づいて前記第1ノードの累積移動平均を計算する累積移動平均計算部、および前記累積移動平均に基づいて前記第1ノードの分割位置を計算し、前記分割位置を基準として前記第1ノードを第2ノードおよび第3ノードに分割する分割処理部を含む、記憶装置。前記位置の値は、前記レコードが挿入されたスロットの番号を前記第1ノード内のレコードの数で割った値である、請求項12に記載の記憶装置。前記累積移動平均計算部は、前記レコードが挿入されたスロットの番号を前記第1ノード内のレコードの数で割った値で、前記累積移動平均、前記第1ノード内のレコードの数、および前記第1ノードに任意のレコードが挿入されるたびに1ずつ増加する定数に基づいて前記累積移動平均を更新することにより、前記第1ノードの累積移動平均を計算する、請求項12に記載の記憶装置。前記累積移動平均計算部は、下記の数式2に基づいて前記累積移動平均を計算する、請求項12に記載の記憶装置。CAi-1は、前記レコードが挿入される前の前記第1ノードの累積移動平均である。CAiは、前記レコードが挿入された後に更新された前記累積移動平均である。Iは、iおよび前記第1ノード内のレコードの数のうちの最小値である。xiは、前記レコードが挿入されたスロットの番号を前記第1ノード内のレコードの数で割った値である。iは、前記第1ノードに任意のレコードが挿入されるたびに1ずつ増加する定数である。前記分割処理部は、前記累積移動平均が指定された範囲内の値である場合、昇順に整列した分割対象レコードの全体の長さの中間を前記分割位置として決める、請求項12に記載の記憶装置。前記分割処理部は、前記累積移動平均が指定された範囲内の値である場合、昇順に整列した分割対象レコードの全体の長さを予め指定された割合で割る位置を前記分割位置として決める、請求項12に記載の記憶装置。前記分割処理部は、前記累積移動平均が指定された範囲内の値である場合、昇順に整列した分割対象レコードの全体の長さを前記累積移動平均の割合で割る位置を前記分割位置として決める、請求項12に記載の記憶装置。前記多重検索ツリーのレコードの長さは可変である、請求項12に記載の記憶装置。本発明の一実施形態は、ノードの累積移動平均に基づいてノードを分割する多重検索ツリーのノード分割方法を提供することができる。本発明の一実施形態は、累積移動平均に基づいて多重検索ツリーのノードを分割する記憶装置を提供することができる。本発明の一側によれば、第1ノードにレコードを挿入するステップ、レコードの第1ノード内の位置値に基づいて第1ノードの累積移動平均を計算するステップ、累積移動平均に基づいて第1ノードの分割位置を計算するステップ、および分割位置を基準として第1ノードを第2ノードおよび第3ノードに分割するステップを含む、多重検索ツリーのノード分割方法が提供される。位置値は、レコードが挿入されたスロットの番号を第1ノード内のレコードの数で割った値であってもよい。第1ノードの累積移動平均を計算するステップは、レコードが挿入されたスロットの番号を第1ノード内のレコードの数で割った値、累積移動平均、第1ノード内のレコードの数、および第1ノードに任意のレコードが挿入されるたびに1ずつ増加する定数に基づいて累積移動平均を更新するステップを含んでもよい。累積移動平均が指定された範囲内の値である場合、分割位置は、昇順に整列した分割対象レコード全体の長さの中間であってもよい。累積移動平均が指定された範囲内の値である場合、分割位置は、昇順に整列した分割対象レコード全体の長さを予め指定された割合で割った位置であってもよい。累積移動平均が指定された範囲内の値である場合、分割位置は、昇順に整列した分割対象レコード全体の長さを累積移動平均の割合で割った位置であってもよい。多重検索ツリーのレコードの長さは、可変であってもよい。レコードは、データベースのインデックスであってもよい。多重検索ツリーは、BツリーまたはBツリーであってもよい。本発明の他の一側によれば、多重検索ツリーの第1ノードにレコードを挿入する挿入処理部、レコードの第1ノード内の位置値に基づいて第1ノードの累積移動平均を計算する累積移動平均計算部、および累積移動平均に基づいて第1ノードの分割位置を計算し、分割位置を基準として第1ノードを第2ノードおよび第3ノードに分割する分割処理部を含む、記憶装置が提供される。累積移動平均計算部は、レコードが挿入されたスロットの番号を第1ノード内のレコードの数で割った値、累積移動平均、第1ノード内のレコードの数、および第1ノードに任意のレコードが挿入されるたびに1ずつ増加する定数に基づいて累積移動平均を更新することにより、第1ノードの累積移動平均を計算してもよい。分割処理部は、累積移動平均が指定された範囲内の値である場合、昇順に整列した分割対象レコード全体の長さの中間を分割位置として決めてもよい。分割処理部は、累積移動平均が指定された範囲内の値である場合、昇順に整列した分割対象レコード全体の長さを予め指定された割合で割った位置を分割位置として決めてもよい。分割処理部は、累積移動平均が指定された範囲内の値である場合、昇順に整列した分割対象レコード全体の長さを累積移動平均の割合で割った位置を分割位置として決めてもよい。累積移動平均に基づいて多重検索ツリーのノードを分割することにより、多重検索ツリーに割り当てられた記憶容量を効率的に活用する方法および装置が提供される。累積移動平均に基づいて多重検索ツリーのノードの分割位置を決めることにより、ノードに挿入されたレコードの値のパターンに応じてノードを分割する多重検索ツリーの分割方法およびこの分割方法を使用する装置が提供される。以下、本発明の一実施形態について、添付の図面を参照しながら詳細に説明する。しかし、本発明は、実施形態によって制限され、限定されるものではない。なお、各図面に提示された同じ参照符号は同じ部材を示す。本発明の実施形態および実施例において、多重検索ツリーは、B-ツリー、Bツリー、またはその他のB-ツリーに基づいたツリーであってもよい。多重検索ツリーがBツリーである場合、本発明の実施形態および実施例において説明された多重検索ツリーは、データノードを省略し、インデックスノードのみを示したツリーであってもよい。例えば、多重検索ツリーに特定のレコードを連続的に挿入する動作は、多重検索ツリーのインデックスノードにレコードが挿入される場合のみを示したものであってもよい。また、多重検索ツリーのルートrootノードは、レコードを含んでもよく、含まなくてもよい。ルートノードがレコードを含まない場合、ルートノードは空のままで、ルートノードの下位ノードにのみレコードが挿入されてもよい。本発明の実施形態および実施例において、レコードは、鍵を含んだ全体データを意味してもよい。また、レコードは、全体データのうちで鍵のみを意味してもよい。すなわち、本発明の実施形態および実施例のレコードは、鍵に代替されてもよい。また、ノードに格納されるレコードが鍵のみを意味する場合、鍵に対応する全体データは、ポインタなどを通じて鍵からリンクされてもよく、鍵を通じてアクセスされてもよい。本発明の実施形態および実施例において、レコードまたは鍵は、データベースのインデックスindexであってもよい。この場合、多重検索ツリーは、データベースの特定のインデックスを管理するためのものであってもよい。図1および図2は、本発明の一実施例に係る多重検索ツリーに順にレコードが挿入される過程を示している。レコードが多重検索ツリーに挿入されるために、レコードの値は、多重検索ツリーのノード内に挿入されたレコードの値と比較される。図1および図2において、挿入されるレコードの値は順に増加している。図1および図2の多重検索ツリーの次数degreeは3である。すなわち、多重検索ツリーのノード内には、最大で2つのレコードが挿入されるようになる。多重検索ツリーのノードは、多重検索ツリーの次数がnであるとき、n-1個のスロットを有する。レコードはスロットのうちの1つに挿入される。図1の第1ツリー110は、空の多重検索ツリーにレコード10が挿入されたものである。図1の第2ツリー120は、第1ツリー110にレコード20が追加で挿入された結果を示している。図1の第3ツリー130は、第2ツリー120にレコード30が追加で挿入されたものである。第2ツリー120のノード122内には、これ以上のレコードが挿入される容量すなわち、スロットがない。したがって、第2ツリー120のノード122は、2つのノード134および136に分割される。また、分割された2つのノード134および136の親ノードとして、新たなルートノード132が生成される。このとき、第3ツリー130の3つのノード132、134、および136は、それぞれ1つのレコードのみを含む。すなわち、第3ツリー130は、第3ツリー130が含むことができるレコードの最大数の半分だけのレコードのみを含んでいる。したがって、第3ツリー130のために割り当てられた記憶容量が無駄になる。図1の第4ツリー140は、第3ツリー130にレコード40が追加で挿入されたものである。多重検索ツリーの特性上、ツリー内のどのレコードよりも大きい値を有するレコードは、多重検索ツリーの最右側の末端ノードに挿入される。図2の第1ツリー210は、図1に示す第4ツリー140にレコード50が追加で挿入されたものである。レコード50は、第4ツリー140の最右側の末端ノード142に挿入されなければならないが、最右側の末端ノード142内には空き容量がない。したがって、最右側の末端ノード142は、図2の第1ツリー210において2つのノード214および216に分割される。分割された2つのノード214および216はそれぞれ1つのレコードを含み、中間値を有するレコード40は、分割された2つのノード214および216の親ノード212に伝達される。親ノード212内には空き容量があるため、レコード40は親ノード212内に挿入される。図2の第2ツリー220は、図2の第1ツリー210にレコード60が追加で挿入されたものである。第1ツリー210の最右側の末端ノード216内には空き容量があるため、レコード60は第2ツリー220の最右側の末端ノード224に挿入される。図2の第3ツリー230は、図2の第2ツリー220にレコード70が追加で挿入されたものである。第2ツリー220の最右側の末端ノード224内には空き容量がない。したがって、最右側の末端ノード224は、2つのノード238および240に分割される。分割された2つのノード238および240はそれぞれ1つのレコードを含み、中間値を有するレコード60は、第2ツリー220の最右側の末端ノード224の親ノード222に挿入されなければならない。しかし、親ノード222内には空き容量がないため、親ノード222は2つのノード234および236に再分割される。親ノード222はルートノードであるため、親ノード222が分割しながら新たなルートノード232が生成される。新たなルートノード232は、親ノード222が分割されることによって生成された2つのノード234および236を子ノードとして有する。2つのノード234および236はそれぞれ1つのレコードを含み、親ノード220が含んでいた1レコード20、および2レコード40と、最右側の末端ノード224の分割によって親ノード220に伝達された、3レコード60のうちで中間値を有するレコード40は、新たなルートノード232に挿入される。第3ツリー230のノードはそれぞれ1つのレコードのみを含む。すなわち、第3ツリー230は、第3ツリー230が含むことができるレコードの最大数の半分だけのレコードのみを含んでいる。したがって、第3ツリー230のために割り当てられた記憶容量が無駄になる。また、この後、第3ツリー230に挿入されるレコードの値が増加し続ければ、多重検索ツリーの特性上、1第3ツリー230のそれぞれの高さにおける最右側ノード232、236、および240、および2、最右側ノード232、236、および240の分割によって生成されたノードにのみレコードが挿入され、その他のノード例えば、ノード234にはこれ以上のレコードが挿入されない。したがって、例えば、多重検索ツリーのノードが分割されるとき、分割によって生成された2つのノードが常に同じ数のレコードを有する場合または、分割によって生成された2つのノードが有するレコードの数に常に1だけの差がある場合、特定のパターンを有するレコード例えば、値が増加し続けるレコードまたは値が減少し続けるレコードが多重検索ツリーに挿入されるとき、多重検索ツリーに割り当てられた記憶容量が無駄になり、多重検索ツリーの高さが必要以上に高くなることがある。図3は、本発明の一例に係る多重検索ツリーのノードに値が順に増加するレコードが挿入される場合の問題点を示している。第1ツリー310のノード330内にはレコードが挿入されている。ノード330内には空き容量がない。第2ツリー350は、第1ツリー310のノード330内に新たなレコード90が挿入された結果を示している。ノード330内には空き容量がないため、新たなレコード90が挿入されるためには、ノード330が分割されなければならない。ノード330内のレコードおよび新たなレコード90の中間値は、レコード50である。したがって、レコード50を基準として、ノード330は、第1分割されたノード360および第2分割されたノード370に分割される。すなわち、第1分割されたノード360は、ノード330内のレコードおよび新たなレコード90のうちの中間値以下の値を有するノードを含む。また、第2分割されたノード370は、ノード330内のレコードおよび新たなレコード90のうちの中間値以上の値を有するノードを含む。多重検索ツリーの次数がn1であるとき、第1分割されたノード360および第2分割されたノード370は、それぞれn/2つのレコードを有してもよい。中間値であるレコード50は、ノード330の親ノード320に挿入のために伝達される。親ノード320も空き容量を有していない場合、上述したように親ノード320も分割される。この後、多重検索ツリーに挿入されるレコードの値が増加し続ける場合、多重検索ツリーの特性上、第1分割されたノード360にはこれ以上レコードが挿入されない。したがって、第1分割されたノード360のために割り当てられた記憶容量が無駄になる。したがって、多重検索ツリーのノードが分割されるとき、ノードに挿入されてきたレコードがなす特定のパターンに基づいてノードを分割する基準となるレコードを決める方法が求められる。図4は、本発明の一実施形態に係る多重検索ツリーにレコードを挿入する方法を示すフローチャートである。多重検索ツリーに挿入されるレコードを追加レコードと命名する。ステップ410で、追加レコードが挿入されるノードが検索される。検索されたノードを対象ノードと命名する。ステップ420で、対象ノード内に追加レコードを挿入する空き容量があるか否かが検査される。すなわち、対象ノード内のレコードの数がノードに割り当てられたスロットの数よりも小さいか否かが検査される。対象ノード内に追加レコードを挿入する空き容量があれば、対象ノードに追加レコードを挿入し、対象ノードの累積移動平均を計算するステップ430、440、および450が実行される。対象ノード内に追加レコードを挿入する空き容量がなければ、追加レコードを多重検索ツリーに挿入するために、対象ノードを分割するステップ460、470、および480が実行される。まず、対象ノード内に追加レコードを挿入する空き容量がある場合に実行されるステップ430、440、および450について説明する。レコード挿入ステップ430で、対象ノードに追加レコードが挿入される。追加レコードの挿入後、下記のステップ440および450で、追加レコードの対象ノード内の位置値に基づいて対象ノードの累積移動平均cumulativemovingaverageまたは、移動平均runningaverageが計算される。挿入位置計算ステップ440で、追加レコードが対象ノード内に挿入された位置に基づいて追加レコードの対象ノード内の位置値が計算される。追加レコードの位置値は、0以上1以下の値であってもよい。追加レコードの位置値は、追加レコードが挿入されたスロットの番号indexを対象ノード内のレコードすなわち、対象ノード内に格納されたレコードの数で割った値であってもよい。スロットの番号は0または1から始まってもよい。下記の実施形態では、スロットの番号が1から始まるものと見なす。累積移動平均計算ステップ450で、追加レコードの位置値に基づいて対象ノードの累積移動平均が計算される。レコードを含まないノードの累積移動平均は、0または1に初期化されてもよい。累積移動平均は、下記の数式1に基づいて計算されてもよい。ここで、CAi-1は、追加レコードが挿入される前の対象ノードの累積移動平均である。また、CAiは、追加レコードが挿入された後に更新された累積移動平均である。iはシーケンスsequenceである。すなわち、対象ノードに任意のレコードが挿入されるたびに1ずつ増加する定数である。iは1から始まってもよい。xiは追加レコードの位置値である。xiにおいて、iはxiが対象ノードにi番目に挿入されたレコードの位置値であることを示す。すなわち、対象ノードの累積移動平均を計算するために使用された位置値は、順にx1、x2、x3、、xnである。削除delete、演算、または分割split演算に基づいて対象ノード内のレコードの数が減ることがある。このような場合、増加し続ける変数であるiが使用される場合、削除または分割後に対象ノードに挿入されるレコードの位置値が、累積移動平均の更新において過度に少なく反映されることがある。したがって、ノード内のレコードの数を反映して累積移動平均を更新するために、下記の数式2に基づいて累積移動平均が計算されてもよい。ここで、Iは、iおよび対象ノード内のレコードの数nのうちの最小値を意味する。すなわち、I=MINi、nである。数式1および数式2を参照しながら上述したように、対象ノードの累積移動平均は、追加レコードが挿入されたスロットの番号を対象ノード内のレコードの数nで割った値xi、累積移動平均CAi-1、対象ノード内のレコードの数n、および対象ノードに任意のレコードが挿入されるたびに1ずつ増加する定数iに基づいて計算されてもよい。下記では、レコードの挿入によってノードの累積移動平均が計算される一例について、図5を参照しながら詳しく説明する。累積移動平均は、ノードのヘッダheaderに保存されてもよい。すなわち、対象ノードに対して計算された累積移動平均は、対象ノードのヘッダに保存されてもよく、以後には更新のために対象ノードのヘッダから抽出されてもよい。次に、対象ノード内に追加レコードを挿入する空き容量がない場合に実行されるステップ460、470、および480について説明する。分割位置計算ステップ460で、対象ノードの累積移動平均に基づいて分割対象レコードの分割位置が計算される。分割対象レコードとは、対象ノードが分割されるとき、分割によって生成される2つのノードのうちの1つのノードに含まれるレコード、および対象ノードの親ノードに伝達されるレコードを意味してもよい。すなわち、分割対象レコードとは、対象ノード内のレコードおよび追加レコードを意味してもよい。また、分割対象レコードは、対象ノード内のレコードを含んでもよい。分割位置は、分割対象レコードが昇順に羅列した一連seriesのうちで特定の位置を示してもよい。対象ノードの分割位置は、対象ノード内のレコードおよび追加レコードのうち、対象ノードが分割されるときに対象ノードの親ノードに伝達されるレコードを示してもよい。すなわち、対象ノードの分割位置が計算されれば、計算された分割位置に対応するレコードが分割の基準となってもよく、分割の基準となったレコードが分割のために対象ノードの親ノードに伝達されてもよい。計算された分割位置に対応するレコードを基準レコードと命名する。ノードの累積移動平均に基づいてノードの分割位置を計算する具体的な方法については、図6~図8を参照しながら詳しく後述する。ノード分割ステップ470で、分割位置を基準として、対象ノードは左側分割ノードおよび右側分割ノードに分割される。すなわち、基準レコードの値よりも小さな値を有するレコードは左側分割ノードに含まれてもよく、基準レコードの値よりも大きな値を有するレコードは右側分割ノードに含まれてもよい。また、分割対象レコードが昇順に整列したとき、分割対象レコードのうちで基準レコードよりも前に位置するレコードは左側分割ノードに含まれてもよく、分割対象レコードのうちで基準レコードよりも後ろに位置するレコードは右側分割ノードに含まれてもよい。この後、ステップ410が再実行されることにより、基準レコードは挿入のために対象ノードの親ノードに伝達されてもよい。分割されたノード初期化ステップ480で、左側分割ノードおよび右側分割ノードはそれぞれ初期化されてもよい。左側分割ノードの累積移動平均は、対象ノードの累積移動平均に初期化されてもよい。また、右側分割ノードの累積移動平均は、対象ノードの累積移動平均に初期化されてもよい。左側分割ノードのシーケンスiは0に初期化されてもよい。このようなシーケンスiの初期化は、左側分割ノードに新たに挿入されるレコードが左側分割ノードの累積移動平均に高い影響を与えるようにする。また、右側分割ノードのシーケンスiは0に初期化されてもよい。ステップ460、470、および480が実行されれば、ステップ410が再実行される。再実行されるステップ410は、ステップ470で、左側分割ノードおよび右側分割ノードに含まれないレコードすなわち、基準レコードを対象ノードの親ノードに挿入するステップであってもよい。すなわち、追加レコードは、ステップ470の基準レコードに変更されてもよい。また、再実行されたステップ410で検索されたノードは、以前の対象ノードの親ノードであってもよい。上述されたステップ410~480を含む多重検索ツリーにレコードを挿入する方法は、多重検索ツリーのノード分割方法として見なされてもよい。すなわち、ステップ430~450は、分割対象ノードの累積移動平均を計算するステップとしてもよく、ステップ460~480は、計算された累積移動平均に基づいて分割対象ノードを分割するステップとしてもよい。図5は、本発明の一例に係る累積移動平均を計算する方法を説明している。第1ノード510は空白ノードである。空白ノードのシーケンスiの初期値は0であってもよい。また、空白ノードの初期累積移動平均CA0は、0または1であってもよい。第2ノード520は、第1ノード510にレコード40が挿入されたノードである。新たなレコードが挿入されることにより、シーケンスiは1増加する。したがって、このときのシーケンスiの値は1である。レコード40は、第2ノード520内の1つのレコードのうちで一番目の位置に挿入された。したがって、レコード40の位置値x1は1である。シーケンスiの値は1であり、第2ノード520内に挿入されたレコードの数は1である。したがって、Iの値は1である。数式2により、第2ノード520の累積移動平均CA1は1である。第3ノード530は、第2ノード520にレコード80が挿入されたノードである。新たなレコードが挿入されることにより、シーケンスiは1増加する。したがって、このときのシーケンスiの値は2である。レコード80は、第3ノード530内の2つのレコードのうちで二番目の位置に挿入された。したがって、レコード80の位置値x2は2/2=1である。シーケンスiの値は2であり、第3ノード530内に挿入されたレコードの数は2である。したがって、Iの値は2である。数式2により、第3ノード530の累積移動平均CA2は1である。第2ノード520および第3ノード530を検討すれば、新たに挿入されたレコードがノード内のレコードのうちで最も後ろに位置すればすなわち、新たに挿入されたレコードの値がノード内のレコードそれぞれの値以上であれば、ノードの累積移動平均は1に維持されることがあり、1により近い値に増加することが分かる。第4ノード540は、第2ノード520にレコード20が挿入されたノードである。新たなレコードが挿入されることにより、シーケンスiは1増加する。したがって、このときのシーケンスiの値は2である。レコード20は、第4ノード540内の2つのレコードのうちで一番目の位置に挿入された。したがって、レコード20の位置値x2は1/2である。シーケンスiの値は2であり、第4ノード540内に挿入されたレコードの数は2である。したがって、Iの値は2である。数式2により、第4ノード540の累積移動平均CA2は3/4である。第5ノード550は、第4ノード540にレコード10が挿入されたノードである。新たなレコードが挿入されることにより、シーケンスiは1増加する。したがって、このときのシーケンスiの値は3である。レコード10は、第5ノード550内の3つのレコードのうちで一番目の位置に挿入された。したがって、レコード10の位置値x3は1/3である。シーケンスiの値は3であり、第5ノード550内に挿入されたレコードの数は3である。したがって、Iの値は3である。数式2により、第5ノード550の累積移動平均CA3は22/36である。第2ノード520、第4ノード540、および第5ノード550を検討すれば、新たに挿入されたレコードがノード内のレコードのうちで最も前に位置すればすなわち、新たに挿入されたレコードの値がノード内のレコードそれぞれの値以下であれば、ノードの累積移動平均は0により近い値に減少することが分かる。ノード内に挿入されるレコードの値が示すパターンが漸進的な増加に近いほど、ノードの累積移動平均が1に近くなってもよい。したがって、ノードの累積移動平均が1に近ければ、ノードを分割するとき、左側分割ノードすなわち、低い値を有するレコードが挿入されるノードに多くのレコードを保存し、右側分割ノードすなわち、高い値を有するレコードが挿入されるノードに少ないレコードを保存することにより、左側分割ノードおよび右側分割ノードに割り当てられた保存場所が効率的に使用されるようにできる。これとは反対に、ノードの累積移動平均が0に近ければ、ノードを分割するとき、左側分割ノードに少ないレコードを保存し、右側分割ノードに少ないレコードを保存することにより、左側分割ノードおよび右側分割ノードに割り当てられた保存場所が効率的に使用されるようにできる。すなわち、ノードの累積移動平均に基づいてノードを分割することにより、分割されたノードに割り当てられた保存場所を効率的に使用できるようになる。また、ノードの累積移動平均に基づいてノードを分割することにより、多重検索ツリーの高さをさらに低めることができる。図6は、本発明の一例に係るノードの累積移動平均に基づいてノードの分割位置を決める方法を説明している。ノードの分割位置は、ノードの累積移動平均に比例して決められてもよい。以下、ノードの累積移動平均をCACumulativemovingaverageと略述し、ノードの分割位置をSPsplitpointと略述する。昇順に整列した分割対象レコードの全体の長さをTRLtotalrecordlengthと略述する。例えば、CAの値が1であれば、SPはTRLの終端となってもよい。ここで、分割対象レコードは、図4を参照しながら上述した分割対象レコードを示してもよい。すなわち、分割対象レコードは、ノードすなわち、図4の対象ノード内に既に挿入されたレコード、およびノード内に新たに挿入されるレコードすなわち、図4の追加レコードを意味してもよい。すなわち、CAの値が1であれば、分割対象レコードはすべて左側分割ノードに含まれてもよく、右側分割ノードは空のノードであってもよい。例えば、CA値が0または0に極めて近い値であれば、SPはTRLの始めすなわち、0であってもよい。すなわち、CAの値が0であれば、分割対象レコードはすべて右側分割ノードに含まれてもよく、左側分割ノードは空のノードであってもよい。または、CAに比例して昇順に整列した分割対象レコードのうち、基準レコードが決められてもよい。このとき、SPは、決められた基準レコードを示す値を有してもよい。例えば、CAが0.5であれば、SPは昇順に整列した分割対象レコードのうちで中間値すなわち、上位50の値を有するレコードを示す値を有してもよい。図6に示すように、SPは、CAが属する範囲に基づいて決められてもよい。図6のグラフ610は、CAの分布を示している。CAが第1指定された範囲例えば、t2以上またはt3以下内の値である場合、SPはTRLの中間を示してもよい。すなわち、SPの値は、TRLに0.5を掛けた値であってもよい。CAが第2指定された範囲例えば、t1以上またはt2以下、またはt3以上またはt4以下内の値である場合、SPは、TRLをCAの割合で割った位置を示してもよい。すなわち、SPの値は、TRLにCAを掛けた値であってもよい。CAが第3指定された範囲例えば、t1以下またはt4以上内の値である場合、SPは、TRLを予め指定された割合例えば、P1またはP2で割った位置を示してもよい。SPの値は、TRLにP1/100または、P2/100を掛けた値であってもよい。前記のP1およびP2は例示的なものである。すなわち、SPの値は、TRLにP3を掛けた値であってもよい。P3は、0以上1以下の自然数であってもよい。上述したt1、t2、t3、およびt4は、特定の値であってもよい。例えば、t1の値は0.05であってもよい。t2の値は0.2であってもよい。t3の値は0.8であってもよい。t4の値は0.95であってもよい。図7は、本発明の一例に係る固定長さレコードがSPによって分割される方法を説明している。対象ノード710は、4つのレコード712、714、716、および718を含んでいる。対象ノード710にレコード40720が挿入されれば、分割対象レコード712、714、716、718、および720は、昇順に整列する場合、レコード10712、レコード20714、レコード30716、レコード40720、およびレコード50718の順になる。SPがTRLの中間である場合、SPが示すレコードはレコード30716である。したがって、レコード30716が基準レコードとして決まる。対象ノード710が分割されれば、左側分割ノード740は基準レコード716よりも前に位置したレコード712および714を含み、右側分割ノード750は基準レコード716よりも後ろに位置したレコード720および718を含む。基準レコード716は、対象ノード710の親ノード730に挿入される。図8は、本発明の一例に係る可変長さレコードがSPによって分割される方法を説明している。対象ノード810は、4つのレコード812、814、816、および718を含む。レコードAA812の長さは2である。レコードBBBB814の長さは4である。レコードC816の長さは1である。レコードDD818の長さは2である。対象ノード810に長さが2であるレコードEE820が挿入されれば、分割対象レコード812、814、816、818、および820は、昇順に整列する場合、レコードAA812、レコードBBBB814、レコードC816、レコードDD718、およびレコードEE820の順となる。このとき、TRLは11である。SPがTRLの中間である場合、SPの値は6である。したがって、分割対象レコードの一連のうち、前から6だけ離れた位置がSPになってもよい。これは、分割対象レコードが占める記憶領域のうち、前から6番目の記憶単位例えば、バイトbyte、ワードword、またはフィールドfieldを示してもよい。分割対象レコードのうちでSPの値に対応する位置を占めるレコードは、レコードBBBB814である。したがって、レコードBBBB814が基準レコードとして決まる。対象ノード810が分割されれば、左側分割ノード840は基準レコード814よりも前に位置したレコード812を含み、右側分割ノード850は基準レコード814よりも後ろに位置したレコード816、818、および820を含む。図9は、本発明の一例に係る記憶装置900の構造図である。記憶装置900は、挿入処理部910、累積移動平均計算部920、分割処理部930、および格納部940を含んでもよい。挿入処理部910は、ステップ410、420、および430を実行してもよい。例えば、挿入処理部910は、多重検索ツリーの第1ノードにレコードを挿入してもよい。累積移動平均計算部920は、ステップ440および450を実行してもよい。例えば、累積移動平均計算部920は、挿入されたレコードの第1ノード内の位置値に基づいて第1ノードの累積移動平均を計算してもよい。位置値は、レコードが挿入されたスロットの番号を第1ノード内のレコードの数で割った値であってもよい。また、累積移動平均計算部920は、1レコードが挿入されたスロットの番号を第1ノード内のレコードの数で割った値、2累積移動平均、3第1ノード内のレコードの数、および4第1ノードに任意のレコードが挿入されるたびに1ずつ増加する定数に基づいて累積移動平均を更新することにより、第1ノードの累積移動平均を計算してもよい。累積移動平均計算部920は、上述した数式1または数式2に基づいて累積移動平均を計算してもよい。分割処理部930は、ステップ460、470、および480を実行してもよい。例えば、分割処理部930は、累積移動平均に基づいて第1ノードの分割位置を計算してもよく、計算された分割位置を基準として第1ノードを第2ノードおよび第3ノードに分割してもよい。分割処理部930は、累積移動平均が指定された範囲内の値である場合、昇順に整列した分割対象レコードの全体の長さの中間を分割位置として決めてもよい。分割処理部930は、累積移動平均が指定された範囲内の値である場合、昇順に整列した分割対象レコードの全体の長さを予め指定された割合で割る位置を分割位置として決めてもよい。分割処理部930は、累積移動平均が指定された範囲内の値である場合、昇順に整列した分割対象レコードの全体の長さを累積移動平均の割合で割る位置を分割位置として決めてもよい。記憶部940は、多重検索ツリーを格納してもよい。記憶部940は、多重検索ツリーを構成するノードを格納してもよい。記憶部940は、ノードのヘッダにノードの累積移動平均およびシーケンスを格納してもよい。図1~図8を参照しながら上述した本発明の一実施形態に係る技術的内容は、本実施例にそのまま適用されてもよい。したがって、より詳細な説明は、以下では省略する。構成要素910、920、および930の機能は、単一な制御部図示せずで実行されてもよい。このとき、制御部は、単一singleまたは複数multiチップchip、プロセッサprocessor、またはコアcoreを示してもよい。構成要素910、920、および930それぞれは、制御部で実行される関数function、ライブラリlibrary、サービスservice、プロセスprocess、スレッドthread、またはモジュールmoduleを示してもよい。本発明の一実施形態に係る方法は、多様なコンピュータ手段によって実行が可能なプログラム命令形態で実現されてコンピュータで読み取り可能な媒体に記録されてもよい。コンピュータで読み取り可能な媒体は、プログラム命令、データファイル、データ構造などを単独または組み合わせて含んでもよい。媒体に記録されるプログラム命令は、実施形態のために特別に設計されて構成されたものであってもよく、コンピュータソフトウェアの当業者に公知されて使用可能なものであってもよい。コンピュータで読み取り可能な記録媒体の例としては、ハードディスク、フロッピー登録商標ディスク、および磁気テープのような磁気媒体magneticmedia、CD-ROM、DVDのような光記録媒体opticalmedia、フロプティカルディスクflopticaldiskのような磁気-光媒体magneto-opticalmedia、およびROM、RAM、フラッシュメモリなどのようなプログラム命令を格納して実行するように特別に構成されたハードウェア装置が含まれる。プログラム命令の例としては、コンパイラによって生成されるもののような機械語コードだけではなく、インタプリタなどを使用してコンピュータによって実行される高級言語コードを含む。上述したハードウェア装置は、実施形態の動作を実行するために1つ以上のソフトウェアモジュールとして作動するように構成されてもよく、その逆も同じである。以上のように、本発明は限定された実施例と図面に基づいて説明されたが、本発明は前記の実施例に限定されるものではなく、本発明が属する分野において通常の知識を有する者であれば、このような記載から多様な修正および変形が可能である。したがって、本発明の範囲は、説明された実施例に限定されて定められてはならず、添付の特許請求の範囲だけではなく、この特許請求の範囲と均等なものに基づいて定められなければならない。