(57)【特許請求の範囲】
【請求項１】
それぞれ０より大きな長さを有する区間を一列に並べた区間列を管理するために、
木構造を形成し、該木構造に前記各区間を割り当て、記憶媒体上に前記木構造を記憶する木構造生成手段を備え、

前記区間列の各区間の終点は数値であり、
前記区間（Ａ）の前記終点は、前記区間列中の並び順における先頭の区間から該区間（Ａ）までの各区間の長さの合計値であり、

前記木構造は、各ノードにカウンタ列を有し、
前記カウンタ列は、該カウンタ列を含むノードの子ノードあるいは子ノードへのポインタを一列に並べたそれぞれの間に、前記各区間の終点を決定するためのカウンタを有し、
前記カウンタは、前記各区間と対応付けられ、

前記対応は、前記カウンタ（Ｂ）及び該カウンタ（Ｂ）を含む前記カウンタ列（Ｃ）に関し、
カウンタ列（Ｃ）中の並び順においてカウンタ（Ｂ）の一方の側に位置するカウンタ、及び、同じく一方の側に位置する子ノードを根とする部分木及びポインタに指示された子ノードを根とする部分木の各ノードのカウンタに対応付けられた前記各区間の終点が、カウンタ（Ｂ）に対応付けられた前記区間の終点以下であり、かつ、
カウンタ列（Ｃ）中の並び順においてカウンタ（Ｂ）の他方の側に位置するカウンタ、及び、同じく他方の側に位置する子ノードを根とする部分木及びポインタに指示された子ノードを根とする部分木の各ノードのカウンタに対応付けられた前記各区間の終点が、カウンタ（Ｂ）に対応付けられた前記区間の終点以上であり、

前記カウンタには、当該カウンタを含むノードの親ノードあるいは先祖ノードの予め定められた条件を満たすカウンタが存在する場合には、当該カウンタに対応付けられた区間の終点から、上記条件を満たすカウンタに対応付けられた区間の終点を引いた値を設定し、
上記条件を満たすカウンタが存在しない場合には、当該カウンタに対応付けられた区間の終点を設定し、

前記条件は、前記親ノードあるいは先祖ノードの前記カウンタ列における、前記当該カウンタを含むノードあるいはその親ノードあるいはその先祖ノードもしくはそれらのノードへのポインタと、カウンタとの位置関係によって指定されるものであることを特徴とする記憶装置。
【請求項２】
それぞれ０より大きな長さを有する区間を一列に並べた区間列を管理するために、
前記各区間を割り当てて記憶媒体上に形成された木構造に対して、

前記区間列の各区間の終点は数値であり、
前記区間（Ａ）の前記終点は、前記区間列中の並び順における先頭の区間から該区間（Ａ）までの各区間の長さの合計値であり、

前記木構造は、各ノードにカウンタ列を有し、
前記カウンタ列は、該カウンタ列を含むノードの子ノードあるいは子ノードへのポインタを一列に並べたそれぞれの間に、前記各区間の終点を決定するためのカウンタを有し、
前記カウンタは、前記各区間と対応付けられ、

前記対応は、前記カウンタ（Ｂ）及び該カウンタ（Ｂ）を含む前記カウンタ列（Ｃ）に関し、
カウンタ列（Ｃ）中の並び順においてカウンタ（Ｂ）の一方の側に位置するカウンタ、及び、同じく一方の側に位置する子ノードを根とする部分木及びポインタに指示された子ノードを根とする部分木の各ノードのカウンタに対応付けられた前記各区間の終点が、カウンタ（Ｂ）に対応付けられた前記区間の終点以下であり、かつ、
カウンタ列（Ｃ）中の並び順においてカウンタ（Ｂ）の他方の側に位置するカウンタ、及び、同じく他方の側に位置する子ノードを根とする部分木及びポインタに指示された子ノードを根とする部分木の各ノードのカウンタに対応付けられた前記各区間の終点が、カウンタ（Ｂ）に対応付けられた前記区間の終点以上であり、

前記カウンタには、当該カウンタを含むノードの親ノードあるいは先祖ノードの予め定められた条件を満たすカウンタが存在する場合には、当該カウンタに対応付けられた区間の終点から、上記条件を満たすカウンタに対応付けられた区間の終点を引いた値を設定し、
上記条件を満たすカウンタが存在しない場合には、当該カウンタに対応付けられた区間の終点を設定し、

前記条件は、前記親ノードあるいは先祖ノードの前記カウンタ列における、前記当該カウンタを含むノードあるいはその親ノードあるいはその先祖ノードもしくはそれらのノードへのポインタと、カウンタとの位置関係によって指定されるものであることを特徴とし、

前記各区間から、指定数値以上で最小の終点を有する区間を探索するために、
前記指定数値を指定して前記木構造を探索する探索手段を備え、

前記探索手段は、探索中に探索ノードと探索数値を記憶し、かつ、
探索開始時に探索数値を０に設定し、その後、
根ノードから葉ノードに向かって順次探索ノードを移動させる探索ステップを実行し、
上記探索ステップにおいて、探索数値に探索ノードのカウンタの値を加えた数値と指定数値とを比較して、指定数値以上でより小さな終点を有する区間に対応するカウンタを含む可能性がある子ノードを決定し、探索ノードを上記子ノードに移動する際に、探索数値に、当該子ノードのカウンタに関し前記条件を満たすカウンタが存在する場合に限りそのカウンタの値を加算することを特徴とする記憶装置。
【請求項３】
それぞれ０より大きな長さを有する区間を一列に並べた区間列を管理するために、
前記各区間を割り当てて記憶媒体上に形成された木構造に対して、

前記区間列の各区間の終点は数値であり、
前記区間（Ａ）の前記終点は、前記区間列中の並び順における先頭の区間から該区間（Ａ）までの各区間の長さの合計値であり、

前記木構造は、各ノードにカウンタ列を有し、
前記カウンタ列は、該カウンタ列を含むノードの子ノードあるいは子ノードへのポインタを一列に並べたそれぞれの間に、前記各区間の終点を決定するためのカウンタを有し、
前記カウンタは、前記各区間と対応付けられ、

前記対応は、前記カウンタ（Ｂ）及び該カウンタ（Ｂ）を含む前記カウンタ列（Ｃ）に関し、
カウンタ列（Ｃ）中の並び順においてカウンタ（Ｂ）の一方の側に位置するカウンタ、及び、同じく一方の側に位置する子ノードを根とする部分木及びポインタに指示された子ノードを根とする部分木の各ノードのカウンタに対応付けられた前記各区間の終点が、カウンタ（Ｂ）に対応付けられた前記区間の終点以下であり、かつ、
カウンタ列（Ｃ）中の並び順においてカウンタ（Ｂ）の他方の側に位置するカウンタ、及び、同じく他方の側に位置する子ノードを根とする部分木及びポインタに指示された子ノードを根とする部分木の各ノードのカウンタに対応付けられた前記各区間の終点が、カウンタ（Ｂ）に対応付けられた前記区間の終点以上であり、

前記カウンタには、当該カウンタを含むノードの親ノードあるいは先祖ノードの予め定められた条件を満たすカウンタが存在する場合には、当該カウンタに対応付けられた区間の終点から、上記条件を満たすカウンタに対応付けられた区間の終点を引いた値を設定し、
上記条件を満たすカウンタが存在しない場合には、当該カウンタに対応付けられた区間の終点を設定し、

前記条件は、前記親ノードあるいは先祖ノードの前記カウンタ列における、前記当該カウンタを含むノードあるいはその親ノードあるいはその先祖ノードもしくはそれらのノードへのポインタと、カウンタとの位置関係によって指定されるものであることを特徴とし、

前記区間の１つを指定して、その終点を得るために、
当該区間に対応する指定カウンタを指定して当該区間の終点を決定する決定手段を有し、

前記決定手段は、前記指定カウンタを含むノードから根ノードに至るパス上の各ノードに関して、
上記各ノードのカウンタへの前記値の設定において使用された、当該カウンタを含むノードの親ノードあるいは先祖ノードの予め定められた条件を満たすカウンタの値だけを合計した数値を、前記指定区間の終点とするステップを実行することを特徴とする記憶装置。
【請求項４】
それぞれ０より大きな長さを有する区間を一列に並べた区間列を管理するために、
前記各区間を割り当てて記憶媒体上に形成された木構造に対して、

前記区間列の各区間の終点は数値であり、
前記区間（Ａ）の前記終点は、前記区間列中の並び順における先頭の区間から該区間（Ａ）までの各区間の長さの合計値であり、

前記木構造は、各ノードにカウンタ列を有し、
前記カウンタ列は、該カウンタ列を含むノードの子ノードあるいは子ノードへのポインタを一列に並べたそれぞれの間に、前記各区間の終点を決定するためのカウンタを有し、
前記カウンタは、前記各区間と対応付けられ、

前記対応は、前記カウンタ（Ｂ）及び該カウンタ（Ｂ）を含む前記カウンタ列（Ｃ）に関し、
カウンタ列（Ｃ）中の並び順においてカウンタ（Ｂ）の一方の側に位置するカウンタ、及び、同じく一方の側に位置する子ノードを根とする部分木及びポインタに指示された子ノードを根とする部分木の各ノードのカウンタに対応付けられた前記各区間の終点が、カウンタ（Ｂ）に対応付けられた前記区間の終点以下であり、かつ、
カウンタ列（Ｃ）中の並び順においてカウンタ（Ｂ）の他方の側に位置するカウンタ、及び、同じく他方の側に位置する子ノードを根とする部分木及びポインタに指示された子ノードを根とする部分木の各ノードのカウンタに対応付けられた前記各区間の終点が、カウンタ（Ｂ）に対応付けられた前記区間の終点以上であり、

前記カウンタには、当該カウンタを含むノードの親ノードあるいは先祖ノードの予め定められた条件を満たすカウンタが存在する場合には、当該カウンタに対応付けられた区間の終点から、上記条件を満たすカウンタに対応付けられた区間の終点を引いた値を設定し、
上記条件を満たすカウンタが存在しない場合には、当該カウンタに対応付けられた区間の終点を設定し、

前記条件は、前記親ノードあるいは先祖ノードの前記カウンタ列における、前記当該カウンタを含むノードあるいはその親ノードあるいはその先祖ノードもしくはそれらのノードへのポインタと、カウンタとの位置関係によって指定されるものであることを特徴とし、

前記区間の１つを指定して、その長さを指定量だけ変更する操作に対応して、
当該区間に対応する指定カウンタ及び前記指定量を指定して、選択的に前記カウンタの値を修正する変更手段を有し、

前記変更手段は、前記指定カウンタを含むノードの子ノードのカウンタ及び前記指定カウンタを含むノードから根ノードに至るパス上の各ノードのカウンタのうち、
前記区間列中の並び順において、当該カウンタに対応する区間と、上記当該カウンタへの値の設定において使用された、当該カウンタを含むノードの親ノードあるいは先祖ノードの予め定められた条件を満たすカウンタに対応する区間との間に、前記指定カウンタに対応する区間が存在するものを、前記指定量だけ変更するステップを実行することを特徴とする記憶装置。
【請求項５】
それぞれ０より大きな長さを有する区間を一列に並べた区間列を管理するために、
前記各区間を割り当てて記憶媒体上に形成された木構造に対して、

前記区間列の各区間の終点は数値であり、
前記区間（Ａ）の前記終点は、前記区間列中の並び順における先頭の区間から該区間（Ａ）までの各区間の長さの合計値であり、

前記木構造は、各ノードにカウンタ列を有し、
前記カウンタ列は、該カウンタ列を含むノードの子ノードあるいは子ノードへのポインタを一列に並べたそれぞれの間に、前記各区間の終点を決定するためのカウンタを有し、
前記カウンタは、前記各区間と対応付けられ、

前記対応は、前記カウンタ（Ｂ）及び該カウンタ（Ｂ）を含む前記カウンタ列（Ｃ）に関し、
カウンタ列（Ｃ）中の並び順においてカウンタ（Ｂ）の一方の側に位置するカウンタ、及び、同じく一方の側に位置する子ノードを根とする部分木及びポインタに指示された子ノードを根とする部分木の各ノードのカウンタに対応付けられた前記各区間の終点が、カウンタ（Ｂ）に対応付けられた前記区間の終点以下であり、かつ、
カウンタ列（Ｃ）中の並び順においてカウンタ（Ｂ）の他方の側に位置するカウンタ、及び、同じく他方の側に位置する子ノードを根とする部分木及びポインタに指示された子ノードを根とする部分木の各ノードのカウンタに対応付けられた前記各区間の終点が、カウンタ（Ｂ）に対応付けられた前記区間の終点以上であり、

前記カウンタには、当該カウンタを含むノードの親ノードあるいは先祖ノードの予め定められた条件を満たすカウンタが存在する場合には、当該カウンタに対応付けられた区間の終点から、上記条件を満たすカウンタに対応付けられた区間の終点を引いた値を設定し、
上記条件を満たすカウンタが存在しない場合には、当該カウンタに対応付けられた区間の終点を設定し、

前記条件は、前記親ノードあるいは先祖ノードの前記カウンタ列における、前記当該カウンタを含むノードあるいはその親ノードあるいはその先祖ノードもしくはそれらのノードへのポインタと、カウンタとの位置関係によって指定されるものであることを特徴とし、

前記区間列において、前記区間の１つ（Ｄ）の、前記区間列中の並び順において直前または直後に、新たな追加区間を挿入追加する変更に応じて、
上記区間（Ｄ）に対応する指定カウンタと上記直前または直後の別、及び上記追加区間の長さを指定して、前記木構造を修正する追加手段を有し、

前記追加手段は、前記指定カウンタを含むノードの子ノードのカウンタ及び前記指定カウンタを含むノードから根ノードに至るパス上の各ノードのカウンタのうち、
前記区間列中の並び順において、当該カウンタに対応する区間と、当該カウンタへの前記値の設定において使用された、当該カウンタを含むノードの親ノードあるいは先祖ノードの予め定められた条件を満たすカウンタに対応する区間との間に、前記追加区間が存在するものを、前記追加区間の長さだけ変更するステップを実行することを特徴とする記憶装置。
【請求項６】
それぞれ０より大きな長さを有する区間を一列に並べた区間列を管理するために、
前記各区間を割り当てて記憶媒体上に形成された木構造に対して、

