JPH0786843B2

JPH0786843B2 - データ構造更新方法

Info

Publication number: JPH0786843B2
Application number: JP1260391A
Authority: JP
Inventors: ジエラルド・パークス・ボズマン
Original assignee: インターナシヨナル・ビジネス・マシーンズ・コーポレーシヨン
Priority date: 1988-10-07
Filing date: 1989-10-06
Publication date: 1995-09-20
Anticipated expiration: 2010-09-20
Also published as: EP0362709A2; US5089952A; EP0362709A3; JPH02144637A

Description

【発明の詳細な説明】 A.産業上の利用分野本発明は、一般にコンピュータ・データの２次記憶装置
のデータ構造に関し、具体的には、データ構造の読取り
装置の並列性を増加させる最適化された構造に関する。

B.従来技術現代のコンピュータ・システムは、大量のデータの中か
らやっと見つけることができる特定のデータを探索し使
用するのにしばしば用いられる。データの構成とそれに
アクセスする方法は、効率的な技術を採用すれば性能と
スループットが大幅に増大するので、特に重要である。

多くのコンピュータ・ソフトウェア及びシステムでは、
高度の並列処理を用いて、すなわち複数のプロセスをい
つでも活動状態にすることによって、高い性能及びスル
ープット利得が得られる。この並列処理の中では、整合
性のないデータ構造が作成されるような形で各プロセス
が相互作用しないようにすることが、依然として必要で
ある。通常、「ロッキング」と呼ばれる技術を使って、
２つのプロセスが同時に同じデータ構造を変更すること
ができないようにしている。ロッキングは、データを読
み取っているが変更はしていないプロセスがもはや存在
しないようにするのにも使用される。複数の読取り装置
が書込みプロセスの不在時に許されることもしばしばあ
る。

実際、読取り装置がデータ構造の同じ部分で書込み側プ
ロセスとして動作することはほとんどない。さらに、純
粋な読取り側プロセス、すなわち、更新する意図のない
読取り側プロセスは、通常「弱い探索側プロセス」であ
る。読取りプロセスが、抽象的な相互関係をもつことも
ある複数のオブジェクトではなくて、単一のオブジェク
ト（たとえば、レコード）を探索するときには特にそう
である。

なお、本明細書中で読取り側プロセス、書込み側プロセ
ス、更新側プロセス、及び探索側プロセスという用語を
用いるが、それらは各々対象のデータ構造に対して、読
取り、書込み、更新、及び探索を行なうプロセス、タス
ク、プログラム、その他のルーチンまたは装置を意味す
る。

熟練したコンピュータ・プログラマやシステム設計者に
は周知のように、データ・ファイルを構造化するための
多くの技術が提案されている。どのファイル構成を選択
するかは、実行されるファイル探索のタイプによって決
まる。おおまかに言うと、順次的およびランダムの２つ
のタイプのファイル探索が必要である。

一般的なタイプの多くのファイル構成では探索側プロセ
スを、ファイルの探索される項目を含む部分に導くこと
により探索側プロセスの速度を上げる、データに対する
インデックスがある。

通常、一義的なキーがファイル中の各項目に割り当てら
れ、そのキーを指定することによって検索が実行され
る。ファイルは、そのファイル情報とそれに一義的に関
連するキーを含むｎ個のレコードの集合と考えることが
できる。キーは一義的にレコードを識別するものと仮定
する。

ユーザは、ファイル・レコードの挿入、削除、検索及び
更新を含めて、ファイルに対して様々なタイプのトラン
ザクションを行なうことができる。４つの基本操作がこ
れらのトランザクションを支援している。

1.INSERT:そのキーが一義的であることを保証する新し
いレコードを追加する。

2.DELETE:キーによって指示されるレコードを削除す
る。

3.FIND:キーによって指示されるレコードを検索する。

4.NEXT:次の情報グループを検索する。

BayerとMcCreightの論文「大型順序付けインデックスの
構成と維持（Organization and maintenance of large
ordered indices）」、Acta Informatica Vol.1（1972
年）、pp.173-189で紹介されて以来、Ｂ木は、動的ラン
ダム・アクセス・ファイルの大型順序付けインデックス
を構成し維持する方法として普及している。元のアルゴ
リズムのいろいろな変形も普及している。本発明は、葉
探索Ｂ木に適用される。これは、H.Wedekindによって開
発された変形である。Klimbie、J.W.及びKoffeman、K.
L.編「データベース・マネジメント（Data Base Manage
ment）」、North-Holland、1974年刊、pp.385-397に所
載の、Wedekind、H.の論文「データベース・システムに
おけるアクセス経路の選択について（Oh the selection
of access paths in a data system）」を参照のこ
と。これは、Comer、D.の論文「遍在するＢ木（The ubi
quitous B-tree）」、ACMコンピューティング・サーベ
イ（ACM Computing Surveys）、Vol.11（1979年）、pp.
121-138ではＢ＋木と呼ばれ、またBayer、R.とUnteraue
r、K.の論文「接頭辞Ｂ木（Prefix B-trees）」、ACMデ
ータベース・システム紀要（ACM Trans.on Database Sy
stems）、Vol.2、１（1977年３月）、pp.11-26及びWede
kihdの上記論文では、Ｂ＋木と呼ばれている。本明細書
では、葉探索Ｂ木を参照するのに、ComerのＢ＋木とい
う用語を使用することにする。

