JPH0212460A - 索引木への並列アクセスのためのデータ・アクセス方法およびデータ処理システム - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】 Ａ、産業上の利用分野 本発明は一般にデータ処理の方法及び装置に関し、具体
的には、実施例に示すように、レコードのデータベース
管理の方法及び装置に関する。

Ｂ、従来技術 データベース管理システムまたはトランザクション処理
システムは、従来技術で周知である。これらのシステム
は、一般に複数のデータ・レコードを含むデータベース
・テーブルに迅速にアクセスするために利用される。リ
レーショナル・トランザクション処理システムは、一般
にあるデータベース・テーブルの要素が別のデータベー
ス・テーブル中の要素と関連づけられている、複数のデ
ータベース・テーブルに対するアクセスを提供する。

リレーショナル・データベースは、ユーザが１つまたは
複数の特定の要素またはフィールドを用いて、複数のデ
ータベース・テーブルに含まれるデータを探索、アクセ
ス及び変更することを可能にする。

こうしたすべてのデータベース俸システムの１つの重要
な特徴は、各データベース中の個々のレコードに対する
迅速で効率のよいアクセスを提供できることである。近
年、同時に複数のユーザによるデータベースの利用をサ
ポートするデータベース管理システムが提供され、ユー
ザは特定のデータに同時にアクセスできるようになった
。

索引ファイルは、テーブル中のレコードに対する迅速で
効率のよいアクセスを提供するため、データベース管理
プログラムによって一般に使用されている。これらの索
引ファイルは、一般にＢ木構造として構成されている。

Ｂ木について論じた参照文献には、レーマン（Ｌｅｈｍ
ａｎ）及びヤオ（Ｙａｏ）の論文「Ｂ本土での並行動作
のための効率的なロック（Ｅｆｆｉｃｉｅｎｔ　Ｌｏｃ
ｋｉｎｇ　ｆｏｒ　ＣｏｎｃｕｒｒｅｎｔＯｐｅｒａｔ
ｉｏｎ　ｏｎ　Ｂ−Ｔｒｅｅ）　Ｊ　、Ａ　ＣＭデータ
ベース。

システム紀要（ＡＣＭ　Ｔｒａｎｓａｃｔｉｏｎｓ　ｏ
ｎ　ＤａｔａｂａｓｅＳｙｓｔｅｍｓ）　、Ｖ　ｏ　ｌ
　、　６、Ｎｏ、　４．１９８１年１２月、ｐｐ、６５
０−６７０がある。Ｂ木構造を対象とする他の文献は、
コーメル（Ｃｏｍｅｒ　）の論文「遍在するＢ木（Ｔｈ
ｅ　Ｕｂｉｑｕｉｔｏｕｓ　Ｂ−Ｔｒｅｅ）　Ｊ、Ｃｏ
ｍｐｕｔｉｎｇ　５ｕｒｖｅｙｓＸＶ　ｏ　１　、　１
１、Ｎｏ、２．１９７９年６月、ｐｐ、１２１−１３７
；及びサギーブ（Ｓａｇｉｖ）　、ｒ追越しを伴うＢ本
土の並行動作（Ｃｏｎｃｕｒｒｅｎｔ　０ｐｅｒａｔｉ
ｏｎ　ｏｎ　Ｂ−Ｔｒｅｅｓ　ｗｉｔｈＯｖｅｒ　Ｔａ
ｋｉｎｇ）　Ｊ　Ｎデータベース・システム原理に関す
るＡＣＭ　　ＳＩＧＡＣＴ−８ＩＧＭＯＤシンポジウム
発表要旨集、１９８５年３月、ｐｐ。

２８−３７である。

Ｂ木構造として構成された索引ファイルは、ルート・ノ
ードから構成され、ルート・ノードから多数のレベルの
７−ドが枝別れしている。これらのノードに含まれる情
報には、次のレベルにあるノードを指すポインタまたは
データベース中のレコードを指すポインタがある。これ
らのノードは、データベース中のレコードを参照するキ
ー・レコード情報と呼ばれる他の情報を含む。レコード
・キーは、それらのノード全体を通して順番に並んでい
る。たとえば、従業員名のＡＢＣ順のリストに対する索
引木が存在する。ルート・ノードは、次のレベルのノー
ドが間接または直接に参照するレコードに関連する参照
キー付きデータを含むことになる。参照キーは、ファイ
ルされた索引、すなわち、従業員名の英字縁りに関する
情報を含む。したがうて、ルート・ノード中の配列され
たキーは、次の後続ノード・レベルを指す。言い替えれ
ば、次の後続ノードは、ＡｌＢｌＣで始まるすべての従
業員名を間接または直接的に参照できる。次の後続ノー
ドは、最初の後続ノードと平行で、姓が文字Ｄ−Ｍで始
まる従業員のレコードを含む。このレベルの最後の後続
ノードは、姓がＮ−Ｚで始まる従業員のレコードを参照
することになる。索引ファイル木を探索するとき、最後
には最下層ノードに達する。最下層ノードの内容は、記
憶域中の個々のレコードを指すレコード・キーを含む。

データベース・テーブルに対する同時アクセスを提供す
る場合、複数のトランザクションが同時に１つのレコー
ドにアクセスしようとするときに問題が起こる。具体的
には、あるユーザがレコードを変更しようとし、別のユ
ーザがこのレコードにアクセスしようとするとき、競合
状況が発生する。競合問題の１つの解決方法は、レコー
ドまたはＢ木索引の部分に対する排他的アクセス（また
はロッキング）を実現して、ユーザがそれにアクセスし
ようとするとき索引ノードまたはレコードが変更されな
いようにすることである。ロッキングについては、「索
引のロッキング及び分割（Ｉｎｄｅｘ　Ｌｏｃｋｉｎｇ
　ａｎｄ　Ｓｐｌｉｔｔｉｎｇ）　Ｊ　Ｎ　　Ｉ　８Ｍ
ディスクロージャ・プルテン、ｖｏｌ、２５、Ｎｏ。

７Ｂ１１９８２年１２月、１）Ｉ）、３７２５−３７２
９：及び「Ｂ本土の並行動作に対するロッキング・プロ
トコル（Ｌｏｃｋｉｎｇ　Ｐｒｏｔｏｃｏｌｓ　ｆｏｒ
Ｃｏｎｃｕｒｒｅｎｔ　０ｐｅｒａｔｉｏｎｓ　ｏｎ　
Ｂ−Ｔｒｅｅｓ）　Ｊ　Ｎ　Ｉ　Ｂ　Ｍディスクロージ
ャ・プルテン、ＶＯｌ、１９、Ｎｏ、１０．１９７７年
３月、Ｉ）１）、３８８７−３８８９で扱われている。

