(57)【要約】【課題】テーブルに使用、未使用の表示エリアを設け、この使用、未使用を検索するテーブル管理においては、管理対象が大きくなるとオーバーヘッドする。【解決手段】テーブルに最小の空きレコード番号が書き込まれる最小空きレコードエリアと、使用前後のリンク情報が書き込まれる前リンクレコードエリア及び後リンクレコードエリアと、使用されている最終レコード番号の書き込まれる使用最終レコードエリアと、レコードの使用状態の有無を表示する使用表示エリアを設け、リンク情報再設定時に各エリア情報を参照することで更新機会を減らすようにした。【選択図】  図１
2005309634.tif 000002
【特許請求の範囲】
【請求項１】
コンピュータシステムにおける使用情報にレコード番号使用・未使用情報を付してテーブルエリアに格納するテーブルにおいて、
前記テーブルに最小の空きレコード番号が書き込まれる最小空きレコードエリアと、使用前後のリンク情報が書き込まれる前リンクレコードエリア及び後リンクレコードエリアと、使用されている最終レコード番号の書き込まれる使用最終レコードエリアと、レコードの使用状態の有無を表示する使用表示エリアとを備えたことを特徴とした情報格納テーブル。
【請求項２】
コンピュータシステムにおける使用情報にリンクレコード番号を付して各エリアに格納すると共に、レコードの使用，未使用エリアを設け、この使用，未使用を管理しながら格納された情報を検索するものにおいて、  
前記テーブルに最小の空きレコード番号が書き込まれる最小空きレコードエリアと、使用前後のリンク情報が書き込まれる前リンクレコードエリア及び後リンクレコードエリアと、使用されている最終レコード番号の書き込まれる使用最終レコードエリアと、レコードの使用状態の有無を表示する使用表示エリアとを設け、未使用レコードが連続する場合には前記各エリアに初期値を設定したことを特徴としたテーブル管理方法。
【請求項３】
前記最小空きレコードエリアに使用可能な最小の空きレコード番号を書き込み、当該空きレコード番号の後リンクレコードエリアに次の未使用エリアのレコード番号を書き込み、続けての空きレコード探索時にこの後リンクレコードエリアを参照して使用可能レコードエリアを検索することを特徴とした請求項２記載のテーブル管理方法。    
【請求項４】
前記使用最終レコードエリアに使用レコードの最終レコード番号を書き込み、リンク情報再設定時に当該設定エリアレコード番号以降の検索を省くことを特徴とした請求項２又は３記載のテーブル管理方法。
【請求項５】
レコードエリアにおける未使用中のレコードを使用にしたとき、当該レコードエリアのリンク情報を参照してリンク情報の再設定を行うことを特徴とした請求項２乃至４記載のテーブル管理方法。
【請求項６】
レコードエリアに設定された使用中のレコードを未使用としたとき、前記最小空きレコードエリア、使用最終レコードエリア及び使用表示エリアのレコード番号を検索することでリンク情報の再設定を行うことを特徴とした請求項２乃至５記載のテーブル管理方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、コンピュータにおける情報を格納するテーブルとそのテーブル管理方法に関するものである。
【背景技術】
【０００２】
コンピュータシステムにおいては、情報が格納されるファイル又はテーブル（以下これらを単にテーブルという）内を検索して目的とするデータを取り出すことが行われている。その際、データのテーブルへの格納方法が、コード番号の小さいものから大きいもの（又はは大きいものから小さいもの）、或いはコード番号が連番でなく、しかも前詰めで格納されているとき、直接目的とするデータを取り出すことができないので所望のデータ検索を行うことになる。そのデータ検索法の一つとして２分探索法（バイナリ・サーチ）が知られている。
【０００３】
２分探索法を用いてテーブル内の或る名称コードを検索する場合、当該名称コードがテーブルサイズの最大まで常に格納されていたときには２分探索法は有効な方法であるが、制御対象規模の拡大が予想されるシステムにおいては、予めテーブルサイズの規模を拡大の予想に合わせて現存する名称コード数の数倍で作成するのが一般である。このような場合、２分探索法のみでは現在未使用となっているエリアの検索も単純に実行してしまうため、検索時間が長くかかる問題を有している。
なお、検索時間を短縮する方法としては、非特許文献１のものがあり、また、テーブルの管理方法として特許文献１のものが知られている。
【特許文献１】特開平３−２３１３４０号公報
【非特許文献１】公開技報番号９６−２３８９
【発明の開示】
【発明が解決しようとする課題】
【０００４】
２分探索法の欠点を補うために、分割した各単位をビット等で使用／未使用を管理する手法が考えられるが、その場合には未使用レコードを探すための管理情報検索が必要となる。そのため、管理対象が大きくなると検索時間がオーバーヘットとなる新たな問題が発生する。また、特許文献１のものには、使用，未使用を管理しながら検索する思想は存在していない。
テーブル内の未使用レコードを検索する場合、レコードの使用／未使用を判断する管理情報の検索が必要となるが、本発明が目的とするところは、従来の検索方法で発生していた検索時間のオーバーヘットを減らすことのできるテーブル構造とその管理・検索方法を提供することにある。
【課題を解決するための手段】
【０００５】
本発明の第１は、コンピュータシステムにおける使用情報にレコード番号を付して格納するテーブルにおいて、
前記テーブルに最小の空きレコード番号が書き込まれる最小空きレコードエリアと、使用前後のリンク情報が書き込まれる前リンクレコードエリア及び後リンクレコードエリアと、使用されている最終レコード番号の書き込まれる使用最終レコードエリアと、レコードの使用状態の有無を表示する使用表示エリアとを備えたことを特徴としたものである。
【０００６】
本発明の第２は、コンピュータシステムにおける使用情報にリンクレコード番号を付して各エリアに格納すると共に、レコードの使用，未使用エリアを設け、この使用，未使用を管理しながら格納された情報を検索するものにおいて、  
前記テーブルに最小の空きレコード番号が書き込まれる最小空きレコードエリアと、使用前後のリンク情報が書き込まれる前リンクレコードエリア及び後リンクレコードエリアと、使用されている最終レコード番号の書き込まれる使用最終レコードエリアと、レコードの使用状態の有無を表示する使用表示エリアとを設け、未使用レコードが連続する場合には前記各エリアに初期値を設定したことを特徴としたものである。
【０００７】
本発明の第３は、前記最小空きレコードエリアに使用可能な最小の空きレコード番号を書き込み、当該空きレコード番号の後リンクレコードエリアに次の未使用エリアのレコード番号を書き込み、続けての空きレコード探索時にこの後リンクレコードエリアを参照して使用可能レコードエリアを検索することを特徴としたものである。
【０００８】
本発明の第４は、前記使用最終レコードエリアに使用レコードの最終レコード番号を書き込み、リンク情報再設定時に当該設定エリアレコード番号以降の検索を省くことを特徴としたものである。
【０００９】
本発明の第５は、レコードエリアにおける未使用中のレコードを使用にしたとき、当該レコードエリアのリンク情報を参照してリンク情報の再設定を行うことを特徴としたものである。
【００１０】
本発明の第６は、レコードエリアに設定された使用中のレコードを未使用としたとき、前記最小空きレコードエリア、使用最終レコードエリア及び使用表示エリアのレコード番号を検索することでリンク情報の再設定を行うことを特徴としたものである。
【発明の効果】
【００１１】
以上のとおり、本発明によれば、テーブルに最小空きレコード、使用最終レコード、リンク情報を管理するための各エリアを設け、そのエリアの情報を参照することによって空きエリアを探索するものであるから、次のような効果を有するものである。  
（１）全てのレコードに対してのリンク情報がエリアにあるので、未使用レコードが連続している場合には「０」（初期値）を設定し、余分なリンク情報を持たせないことによりリンク情報の更新機会を減らすことができる。
（２）最小空きレコード番号を持つことにより、次に使用可能な空きレコードエリアを検索することなく取得可能となる。  
（３）使用最終レコード番号を持つことにより、リンク情報の再設定のときの余分な検索を減らすことができる。  
（４）続けて空きレコードを探す場合、後リンクレコードを参照することにより、検索することなく次に使用可能な空きレコードを取得することが可能となる。  
（５）未使用中のレコードを使用にしたときのリンク情報の更新は、使用にしたレコードのリンク情報を参照することで更新可能となる（再検索不要）。
（６）使用中のレコードを未使用にしたとき、最小空きレコード番号、使用最終レコード番号及びリンク情報を使用することにより最小限の再検索によりリンク情報更新を実現することができる。  
【発明を実施するための最良の形態】
【００１２】
図１は、本発明の実施例を示すテーブル構造を示したもので、テーブルに最小空きレコード番号を書き込む最小空きレコードエリアＭＣ、使用されたレコードの最終番号を書き込む最終レコードエリアＥＵ、各レコードの使用前後のリンク情報が書き込まれる前リンクレコードエリアＬＢ、及び後リンクレコードエリアＬＡを有している。ＮＯはレコード番号エリア、ＵＸは使用表示エリアである。
【００１３】
図１は初期状態を示したものである。この場合、使用レコード番号に書き込まれているレコード番号１〜６は未使用であるので、使用表示エリアＵＸは空欄状態であり、リンク情報エリアのＬＢ，ＬＡはリンク情報なしの初期値０となっており、したがって、使用レコードの最終番号が書き込まれる最終レコードエリアＥＵも０となっている。このときの最小空きレコードエリアＭＣのレコード番号は１となる。
【００１４】
図２は未使用から使用に移行する場合を示したものである。図２の使用表示エリアＵＸの○はレコード使用中を示したもので、同図（ａ）ではレコード番号の１，３，４，５が使用中である。この場合、空きレコードは２，６であるが、２．６のうち小さい方のレコード（最小レコード）は２であるので、最初のレコード番号１の最小空きレコードエリアＭＣに２を書き込み、且つレコード番号１の最終レコードエリアＥＵには使用されたレコード番号の最終レコードは５であるので最終レコードエリアＥＵにはこのレコード番号５が書き込まれる。
また、空きレコードは２，６と非連続であることから、レコード番号２のリンク情報における後リンクレコードエリアＬＡにレコード６が書き込まれる。
一方、未使用のレコード番号６では、当該レコード番号６の前の未使用レコード番号は２であることからこの２が前リンクレコードエリアＬＢに書き込まれる。
【００１５】
図２（ａ）の状態で、リンクレコード２が使用状態に移行した場合を示したものが図２（ｂ）である。レコード２が未使用がら使用に移行したことにより、最小空きレコードＭＣの２は削除されて次の未使用レコードである６がこの最小空きレコードエリアＭＣに新たに書き込まれる。これに伴って削除されたレコード２の使用最終レコードエリアの６も削除されて０となると共に、レコード６の前リンクレコードエリアＬＢの２も削除されて０となる。
また、未使用から使用に移行する場合、新たな空きレコード番号は、前の最小空きレコードの後のリンクレコードエリアに番号が入っていなければ更に前の最小空きレコードの次のレコードとなる。保存した最小空きレコードの後リンクレコードエリアに番号が入っていれば、そのリンクレコード番号のレコードが新たな最小空きレコードとなる。そして、新たな最小空きレコードの前のリンクレコード番号は０となる。
【００１６】
次に使用中から未使用とする場合について説明する。
この場合には、未使用となるレコードが最小空きレコードエリアＭＣに書き込まれた番号より小さい番号の場合（１）と、大きい番号の場合（２）とがある。
【００１７】
（１）最小空きレコードエリアの値より小さい番号のレコードが未使用となった場合の手順について
ａ．最小空きレコードエリアＭＣに、使用中から未使用となったレコード番号を入れる。
ｂ．新たな空きレコードエリアに書き込むためのレコードリンク情報を作成する。このとき、前の最小空きレコードエリアＭＣのレコード番号と未使用となったレコード番号が連続していない場合には、新たな空きレコードの後リンクレコードＬＡに、前の最小空きレコード番号を入れる。未使用レコード番号が連続している場合には、後リンクレコードエリアＬＡの値を０とする。ただし、リンク情報を持つものは非連続に未使用レコードが存在する場合のみとする。
ｃ．使用最終レコードエリアＥＵに使用最終レコード番号を入れる。このとき、前の最小空きレコードエリアＭＣのレコード番号と未使用としたレコード番号が連続していない場合には、使用最終レコードエリアＥＵの値は変更しない。
【００１８】
最小空きレコードエリアの値より小さい番号のレコードが未使用となった場合でも、未使用となったレコードが、変更前の最小空きレコード番号と連続していない場合と連続している場合とがある。
【００１９】
（１）−１、未使用となったレコードが、変更前の最小空きレコード番号と連続していない場合について
図３はレコード４を削除する場合で、レコード番号４は変更前の最小空きレコード番号６とは連続していない例である。
基本的には上記ａ〜ｃの手順に従うが、先ず、最小空きレコードエリアＭＣに使用中から未使用になったレコード番号４を入れる。次に、未使用となったことにより、新たな空きレコードエリアに書き込むためのレコードリンク情報を作成するが、ここでの新たな空きレコードの後のリンクレコードエリアＬＡの情報は、前の最小空きレコード番号６であってこの番号６を入れる。
次に、前の最小空きレコードエリアのレコードリンク情報を作成する。図３（ｂ）の場合には、前の最小空きレコード番号６の前リンクレコードエリアＬＢに新たな最小空きレコード番号４を入れる。
【００２０】
（１）−２、未使用となったレコードが、変更前の最小空きレコード番号と連続している場合について
図４は（ａ）図におけるレコード５を削除する場合で、このレコード番号５は変更前の最小空きレコード番号６とは連続している例である。
先ず、図４（ｂ）で示すように、空きレコードエリアＭＣに使用中から未使用となったレコード番号５を入れる。
次に、未使用となったことにより、新たな空きレコードエリアに書き込むためのレコードリンク情報を作成するが、未使用となったレコードが、変更前の最小空きレコード番号６と連続しているので、新たな空きレコード（レコード番号５）の後のリンクレコードエリアＬＡに０を入れる。
次に、前の最小空きレコードエリア（レコード番号６）のレコードのリンク情報を作成する。この場合、未使用となったレコードが変更前の最小空きレコード番号と連続しているので、前の最小空きレコード番号６のレコードの前リンクレコードエリアＬＢに０を入れる。その後、使用最終レコードエリアＥＵに削除されたレコード番号を入れる。
【００２１】
（２）最小空きレコードエリアの値より大きい番号のレコードが未使用となった場合の手順について
ａ’．最小空きレコード番号のレコードから順にレコードリンク情報を追いかけ、レコードリンク情報に入っている番号を比較していく。
後リンクレコードエリアＬＡの値が０の場合は、次レコード番号がリンク先となる。すなわち、未使用のレコードが連続していることを示している。
なお、使用最終レコードエリアＥＵ以降には使用しているレコードがないことから、上記比較は、使用最終レコードエリアに入っているレコード番号までを行えばよい。
ｂ’．リンク先が未使用となったレコード番号より大きい番号となったときに、リンク情報を作成する。この場合、当該レコードの後リンクレコードエリアに未使用としたレコード番号を入れる。この未使用としたレコード番号の前リンクレコードエリアに当該レコード番号を入れる。
また、未使用としたレコードの後リンクレコードエリアＬＡには、書き換える前、当該レコード番号の後リンクレコードエリアＬＡ入っていたレコード番号を入れる。そして、書き換える前、当該レコード番号の後リンクレコードエリアに入っていたレコード番号の前リンクレコードエリアに未使用としたレコード番号を入れる。
ただし、それぞれのリンク先との間が連続している場合には、連続している双方に対するリンク先の番号を０とする。
ｃ’．使用最終レコードエリアＥＵに使用最終レコード番号を入れる。
この場合、未使用となったレコードが、使用最終レコードより小さいときには、使用最終レコードに変更がないので、使用最終レコードエリアＥＵの値に変更がない。
未使用となったレコードが、使用最終レコードである場合には、未使用となったレコードから前方向に使用しているレコードを順番に検索し、一番初めに見つかった使用中であるレコード番号を使用最終レコードエリアＥＵに入れる。
以下具体的に説明する。
【００２２】
（２）−１、レコード番号を未使用とすることによりリンク先が連続する場合について
図５はレコード３を未使用とした場合の例を示したものである。この場合、最小空きレコード番号（＝１）のレコードから順番にレコードリンクを追いかけ、レコードリンク情報に入っている番号を比較していく。リンク先が未使用となったレコード番号（＝３）より大きい番号となったときにリンク情報を作成する。
図５（ａ）では、レコード番号２の後リンクレコードエリアＬＡの値は６なので、未使用となったレコード番号３より大きくなる。通常では、当該レコードの後リンクレコードエリアＬＡに未使用としたレコード番号を入れ、未使用となったレコード番号の前リンクレコードエリアＬＢに当該レコード番号を入れるが、この場合ではレコード２とレコード３が共に未使用となり、それぞれのリンク先との間が連続している例であるので、レコード２の後リンクレコードエリアＬＡとレコード３の前リンクレコードエリアＬＢの値は、図５（ｂ）で示すように共に０とする。
また、未使用としたレコード（レコード番号３）の後リンクレコードエリアＬＡには、書き換える前、当該レコード番号２の後リンクレコードエリアＬＡに入っていたレコード番号６を入れる。そして、書き換える前、当該レコード番号２の後リンクレコードエリアＬＡに入っていたレコード番号６の前リンクレコードエリアＬＢに未使用としたレコード番号３を入れる。
未使用となったレコード番号３は、使用最終レコードより小さいので、使用最終レコードエリアＥＵの値は変更しない。
【００２３】
（２）−２、レコード番号を未使用とすることによりリンク先が連続しない場合について
図６はレコード番号４を未使用とした場合を示したもので、最小空きレコード番号（＝１）のレコードから順次レコードリンクを追いかけてレコードリンク情報の入っている番号を比較していく。リンク先が未使用となったレコード番号（＝４）より大きい番号となとき、リンク情報を作成する。
図６の場合、レコード２の後リンクレコードエリアＬＡの値は６であるので、未使用となったレコード番号（＝４）より大きくなる。ここで、当該レコード（レコード番号２）の後リンクレコードエリアＬＡに未使用としたレコード番号４を入れ、未使用としたレコード番号４の前リンクレコードエリアＬＢに当該レコード番号２を入れる。
また、未使用としたレコード番号４の後リンクレコードエリアＬＡには、書き換える前、当該レコード番号２の後リンクレコードエリアＬＡに入っていたレコード番号６を入れる。そして、書き換える前に、当該レコード番号２の後リンクレコードエリアＬＡに入っていたレコード番号６の前リンクレコードエリアには未使用としたレコード番号４を入れる。
未使用となったレコード（＝４）は、使用最終レコードより小さいので、使用最終レコードエリアＥＵの値は変更しない。
【００２４】
（２）−３、未使用レコードが使用最終レコードの場合について
図７はレコード場合５を未使用とした場合で、同図（ａ）は変更前、（ｂ）図は変更途中、（ｃ）図は変更後をそれぞれ示したものである。
最小空きレコード番号（＝１）より順次レコードリンク情報を追いかけてレコードリンク情報に入っている番号を比較していく。リンク先が未使用となったレコード番号５より大きい番号となったときにリンク情報を作成する。
図７（ａ）ではレコード４の後リンクレコードエリアＬＡの値は６であるので、未使用となったレコード番号５より大きい。
ここで、当該レコード（＝４）の後リンクレコードエリアＬＡに未使用としたレコード番号５を入れ、未使用としたレコード５の前リンクレコードエリアＬＢに当該レコード番号４を入れる。未使用としたレコード番号５の後リンクレコードエリアＬＡには、書き換える前の、当該レコード番号４の後リンクレコードエリアＬＡに入っていたレコード番号６を入れる。そして、書き換える前に、当該レコード番号４の後リンクレコードエリアＬＡに入っていたレコード番号６の前リンクレコードエリアＬＢに未使用としたレコード番号５を入れる。
ただし、図７の場合には、レコード番号５を未使用とすることによりレコード４，５，６が未使用となり、それぞれのリンク先との間が連続しているので、（ｂ）図で示すように、レコード４，５，の各後リンクレコードエリアＬＡ、及びレコード５，６の各前リンクレコードエリアＬＢの値をそれぞれ０とする。
なお、レコード番号５は、使用最終レコードであったので、以降のレコードは使用されない。
また、未使用となったレコードが使用最終レコードであることから、未使用となったレコードから前方向に使用しているレコードを順番に検索し、使用最終レコードエリアＥＵに見つかったレコード番号３を入れる。
【００２５】
以上本発明によれば、テーブルに最小空きレコード、使用最終レコード、リンク情報を管理するための各エリアを設け、そのエリアの情報を判別することによって空エリアを探索するものであるから、管理対象が大きくなっても検索時間がオーバーヘッドすることなく短時間で検索できるものである。
【図面の簡単な説明】
【００２６】
【図１】本発明の実施形態を示すテーブル構成図。
【図２】テーブル未使用から使用への説明図で、（ａ）は現在状態図、（ｂ）          は未使用レコードを使用に変更したときの状態図。
【図３】テーブル使用中から未使用とする場合で、（ａ）は現在状態図、（ｂ）          は使用中レコードを未使用に変更したときの説明図。
【図４】テーブル使用中から未使用とする場合で、（ａ）は現在状態図、（ｂ）          は使用中レコードを未使用に変更したときの説明図。
【図５】テーブル使用中から未使用とする場合で、（ａ）は現在状態図、（ｂ）          は使用中レコードを未使用に変更したときの説明図。
【図６】テーブル使用中から未使用とする場合で、（ａ）は現在状態図、（ｂ）          は使用中レコードを未使用に変更したときの説明図。
【図７】テーブル使用中から未使用とする場合で、（ａ）は現在状態図、（ｂ）          は変更途中状態図、（ｃ）は使用中レコードを未使用に変更したとき          の説明図。
【符号の説明】
【００２７】
ＭＣ…最小空きレコードエリア  
ＮＯ…リンクレコード番号エリア  
ＵＸ…使用表示エリア  
ＬＢ…前リンクレコードエリア  
ＬＡ…後リンクレコードエリア  
ＥＵ…使用最終レコードエリア  
【図１】
2005309634.tif 000003
【図２】
2005309634.tif 000004
【図３】
2005309634.tif 000005
【図４】
2005309634.tif 000006
【図５】
2005309634.tif 000007
【図６】
2005309634.tif 000008
【図７】
2005309634.tif 000009