Ｂ＋木の弱い探索側プロセスが、Ｂ＋木自体内部でロッ
クを使用する必要がないことが望ましい場合がしばしば
ある。弱い探索側プロセスとは、更新する意図のない読
取り側プロセスである。弱い探索側プロセスとは、探索
中のある時点では有効であったが、探索の終了時には有
効であることが保証されない結果を戻すものである。し
かし、弱い探索側プロセスが、Ｂ木の走査を始める前に
探索のオブジェクトに対するロックを獲得している場
合、本発明を用いると、そのオブジェクトは探索終了時
に有効な（すなわち、現）オブジェクトであることが保
証される。

弱い探索側プロセスがロックを使用する必要がないと、
大半のアクセスが弱い探索側プロセスによるものである
場合、または探索のオブジェクトに対するロックが探索
開始前に獲得される場合、またはロック機能が共用シス
テムのある部分にとって遠隔位置にある分散アプリケー
ションの場合には、特に有益である。その利益は、並列
性の増大とロック・トラフィックによるオーバーヘッド
の減少である。

Lehman、P.とYao、S.の論文「Ｂ木の並列操作の効率的
なロッキング（Efficient locking for concurrent ope
rations on B-tress）」、ACMデータベース・システム
紀要、６（1981年、12月）、pp.650-670は、読取り側プ
ロセスがロックすることを必要としない、Ｂリンク木と
呼ばれる方法を記載している。この方法は、従来のよう
にＢ木を収縮させる方法を定義しない。これは、安定し
た木や、挿入及び削除が均一に分散された変化する木で
は受け入れることができるが、一般に頑丈ではない。具
体的に言うと、Yao.A.の論文「ランダム２−３木（On r
andom2-3trees）」、Acta Informatica.9、２（1978
年）、pp.159-170に記載された、平均密度0.69という結
果はあてはまらない。さらに、Ｂリンク木、複数のノー
ドに関する原子的更新を実行するのに使用されるシャド
ー更新が適用できない。

C.発明が解決しようとする問題点通常、ロックを獲得するプロセスはコストがかかる。読
取り側プロセスが存在すると、読取り側プロセスが終了
するまで書込み側プロセスの開始時間が遅延されて、シ
ステムの並列処理が低下する傾向がある。当技術分野で
既知のシステムでは、純粋な読取り側プロセスがロック
することなく動作することはできなかった。

したがって、本発明の目的は、並列システムでデータ構
造に効率的にアクセスする方法を提供することにある。

本発明の他の目的は、弱い探索側プロセスがロックを必
要とせずに動作できる方法を提供することにある。

D.問題点を解決するための手段本発明の上記及びその他の目的、利点及び特徴は、以下
の説明及び添付の図面を参照すればより明らかになるで
あろう。

本発明の目的と特徴を示す好ましい非限定的な実施例に
よれば、Ｂ＋木の弱い探索側プロセスが、Ｂ＋木構造へ
のアクセスを直列化するロックを回避できる方法が提供
される。これを実現するのに使用される更新技術は、シ
ステム障害の後で修復が不要となるように、Ｂ＋木が２
次記憶装置上で常に正しい状態にあることを保証するも
のである。

弱い探索側プロセスは指定の期間内に読取りを完了する
が、時には、実際にはこの期間内に読取りを完了してい
ないために再起動が必要になることがあるものと仮定す
る。この仮定は、読取り側プロセスと書込み側プロセス
の双方に関してより高度の並列性をもたらす。

読取り側プロセスが局部的にデータの一貫したビューだ
けを必要とする状況では、読取り側プロセスがロックを
獲得する必要なく、読取り側プロセスがデータ構造にア
クセスし続ける間に、書込み側プロセスがデータ構造を
変更できるようにすることが実用的である。読取り側プ
ロセスは、データ構造を指す有効ポインタの獲得以降の
経過時間を測定することができ、所定の時間内に読取り
を終了できなかった場合には再起動することができる。

E.実施例本発明の方法は、アドレス・ポインタで接続されたデー
タ構造に適用される。こうしたデータ構造は、木、リス
ト、及びある種のタイプのテーブル（たとえば、連鎖さ
れたオーバーフロー・バケットをもつハッシュ・テーブ
ル）を含む。以下では、データ構造の諸要素をノードと
呼ぶ。構造中の末端ノード以外の各ノードは、他のノー
ドを指すポインタを含む。この方法は、読取り側プロセ
スが次のことをする場合に実用的である。