ロッキングによる解決方法の欠点は、ロックが１人のユ
ーザにアクセスを提供している間、他のユーザによるア
クセスを妨げることである。したがって、当業者には明
らかなことだが、利用するロックの数を最小に抑えない
と、システムの並行性を高めることはできない。

データ処理システムの他の重要な特徴は、データベース
内に含まれているデータを、回復可能な形で変更させる
ことができることである。すなわち、これらのシステム
は、システムの動作が様々な構成要素の障害によって中
断された場合に、特定のユーザが入力したすべての変更
が持続するか、あるいはそれらがすべて持続されないよ
うにする。

同様に、ユーザがデータベースに加えた変更を、特定の
時点に達するまで、そのユーザが取り消すことを要求す
ることもできる。したがって、ユーザによるデータベー
スへの変更は「回復可能」と呼ばれる。この概念は、「
トランザクション」処理方式で動作するデータベース・
システムに組み込まれている。トランザクションとは、
必ずしもシーケンス中のすべての中間点では整合性を維
持することなく、回復可能データベース資源の第１の整
合状態から他の整合状態に変換する一連の動作から構成
される論理的作業単位をいう。トランザクション処理シ
ステムの利用により、トランザクションが回復可能デー
タベースに対しである種の更新を実行し、トランザクシ
ョンがその通常の終了または一時的整合点に達する前に
障害が発生した場合、それらの更新が取り消される。

トランザクションは、アプリケーションが指定する動作
シーケンスの実行を含んでいるので、システム内でのそ
の存在は、一般に、特殊なｒＢＥＧＩＮ　　ＷＯＲＫＪ
動作で開始され、ｒｃＯＭＭＩＴＪまたはｒＡＢＯＲＴ
Ｊで終了する。前述のＣＯＭＭＩＴ動作及びＡＢＯＲＴ
動作は、次のような点でシステム中に原子構造をもたら
す。すなわち、ＣＯＭＭＩＴ動作は、新しい整合点に到
達し、関連するトランザクションによるすべての更新が
永続的にならなければならないことを示す。

ＡＢＯＲＴ動作は、障害が発生し、関連する特定のトラ
ンザクションによる変更が「ロール・バック」すなわち
「取り消され」なければならず、回復可能データベース
資源が以前の整合点に戻らなければならないことを示す
。

このトランザクション回復を保証するには、回復可能デ
ータに対する更新動作の効果がシステムの再起動時に適
切に反映されるように、データベース・システムが、シ
ステム障害の間中、進行中のトランザクション及びその
更新動作状態を覚えておくことができなければならない
。これは、安定な記憶域に記憶されたログに各トランザ
クションのその初めから終わりまでの進行状況と、回復
可能データ資源を変更させる動作を記録することによっ
て実行できる。このログは、その後、トランザクション
のコミットされた動作が反映され、その非コミット動作
が取り消されて、データベースが整合性を保つようにす
るための資源になる。トランザクション動作のログがデ
ータ・オブジェクトの内容を反映する場合、これらのロ
グ・レコードは、損傷または失われたデータを再構成す
るための資源にもなる。これらのシステムは一般に、レ
コードがログに書き込まれるとき、各ログ・レコードに
固有のログ順序番号（ＬＳＮ）を割り当てる。こうした
ＬＳＮは一般に昇順で割り当てられる。データベース中
のメモリのページに対する更新の記録が完了すると、そ
の更新に対応するログ・レコードのＬＳＮも通常そのペ
ージに記憶される。

上記の形式のシステムは一般に、ログ先行書込みシステ
ムと呼ばれている。ログ先行書込みシステムでは、変更
されたデータ゛の新しいバージョンを持久記憶装置上で
以前のバージョンのデータと置き換える前に、特定の動
作に対応するログ項目を、安定記憶域に物理的に書き込
まなけれはならない。本明細書では、安定記憶域とは、
システム障害の間中も損傷を受けず利用可能なままであ
る持久記憶装置を意味する。こうした例の１つは、磁気
記憶ディスクの利用である。さらに、こうしたシステム
はトランザクション状況をログに記憶し、そのコミット
された状況とそのログ・データすべてが安全に安定記憶
域に記録されるまで、いかなるトランザクションも完了
していないと見なされる。すなわち、システム障害の場
合、首尾よく完了したがシステム障害の前に更新された
資源が安定記憶域に物理的に記憶されるようにはなって
なかったトランザクション内のどの動作も、再起動処理
で回復される。さらに、こうしたシステムでは、そのト
ランザクションのすべてのログ・レコードのすべての部
分が物理ログに書き込まれるまで、トランザクションが
ＣＯＭＭＩＴ処理を完了させることはできない。

Ｃ０発明が解決しようとする問題点 したがって、本発明の目的は、索引木を介してデータベ
ース中のレコードにアクセスする効率の高い方法を提供
することである。

本発明の他の目的は、索引木を介してデータベース中の
レコードにアクセスする効率の高い方法を提供し、かつ
複数のユーザによるデータベースへの効率の高い並行ア
クセスを提供することである。

本発明のさらに他の目的は、木構造の変更によってアク
セスに遅延が起こった場合、もう−回木を走査すること
なく、データにアクセスできる、索引木を介してデータ
ベース中のレコードにアクセスする効率の高い方法を提
供することである。

Ｄ０問題点を解決するための手段 上記の目的は、以後に説明する方法で達成される。トラ
ンザクション処理システムの索引木の並行修正のための
方法及び装置が提供される。索引木は、次に下位のレベ
ルにある１つまたは複数のノードに対するキー・レコー
ド参照をもつ少なくとも１つのルート・ノードと、キー
・レコードに対するアクセスを提供する少なくとも１つ
の最下層レコードを含む。構造修正動作を含むトランザ
クションは、索引木を選択されたノードまで走査し、次
いで構造修正動作の保留状態を示す標識をセットするこ
とによって実行される。並行キー・レコードの挿入また
は削除は、保留中の構造修正動作を示す標識がない索引
木で可能であり、保留中の構造修正動作を示す標識があ
る場合には遅延される。同様に、キー・レコード削除を
含むトランザクションでは、そのトランザクションが新
しい整合点に達せず、取り消されなければならない場合
に構造修正動作が必要となる。したがって、いまだ新し
い整合点に達してない各キー・レコード削除の標識がセ
ットされ、並行キー・レコード挿入も構造修正動作の可
能性が完了するまで遅延される。構造修正動作が完了す
ると、構造修正動作を含むトランザクションが新しい整
合点に達したかどうかにかかわらず、システム障害の場
合に構造修正動作の取消しを妨げるログ・レコードが書
き込まれる。本発明の好ましいモードでは、木を２回目
に走査する必要なしにキーの挿入または削除が可能かど
うかを判定するため、遅延の後にローカル・ノードが探
索される。

