(57)【特許請求の範囲】
【請求項１】
所定の情報処理装置のコンピュータに実行させるデータ処理プログラムであって、
前記コンピュータに、複数の階層で構成されるデータ構造であり、所定のデータの実体および当該データの実体が格納されているメモリ上の場所を示す情報の少なくとも一方を含む要素であるデータ要素が複数存在し、かつ、当該データ要素が互いに関連づけられることで順序づけられた連結リストとして構成されている階層であるデータ要素層と、当該データ要素層より上の階層に位置し、自身の一つ下の階層にある要素のうちの一つと関連づけられている要素である中継ノードが複数存在する中継ノード層とで構成され、当該中継ノード層は更に階層化されており、各階層において各中継ノードは自身の一つ下の階層にある要素の順序に沿って順序づけられ、同じ階層において当該順序内の位置が隣接する関係となる中継ノードは互いに関連づけられている積層リスト構造を生成する積層リスト構造生成ステップを実行させる、データ処理プログラム。
【請求項２】
前記データ処理プログラムは、前記コンピュータに、前記データ要素層での前記順序内における位置が最後尾のデータ要素と関連づけた新たなデータ要素を生成し、当該新たなデータ要素の位置が最後尾となるように前記データ要素層に追加するデータ追加ステップを更に実行させる、請求項１に記載のデータ処理プログラム。
【請求項３】
前記データ処理プログラムは、前記コンピュータに、
前記データ要素の追加の結果、前記中継ノード層の各階層において、最後尾に順序づけられた中継ノードに関連づけられている一階層下の要素から、当該要素の位置する階層の最後尾に順序づけられた要素までの要素である子ノードの数が所定値を超えたか否かを判定する子ノード数判定ステップと、
前記子ノード数判定ステップにおいて前記子ノードの数が第１の所定値を超えたと判定されたとき、前記最後尾に順序づけられた中継ノードの次に新たな中継ノードを追加し、当該追加された中継ノードを前記子ノードのうちのいずれかと関連づける中継ノード追加ステップとを更に実行させる、請求項２に記載のデータ処理プログラム。
【請求項４】
前記データ処理プログラムは、前記コンピュータに、前記データ要素層での所定の位置に新しいデータ要素を挿入し、前記順序内における位置が当該挿入する位置に隣接するデータ要素と当該新しいデータ要素とを関連づけるデータ挿入ステップを更に実行させる、請求項１に記載のデータ処理プログラム。
【請求項５】
前記データ処理プログラムは、前記コンピュータに、
前記データ要素の挿入の結果、所定の前記中継ノードに関連づけられている一階層下の要素から、当該中継ノードと同じ階層における順序内での位置が当該中継ノードの次の位置となる関係の中継ノードである隣接中継ノードに関連づけられている一階層下の要素までの要素である子ノードの数が所定値を超えたか否かを判定する子ノード数判定ステップと、
前記子ノード数判定ステップにおいて前記子ノードの数が第１の所定値を超えたと判定されたとき、前記所定の中継ノードと前記隣接中継ノードとの間に新たな中継ノードを挿入し、当該挿入された中継ノードを前記子ノードのうちのいずれかと関連づける中継ノード追加ステップとを更に実行させる、請求項４に記載のデータ処理プログラム。
【請求項６】
前記中継ノード追加ステップは、前記子ノードの順序内における位置が中心となるような位置の子ノードと前記追加あるいは挿入する中継ノードを関連づける、請求項３または５のいずれかに記載のデータ処理プログラム。
【請求項７】
前記データ要素は、前記所定のデータの実体であるデータフィールドと、当該データフィールドのメモリ上における格納位置を示す情報を有するデータノードとが一対となるよう関連づけられることで構成されており、
前記データ要素層における順序内での位置が隣接する関係になるデータノード同士が関連づけられることで前記連結リストが構成され、
前記中継ノードは前記データノードと関連づけられており、
前記データ挿入ステップは、前記データ要素層での順序内における前記新しいデータ要素を挿入しようとする位置のデータノードが、前記中継ノードと関連づけられているデータノードであるとき、当該挿入しようとする位置のデータノードと関連づけられているデータフィールドと新しいデータノードとを関連付け、新しいデータフィールドと当該挿入しようとする位置のデータノードとを関連付け、当該新しいデータノードを含むデータ要素を挿入しようとするデータノードの次に来るように挿入する、請求項４に記載のデータ処理プログラム。
【請求項８】
前記データ操作プログラムは、前記コンピュータに、前記階層化されている中継ノード層において最上層の中継ノード層に複数の中継ノードが存在するとき、当該最上層の中継ノードの先頭の中継ノードに関連付けた新たな中継ノードを生成し、当該新たな中継ノードを含む新たな中継ノード層を最上層として設定するルートノード設定ステップを更に実行させる、請求項２または４のいずれかに記載のデータ処理プログラム。
【請求項９】
前記データ処理プログラムは、前記コンピュータに、所定の前記データ要素を削除し、前記積層リスト構造が維持されるように当該削除したデータ要素と関連する前記中継ノードを調整するデータ削除ステップを更に実行させる、請求項１に記載のデータ処理プログラム。
【請求項１０】
前記データ要素は、前記所定のデータの実体であるデータフィールドと、当該データフィールドのメモリ上における格納位置を示す情報を有するデータノードとが一対となるよう関連づけられることで構成されており、
前記データ要素層における順序内での位置が隣接する関係になるデータノード同士が関連づけられることで前記連結リストが構成され、
前記中継ノードは前記データノードと関連づけられており、
前記データ削除ステップは、前記データ要素層での順序内における前記削除しようとする位置のデータノードが前記中継ノードと関連づけられているデータノードであるとき、当該削除しようとする位置のデータノードと当該データノードの次に位置するデータノードとの間でデータフィールドを交換し、当該データノードの次に位置するデータ要素を削除する、請求項９に記載のデータ処理プログラム。
【請求項１１】
前記データ処理プログラムは、前記コンピュータに、
前記データ削除ステップによるデータ要素の削除の結果、所定の前記中継ノードに関連づけられている一階層下の要素から、当該中継ノードと同じ階層における順序内での位置が当該中継ノードの次の位置となる関係の中継ノードである隣接中継ノードに関連づけられている一階層下の要素までの要素である子ノードの数が第２の所定値を下回ったか否かを判定する、子ノード数判定ステップと、
前記子ノード数判定ステップにおいて子ノードの数が第２の所定値を下回ったと判定されたとき、前記所定の中継ノードに対して一つ上の階層から関連づけられている中継ノードが存在するか否かを判定する上位ノード判定ステップと、
前記上位ノード判定ステップにおいて、前記所定の中継ノードに対して一つ上の階層から関連づけられている中継ノードが存在すると判定されたときは、当該中継ノードと同階層において当該所定の中継ノードの次に位置する中継ノードを削除し、当該所定の中継ノードに対して一つ上の階層から関連づけられている中継ノードが存在しないと判定されたときは、当該所定の中継ノードを削除する中継ノード削除ステップとを更に実行させる、請求項９に記載のデータ処理プログラム。
【請求項１２】
前記データ処理プログラムは、前記コンピュータに、
前記データ削除ステップによるデータ要素の削除の結果、所定の前記中継ノードに関連づけられている一階層下の要素から、当該中継ノードと同じ階層における順序内での位置が当該中継ノードの次の位置となる関係の中継ノードである隣接中継ノードに関連づけられている一階層下の要素までの要素である子ノードの数が第２の所定値以下であるか否かを判定する、子ノード数判定ステップと、
前記子ノード数判定ステップにおいて子ノード数が第２の所定値を下回ったと判定されたとき、前記所定の中継ノードに対して一つ上の階層から関連づけられている中継ノードが存在するか否かを判定する上位ノード判定ステップと、
前記上位ノード判定ステップにおいて、前記所定の中継ノードに対して一つ上の階層から関連づけられている中継ノードが存在すると判定されたときは、当該中継ノードと同階層において当該所定の中継ノードの次に位置する中継ノードを基準ノードとして設定し、当該所定の中継ノードに対して一つ上の階層から関連づけられている中継ノードが存在しないと判定されたときは、当該所定の中継ノードを基準ノードとして設定する基準ノード設定ステップと、
前記基準ノードの前の位置となる関係の中継ノードに関連づけられている一階層下の要素と、前記基準ノードの次の位置となる関係の中継ノードに関連づけられている一階層下の要素の間の前記子ノードの数が第３の所定値以下であるか否かを判定する調整数判定ステップと、
前記調整数判定ステップにおいて、前記第３の所定値以下と判定されたときは、前記基準ノードを削除し、前記第３の所定値以下と判定されなかったときは、前記子ノードと前記基準ノードとの関連付けを変更する子ノード調整ステップとを更に実行させる、請求項９に記載のデータ処理プログラム。
【請求項１３】
前記子ノード調整ステップは、前記基準ノードと同階層での順序内において当該基準ノードの前に位置する中継ノードに関連づけられている一階層下の要素と、前記基準ノードに関連づけられている一階層下の要素との間の子ノードの数と、前記基準ノードに関連づけられている一階層下の要素と、前記基準ノードと同階層での順序内において当該基準ノードの後ろに位置する中継ノードに関連づけられている一階層下の要素との間の子ノード数とが等しくなるように前記子ノードと前記基準ノードとの関連付けを変更する、請求項１２に記載のデータ処理プログラム。
【請求項１４】
前記データ操作プログラムは、前記中継ノード自身に関連づけられている一階層下の要素から当該中継ノードと同じ階層における順序内での位置が当該中継ノードの次の位置となる関係の中継ノードである隣接中継ノードに関連づけられている一階層下の要素までの要素である子ノードの数を示す子ノード情報を各中継ノードと関連づけて記憶する、子ノード数保持ステップを更に実行させる、請求項１に記載のデータ処理プログラム。
【請求項１５】
所定の情報処理装置であるデータ処理装置であって、
複数の階層で構成されるデータ構造であり、所定のデータの実体および当該データの実体が格納されているメモリ上の場所を示す情報の少なくとも一方を含む要素であるデータ要素が複数存在し、かつ、当該データ要素が互いに関連づけられることで順序づけられた連結リストとして構成されている階層であるデータ要素層と、当該データ要素層より上の階層に位置し、自身の一つ下の階層にある要素のうちの一つと関連づけられている要素である中継ノードが複数存在する中継ノード層とで構成され、当該中継ノード層は更に階層化されており、各階層において各中継ノードは自身の一つ下の階層にある要素の順序に沿って順序づけられ、同じ階層において当該順序内の位置が隣接する関係となる中継ノードは互いに関連づけられている積層リスト構造を生成する積層リスト構造生成手段を備える、データ処理装置。    
【請求項１６】
所定の情報処理システムであるデータ処理システムであって、
複数の階層で構成されるデータ構造であり、所定のデータの実体および当該データの実体が格納されているメモリ上の場所を示す情報の少なくとも一方を含む要素であるデータ要素が複数存在し、かつ、当該データ要素が互いに関連づけられることで順序づけられた連結リストとして構成されている階層であるデータ要素層と、当該データ要素層より上の階層に位置し、自身の一つ下の階層にある要素のうちの一つと関連づけられている要素である中継ノードが複数存在する中継ノード層とで構成され、当該中継ノード層は更に階層化されており、各階層において各中継ノードは自身の一つ下の階層にある要素の順序に沿って順序づけられ、同じ階層において当該順序内の位置が隣接する関係となる中継ノードは互いに関連づけられている積層リスト構造を生成する積層リスト構造生成手段を備える、データ処理システム。
【請求項１７】
所定の情報処理装置または情報処理システムにおけるデータ処理で用いられるデータ処理方法であって、
複数の階層で構成されるデータ構造であり、所定のデータの実体および当該データの実体が格納されているメモリ上の場所を示す情報の少なくとも一方を含む要素であるデータ要素が複数存在し、かつ、当該データ要素が互いに関連づけられることで順序づけられた連結リストとして構成されている階層であるデータ要素層と、当該データ要素層より上の階層に位置し、自身の一つ下の階層にある要素のうちの一つと関連づけられている要素である中継ノードが複数存在する中継ノード層とで構成され、当該中継ノード層は更に階層化されており、各階層において各中継ノードは自身の一つ下の階層にある要素の順序に沿って順序づけられ、同じ階層において当該順序内の位置が隣接する関係となる中継ノードは互いに関連づけられている積層リスト構造を生成する積層リスト構造生成ステップを備える、データ処理方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、リスト構造を有するデータに対するデータ操作プログラムおよびデータ処理装置に関し、より特定的には、整列された連結リストに対するデータの検索・追加・削除の処理を実行するデータ処理プログラムおよびデータ処理装置に関する。
【背景技術】
【０００２】
従来より、いわゆる平衡木の代替として考案されたデータ構造であるスキップリストと呼ばれるデータ構造がある（例えば、非特許文献１）。スキップリストは、平衡木に比べると単純なデータ構造であり、平衡木よりも実装が容易という利点がある。図５４は、当該スキップリストのデータ構造の一例である。図５４に示すように、スキップリストは複数個のポインタを持つ連結リストである。換言すれば、スキップリストはリストの階層になっており、最下層は通常のソートされた連結リストである。上層は、当該複数個のポインタによって「急行列車」のような働きをする。各要素の持つポインタの個数は、各要素が割り当てられるとき（追加されるとき）に、予め定められた確率ｐ（０＜ｐ＜１）の値と乱数を用いて決められる。また、スキップリストでは、各要素の下から数えてi番目のポインタは、i個以上のポインタを持つ、次の要素を指している。更に、スキップリストは、図５４に示すように、スキップリストの先頭の要素を示す”header”と、スキップリストの最終要素を示す”ＮＩＬ”という特別な要素を有している。
【０００３】
スキップリストでは、目的の要素を探すために、スキップリストの先頭の要素から始めて、目的の要素と同じかそれ以下の要素のうち最後のものまでスキャンする。図５５に、検索対象として”１９”の要素を検索する場合の検索パスを示す。図５５では、まず、”header”の最上位層から検索を開始する。検索対象の値（”１９”）が、ポインタで指される要素の値（”６”）より大きい場合、同一の高さの層のポインタを順にたどっていく。その層での検索がＮＩＬに達すると、一つ下の層に移り、その層でのポインタを順にたどっていく（”６”→”２５”とたどる）。検索対象の値がポインタの指す要素の値より小さいかあるいは等しい場合、要素の移動は行わずに、一つ下の層に移って、その層でのポインタを順にたどっていく（”２５”の要素には移動せずに、”６”の要素のところで一つ下の層に移る）。このような検索を続けて、最下層に達したときに、そのすぐ右隣の要素が求める要素となる。この要素の値が検索対象の値と一致していれば検索は成功であり、一致していなければ検索失敗となる。このように、スキップリストでは、先頭から順に検索を行う場合に比べ、中間の要素をスキップして検索を行うことが可能となっている。また、スキップリストにおいて、検索にかかる平均計算量は、平衡木と同じＯ(log n)となっている。
【非特許文献１】「ＵＮＩＸ  ＭＡＧＡＺＩＮＥ」、株式会社アスキー、Ｐ６８〜８０、１９９９年１月号
【発明の開示】
【発明が解決しようとする課題】
【０００４】
しかしながら、上述したような上記非特許文献１に開示されたスキップリストにおいては、以下に示す問題点があった。まず、スキップリストは、「先頭からｎ番目のデータ」のような、データの先頭からの順番を指定したアクセス（以下、インデックスアクセスと呼ぶ）ができない仕様になっている。すなわち、スキップリストでは、各要素は、自身のデータそのものと、自身がどの要素にリンクするかについての情報（ポインタ）は有しているが、自分が「先頭から何番目のデータであるか」という情報は有していない。そのため、上記インデックスアクセスができない構造となっている。
【０００５】
また、上記スキップリストのオーダに関して、上記のように各要素の持つポインタの個数は乱数によって決めており、オーダはその乱数の性能に依存することになる。理論上はスキップリストのオーダは平衡木と同じＯ(log n)であるが、上記の乱数に偏りが生じた場合は、オーダの悪化が生じることがあり、場合によっては、常に最悪のオーダになる可能性がある。
【０００６】
また、データの削除を行った際に、ポインタを多く持っている要素ばかりを削除した場合や、逆に、ポインタが少ない要素ばかりを削除した場合、上記のようなＯ(log n)という性能が発揮できないという問題もある。例えば、図５４で言うと、背の低い要素（ポインタ数の少ない要素）ばかりが削除されたような場合、スキップできる要素の数が減ることとなり、Ｏ(log n)というオーダの性能が発揮できなくなる。また、図５４の背の高い要素（ポインタ数の多い要素）ばかりが削除された場合は、単なる連結リストと大差が無いことになる。
【０００７】
それ故に、本発明の目的は、データの追加や削除が行われても、検索性能の変動が少ないデータ構造を有するデータを作成するデータ処理プログラムおよびデータ処理装置を提供することである。
【課題を解決するための手段】
【０００８】
本発明は、上記の課題を解決するために、以下の構成を採用した。なお、括弧内の参照符号および補足説明等は、本発明の理解を助けるために後述する実施形態との対応関係の一例を示したものであって、本発明を何ら限定するものではない。
【０００９】
第１の発明は、所定の情報処理装置のコンピュータに実行させるデータ処理プログラムであって、コンピュータに、複数の階層で構成されるデータ構造であり、所定のデータの実体および当該データの実体が格納されているメモリ上の場所を示す情報の少なくとも一方を含む要素であるデータ要素が複数存在し、かつ、当該データ要素が互いに関連づけられることで順序づけられた連結リストとして構成されている階層であるデータ要素層と、当該データ要素層より上の階層に位置し、自身の一つ下の階層にある要素のうちの一つと関連づけられている要素である中継ノードが複数存在する中継ノード層とで構成され、当該中継ノード層は更に階層化されており、各階層において各中継ノードは自身の一つ下の階層にある要素の順序に沿って順序づけられ、同じ階層において当該順序内の位置が隣接する関係となる中継ノードは互いに関連づけられている積層リスト構造を生成する積層リスト構造生成ステップを実行させる。
【００１０】
第１の発明によれば、検索性能を高め、且つ、データの追加や削除が実行されたときでも検索性能の変動が少ないデータ構造を利用することができる。
【００１１】
第２の発明は、第１の発明において、データ処理プログラムは、コンピュータに、データ要素層での順序内における位置が最後尾のデータ要素と関連づけた新たなデータ要素を生成し、当該新たなデータ要素の位置が最後尾となるようにデータ要素層に追加するデータ追加ステップ（Ｓ４１〜Ｓ４４）を更に実行させる。
【００１２】
第２の発明によれば、情報処理装置等の処理負荷を軽減しながら積層リスト構造に対してデータを追加することができる。
【００１３】
第３の発明は、第２の発明において、データ処理プログラムは、コンピュータに、データ要素の追加の結果、中継ノード層の各階層において、最後尾に順序づけられた中継ノードに関連づけられている一階層下の要素から、当該要素の位置する階層の最後尾に順序づけられた要素までの要素である子ノードの数が所定値を超えたか否かを判定する子ノード数判定ステップ（Ｓ６４）と、子ノード数判定ステップにおいて子ノードの数が第１の所定値を超えたと判定されたとき、最後尾に順序づけられた中継ノードの次に新たな中継ノードを追加し、当該追加された中継ノードを子ノードのうちのいずれかと関連づける中継ノード追加ステップ（Ｓ４５、Ｓ９１）とを更に実行させる。
【００１４】
第３の発明によれば、中継ノード同士の間隔に偏りが生じないようにデータを追加することができ、積層リスト構造の検索性能を維持しながらデータを追加することができる。
【００１５】
第４の発明は、第１の発明において、データ処理プログラムは、コンピュータに、データ要素層での所定の位置に新しいデータ要素を挿入し、順序内における位置が当該挿入する位置に隣接するデータ要素と当該新しいデータ要素とを関連づけるデータ挿入ステップ（Ｓ８２〜Ｓ９６）を更に実行させる。
【００１６】
第４の発明によれば、積層リスト構造の検索性能を維持しながらデータを追加することができる。
【００１７】
第５の発明は、第４の発明のいずれかにおいて、データ処理プログラムは、コンピュータに、データ要素の挿入の結果、所定の中継ノードに関連づけられている一階層下の要素から、当該中継ノードと同じ階層における順序内での位置が当該中継ノードの次の位置となる関係の中継ノードである隣接中継ノードに関連づけられている一階層下の要素までの要素である子ノードの数が所定値を超えたか否かを判定する子ノード数判定ステップ（Ｓ６４）と、子ノード数判定ステップにおいて子ノードの数が第１の所定値を超えたと判定されたとき、所定の中継ノードと隣接中継ノードとの間に新たな中継ノードを挿入し、当該挿入された中継ノードを子ノードのうちのいずれかと関連づける中継ノード追加ステップ（Ｓ４５、Ｓ９１）とを更に実行させる。
【００１８】
第６の発明は、第３または第５のいずれかの発明において、中継ノード追加ステップは、子ノードの順序内における位置が中心となるような位置の子ノードと追加あるいは挿入する中継ノードを関連づける。
【００１９】
第５乃至第６の発明によれば、中継ノード同士の間隔に偏りが生じないようにデータを挿入することができ、積層リスト構造の検索性能を維持しながらデータを挿入することができる。
【００２０】
第７の発明は、第４の発明において、データ要素は、所定のデータの実体であるデータフィールドと、当該データフィールドのメモリ上における格納位置を示す情報を有するデータノードとが一対となるよう関連づけられることで構成されており、データ要素層における順序内での位置が隣接する関係になるデータノード同士が関連づけられることで連結リストが構成され、中継ノードはデータノードと関連づけられており、データ挿入ステップは、データ要素層での順序内における新しいデータ要素を挿入しようとする位置のデータノードが、中継ノードと関連づけられているデータノードであるとき、当該挿入しようとする位置のデータノードと関連づけられているデータフィールドと新しいデータノードとを関連付け、新しいデータフィールドと当該挿入しようとする位置のデータノードとを関連付け、当該新しいデータノードを含むデータ要素を挿入しようとするデータノードの次に来るように挿入する。
【００２１】
第７の発明によれば、既に存在するデータノードと中継ノードとの関連付けを変更する必要がなく、データ追加処理時における情報処理装置の処理負荷を軽減することができる。
【００２２】
第８の発明は、第２または第４の発明において、データ操作プログラムは、コンピュータに、階層化されている中継ノード層において最上層の中継ノード層に複数の中継ノードが存在するとき、当該最上層の中継ノードの先頭の中継ノードに関連付けた新たな中継ノードを生成し、当該新たな中継ノードを含む新たな中継ノード層を最上層として設定するルートノード設定ステップ（Ｓ６９，Ｓ７０）を更に実行させる。
【００２３】
第８の発明によれば、積層リスト構造の検索性能を維持しながらデータを追加・挿入することができる。
【００２４】
第９の発明は、第１の発明において、データ処理プログラムは、コンピュータに、所定のデータ要素を削除し、積層リスト構造が維持されるように当該削除したデータ要素と関連する中継ノードを調整するデータ削除ステップ（Ｓ１０１〜Ｓ１１１）を更に実行させる。
【００２５】
第９の発明によれば、積層リスト構造の検索性能を維持しながらデータを削除することができる。
【００２６】
第１０の発明は、第９の発明において、データ要素は、所定のデータの実体であるデータフィールドと、当該データフィールドのメモリ上における格納位置を示す情報を有するデータノードとが一対となるよう関連づけられることで構成されており、データ要素層における順序内での位置が隣接する関係になるデータノード同士が関連づけられることで連結リストが構成され、中継ノードはデータノードと関連づけられており、データ削除ステップは、データ要素層での順序内における削除しようとする位置のデータノードが中継ノードと関連づけられているデータノードであるとき、当該削除しようとする位置のデータノードと当該データノードの次に位置するデータノードとの間でデータフィールドを交換し、当該データノードの次に位置するデータ要素を削除する。
【００２７】
第１０の発明によれば、既に存在するデータノードと中継ノードとの関連付けを変更する必要がなく、データ削除処理時における情報処理装置の処理負荷を軽減することができる。
【００２８】
第１１の発明は、第９の発明において、データ処理プログラムは、コンピュータに、データ削除ステップによるデータ要素の削除の結果、所定の中継ノードに関連づけられている一階層下の要素から、当該中継ノードと同じ階層における順序内での位置が当該中継ノードの次の位置となる関係の中継ノードである隣接中継ノードに関連づけられている一階層下の要素までの要素である子ノードの数が第２の所定値を下回ったか否かを判定する、子ノード数判定ステップ（Ｓ１２４）と、子ノード数判定ステップにおいて子ノードの数が第２の所定値を下回ったと判定されたとき、所定の中継ノードに対して一つ上の階層から関連づけられている中継ノードが存在するか否かを判定する上位ノード判定ステップ（Ｓ１２５）と、上位ノード判定ステップにおいて、所定の中継ノードに対して一つ上の階層から関連づけられている中継ノードが存在すると判定されたときは、当該中継ノードと同階層において当該所定の中継ノードの次に位置する中継ノードを削除し、当該所定の中継ノードに対して一つ上の階層から関連づけられている中継ノードが存在しないと判定されたときは、当該所定の中継ノードを削除する中継ノード削除ステップ（Ｓ１３３）とを更に実行させる。
【００２９】
第１２の発明は、第１の発明において、データ処理プログラムは、コンピュータに、データ削除ステップによるデータ要素の削除の結果、所定の中継ノードに関連づけられている一階層下の要素から、当該中継ノードと同じ階層における順序内での位置が当該中継ノードの次の位置となる関係の中継ノードである隣接中継ノードに関連づけられている一階層下の要素までの要素である子ノードの数が第２の所定値以下であるか否かを判定する、子ノード数判定ステップ（Ｓ１２４）と、子ノード数判定ステップにおいて子ノード数が第２の所定値を下回ったと判定されたとき、所定の中継ノードに対して一つ上の階層から関連づけられている中継ノードが存在するか否かを判定する上位ノード判定ステップ（Ｓ１２５）と、上位ノード判定ステップにおいて、所定の中継ノードに対して一つ上の階層から関連づけられている中継ノードが存在すると判定されたときは、当該中継ノードと同階層において当該所定の中継ノードの次に位置する中継ノードを基準ノードとして設定し、当該所定の中継ノードに対して一つ上の階層から関連づけられている中継ノードが存在しないと判定されたときは、当該所定の中継ノードを基準ノードとして設定する基準ノード設定ステップ（Ｓ１２６〜Ｓ１２９）と、基準ノードの前の位置となる関係の中継ノードに関連づけられている一階層下の要素と、基準ノードの次の位置となる関係の中継ノードに関連づけられている一階層下の要素の間の子ノードの数が第３の所定値以下であるか否かを判定する調整数判定ステップ（Ｓ１３０）と、調整数判定ステップにおいて、第３の所定値以下と判定されたときは、基準ノードを削除し、第３の所定値以下と判定されなかったときは、子ノードと基準ノードとの関連付けを変更する子ノード調整ステップ（Ｓ１３１〜Ｓ１３６）とを更に実行させる。
【００３０】
第１３の発明は、第１２の発明において、子ノード調整ステップは、基準ノードと同階層での順序内において当該基準ノードの前に位置する中継ノードに関連づけられている一階層下の要素と、基準ノードに関連づけられている一階層下の要素との間の子ノードの数と、基準ノードに関連づけられている一階層下の要素と、基準ノードと同階層での順序内において当該基準ノードの後ろに位置する中継ノードに関連づけられている一階層下の要素との間の子ノード数とが等しくなるように子ノードと基準ノードとの関連付けを変更する。
【００３１】
第１１乃至１３の発明によれば、中継ノード同士の間隔に偏りが生じないようにデータを削除することができ、積層リスト構造の検索性能を維持しながらデータを削除することができる。
【００３２】
第１４の発明は、第１の発明において、データ操作プログラムは、中継ノード自身に関連づけられている一階層下の要素から当該中継ノードと同じ階層における順序内での位置が当該中継ノードの次の位置となる関係の中継ノードである隣接中継ノードに関連づけられている一階層下の要素までの要素である子ノードの数を示す子ノード情報を各中継ノードと関連づけて記憶する、子ノード数保持ステップ（Ｓ６３、Ｓ６８、Ｓ１３１，Ｓ１３５）を更に実行させる。
【００３３】
第１４の発明によれば、子ノード数の情報を中継ノードに持たせることで、データの追加処理や削除処理を実行する際の検索性能の維持のための調整を行いやすくすることができる。
【００３４】
第１５の発明は、所定の情報処理装置であるデータ処理装置であって、複数の階層で構成されるデータ構造であり、所定のデータの実体および当該データの実体が格納されているメモリ上の場所を示す情報の少なくとも一方を含む要素であるデータ要素が複数存在し、かつ、当該データ要素が互いに関連づけられることで順序づけられた連結リストとして構成されている階層であるデータ要素層と、当該データ要素層より上の階層に位置し、自身の一つ下の階層にある要素のうちの一つと関連づけられている要素である中継ノードが複数存在する中継ノード層とで構成され、当該中継ノード層は更に階層化されており、各階層において各中継ノードは自身の一つ下の階層にある要素の順序に沿って順序づけられ、同じ階層において当該順序内の位置が隣接する関係となる中継ノードは互いに関連づけられている積層リスト構造を生成する積層リスト構造生成手段を備える、データ処理装置。
【００３５】
第１６の発明は、所定の情報処理装置の記憶手段に記憶されるデータ構造であって、
所定のデータの実体および当該データの実体が格納されている記憶手段上の場所を示す情報の少なくとも一方を含む要素であるデータ要素が複数存在し、かつ、当該データ要素が互いに関連づけられることで順序づけられた連結リストとして構成されている階層であるデータ要素層と、当該データ要素層より上の階層に位置し、自身の一つ下の階層にある要素のうちの一つと関連づけられている要素である中継ノードが複数存在する中継ノード層との複数の階層で構成され、当該中継ノード層は更に階層化されており、各階層において各中継ノードは自身の一つ下の階層にある要素の順序に沿って順序づけられ、同じ階層において当該順序内の位置が隣接する関係となる中継ノードは互いに関連づけられていることを特徴とするデータ構造。
【００３６】
第１５乃至第１６の発明によれば、上記第１の発明と同様の効果を得ることができる。
【発明の効果】
【００３７】
本発明によれば、データの追加、挿入や削除が実行されても検索性能の変動が小さいリスト構造を有するデータ構造を提供することができる。
【発明を実施するための最良の形態】
【００３８】
以下、本発明の実施の形態について、図面を参照して説明する。尚、この実施例により本発明が限定されるものではない。
【００３９】
まず、本実施形態にかかるデータ操作処理で用いられるデータの構造について説明する。図１は、本実施形態にかかるデータ構造（以下、積層リスト構造と呼ぶ）の一例である。積層リスト構造は、最下層に、隣接するノードとリンクされている（その結果、各ノードは一列に繋がることになり、順序を有することになる）連結リストを配置し、その上層に、複数のデータを束ねるような役割を持つ中継ノードと呼ばれる要素を階層化して構築したものである。
【００４０】
まず、図１に示した各要素の、本実施形態における呼称について説明する。本実施形態における積層リスト構造では、図１の最下層の楕円で示されている要素をデータフィールドと呼ぶ。また、データフィールド以外の四角で示されている要素をノードと呼ぶ。当該ノードには、データノードと中継ノードの２種類のノードが存在する。データノードは、データフィールドと直接関連づけられているノードである。中継ノードは、データノードの上層に位置するノードであり、複数の中継ノード層が階層化されて構成されている。また、中継ノードのうち、最上層に位置するノードのことを特にルートノードと呼ぶ。また、図１において、各ノードやデータフィールドを繋いでいる矢印は、”参照”を示している。”参照”については、後ほど説明する。
【００４１】
以下の説明においては、各データノードのことをＤＮｎｎ（ｎｎは“０１”から始まる整数、以下同様）と示し、各中継ノード（ルートノードも含む）のことをＲＮｎｎ（RelayNodeの略）と示す。
【００４２】
また、図１における各層については、データフィールドのある層（図１の最下層）のことをデータフィールド層と呼び、その一つ上の層をデータノード層と呼ぶ。中継ノードについては、下から順に中継ノード第１層、中継ノード第２層・・・中継ノード第ｎ層、のように呼ぶ。ルートノードのある層については単にルートノードと呼ぶ（原則として、最上層はノードが一つだけとなるため）。
【００４３】
また、以下の説明においては、積層リスト構造におけるデータの位置を指し示す言葉として「インデックス番号」という言葉を用いる。これは、「先頭からｎ番目」というような先頭を基点とした順番を示すものでもある。
【００４４】
次に、以下の説明で用いられる、所定のノードを中心とした場合の隣接する各ノード間の呼称について説明する。図２は、所定のノードを中心としたときの隣接する各ノードの呼称を説明するための図である。図２において、上記中心とする所定のノードのことをカレントノードと呼ぶ。これは、後述する処理において、現在処理対象となっているノードを示す。次に、カレントノードと同じ層における左隣のノード（つまり、一つ手前のノード）を前ノードと呼ぶ。また、同じ層における右隣のノード（つまり、一つ次のノード）を次ノードと呼ぶ。更に、カレントノードより一つ下の層のノードであり、後述のようなカレントノードからの”参照”先として設定されている（直接関連づけられている）ノードを先頭ノードと呼ぶ。
【００４５】
また、カレントノードより一つ上の層のノードを親ノードと呼び、一つ下の層のノードを子ノードと呼ぶが、この親子関係に関して、図３を用いて説明する。図３〜図５は、本実施形態のノード間の親子関係を説明するための図である。図３は、データ要素（データノード層）と中継ノード第１層とに着目した親子関係を示している。図３において、ＲＮ０１を基準（カレントノード）とすると、子ノードと呼ばれるノードは、ＤＮ０１〜０３である。このうち、ＲＮ０１の直接の参照先として設定されているＤＮ０１は、上記先頭ノードでもある。同様に、ＲＮ０２をカレントノードと考えると、子ノードと呼ばれるノードは、ＤＮ０４〜０６である。また、ＤＮ０４は、先頭ノードでもある。一方、データノード側を基準に考えると、まず、ＤＮ０１〜ＤＮ０３については、ＲＮ０１が親ノードとなる。また、ＤＮ０４〜０６の親ノードは、ＲＮ０２となる。つまり、子ノードとは、カレントノードの一つ下の階層のノードのうち、先頭ノードから、カレントノードの次ノードからの参照がなされているノードの手前までのノードのことをいう。また、親ノードは、自身の一つ上の層のノードであって、自身が先頭ノードの場合は、自身の参照元のノードである。また、自身が先頭ノードではない場合は、自身より手前にある先頭ノードのうち、最も自身に近い先頭ノードの参照元となっているノードである。また、親ノードについては、後述するような処理との関係上、次のように述べることもできる。本実施形態において、積層リスト構造では上から下に向けて検索がなされる関係上、親ノードは、「一つ上の層において、最後にアクセスされた中継ノード」のことを示すものである。
【００４６】
図４は、中継ノード第１層と第２層に着目した親子関係を示している。図４においては、ＲＮ１１とＲＮ０１およびＲＮ０２とが親子関係になり、ＲＮ１２とＲＮ０３が親子関係となっている。また、図５は、中継ノード第２層と第３層（ルートノード）に着目した親子関係を示している。図５では、ルートノードであるＲＮ２１と、中継ノード第２層のＲＮ１１およびＲＮ１２とが親子関係となっている。
【００４７】
次に、上記図１で示した各要素毎の内容について説明する。まず、最下層（データフィールド層）に位置するデータフィールドは、データの実体を示している。また、各データフィールドは、図１でいうと左端を先頭として順序づけられて構成されている。換言すれば、データフィールド層は、順序づけられた連結リストに該当する。
【００４８】
次に、データノードは、図６に示すような情報を有している。図６は、図１に示したデータノードの詳細を示す図である。図６において、データノードは、前参照１０１、データ参照１０２、次参照１０３という情報を有している。その他、図示は省略するが、自身が中継ノードであるかデータノードであるかを識別するための識別子も有している。
【００４９】
図６において、前参照１０１は、上記前ノードへの”参照”を示している。例えば、図１を例にすると、ＤＮ０２の前参照１０１は、ＤＮ０１が格納されているメモリアドレスを示す。すなわち、ＤＮ０２を基準とすると、前ノードはＤＮ０１となる。なお、自身が一番左端の場合は、前参照１０１にはＮＵＬＬ値が設定される。
【００５０】
ここでいう”参照”とは、ＪＡＶＡ（登録商標）言語で用いられる”参照”と同義である。但し、その内容については、例えばＣ言語等で用いられる”ポインタ”であってもよい。あるいは、”リンク”と呼ばれるようなものでもよい。つまり、ＲＡＭ等のメモリ上において、他の要素（ここではノードやデータフィールド）が格納されているメモリアドレスを指し示すような内容であればよい。以下の説明では”参照”と表記して説明する。
【００５１】
次に、データ参照１０２は、データフィールドへの参照を示している。図１の例では、ＤＮ０２のデータ参照１０２は、先頭から２つめのデータフィールドが格納されているメモリアドレスを指し示している。
【００５２】
このように、本実施形態では、データノードとデータフィールドはそれぞれ１対１で関連づけられているが、当該関連づけられていたデータノードとデータフィールドの組のことを、以下の説明では”データ要素”と呼ぶこともある。
【００５３】
次に、次参照１０３は、上述したような次ノードへの”参照”を示している。例えば、図１の例で言うと、ＤＮ０２の次参照１０３は、ＤＮ０３が格納されているメモリアドレスを示す。すなわち、ＤＮ０２を基準とすると、次ノードはＤＮ０３となる。なお、自身が一番右端の場合は、次参照１０３にはＮＵＬＬ値が設定される。
【００５４】
次に、中継ノードの構成について説明する。図７は、図１に示した中継ノードの詳細を示す図である。中継ノードは、前参照２０１と、配下データ要素数２０２と、子ノード数２０３と、先頭ノード参照２０４と、次参照２０５という情報を有している。
【００５５】
前参照２０１は、前ノードへの”参照”を示している。例えば、図１の例で言うと、ＲＮ０２の前参照２０１は、ＲＮ０１のメモリアドレスを示す。なお、自身が一番左端の場合は、前参照２０１にはＮＵＬＬ値が設定される。
【００５６】
配下データ要素数２０２は、そのノードと親子関係にあるノードからアクセス可能なデータ要素数を示す（以下、このようなデータ要素を配下データ要素と呼ぶ）。図１を例にとると、ＲＮ０１の配下データ要素は、ＤＮ０１〜ＤＮ０３であり、ＲＮ０２の配下のデータ要素は、ＤＮ０４〜ＤＮ０６であり、ＲＮ０３の配下データ要素はＤＮ０７〜ＤＮ０８である。また、ＲＮ１１の配下データ要素は、ＤＮ０１〜ＤＮ０６となり、ＲＮ１２の配下のデータ要素は、ＤＮ０７〜ＤＮ０８となる。また、ルートノードであるＲＮ２１は、全データ要素が配下データ要素となる。換言すれば、自身の次ノードからは参照できない範囲までのデータ要素の数が配下データ要素数２０２となる。
【００５７】
次に、子ノード数２０３は、上述したような子ノードの数を示す情報である。すなわち、子ノード数２０３は、一つ下の階層のノードのうち、自身が参照している先頭ノードから、自身の次ノードからの参照がなされているノードの手前までのノードの数を示す。
【００５８】
先頭ノード参照２０４は、上記先頭ノードへの参照を示す情報である。図１を例にすると、ＲＮ０２の先頭ノード参照２０４は、ＤＮ０４のメモリアドレスを示す。また、ＲＮ１１の先頭ノード参照２０４は、ＲＮ０１のメモリアドレスを示す。
【００５９】
次参照２０５は、次ノードへの”参照”を示している。例えば、図１の例では、ＲＮ０１の次参照２０５は、ＲＮ０２のメモリアドレスを示す。
【００６０】
次に、ルートノードについて説明する。上記のように、ルートノード（図１ではＲＮ２１）は、積層リスト構造における最上層の中継ノードのことである。そのため、その構成は中継ノードと同様である（前参照２０１および次参照２０５には双方ともＮＵＬＬが設定される）。そして、積層リスト構造にアクセスする場合は、まず、このルートノードにアクセスすることになる。謂わば、当該ルートノードは、積層リスト構造へのアクセスの入り口的な位置づけにある。そのため、積層リスト構造の外部の要素には、ルートノードへの”参照”が定義されている。以下、当該ルートノードへの”参照”のこと（図１のルートノードの上にある、円で示されている要素）を「外部からの参照」と呼ぶ。
【００６１】
以下、上記のようなデータ構造におけるデータ処理、具体的には、データ検索・データ追加・データ削除の処理の概要を説明する。
【００６２】
まず、図１、および図８〜図１４を用いて、積層リスト構造におけるデータ検索、すなわち、インデックスアクセス（インデックス番号を指定したアクセス）の概要を説明する。一例として、図１のような積層リスト構造において、インデックス番号”５”、すなわち、先頭から５番目のデータにアクセスする場合を例として説明する。図８に、先頭から５番目のデータにアクセスする場合の検索パスを示す。図８に示すように、積層リスト構造では、各ノードの持つ配下データ要素数と、後述する変数”オフセット”を利用して、中間のデータ要素をスキップしながら目的とするデータ要素にアクセスしている。
【００６３】
まず、インデックスアクセスに際して、まず、”オフセット”と呼ばれる変数に”１”が設定される。これは、先頭からの順番を示す値でもある。また、上記カレントノードとしてルートノードであるＲＮ２１が設定される。
【００６４】
上記設定がなされた後、カレントノードについて、次のような内容が判定される。すなわち、カレントノードの有する配下データ要素数２０２の値と、上記オフセットの値を加算した値が、上記目的インデックス番号より大きいか否かが判定される。図９に示すように、カレントノードはＲＮ２１であるため、配下データ要素数”８”＋オフセット”１”＞インデックス番号”５”となり、加算値のほうがインデックス番号より大きいと判定される。
【００６５】
上記加算値のほうがインデックス番号より大きいと判定されたときは、下層のノードをカレントノードとして設定する。ここでは、図１０に示すように、ＲＮ１１がカレントノードとして設定される。そして、再度上記のような判定が行われる。ここでは、カレントノードがＲＮ１１であるため、配下データ要素数”６”＋オフセット”１”＞インデックス番号”５”となり、加算値のほうがインデックス番号より大きいと判定される。その結果、図１１に示すように、更に下層のノードであるＲＮ０１がカレントノードに設定される。
【００６６】
次に、当該ＲＮ０１についても上記のような判定が行われる。ここでは、配下データ要素数”３”＋オフセット”１”＜インデックス番号”５”という関係となる。つまり、加算値よりインデックス番号のほうが大きいと判定される。
【００６７】
加算値よりインデックス番号のほうが大きい場合は、下層には下がらずに、図１２に示すように、同じ層の次ノードであるＲＮ０２がカレントノードとして設定される。また、このとき、”オフセット”の値に、ＲＮ０１の配下データ要素数２０２の値が加算される。そして、ＲＮ０２について上記のような判定が行われる。その結果、配下データ要素数”３”＋オフセット”４”＞インデックス番号”５”となり、加算値のほうがインデックス番号より大きいと判定される。その結果、図１３に示すように、更に下層のノードであるＤＮ０４がカレントノードに設定される。
【００６８】
ここで、ＤＮ０４はデータノードである。すなわち、カレントノードがデータノード層まで下りてきたことになる。換言すれば、より下位の階層のノードが無いということになる。このように、カレントノードがデータノードとなったときは、次のような判定が行われる。すなわち、オフセットとインデックス番号が等しいか否かが判定される。その結果、等しくないときは、オフセットに”１”が加算され、次ノードがカレントノードとして設定される。図１３の例では、オフセット“４”≠インデックス番号“５”となるため、図１４に示すように、次ノードであるＤＮ０５がカレントノードとして設定される。
【００６９】
そして、ＤＮ０５についても、オフセットとインデックス番号が等しいか否かが判定される。換言すれば、オフセットと等しいインデックス番号が見つかるまで、次ノードが順次アクセスされていくことになる。図１４においては、オフセット”５”＝インデックス番号”５”となる。そのため、当該ＤＮ０５が検索目的であるデータ要素ということになり、ＤＮ０５の参照先であるデータフィールドからデータが取得される。以上で、インデックスアクセスの概要説明を終了する。
【００７０】
次に、積層リスト構造におけるデータの追加処理の概要について説明する。まず、本実施形態での追加処理は、データを追加する位置、および、具体的な処理内容の違いから、次の２つに大別される。１つめは、新しいデータを上記データフィールド層の末尾に追加するという処理（以下、末尾追加処理と呼ぶ）である。もう一つは、新しいデータを上記データフィールド層のデータフィールドの並びの途中（指定された位置）に挿入するという処理（以下、挿入処理と呼ぶ）である。図１５は、末尾追加処理と挿入処理の違いを示す図である。まず、図１５（ａ）に示すように、データＡ〜データＤという４つのデータがあるとする。本実施形態では、データを挿入する場合は、挿入したい位置を上記インデックス番号で指定する。例えば、先頭から３番目の位置にデータを挿入したい場合、インデックス番号に”３”を指定して後述するような挿入処理を実行する。この場合、上述のインデックスアクセスによって先頭から３番目のデータ、図１５（ａ）でいうとデータＣの「前」に新たなデータを挿入する。同様に、先頭にデータを挿入する場合は、インデックス番号に”１”を指定する。この場合は、図１５（ｃ）に示すように、１番目のデータであるデータＡの「前」に新たなデータが挿入される。一方、末尾追加処理は、上記のような追加したい位置の指定は行わず、図１５（ｄ）に示すように、単純にデータの並びの最後に新しいデータを追加する処理である。すなわち、末尾のデータであるデータＤの「後」に新しいデータを追加する。このように、本実施形態におけるデータの追加処理については、上述のような２種類の処理が実行される。例えば、新規に積層リスト構造を有するデータファイルを生成するようなときは末尾追加処理を実行することで新規のデータファイルを生成し、既に存在する積層リスト構造のデータファイルにデータを追加するようなときは、上記挿入処理を用いてデータを追加する。
【００７１】
次に、末尾追加処理の概要を説明する。上記のように、本処理は、新しく追加したいデータを上記のようなデータフィールドの並びの一番最後（図１でいうと一番右端）に追加するという処理である。そのため、本処理では、まず、末尾のデータ要素（図１でいうと、ＤＮ０８）にアクセスする。次に、当該データ要素の次の位置（ＤＮ０８の右隣）に新しいデータフィールド、および、これと関連づけられているデータノードを追加する。そして、関連するデータノード間の参照等を適宜更新するという処理が行われる。図１の例でいうと、ＤＮ０８の次参照１０３として、新たに追加したデータノードへの参照を設定する処理や、親ノードであるＲＮ０３の配下データ要素数２０２を”１”増やす処理等が行われる。
【００７２】
次に、挿入処理の概要について、図１６〜図２７を用いて説明する。データの挿入処理については、挿入する位置が上記先頭ノードであるか否かにより、若干処理内容が異なる。まず、先頭ノードのある位置にデータを挿入する場合の例として、先頭から４番目の位置に新たなデータを挿入する場合を例として説明する。
【００７３】
まず、上述したようなインデックスアクセスの処理によって、先頭から４番目のデータノードであるＤＮ０４へのアクセスが行われる。つまり、図１６に示すように、カレントノードはＤＮ０４となる。また、当該ＤＮ０４は上述したような”先頭ノード”でもある。
【００７４】
次に、新しいデータノード（以下、新データノードと呼ぶ）が生成される。当該新データノードには、挿入したいデータ（以下、新データと呼ぶ）への参照が設定されている。
【００７５】
次に、図１７に示すように、カレントノードであるＤＮ０４と新データノードとの間で、データフィールドの交換（より正確には、データ参照１０２の書換）が行われる。これは、先頭ノードの参照元である親ノード（図１６ではＲＮ０２）の先頭ノード参照２０４を変更せずに済ませるためである。
【００７６】
次に、図１８に示すように、新データノードがＤＮ０４の次の位置に挿入される。続いて、図１９に示すように、ＤＮ０４と新データノード間の次参照１０３、および前参照１０１が更新される。更に、新データノードとＤＮ０５間の参照についても更新される。すなわち、ＤＮ０４の次ノードが新ノードとなり、新ノードの次ノードがＤＮ０５となるように更新される。
【００７７】
次に、図２０に示すように、ＤＮ０４の親ノードであるＲＮ０２の配下データ要素数２０２、子ノード数２０３が更新される。つまり、データノードが一つ増えているため、これらの値に”１”が加算されることになる。
【００７８】
更に、図２１に示すように、ＲＮ０２の親ノードであるＲＮ１１、および、ＲＮ１１の親ノードにあたるＲＮ２１についても、同様に配下データ要素数２０２、子ノード数２０３の更新が行われる。なお、図２１の例では、子ノードに該当する中継ノードについては増加していないため、配下データ要素数２０２のみについて”１”加算されるだけである。以上で、先頭ノードの位置へのデータ挿入処理は終了する。
【００７９】
次に、先頭ノードではない位置へのデータ挿入の概要を説明する。一例として、先頭から３番目の位置にデータを挿入する場合を例として説明する。この場合は、図２２に示すように、まず、上記インデックスアクセスによって、先頭から３番目のデータノードであるＤＮ０３がアクセスされる。すなわち、カレントノードがＤＮ０３となる。
【００８０】
次に、新データへの参照が設定された新データノードが生成され、図２３に示すように、ＤＮ０３の手前の位置に挿入される。
【００８１】
そして、図２４に示すように、ＤＮ０２と新データノード間の参照が更新される。また、新データノードとＤＮ０３間の参照も更新される。
【００８２】
最後に、上述したのと同様に、対応する親のノードの配下データ要素数２０２、子ノード数２０３が更新される。つまり、先頭ノードではない位置へのデータ挿入の場合は、指定されたインデックス番号に基づいてデータ要素にアクセスし、単純にそのデータ要素の前に新たなデータを挿入する。以上で、先頭ノードではない位置へのデータ挿入処理は終了する。
【００８３】
次に、データの挿入の結果、中継ノード数が増加する場合について説明する。本実施形態では、データ要素を挿入した結果、中継ノードの子ノード数が所定の値（以下、最大閾値と呼ぶ）を超えると、その中継ノードを２つに分割する。これは、検索性能についてある程度の水準を維持するために行われるものである。すなわち、データ要素の挿入の結果、各中継ノードの間隔（スキップする間隔）について偏りが生じてしまわないようにすることで、検索性能が悪化することを防ぐものである。例えば、図１でいうとＤＮ０５の位置（ＤＮ０４の次の位置）に複数のデータが集中的に挿入されると、ＲＮ０２の配下におけるデータの検索に時間がかかってしまうことになるため、ＲＮ０２〜ＲＮ０３間の中継ノードを適宜増やすことで検索性能の低下を防ぐ。
【００８４】
なお、上記最大閾値は、本実施形態にかかるデータ操作処理が実行される情報処理装置の処理能力に応じて、予め適切な値を算出し、適宜調整することが好ましい。当該閾値を大きく採れば、中継ノードを増やす数を抑え、データ挿入処理時における処理負荷（中継ノード生成にかかる処理）を軽減できる点で有利であり、当該閾値を小さく採れば、中継ノードの数が増えることによる検索性能の向上を図ることができる点で有利である。そのため、上記情報処理装置の処理能力を考慮して、両者のバランスを採った値を設定することが好ましい。
【００８５】
以下、上記最大閾値の一例を”３”とし、図２５に示すように、ＤＮ０４の次に新データノードが挿入された結果、ＲＮ０２の子ノード数２０３が、最大閾値である”３”を超えた場合を例として説明する。この場合は、まず、図２６に示すように、新たな中継ノード（以下、新中継ノードと呼ぶ）が生成され、ＲＮ０２の次に来るように挿入される。
【００８６】
次に、図２７に示すように、ＲＮ０２と新中継ノード間の参照が更新され、新中継ノードとその後ろのノード（図２７では省略されているが、ＲＮ０３）との参照が更新される。更に、ＲＮ０２と新中継ノードの子ノード数２０３が更新される。このとき、双方の値が同数（ＲＮ０２の子ノード数が奇数の場合は、ほぼ同数）となるように更新される。具体的には、図２７の例では、データノード挿入の結果、ＲＮ０２の子ノード数が”４”となったため、”２”で更新される（仮に、最大閾値を”４”とし、新データノードが挿入された結果、ＲＮ０２の子ノード数２０３が奇数である”５”となった場合は、”３”と”２”、あるいは”２”と”３”のように、ほぼ同数となるように更新される）。つまり、ＲＮ０２〜新中継ノードの間隔と、新中継ノード〜ＲＮ０３の間隔とを等しく（あるいは、ほぼ等しく）することで検索性能の低下を防ぎ、一定の水準の性能を維持させるものである。更に、新中継ノードの先頭ノード参照が新たに設定される。図２７では、ＤＮ０４の２つ後ろ（２つ右）に位置するＤＮ０５が新中継ノードの先頭ノードとして設定される。また、このような子ノード数の調整に対応するように、配下データ要素数２０２も適宜更新される。
【００８７】
このように、本実施形態での挿入処理では、中継ノードの持つ子ノード数に制限（最大閾値）を設け、データ挿入時に当該制限値を超えたときは、中継ノードを追加し、各中継ノードの持つ子ノードの数に偏りが生じないように調整することで、検索性能を維持することができる。
【００８８】
次に、本実施形態にかかる積層リスト構造でのデータ削除処理の概要について説明する。データ削除の場合も上記データ挿入の場合と同様、削除対象の位置が先頭ノードであるか否かによって若干処理内容が変わる。まず、先頭ノードの削除の場合を説明する。一例として、図１における先頭から４番目のデータを削除したい場合を例として説明する。
【００８９】
まず、図２８に示すように、削除したいデータのある位置（ＤＮ０４）までインデックスアクセスが行われる。
【００９０】
次に、図２９に示すように、ＤＮ０４と、その次ノードであるＤＮ０５との間で、データフィールドの交換が行われる。つまり、ＤＮ０５が参照していたデータフィールド（以下、旧Ｄａｔａ０５）への参照がＤＮ０４に設定される。また、ＤＮ０４が参照していたデータフィールド（旧Ｄａｔａ０４）への参照がＤＮ０５に設定される。これは、ＤＮ０４の参照元であるＲＮ０２の先頭ノード参照２０４に変更を加えないようにするためである。
【００９１】
次に、図３０に示すように、ＤＮ０５およびＤＮ０５が参照する旧Ｄａｔａ０４が削除される。これにより、先頭から４番目であったデータである旧Ｄａｔａ０４が削除されると同時に、ＲＮ０２からＤＮ０４への参照は維持されたままとなる。ＤＮ０４には、旧Ｄａｔａ０５への参照が設定されているため、結果的に、ＤＮ０４の位置で旧Ｄａｔａ０４が削除されたのと同様の結果となる。
【００９２】
次に、図３１に示すように、ＤＮ０４とＤＮ０６との間の参照が更新される。すなわち、ＤＮ０４の次ノードとしてＤＮ０６が設定される。また、ＤＮ０６の前ノードとしてＤＮ０４が設定される。
【００９３】
次に、図３２に示すように、ＤＮ０４の親ノードであるＲＮ０２の配下データ要素数２０２、子ノード数２０３が更新される。更に、図３３に示すように、ＲＮ０２の親ノードにあたるＲＮ１１と、ＲＮ１１の親ノードにあたるＲＮ２１についても同様に、配下データ要素数２０２、子ノード数２０３が更新される。なお、図３３の例では、中継ノード数に変化がないため、配下データ要素数２０２のみが更新される。
【００９４】
次に、削除対象の位置が先頭ノードではない場合を説明する。一例として、図１における先頭から３番目のデータ（ＤＮ０３の位置のデータ）を削除したい場合を例として説明する。
【００９５】
まず、図３４に示すように、削除したいデータ要素のある位置（ＤＮ０３）までインデックスアクセスが行われる。次に、図３５に示すように、ＤＮ０３および、ＤＮ０３が参照しているデータが削除される。そして、図３６に示すように、ＤＮ０２とＤＮ０４の間の参照が更新される。すなわち、ＤＮ０２の次ノードへがＤＮ０４となるように更新される。また、ＤＮ０４の前ノードとしてＤＮ０２が設定される。
【００９６】
その後、上述したのと同様に、削除したＤＮ０３の親ノードであるＲＮ０１の配下データ要素数２０２、子ノード数２０３が更新される（それぞれ数値が”１”減算されることになる）。更に、ＲＮ０１の親ノードであるＲＮ１１、および、ＲＮ１１の親ノードである。ＲＮ２１についても同様に、配下データ要素数２０２、子ノード数２０３が更新される。このように、先頭ノードではない位置のデータ要素が削除される場合は、単にその位置のデータフィールドおよびデータノードを削除し、関連する親ノードの配下データ要素数２０２、子ノード数２０３を調整するという処理が行われる。
【００９７】
次に、上記のようなデータ削除の結果、中継ノード数が減少する場合について説明する。本実施形態では、データ要素を削除した結果、中継ノードの子ノード数が所定の値（以下、最小閾値と呼ぶ）以下になると、その前ノードまたは次ノードとの間で、上記挿入の場合と同様に子ノード数２０３が同数になるような調整が行われる。あるいは、前ノードまたは次ノードとの統合が行われる。これは、上記挿入の場合と同様、検索性能について、ある程度の水準を維持するために行われるものである。なお、前ノードを対象にするか次ノードを対象にするかは、上記子ノード数が最小閾値以下となった中継ノード（つまり、カレントノード）自身が先頭ノードであるか否かによって決まる。これは、カレントノードが先頭ノードの場合に、当該カレントノードを削除してしまうと、当該カレントノードを参照していた親ノードの先頭ノード参照２０４も変更する必要が発生してしまう。そのため、このような変更にかかる処理を省略するために、以下に述べるような処理を実行する。
【００９８】
なお、上記最小閾値についても上記最大閾値と同様に、本実施形態にかかるデータ操作処理が実行される情報処理装置の処理能力に応じて、予め適切な値が算出され、設定される。
【００９９】
まず、カレントノードが先頭ノードの場合の例を説明する。例えば、図１において、ＤＮ０２のデータ要素を削除した結果、ＤＮ０２の親ノードであり、且つ、先頭ノードであるＲＮ０１の子ノード数２０３が最小閾値以下になったような場合を考える。この場合は、カレントノードであるＲＮ０１と、その次ノードであるＲＮ０２との間で以下に示すような調整処理が実行され、最終的には、先頭ノードであるＲＮ０１が削除されずに残るような処理が実行される。以下、削除せずに残す側のノードを”保存対象ノード”と呼び、他方を”削除対象ノード”と呼ぶ。ここでは、先頭ノードであるカレントノード（ＲＮ０１）が”保存対象ノード”となり、カレントノードの次ノード（ＲＮ０２）が”削除対象ノード”になる。
【０１００】
例えば、上記最小閾値を”２”とし、ＤＮ０２のデータ要素を削除した結果、図３７に示すように、ＲＮ０１の子ノード数が”２”になった場合を例に説明する。この場合、まず、ＲＮ０１（保存対象ノード）と、ＲＮ０２（削除対象ノード）との子ノード数２０３の和を算出する。当該算出した値が、上記最大閾値以下であるか否かで次に実行する処理内容が異なる。例えば、最大閾値を”５”とし、ＲＮ０２の子ノード数が”３”である場合を考えると、当該算出した値は“６”となり、最大閾値より大きくなる。このような場合は、図３８に示すように、ＲＮ０１とＲＮ０２との間で、それぞれの配下になる子ノード数が同数（上記算出した値が奇数のときは、上記同様、ほぼ同数になるように）になるように調整する（図３８では、それぞれ“３”になっている）。
【０１０１】
一方、上記算出した値が最大閾値以下のとき、例えば、最大閾値を”５”とし、ＲＮ０２の子ノード数が”１”である場合は、算出した値は“４”となる。この場合は、図３９に示すように、ＲＮ０２の配下にある子ノードをＲＮ０１に統合するような調整が行われる。すなわち、ＲＮ０１の子ノード数２０３および配下データ要素数２０２にＲＮ０２のそれぞれの値を加算し、その後、ＲＮ０２を削除する。これにより、ＲＮ０２の配下であった子ノードはＲＮ０１配下となる。また、先頭ノードであるＲＮ０１が削除されずに残ることになるため、その親ノードにあたるＲＮ１１の先頭ノード参照２０４には変更の必要が発生しないことになる。
【０１０２】
次に、カレントノードが先頭ノードではない場合の処理を説明する。例えば、図１において、ＤＮ０５のデータ要素を削除した結果、ＲＮ０２の子ノード数２０３が最小閾値以下になったような場合を考える。この場合は、カレントノード（ＲＮ０２）が”削除対象ノード”となり、カレントノードの前ノード（ＲＮ０１）が”保存対象ノード”になる。そして、ＲＮ０２とＲＮ０１との間で、上記と同様の処理が行われる。すなわち、ＲＮ０２とＲＮ０１の子ノード数の和が最大閾値より大きいときは、両ノードの子ノード数が同数またはほぼ同数になるような調整が行われる。一方、最大閾値以下のときは、ＲＮ０２の内容をＲＮ０１に統合する処理が行われ、結果的に、ＲＮ０２が削除されることになる。この場合も、先頭ノードであるＲＮ０１は削除されずに残ることになるため、その親ノードにあたるＲＮ１１の先頭ノード参照２０４には変更の必要が発生しないことになる。
【０１０３】
このように、本実施形態では、複数のノードを管理する役割を有する中継ノードを階層構造とすることで、インデックスアクセスにかかる検索性能を高めている。また、データの追加や削除が実行されたときに、上述したような調整を行うことで中継ノード間の間隔に偏りが生じないようにすることができ、当該検索性能の低下を防ぐことができる。
【０１０４】
以下、本実施形態において実行されるデータ操作処理の詳細を説明する。まず、本実施形態にかかるデータ操作処理を実行する情報処理装置について説明する。図４０は、本発明の実施形態に係る情報処理装置の構成を示したブロック図である。図４０において、情報処理装置は、ＣＰＵ１１とＲＡＭ１２と、入力部１３と表示部１４と外部記憶部１５とで構成される。
【０１０５】
ＣＰＵ１１は、ＲＡＭ１２に読み込まれたプログラムを実行することで、上記のようなデータ操作処理を実現する。入力部１３は、ユーザからの入力を受け付け、その入力内容を示す信号をＣＰＵ１１に出力する。表示部１４は、ＣＰＵ１１で実行された処理の結果（検索結果等）を表示するための装置である。ＲＡＭ１２は、本実施形態にかかる処理を実行する場合に、外部記憶部１５より各種プログラムやデータを読み込むといった一時的にデータやプログラム等を記憶する内部記憶装置を示す。外部記憶部１５は、本実施形態にかかるプログラム等を格納する。例えばハードディスクや光ディスク、メモリーカード等が外部記憶部１５に該当する。
【０１０６】
次に、本実施形態のデータ処理実行時にＲＡＭ１２に格納されるデータについて説明する。図４１は、ＲＡＭ１２のメモリ構成の一例を示す図である。図４１において、ＲＡＭ１２は、プログラム領域１２１、データ領域１２６、および作業領域１３３を含む。プログラム領域１２１は、ＣＰＵ１１によって実行されるデータ処理プログラム１２２を記憶し、このデータ処理プログラム１２２は、インデックスアクセス処理プログラム１２３と、追加挿入処理プログラム１２４と、削除処理プログラム１２５などによって構成される。また、その他、プログラム領域１２１には、入力部１３を介してユーザからの入力操作を受け付けるためのプログラムや、表示部１４への出力を制御するためのプログラム等も含まれる。
【０１０７】
データ領域１２６は、中継ノード領域１２７、データノード領域１２９、データフィールド領域１３１を含む。中継ノード領域１２７は、上記中継ノードが記憶される領域である、データノード領域１２９は、上記データノードが記憶される領域である。また、データフィールド領域１３１は、上記データフィールドが記憶される領域である。なお、図６および図７を用いて上述した各ノードの構成要素と同じものについては、図４１においても同じ参照番号を付している。
【０１０８】
データフィールド１３２は、具体的なデータの実体である。上述のように、当該データフィールド１３２が格納されているＲＡＭ１２上のメモリアドレスが上記データ参照１０２の値として設定されることになる。
【０１０９】
作業領域１３３には、後述の処理で用いられる変数であるインデックス番号１３４、オフセット１３５、親ノード情報１３６等が格納される。インデックス番号１３４は、積層リスト構造においてアクセスしたいデータ要素の位置や、データを挿入あるいは削除したい位置を示す情報である。上述のように、インデックス番号１３４は、先頭を基点とした位置を示している。オフセット１３５は、インデックスアクセスを実行する際に用いられる変数である。親ノード情報１３６は、上述したような親ノードを示すための情報である。具体的には、「一つ上の層において、最後にアクセスされた中継ノード」の格納されているメモリアドレスを示す情報である。当該情報は、後述する処理の過程において、各ノードがアクセスされたときに随時設定される。
【０１１０】
以下、図４２〜図５３を用いて、本実施形態において実行されるデータ処理プログラムの詳細を説明する。
【０１１１】
（インデックスアクセス処理）
まず、上記インデックスアクセスにかかる処理の一例として、インデックス位置のデータを取得するためのデータ取得処理の詳細を説明する。図４２は、データ取得処理の詳細を示すフローチャートである。本処理は、例えば、ユーザが入力部１３を用いて取得したいデータの位置を指定し（先頭からｎ番目、のような指定内容となる）、所定のボタン操作を行ったときに実行される。もちろん、ユーザの操作に限らず、所定のプログラムを実行しているＣＰＵ１１が、当該プログラムに基づいてデータ取得処理を呼び出すことで実行されるようにしてもよい。例えば、"select(n)"のような形式の関数として、引数である(n)にインデックス番号を指定することで呼び出せるよう実装することが考えられる。"select(3)"のように指定すると、積層リスト構造における先頭から３番目のデータを取得することが指示されたことになる（なお、指定したデータの取得だけでなく、指定したデータを更新する処理を実行する際にも利用可能である。例えば、"update(3,“更新内容”)"のような形式の関数で、３番目のデータを更新する指示を行うことが考えられる）。
【０１１２】
図４２において、まず、入力部１３を介したユーザからの入力（あるいは、上述したような引数として指定された値）に基づき、ＣＰＵ１１は、インデックス番号１３４を設定する（ステップＳ１）。
【０１１３】
次に、ＣＰＵ１１は、インデックス番号１３４で示されるデータの位置へアクセスするためのインデックスアクセス処理を実行する（ステップＳ２）。図４３は、上記ステップＳ２で示したインデックスアクセス処理の詳細を示すフローチャートである。図４３において、まず、ＣＰＵ１１は、オフセット１３５に”１”を設定する（ステップＳ２１）。次に、ＣＰＵ１１は、カレントノード、すなわち、処理対象のノードとしてルートノードを設定する（ステップＳ２２）。
【０１１４】
次に、ＣＰＵ１１は、カレントノードから配下データ要素数２０２を取得し、オフセット１３５との和を算出する。そして、インデックス番号１３４が当該算出した値以上であるか否かを判定する（ステップＳ２３）。
【０１１５】
当該判定の結果、インデックス番号１３４が上記算出した値以上のときは（ステップＳ２３でＹＥＳ）、図１２を用いて上述したような、同階層のノードを調べていく処理を行うため、ＣＰＵ１１は、カレントノードに対して次ノードが存在するか否かを判定する（ステップＳ２４）。具体的には、ＣＰＵ１１は、カレントノードの次参照２０５（この処理が実行されるのは、カレントノードが中継ノードのときのみである）に”ＮＵＬＬ”が設定されているか否かで、次ノードの有無を判定する。当該判定の結果、次ノードが存在していれば（ステップＳ２４でＹＥＳ）、ＣＰＵ１１は、カレントノードの配下データ要素数２０２をオフセット１３５に加算する。そして、当該次ノードをカレントノードとして設定し（ステップＳ２５）、上記ステップＳ２３の処理に戻る。
【０１１６】
一方、ステップＳ２４の判定の結果、次ノードが存在していないときは（ステップＳ２４でＮＯ）、目的のデータが存在しないことになるため、ＣＰＵ１１は、検索対象のデータが存在しなかった旨のエラー情報を示すための処理を実行する（ステップＳ２６）。例えば、当該インデックスアクセス処理が関数として呼び出されているようなときは、その戻り値としてエラーを示す値を設定する。
【０１１７】
一方、上記ステップＳ２３の判定の結果、インデックス番号１３４が上記算出した値未満のときは（ステップＳ２３でＮＯ）、ＣＰＵ１１は、（現在の）カレントノードの子ノードを（次の）カレントノードに設定する（ステップＳ２７）。すなわち、先頭ノード参照２０４で示されるノードをカレントノードとして設定する。
【０１１８】
次に、カレントノードが中継ノードであるか否かを判定する（ステップＳ２８）。この判定は、例えば、カレントノードが子ノード数２０３あるいは配下データ要素数２０２という項目を有しているか否かで判定できる。データノードであれば、これらの項目を有していないからである（図６および図７参照）。その他、自身が中継ノードであるかデータノードであるかを識別するための識別子を各ノードに持たせるようにしておき、当該識別子に基づいて判定するようにしてもよい。当該判定の結果、カレントノードが中継ノードのときは（ステップＳ２８でＹＥＳ）、ＣＰＵ１１は、上記ステップＳ２３に戻り、処理を繰り返す（この内容は、上述した図９から図１０、図１１へと遷移する内容に相当する）。
【０１１９】
一方、ステップＳ２８の判定の結果、カレントノードが中継ノードではないときは（ステップＳ２８でＮＯ）、カレントノードはデータノードであるため、図１３、図１４を用いて上述したような、データノード層における処理が実行される。すなわち、ＣＰＵ１１は、”インデックス番号１３４＝オフセット１３５”であるか否かを判定する（ステップＳ２９）。
【０１２０】
当該判定の結果、”インデックス番号１３４＝オフセット１３５”でないときは（ステップＳ２９でＮＯ）、ＣＰＵ１１は、カレントノードに次のノードが存在するか否かを判定する（ステップＳ３０）。具体的には、カレントノードの次参照１０３に”ＮＵＬＬ”が設定されているか否かで、次ノードの有無を判定する。その結果、次ノードが存在しないときは（ステップＳ３０でＮＯ）、目的とするデータが存在しないことになるため、上記ステップＳ２６の処理に進む。
【０１２１】
一方、ステップＳ３０の判定の結果、次ノードが存在するときは（ステップＳ３０でＹＥＳ）、ＣＰＵ１１は、オフセット１３５に”１”を加算する。更に、当該次ノードをカレントノードとして設定する（ステップＳ３１）。その後、上記ステップＳ２９の処理に戻る。つまり、図１３および図１４で上述したように、データノード層においてデータノードを右方向に一つずつ順次調査する処理が行われることになる。
【０１２２】
一方、上記ステップＳ２９の判定の結果、”インデックス番号１３４＝オフセット１３５”であれば（ステップＳ２９でＹＥＳ）、検索目的とするデータが見つかったことになるため、ＣＰＵ１１は、インデックスアクセス処理を終了する。以上で、インデックスアクセス処理の説明を終了する。
【０１２３】
図４２に戻り、インデックスアクセス処理の次に、ＣＰＵ１１は、データが存在しない旨のエラーが発生したか否かを判定する（ステップＳ３）。例えば、上述したように、インデックスアクセス処理が関数として呼び出されているようなときは、当該エラーが発生したときは上記ステップＳ２６において、戻り値としてエラーを示す値が設定される。そのため、当該戻り値の内容を判定することで、エラーが発生したか否かを判定できる。当該判定の結果、データが存在しない旨のエラーが発生していたときは（ステップＳ３でＹＥＳ）、そのままデータ取得処理を終了する。当該エラーが発生していなければ（ステップＳ３でＮＯ）、次に、ＣＰＵ１１は、カレントノードが持つデータを取得する。すなわち、上述のインデックスアクセス処理の結果、カレントノードはいずれかのデータノードとなっているため、ＣＰＵ１１は、当該データノードのデータ参照１０２で示されるデータフィールドの内容を取得する。以上で、データ取得処理の説明は終了する。
【０１２４】
（データ追加処理）
次に、データ追加処理の詳細を説明する。データ追加処理は、上述したように、その具体的処理内容の違いから、末尾追加処理と挿入処理に大別される。ここではまず、末尾追加処理の詳細を説明してから、挿入処理の詳細を説明する。
【０１２５】
（末尾追加処理）
図４４は、末尾追加処理の詳細を示すフローチャートである。本処理は、例えば、ユーザが入力部１３を用いて追加したいデータ内容を入力し、末尾への追加処理を実行するための操作（所定のボタン操作等）を行ったときに実行される。もちろん、ユーザの操作に限らず、所定のプログラムを実行しているＣＰＵ１１が、当該プログラムに基づいて末尾追加処理を呼び出すことで実行されるようにしてもよい（例えば、"ADD()"のような形式の、引数無しの関数として呼び出せるよう実装することが考えられる）。本処理の開始時点で、当該追加したいデータは新たなデータフィールド１３２としてＲＡＭ１２に新規作成されているものとする。
【０１２６】
図４４において、まず、ＣＰＵ１１は、カレントノードとしてルートノードを設定する（ステップＳ４１）。次に、ＣＰＵ１１は、子ノード数が０であるか否かを判定する（ステップＳ４２）。つまり、新規にデータを追加することになるのか否かを判定する。当該判定の結果、子ノード数が０のときは（ステップＳ４２でＹＥＳ）、ＣＰＵ１１は、追加するデータフィールドを参照する新しいデータノード（以下、新データノードと呼ぶ）を生成する（ステップＳ４７）。つまり、新たなデータノードを生成し、データ参照１０２に、新たに追加するデータフィールドへの参照を設定する。続いてＣＰＵ１１は、カレントノードに上記新データノードを登録する（ステップＳ４８）。そして、ＣＰＵ１１は、後述するステップＳ４６の処理に進む。
【０１２７】
一方、ステップＳ４２の判定の結果、子ノード数が０ではない場合、つまり、既に何らかのデータが存在しているときは（ステップＳ４２でＮＯ）、次に、ＣＰＵ１１は、積層リスト構造におけるデータフィールドの並びの末尾の位置に移動するための末尾移動処理を実行する（ステップＳ４３）。図４５は、上記ステップＳ４３で示した末尾移動処理の詳細を示すフローチャートである。本処理は、図１の例で云うと、左上から右下方向に向けて単純にカレントノードを移動させていく処理である。図４５において、まず、ＣＰＵ１１は、カレントノードに次ノードが存在するか否かを判定する（ステップＳ５１）。なお、本処理の開始直後の場合は、カレントノードはルートノードであるため、次ノードは存在しないと判定されることになる。
【０１２８】
当該判定の結果、次ノードが存在しないと判定されたときは（ステップＳ５１でＮＯ）、次に、ＣＰＵ１１は、カレントノードの種類が中継ノードであるか否かを判定する（ステップＳ５２）。その結果、中継ノードであるときは（ステップＳ５２でＹＥＳ）、（現在の）カレントノードの子ノードを（次の）カレントノードとして設定する（ステップＳ５３）。図１でいうと、下方向にカレントノードを移動させていく処理に該当する。そして、上記ステップＳ５１の処理に戻る。
【０１２９】
一方、ステップＳ５１の判定で、次ノードが存在すると判定されたときは（ステップＳ５１でＹＥＳ）、（現在の）カレントノードの次ノード（次参照２０５で示されるノード）を（次の）カレントノードとして設定する（ステップＳ５４）。図１でいうと、右方向にカレントノードを移動させていく処理に該当する。そして、上記ステップＳ５１の処理に戻る。このような処理をループすることで、中継ノードではないノード、すなわちデータノード層にたどり着くまで、カレントノードを移動させるような処理が実行されることになる。
【０１３０】
次に、上記ステップＳ５２の判定の結果、カレントノードの種類が中継ノードではないと判定されたとき（ステップＳ５２でＮＯ）、すなわち、カレントノードがデータノードになったときは（図１の例でいうと、ＤＮ０７の位置までカレントノードが移動したような状態）、次に、ＣＰＵ１１は、当該カレントノードに次ノードが存在するか否かを判定する（ステップＳ５５）。当該判定の結果、次ノードが存在するときは（ステップＳ５５でＹＥＳ）、当該次ノードをカレントノードとして設定する（ステップＳ５６）。そして、ステップＳ５５の処理に戻る。図１の例でいうと、データノード層において右方向へカレントノードを移動させていくような処理が実行される。
【０１３１】
一方、ステップＳ５５の判定の結果、次ノードがないと判定されたときは（ステップＳ５５でＮＯ）、末尾の位置までたどり着いたことになるため（図１の例では、ＤＮ０８の位置）、ＣＰＵ１１は、当該末尾移動処理を終了する。
【０１３２】
図４４に戻り、ステップＳ４３の処理で積層リスト構造におけるデータ要素の末尾までの移動が終われば、次に、ＣＰＵ１１は、新データノードを生成する（ステップＳ４４）。
【０１３３】
次に、ＣＰＵ１１は、上記新データノードを、カレントノード、すなわち末尾のデータノードの次に来るように積層リスト構造に登録する（ステップＳ４５）。具体的には、カレントノードの次参照１０３に新データノードへの参照を設定する。また、新データノードの前参照１０１は、当該カレントノードの参照を設定する。新データノードの次参照１０３には、ＮＵＬＬ値を設定する。図１を例にすると、ＤＮ０８の右に新データノードおよび新たなデータフィールトを追加するような処理となる。
【０１３４】
次に、ＣＰＵ１１は、データ追加時調整処理を実行する（ステップＳ４６）。この処理は、データ要素が追加された際、中継ノードの有する配下データ要素数２０２等を更新したり、上記のように検索性能を一定の水準に維持するために中継ノードの数を適宜調整するための処理である。図４６は、上記ステップＳ４６で示したデータ追加時調整処理の詳細を示すフローチャートである。図４６において、まず、ＣＰＵ１１は、カレントノードについて親ノードがあるか否かを判定する（ステップＳ６１）。当該判定は、カレントノードの有する親ノード情報１３６に基づいて判定する。ここで、ルートノード以外は何らかの親ノードを有するため、この判定内容を換言すると、カレントノードがルートノードであるか否かを判定していることになる。なお、上記のように末尾に新しいデータが追加された結果、この時点でのカレントノードは、末尾から２番目のデータノードを示している。
【０１３５】
当該判定の結果、親ノードがあると判定されたときは（ステップＳ６１でＹＥＳ）、当該親ノードをカレントノードとして設定する（ステップＳ６２）。図１の例でいうと、ＤＮ０８に親ノードが存在するか否かが判定された結果、ＤＮ０８の親ノードであるＲＮ０３が新たにカレントノードとして設定されることになる。
【０１３６】
次に、カレントノードの子ノード数２０３、配下データ要素数２０２を更新する（ステップＳ６３）。ここでは、新しくデータノードおよびデータフィールドが１つ増えているため、更新後の値は、子ノード数２０３、配下データ要素数２０２のそれぞれに”１”が加算された値となる。
【０１３７】
次に、ＣＰＵ１１は、カレントノードの子ノード数２０３が、予め定められている上記最大閾値を超えているか否かを判定する（ステップＳ６４）。当該判定の結果、カレントノードの子ノード数２０３が最大閾値を超えていないときは（ステップＳ６４でＮＯ）、次に、ＣＰＵ１１は、カレントノードに親ノードが存在するか否か（カレントノードがルートノードであるか否か）を判定する。当該判定の結果、親ノードがあるとき（すなわち、カレントノードがルートノードではないとき）は（ステップＳ６５でＹＥＳ）、上記ステップＳ６２に戻り、処理を繰り返す。つまり、図１の例でいうと、右下から左上に向けて（ＲＮ０３→ＲＮ１２→ＲＮ２１という順）中継ノードをたどっていくように処理が進められることになる。
【０１３８】
一方、上記ステップＳ６５の判定で、親ノードがないと判定されたときは（ステップＳ６５でＮＯ）、ルートノードの位置までカレントノードが移動したことになるため、ＣＰＵ１１は、処理を終了する。
【０１３９】
次に、上記ステップＳ６４の判定の結果、カレントノードの子ノード数２０３が最大閾値を超えたときの処理（ステップＳ６４でＹＥＳ）について説明する。このときは、図２５〜図２７を用いて上述したような、中継ノードを追加する処理が実行される。
【０１４０】
まず、ＣＰＵ１１は、新しい中継ノード（以下、新中継ノードと呼ぶ）を生成し、カレントノードの次に来るように積層リスト構造に追加する（ステップＳ６６）。すなわち、カレントノードの次参照２０５を新中継ノードの次参照２０５として設定した後、当該カレントノードの次参照２０５を新中継ノードへの参照に更新する。また、前参照２０１についても、このような関係と対応するようにそれぞれ更新する。
【０１４１】
次に、ＣＰＵ１１は、カレントノードの配下関係にある子ノードのうち、半分を新中継ノードの配下に変更する処理（図２７参照）を実行する（ステップＳ６７）。具体的には、ＣＰＵ１１は、まず、カレントノードの子ノード数２０３の値を２で除算する（子ノード数２０３が奇数の場合、端数は切り捨てる。または、端数は切り上げてもよい）。次に、ＣＰＵ１１は、カレントノードの先頭ノード参照２０４で示されるノードから、上記除算した値だけ先にあるノードのメモリアドレスを取得する。そして、ＣＰＵ１１は、当該メモリアドレスを、新中継ノードの先頭ノード参照２０４として設定する。図２７を例にすると、カレントノードがＲＮ０２であり、先頭ノード参照２０４はＤＮ０４を示している。ＲＮ０２の子ノード数２０３を”２”で除算した値は”２”であるため、ＤＮ０４から２つ右隣のＤＮ０５のメモリアドレスが取得される。そして、ＣＰＵ１１は、ＤＮ０５への参照を新中継ノードの先頭ノード参照２０４に設定する。
【０１４２】
次に、ＣＰＵ１１は、カレントノードと新中継ノードのそれぞれの配下データ要素数２０２、子ノード数２０３を再計算して設定する（ステップＳ６８）。その後、ＣＰＵ１１は、上記ステップＳ６１に戻って処理を繰り返す。
【０１４３】
次に、上記ステップＳ６１の判定の結果、親ノードが存在しないと判定されたときの処理（ステップＳ６１でＮＯ）について説明する。この処理経路は、ルートノードのある層において中継ノードが追加された場合にのみ通る処理経路である。つまり、最上層において中継ノードが２つとなったために、その上層に新たにルートノードを作成する処理が実行される。
【０１４４】
まず、ＣＰＵ１１は、カレントノードを先頭ノードとして参照するような親ノードを生成する（ステップＳ６９）。具体的には、新しい中継ノードを生成し、カレントノードである中継ノードへの参照を新しい中継ノードの先頭ノード参照２０４に設定する。併せて、新しい中継ノードの配下データ要素数２０２や子ノード数２０３も適宜設定する。新しい中継ノードの前参照２０１および次参照２０５にはそれぞれＮＵＬＬ値を設定する。
【０１４５】
次に、ステップＳ６９で新たに生成した親ノードをルートノードとして設定する（ステップＳ７０）。具体的には、上述したような”外部からの参照”（図１の例でいうと、ＲＮ２１の上にある要素）はこの時点ではカレントノードを参照しているため、この内容を、上記新しく生成した親ノードへの参照に更新する。そして、ＣＰＵ１１は、上述したステップＳ６２の処理へと進む。その結果、新しく生成した親ノードがカレントノードとして設定され、最終的に、ステップＳ６５の判定でＮＯの処理経路に進むことで、当該データ追加時調整処理が終了することになる。
【０１４６】
図４６に戻り、データ追加時調整処理が終了すれば、末尾追加処理も終了する。以上で、末尾追加処理の説明を終了する。
【０１４７】
（挿入処理）
次に、上記挿入処理の詳細について説明する。図４７〜図４８は、挿入処理の詳細を示すフローチャートである。上記末尾追加処理と同様に、本処理の開始時点で、挿入したいデータは新たなデータフィールド１３２としてＲＡＭ１２に新規作成されているものとする。また、挿入したい位置を示すインデックス番号についても指定されている状態であるとする（例えば、"insert(n)"という形式の関数として呼び出せるよう実装することが考えられる。そして、引数である(n)にインデックス番号を指定する。例えば、"insert(3)"の場合は、先頭から３番目の位置にデータを挿入することを示す）。
【０１４８】
図４７において、ＣＰＵ１１は、まず、インデックスアクセス処理を実行する（ステップＳ８１）。すなわち、上記インデックス番号で指定されたデータ要素の位置にカレントノードを移動する処理が実行される（図１６参照）。当該処理は、図４３を用いて上述した処理と同様であるため、詳細な説明は省略する。
【０１４９】
次に、ＣＰＵ１１は、挿入するデータフィールドを参照する新データノードを生成する（ステップＳ８２）。つまり、新データノードを生成し、当該新データノードのデータ参照１０２に、新たに挿入するデータフィールドへの参照を設定する。
【０１５０】
次に、ＣＰＵ１１は、カレントノードの種類が先頭ノードであるか否かを判定する（ステップＳ８３）。当該判定の結果、カレントノードが先頭ノードと判定されたときは（ステップＳ８３でＹＥＳ）、図１７を用いて上述したような、新データノードとカレントノードとでデータを交換してデータを挿入する処理が実行される。すなわち、ＣＰＵ１１は、カレントノードのデータ参照１０２が示すデータフィールドへの参照を新データノードのデータ参照１０２に設定する（ステップＳ８４）。
【０１５１】
次に、カレントノードのデータ参照１０２に、今回挿入するデータフィールドへの参照を設定する（ステップＳ８５）。続いて、ＣＰＵ１１は、カレントノードに次ノードが存在するか否かを判定する（ステップＳ８６）。当該判定の結果、次ノードが存在すると判定したときは（ステップＳ８６でＹＥＳ）、ＣＰＵ１１は、新データノードと次ノードとの間の参照関係を更新する処理を実行する。すなわち、ＣＰＵ１１は、次ノードの前参照１０１に新データノードへの参照を設定する（ステップＳ８７）。続いて、ＣＰＵ１１は、新データノードの次参照１０３に、次ノードへの参照を設定する（ステップＳ８８）。そして、後述のステップＳ８９の処理に進む。
【０１５２】
一方、上記ステップＳ８６の判定の結果、次ノードが存在しないと判定したときは（ステップＳ８６でＮＯ）、上記ステップＳ８７およびＳ８８の処理は実行せずに、ステップＳ８９の処理に進む。
【０１５３】
次に、ＣＰＵ１１は、カレントノードと新データノードとの間の参照関係を更新する処理を実行する。まず、ＣＰＵ１１は、カレントノードの次参照１０３に新データノードへの参照を設定する（ステップＳ８９）。続いて、ＣＰＵ１１は、新データノードの前参照１０１にカレントノードへの参照を設定する（ステップＳ９０）。そして、ＣＰＵ１１は、上述したデータ追加時調整処理を実行して、中継ノードの調整を行う（ステップＳ９１）。データ追加時調整処理については、図４６を用いて上述した処理と同様であるため、詳細な説明は省略する。
【０１５４】
次に、上記ステップＳ８３の判定において、カレントノードが先頭ノードでないときの処理（ステップＳ８３でＮＯ）について説明する。この場合は、図２２〜図２４を用いて上述したような、指定された位置に単純に新データを挿入するための処理が実行される。
【０１５５】
まず、ＣＰＵ１１は、新データノードのデータ参照１０２に、今回挿入するデータフィールドへの参照を設定する（ステップＳ９２）。
【０１５６】
次に、ＣＰＵ１１は、新データノードがカレントノードの前に位置するように参照関係を設定する処理を行う。すなわち、ＣＰＵ１１は、前ノードの次参照１０３に新データノードへの参照を設定する（ステップＳ９３）。次に、ＣＰＵ１１は、新データノードの前参照１０１にカレントノードの前ノードへの参照を設定する（ステップＳ９４）。
【０１５７】
続いてＣＰＵ１１は、カレントノードの前参照１０１に新データノードへの参照を設定する（ステップＳ９５）。次に、ＣＰＵ１１は、新データノードの次参照１０３にカレントノードへの参照を設定する（ステップＳ９６）。そして、ＣＰＵ１１は、上記ステップＳ９１の処理に進む。ステップＳ９１の処理が終われば、本実施形態にかかる挿入処理は終了する。
【０１５８】
（削除処理）
次に、削除処理の詳細を説明する。図４９は、削除処理の詳細を示すフローチャートである。本処理は、例えば、ユーザが入力部１３を用いて削除したいデータの位置（すなわち、インデックス番号）を入力し、削除処理を実行するための操作（所定のボタン操作等）を行ったときに実行される。あるいは、所定のプログラムを実行しているＣＰＵ１１が、当該実行しているプログラムに基づいて、インデックス番号を指定して本削除処理を呼び出すことで実行される（例えば、"delete(n)"という形式の関数として呼び出せるよう実装することが考えられる。そして、引数である(n)にインデックス番号を指定する）。
【０１５９】
図４９において、ＣＰＵ１１は、まず、インデックスアクセス処理を実行する（ステップＳ１０１）。すなわち、上記インデックス番号で指定されているデータ要素の位置にカレントノードを移動する処理が実行される（図２８参照）。当該処理は、図４３を用いて説明した処理と同様であるため、詳細な説明は省略する。
【０１６０】
次に、ＣＰＵ１１は、次ノードが存在するか否かを判定する（ステップＳ１０２）。次ノードが存在しないときは（ステップＳ１０２でＮＯ）、ＣＰＵ１１は、カレントノードを削除するための処理を実行する。次ノードが存在しないということは、カレントノード（インデックスアクセス処理の結果、カレントノードはいずれかのデータノードとなっている）が先頭ノードか否かに関わらず、データの末尾に位置していることになる。そのため、末尾のデータであるカレントノードをそのまま削除する処理を行えばよい。この場合は、まず、ＣＰＵ１１は、前ノードの次参照１０３にＮＵＬＬを設定する（ステップＳ１０３）。そして、ＣＰＵ１１は、カレントノードおよびカレントノードが参照しているデータフィールドを削除する（ステップＳ１０４）。その後、後述するデータ削除時調整処理を実行する（ステップＳ１０５）。データ削除時調整処理が終了すれば、本実施形態にかかる削除処理は終了する。
【０１６１】
一方、上記ステップＳ１０２の判定の結果、次ノードが存在すると判定されたときは（ステップＳ１０２でＹＥＳ）、次に、ＣＰＵ１１は、カレントノードの種類が先頭ノードであるか否かを判定する（ステップＳ１０６）。当該判定の結果、カレントノードが先頭ノードと判定されたときは（ステップＳ１０６でＹＥＳ）、図２９〜図３０を用いて上述したような、カレントノードとその次ノードとでデータを交換してから、次ノードのほうを削除する処理が実行される。この場合は、まず、ＣＰＵ１１は、カレントノードの参照するデータと次ノードが参照するデータを交換する処理を実行する（ステップＳ１０７）。具体的には、ＣＰＵ１１は、カレントノードのデータ参照１０２が示すデータフィールドを新データノードのデータ参照１０２として設定し、カレントノードのデータ参照１０２が示すデータフィールドを新データノードのデータ参照１０２として設定する。
【０１６２】
次に、カレントノードの次参照１０３として、次ノードの更に次のデータノード（つまり、カレントノードの２つ後ろのデータノード）への参照を設定する（ステップＳ１０８）。上述した図３０および図３１を例にとると、ＤＮ０４の次参照１０３を、ＤＮ０５からＤＮ０６に変更する処理が実行される。
【０１６３】
次に、ＣＰＵ１１は、カレントノードとして次ノードを設定する（ステップＳ１０９）。そして、ＣＰＵ１１は、当該カレントノードの次ノードの前参照１０１として、当該カレントノードの前ノードへの参照を設定する（ステップＳ１１０）。図３０および図３１を例にとると、カレントノードがＤＮ０４からＤＮ０６に代り、ＤＮ０６の前参照１０１にＤＮ０４への参照を設定する処理が実行される。その後、ＣＰＵ１１は、上記ステップＳ１０４に処理を進める。
【０１６４】
一方、上記ステップＳ１０６の判定の結果、カレントノードが先頭ノードではないと判定されたときは（ステップＳ１０６でＮＯ）、上述の図３５で示したように、カレントノードをそのまま削除する処理が実行される。すなわち、ＣＰＵ１１は、前ノードの次参照１０３に次ノードへの参照を設定する。図３５および図３６の例でいうと、カレントノードがＤＮ０３であり、前ノードはＤＮ０２、次ノードがＤＮ０４である。この状態で、ＤＮ０２の次参照１０３としてＤＮ０４を設定する処理が実行される。その後、ＣＰＵ１１は上記ステップＳ１１０に処理を進める。当該ステップＳ１１０の処理においては、図３６の例でいうと、ＤＮ０４の前参照１０１にＤＮ０２への参照を設定する処理が実行される。その後、上記ステップＳ１０４の処理でカレントノードであるＤＮ０３が削除された後、ステップＳ１０５において以下に説明するようなデータ削除時調整処理が実行されれば、本実施形態にかかる削除処理は終了する。
【０１６５】
次に、上記ステップＳ１０５のデータ削除時調整処理の詳細を説明する。この処理は、上記挿入処理におけると調整処理と同様、データ要素の削除に伴う中継ノードの数の調整（削除された分の反映）や配下データ要素数２０２の更新等の各種調整を行うための処理である。
【０１６６】
図５０は、上記ステップＳ１０５で示したデータ削除時調整処理の詳細を示すフローチャートである。図５０において、まず、ＣＰＵ１１は、現在のカレントノードの親ノードを次のカレントノードとして設定する（ステップＳ１２１）。本処理の開始直後のカレントノードはいずれかのデータノードであるため、この処理が実行されると、中継ノード第１層の中継ノードのいずれかがカレントノードとして設定されることになる。
【０１６７】
次に、ＣＰＵ１１は、カレントノードの子ノード数２０３、配下データ要素数２０２の再計算を実行する（ステップＳ１２２）。カレントノードが中継ノード第１層の中継ノードの場合は、子ノード数２０３、配下データ要素数２０２のそれぞれから”１”が減算された値が算出されることになる。
【０１６８】
次に、ＣＰＵ１１は、現在のカレントノードに親ノードが存在するか否かを判定する（ステップＳ１２３）。つまり、カレントノードがルートノードであるか否かが判定される。
【０１６９】
ステップＳ１２３の判定の結果、親ノードが存在すると判定されたときは（ステップＳ１２３でＹＥＳ）、次に、ＣＰＵ１１は、カレントノードの子ノード数２０３が上記最小閾値以下であるか否かを判定する（ステップＳ１２４）。当該判定の結果、子ノード数２０３が最小閾値以下であるときは（ステップＳ１２４でＹＥＳ）、図３８〜図３９を用いて上述したような、隣接する中継ノードとの間で子ノード数等を同数にする調整、あるいは統合するための処理が実行される。具体的には、まず、ＣＰＵ１１は、カレントノードの種類が先頭ノードであるか否かを判定する（ステップＳ１２５）。
【０１７０】
ステップＳ１２５の判定の結果、カレントノードの種類が先頭ノードのときは（ステップＳ１２５でＹＥＳ）、次に、ＣＰＵ１１は、上述したような”保存対象ノード”としてカレントノードを設定する（ステップＳ１２６）。次に、ＣＰＵ１１は、”削除対象ノード”として現在のカレントノードの次ノードを設定する（ステップＳ１２７）。そして、後述のステップＳ１３０の処理に進む。
【０１７１】
一方、上記ステップＳ１２５の判定の結果、カレントノードが先頭ノードではないときは（ステップＳ１２５でＮＯ）、ＣＰＵ１１は、”保存対象ノード”として前ノードを設定する（ステップＳ１２８）。次に、ＣＰＵ１１は、”削除対象ノード”としてカレントノードを設定する（ステップＳ１２９）。
【０１７２】
次に、ＣＰＵ１１は、保存対象ノードの子ノード数２０３と削除対象ノードの子ノード数２０３との和を算出する。そして、当該算出した値が上記最大閾値以下であるか否かを判定する（ステップＳ１３０）。当該判定の結果、最大閾値より大きいときは（ステップＳ１３０でＮＯ）、ＣＰＵ１１は、保存対象ノードの子ノード数２０３と削除対象の子ノード数２０３が同数（上記算出した値が奇数のときは、ほぼ同数）となるように調整する処理を実行する（ステップＳ１３４）。具体的には、ＣＰＵ１１は、上記ステップＳ１３０で算出した値を”２”で除算する（除算した結果、小数点以下の値については切り捨てる）。次に、保存対象ノードの先頭ノード参照２０４で示されるデータノードから、上記除算して得られた値だけ先にあるノードのメモリアドレスを取得する。そして、ＣＰＵ１１は、当該メモリアドレスを削除対象ノードの先頭ノード参照２０４として設定する。
【０１７３】
次に、ＣＰＵ１１は、保存対象ノード、削除対象ノードそれぞれの子ノード数２０３を更新する（ステップＳ１３５）。すなわち、保存対象ノードの配下の子ノードの数、および、削除対象ノードの配下の子ノードの数を再計算して、それぞれの子ノード数２０３に設定する。
【０１７４】
次に、ＣＰＵ１１は、保存対象ノードおよび削除対象ノードの配下データ要素数２０２をそれぞれ再計算して設定する（ステップＳ１３６）。そして、上記ステップＳ１２１に戻り、処理を繰り返す。
【０１７５】
一方、ステップＳ１３０の判定の結果、保存対象ノードの子ノード数２０３と削除対象ノードの子ノード数２０３との和が最大閾値以下のときは（ステップＳ１３０でＹＥＳ）、ＣＰＵ１１は、図３９で示したように、削除対象ノード配下の子ノードを保存対象ノードの配下になるよう調整する処理、すなわち、保存対象ノードと削除対象ノードを統合するための処理を実行する。まず、ＣＰＵ１１は、削除対象ノードの子ノード数２０３を保存対象ノードの子ノード数２０３に加算する（ステップＳ１３１）。続いて、ＣＰＵ１１は、保存対象ノードの配下となるデータ要素の数を再計算し、保存対象ノードの配下データ要素数２０２として更新する（ステップＳ１３２）。そして、ＣＰＵ１１は、削除対象ノードを削除する（ステップＳ１３３）。このような処理の結果、削除対象ノードの配下であった子ノードは保存対象ノードの配下となり、中継ノードが統合されることになる。
【０１７６】
次に、上記ステップＳ１２３の判定の結果、親ノードが存在しなかったときの処理（ステップＳ１２３でＮＯ）、すなわち、カレントノードがルートノードとなったときの処理について説明する。この場合に行われる処理概要を図５２〜図５３を用いて説明する。ここで行われる処理は、中継ノードが一つだけの層が２つ縦に並んだ場合に一方を削除するための処理である。具体的には、図５２に示すように、ルートノードの下の層が中継ノードが１つだけの層であるときに（つまり、ルートノードの層以外に中継ノードが１つだけの層がある場合）、図５３に示すように、最上層のノードを削除するための処理が実行される。
【０１７７】
上記ステップＳ１２３の判定の結果、親ノードが存在しなかったと判定されたときは、ＣＰＵ１１は、カレントノードの子ノード数２０３が”１”であるか否かを判定する（ステップＳ１３７）。当該判定の結果、カレントノードの子ノード数２０３が”１”のときは（ステップＳ１３７でＹＥＳ）、次に、ＣＰＵ１１は、当該子ノードの種類が中継ノードであるか否かを判定する（ステップＳ１３８）。当該判定の結果、子ノードが中継ノードではないときは（ステップＳ１３８でＮＯ）、ＣＰＵ１１は、削除時調整処理を終了する。つまり、この場合は子ノードはデータノードであるため、図５２のような、”中継ノード”が１つだけの層が”縦に２つ”並んでいる状態ではないと考えられるからである。
【０１７８】
一方、ステップＳ１３８の判定の結果、子ノードが中継ノードであるときは（ステップＳ１３８でＹＥＳ）、図５２に示したように、中継ノードが１つだけの層が縦に２つ並んだ状態である。そのため、ＣＰＵ１１は、上記”外部からの参照”（図５２の円で示されている要素）に、当該子ノードへの参照を設定する（ステップＳ１３９）。次に、ＣＰＵ１１は、カレントノードを削除する（ステップＳ１４０）。その結果、図５３に示したような状態となる。そして、ＣＰＵ１１は、子ノードをカレントノードに設定してから（ステップＳ１４１）、上記ステップＳ１３７の処理に戻る。
【０１７９】
一方、上記ステップＳ１３７の判定の結果、子ノード数２０３が”１”ではないときは（ステップＳ１３７でＮＯ）、ＣＰＵ１１はそのまま削除時調整処理を終了する。この場合も、図５２のような、”中継ノード”が１つだけの層が”縦に２つ”並んでいる状態ではないと考えられるからである。
【０１８０】
以上で、データ削除時調整処理の説明を終了する。
【０１８１】
このように、本実施形態では、中継ノードを階層化してデータを管理することで、インデックスアクセスを行う際の検索性能の変動を少なくすることができる。また、データの追加あるいは削除が行われた際に、上記中継ノード間の間隔に偏りが生じないように調整する処理を行うことで、データの追加、挿入や削除を行っても、検索性能に大きな変動が生じないようすることができ、一定の水準の検索性能を維持することが可能となる。
【０１８２】
なお、上記実施形態では、データノードにデータフィールドへの参照を持たせる構成にしているが、これに限らず、データノードにデータそのものを含める、つまり、データノードとデータフィールドが一体化したような構成にしてもよい。
【産業上の利用可能性】
【０１８３】
本発明にかかるデータ処理プログラムは、検索性能を一定の水準に保つデータ構造を提供することができ、ゲーム装置やパーソナルコンピュータ等の情報処理装置に有用である。
【図面の簡単な説明】
【０１８４】
【図１】本実施形態にかかる積層リスト構造の一例
【図２】本実施形態における各ノードの呼称を説明するための図
【図３】本実施形態の積層リスト構造におけるノード間の親子関係を説明するための図
【図４】本実施形態の積層リスト構造におけるノード間の親子関係を説明するための図
【図５】本実施形態の積層リスト構造におけるノード間の親子関係を説明するための図
【図６】データノードの詳細を示す図
【図７】中継ノードの詳細を示す図
【図８】積層リスト構造における検索処理の概要を説明するための図
【図９】積層リスト構造における検索処理の概要を説明するための図
【図１０】積層リスト構造における検索処理の概要を説明するための図
【図１１】積層リスト構造における検索処理の概要を説明するための図
【図１２】積層リスト構造における検索処理の概要を説明するための図
【図１３】積層リスト構造における検索処理の概要を説明するための図
【図１４】積層リスト構造における検索処理の概要を説明するための図
【図１５】積層リスト構造における追加処理の概要を説明するための図
【図１６】積層リスト構造における追加処理の概要を説明するための図
【図１７】積層リスト構造における追加処理の概要を説明するための図
【図１８】積層リスト構造における追加処理の概要を説明するための図
【図１９】積層リスト構造における追加処理の概要を説明するための図
【図２０】積層リスト構造における追加処理の概要を説明するための図
【図２１】積層リスト構造における追加処理の概要を説明するための図
【図２２】積層リスト構造における追加処理の概要を説明するための図
【図２３】積層リスト構造における追加処理の概要を説明するための図
【図２４】積層リスト構造における追加処理の概要を説明するための図
【図２５】積層リスト構造における追加処理の概要を説明するための図
【図２６】積層リスト構造における追加処理の概要を説明するための図
【図２７】積層リスト構造における追加処理の概要を説明するための図
【図２８】積層リスト構造における削除処理の概要を説明するための図
【図２９】積層リスト構造における削除処理の概要を説明するための図
【図３０】積層リスト構造における削除処理の概要を説明するための図
【図３１】積層リスト構造における削除処理の概要を説明するための図
【図３２】積層リスト構造における削除処理の概要を説明するための図
【図３３】積層リスト構造における削除処理の概要を説明するための図
【図３４】積層リスト構造における削除処理の概要を説明するための図
【図３５】積層リスト構造における削除処理の概要を説明するための図
【図３６】積層リスト構造における削除処理の概要を説明するための図
【図３７】積層リスト構造における削除処理の概要を説明するための図
【図３８】積層リスト構造における削除処理の概要を説明するための図
【図３９】積層リスト構造における削除処理の概要を説明するための図
【図４０】本発明の実施形態に係る情報処理装置の構成を示したブロック図
【図４１】ＲＡＭ１２のメモリ構成の一例を示す図
【図４２】データ取得処理の詳細を示すフローチャート
【図４３】図１４のステップＳ２で示したインデックスアクセス処理の詳細を示すフローチャート
【図４４】末尾追加処理の詳細を示すフローチャート
【図４５】図４５のステップＳ４５で示したデータ追加時調整処理の詳細を示すフローチャート
【図４６】図４５のステップＳ４５で示したデータ追加時調整処理の詳細を示すフローチャート
【図４７】挿入処理の詳細を示すフローチャート
【図４８】挿入処理の詳細を示すフローチャート
【図４９】削除処理の詳細を示すフローチャート
【図５０】図４９のステップＳ１０５で示したデータ削除時調整処理の詳細を示すフローチャート
【図５１】図４９のステップＳ１０５で示したデータ削除時調整処理の詳細を示すフローチャート
【図５２】図４９のステップＳ１２３でＮＯの判定のときの処理を説明するための図
【図５３】図４９のステップＳ１２３でＮＯの判定のときの処理を説明するための図
【図５４】従来のスキップリスト
【図５５】従来のスキップリスト
【符号の説明】
【０１８５】
１１    ＣＰＵ
１２    ＲＡＭ
１３    入力部
１４    表示部
１５    外部記憶部
【図１】
0005344543.tif 000002
【図２】
0005344543.tif 000003
【図３】
0005344543.tif 000004
【図４】
0005344543.tif 000005
【図５】
0005344543.tif 000006
【図６】
0005344543.tif 000007
【図７】
0005344543.tif 000008
【図８】
0005344543.tif 000009
【図９】
0005344543.tif 000010
【図１０】
0005344543.tif 000011
【図１１】
0005344543.tif 000012
【図１２】
0005344543.tif 000013
【図１３】
0005344543.tif 000014
【図１４】
0005344543.tif 000015
【図１５】
0005344543.tif 000016
【図１６】
0005344543.tif 000017
【図１７】
0005344543.tif 000018
【図１８】
0005344543.tif 000019
【図１９】
0005344543.tif 000020
【図２０】
0005344543.tif 000021
【図２１】
0005344543.tif 000022
【図２２】
0005344543.tif 000023
【図２３】
0005344543.tif 000024
【図２４】
0005344543.tif 000025
【図２５】
0005344543.tif 000026
【図２６】
0005344543.tif 000027
【図２７】
0005344543.tif 000028
【図２８】
0005344543.tif 000029
【図２９】
0005344543.tif 000030
【図３０】
0005344543.tif 000031
【図３１】
0005344543.tif 000032
【図３２】
0005344543.tif 000033
【図３３】
0005344543.tif 000034
【図３４】
0005344543.tif 000035
【図３５】
0005344543.tif 000036
【図３６】
0005344543.tif 000037
【図３７】
0005344543.tif 000038
【図３８】
0005344543.tif 000039
【図３９】
0005344543.tif 000040
【図４０】
0005344543.tif 000041
【図４１】
0005344543.tif 000042
【図４２】
0005344543.tif 000043
【図４３】
0005344543.tif 000044
【図４４】
0005344543.tif 000045
【図４５】
0005344543.tif 000046
【図４６】
0005344543.tif 000047
【図４７】
0005344543.tif 000048
【図４８】
0005344543.tif 000049
【図４９】
0005344543.tif 000050
【図５０】
0005344543.tif 000051
【図５１】
0005344543.tif 000052
【図５２】
0005344543.tif 000053
【図５３】
0005344543.tif 000054
【図５４】
0005344543.tif 000055
【図５５】
0005344543.tif 000056