1.1つのノードまたは論理的隣接ノードの小さなサブセ
ットに完全に含まれるオブジェクトを探索する（共通の
親をもつ木兄弟が論理的隣接ノードの例である）。この
種の探索を可能にする更新方法は、データ構造内での局
部的整合性を維持する。

2.抽象的な相互関係を持たない複数のノードに含まれる
複数のオブジェトを探索する。この種の探索の例は、フ
ァースト・ネームが“Alfred"であるすべての従業員の
電話番号の探索である。この照会では、探索中に入力項
目が挿入、削除または修正されるかどうかは問題ではな
い。

この方法は、任意の切断されたノードが、それが再使用
され、したがって、その以前の内容が破壊される前に、
ある時間の間維持されることを読取り側プロセスに保証
する。これは次のどちらかの方法によって行なわれる。

1.ノードを修正または除去する書込み側プロセスに、指
定した時間の間、古いノードを修正しないままにさせ
る。この指定の時間が経過すると、書込み側プロセスは
自由に記憶装置を再使用できる。これは通常、記憶装置
が自由記憶（free memory）マネージャに戻されてから
記憶装置が自由記憶マネージャによって再使用のために
割り当てられるまでの間に遅延があることを意味してい
る。

2.同じ構造中のノードだけを再使用するか、またはその
ノードがもはや同じ構造のメンバではないことを読取り
側プロセスが決定できるように、すべてのデータ・オブ
ジェクトにオブジェクト識別子を追加する。さらに、そ
のノードは、それが同じ構造中の他のノードとして再使
用される場合、それが行なわれたと読取り側プロセスが
判定できるのに十分な補助識別を含んでいなければなら
ない。

すなわち、ケース１では、あるノードを指すポインタを
獲得してからノードの探索を終了するまでの間の時間を
読取り側プロセスが原子的に計算する場合、読取り側プ
ロセスは、その時間を指定された時間と比較し、ａ）そ
の経過時間が指定の時間より短い場合は先へ進み、ｂ）
その持続時間が指定の時間を超える場合は最初からの処
理を再開始する。指定の時間は、大半の読取り側プロセ
スが再開始することなく終了し、わずかな量の記憶域だ
けが保留状態になることが保証されるように選択する。
また、実際には、読取り側プロセスは、経過時間を測定
する際に、最大誤差を表す時間量だけ指定の時間よりも
早目に打ち切る。

ケース２では、読取り側プロセスは、もはや同じ構造の
一部ではないノード、またはその構造の別のノードとし
て再使用されたノードに達すると、再開始する。

有効なデータ構造が、すでにポインタをもつ読取り側プ
ロセスのために残されるようにするため、書込み側プロ
セスは様々な技術を使用することができる。１つの技術
は、間接割振りであり、「シャドー書込み」とも呼ばれ
る。シャドー書込みとは、異なるメモリ域に新しいノー
ドを作成することである１回の原子的更新で、書込み側
プロセスは新しい単数または複数のノードを指すポイン
タを変更する。すなわち、読取り側プロセスがポインタ
をすでに獲得している場合、その読取り側プロセスには
新しいノードが見えず、あるいは再使用されるまでの古
いノードが見え続ける。そのノードは指定の期間の間再
使用されないので、読取り側プロセスはその期間内にそ
の参照を行なわなければならない。

上記のようにデータベース・システムでは普通のことで
あるが、使用されるデータ構造が木である場合、データ
構造が変更されると、一回の原子的更新で古い枝を剪定
して新しい枝を付加できる程度にまで、完全な部分木に
シャドー操作を行なう。以下では、本発明をＢ＋木に関
して説明する。

Ｂ＋木の定義本発明では、Ｂ＋木は、すべてのキー（及びおそらくは
関連するデータ）が外部ノード（すなわち、葉）に現
れ、内部ノードは葉への経路を示す分離キー（separato
r key）を含むという、葉探索木である。これらの分離
キーはしばしばルータ（router）と呼ばれ、その経路指
定方式が並列性に影響を及ぼす可能性がある。（Kwong
Y.とWood、D.論文「Ｂ木について：経路指定方式と並列
性（On B-trees:routing schemes and concurrenc
y）」、ACM/SIGMOD国際データ管理会議（ACM/SIGMOD In
t.Conf.Management of Data）、1980年、pp.207-21
3）。第１図では、葉はノード10−22であり、内部ノー
ド24−28はルータを含む。