Ｅ、実施例 第１図には、本発明による並行アクセス・データベース
・システムの構成図が示しである。図を見るとわかるよ
うに、並行アクセス・データベース・システムは、複数
の対話型ワーク・ステーション１０（ＩＷＳ）をもつ。

これらのワーク・ステーシロンはすべて上位プロセッサ
１２に接続されている。上位プロセッサ１２は、データ
ベース１４に接続されている。当業者には当然のことな
がら、ここではこの特定の実施例を開示するが、ローカ
ル・エリア・ネットワークを介して接続された個々のコ
ンピュータから構成される類似のシステムも利用できる
。図を見るとわかるように、対話型ワーク・ステーショ
ン１０の各操作員は、通常上位プロセッサ１２内に組み
込まれているデータベース管理システムを用いて、デー
タベース１４内に含まれるレコードを探索し、アクセス
し、変更することができる。当業者には当然のことなが
ら、データベース１４は通常、索引ファイルを利用する
ことによって検索される。索引ファイルは一般に上記の
ようにＢ木構造として構成されている。代表的なり木構
造は、少なくとも１つのルート・ノードから構成され、
複数のレベルのノードがルート・ノードから枝分れして
いる。各ノードに含まれる情報は、次の下位レベルにあ
るノードを指すポインタ、あるいは最下層レベルのノー
ドではデータベースに含まれるレコードを指すポインタ
を含む。

最下層レベルはしばしば、リーフ・ノードと呼ばれる。

第２図では、本発明によるデータベースにおける初期探
索動作を示す論理流れ図を示す。図を見るとわかるよう
に、アクセス・プログラムはステップ１００から始まり
、ステップ１０２に進んで、そこで索引ルート・ノード
がＳラッチされアクセスされる。Ｓラッチは、他の並行
ユーザに制限されたアクセスを提供する。この制限され
たアクセスにより、他のユーザは、ノード内に含まれる
情報にアクセスしてそれを読み取る能力を与えられる。

削除や変更の能力など他のアクセスは提供されない。索
引ルート・ノードは、索引の形式を識別し、この例では
レコードにアクセスするための初期方向を提供する。た
とえば、索引ルート・ノードは、索引を複数の名前に対
する昇順のアルファベット順索引として識別することが
できる。ステップ１０３で、アクセスすべき子ノードが
、親ノードの情報に基づいて識別される。ステップ１０
４で示されているように、次に、実行すべき動作が取出
し動作であるかどうかが判定される。動作が取出し動作
でない場合、すなわち、動作がレコード挿入（またはキ
ー・レコード挿入）動作またはレコード削除（またはキ
ー・レコード削除）動作である場合、アクセス・プログ
ラムはステップ１０６に進み、親ノードの下の次のノー
ドが最下層ノードすなわち「リーフ・ノード」であるか
どうか判定する。次のノードがリーフ・ノードである場
合、プログラムはステップ１１０に進み、子ノードに対
するＸラッチを獲得する。Ｘラッチは、この特定のノー
ドに対する他のすべてのアクセスを排除する排他的ラッ
チである。問題のノードにＸラッチをかけることにより
、プログラムは、他のすべてのトランザクシぼンがこの
特定のノードにアクセスすることを禁止する。

ステップ１０４に戻って、動作が取出し動作である場合
、あるいはステップ１０６に戻って、子ノードがリーフ
・ノードでない場合、アクセス・プログラムはステップ
１０８に進み、子ノードに対するＳラッチを獲得する。

次に、アクセス・プログラムはステップ１１２に進み、
探索中のレコードのキーが子ノード中の最上位キーより
も大きいかどうか判定する。もちろん、当業者には当然
のことながら、探索が空のノードに入った場合、探索中
のキーは自動的に子ノード中の最上位キーよりも大きい
と解釈される。探索中のキー・レコードが子ノード中の
最上位キーよりも大きい場合、プログラムはステップ１
１４に進み、木索引構造がラッチされているかどうか判
定する。その木がラッチされていない場合、プログラム
は、ステップ１１８に進み、そこで親ノードと子ノード
がラッチ解除され、木がラッチされる。アクセス・プロ
グラムは、次にステップ１１８からステップ１０２に戻
り、木ラッチが許可されるとすぐ動作を再開する。当業
者には当然のことながら、最適化により、動作を再試行
するときにアクセスしなければならないノードの数を減
らすことができる。

この例では、木に対するＸラッチは、木構造の変更が行
なわれていることを他のすべてのアクセスに示すために
設けられている。木に対してラッチが試みられていると
きに木のＸラッチ・アクセスが進行中である場合、試行
中のアクセスは、以前のアクセスが完了するまで待たな
ければならない。木に対するＳラッチは、構造上の変更
は行なわれていないが他のアクセスが同時に索引水にア
クセスしている可能性があることを、他のすべてのアク
セスに示すために設けられる。Ｓラッチが解除されるま
で、他の変更は行なわれない。ＳラッチやＸラッチの有
無にかかわらず、木の走査は行なえる。こうした木の走
査には、キー・レコードの削除や挿入がある。

ステップ１１４で、木がラッチされている場合、あるい
はステップ１１２で、キーが子ノード内に含まれる最上
位キーよりも大きくない場合、プログラムはステップ１
１６に進み、子ノードがリーフ・ノードかどうか判定す
る。子ノードがリーフ・ノードでない場合、プログラム
はステップ１１６に進み、親ノードのラッチを解除して
、ステップ１０３に戻る。しかし、子ノードがリーフ・
メートの場合、プログラムはステップ１２０に進み、親
ノードのラッチを解除し、次いで、ステップ１２２．１
２４及び１２６に進んで、動作が取出し、挿入、削除動
作かどうか判定する。この実施例では、これら３つの動
作のどれも試みられてない場合、プログラムは、ステッ
プ１３０に示すようにユーザに戻る。実際には、この帰
還で、実行される動作がこのプログラムでは識別不可能
であることを示すエラー・メツセージが出る。

