(57)【特許請求の範囲】
【請求項１】
二次記憶のオフセット空間に対して、次元、ノード及び辺により超立方体を定義し、前記オフセット空間を分割構成する先頭ページから最終ページまでの各々を前記超立方体のノードに割り当てると共に、先頭ページのノードから後続ページのノードに向けてページ間をリンクする辺を設定し、前記各ページをヘッダ部とデータ部で構成し、前記ヘッダ部に前記超立方体のノードに割り当てた後続するページのリンク情報を格納し、前記二次記憶のオフセット空間を超立方体のデータ格納構造として実現する超立方体構成部と、
要求されたオフセットに基づき、前記超立方体の次元、ノード及び辺で決まるルートに従って先頭ページから要求ページに向けて各ページのリンク情報を参照しながら順次アクセスするアクセス処理部とを備え、
前記超立方体構成部は、前記ヘッダ部のリンク情報として、リンク先のページ識別子、隣接するページ及びその配下にあるページの中で獲得できる最大の連続領域の大きさからなる後続するページ中の獲得可能な最大領域サイズ、及び後続する部分超立方体の最後のオフセットである隣接するページをルートとする部分超立方体の最後のオフセットを設定した、
ことを特徴とする記憶装置。
【請求項２】
請求項１記載の記憶装置に於いて、前記超立方体構成部は、前記超立方体のノードを含む辺上に割り当てるページの数を辺の長さと定義し、該辺の長さを２以上に設定し、一辺に存在するページ数を２以上としたことを特徴とする記憶装置。
【請求項３】
請求項１乃至２記載の記憶装置に於いて、前記超立方体構成部は、予め構成した前記超立方体上にページを割り当てたオフセット空間が一杯になった場合、新たな超立方体をリンクしてオフセット空間を拡張することを特徴とする記憶装置。
【請求項４】
請求項１乃至３記載の記憶装置に於いて、前記超立方体に割り当てるページの大きさを異ならせたことを特徴とする記憶装置。
【請求項５】
請求項１乃至４記載の記憶装置に於いて、前記超立方体に割り当てるページの大きさを、最小サイズ及び最小サイズの倍数又はべき乗の倍数としたことを特徴とする記憶装置。
【請求項６】
請求項１乃至５記載の記憶装置に於いて、前記超立方体構成部は、前記超立方体の次元ｄ及びノードを含む辺上に割り当てるページ数で定義される辺の長さｅを調整することにより、各種の要求に適応することを特徴とする記憶装置。
【請求項７】
コンピュータを、
次元、ノード及び辺により超立方体を定義して、オフセット空間を分割構成する先頭ページから最終ページまでの各々を前記超立方体のノードに割り当てると共に、先頭ページのノードから後続ページのノードに向けてページ間をリンクする辺を設定する第１の手順、
前記各ページをヘッダ部とデータ部で構成し、前記ヘッダ部に前記超立方体のノードに割り当てた後続するページのリンク情報を格納する第２の手順、
前記ヘッダ部のリンク情報として、リンク先のページ識別子、隣接するページ及びその配下にあるページの中で獲得できる最大の連続領域の大きさからなる後続するページ中の獲得可能な最大領域サイズ、及び後続する部分超立方体の最後のオフセットである隣接するページをルートとする部分超立方体の最後のオフセットを設定する第３の手順として機能させるためのプログラムを記憶したコンピュータ読み取り可能な記録媒体媒体。
【請求項８】
請求項７記載の記録媒体に於いて、前記超立方体のノードを含む辺上に割り当てるページの数を辺の長さと定義し、該辺の長さを２以上に設定し、一辺に存在するページ数を２以上としたことを特徴とする記録媒体。
【請求項９】
請求項７乃至８記載の記録媒体に於いて、予め構成した前記超立方体上にページを割り当てたオフセット空間が一杯になった場合、新たな超立方体をリンクしてオフセット空間を拡張することを特徴とする記録媒体。
【請求項１０】
請求項７乃至９記載のデータ記録媒体に於いて、前記超立方体に割り当てるページの大きさを異ならせたことを特徴とする記録媒体。
【請求項１１】
請求項７乃至１０記載の記録媒体に於いて、前記超立方体に割り当てるページの大きさを、最小サイズ及び最小サイズの倍数又はべき乗の倍数としたことを特徴とする記録媒体。
【請求項１２】
請求項７乃至１１記載の記録媒体に於いて、前記超立方体の次元ｄ及びノードを含む辺上に割り当てるページ数で定義される辺の長さｅを調整することにより、各種の要求に適応することを特徴とする記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、ハードディスクドライブ等による二次記憶上のアドレス空間を構築するための記憶装置及び記憶構造に関し、特に、二次記憶上のオフセット空間を超立方体のデータ格納構造で実現する記憶装置及びデータ記憶構造に関する。
【０００２】
【従来の技術】
従来より計算機のアドレス空間は、主記憶上に実現されるアドレス空間に加え、ディスクドライブ等の外部記憶装置を用いた二次記憶上で実現されるアドレス空間を使用している。
【０００３】
以下の説明では、主記憶上のアドレス空間と区別するために、二次記憶上のアドレス空間のことをオフセット空間と呼ぶことにする。また、このオフセット空間上でのアドレスを単にオフセットと呼ぶことにする。
【０００４】
オフセット空間の例としては、代表的なオペレーティングシステム（ＯＳ）であるＵＮＩＸのファイルシステムがあげられる。オフセットは、通常のアドレス空間やＵＮＩＸファイルと同様、バイト単位で０から順に１，２、３，・・・とふられるものとする。
【０００５】
最近のデータベースには、ＣＡＤのデータや分子構造など複雑なデータや、画像、文書などのマルチメディアなどの長大データを格納することが要求されている。一方、当然に、従来からの数値や文字データ、レコードなどの比較的単純なデータや、少量のデータも扱えることが要求されている。これらの要求は、オフセット空間によって統一的に扱うことができる。このためオフセット空間は、アクセス効率が良いように実現されていることが望ましい。
【０００６】
オフセット空間が複雑で長大なデータと同時に単純で少量のデータを統一的に格納するという要求を満たす理由をより詳しく説明する。
（１）複雑なデータの格納
最近のデータベースでは、ＣＡＤデータや分子構造などの複雑なデータも扱えることが要求されている。複雑なデータは一般に木やネットワーク状の構造をとりうる。
【０００７】
これらのデータを二次記憶で実現するためには、主記憶上のデータ構造のように領域にアドレスがふられ、アドレスでデータ構造同士をリンクできることが望ましい。その際、プログラミングの容易さやスペース効率の観点から、アドレスはなるべく簡略なものが望ましい。オフセット空間はこの要求を満たす。
（２）長大データの格納
最近のデータベースでは、画像、文書などの長大データを格納することが要求されている。これらのデータはファイルとして格納されることが多い。オフセット空間は上記のように概念的にファイルを含んでおり、長大データを格納することができる。
【０００８】
具体的には、ｎバイトの長大データがあった時、その長大データをオフセット空間のオフセット０からｎ−１までに格納することによって、長大データを格納することができる。オフセット空間はこの要求を満たす。
（３）単純データの格納
オフセット空間には、複雑なデータが格納できるので、当然、従来からの文字列、数値やレコードも格納できる。しかし、単純なデータの場合、一般には量も少ない。データが１ページに収まるような場合、データベースでは、当然ながら１ページに格納する。
【０００９】
したがって、このような場合、オフセット空間も１ページ単位で実現できることが望ましい。また、従来からデータベースには、オーバフローをどう解決するかという問題がある。オフセット空間はこれにも見通しのよい解を与える。
（４）ページを意識させない
データベースでは、ページと呼ばれる固定長、例えば４ＫＢの領域に分けてデータを格納する。ページは二次記憶と主記憶間の入出力の単位である。ＯＳにおける入出力の単位も一般にこのページである。
【００１０】
図１６に示すように、ページ１００は、通常、ヘッダ部１０２とデータ部１０４に分かれる。ユーザデータを格納する場合、そのデータとは別にシステム側の情報が必要である。たとえば、ユーザデータの大きさとか、空き領域がどれくらいあるかといった情報である。これらの情報を管理情報と呼ぶことにする。
【００１１】
データ部１０４には、ユーザデータ及び場合によっては管理情報が格納される。ヘッダ部１０２には管理情報が格納される。
【００１２】
図１７は、データベースにおけるデータの格納の様子の一例を示すものである。この例ではレコードＲ１、レコードＲ２が０ページ１００−０に格納されている。次にレコードＲ３を挿入しようとした場合、もし、０ページ１００−０に入らないのであれば、新しい１ページ１００−１が獲得され、レコードＲ３は１ページ１００−１に格納される。
【００１３】
データベースのシステムを構築する場合、一般に、このページを意識してプログラミングが行われる。例えば、図１７のレコードＲ１が更新されることを考える。もしレコードＲ１の長さが増え、しかも０ページ１００−０に入り切らなくなった場合、解決策の１つとしては、図１８のように、新たに２ページ１００−２を確保し、更新後のレコードＲ１のある部分、あるいは、レコードＲ１全体を移すという手段がある。
【００１４】
図１８では、レコードＲ１は更新後に二つの部分レコードＲ１１、レコードＲ１２になり、レコードＲ１１は０ページ１０４−０に、レコードＲ１２は２ページ１０４−２に格納された場合を示す。このように一まとまりのデータが１つのページに収まらなくなる状態をオーバフローと呼ぶ。
【００１５】
このオーバフローはページを意識する一例である。オフセット空間を用いた場合、一般には、オーバフローやページを意識することなく、データを扱うことができる。ただし、実現の仕方にもよるが、領域の連続性の問題があるので、コピーしなければならないなどの状況は生じる。図１９は、図１８のオーバフローしたレコードがオフセット０〜７９９９のオフセット空間に格納された様子を示す。
【００１６】
【従来技術】
従来、オフセット空間の代表的な例としてはＵＮＩＸ等のＯＳにおけるファイルシステムがある。ＵＮＩＸのファイルシステムの特徴は以下の通りである。
（１）オフセット空間
ＵＮＩＸのファイルはオフセット空間と考えられる。ＵＮＩＸファイルのデータには、各バイトに先頭から０、１、２、・・・とオフセットがふられている。（２）管理ページを別に管理
ＵＮＩＸでは、ユーザデータと管理情報を別々のページで管理している。この管理情報を格納するページを管理ページと呼ぶことにする。
（３）管理ページは木構造
管理ページはバランスしていない木構造として実現されている。
（４）領域管理の機能がない
主記憶上のアドレス空間では、領域管理の機能が提供されている。具体的には、ＵＮＩＸでは、malloc（），free（）という関数がサポートされていて、大きさがsizeの領域を確保したい場合、
address ＝  malloc(area) ；
と、この関数を呼ぶことによって、システム側が主記憶上にある連続領域を確保し、そのアドレスを「address 」として返す。
【００１７】
また、
free(address)
とすることによって、この領域は開放される。「address 」に対応する領域を開放しない限り、この領域がmalloc（）で再度渡されることはない。しかし、ＵＮＩＸのオフセット空間であるファイルには、この主記憶空間の領域管理機能はない。
【００１８】
ＵＮＩＸにあるのは、あるオフセットからｎバイトの領域にユーザが指定した主記憶上のｎバイトの連続領域（これを「ユーザバッファ」と呼ぶ）の内容を書き込む処理や、逆にあるオフセットからｎバイトの内容をユーザが指定したｎバイトのユーザバッファに読み込むといった処理である。ただし、この領域管理はデータベースなどではレコードの領域などに関して行われている。
（５）バッファへのコピー
二次記憶上にあるページは、システムが管理するバッファへコピーされるが、更にそこから主記憶上のユーザバッファへコピーされる。これは、ページにまたがった領域の連続性が保証されないためである。
【００１９】
【発明が解決しようとしている問題点】
しかしながら、このような従来システムにおいてアクセス効率のよいオフセット空間を実現するためには次のような課題が残されている。
（１）データアクセスの効率性
オフセット空間を実現する場合、まず最も単純な方法として、オフセット空間を構成するページを線状にリンクすることが考えられる。
【００２０】
図２０に、オフセット空間を構成するページを線状にリンクする例を示す。この例では、最初の０ページ１００−０にオフセット０〜３９９９のデータが格納され、次の１ページ１００−１にオフセット４０００〜７９９９のデータが格納され、最後の２ページ１００−２にオフセット８０００〜１１９９９のデータが格納されている。
【００２１】
このように、線状にリンクを張った場合、後ろのデータにアクセスするには途中のページを辿らなければならず、入出力の回数、即ち入出力のコストがかかる。例えば、図２０において、オフセットが１００００の領域にアクセスしようとすると、まず０ページ１００−０にアクセスし、次に１ページ１００−１にアクセスし、それから２ページ１００−２にアクセスしなければならない。即ち、３回の入力が必要になる。
【００２２】
図２１は、オフセット空間を構成するページを木状にリンクする例を示す。この場合、先頭のページには後ろに存在する全てのベージのリンク情報が入っている。このように木状にリンクすると、オフセット１００００の領域にアクセスする場合、まず先頭の０ページ１００−０にアクセスした後に、そのリンク情報Ｌ０２によって２ページ１００−２にすぐアクセスできるので、２回の入力で済む。ＵＮＩＸのファイルシステムは、バランスしていない木状のリンクでオフセット空間を実現している。
【００２３】
（２）ユーザデータと管理情報の共存
ＵＮＩＸのファイルシステムでは、管理情報とユーザデータは別ページに格納されている。このため、あるユーザデータにアクセスする場合、まず管理ページにアクセスし、そのあとにユーザページにアクセスすることになる。即ち、少なくとも２回の入力が必要になる。管理情報とユーザデータが同じページに格納されていれば、この問題が解決される。
【００２４】
図２０及び図２１は、管理情報とユーザデータを同じページに格納した例になっており、これは一般にデータベースでとられる方式である。
【００２５】
（３）拡張できるオフセット空間の実現
ユーザデータは最初は少量だが、後で追加、更新されてより大きくなっていくことが多い。即ち、オフセット空間は拡張できることが望ましい。また、もしオフセット空間の大きさの最大値が小さいと、それ以上追加や更新ができなくなってしまう。
【００２６】
したがって、最大値の制限もなるべくゆるやかなことが望ましい。オフセット空間を大きくする方法としては、例えば図２１の場合、木が１段だが、この構造を複数段にすることにより実現できる。ＵＮＩＸでも段数を増加して拡張する方式がとられている。
【００２７】
（４）ユーザデータと管理情報のバランス
比較的少量のデータの場合、先頭の０ページになるべくデータを格納することが、アクセス効率の面から望ましい。管理情報が多いと、ユーザデータが圧迫されて先頭の０ページに入るべきデータが追い出され、アクセス効率が悪くなるからである。
【００２８】
一方、長大データの場合は、全体の入出力回数が問題となるため、逆に先頭の０ページや木構造の上位のページには、なるべく管理情報を入れておくことが望ましい。すなわち、データ量によって、ユーザデータと管理情報のバランスを調節できることが望ましい。
【００２９】
（５）連続領域と不連続領域の実現
長大データのような場合、例えば、１００００バイトのデータを格納する場合、図２１で、０ページ１００−０のオフセット０から２ページ１００−２の９９９９までに、このデータを格納すればよい。
【００３０】
しかし、逆にオフセット空間に格納したこの１００００バイトのデータにアクセスする場合、オフセット０から３９９９までは同じ０ページ１００−０に格納されているので、連続しているが、オフセット４０００から７９９９まで、及び８０００から９９９９まではそれぞれ１ページ１００−１、２ページ１００−２という別ページに格納されるため、連続してはアクセスできない。
【００３１】
そこで、このようにデータが複数ページに分かれてオフセット空間に格納されている場合、一般に１００００バイトのデータが入るユーザが用意したユーザバッファの先頭から順に、オフセット０〜３９９９、オフセット４０００〜７９９９、オフセット８０００〜９９９９のデータを順次コピーすることによって、連続した情報としてアクセスできるようにする。
【００３２】
長大データを連続してアクセスするために、一般に、ユーザバッファにコピーするこの方法がとられている。しかし、この場合、コピーするコストがかかる。
【００３３】
一方、たとえば１００バイトといった小さいデータの場合は、１つのページ上に、１００バイトの領域を連続した領域としてとることが可能である。この場合は、ユーザバッファにコピーする必要はなく、連続した領域として直接アクセスできる。
【００３４】
アクセス効率の良いオフセット空間を実現するためには、この両者が実現できることが望ましい。また、連続領域の大きさの最大値も大きい方が望ましい。
【００３５】
本発明は、このようなオフセット空間に要求される各種の条件を満たしてアクセス効率の良いオフセット空間を実現するための記憶装置及び記憶構造を提供することを目的とする。
【００３６】
【課題を解決するための手段】
図１は本発明の原理説明図である。
（超立方体構造）
本発明の記憶装置は、図１（Ａ）のように、二次記憶のオフセット空間３０を、超立方体（ハイパー・キューブ）３４のデータ格納構造として実現する超立方体構成部１８と、超立方体３４のデータ構造を利用して、要求されたオフセット空間３０の領域に高速にアクセスするアクセス処理部２０とを備えたことを特徴とする。
【００３７】
超立方体構成部１８は、図１（Ｂ）のように、次元ｄ、ノード（頂点）及び辺により超立方体３４を定義し、オフセット空間を分割構成する先頭ページ（トップページ）３２−０から最終ページ３２−ｎまでの各々を、超立方体３４のノードに割り当てると共に、先頭ページ３２−０のノードから後続ページのノードに向けてページ間をリンクする辺を設定する。
【００３８】
アクセス処理部２０は、要求されたオフセットとサイズ（バイト数）に基づき、超立方体３４の次元ｄ、ノード及び辺で決まるルートに従って要求ページにアクセスする。
【００３９】
このように本発明は、オフセット空間を超立方体状に構成することにより、効率の良いデータアクセスを実現する。
【００４０】
ここで、辺については、超立方体の通常の辺を全て用いるのではなく、超立方体３４のように、ページを割り当てた状態で木を構成する部分の辺のみを用いる。これは、データアクセスのために全ての辺が必要なわけではなく、ノードを含む木の部分があれば、アクセス効率を損ねることなく、実現できるためである。
【００４１】
図１（Ｂ）の超立方体３４のノードが、オフセット空間１６のページから構成した図１（Ａ）の０ページ３２−０〜１５ページ３２−１５に対応する。超立方体の各ノードにふられた番号がページ番号である。データは番号の小さい方から順に格納される。
【００４２】
例えば１ページのデータ部４ＫＢ（４０９６バイト）とすると、オフセット０〜３９９９が０ページ３２−０に、オフセット４０００〜７９９９が１ページ３２−１に、オフセット８０００〜１１９９９が２ページ３２−２に，・・・という具合に格納される。
【００４３】
ここでデータが０ページ３２−０に収まる間は、０ページ３２−０のみが存在する。０ページ３２−１にデータ収まらなくなると、超立方体構成部１８は１ページ３２−１を確保し、オフセット空間３０が拡張される。以降、同様に、２ページ３２−２、３ページ３２−３，・・・ｎページ３２−ｎの順に拡張されていく。
【００４４】
超立方体３４には、ノード数が増えても一つのノードから出る辺の数がそれほど増えないという性質がある。ここで例えばｎ次元の超立方体の場合、ノードの数は２のｎ乗になるが、１つのノードから出る辺の数は高々ｎであり、全体の辺の数は、木であることを考慮すると、ノード数より１つ少ない２のｎ乗マイナス１（＝２n −１）となる。
【００４５】
また、元のノードから最も遠いノードまでの距離、即ち辿る辺の数がそれほど大きくならないという好ましい性質がある。
【００４６】
このため、超立方体の構造は並列計算機などでも使われている。並列計算機でも一つのノード、即ちプロセッサからでる通信線の数は増やしたくないが、通信コストを少なくするため、ノード間の平均距離も短くしたいという要求があり、超立方体がバランスがとれた構造になっている。本発明は、このような超立方体の性質を用いて距離と辺の数とのバランスをとり、アクセス効率の良いオフセット空間を実現する。
（ユーザデータと管理情報の共存）
超立方体構成部１８は、図１（Ｄ）のように、各ページをヘッダ部３６とデータ部３８で構成し、ヘッダ部３６に超立方体のノードに割り当てた後続ページへのリンク情報を格納する。このため、アクセス処理部２０は、先頭ページから要求ページに向けて各ページのリンク情報を参照しながら順次アクセスする。
【００４７】
超立方体構成部１８は、ヘッダ部３６のリンク情報として、リンク先のページ識別子４６、後続するページ中の獲得可能な最大領域サイズ４８、及び後続する部分超立方体の最後のオフセット５０を設定する。
【００４８】
このためアクセス処理部２０は、自己のページ領域に要求オフセットが含まれる場合は、超立方体のルート探索を終了して該当する領域のデータをアクセスする。また自己のページ領域に要求オフセットが含まれない場合は、要求オフセットが含まれる後続ルートのページを選択してアクセスする。
【００４９】
このように本発明は、基本的にユーザデータと管理情報を同じページ入れる構造をとっている。これはアクセス効率を考慮してユーザデータと管理情報の共存を実現するためである。更に本発明は、ユーザデータと管理情報の割合をどの程度にするかカスタマイズできるようにしている。極端な場合、トップページに関しては管理情報だけにすることも可能である。
（次元と辺の長さによるカスタマイズ）
超立方体構成部１８は、図１（Ｃ）のように、超立方体３４のノードを含む辺上に割り当てるページの数を辺の長さｅと定義した場合、辺の長さｅを３以上に設定し、一辺に存在するページ数を３以上とすることができる。尚、図１（Ｂ）は辺の長さが２の場合である。
【００５０】
超立方体構成部１８は、超立方体３４の次元ｄ、ノードを含む辺の長さｅを調整することにより、各種の要求に適応したオフセット空間を実現する。
【００５１】
通常言われている超立方体では、１つの辺には２つのノードがのるが、本発明では、１つの辺に３つ以上のノードがのる構成を更に考えている。ここで辺にｅ個のノードがのっている場合、その辺の長さはｅであるということにする。
【００５２】
図１（Ｃ）のように、辺に３個のページが並ぶ場合、辺の長さｅは３である。また、図１（Ｂ）の場合は辺の長さｅは２である。本発明では、次元ｄと辺の長さｅを調節できるようにしている。
【００５３】
ここで、辺に乗っているページは０ページに近い方の頂点のノードのページから１回の入力でアクセスできることを意味している。例えば、図１（Ｂ）の０ページから、１ページ又は２ページにアクセスするには、ともに１回の入力で済む。これは０ページに、同じ辺にある１ページと２ページへのリンク情報を格納するためである。
【００５４】
更に詳しく説明すると次のようになる。いま図１（Ｂ）のように、辺に２つのノードがのっている場合、例えばノード４とノード６の間の辺に注目すると、その辺のノードのうち、ノード０に近いノード４からその辺の別のノードであるノード６へアクセスするためのリンク情報は１つ必要である。ノード６では、ノード０に戻る方向のノード４に関するリンク情報は必要なく、ノード７に関するリンク情報だけでよい。
【００５５】
１つの辺上にｅ＝３個のっている場合、例えば図１（Ｃ）のノード１８、１９、２０がのっている辺に注目すると、その辺のノード０に近い端のノード１８にノード１９，２０の各々に向かうための（ｅ−１）個、即ち２個のリンク情報が必要になる。逆にノード１９、２０に関してはノード１８に戻る方向のリンク情報は必要ない。
【００５６】
このように、辺の長さｅを３以上にできるようにし、次元ｄと辺の長さｅを調節できることにより、オフセット空間に対するいろいろな要求に対応することができる。例えば、次のような相異なる要求に対応できる。
【００５７】
▲１▼データ量が１ページに収まることが最初からわかっており、リンクは必要なく、トップページになるべくたくさんのユーザデータを入れたい。
【００５８】
▲２▼将来データ量が多くなる可能性があり、そのためのリンクも必要だが、最初少量なので、トップページにもデータを入れたい。
【００５９】
▲３▼データ量が多いので、トップページはリンク情報ばかりでよいが、とにかく、リンクを辿る手間を少なくして、アクセス効率を高めたい。
【００６０】
（空間の拡張）
超立方体構成部１８は、予め構成した超立方体３４上にページを割り当てたオフセット空間が一杯になった場合、新たな超立方体をリンクしてオフセット空間を拡張することができる。
【００６１】
本発明では、次元ｄ及び辺の長さｅで指定された超立方体までページを増してオフセット空間を大きくしていくことがまず可能である。最初からこれらのページをとっておく必要はない。例えば、図１（Ｂ）の例では、０ページから始まり１５ページまで拡張できる。しかし、１５ページまでくると満杯の状態になる。
【００６２】
もし、これ以上拡張できないとすると、データ量がどの程度になるかわからないような場合、次元ｄや辺の長さｅを必要以上に大きく指定しなければならない等の状況が生じ、不便な場合がある。そこで、最初に構成したオフセット空間が一杯になった場合、新たな超立方体をリンクしてオフセット空間を拡張できるようにする。
【００６３】
ただし、初期設定した超立方体のオフセット空間を越える拡張は、アクセス効率が悪くなるので多用すべきでなく、データの大きさが予想される時は、きちんと次元ｄや辺の長さｅを指定すべきである。
（連続領域と不連続領域の実現）
超立方体構成部１８は、超立方体３４に割り当てるページの大きさを異ならせてもよい。例えば超立方体３４に割り当てるページの大きさを、最小サイズ及び最小サイズの倍数又はべき乗の倍数とする。例えば最小サイズを４ＫＢとすると、２のべき乗の倍数となる８ＫＢ，１６ＫＢ，３２ＫＢ，・・・のページサイズとする。
【００６４】
ページの大きさを例えば４ＫＢと固定しても、二次記憶上ではデータは一般に不連続になる。しかし、ユーザがバッファ上に連続領域を用意すれば、ページからバッファにコピーすることによって連続領域としてアクセスできる。しかし、コピーするコストはかかる。
【００６５】
そこで本発明は、８ＫＢ，１６ＫＢ，３２ＫＢ，・・・といったページサイズを持つことで、４ＫＢで収まらないデータを連続領域としてコピーすることなく、直接アクセスすることが可能である。
【００６６】
また本発明は、データ記憶構造そのものを提供するものであり、外部記憶装置により構築された２次記憶のオフセット空間と、このオフセット空間を、超立方体のデータ格納構造として実現する超立方体構成部１８とを備える。この超立方体構成部１８の詳細は、記憶装置の場合と同じである。
【００６７】
【発明の実施の形態】
＜目  次＞
１．一辺にページが２個並ぶ超立方体データ格納構造
２．一辺にページが３個以上並ぶ超立方体データ格納構造
３．次元と辺の長さによるカスタマイズ
４．オフセット空間の拡張と連続領域の実現
１．一辺にページが２個並ぶ超立方体データ格納構造
図２は、本発明の超立方体データ構造が適用される一般的な計算機を例にとったハードウェア構成のブロック図である。
【００６８】
図２において、本発明の記憶装置は、中央処理装置１０、主記憶装置１２、２次記憶装置として使用するディスク装置１４、更に本発明の超立方体データ格納構造を実現する超立方体データ構造装置１６を備え、これらをバス２２で接続する。ディスク装置１４としては、ハードディスクドライブ以外に光ディスクドライブ、半導体メモリ装置など適宜の２次記憶装置が使用できる。
【００６９】
超立方体データ構造装置１６には、超立方体構成部１８とアクセス処理部２０が設けられる。超立方体構成部１８は、２次記憶のオフセット空間を超立方体のデータ格納構造として実現する。また、アクセス処理部２０は、超立方体のデータ構造を利用して、中央処理装置１０から要求されたオフセット空間の領域に高速にアクセスする。
【００７０】
図３は、図２のハードウェア構成を前提とした本発明の機能構成のブロック図である。
【００７１】
図３において、図２のディスク装置１４で実現される２次記憶上のオフセット空間３０は、例えば０ページ３２−０〜１５ページ３２−１５の１６ページで構成されている。ここで、オフセット空間３０は、中央処理装置１０の論理空間を主記憶装置１２の主記憶空間と共に構成している。
【００７２】
具体的には、図４に示すように中央処理装置１０の論理空間（ＣＰＵ空間２６）の上位アドレス側に主記憶装置１２の主記憶空間２８が割り当てられ、主記憶空間２８に続いて２次記憶上のオフセット空間３０が割り当てられている。
【００７３】
超立方体データ構造装置１６に設けた超立方体構成部１８は、例えば図５のような超立方体３４のデータ格納構造を実現する。この超立方体３４は、図３のようにオフセット空間１６を１６個のページ３２−０〜３２−１５で構成する場合に適用される。
【００７４】
超立方体３４によるデータ格納構造は、超立方体の次元ｄと一辺に存在するページ数で定義される辺の長さｅの指定で構造が決められる。図５の超立方体３４は、次元ｄが２次元で、辺の長さｅが２、すなわち一つの辺に２個のページが並ぶ場合である。
【００７５】
また、超立方体の頂点となるノードがオフセット空間３０のページに対応しており、各ノードに図３の０ページ３２−０〜１５ページ３２−１５に対応したページを示すノード番号０〜１５を割り当てている。
【００７６】
図６は、図５の超立方体３４のデータ格納構造に適用される図３のオフセット空間３０のページのデータ構造であり、０ページとなるトップページ３２−０を例にとっている。このページのデータ構造は、ヘッダ部３６とデータ部３８で構成される。
【００７７】
ヘッダ部３６には、［ｈｅａｄｅｒ０］で示すヘッダ固定領域４０、「ｎｏＮｅｘｔ」で示される後続ページ数格納領域４２、更にｎｅｘｔ［０］〜ｎｅｘｔ［３］の配列で示される１ページリンク情報４４−１，２ページリンク情報４４−２，４ページリンク情報４４−３及び８ページリンク情報４４−４が格納される。尚、「ｎｏＮｅｘｔ」は、「ｎｏ．  ｏｆ  ｎｅｘｔ」の略である。
【００７８】
データ部３８には、ユーザデータが一回のアクセス単位に格納され、例えば「ａｒｅａ１」のデータ領域５２−１と「ａｒｅａ２」のデータ領域５２−２が使用されている。
【００７９】
次にヘッダ部３６の各管理情報を詳細に説明する。まずヘッダ部３６のページ毎のリンク情報を説明する。図６のトップページ３２−０の場合、図５の超立方体３４から明らかなように、トップページから辿ることのできる隣接するページは１ページ、２ページ、４ページ、８ページの４つがあることから、図６のヘッダ部３６の配列ｎｅｘｔ［０］〜配列ｎｅｘｔ［３］には、それぞれ１ページリンク情報４４−１、２ページリンク情報４４−２、４ページリンク情報４４−３、及び８ページリンク情報４４−４のそれぞれが格納される。
【００８０】
これらの各ページリンク情報４４−１〜４４−４は、図７にリンク情報４４−ｉとして取り出して示すデータ構造をもつ。即ち、リンク情報４４−ｉは、「ｐａｇｅＩｄ」で示されたページＩＤ４６、「ｍａｘＡｒｅａＳｉｚｅ」で示されたマックスエリアサイズ４８、更に「ｌａｓｔＯｆｆｓｅｔ」で示されたラストオフセット５０を格納している。
【００８１】
このリンク情報４４−ｉは、現在ページからアクセスする別のページに関する情報のことである。このリンク情報のうち、ページＩＤ４６には、隣接するページのページ識別子が格納される。このページ識別子４６によって、隣接する次のページにアクセスすることができる。
【００８２】
通常、リンク情報というとページ識別子のような情報を指すことが多いが、本発明にあっては、このページ識別子に加え、更にマックスエリアサイズ４８やラストオフセット５０などを含む広い意味で用いている。
【００８３】
次のマックスエリアサイズ４８には、隣接するページ、及びその配下にあるページの中で獲得できる最大の連続領域の大きさが「配下ページ中の獲得可能な最大領域サイズ」として格納される。ここで配下とは、例えば図５の超立方体３４において、隣接するページを４ページとすると、配下のページは５ページ、６ページ、７ページとなる。また７ページであれば、配下のページはない。
【００８４】
マックスエリアサイズ４８は、ページ内に連続領域を実現するために必要な情報であり、長大データのようにページ間に分けられた不連続なデータをつなぎ合わせてバッファ上にデータを構成するような場合には必要無い。
【００８５】
ここで本発明にあっては、部分超立方体という用語を導入する。図５の超立方体３４における４ページ、５ページ、６ページ、７ページの部分について別の見方をすると、これらのページにより同様に超立方体を構成している。この様に超立方体３４の中の部分的な超立方体を部分超立方体と呼ぶことにする。例えば、４ページ、５ページ、６ページ、７ページから成る部分超立方体は４ページをルートとする部分超立方体と呼ぶことにする。
【００８６】
このため７ページだけから成る部分超立方体も考えられる。更に、０ページをルートとする全体的な超立方体３４も特別な部分超立方体と考えられる。この様な部分超立方体についても次元を考えることができる。４ページをルートとする部分超立方体は２次元、ページ７をルートとする部分超立方体の次元は０次元、０ページをルートとする部分超立方体の次元は４次元である。
【００８７】
また、図５の超立方体３４におけるページ番号を付けた各ノードの次元を、以下の説明で使うために便宜的に定義しておく。即ち、あるノードの次元をそのノードをルートとする部分超立方体の次元に等しいものとして定義する。例えば、４ページのノードは２次元、７ページのノードは０次元である。
【００８８】
部分超立方体という言葉を使うと、図７のマックスエリアサイズ４８には隣接するページをルートとする超立方体の中で獲得できる最大の連続領域の大きさが格納されるということができる。このマックスエリアサイズ４８の値を見ることで、後続のページにアクセスする前に現在のページのアクセスで新たに領域が獲得できるかどうかを判定することができる。
【００８９】
次のラストオフセット５０には、隣接するページをルートとする部分超立方体の最後のオフセットが格納される。このラストオフセット５０の値によって、あるオフセットをもった領域にアクセスする場合、どのページにアクセスすれば良いかが分る。
【００９０】
このラストオフセット５０の値の別の設定方式としては、長大データのように不連続な領域をつなげ合わせる場合、ページの大きさを例えば４ＫＢと固定し、隣接するページのラストオフセット５０に、その隣接するノードをルートとする部分超立方体でとれる最大のオフセットの値を設定することも考えられる。
【００９１】
再び図６を参照するに、ヘッダ部３６の「ｎｏＮｅｘｔ」で示された後続ページ数格納領域４２には、トップページから辿ることのできるページ数、例えば図５の超立方体３４の場合には、「４」が格納される。
【００９２】
またヘッダ部３６の先頭の「ｈｅａｄｅｒ０」で示されたヘッダ固定領域４０には、それ以外の管理情報が格納される。この管理情報としては、例えば０ページでどれだけのスペースが連続領域のために空きで残っているかというような管理情報を格納する。
【００９３】
ヘッダ部３６に続いて設けられたデータ部３８には、ユーザデータを格納するためのデータ領域が上から順にとられる。この例では、「ａｒｅａ１」と「ａｒｅａ２」で示す２つのデータ領域５２−１，５２−２がとられている。この場合データ領域５２−１のオフセットは０、長さは４Ｂである。またデータ領域５２−２のオフセットは４、長さは８Ｂである。
【００９４】
図６は、図３のトップページ３２−０のデータ構造を例にとるものであったが、残りの１ページ〜１５ページのデータ構造も基本的には図６のトップページと同様である。トップページと異なる点は、ヘッダ部３６の「ｎｏＮｅｘｔ」で示された後続ページ数格納領域４２が、そのページから更に辿れるページの数を格納することとなり、トップページより数が少なくなる点である。
【００９５】
例えば、後続ページ数格納領域４２には、１ページや１５ページなどでは「０」が格納され、２ページや６ページなどでは「１」が格納され、４ページや１２ページでは「２」が格納され、更に８ページでは「３」が格納される。
【００９６】
図８は、図３のオフセット空間３０のデータ構造の内容を図５の超立方体３４に対応したルートのリンクで表わして、一部を具体的に示している。即ち図６に示した０ページ３２−０に格納している４つのページリンク情報に対応して１ページ３２−１、２ページ３２−２、４ページ３２−４及び８ページ３２−８のそれぞれが配置される。
【００９７】
この場合、１ページ３２−１は後続するページがないことから「ｈｅａｄｅｒ１」のヘッダ固定領域のみがヘッダ部に設けられ、それ以外はすべてデータ部となっている。
【００９８】
２ページ３２−２、４ページ３２−４及び８ページ３２−８のそれぞれについては、後続するページが存在する事から後続ページ数格納領域４２に後続ページ数「１」「２」「３」がそれぞれ格納され、更に後続ページ数に対応した数のページリンク情報が配列ｎｅｘｔ［ｉ］により格納されている。
【００９９】
更に２ページ３２−２には次の３ページ３２−３がリンクし、４ページ３２−４には次の５ページ３２−５及び６ページ３２−６のそれぞれがリンクし、６ページ３２−６は更に７ページ３２−７にリンクしている。
【０１００】
また８ページ３２−８は次の９ページ、１０ページ、１２ページにリンクしている。尚、説明の都合上ページのデータ構造は８ページ３２−８及び６ページ３２−６までを示している。
【０１０１】
ここで、オフセット空間を使用してデータベースを構築する場合、データベースでは入出力はコストがかかるので入出力回数を減らすことが重要である。本発明にあっては、オフセット空間での入出力を考えるにあたって「距離」という用語を導入する。即ち、オフセット空間に於いて、各ページにアクセスするために必要な入力回数を各ページまでの距離、あるいは各ページの距離と呼ぶことにする。
【０１０２】
図９は、図５の超立方体３４のデータ格納構造を用いて０ページから１５ページを格納した場合の各ページまでの距離、即ち各ページにアクセスするために要する入出力回数を各ノードに１〜５の数値で示して表わしている。
【０１０３】
例えば、図５の０ページにアクセスするためには、１回の入力が必要であるので、距離は図９のように「１」である。また図５の１ページにアクセスするためには、まず０ページにアクセスし、それから１ページにアクセスするため２回の入力が必要であるので距離は図９に示すように「２」である。同様に図５の３ページでは図９のように距離は「３」、図５の１５ページでは図９のように距離は「５」となる。
【０１０４】
ここで、ノードの距離という言葉で定義したのは、入出力回数といっても同じであるが、図９から分かるように幾何学的にイメージし易くするためである。
【０１０５】
この距離という言葉を用いると、オフセット空間の平均入出力回数は各ページまでの平均距離として求める事ができる。図５の超立方体３４の場合、図９のような距離をもつ事からこの場合の平均距離は次式で与えられる。
（１×１＋２×４＋３×６＋４×４＋５×１）／１６＝３
一方、図２０の従来構造に示したように各ページを線状にリンクしてオフセット空間を実現した場合の平均距離は次式で与えられる。
（１＋２＋３＋Ｐ４＋・・・＋１６）／１６＝８．５
更に図２１の従来構造のように各ページを一段の木状にリンクしてオフセット空間を実現した場合の平均距離は次式で与えられる。
（１×１＋２×１５）／１６＝１．９４
この場合トップページに格納されるリンク情報の数は１５となる。
【０１０６】
図７に示した本発明の超立方体の場合は、ページ内に設けるリンク情報の最大数は、トップページの４が最大である。このように本発明の超立方体によって、オフセット空間の平均距離とリンク情報の数のバランスを取ることができる。
【０１０７】
図１０は、図３の超立方体データ構造装置１６に設けているアクセス処理部２０による超立方体データ格納構造を利用したオフセット空間のアクセス処理のフローチャートである。
【０１０８】
ステップＳ１で中央処理装置１０より論理アドレス及びサイズをパラメータに含むアクセスコマンド、具体的にはリードコマンドやライトコマンドを受領すると、次のステップＳ２で論理アドレスをオフセットアドレスに変換する。このオフセットアドレスへの変換は、図４に示したように論理空間２６に対する主記憶空間２８が分かっていることから主記憶空間２８のサイズアドレスを引く事でオフセット空間３０のアドレスとなるオフセットを求めることができる。
【０１０９】
続いてステップＳ３に進み、超立方体データ構造上の０ページから順番に各ページのヘッダ部に設けているページリンク情報を参照しながら要求ページにアクセスする。
【０１１０】
最終的にステップＳ４で要求ページのオフセットアドレスからサイズ分のデータをアクセスして処理を終了する。この場合、リードアクセスであれば要求ページのオフセットアドレスからサイズ分のデータをリードして要求元に転送する。ライトアクセスであれば、要求ページのオフセットアドレスからサイズ分のデータに対する書き込みを行う。
【０１１１】
尚、詳細は割愛するが、本発明の自明な適用実施形態としては、１つのオフセット空間で１つのファイルを実現することが考えられる。この場合は、２次記憶上に複数のオフセット空間が実現される。
【０１１２】
また、データベースシステムの１つのページを１つのオフセット空間で実現することも考えられる。この場合も２次記憶上に複数のオフセット空間が実現される。
２．１辺にページが３個以上並ぶ超立方体データ格納構造
図１１は、本発明の超立方体データ格納構造の他の実施形態であり、この実施形態にあっては、図５の１辺に２個のページが並べる超立方体３４を拡張し、超立方体３４の１辺に３個以上のページを並べるようにしたことを特徴とする。
【０１１３】
即ち、図１１の超立方体３４にあっては、次元ｄは４であるが、１辺に並べるページの数を３個、即ち辺の長さｅを３と指定することで超立方体３４を構成している。この場合、オフセット空間に格納することのできるページ数は最大で８１ページとなる。
【０１１４】
このように超立方体３４の辺に３個以上のページを乗せることにより、各ページに設けるリンク情報は増えてしまうが、ページ間の平均距離を減らすことができる。
【０１１５】
図１２は、図１１の超立方体３４のデータ格納構造を実現するためのページデータ構造であり、トップページ６０−０を例にとっている。この場合もページのデータ構造はヘッダ部３６とデータ部３８で構成される。ヘッダ部３６には図６と同様、「ｈｅａｄｅｒ１」で示されるヘッダ固定領域４０、「ｎｏＮｅｘｔ」で示される後続ページ数格納領域４２が設けられる。
【０１１６】
更に０ページにつながる次のページのリンク情報が格納されるが、この実施形態にあっては１辺に３個のページを割り当てているため、図６の場合の４つのページリンク情報の２倍となる８つのページ情報が格納されている。
【０１１７】
即ち図１１の超立方体３４の０ページから辿れる隣接するページは、１ページ、２ページ、３ページ、６ページ、９ページ、１８ページ、２７ページ、５４ページの８ページである。この内、同一辺上には１ページと２ページ、３ページと６ページ、９ページと１８ページ、２７ページと５４ページのそれぞれが存在する。
【０１１８】
図１３は、図１１の１辺に３個ページを並べた場合の超立方体３４における各ページまでの入力回数となる距離を１〜５の数字で表わしている。この場合の各ページまでの平均距離は次式で与えられる。
（１×１＋２×８＋３×２４＋４×３２＋５×１６）／８１＝３．６６・・・
即ち、各ページにアクセスするための平均入力回数は、ページが全体で８１ページあるにもかかわらず、約３．６６回となっている。またページに格納されるリンク情報の数もトップページの８個が最大である。
【０１１９】
これに対し図２０の従来例のように、８１ページを線状にリンクしてオフセット空間を実現した場合の平均距離は次式となる。
（１＋２＋３＋４＋・・・＋８１）／８１＝４１
また図２１のように、８１ページを１段の木状にリンクしてオフセット空間を実現した場合の平均距離は次式で与えられる。
（１×１＋２×８０）／８１＝１．９９
ここで図２１の場合の平均距離が約１．９９回と最小になるが、この場合にトップページに格納されるリンク情報の数は８０となり、本発明におけるトップページのリンク情報の数が高々８であるのに比べるとリンク情報の数が格段に多い。
３．次元と辺の長さによるカスタマイズ
本発明の超立方体データ格納構造にあっては、オフセット空間のアクセスにおいて要求されるユーザによる各種の条件に適合したカスタマイズのための調整が可能である。このカスタマイズを説明する前に、オフセット空間が何バイトの空間からなるかを示すオフセット空間の大きさを説明する。
【０１２０】
本発明による超立方体データ格納構造を用いたオフセット空間のスペースサイズは、ページの大きさが固定であれば、超立方体の次元ｄと辺の長さｅの指定で決まる。ページの大きさは可変でも構わないが、説明を簡単にするため、ここではページの大きさは固定でｐバイトとする。また次元をｄ、辺の長さをｅ、この場合のオフセット空間の大きさをＳ（ｄ，ｅ）で表わすことにする。
【０１２１】
また図６及び図１２に示した各ページのヘッダ部３６におけるヘッダ固定領域４０の大きさをｈバイト、後続ページとなる子供がいる場合に作られる後続ページ数格納領域４２をａバイト、同じく子供がいる場合に作られる配列ｎｅｘｔ［］のページリンク情報の１つの大きさをｂバイトとする。
【０１２２】
更に次元ｉのノードの個数をＮＣ（ｉ，ｄ，ｅ）で表わし、この次元ｉのノードのスペースの大きさをノードスペースＮＳ（ｉ，ｅ）で表わす。このノードスペースＮＳ（ｉ，ｅ）は、次元ｄには依存しない。このように定義した場合、オフセット空間のスペースサイズＳ（ｄ，ｅ）は次式で与えられる。
S(d,e)=Sum[i=0,d]NS(i,e)＊NC(i,d,e)                           （１）
但し、S(d,e)：オフセット空間サイズ
ｐ    ：ページサイズ
ｄ    ：次元
ｅ    ：辺の長さ
ｈ    ：ヘッダ固定領域のバイト数
ａ    ：noNextのバイト数
ｂ    ：配列nextのバイト数
ここで、（１）式におけるSum[i=0,d]は、その関数をｆ（ｉ）とすると
Sum[i=0,d]f(i)＝f(0)＋f(1)＋・・・＋f(n)
を表わしている。また、このスペースサイズＳ（ｄ，ｅ）をもつオフセット空間を構築する超立方体の次元ｉのノード個数ＮＣ（ｉ，ｄ，ｅ）は次式で与えられる。
【０１２３】
【数１】
0003859110.tif 000002
【０１２４】
ここで、（２）式の右辺２段目のｅ＾(d-i-1) は、ｅの(d-i-1) 乗を意味する。
【０１２５】
更に次元ｉのノードスペースＮＳ（ｉ，ｅ）は次式で与えられる。
【０１２６】
【数２】
0003859110.tif 000003
【０１２７】
本発明にあっては、超立方体についてその次元ｄと辺の長さｅをユーザが指定できるようにしており、この値をユーザが指定することによって次のようなカスタマイズを行うことができる。
（１）格納するデータ量が多い場合
次元ｄや辺の長さｅを大きくする。
（２）格納するデータ量が比較的少ない場合
この場合はユーザデータをたくさん入れ、管理情報を少なくしたい。このためには次元ｄや辺の長さｅを少なくすることによって実現できる。
（３）平均距離と管理情報のバランスを取りたい場合
この場合は次元ｄと辺の長さｅとして上記２つの中間的な値を指定する。
（４）平均距離を短くしたい場合
この場合は辺の数ｅを多くすることによって実現できる。但し、この場合には同じページ内に入るユーザデータの量はリンク情報により圧迫され、少なくなる。
【０１２８】
このカスタマイズの（４）の平均距離を短くしたい場合について詳細に説明すると次のようになる。
【０１２９】
ノードの平均距離を短くしたい場合、即ち入力回数を少なくして高速アクセスしたい場合の最も極端な構成は、トップページを全て管理情報で一杯にすることである。即ち、オフセット空間のスペースサイズＳ（ｄ，ｅ）を求める（１）式で示した記号を使用すると、トップページを管理情報で一杯にした場合の辺の長さｅは次のように表わされる。
ｅ＝floor （（ｐ−ｈ−ａ）／ｂ＊ｄ＋１）                    （４）
但し、floor （）は、括弧内の値以下の最大の整数を意味する。
いまページの大きさｐを４ＫＢ（＝４０９６バイト）、ヘッダ部３６の固定領域４０の長さｈを９６バイト、後続ページを持つ子供がいる場合に作られる後続ページ数格納領域４２の大きさａを４バイト、同じく子供がいる場合に作られるリンク情報４４−ｉの１つの要素の大きさｂを１２バイトに仮定する。  この場合、次元ｄ、辺の長さｅ、及びそのとき実現できるオフセット空間の大きさ、即ちスペースサイズＳ（ｄ，ｅ）の関係は、図１４の表に示すようになる。この図１４の表でオフセット空間の大きさ、即ちスペースサイズＳ（ｄ，ｅ）の計算は前記（１）式を使用している。また計算した辺ｅの長さは非常に大きい。
【０１３０】
この場合、オフセット空間の大きさは、おおよそ０次元のノードのスペースの大きさの合計で決まる。即ち、次式でスペースサイズＳ（ｄ，ｅ）が算出される。
S(d,e)〜NS(0,d,e) ＊NC(0,d,e) ＝(e-1) ＊ｅ＾(d-1) ＊(p-h)     （５）
この（５）式で「〜」は、おおよそ等しいことを表わしている。図１４は（５）式で算出したオフセット空間の概算結果であるが、実際のオフセット空間の大きさは図１４の表の値よりも若干大きくなる。この図１４の結果から明らかなように、比較的少ない段数即ち次元ｄで非常に大きなオフセット空間を構築することができる。
４．オフセット空間の拡張と連続領域の実現
図５及び図１１に示した本発明のデータ格納構造を実現する超立方体３４にあっては、次元ｄと辺の長さｅで指定された超立方体のノード数によりオフセット空間の最大ページ数が決まっており、使用したページ数が最大ページ数に達してオフセット空間が一杯になった場合、本発明にあっては更に、超立方体のデータ格納構造を増加してオフセット空間の拡張機能を備える。
【０１３１】
このオフセット空間の拡張は、
▲１▼再帰的拡張方法
▲２▼再構成による拡張方法
等を用いる。
【０１３２】
図１５は、再帰的方法によるオフセット空間の拡張である。超立方体３４で決まるオフセット空間が一杯になった場合、例えば１５ページは通常リンクを持たないが、ここで拡張のために１５ページの構造を０ページと同じものにする。即ち、１５ページから０ページと同じ構造を持つ超立方体６２を追加し、１６ページから３１ページまで拡張可能とする。
【０１３３】
更に、拡張した超立方体６２において、３１ページまで一杯になった場合には、同様に３１ページから０ページと同じように、０ページからの超立方体を拡張し、３２ページから４７ページまで拡張可能とする。このようにして本発明の超立方体は、基本的にはディスク装置等の二次記憶の領域が許す限りいくらでも拡張できるようにすることが可能である。
【０１３４】
次に再構成による拡張方法を説明する。再構成による拡張方法は、最初に指定した次元ｄと辺の長さｅで構成した超立方体によるオフセット空間が一杯になった場合、例えば次元ｄを増加させる方法である。但し、このように次元ｄを増加させた場合にはページ内の管理情報を大きくする必要があり、一杯になった際のオフセット空間の情報を別の領域に複写した後に次元ｄを増加させて、もう一度各ページの管理情報を作り直す必要がある。
【０１３５】
次に本発明の超立方体データ格納構造において、ページの大きさに依存せずに連続領域を実現するための実施形態を説明する。連続領域を実現するためには、より大きなサイズのページを実現すればよい。より大きなページのサイズを設定する方法としては次のものがある。
【０１３６】
▲１▼最小ページ例えば４ＫＢの最小ページの倍数分のページである８ＫＢ，１２ＫＢ，１６ＫＢ，・・・のページを用いる。
【０１３７】
▲２▼最小ページ例えば４ＫＢの最小ページの倍々となる大きさのページ、即ち最小ページに２のべき乗の倍数を乗じた例えば４ＫＢ，８ＫＢ，１６ＫＢ，・・・というページを用いる。
【０１３８】
このような大きさのページを実現する場合、ページ開始位置を示すポインタはページを連続な領域として見えるようにしなければならない。そのためにはシステム側でこれらの大きさのページを乗せる連続したバッファを用意する必要がある。
【０１３９】
しかしながら、これらの大きさのページは二次記憶上では必ずしも連続である必要はない。例えば全て二次記憶上では４ＫＢの大きさに分けられており、この場合、システムが準備したバッファにコピーすることで例えば８ＫＢ，１２ＫＢ，１６ＫＢ，・・・といった連続領域に見せればよい。
【０１４０】
次に図６及び図１２に示した各ページにおいて、データ部におけるデータの格納状態を管理するためのページ管理領域の実現方法を説明する。このページ内のデータ部３８におけるデータの格納状態を示すページ領域管理の情報は、ヘッダ部３６の固定格納領域４０に管理情報を格納している。
【０１４１】
ページ内のデータ格納状態を管理するためのページ領域管理の第１の方法としては、主記憶の領域管理と同様な方法を使用すればよい。
【０１４２】
即ち、ページ内のデータ部３８に格納している例えばデータ領域５２−１，５２−２とアドレスの対応関係を示すリストを作成し、このリストに従って各領域を管理し、領域が開放された場合はその領域の再利用を可能とする。
【０１４３】
第２のページ内のデータ格納領域の状態を管理するページ領域管理の実現方法としては、ヒープによる方法がある。このヒープによる方法は、主記憶の領域管理に比べると、より簡単な方法である。
【０１４４】
まずヒープと呼ばれる連続した領域をデータ部３８に確保しておき、このヒープ領域の先頭位置に、最初にあるポインタを設けて示しておく。アクセスにより領域が要求された場合には、ポインタから要求された長さ分だけの領域を介し、ポインタを要求領域分だけ進めておく。しかしながら、このヒープによる方法は、使用済みの領域が途中で開放されても、その開放がわからないことから、再利用はできない。
【０１４５】
尚、本発明は上記の実施形態に限定されず、その目的と利点を損なわない適宜の変形を含む。また本発明は上記の実施形態に示した数値による限定は受けない。
【０１４６】
【発明の効果】
以上説明してきたように本発明によれば、次の効果が得られる。
【０１４７】
まずデータ格納構造として超立方体の構造をとっているため、アクセス効率の良いオフセット空間が実現できる。具体的には、従来からのデータ、複雑なデータ、長大データを効率よくアクセスして格納することができる。
【０１４８】
また、オフセット空間に対する多様な要求への対応が適切にできる。例えば、超立方体のページまでの入力回数を示す辺の長さを３以上でも可能としたことと、この辺の長さと次元の２つのパラメータによって管理情報とユーザ情報のバランスをカスタマイズでき、いろいろなオフセット空間に対する要求に適切に応えることができる。
【０１４９】
具体的な要求としては、データ量が多い場合、あるいは多くなる可能性がある場合、更には長大データの場合、トップページに管理情報を集めるようにすることで全体の平均アクセス効率を高めるという要求に応えることができる。
【０１５０】
またデータ量が少ない場合には、トップページの管理情報を少なくし、なるべくユーザデータの部分がトップページの管理情報に圧迫されないようにすることで、アクセス回数をトップページに集中させることで効率を高めることができる。
【０１５１】
更に両者の中間的な場合について、管理情報とユーザデータをバランスよく共存させることができる。また本発明にあっては、予め指定した次元と辺の長さで決まる超立方体のデータ格納構造を持つオフセット空間でページ単位に必要な分だけ拡張でき、更にオフセット空間が一杯になった場合には新たな超立方体のデータ構造を持つ拡張空間の追加あるいは次元の増加による再構成で、最初に指定したオフセット空間より大きな空間に拡張することができる。
【０１５２】
更に、ユーザが用意したシステム上の領域にコピーすることなく、オフセット空間上のページサイズを変えることにより空間内に連続領域をとり、この連続領域のデータをユーザにコピーの手間をかけることなく提供することができる。
【図面の簡単な説明】
【図１】本発明の原理説明図
【図２】本発明のハードウェア構成のブロック図
【図３】本発明の機能構成のブロック図
【図４】本発明における論理空間、主記憶空間及びオフセット空間の説明図
【図５】次元ｄを４次元、辺の長さｅを２とした本発明の超立方体のデータ記憶構造の説明図
【図６】図３の０ページのデータ構造の説明図
【図７】図６のヘッダ部に設けたリンク情報の説明図
【図８】図５の超立方体に従って格納した図３のオフセット空間の説明図
【図９】図５の超立方体の距離を示した説明図
【図１０】図３の超立方体データ構造装置によるオフセット空間アクセス処理のフローチャート
【図１１】次元ｄを４次元、辺の長さｅを３とした本発明の超立方体のデータ記憶構造の説明図
【図１２】図１１の０ページのデータ構造の説明図
【図１３】図１１の超立方体の距離を示した説明図
【図１４】図１１の超立方体データ構造でトップページにのみ管理情報を格納した場合の次元ｄと辺の長さｅに対するオフセット空間の大きさの対応関係の説明図
【図１５】図５の超立方体のオフセット空間が満杯になった場合の拡張構造の説明図
【図１６】オフセット空間におけるページ構造の一般的な説明図
【図１７】ページによるデータ格納の説明図
【図１８】ページに格納しているデータがオーバフローした場合のベージ拡張の説明図
【図１９】オフセット空間でのページ格納状態の説明図
【図２０】ページの線状のリンクで実現されるオフセット空間の説明図
【図２１】ページの木状のリンクで実現されるオフセット空間の説明図
【符号の説明】
１０：中央処理装置
１２：主記憶装置
１４：ディスク装置（二次記憶装置）
１６：超立方体データ構造装置
１８：超立方体構成部
２０：アクセス処理部
２２：バス
２６：論理空間
２８：主記憶空間
３０：オフセット空間
３２−０：０ページ（トップページ）
３２−１〜３２−ｎ：１〜ｎページ
３４，６０：超立方体
３６：ヘッダ部
３８：データ部
４０：ｈｅａｄｅｒｉ（ｉペーシ空き領域情報等）
４２：ｏｎＮｅｘｔ（トップペーシから辿るページ数）
４４−ｉ：配列ｎｅｘｔ［ｉ］（リンク情報）
４６：pageId（ページ識別子）
４８：maxAreaSize （は以下ページ中の獲得可能な最大領域サイズ）
５０:lastOffset(そのページをルートとする部分超立方体の最後のオフセット）
６２：拡張超立方体
【図１】
0003859110.tif 000004
【図２】
0003859110.tif 000005
【図３】
0003859110.tif 000006
【図４】
0003859110.tif 000007
【図５】
0003859110.tif 000008
【図６】
0003859110.tif 000009
【図７】
0003859110.tif 000010
【図８】
0003859110.tif 000011
【図９】
0003859110.tif 000012
【図１０】
0003859110.tif 000013
【図１１】
0003859110.tif 000014
【図１２】
0003859110.tif 000015
【図１３】
0003859110.tif 000016
【図１４】
0003859110.tif 000017
【図１５】
0003859110.tif 000018
【図１６】
0003859110.tif 000019
【図１７】
0003859110.tif 000020
【図１８】
0003859110.tif 000021
【図１９】
0003859110.tif 000022
【図２０】
0003859110.tif 000023
【図２１】
0003859110.tif 000024