すなわち、第１図の例を参照すると、ノード28から始め
てキー103を探索する場合、経路28Aが選ばれる。という
のは、その経路はキー340の左側にあり、103は340より
小さいからである。ノード24では、経路24Aが選ばれ
る。というのは、この経路は38より大きく123より小さ
いからである。この経路はノード18に達し、そこでキー
103が見つかる。

具体的には、ｍ次のＢ＋木は以下の特性をもつ。

1.各経路指定ノードはせいぜいｍ個の子をもつ。

2.根ノード以外の各経路指定ノードは、少なくともceil
ing（m/2）個の子をもつ。関数ceiling（ｘ）は、引数
より大きいかまたはそれに等しい最小の整数を見つける
関数であると定義される。

3.根ノードはすくなくとも２個の子をもつ。

4.すべての葉は、同じレベルに現れなければならない。

5.木内に存在するすべてのキーは葉に現れる。通常、そ
れらのキーは各葉の内部で順序づけられる。葉は各キー
に関連するデータも含む。これは、インデックスから分
離されているレコードを指すポインタであることが多い
が、Ｂ＋木に組み込まれたデータ・レコードのこともあ
る。そのデータは可変長でもよいが、話を簡単にするた
めに、そのキーまたはキーとそれに関連するデータが、
木全体にわたって固定長であると仮定する。可変長デー
タまたは大きな固定長データはなんらかのセグメント化
方式によって維持できるが、これは本発明の範囲内には
含まれない。この発明では、「キー／データ」の語で、
キーだけまたはキーとその関連するデータのうち、特定
の実施にとって適切な方のものを指すことにする。

したがって、 6.すべての葉は、せいぜいｍ′−１、少なくともceilin
g（ｍ′/2-1）個のキーまたはキー／データ要素を含
む。ｍ′はｍに対して正式の関係をもたないことを指摘
しておく。すなわち、ｍ′はｍより小さくても、大きく
ても、等しくてもよい。

ノードのレベルは、それが根ノードの場合は１であり、
それ以外の場合はその親のレベル＋１である。同じタイ
プのＢ＋木ノード（すなわち、葉、非葉）、及びしばし
ばすべてのノードが、固定サイズのページである。した
がって、Ｂ木は一般にページ木または多岐ページ木と呼
ばれることが多い。

説明を容易にするために、ｍまたはｍ′の両方を指すの
にｍを使い、区別が重要でない場合は、キー／データを
指すのに要素を使うことにする。また、多くの文献で
は、葉の父レベルにも葉を使用する。

第１図のＢ＋木は、ｍ＝４、ｍ′＝６である。ここで
は、非葉ノードに対して（≦、＜）経路指定方式を使用
する。この経路指定方式は以下のように定義される。

ｊ個のルータｒ（１≦ｒ≦ｊ）及びｊ＋１個のポインタ
ｐ（０≦ｐ≦ｊ）を含む任意の非葉ノードで、p_iで指示
される部分木をＳ（p_i）と置く。そうすると、（≦、
＜）経路指定方式では、ルータr_iは次式を満足する。１
≦ｉ≦ｊで、「Ｓ（p_i-1）中のすべてのキー」≦r_i＜
「Ｓ（p_i）中のすべてのキー」。

葉探索Ｂ木の多くの用途のうちの２つの例は次のとおり
である。

1.ワードまたは記号をキーとする辞書 2.ファイル名をキーとし、各キーに関連するデータが、
たとえば、ファイル属性、及びファイル・データを指す
ポインタである、ファイル辞書。

この説明では、読取り側プロセスとは、純粋の弱い探索
側プロセス、すなわちその探索が探索の対象に対する外
部ロックによって強化されている「弱い探索側プロセ
ス」を意味するものとする。Ｂ＋木は、ある整合性のあ
る状態から後続の整合性のある状態へと原子的に変化す
る。したがって、再構造化操作中にシステム障害が起こ
った場合に常に汚染を受けにくい状態にある。

ライブ・ロック（live lock）は、どんなデータ構造の
並列読取り及び書込みをも可能にするどの解決策にでも
存在する可能性が大きいので、本発明でも論理的には可
能である。しかし、本発明は、主として書込み側プロセ
スより読取り側プロセスの数が多いときに価値があり、
Ｂ＋木再構造化はm/2回の更新ごとにほぼ１回行なわれ
るので、ライブ・ロックは実際上問題にならない傾向に
ある。いずれにせよ、LehmanとYaoの上記論文に述べら
れているようなライブ・ロックに対する解決策を、必要
に応じて実施することができる。

記憶装置モデルＢ＋木のページ（すなわち、ノード）は、２次記憶装
置、たとえばディスク上に記憶される。複数のプロセス
が並列にＢ＋木を読み取り、修正する可能性がある。こ
れらのプロセスは、１つまたは複数のコンピュータ・シ
ステムで行なわれることがある。