実行される動作が取出し動作である場合、アクセス・プ
ログラムは、第３図のステップ２００に進む。第３図に
は、本発明によるデータベースにおける取出し動作を示
す論理流れ図が示されている。ステップ２００で、プロ
グラムは探索中の要求されたキーまたはデータベース中
の次に上位のキーを見つける。ステップ２０２で、プロ
グラムは、発見されたキー・レコードに対する条件付き
ロックを要求する。この例では、条件付きロックは、レ
コード・キーに対するロックを管理するデータベース管
理プログラムから要求される。「条件付き」という言葉
は、ロックがすぐには許可されない場合、こうしたロッ
クが許可されないことを示す応答が、要求側アクセス機
構に送られることを意味する。この応答は、ステップ２
０４に示す判定を行なうために利用される。ロックが許
可されていない場合、プログラムはステップ２０６に進
み、子ノードのラッチを解除し、次いでステップ２０８
に進み、キー・レコードに対する無条件ロックを要求す
る。ステップ２０８に示されている無条件ロックは、次
に進む前にこうしたロックが許可されるまでアクセス機
構が待機することを要求する。ロックが許可されると、
プログラムは、ステップ２１４で子ノードを再ラツチし
、ステップ２１６で、そのノードが変更されたかどうか
判定する。ステップ２１６でのこのノードの検査は、本
明細書では「ローカル探索」と呼び、ノードが実質的に
修正されていない場合、プログラムが、２回目に木を走
査するのではなく、ローカル・ノードから再び前へ進め
ることによって、システムの効率を高めるのに利用され
る。このことは、たとえば、ノードに記憶されているＬ
ＳＮと待機期間の前に記録されたＬＳＮを比較すること
によって判定できる。ノードが変更されていない場合、
ステップ２１８で、そのキーがローカル・ノード中の最
初のキーかどうか判定される。そうでない場合、ステッ
プ２０９に示すように見つかったキー・レコードが戻さ
れる。その後、ステップ２１０に示すように、子ノード
のラッチが解除される。当業者には明らかなように、ス
テップ２１１は、トランザクションが完成したとき、ま
たはそれ以前に実行される。

ステップ２１８を再び参照すると、見つかったキーがノ
ード中の最初のキーである場合、プログラムは第２図の
処理の始めに戻り、２回目に木の走査を行なう。それが
必要なのは、要求されたキー・レコードが見つからず、
見つかった次に上位のキーがローカル・ノード中の最初
のキーであったという可能性があるためである。見つか
ったキー・レコードに対する無条件ロックを待っている
間に遅延があった場合、それはキー・レコード挿入が次
に下位のノードで行なわれ、そのため要求されたキー・
レコードが存在するかもしれないことを示す。この場合
、要求されたキー・レコードが存在するかどうかを判定
するために再度水を走査しなければならない。

ステップ２１６を再び参照すると、ノードが変更された
場合、ステップ２２０で、そのノードが依然として以前
の子ノードと同じ木の同じレベルにあるかどうかを判定
する。変更されていない場合、木を再度走査して、要求
されたキー・レコードに対する適切な子ノードを見つけ
出さなければならない。ノードの変更の有無にかかわら
ず、ローカル・ノードの木及びレベルが同じ場合、ステ
ップ２２２で、要求されたキーまたは次に上位のキーを
見つける。次に、ステップ２２４で、プログラムが以前
と同じキーを見つけたかどうか判定する。

同じキーが見つかった場合、適切なキー・レコードが見
つかり、上記のようにステップ２０９を介して戻る。そ
うでない場合、適切な子ノードを見つけるために木を再
度走査しなければならない。

要求されたキー・レコードより少ない子ノード内にキー
がある場合、ステップ２２６で、以前に見つかったキー
・レコードに対するロックが解除されて、ステップ２０
０に戻り、再び、要求されたキーまたは次に上位のキー
を見つけ出す。

第４図を参照すると、本発明によるデータベースにおけ
る挿入動作を示す論理流れ図が示しである。当業者には
自明であるが、挿入すべきキー・レコードは、挿入動作
が始める前に必要ならＸロックされる。この動作は、コ
ンピュータ・メモリにレコードを挿入するのに利用され
、索引の当該ノードを更新する索引にキーを挿入して、
他のトランザクションが新しく挿入されたレコードにア
クセスできるようにする。

ステップ３００で、まず、挿入すべきキー・レコードが
最下層ノードすなわちリーフ・ノードにフィツトするか
どうかが判定される。フィツトする場合、プログラムは
ステップ３０４に進み、挿入されるキーより大きい次の
キーを見つける。次のキーがメート中にない場合、アク
セス・プログラムに、次の後続位置にあるリーフ・ノー
ドが指される。次の後続位置にあるリーフ・ノードがな
い場合、アクセス・プログラムは空白（ｎｕｌｌ　）標
識を見つける。次いで、ステップ３０８で、アクセス・
プログラムは、次のキー・レコードに対する条件付きＸ
ロックを要求する。ステップ３１２で、この条件付きＸ
ロック要求が許可されているかどうか判定が行なわれる
。許可された場合、ステップ３３０で、ＳＭＯビットが
ゼロに等しいかどうか判定する。

ＳＭＯビットは、構造修正動作を含むトランザクション
の保留状態によって設定される、リーフ・ノード中にあ
るフラグである。本発明によると、このフラグ・ビット
は、第２のユーザの構造修正動作が保留中に、第１のユ
ーザの動作を遅延させるのに利用される。第２のユーザ
の構造修正動作が完了すると、本発明によれば、システ
ム障害の場合にも構造修正は取り消されず、その後、Ｓ
ＭＯビットがゼロに設定される。

次に、ステップ３３２で、削除ビットがゼロに等しいか
どうか判定する。本発明の他の重要な態様によると、削
除ビットは各リーフ・ノードに設けられ、問題のノード
が、新しい整合状態をまだ実現していない削除動作に関
与している、または関与していたかどうかを示す。削除
動作の取消しが必要な場合、整合状態を実現する前に、
以前に削除されたビットを再挿入するのに十分なスペー
スがノード中に残ってない場合、以前に削除されたレコ
ードのその後の挿入に、ノードの分割が必要であること
から考えて、このことを認識することは重要である。索
引水の構造のこの変更は、並行動作に悪影響を及ぼすこ
とがある。

したがって、削除ビットが１に等しい場合、試行中のキ
ー・レコード動作は、新しい整合点に達するまで遅延さ
れなければならない。これらの両条件が満たされる場合
、ステップ３３４で、すべてのログ先行書込みシステム
に必要な挿入動作の記録が行なわれる。その後、ステッ
プ３１８で問題の子ノードに対するキーを挿入する。ス
テップ３２４で、次のレコードとキー・レコードのロッ
クが解除される。さらに、ステップ３２９ですべてのラ
ッチが解除され、ステップ３２５でプログラムがユーザ
に戻る。