前記区間列の各区間の終点は数値であり、
前記区間（Ａ）の前記終点は、前記区間列中の並び順における先頭の区間から該区間（Ａ）までの各区間の長さの合計値であり、

前記木構造は、各ノードにカウンタ列を有し、
前記カウンタ列は、該カウンタ列を含むノードの子ノードあるいは子ノードへのポインタを一列に並べたそれぞれの間に、前記各区間の終点を決定するためのカウンタを有し、
前記カウンタは、前記各区間と対応付けられ、

前記対応は、前記カウンタ（Ｂ）及び該カウンタ（Ｂ）を含む前記カウンタ列（Ｃ）に関し、
カウンタ列（Ｃ）中の並び順においてカウンタ（Ｂ）の一方の側に位置するカウンタ、及び、同じく一方の側に位置する子ノードを根とする部分木及びポインタに指示された子ノードを根とする部分木の各ノードのカウンタに対応付けられた前記各区間の終点が、カウンタ（Ｂ）に対応付けられた前記区間の終点以下であり、かつ、
カウンタ列（Ｃ）中の並び順においてカウンタ（Ｂ）の他方の側に位置するカウンタ、及び、同じく他方の側に位置する子ノードを根とする部分木及びポインタに指示された子ノードを根とする部分木の各ノードのカウンタに対応付けられた前記各区間の終点が、カウンタ（Ｂ）に対応付けられた前記区間の終点以上であり、

前記カウンタには、当該カウンタを含むノードの親ノードあるいは先祖ノードの予め定められた条件を満たすカウンタが存在する場合には、当該カウンタに対応付けられた区間の終点から、上記条件を満たすカウンタに対応付けられた区間の終点を引いた値を設定し、
上記条件を満たすカウンタが存在しない場合には、当該カウンタに対応付けられた区間の終点を設定し、

前記条件は、前記親ノードあるいは先祖ノードの前記カウンタ列における、前記当該カウンタを含むノードあるいはその親ノードあるいはその先祖ノードもしくはそれらのノードへのポインタと、カウンタとの位置関係によって指定されるものであることを特徴とし、

前記区間列において、前記区間の１つ（Ｄ）を、前記区間列から削除する変更に応じて、
上記区間（Ｄ）に対応する指定カウンタを指定して、前記木構造を修正する削除手段を有し、