この目的では、コンピュータ・システムは、１台または
複数のプロセッサに接続された１次記憶装置から構成さ
れる。プロセスは一時に１ページしか読取りまたは書込
みができないが、１次記憶装置中に同時にアクセス可能
な複数のページを有することができる。話を簡単にする
ため、１次記憶装置から２次記憶装置にノードを書き込
む出力操作が分割できないものと仮定する。Ｂ＋木内の
ノードを修正するプロセスは、１次記憶装置中のノード
の私用コピーに対して作用し、次いで１次記憶装置から
２次記憶装置にそれを書き込むことにより、ノードをＢ
＋木に導入する。

そのキー範囲が修正されたノードは、２次記憶装置の既
存の位置ではなく新しい頁位置に書き込まれる。新しい
位置に書き込むこの技術は、シャドーイングまたはシャ
ドー更新と呼ばれることが多い。

ロッキングＢ＋木の頁の内容を修正しようとするプロセスでは、ま
ずそのページをロックしなければならない。更新側プロ
セスは、Ｂ＋木修正の正しい直列化を保証するものなら
どんなロック技術を使ってもよい。ロックはそのプロセ
スに、ページに対する独占的修正権を与える。読取り側
プロセスは、ロックを使用する必要はなく、ページへの
アクセスを妨げられない。本発明は、ロッキングの原理
または分散環境に対するその実施の細部には無関係であ
る。

Ｂ木上の並列操作というテーマに関する初期の研究者
は、更新側プロセスに関して、以下の重要な事実に気付
いた。KwongとWoodの用語を用いると（Kwong,Y.とWood,
D.の論文「Ｂ木における並列処理の新しい方法（A new
method for concurrency in B-trees）」、IEEEソフト
ウェア・エンジニアリング紀要（IEEE Trans.on Softwa
re Engineering）、Vol.8、No.3（1982年５月）、pp.21
1-22）、どの更新側プロセスＵに対しても、更新操作か
ら生じるすべての構造変化及びデータ変更を完全に含む
最小部分木の根となるノードがある。これは、Ｕの最深
安全ノードと呼ばれ、それから葉に向かう経路は、Ｕの
範囲と呼ばれる。具体的には、Ｂ木中のノードは、それ
が満杯でない場合、すなわちｍ−１個未満のキーしかも
たない場合、挿入に対して安全である。それが最小でな
い場合、すなわち、ceiling（m/2-2）個より多くのキー
をもつ場合、削除に対して安全である。

シャドー更新以下の手続きは、読取り側プロセスが、ロックを使用せ
ずにＢ＋木を走査できるようにするために、更新側プロ
セスが従わなければならないものである。さらに、これ
は、冗長データを決して含まず、常に一貫しているＢ＋
木をもたらす。

挿入Ｂ＋木を変更する前に、挿入プロセスはまずあるロッキ
ング・プロトコルを用いてその範囲をロックする。その
結果、その根ノードが最深安全ノードとなっている部分
木は、挿入点が見つかったとき、部分木のままである。
この部分木の最も簡単な形は、オーバーフローを引き起
こさずに新しいキーとデータが挿入できる、安全な葉ノ
ードである。そうでない場合、挿入に対して安全ではな
く、したがって挿入によってノードが分割される。子孫
経路の親となる最深安全ノードである。これを実行する
従来の方法は、新しいキー／データを受け取っている葉
ノードを、それぞれceiling（ｍ′/2-1）個とｍ′−cei
ling（ｍ′/2）個のキー／データ要素を含むノードに分
割し、新しい要素を適切なノードに追加するものであ
る。その場合、ルータ／ポインタ要素が親に伝播され
る。その結果、親が挿入に対して安全ではない場合、オ
ーバーフローが生じる。したがって、この「上方」伝播
は、最深挿入安全ノードに達するまで繰り返して起こる
ことがあり得る。

本発明では、シャドー更新を使用して、従来の方法を以
下のように修正する。

葉ノードが挿入に対して安全な場合、新しいデータが挿
入され、葉ノードが２次記憶装置の従来の位置に書き込
まれる（すなわち、元のまま）。そうでない場合、最深
挿入安全ノードまでの各分割ノードについて、以前のノ
ードに代わって２つの新しいノードが、それらの従来の
位置ではなく２次記憶装置の新しい位置に書き込まれ
る。すなわち、分割によって生じた両方のノードが、そ
の最終の形で、２次記憶装置の新しい位置に書き込ま
れ、Ｂ＋木は以前の一貫した状態のままとなる。それら
は、新しいルータを２つの新しいポインタと共に挿入安
全ノードに挿入することにより、木に接続される。次い
で、挿入安全ノードが、２次記憶装置の既存の位置に書
き込まれる。この操作の結果、Ｂ＋木はその新しい一貫
した状態に変換される。更新完了後、プロセスは、現在
外された以前の枝に関連する２次記憶ノードの返還／再
使用を管理しなければならない。これは、この枝を依然
として通過する読取り側プロセスが、正しい結果を得ら
れるように行なわなければならない。これを行なう方法
は、本明細書で後で説明する。