ステップ３３０及び３３２を再び参照すると、ＳＭＯビ
ットが１であるか、または削除ビットが１で、構造修正
動作が保留中であるか、または取消し中に構造修正動作
が必要となる可能性があることを示す場合、アクセス・
プログラムは、ステップ３３６に示すように、索引水に
対する条件付きＳラッチを要求しなければならない。ス
テップ３３８で、ラッチが許可されているかどうかが判
定され、許可されている場合、ステップ３４０で、ステ
ップ３３４及び３１８に関して上記で述べたように、挿
入を記録し実行する前に、ＳＭＯビットと削除ビットが
ゼロに設定される。

ステップ３３６で木に対して要求された条件付きＳラッ
チが許可されていない場合、ステップ３４２で、そのノ
ードのラッチが解除され、ステップ３４４で、木に対す
る無条件Ｓラッチが要求される。時間が経過して無条件
Ｓラッチが許可された後、ステップ３４６で問題のノー
ドが再ラツチされる。次にステップ３４８で、次にノー
ドがローカルに探索されて、ノードが実質的に変更され
たかどうかが判定される。ノードが変更されていない場
合、ステップ３３４と３１８で、挿入すべきキー・レコ
ードが記録され挿入される。

以前に見つかったノードが実質的に変更されている場合
、ステップ３５０で、見つかったノードが同じ索引木の
同じレベルにあるかどうかが判定される。そうでない場
合、プログラムは第２図に示された探索動作に戻り、適
切なノードを判定するために木が再び走査される。

見つかったノードが変更されているが、木及びレベルは
同じである場合、ステップ３５２で挿入すべきキーがロ
ーカル・ノード上で境界を定められている（ｂｏｕｎｄ
ｅｄ）かどうかが判定される。その場合、再度木を走査
する必要はなく、ステップ３３４及び３１８で挿入が記
録され実行される。

そうでない場合、上記のように、第２図の探索手順が再
び始まり、キー挿入のための適切なノードを見つけて識
別する。

ステップ３１２を再び参照すると、次のキー・レコード
に対する条件付きＸロックが許可されない場合、プログ
ラムはステップ３１６に進み、そこで子ノードのラッチ
を解除し、次に、ステップ３２２に進み、次のキー・レ
コードに対する無条件Ｘロックを要求する。無条件Ｘロ
ックが許可された後、ステップ３５４でノードの再ラツ
チが行なわれ、ステップ３５６でノードを検査して、待
機期間中にノードが実質的に変更されたかどうかが判定
される。ノードが変更されていない場合、ステップ３６
０で、挿入キーがノード上で境界を定められているかど
うかが判定される。その場合、ステップ３３４及び３１
８で挿入が記録され実行される。

ノードが変更されている場合、ステップ３５８で、ノー
ドの木及びレベルが同じであるかどうかが判定される。

そうでない場合、第２図に示す探索手順が、適切なノー
ドを見つけるために再び繰り返される。ノードの木及び
レベルが同じままである場合、ステップ３６０で、挿入
すべきキー・レコードがローカル・ノード上で境界を定
められているかどうかが判定される。境界を接していな
い場合、上記と同様に第２図の探索手順が繰り返される
。挿入すべきキー・レコードがローカル・ノードと境界
を接している場合、プログラムはステップ３００に戻り
、上記に列挙した手順に従う。

ステップ３００（こ戻って、挿入すべきキー・レコード
がリーフ・ノードに当てはまらない場合、プログラムは
ステップ３０２に進み、索引木に対する条件付きＸラッ
チを要求する。次いでステ、ツブ３０６で、条件付きラ
ッチが許可されているかどうかが判定される。許可され
てない場合、プログラムはステップ３１０に進み、子ノ
ードのう・ソチを解除し、次いで、ステップ３１４に進
み、索引木に対する無条件Ｘラッチを要求する。索引木
に対する無条件Ｘラッチが許可された後、ステップ３６
２でノードが再ラツチされ、次にステップ３６４で、待
機期間中にノードが変更されたかどうかを判定するため
、ローカル・ノードが検査される。

ノードが変更された場合、ステップ３２０で、後でより
詳しく説明するノード分割アルゴリズムが呼び出され、
その汲水がラッチを解除され、挿入プロセスはステップ
３００に戻り、キー値に応じて、新しく設定されたノー
ドまたは元々見つけ出されたノードにキー・レコードを
挿入する。見つけられたノードが変更されている場合、
ステ、ツブ３６６で、ローカル・ノードの木及びレベル
が同じままであるかどうかが判定される。同じでない場
合、上記のように、プログラムは第２図に示す探索処理
に戻り、適切なリーフ・ノードを見つけ出す。ローカル
・ノードの木及びレベルが同じままである場合、ステッ
プ３６８で、挿入すべきキー・レコードがローカル・ノ
ード上で境界を定められているかどうかが判定される。

範囲外の場合、第２図に示す探索手順が繰り返される。

挿入すべきキー・レコードがノード上で境界を定められ
ている場合、プログラムはステップ３００に戻り、キー
・レコードを挿入するのに必要なステップに進む。

次に第５図を参照すると、本発明によるデータベースに
おける削除動作を示す論理流れ図が示されている。当業
者には自明のことだが、削除動作が始まる前に、必要な
ら削除すべきキー・レコードがＸロックされる。ステッ
プ４００で、プログラムは削除すべきキーより大きな次
のキーを見つける。ステップ４０２で、プログラムは、
この次のレコード・キーに対する条件付きＸロックを要
求する。プログラムはステップ４０４に進み、条件付き
Ｘロックが許可されているかどうか判定する。要求され
た条件付きＸロックが許可されなかった場合、プログラ
ムは、ステップ４０６で子ノードのラッチを解除し、ス
テップ４１０で次のキー・レコードに対する無条件ロッ
クを要求する。

無条件ロックが許可されるまで待機した後、ステップ４
５６で、子ノードが再ラツチされる。その後、ステップ
４５８で、待機期間中にノードが実質的に変更されたか
どうか判定するため、ローカル・ノードが検査される。

変更されてない場合、ステップ４６２で、削除すべきキ
ーが依然として存在しているかどうかが判定される。変
更されている場合、プログラムはステップ４００に戻り
、削除処理を開始する。変更されてない場合、第２図の
探索処理が繰り返される。

ローカル・ノードが実質的に変更されている場合、ステ
ップ４６０で、ノードの木及びレベルが同じままかどう
かが判定される。同じままでない場合、プログラムは、
第２図に示す探索処理に戻る。ローカル・ノードの木及
びレベルが同じままである場合、ステップ４６２で、削
除すべきキーがローカル・ノード内に依然存在している
かどうかが判定される。存在してない場合、プログラム
は、適切なリーフ・ノードを見つけるため、再び第２図
に示す探索手順に戻る。しかし、削除すべきキーがロー
カル・ノードにある場合、プログラムはステップ４００
に戻り、削除処理を開始する。

