JPH052512A - 空き領域検索方式 - Google Patents
空き領域検索方式Info
- Publication number
- JPH052512A JPH052512A JP3178695A JP17869591A JPH052512A JP H052512 A JPH052512 A JP H052512A JP 3178695 A JP3178695 A JP 3178695A JP 17869591 A JP17869591 A JP 17869591A JP H052512 A JPH052512 A JP H052512A
- Authority
- JP
- Japan
- Prior art keywords
- unit
- additional
- addition
- additional unit
- vacancy
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Granted
Links
Classifications
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
- G06F16/90—Details of database functions independent of the retrieved data types
- G06F16/901—Indexing; Data structures therefor; Storage structures
- G06F16/9017—Indexing; Data structures therefor; Storage structures using directory or table look-up
- G06F16/902—Indexing; Data structures therefor; Storage structures using directory or table look-up using more than one table in sequence, i.e. systems with three or more layers
-
- Y—GENERAL TAGGING OF NEW TECHNOLOGICAL DEVELOPMENTS; GENERAL TAGGING OF CROSS-SECTIONAL TECHNOLOGIES SPANNING OVER SEVERAL SECTIONS OF THE IPC; TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS
- Y10—TECHNICAL SUBJECTS COVERED BY FORMER USPC
- Y10S—TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS
- Y10S707/00—Data processing: database and file management or data structures
- Y10S707/99951—File or database maintenance
- Y10S707/99956—File allocation
Landscapes
- Engineering & Computer Science (AREA)
- Databases & Information Systems (AREA)
- Theoretical Computer Science (AREA)
- Software Systems (AREA)
- Data Mining & Analysis (AREA)
- Physics & Mathematics (AREA)
- General Engineering & Computer Science (AREA)
- General Physics & Mathematics (AREA)
- Information Retrieval, Db Structures And Fs Structures Therefor (AREA)
Abstract
(57)【要約】
【目的】 データレコードを格納するための空きを付加
単位から高速に探し出せるようにする。 【構成】 格納単位空き判定手段１は格納単位に空きが
あるかどうかを判定し、上位付加単位結合判定手段２は
上位付加単位が結合しているかどうかを判定し、上位付
加単位取得手段３は付加ポインタをたどり上位付加単位
を取得し、上位付加単位空き判定手段４は上位付加単位
に空きがあるかどうかを判定し、下位付加単位空き判定
手段５は上位付加単位制御レコード中の下位付加単位空
き情報を参照して下位付加単位に空きがあるかどうかを
判定し空きがなければ上位付加単位結合判定手段２に制
御を戻し、上位付加単位結合手段６は新しい上位付加単
位を結合し、下位付加単位結合手段７は新しい上位付加
単位に新しい下位付加単位を所定数だけ結合する。
単位から高速に探し出せるようにする。 【構成】 格納単位空き判定手段１は格納単位に空きが
あるかどうかを判定し、上位付加単位結合判定手段２は
上位付加単位が結合しているかどうかを判定し、上位付
加単位取得手段３は付加ポインタをたどり上位付加単位
を取得し、上位付加単位空き判定手段４は上位付加単位
に空きがあるかどうかを判定し、下位付加単位空き判定
手段５は上位付加単位制御レコード中の下位付加単位空
き情報を参照して下位付加単位に空きがあるかどうかを
判定し空きがなければ上位付加単位結合判定手段２に制
御を戻し、上位付加単位結合手段６は新しい上位付加単
位を結合し、下位付加単位結合手段７は新しい上位付加
単位に新しい下位付加単位を所定数だけ結合する。
Description
【０００１】
【産業上の利用分野】本発明は電子計算機システムにお
けるデータベースシステムに関し、特にデータレコード
を格納するデータ格納領域とデータ格納領域があふれた
場合にデータ格納領域に領域を追加するためのあふれ領
域とから構成されるデータファイルを備えるデータベー
スシステムにおける空き領域検索方式に関する。
けるデータベースシステムに関し、特にデータレコード
を格納するデータ格納領域とデータ格納領域があふれた
場合にデータ格納領域に領域を追加するためのあふれ領
域とから構成されるデータファイルを備えるデータベー
スシステムにおける空き領域検索方式に関する。
【０００２】
【従来の技術】従来、この種の空き領域検索方式では、
図５に示すように、データレコードを格納しようとする
格納単位５００に空きがなかった場合には、データ格納
領域の格納単位５００に領域を追加するためのあふれ領
域の付加単位５０１が単に付加ポインタ５０２により順
次結合されているだけであったので、結合された付加単
位５０１内からデータレコードを格納するための空きを
探すときには、付加単位５０１の付加ポインタ５０２を
順にたどってすべての付加単位５０１の空きを検索して
いた。
図５に示すように、データレコードを格納しようとする
格納単位５００に空きがなかった場合には、データ格納
領域の格納単位５００に領域を追加するためのあふれ領
域の付加単位５０１が単に付加ポインタ５０２により順
次結合されているだけであったので、結合された付加単
位５０１内からデータレコードを格納するための空きを
探すときには、付加単位５０１の付加ポインタ５０２を
順にたどってすべての付加単位５０１の空きを検索して
いた。
【０００３】詳しくは、図６に示すように、データレコ
ードを格納するための空きを探す場合には、まずデータ
レコードを格納すべき格納単位５００に空きがあるかど
うかをチェックし（ステップ６０１）、空きがある場合
には（ステップ６０２でイエス）、処理を終了する。格
納単位５００に空きがない場合には（ステップ６０２で
ノー）、格納単位５００に付加単位５０１を結合してい
るかどうかチェックし（ステップ６０３）、結合してい
ない場合には（ステップ６０４でノー）、新しい付加単
位５０１を結合して処理を終了する（ステップ６０
８）。格納単位５００に付加単位５０１を結合している
場合には（ステップ６０４でイエス）、付加ポインタ５
０２をたどり次の付加単位５０１を得て（ステップ６０
５）、付加単位５０１内に空きがあるかどうかをチェッ
クする（ステップ６０６）。空きがある場合には（ステ
ップ６０７でイエス）、処理を終了し、空きがない場合
には（ステップ６０７でノー）、ステップ６０３に制御
を戻す。
ードを格納するための空きを探す場合には、まずデータ
レコードを格納すべき格納単位５００に空きがあるかど
うかをチェックし（ステップ６０１）、空きがある場合
には（ステップ６０２でイエス）、処理を終了する。格
納単位５００に空きがない場合には（ステップ６０２で
ノー）、格納単位５００に付加単位５０１を結合してい
るかどうかチェックし（ステップ６０３）、結合してい
ない場合には（ステップ６０４でノー）、新しい付加単
位５０１を結合して処理を終了する（ステップ６０
８）。格納単位５００に付加単位５０１を結合している
場合には（ステップ６０４でイエス）、付加ポインタ５
０２をたどり次の付加単位５０１を得て（ステップ６０
５）、付加単位５０１内に空きがあるかどうかをチェッ
クする（ステップ６０６）。空きがある場合には（ステ
ップ６０７でイエス）、処理を終了し、空きがない場合
には（ステップ６０７でノー）、ステップ６０３に制御
を戻す。
【０００４】
【発明が解決しようとする課題】上述した従来の空き領
域検索方式では、付加単位５０１の空きを探すためには
付加ポインタ５０２をたどって順次検索していかなくて
はならなかったので、格納単位５００に結合している付
加単位５０１が多くなると空きを検索する処理時間が多
くかかり過ぎ、データベースシステム全体の処理速度に
大きな影響を与えるという問題点がある。
域検索方式では、付加単位５０１の空きを探すためには
付加ポインタ５０２をたどって順次検索していかなくて
はならなかったので、格納単位５００に結合している付
加単位５０１が多くなると空きを検索する処理時間が多
くかかり過ぎ、データベースシステム全体の処理速度に
大きな影響を与えるという問題点がある。
【０００５】本発明の目的は、上述の点に鑑み、付加単
位を上位付加単位と下位付加単位とに分けるとともに、
上位付加単位制御レコード中の下位付加単位空き情報を
参照して下位付加単位に空きがあるかどうかをチェック
するようにして、付加単位からデータレコードを格納す
るための空きを高速に探し出すことができるようにした
空き領域検索方式を提供することにある。
位を上位付加単位と下位付加単位とに分けるとともに、
上位付加単位制御レコード中の下位付加単位空き情報を
参照して下位付加単位に空きがあるかどうかをチェック
するようにして、付加単位からデータレコードを格納す
るための空きを高速に探し出すことができるようにした
空き領域検索方式を提供することにある。
【０００６】
【課題を解決するための手段】本発明の空き領域検索方
式は、データレコードを格納するデータ格納領域と、こ
のデータ格納領域があふれた場合に前記データ格納領域
に領域を追加するためのあふれ領域とから構成されるデ
ータファイルを備えるデータベースシステムにおいて、
上位付加単位を結合する付加ポインタを有する格納単位
制御レコードが格納された格納単位からなる前記データ
格納領域と、上位付加単位を結合する付加ポインタ，下
位付加単位を結合する下位付加ポインタおよび下位付加
単位空き情報を有する上位付加単位制御レコードが格納
された上位付加単位と、上位付加単位を結合する上位付
加ポインタを有する下位付加単位制御レコードが格納さ
れた下位付加単位とに分類される付加単位からなる前記
あふれ領域と、格納単位に空きがあるかどうかを判定す
る格納単位空き判定手段と、この格納単位空き判定手段
および後記下位付加単位空き判定手段により空きがない
と判定されたときに格納単位および上位付加単位に上位
付加単位が結合しているかどうかを判定する上位付加単
位結合判定手段と、この上位付加単位結合判定手段によ
り上位付加単位が結合していると判定されたときに付加
ポインタをたどり次の上位付加単位を得る上位付加単位
取得手段と、この上位付加単位取得手段により取得され
た上位付加単位に空きがあるかどうかを判定する上位付
加単位空き判定手段と、この上位付加単位空き判定手段
により上位付加単位に空きがないと判定されたときに上
位付加単位制御レコード中の下位付加単位空き情報を参
照して下位付加単位に空きがあるかどうかを判定し空き
がなければ前記上位付加単位結合判定手段に制御を戻す
下位付加単位空き判定手段と、前記上位付加単位結合判
定手段により上位付加単位が結合されていないと判定さ
れたときに新しい上位付加単位を結合する上位付加単位
結合手段と、この上位付加単位結合手段により結合され
た新しい上位付加単位に新しい下位付加単位を所定数だ
け結合する下位付加単位結合手段とを有する。
式は、データレコードを格納するデータ格納領域と、こ
のデータ格納領域があふれた場合に前記データ格納領域
に領域を追加するためのあふれ領域とから構成されるデ
ータファイルを備えるデータベースシステムにおいて、
上位付加単位を結合する付加ポインタを有する格納単位
制御レコードが格納された格納単位からなる前記データ
格納領域と、上位付加単位を結合する付加ポインタ，下
位付加単位を結合する下位付加ポインタおよび下位付加
単位空き情報を有する上位付加単位制御レコードが格納
された上位付加単位と、上位付加単位を結合する上位付
加ポインタを有する下位付加単位制御レコードが格納さ
れた下位付加単位とに分類される付加単位からなる前記
あふれ領域と、格納単位に空きがあるかどうかを判定す
る格納単位空き判定手段と、この格納単位空き判定手段
および後記下位付加単位空き判定手段により空きがない
と判定されたときに格納単位および上位付加単位に上位
付加単位が結合しているかどうかを判定する上位付加単
位結合判定手段と、この上位付加単位結合判定手段によ
り上位付加単位が結合していると判定されたときに付加
ポインタをたどり次の上位付加単位を得る上位付加単位
取得手段と、この上位付加単位取得手段により取得され
た上位付加単位に空きがあるかどうかを判定する上位付
加単位空き判定手段と、この上位付加単位空き判定手段
により上位付加単位に空きがないと判定されたときに上
位付加単位制御レコード中の下位付加単位空き情報を参
照して下位付加単位に空きがあるかどうかを判定し空き
がなければ前記上位付加単位結合判定手段に制御を戻す
下位付加単位空き判定手段と、前記上位付加単位結合判
定手段により上位付加単位が結合されていないと判定さ
れたときに新しい上位付加単位を結合する上位付加単位
結合手段と、この上位付加単位結合手段により結合され
た新しい上位付加単位に新しい下位付加単位を所定数だ
け結合する下位付加単位結合手段とを有する。
【０００７】
【作用】本発明の空き領域検索方式では、データ格納領
域が上位付加単位を結合する付加ポインタを有する格納
単位制御レコードが格納された格納単位からなり、あふ
れ領域が上位付加単位を結合する付加ポインタ，下位付
加単位を結合する下位付加ポインタおよび下位付加単位
空き情報を有する上位付加単位制御レコードが格納され
た上位付加単位と、上位付加単位を結合する上位付加ポ
インタを有する下位付加単位制御レコードが格納された
下位付加単位とに分類される付加単位からなり、格納単
位空き判定手段が格納単位に空きがあるかどうかを判定
し、上位付加単位結合判定手段が格納単位空き判定手段
および下位付加単位空き判定手段により空きがないと判
定されたときに格納単位および上位付加単位に上位付加
単位が結合しているかどうかを判定し、上位付加単位取
得手段が上位付加単位結合判定手段により上位付加単位
が結合していると判定されたときに付加ポインタをたど
り次の上位付加単位を得、上位付加単位空き判定手段が
上位付加単位取得手段により取得された上位付加単位に
空きがあるかどうかを判定し、下位付加単位空き判定手
段が上位付加単位空き判定手段により上位付加単位に空
きがないと判定されたときに上位付加単位制御レコード
中の下位付加単位空き情報を参照して下位付加単位に空
きがあるかどうかを判定し空きがなければ上位付加単位
結合判定手段に制御を戻し、上位付加単位結合手段が上
位付加単位結合判定手段により上位付加単位が結合され
ていないと判定されたときに新しい上位付加単位を結合
し、下位付加単位結合手段が上位付加単位結合手段によ
り結合された新しい上位付加単位に新しい下位付加単位
を所定数だけ結合する。
域が上位付加単位を結合する付加ポインタを有する格納
単位制御レコードが格納された格納単位からなり、あふ
れ領域が上位付加単位を結合する付加ポインタ，下位付
加単位を結合する下位付加ポインタおよび下位付加単位
空き情報を有する上位付加単位制御レコードが格納され
た上位付加単位と、上位付加単位を結合する上位付加ポ
インタを有する下位付加単位制御レコードが格納された
下位付加単位とに分類される付加単位からなり、格納単
位空き判定手段が格納単位に空きがあるかどうかを判定
し、上位付加単位結合判定手段が格納単位空き判定手段
および下位付加単位空き判定手段により空きがないと判
定されたときに格納単位および上位付加単位に上位付加
単位が結合しているかどうかを判定し、上位付加単位取
得手段が上位付加単位結合判定手段により上位付加単位
が結合していると判定されたときに付加ポインタをたど
り次の上位付加単位を得、上位付加単位空き判定手段が
上位付加単位取得手段により取得された上位付加単位に
空きがあるかどうかを判定し、下位付加単位空き判定手
段が上位付加単位空き判定手段により上位付加単位に空
きがないと判定されたときに上位付加単位制御レコード
中の下位付加単位空き情報を参照して下位付加単位に空
きがあるかどうかを判定し空きがなければ上位付加単位
結合判定手段に制御を戻し、上位付加単位結合手段が上
位付加単位結合判定手段により上位付加単位が結合され
ていないと判定されたときに新しい上位付加単位を結合
し、下位付加単位結合手段が上位付加単位結合手段によ
り結合された新しい上位付加単位に新しい下位付加単位
を所定数だけ結合する。
【０００８】
【実施例】次に、本発明について図面を参照して詳細に
説明する。
説明する。
【０００９】図１は、本発明の一実施例に係る空き領域
検索方式の構成を示す流れ図である。本実施例の空き領
域検索方式は、格納単位空きチェックステップ１０１
と、空き判定ステップ１０２と、上位付加単位結合チェ
ックステップ１０３と、結合判定ステップ１０４と、上
位付加単位取得ステップ１０５と、上位付加単位空きチ
ェックステップ１０６と、空き判定ステップ１０７と、
下位付加単位空きチェックステップ１０８と、空き判定
ステップ１０９と、上位付加単位結合ステップ１１０
と、下位付加単位結合ステップ１１１とからなる。な
お、格納単位空きチェックステップ１０１および空き判
定ステップ１０２が格納単位空き判定手段１を、上位付
加単位結合チェックステップ１０３および結合判定ステ
ップ１０４が上位付加単位結合判定手段２を、上位付加
単位取得ステップ１０５が上位付加単位取得手段３を、
上位付加単位空きチェックステップ１０６および空き判
定ステップ１０７が上位付加単位空き判定手段４を、下
位付加単位空きチェックステップ１０８および空き判定
ステップ１０９が下位付加単位空き判定手段５を、上位
付加単位結合ステップ１１０が上位付加単位結合手段６
を、下位付加単位結合ステップ１１１が下位付加単位結
合手段７をそれぞれ構成している。
検索方式の構成を示す流れ図である。本実施例の空き領
域検索方式は、格納単位空きチェックステップ１０１
と、空き判定ステップ１０２と、上位付加単位結合チェ
ックステップ１０３と、結合判定ステップ１０４と、上
位付加単位取得ステップ１０５と、上位付加単位空きチ
ェックステップ１０６と、空き判定ステップ１０７と、
下位付加単位空きチェックステップ１０８と、空き判定
ステップ１０９と、上位付加単位結合ステップ１１０
と、下位付加単位結合ステップ１１１とからなる。な
お、格納単位空きチェックステップ１０１および空き判
定ステップ１０２が格納単位空き判定手段１を、上位付
加単位結合チェックステップ１０３および結合判定ステ
ップ１０４が上位付加単位結合判定手段２を、上位付加
単位取得ステップ１０５が上位付加単位取得手段３を、
上位付加単位空きチェックステップ１０６および空き判
定ステップ１０７が上位付加単位空き判定手段４を、下
位付加単位空きチェックステップ１０８および空き判定
ステップ１０９が下位付加単位空き判定手段５を、上位
付加単位結合ステップ１１０が上位付加単位結合手段６
を、下位付加単位結合ステップ１１１が下位付加単位結
合手段７をそれぞれ構成している。
【００１０】図２を参照すると、データファイル２００
は、データ格納領域２０１と、あふれ領域２０２とから
構成されている。データ格納領域２０１は、さらに幾つ
かの格納単位２０３から構成され、あふれ領域２０２
は、さらに幾つかの上位付加単位２０４と、下位付加単
位２０５とから構成される。格納単位２０３，上位付加
単位２０４および下位付加単位２０５には、幾つかのデ
ータレコード２０６が格納される。ただし、格納単位２
０３の１番目には格納単位制御レコード２０７が格納さ
れ、上位付加単位２０４の１番目には上位付加単位制御
レコード２０８が格納され、下位付加単位２０５の１番
目には下位付加単位制御レコード２０９が格納される。
は、データ格納領域２０１と、あふれ領域２０２とから
構成されている。データ格納領域２０１は、さらに幾つ
かの格納単位２０３から構成され、あふれ領域２０２
は、さらに幾つかの上位付加単位２０４と、下位付加単
位２０５とから構成される。格納単位２０３，上位付加
単位２０４および下位付加単位２０５には、幾つかのデ
ータレコード２０６が格納される。ただし、格納単位２
０３の１番目には格納単位制御レコード２０７が格納さ
れ、上位付加単位２０４の１番目には上位付加単位制御
レコード２０８が格納され、下位付加単位２０５の１番
目には下位付加単位制御レコード２０９が格納される。
【００１１】図３を参照すると、格納単位制御レコード
２０７は、付加ポインタ３０１から構成される。上位付
加単位制御レコード２０８は、付加ポインタ３０１，下
位付加ポインタ３０２および下位付加単位空き情報３０
３から構成される。下位付加単位空き情報３０３は、上
位付加単位２０４に結合されている所定数の下位付加単
位２０５の空きの有無を記録しており、初期値として空
きがあることが記録され、本実施例の空き領域検索方式
の外部で下位付加単位２０５にデータレコードが格納さ
れて下位付加単位２０５が満杯になったときに空きがな
くなったことが記録されるようになっている。下位付加
単位制御レコード２０９は、上位付加ポインタ３０４か
ら構成される。
２０７は、付加ポインタ３０１から構成される。上位付
加単位制御レコード２０８は、付加ポインタ３０１，下
位付加ポインタ３０２および下位付加単位空き情報３０
３から構成される。下位付加単位空き情報３０３は、上
位付加単位２０４に結合されている所定数の下位付加単
位２０５の空きの有無を記録しており、初期値として空
きがあることが記録され、本実施例の空き領域検索方式
の外部で下位付加単位２０５にデータレコードが格納さ
れて下位付加単位２０５が満杯になったときに空きがな
くなったことが記録されるようになっている。下位付加
単位制御レコード２０９は、上位付加ポインタ３０４か
ら構成される。
【００１２】次に、このように構成された本実施例の空
き領域検索方式の動作について説明する。
き領域検索方式の動作について説明する。
【００１３】データレコードを格納するための空きを探
す場合に、まず、格納単位空き判定手段１により、デー
タをデータレコード２０６として格納しようとする格納
単位２０３に空きがあるかどうかをチェックし（ステッ
プ１０１）、空きがある場合には（ステップ１０２でイ
エス）、処理を終了する。
す場合に、まず、格納単位空き判定手段１により、デー
タをデータレコード２０６として格納しようとする格納
単位２０３に空きがあるかどうかをチェックし（ステッ
プ１０１）、空きがある場合には（ステップ１０２でイ
エス）、処理を終了する。
【００１４】格納単位２０３に空きがなかった場合には
（ステップ１０２でノー）、上位付加単位結合判定手段
２により、格納単位２０３に上位付加単位２０４が結合
しているかどうかをチェックし（ステップ１０３）、結
合していなかった場合には（ステップ１０４でノー）、
上位付加単位結合手段６により、新しい上位付加単位２
０４を結合し（ステップ１１０）、下位付加単位結合手
段７により、新しい上位付加単位２０４に所定数の下位
付加単位２０５を結合して処理を終了する（ステップ１
１１）。
（ステップ１０２でノー）、上位付加単位結合判定手段
２により、格納単位２０３に上位付加単位２０４が結合
しているかどうかをチェックし（ステップ１０３）、結
合していなかった場合には（ステップ１０４でノー）、
上位付加単位結合手段６により、新しい上位付加単位２
０４を結合し（ステップ１１０）、下位付加単位結合手
段７により、新しい上位付加単位２０４に所定数の下位
付加単位２０５を結合して処理を終了する（ステップ１
１１）。
【００１５】格納単位２０３に上位付加単位２０４が結
合していた場合には（ステップ１０４でノー）、上位付
加単位取得手段３により、付加ポインタ３０１をたどっ
て次の上位付加単位２０４を得る（ステップ１０５）。
合していた場合には（ステップ１０４でノー）、上位付
加単位取得手段３により、付加ポインタ３０１をたどっ
て次の上位付加単位２０４を得る（ステップ１０５）。
【００１６】次に、上位付加単位空き判定手段４によ
り、得られた上位付加単位２０４に空きがあるかどうか
をチェックし（ステップ１０６）、空きがあった場合に
は（ステップ１０７でイエス）、処理を終了する。
り、得られた上位付加単位２０４に空きがあるかどうか
をチェックし（ステップ１０６）、空きがあった場合に
は（ステップ１０７でイエス）、処理を終了する。
【００１７】上位付加単位２０４に空きがなかった場合
には（ステップ１０７でノー）、下位付加単位空き判定
手段５により、上位付加単位制御レコード２０８内にあ
る下位付加単位空き情報３０３を参照して上位付加単位
２０４に結合されている所定数の下位付加単位２０５内
に空きがあるかどうかをチェックし（ステップ１０
８）、空きがあった場合には（ステップ１０９でイエ
ス）、処理を終了し、空きがなければ（ステップ１０９
でノー）、ステップ１０３に制御を戻す。
には（ステップ１０７でノー）、下位付加単位空き判定
手段５により、上位付加単位制御レコード２０８内にあ
る下位付加単位空き情報３０３を参照して上位付加単位
２０４に結合されている所定数の下位付加単位２０５内
に空きがあるかどうかをチェックし（ステップ１０
８）、空きがあった場合には（ステップ１０９でイエ
ス）、処理を終了し、空きがなければ（ステップ１０９
でノー）、ステップ１０３に制御を戻す。
【００１８】例えば、図４を参照すると、上位付加単位
４０１は、格納単位４００を先頭に付加ポインタ４１０
により結合されている。この図では、付加単位としては
６番目に当たる下位付加単位４０６に空きがあるが、付
加単位として１番目に当たる上位付加単位４０１の空き
を検索した後は、下位付加単位空き情報３０３を参照す
ることより付加単位として２番目，３番目および４番目
に当たる下位付加単位４０２，４０３および４０４に空
きがないことが検索することなしにわかるので、次に付
加ポインタ４１０により付加単位として５番目に当たる
上位付加単位４０５の検索を行う。上位付加単位４０５
にも空きがないので、下位付加単位空き情報３０３を参
照して下位付加単位４０６に空きがあることがわかるた
め、下位付加ポインタ４１１をたどって下位付加単位４
０６の空きを探しにいく。これにより、付加単位として
は６番目に当たる下位付加単位４０６は、前の下位付加
単位４０２，４０３および４０４内に空きがないことが
検索することなしにわかるので、付加単位としては３番
目に検索される。すなわち、従来技術によれば付加単位
を６回検索しなければならなかったが、本実施例の空き
領域検索方式によれば付加単位を３回検索するだけで空
きを求めることができる。
４０１は、格納単位４００を先頭に付加ポインタ４１０
により結合されている。この図では、付加単位としては
６番目に当たる下位付加単位４０６に空きがあるが、付
加単位として１番目に当たる上位付加単位４０１の空き
を検索した後は、下位付加単位空き情報３０３を参照す
ることより付加単位として２番目，３番目および４番目
に当たる下位付加単位４０２，４０３および４０４に空
きがないことが検索することなしにわかるので、次に付
加ポインタ４１０により付加単位として５番目に当たる
上位付加単位４０５の検索を行う。上位付加単位４０５
にも空きがないので、下位付加単位空き情報３０３を参
照して下位付加単位４０６に空きがあることがわかるた
め、下位付加ポインタ４１１をたどって下位付加単位４
０６の空きを探しにいく。これにより、付加単位として
は６番目に当たる下位付加単位４０６は、前の下位付加
単位４０２，４０３および４０４内に空きがないことが
検索することなしにわかるので、付加単位としては３番
目に検索される。すなわち、従来技術によれば付加単位
を６回検索しなければならなかったが、本実施例の空き
領域検索方式によれば付加単位を３回検索するだけで空
きを求めることができる。
【００１９】
【発明の効果】以上説明したように本発明は、付加単位
を上位付加単位と下位付加単位とに分けるとともに、上
位付加単位制御レコード中の下位付加単位空き情報を参
照して下位付加単位内に空きがあるかどうかをチェック
するようにしたことにより、データをデータレコードと
して格納するための空きを求める際に、付加単位の検索
回数が少なくて済み、空き領域の検索処理を高速化でき
るという効果がある。
を上位付加単位と下位付加単位とに分けるとともに、上
位付加単位制御レコード中の下位付加単位空き情報を参
照して下位付加単位内に空きがあるかどうかをチェック
するようにしたことにより、データをデータレコードと
して格納するための空きを求める際に、付加単位の検索
回数が少なくて済み、空き領域の検索処理を高速化でき
るという効果がある。
【図１】本発明の一実施例に係る空き領域検索方式の構
成を示す流れ図である。
成を示す流れ図である。
【図２】本実施例の空き領域検索方式におけるデータフ
ァイルの構造を示す図である。
ァイルの構造を示す図である。
【図３】図２中の格納単位制御レコード，上位付加単位
制御レコードおよび下位付加単位制御レコードの構造を
示す図である。
制御レコードおよび下位付加単位制御レコードの構造を
示す図である。
【図４】本実施例の空き領域検索方式による格納構造の
一例を示す図である。
一例を示す図である。
【図５】従来技術による格納構造の一例を示す図であ
る。
る。
【図６】従来技術による空き領域検索方式の処理を示す
流れ図である。
流れ図である。
１ 格納単位空き判定手段 ２ 上位付加単位結合判定手段 ３ 上位付加単位取得手段 ４ 上位付加単位空き判定手段 ５ 下位付加単位空き判定手段 ６ 上位付加単位結合手段 ７ 下位付加単位結合手段 ２００ データファイル ２０１ データ格納領域 ２０２ あふれ領域 ２０３ 格納単位 ２０４ 上位付加単位 ２０５ 下位付加単位 ２０６ データレコード ２０７ 格納単位制御レコード ２０８ 上位付加単位制御レコード ２０９ 下位付加単位制御レコード ３０１ 付加ポインタ ３０２ 下位付加ポインタ ３０３ 下位付加単位空き情報 ３０４ 上位付加ポインタ ４００ 格納単位 ４０１，４０５，４０９ 上位付加単位 ４０２，４０３，４０４，４０６，４０７，４０８ 下
位付加単位 ４１０ 付加ポインタ ４１１ 下位付加ポインタ ４１２ 上位付加ポインタ
位付加単位 ４１０ 付加ポインタ ４１１ 下位付加ポインタ ４１２ 上位付加ポインタ
Claims (1)
- 【特許請求の範囲】 【請求項１】 データレコードを格納するデータ格納領
域と、このデータ格納領域があふれた場合に前記データ
格納領域に領域を追加するためのあふれ領域とから構成
されるデータファイルを備えるデータベースシステムに
おいて、上位付加単位を結合する付加ポインタを有する
格納単位制御レコードが格納された格納単位からなる前
記データ格納領域と、上位付加単位を結合する付加ポイ
ンタ，下位付加単位を結合する下位付加ポインタおよび
下位付加単位空き情報を有する上位付加単位制御レコー
ドが格納された上位付加単位と、上位付加単位を結合す
る上位付加ポインタを有する下位付加単位制御レコード
が格納された下位付加単位とに分類される付加単位から
なる前記あふれ領域と、格納単位に空きがあるかどうか
を判定する格納単位空き判定手段と、この格納単位空き
判定手段および後記下位付加単位空き判定手段により空
きがないと判定されたときに格納単位および上位付加単
位に上位付加単位が結合しているかどうかを判定する上
位付加単位結合判定手段と、この上位付加単位結合判定
手段により上位付加単位が結合していると判定されたと
きに付加ポインタをたどり次の上位付加単位を得る上位
付加単位取得手段と、この上位付加単位取得手段により
取得された上位付加単位に空きがあるかどうかを判定す
る上位付加単位空き判定手段と、この上位付加単位空き
判定手段により上位付加単位に空きがないと判定された
ときに上位付加単位制御レコード中の下位付加単位空き
情報を参照して下位付加単位に空きがあるかどうかを判
定し空きがなければ前記上位付加単位結合判定手段に制
御を戻す下位付加単位空き判定手段と、前記上位付加単
位結合判定手段により上位付加単位が結合されていない
と判定されたときに新しい上位付加単位を結合する上位
付加単位結合手段と、この上位付加単位結合手段により
結合された新しい上位付加単位に新しい下位付加単位を
所定数だけ結合する下位付加単位結合手段とを有するこ
とを特徴とする空き領域検索方式。
Priority Applications (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP3178695A JP2962335B2 (ja) | 1991-06-24 | 1991-06-24 | 空き領域検索方式 |
| US08/526,307 US5737603A (en) | 1991-06-24 | 1995-09-11 | Database system capable of carrying out an efficient free area search |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP3178695A JP2962335B2 (ja) | 1991-06-24 | 1991-06-24 | 空き領域検索方式 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPH052512A true JPH052512A (ja) | 1993-01-08 |
| JP2962335B2 JP2962335B2 (ja) | 1999-10-12 |
Family
ID=16052938
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP3178695A Expired - Fee Related JP2962335B2 (ja) | 1991-06-24 | 1991-06-24 | 空き領域検索方式 |
Country Status (2)
| Country | Link |
|---|---|
| US (1) | US5737603A (ja) |
| JP (1) | JP2962335B2 (ja) |
Families Citing this family (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP3218007B2 (ja) * | 1998-03-20 | 2001-10-15 | 富士通株式会社 | インデックスの管理装置，更新方法及び管理方法並びにコンピュータ読取可能な記憶媒体 |
| EP1292948A2 (en) * | 2000-05-30 | 2003-03-19 | Koninklijke Philips Electronics N.V. | Method of and apparatus for allocating recording space on a recording medium |
| US9002860B1 (en) * | 2012-02-06 | 2015-04-07 | Google Inc. | Associating summaries with pointers in persistent data structures |
Citations (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPH0296213A (ja) * | 1988-10-03 | 1990-04-09 | Nec Corp | 階層ビットマップによる二次記憶管理方法 |
| JPH02127742A (ja) * | 1988-11-07 | 1990-05-16 | Nec Corp | 空き領域検索方式 |
Family Cites Families (11)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US4536837A (en) * | 1982-05-25 | 1985-08-20 | Elxsi | Improved disk file allocation and mapping system utilizing cylinder control blocks and file map having unbalanced tree structure |
| AU575182B2 (en) * | 1984-06-28 | 1988-07-21 | Wang Laboratories, Inc. | Self extending memory file |
| US5034914A (en) * | 1986-05-15 | 1991-07-23 | Aquidneck Systems International, Inc. | Optical disk data storage method and apparatus with buffered interface |
| US5107481A (en) * | 1988-03-16 | 1992-04-21 | Matsushita Electric Industrial Co., Ltd. | Recording area management system for writable type optional disk |
| US5021946A (en) * | 1988-06-17 | 1991-06-04 | Modular Computer Systems, Inc. | Mostly contiguous file allocation technique involving file extension |
| GB8829919D0 (en) * | 1988-12-22 | 1989-02-15 | Int Computer Limited | File system |
| US5200864A (en) * | 1989-06-28 | 1993-04-06 | International Business Machines Corporation | Combining small records into a single record block for recording on a record media |
| US5247660A (en) * | 1989-07-13 | 1993-09-21 | Filetek, Inc. | Method of virtual memory storage allocation with dynamic adjustment |
| JPH03266039A (ja) * | 1990-03-16 | 1991-11-27 | Fujitsu Ltd | フリーフォーマットデータリンク処理方式 |
| US5339411A (en) * | 1990-12-21 | 1994-08-16 | Pitney Bowes Inc. | Method for managing allocation of memory space |
| US5276840A (en) * | 1991-03-22 | 1994-01-04 | Acer Incorporated | Disk caching method for writing data from computer memory including a step of writing a plurality of physically adjacent blocks in a single I/O operation |
-
1991
- 1991-06-24 JP JP3178695A patent/JP2962335B2/ja not_active Expired - Fee Related
-
1995
- 1995-09-11 US US08/526,307 patent/US5737603A/en not_active Expired - Lifetime
Patent Citations (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPH0296213A (ja) * | 1988-10-03 | 1990-04-09 | Nec Corp | 階層ビットマップによる二次記憶管理方法 |
| JPH02127742A (ja) * | 1988-11-07 | 1990-05-16 | Nec Corp | 空き領域検索方式 |
Also Published As
| Publication number | Publication date |
|---|---|
| JP2962335B2 (ja) | 1999-10-12 |
| US5737603A (en) | 1998-04-07 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US4267568A (en) | Information storage and retrieval system | |
| US20060161539A1 (en) | Method and system of database management with shared area | |
| JPH052512A (ja) | 空き領域検索方式 | |
| US8818990B2 (en) | Method, apparatus and computer program for retrieving data | |
| JP4314126B2 (ja) | 同時実行制御方法及び装置 | |
| JPH081642B2 (ja) | キーワード検索方式 | |
| JP2706021B2 (ja) | 構造型データベースにおける検索高速化方法 | |
| CN114398378B (zh) | 确定索引代价的方法和装置 | |
| CN116521734B (zh) | 一种数据查询的方法、装置、介质及设备 | |
| CN113204523B (zh) | 底盘多楼层地图管理方法、装置、计算机设备及存储介质 | |
| JP2822677B2 (ja) | 電子回路設計装置 | |
| JPH10254887A (ja) | データベースシステム | |
| JPH0764833A (ja) | ファイル容量削減方法 | |
| JPH05120340A (ja) | ルーテイングアドレス管理方法 | |
| JPH02127742A (ja) | 空き領域検索方式 | |
| JP2747009B2 (ja) | 索引順編成ファイルのレコード追加方式 | |
| JP3085251B2 (ja) | データベース装置及びその検索方法並びにデータベース装置をコンピュータによって検索するための検索プログラムを記録した記録媒体 | |
| JPH11306183A (ja) | データベース検索システム | |
| JPH03276238A (ja) | レコード管理方式 | |
| JP2000172542A (ja) | ファイルアクセス方式 | |
| JPS63172334A (ja) | デ−タベ−スシステムのデ−タ処理方式 | |
| JPH05120347A (ja) | フアイル検索方式 | |
| JPH0520149A (ja) | Ｃａｄシステムにおける高速検索・読出方式 | |
| JPH0225974A (ja) | データベース更新検索方式 | |
| JPH06214849A (ja) | データベースシステム |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20070806 Year of fee payment: 8 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20080806 Year of fee payment: 9 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20080806 Year of fee payment: 9 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20090806 Year of fee payment: 10 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20090806 Year of fee payment: 10 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20100806 Year of fee payment: 11 |
|
| LAPS | Cancellation because of no payment of annual fees |