挿入の新しい解決策を、第2A図、第2B図、及び第2C図に
示す。第2A図は、要素100の挿入前の、３つのノード3
0、32、34をもつＢ＋木の一部分を示す。第2B図は、
（オーバーフローによって生じる）新しいシャドー更新
されたノード36、38、40、42が書き込まれた後で挿入安
全ノード30に接続される前の状態を示す。第2C図では、
シャドー化されたノードが、キー98をノード30に挿入す
ることにより、その２つの隣接ポインタを介してノード
30に接続されている。以前の経路は木への接続を解除さ
れていることに留意されたい。

削除削除プロセスでは、挿入プロセスと同様に、ロッキング
・プロトコルを用いてその範囲をロックする。次いで、
目標要素が、挿入安全ノードでキーの回転または削除が
行なわれるまで削除されるが、（アンダーフローによっ
て）その後でマージが行なわれることもあり得る。本発
明では、読取り側プロセスがロックを使用せずにＢ＋木
を走査できるように、削除を以下のように管理する。

削除された要素を含むノードが、その削除の結果として
アンダーフローにならない場合、そのノードが元の場所
に書き込まれて、プロセスは終了する。そうでない場
合、マージ要素を受け取る直接の兄弟が、新しい２次記
憶装置の位置に書き込まれることによって、シャドー更
新される。（直接の兄弟とは共通の親の下で隣接するも
のである。したがって、左端及び右端のポインタで指定
されるノードは、１つしか直接の兄弟をもたない。親の
他の子はすべて直接の兄弟を２つもつ。）この手続きが
キーの回転によって終了する場合、その回転に関係する
兄弟もシャドー更新される。この場合、そのキーの回転
に関係する親は、元の場所に書き込まれ、それによって
新しいノードを木に接続する。このマージ手続きが削除
安全ノードの削除によって終了する場合、新しいシャド
ー書込みされた枝がこのとき木に接続され、削除安全ノ
ードが元の場所に書き込まれる。どちらの方法でも古い
枝は木から切断され、したがって切断された枝にいるど
の読取り側プロセスも、その探索を正しく終了するよう
にしなければならない。それを実施する技術について
は、次節で説明する。

第3A図、第3B図、及び第3C図は、本発明による新しい削
除方法を示す。第3A図は、要素108の削除前の、ノード4
0−52をもつＢ＋木の一部分を示す。第3B図では、葉の
アンダーフローによって生じる新しい２つのシャドー更
新されたノード54と56及びその親が破線で示されてい
る。第3C図には、回転によってシャドーされたノードが
接続された後のＢ＋木の同じ部分が示されている。現在
は切断されている以前のノード42−56も破線で示されて
いる。ルータ185と200を回転させるため、対応するノー
ド62と60のシャドー書込みを行なうことによって、ノー
ド42と44が更新されていることに留意されたい。この回
転は、ルータ185を根ノード中の200と置換し、根ノード
を元の橋に書き込むことによって完了している。

以上、シャドー更新を用いて再構造化操作の「局所的」
一貫性を実現することを説明した。しかし、この技術を
使って、より広範囲の一貫性を実現することもできる。
たとえば、共通ノード、すなわち変更された要素をすべ
て含む最小部分木の根ノードに達するまでシャドー更新
することにより、Ｂ＋木中の、論理的には接続されてい
るが物理的には切断されている任意の数の要素を原子的
に変更することができる。共通ノードに達した時点で、
変更の全体が１回の操作で導入される。

切断されたノードの再使用前述のように、読取り側プロセスはＢ＋木の切断された
ノードに残ることができる。これらのノードは、それら
を使用するすべての読取り側プロセスが読取りを完了す
るまで、またはそうした読取り側プロセスがその探索を
再開するように警告されるまで、再使用されないことが
必要である。３つの解決策がある。

1.切断されたノードは、切断後ある時間増分Δｔまで再
使用されない。読取り側プロセスはＢ＋木に入った時間
を登録しておき、ノード探索の結果を使用（または報
告）する前に、その探索が始まってからΔｔが経過した
かどうか検査する。経過している場合、読取り側プロセ
スは根ノードから探索を再開する。そうでない場合は、
先へ進む。特定の実施態様では、ａ）読取り側プロセス
が「タイム・アウト」する可能性が非常に低くなるよう
にし、ｂ）過剰な量のノードを「保留」状態で蓄積しな
いようにする、Δｔの値を設定することができる。