ステップ４０４に戻って、次のキー・レコードの条件付
きＸロックが許可されると、ステップ４３２で、削除す
べきキーがローカル・ノード上で境界を定められている
（　ｂｏｕｎｄｅｄ）かどうかが判定される。その場合
、ステップ４３４で、問題のリーフ・ノードが、まだ完
成してない構造修正動作に関与していないことを示すＳ
ＭＯビットがゼロに等しいかどうかが判定される。ＳＭ
Ｏビットがゼロに等しい場合、ステップ４３６で問題の
ノードが、新しい整合点にまだ達していないトランザク
ション中に削除されたキー・レコードをもっていること
を示す削除ビットが１に設定される。その後、ステップ
４３７に示すように、削除すべきキー・レコードが記録
され、ステップ４０８で、そのキー・レコードが削除さ
れる。

削除すべきキー・レコードがリーフ・ノート上で境界を
定められていない場合、またはＳＭＯビットがゼロに等
しくない場合、ステップ４３８で、索引水に対する条件
付きＳラッチが要求される。

ステップ４４０で、要求されたラッチが許可されている
と判定された場合、ステップ４４２で、ＳＭＯビット及
び削除ピットがゼロに設定され、ステップ４３７と４０
８に従って削除が記録され実行される。索引水に対して
要求された条件付きＳラッチが許可されない場合、ステ
ップ４４４で、ノードのラッチが解除され、ステップ４
４６で、索引水に対する無条件Ｓラッチが要求される。

無条件Ｓラッチが許可されるまで待った後、ステップ４
４８で、子ノードが再ラツチされ、ステップ４５０で、
ノードが待機期間中に実質的に変更されたかどうか判定
するため、ノードのローカル探索が行なわれる。変更さ
れていない場合、プロダラムはステップ４４２に戻り、
そこでＳＭＯビット及び削除ビットがゼロに設定され、
ステップ４３７と４０８に従って削除が記録され実行さ
れる。

ローカル・ノードが実質的に変更されている場合、ステ
ップ４５２で、ノードが依然として同じ木及び同じレベ
ルにあるかどうかが判定される。ノードが依然として同
じ木及び同じレベルにある場合、ステップ４５４で、削
除すべきキー・レコードがノード内にあるかどうかが判
定される。その場合、プログラムはステップ４００に戻
り、削除処理を開始する。ローカル・ノードが同じ木ま
たは同じレベルにもはやない場合、あるいは削除すべき
キー・レコードがない場合、プログラムは第２図に示し
た探索手順に戻り、問題の動作に応じた適切なリーフ・
ノードを決定する。

ステップ４０８に従ってキー・レコードを削除した後、
プログラムはステップ４１２に進み、そのキー・レコー
ドを以前に含んでいたノードが現在空であるかどうか判
定する。空でない場合、プログラムはステップ４２１で
ノードのラッチを解除し、ステップ４１４で操作員に戻
る。一方、削除されたキー・レコードを以前に含んでい
たノードが空の場合、ステップ４１６で、索引水に対す
る条件付きＸラッチが要求される。次に、ステップ４１
８で、プログラムは、条件付きラッチが許可されている
かどうか判定する。許可されている場合、プログラムは
ステップ４２４に進み、ノート圧縮アルゴリズムを実行
する。このアルゴリズムについては、後でより詳しく説
明する。ノード圧縮アルゴリズムは、索引水中の先行ノ
ードがら空ノードに対する参照及び空ノードを除去する
。

その後、ステップ４２６で、木のラッチを解除し、ステ
ップ４３０でプログラムは操作員に戻る。

ステップ４１８に戻って、索引水に対して要求された条
件付きＸラッチが許可されていない場合、ステップ４２
０で、子ノードのラッチが解除され、ステップ４２２に
示すように木に対する無条件Ｘラッチが要求される。索
引水に対する無条件Ｘラッチが許可されるのを待った後
、ステップ４２３で、問題のノードが待機期間中に変更
されたかどうかが判定される。変更された場合、プログ
ラムは、ステップ４２５で操作員に戻り、そうでない場
合、上記のノード圧縮アルゴリズムとその後のステップ
が実行される。

次に第６図を参照すると、本発明によるデータベースに
おけるキー・レコード挿入の取消し動作を示す論理流れ
図が示しである。当業者には当然のことながら、キー・
レコードがトランザクションに挿入され、システム障害
が新しい整合点に達する前に発生した場合、キー・レコ
ード挿入をロールバックする、すなわち「取り消す」必
要がある。

これは、キー・レコード削除と等価である。第８図に示
すように、キー・レコード挿入の取消しの最初のステッ
プは、ステップ５００に示すように、ログ・レコードか
ら適切なノードを決定することである。次に、ステップ
５０２に示すように、適切なノードがＸラッチされ、ス
テップ５０４で、システムの再起動の結果として取消し
が実行されている場合、ＳＭＯビットと削除ビットがゼ
ロに設定される。次にステップ５０６で、問題のノード
が取消しの原因となったシステム障害の前と同じ木及び
同じレベルにあるかどうかが判定される。

同様に、ステップ５０８で、削除すべきキーがノード内
にあるかどうかが判定される。どちらの場合も、木とレ
ベルが変化するか、またはキーが存在してない場合、プ
ログラムは第２図に示す探索手順に戻らなければならな
い。次に、ステップ５１０で、問題のノードが依然とし
て保留中の構造修正動作に関与していることを示すＳＭ
Ｏビットが１であるかどうかが判定される。そうでない
場合、ステップ５１２で、削除すべきキーがノード中の
最初のキーまたは最後のキーであるかどうかが判定され
る。ＳＭＯビットが１に等しいか、または削除すべきキ
ーが当該のノード中の最初のキーである場合、ステップ
５１４で、木に対する条件付きＳラッチが要求される。

次に、ステップ５１６で、ラッチが許可されているかど
うかが判定され、許可されている場合、ステップ５１８
で、ＳＭ。

ビットと削除ビットがゼロに設定される。