前記削除手段は、前記指定カウンタを含むノードの子ノードのカウンタ及び前記指定カウンタを含むノードから根ノードに至るパス上の各ノードのカウンタのうち、
前記区間列中の並び順において、当該カウンタに対応する区間と、当該カウンタへの前記値の設定において使用された、当該カウンタを含むノードの親ノードあるいは先祖ノードの予め定められた条件を満たすカウンタに対応する区間との間に、前記指定カウンタに対応する区間が存在するものを、前記指定カウンタに対応する区間の長さだけ変更するステップを実行することを特徴とする記憶装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般にデータ構造の分野に関し、より具体的には、木構造の各ノードに配置されたカウンタに、単調非減少あるいは単調非増加な数列データの各項を対応付け、そのカウンタに対応付けられた項と、他の項との差分を記憶する、記憶装置に関する。また、このような記憶装置を、計算機及び計算機の主記憶等のランダムアクセス記憶媒体を用いて構成し、指定に応じて前記データ構造から前記データの必要な部分、具体的には指定した数値以上で最小の項、を決定するデータ検索技術、前記データの変更に応じて記憶媒体上の前記データの記憶状態を変更し、前記データ検索技術の適用を維持するデータ更新技術を含む、データ管理技術に関する。
【背景技術】
【０００２】
計算機を使用したデータ処理においては、次の（１）〜（５）の特徴（操作）を有する、単調非減少な数列データ、あるいはその各項にさらなるデータを対応付けたデータを、記憶媒体に記憶し、検索・更新のアクセス操作を行なう必要が生じる。なお、同一項が含まれる場合にも識別できるように、また、他のデータとの対応付けが容易なように、記憶媒体上では、各項は、その項に対応付けられた、あるいは、その項として機能する記憶場所（番地）によって同定される。
（１）指定数値以上で最小の項の記憶場所を決定することができる。
（２）指定した記憶場所の項の値を決定することができる。
（３）数列中の１つの項を増減させたとき、以降の各項を、その項と同じだけ増減させる。
（４）数列中に１つの項を追加したとき、以降の各項に、その項とその項の直前の項との差（直前の項がない場合はその項の値）を加える。
（５）数列中の１つの項を削除したとき、以降の各項から、その項とその項の直前の項との差（直前の項がない場合はその項の値）を減じる。
本発明は、このような特徴を持つ単調非減少数列データを記憶・管理することを目的としている。なお、単調非増加な数列データについても、同様に扱う必要が生じるが、項（数値）の符号（＋−）を反転する等して、単調非減少な数列データを扱うのと同様の方法・技術が適用できるので、以下においては、説明を簡便にするために、単調非減少な数列データを扱う場合に限って説明する。
【０００３】
このような数列として扱うことができる典型的なデータは、順位（順序値）の列または連続する複数の順位からなる区間の列を含むデータである。順位の列または連続する１つ以上の順位からなる区間の列（以下「区間列」という）を含むデータ（以下「区間列データ」という）とは、同種のものを複数結合した構成のデータセットである。このようなデータセットは広く使われており、文字コードの列であるテキストデータ、同一構成のレコードの列である順編成ファイル、行と列で構成される表形式データ、頁や行、列、あるいは章や節から構成される文書データ等はその一例である。なお、１つの順位は、その順位のみを含む長さ１の区間として扱うことができるので、以下、区間列について説明するが、連続する順位からなる順位列に関しても全く同じ説明が可能である。区間列もまた、順位の変更操作（増減・追加・削除）によって、操作対象順位（位置）以降の順位が影響を受けるような、例えば各区間の末尾の順位のみからなる順位列、すなわち上記性質を有する数列として、扱うことができる。
【０００４】
区間列データに対しては、順位を指定して、その順位（位置）を含む区間に対応付けられたデータ、及び／またはその順位を含む区間を決定するというアクセス方法が一般的である。また、単調に増加する順位（区間）の順序と、区間に対応付けられたキーとなるデータの順序を一致させることによって、キーの整列状態を実現し、これを利用して効率的なキー（データ）探索を行うことができる。このようなデータにおいては、区間列との対応付けによって実現されるデータ間の順序関係自体が、区間列データが表す主要な情報なので、各区間への効率よいアクセス手段が必要とされる。さらには、デジタル回路端子の信号値の時系列やＦＡＸデータのように、同一コード（データ）が連続するデータ列においては、同一（１つ）のデータに対応付けられた区間が区間列中でどのような位置を占めるか、すなわち各区間の両端の順位及び長さが、そのデータセットが表す主要な情報である場合も存在する。これらの場合には、特定の１つの順位にどのようなデータが対応付けられているかということだけでなく、各区間の両端の順位や長さが、重要な情報として頻繁に読み取られたり変更されたりする。区間列データがこのように広く利用されるのには、区間列に含まれる順位の列が、全体として１つの連続する整数列（例えば１から順位の数までの）であるという性質があるからで、変更の際には、その性質を維持する必要がある。例えば、区間の削除により、その区間に含まれていた順位が区間列から失われると、後続の全ての区間の順位を削除区間の長さだけ減じて、順位の連続性が維持されるようにしなければならない。
【０００５】
このような区間列へのアクセスを効率化するには、それを実現するデータ構造が、次のような操作を効率的に提供する必要がある。
（１）指定順位を含む区間の探索
（２）指定区間の先頭（左端）順位／末尾（右端）順位の決定、及び区間長の決定
（３）指定区間の区間長の変更（それに伴う、後続区間の順位の変更を含む）
（４）指定区間の直前／直後への新たな区間の追加（それに伴う、後続区間の順位の変更を含む）
（５）指定区間の削除（それに伴う、後続区間の順位の変更を含む）
これらはそれぞれ、上記単調非減少数列データへの（１）〜（５）の操作をそれぞれ用いて、容易に構成できる。すなわち、上述のように区間列を、各区間の末尾の順位を項とする単調非減少数列データとすれば、各区間はそれぞれ、上記の項の記憶場所に対応付けられる。区間列に対する操作（１）、（３）、（４）及び（５）は、単調非減少数列に対する操作（１）、（３）、（４）及び（５）によってそれぞれ実現される。区間列に対する操作（２）のうち、右端の順位の決定は、単調非減少数列に対する操作（２）をそのまま、指定区間に対応する項の記憶場所に適用することによって実現される。一方、左端の順位の決定は、指定区間に対応する項の直前の項の記憶場所に同じく操作（２）を適用して、指定区間の直前の区間の右端の順位を求め、これに、隣り合う区間の相続く右端と左端の差（通常の順位区間の場合は１）を加えればよい。さらに、区間長は、上述のようにして求めた、指定区間の右端の順位から、指定区間の直前の区間の右端の順位を引いた値として計算できる。したがって、上記単調非減少数列に対する（１）〜（５）の操作に、直前の項の記憶場所を決定する操作が加われば、上記単調非減少数列を扱うデータ構造を、区間列を扱うデータ構造として用いることができる。
【０００６】
区間列データを記憶するのに、計算機の主記憶等の記憶媒体に固定的に割り付けられた番地を、直接順位に対応付けるような方法をとれば、上記の更新操作を効率的に行うことができず、実用に耐えない。それゆえ、記憶媒体の特性やデータの利用形態に応じたデータ構造を工夫して、区間列データを記憶する技術が、従来から必要とされてきた。区間列を扱う従来の技術として、特登２７６８９２１（請求項１８〜３４及び４５〜５０、第６実施形態）が知られている。この技術（以下「従来例１」という）は、区間列データを二分木として記憶媒体に記憶し、上記（１）〜（５）の機能を提供することができた。また、同様の方法を二分木以外のデータ構造にも拡張して適用した技術として、特開２００２−２２９８２５がある。この技術（以下「従来例２」という）によれば、二分木以外の、例えばＢ木のように、１つの親ノードが多数の子ノードへのポインタを含むようなデータ構造を使用しても、上記（１）〜（５）の機能を提供することが可能であることが知られる。
【特許文献１】特登２７６８９２１
【特許文献２】特開２００２−２２９８２５
【発明の開示】
【発明が解決しようとする課題】
【０００７】
しかしながら、従来例１は、区間列の記憶媒体への記憶形態が二分木に限られているため、次のような問題点があった。上述のように、区間の順序と、区間に対応付けられたデータ（キー）との順序が（昇順または降順で）一致している場合は、区間を探索する木構造とキーを探索する木構造を兼用できる。順序（順位）付けられたデータ（キー）を探索するための木構造は、二分（探索）木以外にも多数知られている。これも上述のように、記憶媒体の種類や、利用形態によっては、探索木として二分木以外の構造を採用したほうが適切な場合がある。従来例１では区間を扱う探索木が二分木に限られているため、キーの探索に二分木と異なるデータ構造を採用した場合には、両者を１つの木構造で兼用することができない。また、従来例１の第６実施形態（図５１等）にみられるようなポインタを多用した二分木の構成が、更新操作を短時間で扱えるのは、計算機の主記憶のような、完全なランダムアクセス性能が保証された記憶媒体に限られる。しかも、１ノードにつき２個乃至３個の番地を記憶せねばならず、多くの記憶媒体を必要とする。従来例１にはこのような制約があるので、記憶媒体の種類によっては所期の性能・効率が得られない場合がある。
【０００８】
従来例２においては、キーを整列させるための二分（探索）木以外のデータ構造に関して、従来例１と同様の構成、すなわち、キーの順序付き集合（順位の集合）のサブセットに対応する各データ構造（二分木においては各ノード（を根とする部分木））に、そのサブセットに含まれるエントリの数を表すカウンタを対応付けるという方法が開示されている。しかしながら、Ｂ木のように、１つのノードに、前記サブセットに対応する複数のデータ構造がキー（順位）順に線形に配置されている場合、指定した順位のエントリがどのサブセットに属するかを決定するのに、複数のカウンタの値を積算した上で指定順位と比較判定せねばならない。すなわち、ノードの内部では、従来例１において、従来の技術の第３の手法（図８５）について指摘されていると同様に、二分探索法を適用することができず、線形探索をせざるをえない。このため、同一のデータ構造を使用するとはいえ、ノード内部で二分探索法が適用できるソートキーの探索の場合と、同等の探索性能を得ることができない。この問題は、指定したエントリ（区間）から、その（端の）順位を計算する場合にも生じる。
【０００９】
本発明は、上記のような従来技術の問題点を解決するために提案されたもので、その目的は、二分木に限定されない、各種の探索木を用いて実施できる、記憶装置を提供することである。また、本発明の他の目的は、二分木以外のデータ構造で実施された場合にも、そのデータ構造を使用してキー探索を行うのと同等の効率で、順位及び区間、すなわち上記単調非減少数列の項を、上記（１）及び（２）の操作で探索できる記憶装置を提供することである。また、本発明の他の目的は、区間列、すなわち上記単調非減少数列を、その特徴を維持するよう上記（３）、（４）及び（５）の操作で更新できる記憶装置を提供することである。
【課題を解決するための手段】
【００１０】
上記の目的を達成するため、請求項１の記憶装置は、それぞれ０より大きな長さを有する区間を一列に並べた区間列を管理するために、木構造を形成し、該木構造に前記各区間を割り当て、記憶媒体上に前記木構造を記憶する木構造生成手段を備え、前記区間列の各区間の終点は数値であり、前記区間（Ａ）の前記終点は、前記区間列中の並び順における先頭の区間から該区間（Ａ）までの各区間の長さの合計値であり、前記木構造は、各ノードにカウンタ列を有し、前記カウンタ列は、該カウンタ列を含むノードの子ノードあるいは子ノードへのポインタを一列に並べたそれぞれの間に、前記各区間の終点を決定するためのカウンタを有し、前記カウンタは、前記各区間と対応付けられ、前記対応は、前記カウンタ（Ｂ）及び該カウンタ（Ｂ）を含む前記カウンタ列（Ｃ）に関し、カウンタ列（Ｃ）中の並び順においてカウンタ（Ｂ）の一方の側に位置するカウンタ、及び、同じく一方の側に位置する子ノードを根とする部分木及びポインタに指示された子ノードを根とする部分木の各ノードのカウンタに対応付けられた前記各区間の終点が、カウンタ（Ｂ）に対応付けられた前記区間の終点以下であり、かつ、カウンタ列（Ｃ）中の並び順においてカウンタ（Ｂ）の他方の側に位置するカウンタ、及び、同じく他方の側に位置する子ノードを根とする部分木及びポインタに指示された子ノードを根とする部分木の各ノードのカウンタに対応付けられた前記各区間の終点が、カウンタ（Ｂ）に対応付けられた前記区間の終点以上であり、前記カウンタには、当該カウンタを含むノードの親ノードあるいは先祖ノードの予め定められた条件を満たすカウンタが存在する場合には、当該カウンタに対応付けられた区間の終点から、上記条件を満たすカウンタに対応付けられた区間の終点を引いた値を設定し、上記条件を満たすカウンタが存在しない場合には、当該カウンタに対応付けられた区間の終点を設定し、前記条件は、前記親ノードあるいは先祖ノードの前記カウンタ列における、前記当該カウンタを含むノードあるいはその親ノードあるいはその先祖ノードもしくはそれらのノードへのポインタと、カウンタとの位置関係によって指定されるものであることを特徴とする。請求項１の発明では、探索に使用する階層データ構造を限定することなく、また、いずれのデータ構造においても、キー探索を行なうのと同等の効率で、順位及び区間の探索を行なうことができる木構造を、生成できる。
【００１１】
また、請求項２の発明は、それぞれ０より大きな長さを有する区間を一列に並べた区間列を管理するために、前記各区間を割り当てて記憶媒体上に形成された木構造に対して、前記区間列の各区間の終点は数値であり、前記区間（Ａ）の前記終点は、前記区間列中の並び順における先頭の区間から該区間（Ａ）までの各区間の長さの合計値であり、前記木構造は、各ノードにカウンタ列を有し、前記カウンタ列は、該カウンタ列を含むノードの子ノードあるいは子ノードへのポインタを一列に並べたそれぞれの間に、前記各区間の終点を決定するためのカウンタを有し、前記カウンタは、前記各区間と対応付けられ、前記対応は、前記カウンタ（Ｂ）及び該カウンタ（Ｂ）を含む前記カウンタ列（Ｃ）に関し、カウンタ列（Ｃ）中の並び順においてカウンタ（Ｂ）の一方の側に位置するカウンタ、及び、同じく一方の側に位置する子ノードを根とする部分木及びポインタに指示された子ノードを根とする部分木の各ノードのカウンタに対応付けられた前記各区間の終点が、カウンタ（Ｂ）に対応付けられた前記区間の終点以下であり、かつ、カウンタ列（Ｃ）中の並び順においてカウンタ（Ｂ）の他方の側に位置するカウンタ、及び、同じく他方の側に位置する子ノードを根とする部分木及びポインタに指示された子ノードを根とする部分木の各ノードのカウンタに対応付けられた前記各区間の終点が、カウンタ（Ｂ）に対応付けられた前記区間の終点以上であり、前記カウンタには、当該カウンタを含むノードの親ノードあるいは先祖ノードの予め定められた条件を満たすカウンタが存在する場合には、当該カウンタに対応付けられた区間の終点から、上記条件を満たすカウンタに対応付けられた区間の終点を引いた値を設定し、上記条件を満たすカウンタが存在しない場合には、当該カウンタに対応付けられた区間の終点を設定し、前記条件は、前記親ノードあるいは先祖ノードの前記カウンタ列における、前記当該カウンタを含むノードあるいはその親ノードあるいはその先祖ノードもしくはそれらのノードへのポインタと、カウンタとの位置関係によって指定されるものであることを特徴とし、前記各区間から、指定数値以上で最小の終点を有する区間を探索するために、前記指定数値を指定して前記木構造を探索する探索手段を備え、前記探索手段は、探索中に探索ノードと探索数値を記憶し、かつ、探索開始時に探索数値を０に設定し、その後、根ノードから葉ノードに向かって順次探索ノードを移動させる探索ステップを実行し、上記探索ステップにおいて、探索数値に探索ノードのカウンタの値を加えた数値と指定数値とを比較して、指定数値以上でより小さな終点を有する区間に対応するカウンタを含む可能性がある子ノードを決定し、探索ノードを上記子ノードに移動する際に、探索数値に、当該子ノードのカウンタに関し前記条件を満たすカウンタが存在する場合に限りそのカウンタの値を加算することを特徴とする。請求項２の発明では、指定した順位を含む区間に対応するカウンタを、効率的に決定することができる。
【００１２】
また、請求項３の発明は、それぞれ０より大きな長さを有する区間を一列に並べた区間列を管理するために、前記各区間を割り当てて記憶媒体上に形成された木構造に対して、前記区間列の各区間の終点は数値であり、前記区間（Ａ）の前記終点は、前記区間列中の並び順における先頭の区間から該区間（Ａ）までの各区間の長さの合計値であり、前記木構造は、各ノードにカウンタ列を有し、前記カウンタ列は、該カウンタ列を含むノードの子ノードあるいは子ノードへのポインタを一列に並べたそれぞれの間に、前記各区間の終点を決定するためのカウンタを有し、前記カウンタは、前記各区間と対応付けられ、前記対応は、前記カウンタ（Ｂ）及び該カウンタ（Ｂ）を含む前記カウンタ列（Ｃ）に関し、カウンタ列（Ｃ）中の並び順においてカウンタ（Ｂ）の一方の側に位置するカウンタ、及び、同じく一方の側に位置する子ノードを根とする部分木及びポインタに指示された子ノードを根とする部分木の各ノードのカウンタに対応付けられた前記各区間の終点が、カウンタ（Ｂ）に対応付けられた前記区間の終点以下であり、かつ、カウンタ列（Ｃ）中の並び順においてカウンタ（Ｂ）の他方の側に位置するカウンタ、及び、同じく他方の側に位置する子ノードを根とする部分木及びポインタに指示された子ノードを根とする部分木の各ノードのカウンタに対応付けられた前記各区間の終点が、カウンタ（Ｂ）に対応付けられた前記区間の終点以上であり、前記カウンタには、当該カウンタを含むノードの親ノードあるいは先祖ノードの予め定められた条件を満たすカウンタが存在する場合には、当該カウンタに対応付けられた区間の終点から、上記条件を満たすカウンタに対応付けられた区間の終点を引いた値を設定し、上記条件を満たすカウンタが存在しない場合には、当該カウンタに対応付けられた区間の終点を設定し、前記条件は、前記親ノードあるいは先祖ノードの前記カウンタ列における、前記当該カウンタを含むノードあるいはその親ノードあるいはその先祖ノードもしくはそれらのノードへのポインタと、カウンタとの位置関係によって指定されるものであることを特徴とし、前記区間の１つを指定して、その終点を得るために、当該区間に対応する指定カウンタを指定して当該区間の終点を決定する決定手段を有し、前記決定手段は、前記指定カウンタを含むノードから根ノードに至るパス上の各ノードに関して、上記各ノードのカウンタへの前記値の設定において使用された、当該カウンタを含むノードの親ノードあるいは先祖ノードの予め定められた条件を満たすカウンタの値だけを合計した数値を、前記指定区間の終点とするステップを実行することを特徴とする。請求項３の発明では、指定したカウンタに対応する区間の（両端の）順位を、効率的に決定することができる。
【００１３】
また、請求項４の発明は、それぞれ０より大きな長さを有する区間を一列に並べた区間列を管理するために、前記各区間を割り当てて記憶媒体上に形成された木構造に対して、前記区間列の各区間の終点は数値であり、前記区間（Ａ）の前記終点は、前記区間列中の並び順における先頭の区間から該区間（Ａ）までの各区間の長さの合計値であり、前記木構造は、各ノードにカウンタ列を有し、前記カウンタ列は、該カウンタ列を含むノードの子ノードあるいは子ノードへのポインタを一列に並べたそれぞれの間に、前記各区間の終点を決定するためのカウンタを有し、前記カウンタは、前記各区間と対応付けられ、前記対応は、前記カウンタ（Ｂ）及び該カウンタ（Ｂ）を含む前記カウンタ列（Ｃ）に関し、カウンタ列（Ｃ）中の並び順においてカウンタ（Ｂ）の一方の側に位置するカウンタ、及び、同じく一方の側に位置する子ノードを根とする部分木及びポインタに指示された子ノードを根とする部分木の各ノードのカウンタに対応付けられた前記各区間の終点が、カウンタ（Ｂ）に対応付けられた前記区間の終点以下であり、かつ、カウンタ列（Ｃ）中の並び順においてカウンタ（Ｂ）の他方の側に位置するカウンタ、及び、同じく他方の側に位置する子ノードを根とする部分木及びポインタに指示された子ノードを根とする部分木の各ノードのカウンタに対応付けられた前記各区間の終点が、カウンタ（Ｂ）に対応付けられた前記区間の終点以上であり、前記カウンタには、当該カウンタを含むノードの親ノードあるいは先祖ノードの予め定められた条件を満たすカウンタが存在する場合には、当該カウンタに対応付けられた区間の終点から、上記条件を満たすカウンタに対応付けられた区間の終点を引いた値を設定し、上記条件を満たすカウンタが存在しない場合には、当該カウンタに対応付けられた区間の終点を設定し、前記条件は、前記親ノードあるいは先祖ノードの前記カウンタ列における、前記当該カウンタを含むノードあるいはその親ノードあるいはその先祖ノードもしくはそれらのノードへのポインタと、カウンタとの位置関係によって指定されるものであることを特徴とし、前記区間の１つを指定して、その長さを指定量だけ変更する操作に対応して、当該区間に対応する指定カウンタ及び前記指定量を指定して、選択的に前記カウンタの値を修正する変更手段を有し、前記変更手段は、前記指定カウンタを含むノードの子ノードのカウンタ及び前記指定カウンタを含むノードから根ノードに至るパス上の各ノードのカウンタのうち、前記区間列中の並び順において、当該カウンタに対応する区間と、上記当該カウンタへの値の設定において使用された、当該カウンタを含むノードの親ノードあるいは先祖ノードの予め定められた条件を満たすカウンタに対応する区間との間に、前記指定カウンタに対応する区間が存在するものを、前記指定量だけ変更するステップを実行することを特徴とする。請求項４の発明では、指定したカウンタに対応する区間の区間長を変更するとともに、後続の各区間の順位をその変更差分だけ増減させ、１つの区間の変更に際して、順位の連続性を保ったまま区間列の構成を維持することができる。
【００１４】
また、請求項５の発明は、それぞれ０より大きな長さを有する区間を一列に並べた区間列を管理するために、前記各区間を割り当てて記憶媒体上に形成された木構造に対して、前記区間列の各区間の終点は数値であり、前記区間（Ａ）の前記終点は、前記区間列中の並び順における先頭の区間から該区間（Ａ）までの各区間の長さの合計値であり、前記木構造は、各ノードにカウンタ列を有し、前記カウンタ列は、該カウンタ列を含むノードの子ノードあるいは子ノードへのポインタを一列に並べたそれぞれの間に、前記各区間の終点を決定するためのカウンタを有し、前記カウンタは、前記各区間と対応付けられ、前記対応は、前記カウンタ（Ｂ）及び該カウンタ（Ｂ）を含む前記カウンタ列（Ｃ）に関し、カウンタ列（Ｃ）中の並び順においてカウンタ（Ｂ）の一方の側に位置するカウンタ、及び、同じく一方の側に位置する子ノードを根とする部分木及びポインタに指示された子ノードを根とする部分木の各ノードのカウンタに対応付けられた前記各区間の終点が、カウンタ（Ｂ）に対応付けられた前記区間の終点以下であり、かつ、カウンタ列（Ｃ）中の並び順においてカウンタ（Ｂ）の他方の側に位置するカウンタ、及び、同じく他方の側に位置する子ノードを根とする部分木及びポインタに指示された子ノードを根とする部分木の各ノードのカウンタに対応付けられた前記各区間の終点が、カウンタ（Ｂ）に対応付けられた前記区間の終点以上であり、前記カウンタには、当該カウンタを含むノードの親ノードあるいは先祖ノードの予め定められた条件を満たすカウンタが存在する場合には、当該カウンタに対応付けられた区間の終点から、上記条件を満たすカウンタに対応付けられた区間の終点を引いた値を設定し、上記条件を満たすカウンタが存在しない場合には、当該カウンタに対応付けられた区間の終点を設定し、前記条件は、前記親ノードあるいは先祖ノードの前記カウンタ列における、前記当該カウンタを含むノードあるいはその親ノードあるいはその先祖ノードもしくはそれらのノードへのポインタと、カウンタとの位置関係によって指定されるものであることを特徴とし、前記区間列において、前記区間の１つ（Ｄ）の、前記区間列中の並び順において直前または直後に、新たな追加区間を挿入追加する変更に応じて、上記区間（Ｄ）に対応する指定カウンタと上記直前または直後の別、及び上記追加区間の長さを指定して、前記木構造を修正する追加手段を有し、前記追加手段は、前記指定カウンタを含むノードの子ノードのカウンタ及び前記指定カウンタを含むノードから根ノードに至るパス上の各ノードのカウンタのうち、前記区間列中の並び順において、当該カウンタに対応する区間と、当該カウンタへの前記値の設定において使用された、当該カウンタを含むノードの親ノードあるいは先祖ノードの予め定められた条件を満たすカウンタに対応する区間との間に、前記追加区間が存在するものを、前記追加区間の長さだけ変更するステップを実行することを特徴とする。請求項５の発明では、指定した位置に区間を挿入するように新たなカウンタを割付けるとともに、後続の各区間の順位をその区間長だけ増加させ、１つの区間の追加に際して、順位の連続性を保ったまま、追加区間以外の従前の区間列の構成を維持することができる。
【００１５】
また、請求項６の発明は、それぞれ０より大きな長さを有する区間を一列に並べた区間列を管理するために、前記各区間を割り当てて記憶媒体上に形成された木構造に対して、前記区間列の各区間の終点は数値であり、前記区間（Ａ）の前記終点は、前記区間列中の並び順における先頭の区間から該区間（Ａ）までの各区間の長さの合計値であり、前記木構造は、各ノードにカウンタ列を有し、前記カウンタ列は、該カウンタ列を含むノードの子ノードあるいは子ノードへのポインタを一列に並べたそれぞれの間に、前記各区間の終点を決定するためのカウンタを有し、前記カウンタは、前記各区間と対応付けられ、前記対応は、前記カウンタ（Ｂ）及び該カウンタ（Ｂ）を含む前記カウンタ列（Ｃ）に関し、カウンタ列（Ｃ）中の並び順においてカウンタ（Ｂ）の一方の側に位置するカウンタ、及び、同じく一方の側に位置する子ノードを根とする部分木及びポインタに指示された子ノードを根とする部分木の各ノードのカウンタに対応付けられた前記各区間の終点が、カウンタ（Ｂ）に対応付けられた前記区間の終点以下であり、かつ、カウンタ列（Ｃ）中の並び順においてカウンタ（Ｂ）の他方の側に位置するカウンタ、及び、同じく他方の側に位置する子ノードを根とする部分木及びポインタに指示された子ノードを根とする部分木の各ノードのカウンタに対応付けられた前記各区間の終点が、カウンタ（Ｂ）に対応付けられた前記区間の終点以上であり、前記カウンタには、当該カウンタを含むノードの親ノードあるいは先祖ノードの予め定められた条件を満たすカウンタが存在する場合には、当該カウンタに対応付けられた区間の終点から、上記条件を満たすカウンタに対応付けられた区間の終点を引いた値を設定し、上記条件を満たすカウンタが存在しない場合には、当該カウンタに対応付けられた区間の終点を設定し、前記条件は、前記親ノードあるいは先祖ノードの前記カウンタ列における、前記当該カウンタを含むノードあるいはその親ノードあるいはその先祖ノードもしくはそれらのノードへのポインタと、カウンタとの位置関係によって指定されるものであることを特徴とし、前記区間列において、前記区間の１つ（Ｄ）を、前記区間列から削除する変更に応じて、上記区間（Ｄ）に対応する指定カウンタを指定して、前記木構造を修正する削除手段を有し、前記削除手段は、前記指定カウンタを含むノードの子ノードのカウンタ及び前記指定カウンタを含むノードから根ノードに至るパス上の各ノードのカウンタのうち、前記区間列中の並び順において、当該カウンタに対応する区間と、当該カウンタへの前記値の設定において使用された、当該カウンタを含むノードの親ノードあるいは先祖ノードの予め定められた条件を満たすカウンタに対応する区間との間に、前記指定カウンタに対応する区間が存在するものを、前記指定カウンタに対応する区間の長さだけ変更するステップを実行することを特徴とする。請求項６の発明では、指定したカウンタに対応する区間を削除するとともに、後続の各区間の順位をその区間長だけ減少させ、１つの区間の削除に際して、順位の連続性を保ったまま、削除区間以外の従前の区間列の構成を維持することができる。
【発明の効果】
【００１６】
以上のように、本発明によれば、各種の探索木を用いて区間列データを管理することができるので、記憶媒体の特性や利用形態に即して、効率的に区間列データを管理できるという効果が得られる。また、キーの探索と区間（順位）の探索とを、１つの木構造を兼用して同等の性能で行うことができ、必要な記憶媒体の量を節約できると同時に、更新操作を１つの木構造に関する操作だけで済ませることができるので、更新の手間も節約できる。
【発明を実施するための最良の形態】
【００１７】
図１８は、本発明を実施する記憶装置の典型的な機能ブロック図である。上記記憶装置は、単調非減少数列データを扱うためのカウンタを備えた階層データ構造１と、これをアクセスして前記（１）の操作を行なう項探索手段２、前記（２）の操作を行なう項決定手段３、前記（３）の操作を行なう項変更手段４、前記（４）の操作を行なう項追加手段５及び前記（５）の操作を行なう項削除手段６を備えている。また、項追加手段５及び項削除手段６は、その機能を達成するために、項変更手段４を使用する。階層データ構造の生成は、上記項追加手段を繰り返し適用して行なうことができるが、各カウンタの計算方法にしたがって予めカウンタ値を計算し、一括して生成する手段を設けることもできる。
【００１８】
説明と理解を容易にするために、本発明に従った階層データ構造は、特に断らない限り、計算機の主記憶内にポインタ（番地情報）等を用いて構成される木構造として説明する。本発明の階層データ構造は、任意のランダムアクセス記憶媒体上で、任意のプロセサによって操作する形態で実施でき、また、任意の記憶媒体に保存できるとともに、任意の通信手段で一方の記憶媒体から他方の記憶媒体に転送できる。従って、本発明の全ての実施例は例示のためだけに示されており、本発明がこれらに限定されるものとはみなされない。従来例２に言うように、このようなデータ構造は、計算機の主記憶または二次記憶内のデータをインデックス付けして記憶するために用いられることが多い。しかしながら、区間列だけを単独のデータとして実施することも可能であり、インデックス付けは単に区間列の応用（用途）の一形態にすぎない。そこで、区間列の各区間だけを階層データ構造で扱う形態についてのみ説明し、それらに対応付けられる、さらなるデータには言及しない。なお、各実施例は、区間列を、各区間の末尾の順位からなる単調非減少数列として、本発明の階層データ構造を使用して実現するものである。
【００１９】
実施に用いられる公知の階層データ構造は、検索対象の要素を昇順（または降順）に、検索可能なように、構造によって定まる構造内の各記憶場所に記憶し、あるいは対応付ける。そこで、各実施例においては、区間の末尾順位を項とする単調非減少数列の各項を、上記公知の順序にしたがって階層データ構造内の記憶場所（カウンタ）への対応付け、それらのカウンタに記憶する値の計算方法を示すとともに、上記（１）〜（５）の操作における、カウンタの使用方法及び更新方法を示す。区間列への応用に際しては、上記記憶場所の（要素の）昇順への対応付けにおいて、直前の項のカウンタを決定する操作が必要であるが、これは各階層データ構造について公知なので、概略を説明するにとどめる。
【００２０】
区間列の各区間と数列の各項の対応付けは、必要に応じて適宜補足する。１つ以上の順位を含む（長さ１以上の）区間に言及する場合、その両端（先頭及び末尾）の順位の間に記号「．．」を挟み、「［］」で囲んだもので表す。［６．．９］は順位６、７、８、９からなる区間であり、［１６．．１６］は順位１６のみからなる区間を表す。また、先頭の順位を「左端」、末尾の順位を「右端」とも言う。これは、実施例で使用する木構造及びそのノードを図示する際に、昇順に、項（区間）やフィールドを、左から右に配置することによる。フィールドを指定する際の正式な呼称は「第１の…」「第２の…」等々であって、左右の別は図を活用して説明を簡明にするために定めただけなので、実施における制約とはならない。このような便宜的な配置の上で、「左端」「右端」「左隣」「右隣」等によって当該項（区間）または順位を指定する。各実施例に使用される階層データ構造は、いずれも公知の探索木であって、それらを構成する複数のノードと、それらのノードを結合する（有向）エッジを、計算機がアクセスする記憶媒体上に記憶する方法、及びそれらの構造を探索・変更する方法についても、複数の方法が知られている。
【００２１】
これらの構造を図示する場合は、フィールド（□で示す）を連ねたノードと、フィールドからノードを指すエッジ（↓で示す）で表す。このエッジは、親ノードから子ノードへの探索を可能にするものであるが、実施にあたっては、子ノードから、自分を指す親ノードのフィールドを決定できる、すなわち、逆向きに探索できる構成を採る。例えば、ノードのフィールドや変数に記憶する番地として、ノードの先頭番地とフィールドオフセットの組を使用すれば、番地を知ることによって、その番地のフィールドを含むノードの先頭番地及びノード内でのフィールドの特定が可能である。さらに、木構造を構成する際に、親ノードの各フィールドに、子ノードの番地を記憶するだけでなく、前記子ノードにも、前記親ノードのフィールドの番地を記憶し、子ノードから、その番地を記憶した親ノードのフィールドが決定できるようにする。親ノードのフィールドを変更して子ノードを切り換えた場合には、それに応じて、子ノード側に記憶された親ノードのフィールドの番地の変更を合わせて行なえばよい。これらの操作は、通常のプログラミング技法の範囲で、容易に実現できる。
【００２２】
したがって、データ構造に関する公知の探索・変更の操作に関しては、フィールドや変数の値の参照・代入に詳細に言及する代わりに、その参照・代入によって達成される作用・効果の記述を用いる。例えば「ノードの右の子ノードの番地フィールドの値がＮＩＬ（空ポインタ）でなければ」の代わりに「ノードに右の子があれば」を使用し、また「ノードの右の子ノードの番地フィールドに、新たなノードの番地を代入し、新たなノードの親ノードの番地フィールドに、前記ノードの番地を代入する」の代わりに、「新たなノードを、前記ノードの右の子とする」を用いる。また、数値または番地を値として代入できる変数（名称○○）に、値（表現××）を設定・代入することを、「○○を××と（に）する」ということにする。値の表現において、「変数またはフィールドの値」といえば、それらに記憶されている数値または番地を指し、「ノードまたはフィールドの番地」といえば、それらの番地を指す。なお、データとして「空」の数列（区間列）を表す場合は、ノードを持たない空の木構造を使用し、これに対しては項の追加（操作（４）の特別な場合として説明）以外の操作は適用しないものとする。各実施例とも、扱う数列は、正整数（自然数）からなる単調非減少数列で、応用として、１から始まる順位区間列を表す。したがって、操作（１）で指定される数値は１以上とする。
【実施例１】
【００２３】
実施例１は、本発明を実施するデータ構造として二分探索木を使用する。図７にそのノードの構成を示す。１つのノードは、左の子ノードの番地、及び右の子ノードの番地を記憶する番地フィールドと、１つの区間に対応付けられた１つのカウンタとして数値フィールドを備えている。このカウンタは、通常の二分探索におけるキーフィールドに相当する機能を果たす。前述のように、親ノードの番地を記憶するフィールドは、図からは省略されているが、本実施例においても、１つのノードから、左の子ノード、右の子ノードを（有無を含めて）決定できるだけでなく、その親ノード及び、親ノードの左右どちらの子であるか、を決定することができる。
【００２４】
図８は、本実施例のデータ構造で、区間列［１．．３］［４．．５］［６．．９］［１０．．１５］［１６．．１６］を、数列３，５，９，１５，１６として実現したものの一例である。各ノードのカウンタは、ノードを中間順序、すなわち二分探索が適用できる順序にしたがって並べた順番で、数列の各項と対応付けられる。各カウンタには、そのカウンタの項と親ノードのカウンタの項との差分が記憶される。親ノードを持たない根ノードのカウンタには、対応する項の値を、そのまま記憶する。二分探索木であるから、左の子ノードのカウンタの項は、親のカウンタの項より小さく、右の子ノードのカウンタの項は親のカウンタの項より大きい。したがって、左の子であるノードのカウンタは負の値、右の子であるノードのカウンタは正の値になる。参考のために、各ノード右側には、その区間を表示し（［．．］）、同じく区間の表示の下には、カウンタに記憶する値の計算式を示してある。実際に記憶されているのは、カウンタ（□内）の値だけである。
【００２５】
以下、例を参照しながら、上記（１）〜（５）の各操作が、効率的に実行できることを説明する。また、ニ分木に加えられる別の変更操作として、ノード間の中間順序を変えずに、二分木の構造（ノード間の親子関係）だけを変更する操作が知られているが、このような操作に際して、上記特徴を持つ数列（区間列）としての機能を維持するようにカウンタ値を変更する方法についても説明する。必要に応じてフローチャートによって手続を図示するが、それらにおいて、「探索ノード」、「候補ノード」は番地変数、「探索数値」、「候補数値」は数値変数である。また、「探索ノード」、「候補ノード」で、それらに記憶された番地のノードにも言及する。
【００２６】
（１）指定数値以上で最小の項のカウンタを決定する操作
図１に操作手続のフローチャートを示す。まず、Ｓ１０１〜Ｓ１０５で、指定数値以上の項のカウンタを含むノードのうちで、根ノードに最も近いノードを決定する。そのようなノードがもしあれば、項が指定数値以上のカウンタを含むノードは、このノードを根とする部分木に全て含まれているから、Ｓ１０７〜Ｓ１１５によって、それらのうちで、中間順序が最も左のノードを決定する。決定したカウンタの項は、候補数値の値として得られている。
【００２７】
参考に、図８のデータ構造例において、指定数値＝８以上で最小の項の探索がどのように進行するかを説明する。まずＳ１０１で、探索ノード＝Ｂ、探索数値＝５とする。指定数値＝８＞探索数値＝５なので、Ｓ１０２からＳ１０３に進み、Ｓ１０３において、探索ノード＝Ｂには右の子ノードＤがあるので、Ｓ１０４及びＳ１０５を実行して探索ノード＝Ｄ、探索数値＝５＋１０＝１５として、Ｓ１０２に戻る。今度は、指定数値＝８＜探索数値＝１５だから、Ｓ１０７に進む。Ｓ１０７において、候補ノード＝Ｄ、候補数値＝１５とし、Ｓ１０８に進む。Ｓ１０８において、探索ノード＝Ｄには左の子Ｃがあるので、Ｓ１０９及びＳ１１０を実行して、探索ノード＝Ｃ、探索数値＝１５−６＝９とする。続くＳ１１１で、指定数値＝８＜探索数値＝９だから、Ｓ１０７に戻り、候補ノード＝Ｃ、候補数値＝９として、Ｓ１０８に進む。今度は、探索ノード＝Ｃに左の子はないから、Ｓ１１６に進む。Ｓ１１６において、候補ノード＝Ｃのカウンタの項、すなわち候補数値＝９が、指定数値＝８以上で最小の項であると判定される。この例に限らず、この手続によれば、根ノードから、１つの終端ノードまたは中間ノード至るパスを１回だけたどることによって探索を完了することができる。
【００２８】
（２）指定したカウンタの項の値を決定する操作
図２に操作手続のフローチャートを示す。この手続は、指定カウンタを含むノードから根ノードに至るパス上の各ノードのカウンタの値を合計し、指定カウンタの項の値とする。
【００２９】
参考に、図８のデータ構造例において、ノードＤのカウンタの項の値がどのように決定されるかを説明する。Ｓ２０１を実行した結果、探索ノードはＤに、探索数値は０に設定される。次にＳ２０２において、探索数値は（０＋Ｄのカウンタ＝１０）＝１０に設定される。続くＳ２０３において、Ｄは根ノードではないので、Ｓ２０４に進んで、Ｄの親ノードＢを探索ノードとし、Ｓ２０２に戻る。Ｓ２０２において、探索数値には、（１０＋Ｂのカウンタ＝５）＝１５が代入される。今度は、Ｂが根ノードなので、Ｓ２０３の条件判定からＳ２０５に進み、探索数値＝１５を指定カウンタの項の値として、処理を終了する。
【００３０】
区間列への応用では、区間の左端の順位を決定するために、指定カウンタの項の直前（左隣）の項のカウンタを決定する必要がある。この手続は、二分木中で、指定ノードの、中間順序で直前（左隣）のノードを決定する手続として、公知である。すなわち、左の部分木（子ノード）がある場合は、その部分木の最右端の子孫ノードとし、そうでない場合は、根ノードまでのパスをたどって最初に現れる、パス上のノードを右の子とする親（先祖）ノードとし、それでもみつからない場合は、直前のノードはない（指定ノードが先頭（左端））と判定すればよい。このようにして決定したカウンタに対して、その項の値を決定する上記手続を適用すれば、直前の項の値が得られるので、区間としての左端の順位はそれをもとに計算できる。これらの手続は、指定区間の右端の順位、及び指定区間の左隣の区間の右端の順位を、それぞれのカウンタを含むノードから根ノードに至るパス上のノードのカウンタ値を合計することによって算出するものである。いずれも、あるノードから根ノードに木構造を遡りながらカウンタを加算する手順を含み、一方のノードは、他方のノードから根ノードに至るパス上にある。したがって、区間長の決定のように、両手続を同時に行なう場合には、これらをひとつの手続にまとめて、重複する操作を省くことも可能である。例えば、区間長を決定する手続は、上述の直前のノードを決定する手続と同じノードを訪れながら、それらのノードのカウンタ値を合計するだけでよい。
【００３１】
（３）数列中の１つの項を増減させる操作（以降の各項を同じだけ増減させる変更を含む）
指定したカウンタの項を、指定差分だけ変更（＋ならば増加、−ならば減少）する手続のフローチャートを、図３に示す。但し、直前の項より小さくなる（先頭の項の場合は負となる）ような変更はできない。項の指定は、そのカウンタを含むノードの番地による。この手続は、指定カウンタを含むノードの左の子ノードから根ノードに至るパス上のノードのうちで、次のようなノードのカウンタだけを変更する。すなわち、そのノードのカウンタの項が指定カウンタの項以前で、親ノードのカウンタの項が、指定カウンタの項以降であるノードのカウンタからは、指定差分を減じ、そのノードのカウンタの項が指定カウンタの項以降で、親ノードのカウンタの項が指定カウンタの項以前であるノードのカウンタには、指定差分を加える。
【００３２】
参考に、図８のノードＣのカウンタの項を２減じる、すなわち指定差分＝−２として、データ構造がどのように変更されるか説明する。まず、Ｃには左の子ノードはないから、Ｓ３０２からＳ３０４に進む。Ｃは根ノードではなく、親ノード＝Ｄの左の子であるから、Ｓ３０５からＳ３０６に進み、Ｄを新たに探索ノードとして、再びＳ３０４を実行する。Ｄは根ノードではなく、親ノード＝Ｂの右の子だから、Ｓ３０５からＳ３０８に進んで、Ｄのカウンタ＝１０に指定差分＝−２を加えて８とし、Ｂを新たな探索ノードとして、Ｓ３１０に進む。Ｂは根ノードだから、そこで処理を終了する。変更後の項（区間）と各カウンタの値は、図９ようになる。このデータ構造を、指定数値＝８として上記（１）の手続で探索すれば、今度はノードＤのカウンタ（項＝１３、区間［８．．１３］）が得られることが確認できる。
【００３３】
（４）数列中に１つの項を追加する操作（以降の各項に、その項と直前の項との差（直前の項がない場合はその項の値）を加える変更を含む）
新たな項の追加は、その項のカウンタを含むノード（となるべきノード）を、二分探索木の新たな終端ノードとして追加するステップと、後続の項の数値の変更の効果をもたらすように、各ノードのカウンタを変更するステップからなる。前者のノード追加ステップは公知であり、概略次のように行うことができる。すなわち、指定カウンタの項の直後（右隣）に新たな項を追加する場合は、指定カウンタを含むノード（指定ノード）に右の子ノードがなければ、追加すべきノードを指定ノードの右の子ノードの位置に追加する。指定ノードに右の子ノードがあれば、その右の子ノードから始めて左の子ノードがある限り左の子ノードへのエッジをたどり、左の子ノードを持たないノードに至って、追加すべきノードをそのノードの左の子ノードの位置に追加する。このとき、追加ノードを右の子ノードの位置に追加した場合は、そのカウンタを０に設定し、左の子ノードの位置に追加した場合は、そのカウンタを−（親（となった）ノードのカウンタの項とその直前の項との差分）に設定する。なお、後者の場合、設定する値は上記（２）の手続によっても得られるが、追加位置を決定する過程で、指定ノードの右の子ノードから親となったノードまでの、訪れた全てのノードのカウンタを合計してもよい。このように追加ノードのカウンタを設定した後、追加ノード及び既存ノードのカウンタの変更を、次のように行なう。
【００３４】
すなわち、追加ノードのカウンタ（の項）を指定カウンタ（指定項）とし、追加した項と直前の項との差分を指定差分（増分）として上記（３）の変更手続を実行する。これは、ノード追加ステップの完了時（追加ノードのカウンタの設定時）において、数列上で指定された位置に挿入された、直前の項と同一数値の項を、改めて当初指定された数値に変更する操作に相当する。区間列としてみれば、初めに長さ０の区間として追加し、追加後に当初指定した区間長に変更することになる。なお、指定カウンタの項の直前への追加の場合は、上記のノード追加ステップ（のみ）において左右を読み替えて操作を行なえばよい。すなわち、指定ノードに左の子ノードがなければ、追加すべきノードを指定ノードの左の子ノードの位置に追加する。この際、追加ノードのカウンタを、（指定ノードのカウンタの項の直前の項−指定ノードのカウンタの項）に設定する。指定ノードに左の子ノードがあれば、その左の子ノードから始めて右の子ノードがある限り右の子ノードへのエッジをたどり、右の子ノードを持たないノードに至って、追加すべきノードをそのノードの右の子ノードの位置に追加する。この際、追加ノードのカウンタを０とする。その後のカウンタの変更に関しては、上記直後に追加する場合と全く同様に行なえばよい。このように、新たな項の追加は、公知のノード追加操作と、（３）の数値変更手続を組み合わせて構成できる。なお、空の数列に項を追加する場合には、新たなノードのカウンタに項の値を設定して根ノードとし、そのノードのみからなる二分探索木とする。
【００３５】
図１０は、図９のデータ構造において、上記手続に従って、項５（区間［４．．５］、ノードＢ）の直後に、新たに項８を挿入し、区間列を［１．．３］［４．．５］［６．．８］［９．．１０］［１１．．１６］［１７．．１７］とした状態のデータ構造を示す。ノードＸが追加されたノードである。追加ノードから根ノードに至るパス上のノードのカウンタは、必ずしも全てが変更されるわけではない。この例の場合でも、ノードＣ、Ｄ、Ｂのうち、変更されたのはＤのカウンタだけである。
【００３６】
（５）数列中の１つの項を削除する操作（以降の各項から、その項と直前の項との差（直前の項がない場合はその項の値）を減じる変更を含む）
指定項の削除は、その項のカウンタを含むノード（指定ノード）を削除するステップと、それに先立って、後続の項の数値の変更の効果をもたらすように、各ノードのカウンタを変更するステップからなる。まず、削除すべき項のカウンタを指定し、直前の項とその項との差分（負数）を指定差分として、上記（３）の変更手続を実行する。これは、削除前の数列において、削除すべき項を直前の項と同じ値に変更する操作である。
【００３７】
続いて行なわれる、指定ノードを二分探索木から削除するステップは公知であって、概略次のように行なうことができる。すなわち、指定ノードに子がない場合は単に指定ノードを削除するだけでよい。指定ノードに、左右いずれか一方の子だけがある場合は、その子ノードを指定ノードの代わりに、指定ノードの親ノードの（指定ノードが子であった方の）子とする。このとき、指定ノードの代わり（に子）となるノードのカウンタに、指定ノードのカウンタ値を加算する。指定ノードに、左右両方の子がある場合は、次の２つの操作のいずれかを行なう。一方は、指定ノードの右の子を指定ノードの親ノードの（指定ノードが子であった方の）子とする。それとともに、右の子から出発して左の子がある限り左の子へのエッジをたどって左の子を持たないノードに至り、指定ノードの左の子をそのノードの左の子の位置に追加する。この際、指定ノードの左の子であったノードのカウンタを、新たに親になったノードのカウンタの項の直前の項と、その項との差分（負数）に設定する。この設定値は、（４）に述べたように、そのノードを決定する過程で訪れたノードのカウンタを合計することによっても、求めることができる。他方は、指定ノードの左の子を指定ノードの親ノードの（指定ノードが子であった方の）子とする。それとともに、左の子から出発して右の子がある限り右の子へのエッジをたどって右の子を持たないノードに至り、指定ノードの右の子をそのノードの右の子の位置に追加する。この場合は、指定ノードの右の子であったノードのカウンタを変更する必要はない。なお、いずれの場合も、指定ノードに代わって、指定ノードの親ノードの（指定ノードが子であった方の）子になったノードのカウンタには、指定ノードのカウンタ値を加算する。このように、項の削除は、（３）の変更手続と、公知のノード削除操作及び削除ノードの子ノードのカウンタ変更操作を組み合わせて行なうことができる。
【００３８】
図１１は、図１０のデータ構造において、上記手続に従って、項１６（区間［１１．．１６］、ノードＤ）を削除し、区間列を［１．．３］［４．．５］［６．．８］［９．．１０］［１１．．１１］とした状態のデータ構造を示す。Ｄには左右両方の子があったので、ノードの削除においては左の子ＣをＤの代わりとする、上記の後者の手続が採られている。
【００３９】
これらの手続はいずれも、二分探索木の根ノードから１つの終端ノードに至るパスの長さに比例する程度のステップ数で実行することができるので、二分探索木の探索・更新の効率を阻害しない。二分探索木の探索・更新の効率は、上記パスの長さに依存するので、これらのパスの長さ（いわゆる木の高さ）を、平均して、あるいは常に、ノードの数の対数に比例する程度に維持する方法が複数知られている。それらの方法は、二分探索木の各ノード間の、いわゆる「中間順序（ｉｎｏｒｄｅｒ）」を変えることなく、ニ分木の構造を変形する。従来例１にも説明されているように、それらの構造変形操作は、数種類の「回転（ｒｏｔａｔｉｏｎ）」と呼ばれる単位操作の組み合わせとして構成可能である。本実施例の二分探索木も、構造変形に係わるノードのみのカウンタの変更によって、変形後も機能を維持することが可能である。これを、上記各回転操作に伴うカウンタの変更操作として実施することができる。これによって、任意の構造変形操作を伴う二分探索木において、本発明を実施できる。
【００４０】
図１２に、構造変形の単位操作（全６種類）に伴う、カウンタの変更方法を示す。ＮＸ、ＮＹ、ＮＺ、ＮＡ、ＮＢ、ＮＣ、ＮＤが、変形に係わるノードＸ、Ｙ、Ｚ、Ａ、Ｂ、Ｃ、Ｄのカウンタの、変形前の値で、ｎＸ、ｎＹ、ｎＺ、ｎＡ、ｎＢ、ｎＣ、ｎＤが、それぞれの変形（変更）後の値である。それぞれの単位操作を示す図（ａ）〜（ｆ）の下に、ｎＸ、ｎＹ、ｎＺ、ｎＡ、ｎＢ、ｎＣ、ｎＤをＮＸ、ＮＹ、ＮＺ、ＮＡ、ＮＢ、ＮＣ、ＮＤから計算する計算式を示す。計算式が示されていないカウンタは、変更の必要がないカウンタである。これらの計算式にしたがって、変形（変更）前のカウンタ値をもとに変形後のカウンタを設定する。左右対称のケース（（ａ）と（ｂ）、（ｃ）と（ｄ）、（ｅ）と（ｆ））について、計算式が同一になっているのは、対称の位置のノード（のカウンタ）に同じ名前付けをしたためである。
【００４１】
図１３は、図１０のデータ構造において、ノードＸに対してｓｐｌａｙｉｎｇ操作を適用した際に、ニ分木の構造とカウンタが、上記単位操作を受けて変更される過程を示す。なお、従来例１にも開示されているように、上記各単位操作に伴うカウンタ変更を行なえば、ｓｐｌａｙ−ｔｒｅｅだけでなく、平衡二分木を始めとする、動的構造調整機構を備えた各種二分木構造に、上記単調非減少数列すなわち順位区間列を扱う機能を追加できる。
【００４２】
以上説明したように、本実施例は、従来例１と同じく、二分探索木の各ノードに設けられた１つのカウンタを使用して、順位区間列の機能を提供（追加）できる。ここで、従来例１に比較した、本実施例の特長を説明する。従来例１と本実施例では、上記（１）〜（５）の手続及び、構造変形単位操作（ａ）〜（ｆ）に伴うカウンタの変更方法が、全て異なっている。これらのうち、（３）の手続においては、従来例１が、指定ノードの親ノードから根ノードに至るパス上の全てのノードのカウンタを変更するのに対して、本実施例は、指定ノードの左の子ノードから根ノードに至るパス上のノードのうち、「左の子がパス上にあり、かつ、自らが右の子」か、あるいは、「右の子がパス上にあり、かつ、自らが左の子」という条件が成り立つノードについてのみ、カウンタを変更すれば済む。（４）の手続においても同様に、従来例１では、追加ノードの親ノードから根ノードに至るパス上の全てのノードのカウンタを変更するのに対して、本実施例は、そのパス上のノードのうち、上記特定の条件が成り立つノードについてのみカウンタを変更すれば済む。（５）の手続においては、同様に削除すべきノードの親ノードから根ノードに至るパス上で、カウンタを変更するノードが少数で済むというだけでなく、次の点でもカウンタの変更が省かれている。すなわち、従来例１においては、削除すべきノードに左右両方の子があった場合は、一方（例えば右）の子から出発して、それと反対の子（左）がある限りたどるパス（このパスの終端ノードの左の子として、削除ノードの左の子を追加）上の全てのノードのカウンタを変更する必要があった。これに対して、本実施例では、削除ノードの代わりに、その親ノードの子とするノード（上記説明例では、削除ノードの右の子）以外は、（上記パス上のノードの）カウンタを変更する必要がない。このように本実施例によれば、従来例１と同等のリソース（記憶領域）を使用して、従来例１より効率的に、従来例１と同等の区間列の機能を提供できる。
【実施例２】
【００４３】
実施例２は、本発明を実施するデータ構造としてＢ木を使用する。Ｂ木は通常、次のようなデータ構造として定義される。
「各ノードは２ｎ個以下の項目を記憶する。このｎをｏｒｄｅｒと呼ぶ。」
「根を除く各ノードは、少なくともｎ個の項目を含む。」
「各ノードは、子を持たない終端ノードか、項目数＋１の子を持つ中間ノードのいずれかである。」
「全ての終端ノードは同じレベル（深さ）にある。すなわち、根に至るパスの長さが等しい。」
例えば、ｏｒｄｅｒ＝２のノードは、子ノードの番地を記憶すべき５個のポインタフィールドと、それらの間に交互に配列された４個の項目フィールドからなる。Ｂ木が探索木として使用できるのは、これらのポインタフィールドと項目フィールドの間に、次の関係を成立・維持させることによる。
「ポインタフィールドに記憶された番地のノードを根とする部分木の、いずれの項目も、そのポインタフィールドの、左隣の項目以上であり、右隣の項目未満である。」
当然、同一ノード内の項目は、左から右に、単調非減少に並ぶ。Ｂ木は、通常は項目として探索キー（データ）を記憶する。
【００４４】
Ｂ木に関する探索・更新の技術は公知であり、例えば、ニクラウス・ヴィルト「アルゴリズム＋データ構造＝プログラム」日本コンピュータ協会（１９７９）４．５多分木（以下、参考文献１という）等に詳しく述べられている。なお、Ｂ木においては、根ノードを除く各ノードの番地を記憶するポインタフィールドは、データ構造中にそれぞれ１つしかないので、煩雑になるのを避けるために、誤解のおそれがない場合は、ノードの番地を記憶している（親ノードの）ポインタフィールドを、省略して「ノードへのポインタ」または「ノードを指すポインタ」ということにする。したがって、「ノードへのポインタの右隣の項目」といえば、「ノードの番地を記憶したポインタフィールドの右隣の項目フィールド」ということである。また、ポインタフィールドに記憶された番地のノードを、その「ポインタが指す（子）ノード」ということにする。また、これらのように、各フィールド（記憶場所）に言及する際に、「フィールド」の呼称を省略する。
【００４５】
Ｂ木が上記単調非減少数列の機能を提供するように、各項目（フィールド）に代えて、それぞれ１つの項に対応付けられたカウンタ（フィールド）を設ける。図１４は、本実施例における、ｏｒｄｅｒ＝２のＢ木のノード構成である。ポインタが指す子ノードを根とする部分木のいずれのカウンタの（対応する）項も、そのポインタの左隣のカウンタの項より右（後）の項であり、右隣のカウンタの項より左（前）の項である。各カウンタをこのように機能させるために、各カウンタには、そのカウンタの項から、そのカウンタを含むノードを指すポインタの左隣のカウンタの項を引いた差分（正数）を記憶する。該当するポインタが、それを含むノードの左端にあって、左隣のカウンタを持たない場合は、さらに、そのノードを指すポインタへと、ポインタが左隣のカウンタを持つまで遡り、その左隣のカウンタの項を、引くべき項として用いる。左隣のカウンタを持つポインタが得られないうちに、根ノード（の左端のポインタ）に至った場合には、引くべき項を０とする。すなわち、そのカウンタに対応付けられた項をカウンタに記憶する。したがって、根ノードの各カウンタには、それぞれ対応する項が記憶される。
【００４６】
このようにして決まる値を記憶したカウンタは、ノード内では左から右に、値の昇順に並ぶことになる。このような構造（性質）を利用して探索手続を構成し、このような構造（性質）を成立・維持するように更新手続を構成する。なお、前述のように、親子関係は、親のポインタから子ノードへたどれるだけでなく、子ノードからそれを指す（親ノードの）ポインタの番地、及び親ノードの番地も決定できるものとする。また、手続で使用する番地変数は、ノードの区別だけでなく、ノード内のフィールドの区別（どのポインタ、カウンタか）も記憶・表現できる。図１５は、参考文献１のＰＰ２５０Ｆｉｇ．４．４８（ｆ）と同一の、ｏｒｄｅｒ＝２、ｌｅｖｅｌ＝３の構造を用い、その各項目（キー）の整数値を項とする単調非減少数列を扱う、本実施例に従うデータ構造の一例である。参考文献１と本実施例では、項（キー）とカウンタ（項目フィールド）との対応付けは全く同じであるが、カウンタに記憶される値は、上記の方法で決定されたものである。この例を参照しながら、上記（１）〜（５）の各操作が、効率的に実現できることを説明する。
【００４７】
（１）指定数値以上で最小の項のカウンタを決定する操作
図４に操作手続のフローチャートを示す。ステップＳ４０２〜Ｓ４０９は、開始ノードを根ノードとする部分木の中に、項が指定数値以上のカウンタが含まれていた場合、それらのうちで、開始ノードに最も近いノードの、最も左に位置するものを決定して、その番地を、候補カウンタに記憶する。一方、終端ノードまで探索してもそのようなカウンタが見つからない場合は、処理を終了する。前者の場合、上記部分木に含まれる、指定数値以上で最小の項のカウンタは、候補カウンタの左隣のポインタが指すノードを根ノードとする部分木に、指定数値以上の項のカウンタが含まれていれば、それらのいずれかであり、含まれていなければ、候補カウンタであることが確定する。したがって、Ｓ４１７で候補カウンタの左隣のポインタが指すノードを新たな開始ノードとして、上記Ｓ４０２〜Ｓ４１７を繰り返し適用することによって、最終的に求めるカウンタ（の番地）を、候補カウンタに得ることができる。なお、ノード内では、カウンタはその値の昇順に配列しており、Ｓ４０３で行なう、これらに対する二分探索の手続きは公知である。
【００４８】
参考に、図１５のデータ構造例において、指定数値＝３２以上で最小の項のカウンタの探索がどのように進行するかを説明する。まず、Ｓ４０１で開始ノード＝根ノードＡ、探索数値＝３２、左隣数値＝候補数値＝０、左隣カウンタ＝候補カウンタ＝ＮＩＬとなる。Ｓ４０２で探索ノード＝Ａとした後、Ｓ４０３で、探索数値＝３２をキーとして探索ノードＡの各カウンタを二分探索する。Ａでは（左端かつ右端の）１つのカウンタしか使われておらず、探索数値＝３２はその値２５より大きいから、Ｓ４０４の条件判定はＮＯとなり、Ｓ４０５に進む。左隣カウンタが、その右端のカウンタとされ、Ｓ４０６で左隣数値は０＋２５＝２５となる。Ｓ４０７で、探索数値は３２−２５＝７とされる。探索ノードＡの右端のポインタはＮＩＬではないから、Ｓ４０９に進んで、探索ノードを上記ポインタが指すノードＣとして、再びＳ４０３を実行する。今度は、探索数値＝７で、カウンタ値５、１５を二分探索し、７以上の最小の値のカウンタを値１５のカウンタ、その左隣のカウンタを値５のカウンタと決定する。この場合、Ｓ４１０、Ｓ４１１、Ｓ４１２、Ｓ４１３、Ｓ４１４、Ｓ４１５が実行され、候補カウンタを値１５のカウンタとし、候補数値を２５＋１５＝４０とし、左隣カウンタを値５のカウンタとし、左隣数値を２５＋５＝３０とし、探索数値を７−５＝２とする。候補カウンタと左隣カウンタとの間のポインタはノードＨを指しているので、Ｓ４１６からＳ４１７に至って開始ノードをＨとし、再びＳ４０２を実行する。探索数値＝２で、カウンタ値２、５、８を二分探索し、カウンタ値２と一致する（探索数値以上で左端のカウンタは値２のカウンタである）ことが判明してＳ４１０に進む。候補カウンタを値２のカウンタとし、候補数値を３０＋２＝３２とする。候補カウンタには左隣のカウンタはないので、Ｓ４１２からＳ４１６に進む。候補カウンタの左隣のポインタはＮＩＬなので、Ｓ４１８に進む。結局、ノードＨの値２のカウンタが、指定数値＝３２以上で最小の項のカウンタであると決定される。その項の値は、候補数値＝３２である。また、直前の項のカウンタは左隣カウンタとして得られており、その項の数値は、左隣数値＝３０である。このようにして、この例に限らず、上記手続によれば、根ノードから、１つの終端ノードに至るパスを１回だけたどることによって探索を完了することができる。
【００４９】
（２）指定したカウンタの項の値を決定する操作
図５に操作手続のフローチャートを示す。この手続は、指定カウンタと、指定カウンタを含むノードから根ノードに至るパスを構成する各ポインタの左隣カウンタの値を合計して、指定カウンタの項の値とする。
【００５０】
参考として、図１５のデータ構造例において、ノードＦの左端のカウンタの区間の右端の順位がどのように決定されるかを説明する。まずＳ５０１を実行して、探索ノードはＦに、探索数値は２に設定される。Ｆは根ノードではないから、Ｓ５０２からＳ５０３に進み、ＦへのポインタであるＢの右端のポインタの左隣のカウンタの値２０を、Ｓ５０４で探索数値に加えて２２とし、Ｓ５０５で探索ノードをＢとする。再びＳ５０２においてＢは根ノードではないから、Ｓ５０３に進むが、探索ノードＢへのポインタであるＡの左端のポインタには左隣のカウンタがないので、Ｓ５０５に進んで探索ノードをＡとする。Ａは根ノードであるから、Ｓ５０２からＳ５０６に進み、指定カウンタの項の数値を、探索数値の値２２として処理を終了する。
【００５１】
なお、区間列への応用で必要となる、指定カウンタの項の直前（左隣）の項のカウンタを決定する手続は、Ｂ木において指定した項目（カウンタ）の、直前の項目（カウンタ）を決定する手続として公知である。すなわち、指定カウンタの左隣のポインタがＮＩＬでなければ、それが指すノードから始めて右端のポインタをたどり、終端ノードに至ってその右端のカウンタを直前のカウンタとする。左隣のポインタがＮＩＬの場合は、指定カウンタに左隣のカウンタがあれば、それが直前のカウンタであり、なければ、指定カウンタを含むノードを指すポインタから始めて、最初に左隣のカウンタを持つポインタまで遡り、その左隣のカウンタを直前のカウンタとする。根ノードまで遡っても左隣のカウンタがない場合は、指定カウンタが先頭の項のカウンタである。区間の左端順位を決定する手続も、区間長を計算する効率的な方法も、実施例１と同様に構成できる。
【００５２】
（３）数列中の１つの項を増減させる操作（以降の各項を同じだけ増減させる変更を含む
）
図６は、指定カウンタの項を、指定差分（＋ならば増加、−ならば減少）だけ変更する手続のフローチャートである。但し、減少分は、その項と直前の項との差（直前の項がない場合はその項の値）以下とする。「境界ポインタ」はポインタの番地を記憶する変数である。この手続は非常に単純なので、図１５のデータ構造において、ノードＧの右端のカウンタの項２７（区間［２７．．２７］）を＋３した結果の状態のみを図１６に示す。項２７が項３０（区間［２７．．３０］）に変更されるだけでなく、以降の項（区間の両端）も全て＋３される。図１６の下部には、その状態における各カウンタの区間を表示した。図１６のデータ構造に対して、指定順位（数値）＝３２として上記（１）の手続を実行すれば、ノードＣの左端のカウンタの区間［３１．．３３］が得られることが確認できる。
【００５３】
（４）数列中に１つの項を追加する操作（以降の各項に、その項と直前の項との差（直前
の項がない場合はその項の値）を加える変更を含む）
新たな項の追加は、その項に対応するカウンタとして、Ｂ木のノードのカウンタを割付けるステップと、後続の項の数値の変更の効果をもたらすように、各ノードのカウンタを変更するステップからなる。前者のカウンタ割付けステップは、Ｂ木に対するキーの追加手続として公知であり、参考文献１にも詳しく述べられている。すなわち、新たな割付けは、まず終端ノードの指定項のカウンタの左隣あるいは右隣への新たなカウンタの挿入割付けとして扱うことができる。手続を簡単にするために、各ノードには、一時的にｏｒｄｅｒの２倍＋１個のカウンタ、及びｏｒｄｅｒの２倍＋２個のポインタを設定できるものとする。まず、カウンタを挿入すべき位置の右にあるカウンタをすべて１つづつ右にずらして（ポインタはすべてＮＩＬなので操作しなくてよい）、空いたカウンタを追加項のカウンタとする。このとき、追加項のカウンタ値は、左隣のカウンタがあればそれと同じ値に、なければ０に設定する。これは、追加項を直前の項と同じ数値とすることに相当する。区間列への応用の見地からは、区間長を０として新たな区間を挿入するのと同等の効果を持つ。
【００５４】
次に、追加した項のカウンタを指定して、上記（３）の変更手続を使用して、その項の数値を、当初指定された数値に変更する（増加させる）。カウンタを追加した後で、ノード内のカウンタの数がｏｒｄｅｒの２倍以下であれば、カウンタの割付け手続は完了する。カウンタの数がｏｒｄｅｒの２倍＋１個になってしまった場合、そのノードを２つに分割する。分割手続のうち、カウンタ及びポインタの割付けの変更は公知の手続であるが、それに伴うカウンタ値の変更は、本実施例（本発明）に特有の操作である。すなわち、中央の（ｏｒｄｅｒ＋１個目の）カウンタの右にあるポインタ及びカウンタの割付を新たなノードに移す。このとき、移動した各カウンタから中央のカウンタ値を減ずる。中央のカウンタの左にあるポインタとカウンタはそのまま割付けておく。そして、中央のカウンタの割付けを、そのノードを指すポインタの右隣の位置に変更する。つまり、今度はそのポインタの右にあるカウンタ及びポインタをすべて１つづつ右にずらして、空いたカウンタを上記中央のカウンタとして割付ける。このとき、左隣にカウンタがあれば、その値をこれまでの（上記中央のカウンタ）値に加算する。また、上記空いたカウンタの右隣のポインタに、上記新たなノードを指させる。
【００５５】
これで、１回のノード分割手続は終了するが、この結果中央のカウンタを再割付け（移動）した先のノード（親ノード）において、カウンタの数がｏｒｄｅｒの２倍＋１になった場合には、さらにこのノードを分割する。このようにして、分割が根ノードに至った場合は、さらに新たなノードを用意して根ノードとし、これまでの根ノードの中央のカウンタをその左端のカウンタに再割付けし、その左隣のポインタにこれまでの根ノードを指させ、右隣のポインタには分割で新たに導入された（これまでの根ノードの右半分のポインタ及びカウンタを移した）ノードを指させる。なお、追加した項の数値を（３）の手続を使用して当初指定の数値に変更する操作を、上記のノード分割手続の後で行なうことも可能である。そうする場合には、分割に伴う再割付けや移動において、最初に追加したカウンタがノード間を移動することがあるので、どれが追加した項のカウンタかを記憶しておく。なお、空の数列に項を追加する場合には、新たなノードの左端のカウンタに項の値を設定して根ノードとし、そのノードのみからなるＢ木とする。
【００５６】
（５）数列中の１つの項を削除する操作（以降の各項から、その項と直前の項との差（直
前の項がない場合はその項の値）を減じる変更を含む）
指定した項の削除は、その項のカウンタを削除するステップと、それに先立って、後続の項の数値の変更の効果をもたらすように、各ノードのカウンタを変更するステップからなる。まず、削除すべき項のカウンタを指定カウンタとし、その項と直前の項との差（直前の項がない場合はその項の値）を負数（マイナス）にした値を指定差分として、上記（３）の変更手続を実行する。これは、削除前の数列において、削除すべき項の数値を直前の項と同じ値にする（区間として見れば、その区間長を０にする）操作に相当する。
【００５７】
続いて行なわれる、指定カウンタをＢ木から削除するステップは公知であって、概略次のように行なうことができる。但し、削除に伴う各ノードのカウンタの変更は、本実施例に特有の操作である。まず、削除すべきカウンタが終端ノードにない、すなわち中間ノード上にある場合は、そのカウンタの左隣のポインタの指すノードから出発して、右端のポインタがＮＩＬでない限り右端のポインタが指すノードをたどり、右端のポインタがＮＩＬとなったノードの右端のカウンタと指定カウンタの割付けを交換する。このとき、両カウンタは異なる項に対応付けられているとはいえ、同一の数値を表すので、単に上記右端のカウンタを次のステップで削除し、上記指定カウンタを残せば、上記指定カウンタが新たに、上記右端のカウンタの項のカウンタとして機能するようになる。もちろん、上記右端のカウンタの項に対応付けられていた他の情報がもしあれば、そのカウンタへの対応付けは、上記指定カウンタに変更しなければならない。
【００５８】
Ｂ木の終端ノードからのカウンタの削除は、それより右にあるカウンタを全て、１つづつ左に移動させる。この際、カウンタの値は変更しなくてよい。終端ノードでは全てのポインタはＮＩＬだから、操作・変更を加える必要はない。参考文献１によれば、Ｂ木の終端ノードからの項目（カウンタ）の削除に続いて、そのノードの項目数がｏｒｄｅｒ未満になった場合には、まず「バランス化」と呼ばれる操作を試みる。バランス化は、「隣のノードの１つから１つの項目を借りてくる，あるいは取ってくることである」。これに伴うカウンタ値の変更は、本実施例（本発明）に特有の操作である。具体的には、親ノードの１つのカウンタと、その両隣のポインタが指す左右２つの（終端）ノードの間で、左から右へ、または右から左へ、１つのカウンタを順送りに割付け（位置）を移動させる操作によって実現される。右から左へ移動させる場合は、親ノードのカウンタを左ノードの右端のカウンタとして追加し、親ノードのカウンタの位置には、右ノードの左端のカウンタを移動し、右ノードのそれ以外の全てのカウンタから左端のカウンタの値を減じるとともに、それらを１つづつ左へ移動する。上記右ノードの左端のカウンタを親ノードのカウンタの位置に移動する際には、その値に親ノードのカウンタの値を加える。親ノードのカウンタを左ノードの右端に移動する際には、移動前の親ノードにおいて左隣のカウンタがあればその値を減じる。左から右へ移動させる場合は、まず右ノードの全てのカウンタに親ノードのカウンタの項と直前の項との差分を加えるとともに、それらを１つづつ右へ移動する。空いた左端の位置に、親ノードのカウンタを移動してその値をその項と直前の項との差分とする。親ノードのカウンタの位置には、左ノードの右端のカウンタを移動する。この際、上記親ノードのカウンタの位置に左隣のカウンタがあれば、その値を加算する。複数のカウンタを移動する場合は、この操作を繰返してもよいし、移動するカウンタの項と直前の項との差分（区間としてみれば、移動するカウンタの区間の区間長）を予め計算して、それらの移動先での値やノード内で移動されるカウンタの値を一度に計算するようにしてもよい。
【００５９】
バランス化が適用できない場合、すなわち、隣のノードがいずれも既にｏｒｄｅｒ個のカウンタしか含まない場合は、いずれかのノードとの間で「統合」と呼ばれる操作を行なう。これに伴うカウンタ値の変更は、本実施例（本発明）に特有の操作である。具体的には、親ノードの１つのカウンタと、その左右のポインタが指すノードのカウンタ及びポインタを連接して、ｏｒｄｅｒの２倍の数のカウンタとそれより１つ多いポインタからなるノードを作成し、そのノードへのポインタを親ノードの前記左のポインタとし、親ノードの前記右のポインタの右にあるカウンタ及びポインタを、１つづつ左に移動する。２つのノードと１つのカウンタを１つのノードにまとめる際に、左右どちらのノードを残す手続も可能であるが、ここでは左の（ポインタが指す）ノードを残す手続を説明する。親ノードのカウンタは、左のノードの右端のカウンタ（ポインタ）の右隣に移動する。その右隣から続けて、右のノードのポインタとカウンタを、そのままの順で移動する。このとき、元の親ノードのカウンタの値からその左隣のカウンタの値（親ノードのカウンタが左端の場合は０）を引いた値を、親ノードのカウンタの移動先での値とする。さらに、右のノードから左のノードに移動したカウンタの値に、この親ノードのカウンタの移動先での値を加算する。元から左のノードにあった各カウンタの値はそのままでよい。統合は、最初、終端ノードとその親ノードのカウンタとの間で行なわれるが、親ノードのカウンタが１つ削除（移動）された結果、カウンタ数がｏｒｄｅｒ未満になって、中間ノードの間でも統合が必要になることがある。このため、中間ノードの統合では、上記手続に合わせてポインタも移動する。さらには、これが伝播して、根ノードのカウンタを含む統合が生じることがある。根ノードの１つしかないカウンタを巻き込んで統合が行なわれると、統合後は元の根ノードは空になって削除され、残った左の（子）ノードが新たな根ノードとなる。
【００６０】
以上、カウンタの削除に先立って後続の項の数値の変更のために各ノードのカウンタを変更する手続、カウンタを終端ノードに移動する手続に伴うカウンタ値変更手続、バランス化の手続に伴うカウンタ値変更手続、統合の手続に伴うカウンタ値変更手続を説明した。Ｂ木から項目を削除する（公知の）手続は、（項目の）終端ノードへの移動、バランス化、及び、統合の組み合わせとして種々構成できるから、それに、上記カウンタの変更手続を付加すれば、カウンタの削除手続を得ることができる。
【００６１】
以上説明したように、本実施例は、従来例２と同じく、Ｂ木の各項目の位置に、単調非減少数列の各項に対応付けられたカウンタを設けて、上記特徴をもつ単調非減少数列を扱う機能、すなわち順位区間列を扱う機能を提供できる。Ｂ木によって探索可能な各項目に加えて、これらのカウンタを設ければ、従来例２と同様に、順序付けられたキー集合を扱う記憶装置が実現できる。従来例２は正確には、順序付き要素（順位）を終端ノードのみに記憶する（対応付ける）Ｂ’木を使用している。本発明をＢ’木で実施する例は、次の実施例３で説明するが、従来例２と本発明との差異は、Ｂ木及びＢ’木で実施する場合に共通しているので、ここで、従来例２に比較した、本実施例の特長を説明する。
【００６２】
従来例２と本実施例では、上記（１）〜（５）の手続、及びそれらに伴うカウンタの変更方法が、全て異なっている。これらのうち、（１）の手続においては、従来例２が、ノード内で次にたどるべきポインタ、あるいは指定数値以上で最小の項のカウンタを決定する際に、左端（あるいは右端）のカウンタから、カウンタ値を累計しながら線形探索せざるをえない（従来例２、図１２、５０５のステップ）のに対して、本実施例（本発明）では、ノード内の各カウンタの値と指定数値を加工した探索数値とを直ちに比較して上記（カウンタの項が指定数値以上か否かの）決定が行なえるので、二分探索が実行できる（（１）Ｓ４０３）。このため、１つのノードが多数のカウンタ（ポインタ）を含む場合でも、該当するカウンタやたどるべきポインタを効率良く決定できる。すなわち、探索に要する比較回数は、（ｏｒｄｅｒの対数）×（カウンタの総数の対数）に比例する程度に抑えることができる。従来例２における比較回数は、ｏｒｄｅｒ×（カウンタの総数の対数）に比例するので、ｏｒｄｅｒが大きくなるのに比例して手間が増大する。
【００６３】
また、従来例２には、本実施例（２）に対応する操作は開示されておらず、その代わりに、キーを探索しながらそのキーの順位を同時に計算する手続（キーカウント）が開示されている。上記（２）とキーカウントとは、Ｂ木を根に向かってたどるか根から出発してたどるかが違うだけで、パス上のノードのカウンタ値から順位を計算するという機能は同じである。すなわち、相互に、同じ機能となるように手続を改変できる。しかしながら、従来例２では各ノードにおいて、「左側の部分木のカウントの小計をとる（従来例２、図１１、４０５のステップ）」操作が必須で、ノードのカウンタ数（ｏｒｄｅｒ）に比例する手間がかかる。これに対して、本実施例（本発明）では、パス上の各ポインタの左隣のカウンタのみを、すなわち１つのノードについて高々１つのカウンタの値のみを加算するだけで済む。つまり、パスの長さ、すなわちＢ木の「高さ」以下の回数の加算を行なうだけで、項の数値（順位）を決定できる。ｏｒｄｅｒが大きいほどＢ木の高さは低くなるので、本実施例の順位（項）決定手続の手間は減少し、対照的に従来例２の順位決定手続の手間は増加する。このように、本実施例によれば、従来例２と同等のリソース（記憶領域）を使用して、従来例２より効率的に（順位）区間列の探索機能を提供することができる。
【実施例３】
【００６４】
実施例３は、本発明を実施するデータ構造としてＢ’木を使用する。Ｂ’木は実施例２で用いたＢ木に類似のデータ構造で、探索対象の項目を終端ノードのみに記憶する。中間ノードの項目には、根ノードから出発して終端ノードの項目に至る探索の過程を制御するための値が記憶される。これに対して終端ノードには、探索対象の項目だけが記憶される。各ノードの項目は、その値の（昇）順に左から右に並べられる。通常、中間ノードの項目には、その項目の左隣のポインタが指す（ノードを根とする）部分木の終端ノードの項目（すなわち探索対象項目）のうちで最大（すなわち右端）の値がコピーされている。指定した値をキーとして項目を探索する手続において、Ｂ木と異なるのは、中間ノードで一致する項目が見つかった場合でも探索を終了せず、その左隣のポインタをたどって探索を継続する点である。キーと一致する項目の決定及び一致する項目が無いことの決定は、探索が終端ノードに至って初めて行なわれる。本実施例では、実施例２と同じ構成のノードを使用する。
【００６５】
実施例２と異なるのは、区間列への応用において、区間列の各区間に対応付けられるのが、終端ノードの各カウンタ（の項）だけで、中間ノードのカウンタ（の項）は対応付けられない点である。終端ノードのカウンタの項は、全て、区間列のいずれかの区間の右端順位に対応付けられる。これに対して、中間ノードのカウンタの項は、その直前の項と、同一の数値を表すように設定される。すなわち、中間ノードのカウンタは、その左隣のポインタが指すノードを根とする部分木の終端ノードのカウンタの区間からなる部分区間列の、右端の区間の右端順位を表す。これは、そのような右端順位を持つ長さ０の（仮想的な）区間を、元の区間列に追加して、それらに中間ノードのカウンタを対応付けたと同等なので、（終端ノードも中間ノードも）各カウンタに記憶する値は、実施例２と全く同様にして計算できる。
【００６６】
図１７は、図１５で扱われた項のうち、終端ノードのカウンタの項のみを、区間列の各区間の右端順位とし、中間ノードのカウンタの項は、上述のように直前の項と同一数値に設定（変更）した数列として、Ｂ’木によって表された区間列の例である。図の下部は、中間ノードのカウンタに対応する、長さ０で右端順位ｎｎの区間を、「［ｎｎ］」の表記で追加した区間列を示している。検索・更新対象として扱われるのは、この列から［ｎｎ］を除いた、［ｍｍ．．ｎｎ］のみからなる区間列（の区間）である。この例は、図１５の中間ノードのカウンタの区間の区間長をそれぞれ０とし、それらの区間長だけその左隣の区間の区間長を増した状態（区間列）と同等である。
【００６７】
実施例２と関連付けて別の説明をすれば、実施例２の（５）（区間）削除手続において、削除に先立って対象区間の区間長を０とするようなカウンタの変更を（３）（区間長）変更手続を用いて行なった。この状態でも、他の区間の順位は既に削除後の値として探索可能になっているので、区間長０の区間（カウンタ）を探索結果としないで、探索を継続するように（１）探索手続を修正すれば、カウンタの削除を行なわなくても、削除後に探索したのと同じ結果を得ることができる。そこで、中間ノードのカウンタの区間の区間長を全て０とし、終端ノードのカウンタの区間のみが１以上の区間長を持つ探索対象区間となるようなデータ構造（実施例２のＢ木による単調非減少数列を扱うデータ構造のサブセット）を、本実施例のデータ構造として使用するのである。
【００６８】
応用における操作の対象が、終端ノードのカウンタ、すなわち、数列中の同一数値の項のうち、左端の項のカウンタのみに限られ、さらに、同一数値の項はＢ’木としての構成を維持するために、適宜追加・削除されるので、上記（１）〜（５）の各操作には、実施例２とは若干異なるものもある。以下にこれらの各操作を説明するが、重複を避けるために、それぞれ実施例２の各手続を前提にして、本実施例における変更点のみを説明する。
【００６９】
（１）指定順位を含む区間の探索（指定数値以上で最小の項のうち、左端のもののカウン
タの決定）
図４に示した、実施例２（１）と同じ手続が使用できる。本実施例のデータ構造では、該当する項のカウンタが存在する場合には、終端ノードにおいて必ず探索数値以上の値のカウンタが見つかるので、Ｓ４１５には必ずＳ４１３から到達し、その直前のＳ４０９において、終端ノードのカウンタが候補カウンタとされる。したがって、この手続によって、検索対象でない中間ノードのカウンタが検索結果とされる恐れはない。
【００７０】
（２）指定区間の右端順位／左端順位の決定（指定したカウンタの項の値の決定）
実施例２（２）の手続をそのまま使用することができる。但し、本実施例では、指定カウンタは必ず終端ノード上のカウンタなので、その左隣のポインタはＮＩＬである。したがって、直前のカウンタを決定する手続においては、同じ終端ノードに左隣のカウンタがあれば、それが直前のカウンタであり、なければ、まず、親（先祖）ノードに遡っていく手続によって、Ｂ木における直前のカウンタを決定する。次に、決定されたカウンタの左隣のポインタが指すノードから始めて、右端のポインタが指すノードをたどり、到達した終端ノードの右端のカウンタを、直前のカウンタとする。
【００７１】
（３）指定区間の区間長の変更、及び後続区間の順位の変更（数列中の１つの項の値の増減）
実施例２（３）の手続をそのまま使用する。本実施例では、指定カウンタは必ず終端ノード上のカウンタである。
【００７２】
（４）指定区間の直前／直後への新たな区間の追加、及び後続区間の順位の変更（数列への１つの項の追加）
まず、実施例２と同じく、終端ノードの指定区間のカウンタの左隣あるいは右隣への新たなカウンタの挿入割付けを、区間長を０（直前の項と同一数値）として行なう。続いて、上記（３）の手続を使用して、追加した区間（カウンタ）の区間長を、指定された長さに増加させるステップも、実施例２と同様である。本実施例では、ノードの分割の方法が実施例２とは少し異なっている。まず、終端ノードにおいては、カウンタの数がｏｒｄｅｒの２倍に達したら、ノードを分割する。具体的には、分割すべき終端ノードの右半分のｏｒｄｅｒ個のカウンタを１つづつ右に移動して、中央の（ｏｒｄｅｒ＋１個目の）カウンタを空け、これに左隣のカウンタと同じ値を設定する。これは、そのノードが表す（部分）区間列の中央に、長さ０の区間を新たに挿入したのに相当する。これで、その終端ノードはｏｒｄｅｒの２倍＋１個のカウンタを含むことになり、実施例２の（終端）ノードの分割条件に該当する。これ以降のノード分割ステップは、実施例２の手続をそのまま使用する。すなわち、まず、終端ノードを２つに分割し、中央の長さ０の区間のカウンタを移動して親ノードに挿入する。親ノード以上の、中間ノードにおける分割手順は、実施例２と全く同様である。この操作によって、追加された区間を含めて、長さが１以上の探索対象の区間のカウンタが終端ノードのみに割付けられているというＢ’木の性質は維持される。
【００７３】
（５）指定区間の削除、及び後続区間の順位の変更（数列中の１つの項の削除）
終端ノード上の指定区間のカウンタに対して、まず、上記（３）の区間長変更手続を適用して、その区間長を０に変更する。その後、このカウンタ（に対する区間の割付け）を削除して、その右のカウンタを１つづつ左に移動する。本実施例では、削除対象の区間のカウンタは全て終端ノードにあるから、実施例２のように、中間ノード上の削除対象カウンタを終端ノードのカウンタと交換する手続は不要である。続いて、カウンタを削除した終端ノードのカウンタの数が、ｏｒｄｅｒ未満になった場合は、まず、バランス化の操作を試みる。実施例２と異なって、カウンタ移動先の（子）ノードに移されるのは、親ノードのカウンタではなく、隣の（もう一つの子）ノードの移動先ノード側の端のカウンタである。左のノードの右端に、右のノードの左端のカウンタを移動する場合は、その移動先でのカウンタ値に、移動先での左隣のカウンタの値を加え、右のノードに残って１つづつ左へずらされる各カウンタからは、移動前の上記左端のカウンタの値、すなわちその区間の区間長をそれぞれ減じ、左右のノードを指す親ノードのポインタの間のカウンタには、前記区間長を加える。一方、右のノードの左端に、左のノードの右端のカウンタを移動する場合は、まず、右のノードの各カウンタを１つづつ右に移動して左端のカウンタを空け、そこに左のノードの右端のカウンタを移動して、その値をその区間の区間長とする。そして、元から右のノードにあった各カウンタに、上記区間長をそれぞれ加えるとともに、左右のノードを指す親ノードのポインタの間のカウンタからは、前記区間長を減じる。バランス化が適用できない場合には、左右のノードの統合が行なわれるが、本実施例では、２つの終端ノードを統合する場合には、親ノードのカウンタを、子ノードである終端ノードには移動せず、木（ノード）から削除する。中間ノードである親ノードのカウンタは、探索対象の区間を表さないからである。これに対して、終端ノードの統合の影響で生じる中間ノードの統合に際しては、実施例２と全く同じ手続が適用される。なお、統合に伴うカウンタの移動・変更は、上記バランス化の場合と同様の手続による。
【００７４】
以上説明したように、本実施例は、終端ノードのみに含まれる各（項の）カウンタに区間を対応付けるＢ’木のような階層データ構造を使用して、順位区間列の機能を提供（追加）できる。従来例２も、このように終端ノードのみに項目（順位）を記憶する（対応付ける）木構造を使用して順位を扱う技術を開示している。従来例２に比較した本実施例（本発明）の特長は、上記実施例２の説明において述べたとおりである。
【００７５】
なお、本発明は上記各実施例の形態に限定されるものではなく、適宜実施態様を変更して実施できる。すなわち本発明は、各カウンタを単調非減少数列の各項に対応付け、各カウンタの値を、それに対応付けられた項と、それぞれ定められた他のカウンタに対応付けられた項との差分になるように設定・維持する。これにより、（２）の手続にみるように、指定されたカウンタを始めとして、その値（差分）を決める上記定められたカウンタを次々にたどりながら加算して、その項の値を算出できるようになっている。（１）の手続では、加算の順番が変わるだけで、探索結果のカウンタについて、その項の値を計算するのに使用されるカウンタの組は同じである。このようにして項の値が決定できるためには、各項間の相対的な差分だけでなく、差分の起点となる項の値自体が、それらの累計に１つ含まれるようにする必要がある。このように、項の値自体を記憶したカウンタは、上記各実施例においては根ノードに配置されているが、累計手続が起点となる項を正しく含むように構成されていれば、必ずしも根ノードに置かなくてもよい。また、計算に使用される他のカウンタの配置も、（１）、（２）の探索手続においてそれらのカウンタの組が決定できるのであれば、それらが木構造の各ノードにどのように配置されていても構わない。また、探索手続における上記カウンタの組の決定方法（配置方法）が定まれば、それに合わせて、（３）、（４）、及び（５）の各更新手続を構成できる。カウンタの配置としては、例えば、１つのノードが複数のカウンタを含む場合に、それらのうちのいくつかは、同一ノード内のカウンタを上記定められたカウンタとして、その項との差分を記憶するようにしてもよい。また、実施例２及び実施例３では、各カウンタの項と差分をとるべき項のカウンタは、そのカウンタを含むノードを指すポインタの左隣のカウンタで、そのようなカウンタが見つかるまで、根ノードに至るパスを遡るとした。これを、実施例１のように、前記ポインタに左隣のカウンタがない（左端のポインタの）場合は、右隣のカウンタの項との差分をとる、という構成を採用することもできる。逆に、実施例１の二分探索木において、左の子ノードのカウンタが差分をとるべき項のカウンタを、根ノードへのパス上で、最初に右の子の親となっているノードのカウンタとし、実施例２と同様に、カウンタには全て正の値（差分）が記憶されるようにすることもできる。
【００７６】
使用する階層的データ構造（木構造）も、上記各実施例の二分木、Ｂ木、Ｂ’木に限定されず、任意の木構造を使用することができる。上記実施例３（Ｂ’木）において説明したように、これらのデータ構造には、その一部のノード（Ｂ’木では終端ノード）にしか、探索対象項目（カウンタ）を記憶しないものも含まれる。そのようなデータ構造において実施する場合には、探索の際にアクセスされるが、探索対象でない（探索結果にならない）カウンタ（Ｂ’木では中間ノードの項目）には、順位のみあって長さが０の区間を対応付けることによって、手続の多くの部分が、全てのノードのカウンタが探索対象であるデータ構造において実施する場合の手続と共通にできる。
【００７７】
上記各実施例では、本発明に従ったデータ構造は、計算機の主記憶内にポインタ（番地情報）等を用いて構成される木構造として説明されたが、本発明の実施例はこれに限られない。ノード及び項目（カウンタ）の一部または全部が、二次記憶装置に記憶されており、それらをＣＰＵと主記憶からなる計算機が読み出して処理を行なうという形態も可能である。また、構造の一部または全部が、通信ネットワーク等の通信手段を経由して他の記憶媒体上に、複製あるいは分割して配置されるという形態も可能である。その際、データ構造を構成するためのポインタとしては、主記憶の番地に代わって、ノードの所在及びアクセス手段を表す情報が適宜使用される。また、ノード間の接続を実現する方法も、ポインタまたはそれに準じる情報を記憶する方法に限らず、ノードの番地または所在から直接計算する方法、例えば、二分木において、番地Ｎのノードの左の子を番地２Ｎに、右の子を番地２Ｎ＋１に配置する等の方法をとることもできる。
【００７８】
さらに、最初に述べたように、本発明は、直接変更対象となる数（位置）以降の数が、相互の差を維持するように変更される、単調非減少な数列を管理するものであるから、扱われる数列は、自然数（整数）からなる順位列に限られない。例えば浮動小数点数からなる数列（区間列）の管理を行なうこともできる。この場合は、各区間の、カウンタに対応付けられていない方の端の値の計算（上記実施例で、左端順位＝左隣区間の右端順位＋１となっている）を新たに定義する必要はあるが、検索・更新の各手続は変更を要しない。なお、区間列への応用に限っていえば、上記各実施例では、各カウンタに、そのカウンタに対応付けられる区間の右端（末尾）順位を表す（計算するための）値が記憶されるようにしたが、左端（先頭）順位を表す値を記憶するようにしても、同様に探索・更新の手続を構成できる。また、各カウンタに、その値が、左端／右端のどちらの順位を表す値かを示す情報を付与すれば、カウンタごとにその値がどちらの端の順位を表すものかが異なっていてもよい。また、１つの区間に対応するカウンタを２つとして、左右両端の順位を表す値をそれぞれ記憶するか、一方のカウンタに区間長を記憶する形態で実施することもできる。この場合は、（１）、（２）の探索手続において左隣の区間に関する探索を行なわなくて済むので、探索手続が簡略になる。また、この場合は、カウンタの数は増加しても更新手続の手間の増加はわずかで済む。以上説明したように、本発明は、その主旨を逸脱しない範囲で、種々の実施態様を採ることができる。
【図面の簡単な説明】
【００７９】
【図１】実施例１の指定数値以上で最小の項のカウンタを決定する操作のフローチャート
【図２】実施例１の指定したカウンタの項の値を決定する操作のフローチャート
【図３】実施例１の数列中の１つの項を増減させる操作のフローチャート
【図４】実施例２の指定数値以上で最小の項のカウンタを決定する操作のフローチャート
【図５】実施例２の指定したカウンタの項の値を決定する操作のフローチャート
【図６】実施例２の数列中の１つの項を増減させる操作のフローチャート
【図７】実施例１の二分探索木のノードの構成
【図８】区間列［１．．３］［４．．５］［６．．９］［１０．．１５］［１６．．１６］を実現する二分探索木の構成例
【図９】区間長変更後の区間列［１．．３］［４．．５］［６．．７］［８．．１３］［１４．．１４］を実現する二分探索木の構成例
【図１０】区間追加後の区間列［１．．３］［４．．５］［６．．８］［９．．１０］［１１．．１６］［１７．．１７］を実現する二分探索木の構成例
【図１１】区間削除後の区間列［１．．３］［４．．５］［６．．８］［９．．１０］［１１．．１１］を実現する二分探索木の構成例
【図１２】ｓｐｌａｙｉｎｇの単位操作（ｒｏｔａｔｉｏｎ）と変形後のカウンタの値の計算式
【図１３】ｓｐｌａｙｉｎｇ適用後の区間列［１．．３］［４．．５］［６．．８］［９．．１０］［１１．．１６］［１７．．１７］を実現する二分探索木の構成例
【図１４】実施例２のＢ木のノードの構成
【図１５】Ｂ木の構成例とカウンタの値、及び、表される区間列と、各区間のカウンタが含まれるノード
【図１６】区間長変更後のカウンタの値、及び、表される区間列と、各区間のカウンタが含まれるノード
【図１７】実施例３のＢ’木の構成例とカウンタの値、及び、表される区間列と、各区間（または右端順位）のカウンタが含まれるノード
【図１８】本発明の実施例の典型的な機能ブロック図
【符号の説明】
【００８０】
１  階層データ構造
２  項探索手段
３  項決定手段
４  項変更手段
５  項追加手段
６  項削除手段
【図１】
0004412291.tif 000002
【図２】
0004412291.tif 000003
【図３】
0004412291.tif 000004
【図４】
0004412291.tif 000005
【図５】
0004412291.tif 000006
【図６】
0004412291.tif 000007
【図７】
0004412291.tif 000008
【図８】
0004412291.tif 000009
【図９】
0004412291.tif 000010
【図１０】
0004412291.tif 000011
【図１１】
0004412291.tif 000012
【図１２】
0004412291.tif 000013
【図１３】
0004412291.tif 000014
【図１４】
0004412291.tif 000015
【図１５】
0004412291.tif 000016
【図１６】
0004412291.tif 000017
【図１７】
0004412291.tif 000018
【図１８】
0004412291.tif 000019