たとえば、葉に達するために４つのノードを読み取らな
ければならず、各ノードは処理するのに（待ち時間を含
めて）平均20ミリ秒かかり、毎秒平均100個のノードが
シャドー書込みされる、Ｂ＋木を考えてみる。Δｔを25
0ミリ秒に設定した場合、再開の回数は非常に小さくな
り、保留状態のノードの平均数は25になる。

分散環境では、実時間ではなくて間隔を使用するので、
この方法を支援するためにクロックを同期させる必要は
ない。実際、切断されたノードが再使用される前にそれ
らのノードを保留するプロセスは、クロックすべての相
対的な動的精度内に誤差を納めるのに十分な小さな時間
増分をΔｔに加える（すなわち、間隔Δｔにわたる「最
高速」クロックと「最低速」クロックの差）。

2.活動状態の読取り側プロセスがすべて確実に終了した
場合、切断されたノードは無条件で再使用できる。とい
うのは、もはやＢ＋木中にそのノードが向かう経路がな
いため、そのノードはどのオブジェクト中でも再使用可
能だからである。

切断されたノードは、切断時に活動状態であったすべて
の読取り側プロセスが終了したことが確実ではない場
合、同じＢ＋木中のノードとしてしか使用できない。そ
の場合、（切断された枝を走査している）活動状態の読
取り側プロセスがあり、そのノードが同じＢ＋木中で再
使用される場合、ノードが再使用されたかどうかを読取
り側プロセスが判定できるように、以下の２つの技術の
どちらかを実施しなければならない（したがって、読取
り側プロセスはその探索を再開しなければならない）。

a.読取り側プロセスが、探索前にキー範囲とノードのレ
ベルを検査できる。これは、各ノードにキー範囲とレベ
ル数を追加することによって実現される。根ノード以外
のすべてのノードでは、キー範囲は親のルータによって
定義される。たとえば、第１図では、ノード18のキー範
囲は39−123である。根ノードでは、それはＢ＋木のキ
ー定義域である。

b.その構造にノードが追加された時間を指定する時間値
が、Ｂ＋木の各ノードに追加される。読取り側プロセス
は、ノード探索の結果を使用または報告する前に、この
フィールドを検査し、木に入るより後の時間が含まれる
場合、読取り側プロセスはその根ノードから再開する。

3.B＋木を支援するファイル・システムが、各データ・
ページをさらに識別する接辞を含む場合、ファイル・シ
ステム中の各オブジェクトに対する一義的な識別子がそ
れに入れられる。この場合、切断されたノードは再使用
できる。次いで読取りプロセスは、接辞のオブジェクト
識別を検査して、それが依然としてＢ＋木構造中にある
ことを確認し、方法２の所で示した２つの技術のどちら
かを使って、ノードが再使用されたかどうか決定する。

３つの方法はすべて、読取り側プロセスを時々不必要に
再開させるが、切断されたノードにいる読取り側プロセ
スを保護する。方法１は、若干の量の２次記憶空間が一
時的に保留にされる代わり、ほとんど（通常はまった
く）再開を起こさせない。方法２と３は、必要に応じて
ノードが再使用できるが、読取り側プロセスの再開がよ
り多くなる傾向がある。

これらの方法は、読取り側プロセスに対してのみ最適の
並列性を実施するものである。それらは、探索プロセス
中に、結果が無効であるかどうか判定するための簡単な
方法を使用する。

例次に、（常に）一義的なオブジェクト識別子を含む接辞
（affix）を含むファイル・システムを使った、本発明
の実施態様について説明する。

第４図は、Ｂ＋木に新しい要素を挿入する際に従うべき
手続きを示す。標準のＢ＋木探索技術を使って、新しい
要素を含むことになる葉ノードを見つける（論理ブロッ
ク100）。適切なロッキング・プロトコルを使って、更
新範囲をロックする。新しい要素の挿入によってノード
中でオーバーフローが発生しない場合、その新しい要素
が挿入され、そのノードと接辞が元の場所に書き込まれ
る（論理ブロック101−103）。挿入によってオーバーフ
ローが発生する場合、挿入安全ノードが見つかるまで以
下のこと（論理ブロック104−105、101）が繰り返して
行なわれる。

1.それぞれceiling（m/2）−１個及びｍ−ceiling（m/
2）個のキー／データ要素を含む、２つの新しいノード
（接辞つき）のシャドー書込みを行なう。

2.親に新しいルータを挿入する準備をする。

3.親が挿入に対して安全でない場合、親ノードを使用す
ると上記の１に戻る。

これが完了すると、新しいルータが挿入安全ノードに挿
入され、そのノードとそれに関連する接辞が元の場所に
書き込まれる（論理ブロック103）。