ＳＭＯビットが１に等しくなく、削除すべきキーが当該
のノード中の最初のキーでない場合、ステップ５２０で
、キー・レコード削除を実行する前にログ・レコードが
書き込まれる。その後、ステップ５２２に示すようにキ
ー・レコードが削除され、ステップ５２８で、ノードが
現在空であるかどうかが判定される。そうでない場合、
ステップ５３０で、プログラムは操作員に戻る。実際に
キー・レコードの削除でノードが空になった場合、ステ
ップ５３２で、プログラムはノード圧縮アルゴリズムに
進み、そのステップの完了後、こうしたステップ５３４
で木のラッチが解除され、ステップ５３６でプログラム
は操作員に戻る。

ステップ５１６に戻って、木に対して要求された条件付
きＳラッチが許可されていない場合、ステップ５２４で
、ノードのラッチが解除され、ステップ５２６に示すよ
うに、木に対する無条件Ｓラッチが要求される。その後
、プログラムはステップ５０２に戻り、無条件Ｓラッチ
が許可された後、キー挿入動作の取消しを開始する。

第７図を参照すると、本発明によるキー・レコード削除
の取消しを示す論理流れ図が示しである。

当業者には当然のことながら、索引水を整合点に維持す
るために、完了の前にシステム障害または他のエラー条
件が発生した場合、新しい整合状態にまだ達してない動
作をロールバックする、すなわち「取り消す」ことが定
期的に必要になる。

キー・レコード削除の取消しは、キー・レコード挿入と
ほぼ同じ方式で動作する。図かられかるように、最初の
ステップは、ログ先行書込みプロトコルに従って維持さ
れたログ・レコードから適切なノードを決定することで
ある。これはステップ６００に示されている。次にステ
ップ６０２で、そのノードのＸラッチが行なわれ、ステ
ップ６０４で、システム障害の後の再起動の結果として
取消しが実行されている場合、ＳＭＯビットと削除ビッ
トがゼロに設定される。

ステップ６０６で、ノードが、取消しの原因が発生する
前の状態と同じ木及び同じレベルにあるかどうかが判定
され、そうでない場合、第２図に示す探索手順が繰り返
される。次に、ステップ６０８で、取消し動作によって
削除すべきキーがノードと境界を接しているかどうかが
判定される。そうでない場合は、やはり、第２図に示す
探索手順が繰り返される。

削除すべきキーがローカル・ノードと境界を接している
場合、ステップ６１０で、上記のように、問題のノード
が保留中の構造修正動作に関係していることを示すＳＭ
Ｏビットが１に等しいかどうかが判定される。ＳＭＯビ
ットが１に等しくない場合、ステップ６１２で、削除ビ
ットが１に等しいかどうかが判定され、問題のノードが
、整合点にまだ達してないトランザクション中に削除さ
れたレコードを最近もっていたかどうかが判定される。

ＳＭＯビットも削除ビットも１に等しくない場合、プロ
グラムはステップ６２４に進み、挿入すべきキー・レコ
ードが適切なノードにフィツトするかどうかを判定する
。ステップ６１０と６１２を再び参照すると、ＳＭＯビ
ットが１に等しいか、または削除ビットが１に等しい場
合、ステップ６１４で、木に対する条件付きＳラッチが
要求される。次にステップ６１６で、Ｓラッチが許可さ
れているかどうかが判定され、許可されている場合、ス
テップ６２２で、ＳＭＯビットと削除ビットがゼロに等
しく設定され、その後、ステップ８２４に関して述べた
ように、挿入すべきキーがノードにフィツトするかどう
かが判定される。

ステップ６１４で木に対して要求された条件付きＳラッ
チが許可されていない場合、ステップ６１８で、ノード
・ラッチが解除され、ステップ６２０で、木に対する無
条件Ｓラッチが要求される。

木に対する無条件Ｓラッチが許可された後、プログラム
はステップ８０２に戻り、そこでノードがＸラッチされ
、処理が再び開始する。

ステップ６２４に戻ると、挿入すべきキー・レコードが
当該のノードに当てはまらない場合、ステップ６２６で
ノード分割アルゴリズムが呼び出される。ノード分割ア
ルゴリズムが完了した後、ステップ６２８で木のラッチ
が解除され、プログラムは再びステップ６０２に戻り、
再び処理を開始する。挿入すべきキー・レコードが当該
のノードに当てはまる場合、ステップ６３０で、ログ・
レコードが書き込まれ、その後ステップ６３２でその挿
入が実行される。その後ステップ６３４で、プログラム
はユーザに戻る。

第８図には、本発明によるノード分割アルゴリズムを示
す論理流れ図が示されている。図を見るとわかるように
、ノード分割アルゴリズムは、適切なログ順序番号を記
憶することによって始まる。

その番号は、ノード分割動作の直前に実行された動作に
関連する。当業者には当然のことながら、順方向伝播ト
ランザクションでは、これは、ノード分割アルゴリズム
の直前に実行されたログ順序番号になる。しかし、ノー
ド分割動作を必要とする取消しでは、このログ順序番号
は、問題の命令の直後に行なわれた動作のログ順序番号
になる。

次に、ステップ７０２に示すように、木がＸラッチされ
、ステップ７０４に示すように、新しいノード要件がロ
グ先行書込みプロトコルに従って記録される。ステップ
７０６で、新しいノードが獲得され、ステップ７０８で
、必要に応じて新しいノードと古いノードのＸラッチが
行なわれる。ステップ７１０で、先行書込みプロトコル
に従って、キー位置の変更がログに書き込まれ、その後
にステップ７１２で、キーの一部分が古いノードから新
しいノードに移される。ステップ７１２で、問題のノー
ドがまだ完了してない構造修正動作に関連することを並
行ユーザが判定できるように、影響を受けたリーフ・ノ
ード中でＳＭＯビットが１に設定される。

次に、ステップ７１４に示すように、古いノードと新し
いノードのラッチが解除され、ステップ７１６に示すよ
うに、親ノードがＸラッチされる。

親ノード中に必要な変更があれば、ステップ７１８でそ
れが記録され、ステップ７２０で親メートが更新される
。ステップ７２２に示すように、親ノードのラッチが解
除され、ダミー補償ログ・レコード（ＣＬＲ）が、記憶
された適切なログ順序番号（ＬＳＮ）を指すログ・メモ
リに書き込まれる。当業者には当然のことながら、補償
ログ・レコードとは、取消しが行なわれる場所と時間を
規定するログであり、その時点で何がどれぐらい取り消
されるかを識別する。このようにして、実行されたばか
りの構造修正動作は、関連するトランザクションが新し
い整合点に達する前にシステム障害が発生しうるにも関
わらず、取り消されない。

こうした障害が発生した場合、見かけＣＬＲレコードに
よって、取消しアルゴリズムは、構造修正動作の完了の
始めの直前に行なわれた動作にジャンプする。すなわち
、構造修正動作に関するトランザクションは、構造修正
動作が完了されてない場合は、そっくりロールバックさ
れるが、通常の処理中システム障害またはトランザクシ
ョン打切りの前に構造修正動作が完了していた場合は、
非構造修正動作に関してだけロールバックされる。この
ため、コミット状況を実現するための構造修正を含むト
ランザクションの障害にも関わらず、完了した構造修正
の取消しが有効に禁止されることに留意されたい。この
ようにして、コミット状態を実現するためにトランザク
ションを必要とせずにシステムが構造修正をコミットで
きるので、より高いレベルの並行性が得られる。

最後に、第９図を参照すると、本発明によるノード圧縮
アルゴリズムを示す論理流れ図が示しである。図を見る
とわかるように、メート分割アルゴリズムで示したのと
同様に、処理はステップ８００で、適切なログ順序番号
（ＬＳＮ）を記憶することから始まる。次に、ステップ
８０２で木がＸラッチされ、ステップ８０４で必要に応
じて隣接ノードと古いノードがＸラッチされる。

先述のログ先行書込みプロトコルに従って、ステップ８
０６でノード圧縮キーの移動が記録され、ステップ８０
８で、隣接するノードから空のノードにキーが移される
。ステップ８０８で、この特定ノードに関して保留中の
構造修正動作が進行中であることを並行ユーザに示すＳ
ＭＯビットが１に設定される。次にステップ８１０で、
順方向ノード・ポインタが更新され、ステップ８１２で
、隣接するノードが除去される。

次にステップ８１４で子ノードと隣接ノードのラッチが
解除され、ステップ８１６で親ノードがＸラッチされ、
その後親ノードが変更される。ステップ８１８で、親ノ
ードに対する変更が記録され、その後にステップ８２０
でそうした変更が実行される。その後ステップ８２２で
、親ノードのラッチが解除され、記憶された適切なログ
順序番号（ＬＳＮ）を指すダミー補償ログ・レコード（
ＣＬＲ）が書き込まれる。

前述したノード分割アルゴリズム及びノード圧縮アルゴ
リズムでは、当業者には当然のことながら、ＳＭＯビッ
トは、構造修正動作が完了した後いつでも適切などんな
方式ででもゼロに設定される。以上の記載により、当業
者には理解できるように、本出願人等は、構造修正動作
が保留中である領域以外の木全体でキー・レコードの挿
入及び削除の実行を可能にすることによって、高度な並
行性を備えた、トランザクション処理システムにおける
索引木の並行修正の方法及び装置を提供した。

さらに、構造修正動作が完了すると、見かけ補償ログ・
レコードを利用して、問題のトランザクションが新しい
整合点に達する前に、システム障害に関わらず、構造修
正動作は取り消されないようにする。このようにして、
索引木の物理的整合性が維持され、この維持に基づく高
度な並行性により、複数の並行ユーザによる索引木の利
用度が高まる。

同様に、削除が行なわれたばかりのノード内のフラグ・
ビットを利用して、取消し中に発生する構造修正動作の
影響を受ける恐れのあるキー・レコード挿入が遅延され
る。レコード削除を組み込んでいるトランザクションが
整合状態に達すると、削除ビットが再度ゼロに設定され
、遅延されたキー・レコード挿入が進行できるようにな
る。

当業者には理解できるように、本明細書に記載された動
作は、一般的にリーフ・モードで行なわれるように示さ
れているが、こうしたノード分割動作及びノード圧縮動
作によってしばしば、同様の動作がルート・ノードに向
かって木をさかのぼって伝播される。本明細書で開示し
た方法は、こうしたより高いレベルの動作にも同様に適
用できることを理解されたい。

本発明を好ましい実施例に関して詳しく図示し説明した
が、当業者には当然のことながら、本発明の精神と範囲
を逸脱せずに形態及び細部に様々な変更を加えることが
できる。

Ｆ１発明の効果 本発明によれば、索引木を介してデータベース中のレコ
ードにアクセスする効率の高い方法が提供される。

【図面の簡単な説明】

第１図は、本発明による並行アクセス・データベース・
システムの構成図である。 第２図は、本発明によるデータベースにおける初期探索
動作を示す論理流れ図である。 第３図は、本発明によるデータベースにおける取出し動
作を示す論理流れ図である。 削除動作を示す論理流れ図である。 第６図は、本発明によるキー・レコード挿入の取消し動
作を示す論理流れ図である。 第７図は、本発明によるデータベースにおけるキー・レ
コード削除の取消しを示す論理流れ図である。 第８図は、本発明によるノード分割アルゴリズムを示す
論理流れ図である。 第９図は、本発明によるノード圧縮アルゴリズムを示す
論理流れ図である。 １０・・・・対話型ワーク・ステーション、１２・・・
・上位プロセッサ、１４・・・・データベース。 出願人　　インターナショナル・ビジネス・マシーンズ
ｅコーポレーション 代理人　　弁理士　　頓　　宮　　孝 （外１名） 第１図 ！’Ｔ４ｂ図 第５ｂ図 ６ａ 第９図

Claims (2)

【特許請求の範囲】
1. （１）少なくとも１つの構造変更動作を含む複数の動作
   を含むトランザクションを実行する間に索引木に並行的
   にアクセスすることを可能にする方法であって、 上記複数の動作を順次に実行し、 上記構造変更動作前に実行された選択された動作の系列
   の標識を記憶し、 上記構造変更動作の完了時に上記選択された動作の上記
   記憶された標識を指すレコードを書込み、上記構造変更
   動作の完了前に上記トランザクションの終了が起きた時
   は上記複数の動作の各々をロール・バックし、 上記構造変更動作の完了後に上記トランザクションの終
   了が起きた時は構造変更に関係しない動作のみをロール
   ・バックするステップを含む 索引木への並行アクセス方法。
2. （２）少なくとも１つの構造変更動作を含む複数の動作
   を含むトランザクションを実行する間に索引木を通じて
   データにアクセスする並行アクセス・データベース・シ
   ステムであって、 上記複数の動作を順次に実行する手段と、 上記構造変更動作の前に実行された選択された動作の順
   次位置の標識を記憶する手段と、上記構造変更動作の完
   了時に上記選択された動作の順次位置の上記記憶された
   標識を指す補償ログ・レコードを記憶する手段と、 上記構造変更動作の完了前に上記トランザクションが終
   了する時は上記複数の動作の各々をロール・バックし、
   かつ上記構造変更動作の完了後に上記トランザクション
   が終了する時は構造変更に関係しない動作のみをロール
   ・バックする制御手段とを有するデータベース・システ
   ム。