第５図は、Ｂ＋木中の要素を削除する際に従うべき手続
きを示す。標準のＢ＋木探索技術を使って、削除すべき
要素を含む葉ノードを見つける（論理ブロック200）。
適切なロッキング・プロトコルを使って、更新範囲をロ
ックする。要素の削除によってノードのアンダーフロー
が発生しない場合、その要素が削除され、そのノード及
び接辞が元の場所に書き込まれる（論理ブロック201−2
03）。削除によってアンダーフローが発生する場合、２
つのノードを１つに接合できるかどうか調べるため、直
接の兄弟を検査する（論理ブロック204）。接合できる
場合、それらのノードを組み合わせて新しいノードに
し、それを接辞つきでシャドー書込みする。そうする
と、その親中のルータが削除されて、親ノードが選択さ
れ、プロセスは論理ブロック201に戻って、次の削除に
よるアンダーフローの有無を検査する。２つのノードが
接合できない（すなわち、２つのノードの要素の数がｍ
−１個を越える）場合、削除を受けるノードがもはやア
ンダーフローしないように直接の兄弟から要素を回転さ
せることによって、２つのノードの均衡が取られる（20
7）。この回転によって生じた新しく均衡が取られたノ
ードが，その接辞と共にシャドー書込みされる。次に、
親中のルータが、２つの回転されたノード間の新しい分
割キーを反映するように更新されて（論理ブロック208
−209）、関連する接辞つきの親ノードが元の場所に書
き込まれる（論理ブロック203）。

第６図は、読取り側プロセス（すなわち、弱い探索側プ
ロセス）が従うべき手続きを示す。Ｂ＋木の最初のノー
ド（すなわち、根ノード）が読み取られる（論理ブロッ
ク301）。オブジェクト識別が正しいかどうか、接辞を
検査する（論理ブロック302）。正しくない場合、再試
行を試みる（論理ブロック303、301）。探索側プロセス
が始動してからそのノードが次に検査されるまでの間
に、そのノードがＢ＋木から除去されて他のオブジェク
ト中で再使用される場合、接辞はエラーを示す。そのノ
ードが接辞検査に合格した場合、ノードのキー範囲とレ
ベルが、期待されるキー範囲（根ノードの場合は、Ｂ＋
木全体のキー範囲である）及びレベルであるかどうか検
査される（論理ブロック304）。キー範囲が正しくない
場合、探索が再開される（論理ブロック303）。ノード
が削除されてその後探索中にＢ＋木中で他のノードとし
て再使用される場合、キー範囲は正しくならない。ノー
ドが葉ノードである場合、目標データを求めてそのノー
ドが探索され、探索状況と目標データが見つかった場
合、それらが顧客に戻される（論理ブロック305−30
6）。ノードが葉ではない場合、ルータを走査すること
によって探索すべき次のノードが決定され（論理ブロッ
ク307）、探索は論理ブロック301に進む。

F.発明の効果本発明を用いれば、並列処理システムにおいて読取りを
ロックなしに行なうことができ、ロックに伴なうオーバ
ーヘッドを除いて処理を効率化することができる。

【図面の簡単な説明】

第１図は、４次Ｂ＋木を示す図である。第2A図、第2B図、第2C図は、挿入例を示す図である。第3A図、第3B図及び第3C図は、シャドー更新を伴う削除
例を示す図である。第４図は、本発明による挿入の流れ図である。第５図は、本発明による削除の流れ図である。第６図は、本発明による弱い探索側プロセスによる手続
きの流れ図である。

Claims

【特許請求の範囲】

【請求項１】データ値の更新を伴うことなくそのデータ
値を読み取るために探索し、かつ探索の開始及び終了の
間で以前に有効であったデータ値の有効性を保証でき
る、というプロセスを含む探索のプロセス（以下弱い探
索側プロセスという）を許可する間、アドレス・ポイン
タで接続されたノードのデータ構造の更新を実行するた
めのコンピュータにおける改善された方法であって、ロ
ッキングなしに該データ構造を読み取るために、前記更新の領域が１つのノード内におさまるときは、該
ノードをその場で更新することによって前記データ構造
を更新し、前記更新の領域が１つのノードをこえるときは、前記更
新の領域の最深安全ノード（最深安全ノードとは更新が
全ておさまる最小の部分木の根ノードをいう）をその場
で更新し、かつ該最深安全ノードの他の、前記更新の領
域の中で更新されるノードをその場で更新するのでなく
補助的に別の記憶域に書き込むことによって、前記デー
タ構造を更新し、弱い探索側プロセスが前記データ構造におけるノードで
ロックをかけることなしに前記データ構造へ読み取りア
クセスし、前記更新ノードのシャドー書込みの結果として前記デー
タ構造から切断状態になるようになったノードによって
占有される前記記憶域を再使用するための手順を供給
し、前記記憶域の再使用のための手順は、また、切断状態に
なる前記ノードを探索するであろう弱い探索側プロセス
の探索が完了することを可能とする前記方法。を含む方法。