WB


次: , 前: (dir), 上: (dir)


次: , 前: Top, 上: Top

1 概要


次: , 前: 概要, 上: 概要

1.1 説明

[Note from the translator: This is a private and unofficial translation into Japanese of wb.texi, published in the hope to be useful but without any warranty of its correctness. The canonical version of the document is the original one. - dai inukai 2006-01-16 -]

[翻訳者の注: これはwb.texiの個人的で非公式な日本語への翻訳です。役に立つことを願って公開するものであり翻訳の正しさは一切保証致しません。規範となる文書は原文だけです。犬飼 大 2006-01-16]

WBはディスクベースの(ソート済み)連想配列Cライブラリである。連想配列は可変長(0.B〜255.B)のキーと値で構成される。以下を行う関数が用意されている。

WBの実装には、2^32*ブロックサイズ(デフォルトは2048.B)=2^43バイト(8796.GB)というファイルサイズ上の限界がある。WBは数100メガバイトのデータベースを使用して、日常業務に使用されている。WBは自分自身でメモリとディスクを管理し、最近利用されたブロックのRAMキャッシュを保持する。

1つのディスクファイルには複数の連想配列を格納できる。複数のディスクファイルへの同時アクセスに対応している。 構造検査、ガーベージコレクションプログラム、ビューアが用意されている。コンパイル後のWBの大きさは約66kバイトである。

WBは、B-ツリー構造の1変種を使用して実装される。B-ツリーはアクセスがハッシングよりは遅いけれども動的な変更が可能であり、後続キーと先行キーの判定が効率的である。データベースの大きさに対して、すべての操作がO(log(n))である。インデックス構造を実装するデータベースシステムでは、通常はB-ツリーが使用される。B-ツリーは、大きなデータ構造に対して最小のディスク操作数を使用するように最適化される。ディスクの充填率を高めるために、WBでは前置キーと後置キーの圧縮が使用される。


次: , 前: 説明, 上: 概要

1.2 複製許諾

Copyright (C) 1991, 1992, 1993, 1996, 1999, 2000, 2003
Free Software Foundation, Inc.
59 Temple Place, Suite 330, Boston, MA 02111, USA

Permission to use, copy, modify, distribute, and sell this software and its documentation for any purpose is hereby granted without fee, provided that the above copyright notice appear in all copies and that both that copyright notice and this permission notice appear in supporting documentation.

NO WARRANTY

BECAUSE THE PROGRAM IS LICENSED FREE OF CHARGE, THERE IS NO WARRANTY FOR THE PROGRAM, TO THE EXTENT PERMITTED BY APPLICABLE LAW. EXCEPT WHEN OTHERWISE STATED IN WRITING THE COPYRIGHT HOLDERS AND/OR OTHER PARTIES PROVIDE THE PROGRAM "AS IS" WITHOUT WARRANTY OF ANY KIND, EITHER EXPRESSED OR IMPLIED, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. THE ENTIRE RISK AS TO THE QUALITY AND PERFORMANCE OF THE PROGRAM IS WITH YOU. SHOULD THE PROGRAM PROVE DEFECTIVE, YOU ASSUME THE COST OF ALL NECESSARY SERVICING, REPAIR OR CORRECTION.

IN NO EVENT UNLESS REQUIRED BY APPLICABLE LAW OR AGREED TO IN WRITING WILL ANY COPYRIGHT HOLDER, OR ANY OTHER PARTY WHO MAY MODIFY AND/OR REDISTRIBUTE THE PROGRAM AS PERMITTED ABOVE, BE LIABLE TO YOU FOR DAMAGES, INCLUDING ANY GENERAL, SPECIAL, INCIDENTAL OR CONSEQUENTIAL DAMAGES ARISING OUT OF THE USE OR INABILITY TO USE THE PROGRAM (INCLUDING BUT NOT LIMITED TO LOSS OF DATA OR DATA BEING RENDERED INACCURATE OR LOSSES SUSTAINED BY YOU OR THIRD PARTIES OR A FAILURE OF THE PROGRAM TO OPERATE WITH ANY OTHER PROGRAMS), EVEN IF SUCH HOLDER OR OTHER PARTY HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGES.

Unofficial translation into Japanese follows:

(非公式な翻訳) 前記の著作権情報がすべての複製に表示され、著作権情報と本許諾情報の両方が解説文書に表示される限りにおいて、いかなる目的についても本ソフトウェアとマニュアルの使用料を支払わない使用、複製、変更、頒布、販売の許諾をここに認可する。

無保証

プログラムが無償でライセンス供与される以上、準拠法が許可する範囲においてプログラムの保証は全く存在しない。文書による別段の指定がない限り、著作権保有者とその他の当事者のいずれかもしくは両方は「現状のままで」本「プログラム」を提供するものであり、明示的と暗黙とにかかわらずいかなる種類の保証も行わない。保証には市場性や適合性に関するあるゆる目的の暗黙の保証が含まれるが、暗黙の保証に限定されるものではない。プログラムの品質と性能に関する全てのリスクはユーザに帰するものである。万一プログラムに欠陥があると判明した場合にも、修復や訂正のすべての必要な修理コストはユーザの負担とする。

準拠法によって要求されるか、もしくは文書による同意がない限り、著作権保有者も、上記に許可されてプログラムの修正と再配付のいずれかもしくは両方を行うその他のいかなる当事者も、ユーザに対して損害の責任を負わないものとする。これにはプログラムの使用もしくは適用不能によって発生するあらゆる一般的な、特別な、付帯的な、結果的な損害賠償責任が含まれる(これにはデータの喪失、不正確なデータの生成、ユーザもしくは第三者が被る損害、その他あらゆるプログラムと当該プログラムとの協調動作の不能が含まれるがそれに限定されるわけではない)。前述の著作権保有者もしくはその他の当事者が前述の損害の可能性に関して通知を受けていた場合も例外ではない。


次: , 前: 複製許諾, 上: 概要

1.3 来歴

B-ツリーは1972年に[BM72]R. BayerとE. McCreightによって初めて考案された。

Roland Zito-Wolf、Jonathan Finger、Aubrey Jafferは1991年から1993年の間Holland Mark Martinで働きながら、ここに説明するWanna B-treeシステムを書き下ろした。

Jonathan FingerはWBを使用して、MUMPSに似たバイトコード化インタープリタSliced Breadを書いた。この統合システムはその後10年間、Holland Mark Martinにて頻繁に使用された。


次: , 前: 来歴, 上: 概要

1.4 構成

WBレイヤを使用するにあたっての最初のCインクルードファイルはwbsys.hである。このファイルにより、同じディレクトリのその他の複数のファイルが取り込まれる。wbsys.hではWBの内部データ型も定義されている。 WBには、ディスク上に保存されたデータベースファイルについてのユーティリティプログラムが含まれる。

— プログラムwbcheck: path

pathで指定されたデータベースの構造を検査して一時ツリーを回収し、フリーリストに再利用する。

WBソースは、schlep.scmによってSCMから(K&R)CとTeXinfoに変換される。make.scmは変換を統合するプログラムである。ソースはCに変換された後でプラットフォームのネイティブコンパイラでコンパイルされる。

収録内容

wb.info
理論、データフォーマット、アルゴリズムと、WB-ツリーに対するCとSCMのインタフェースの詳細を文書にしたものである。
ChangeLog
WBへの変更の詳細を説明する。
example.scm
SCMでWB-ツリーを使用するサンプルプログラム。
defs.scm
defs.hにコンパイルされるSCM構成コード。
handle.scm
blink.scm
prev.scm
del.scm
ent.scm
scan.scm
stats.scm
拡張子".c"と".h"でCコードにコンパイルされるWB-ツリー用のSCMコード。
blkio.scm
ディスクに対する弱いPOSIXインタフェース。 ディスクに対するより直接的なインタフェースがあればそれで置き換えてもよい。
wbsys.h
WBレイヤを使用する場合の最初のCインクルードファイル。
wbsys.c
共有データと低レベルCアクセスメカニズム。
wbsys.scm
SCMでデバッグする場合の共有データと低レベルアクセスメカニズム。
db.c
WB-ツリーへのSCMインタフェース用Cコード。
db.scm
SCMでデバッグする場合のSCMインタフェース用コード。
schlep.scm
SCMコードをCに変換するSCMコード。
schlep.typ
生成されるCの型に変数名を関連づける規則。
test.scm
WB-ツリーシステムのテスト用ファイル。
test2.scm
WB-ツリーシステムの追加のテスト。
Makefile
Unix makefile
VMSBUILD.COM
VMSでコンパイルする場合のコマンドスクリプト。
make.scm
WB-ツリーシステムを変換してコンパイルするSCMプログラム。
all.scm
すべてのSCMファイルをデバッグ用にロードする。
wbtab.scm
SLIBリレーショナルデータベースにWBを実装するSCMコード。
wbcheck.c
WB-ツリーデータベースの検査、修復、ガーベージコレクション用プログラム。


次: , 前: 構成, 上: 概要

1.5 インストール

WBは名前がwbのディレクトリに展開される。WBをSCMで使用したい場合は、ディレクトリscmwbを同じディレクトリ配下に置く必要がある。

VMSシステムでは、wbcheckとdb(SCM)はVMSBUILD.COMスクリプトで作成される。

unixの場合:

make all
libwb、wbscm.so、実行プログラムwbcheckがコンパイルされる。
make install
Makefileで指定された$(prefix)ツリーにlibwb、wbscm.so、wbcheckがインストールされる。


前: インストール, 上: 概要

1.6 Schemeソースからの構築

Schemeインフラストラクチャ

SCMソースは以下から入手できる。 http://swissnet.ai.mit.edu/ftpdir/scm/scm5d9.zip or ftp://swissnet.ai.mit.edu/pub/scm/scm5d9.zip

以下からはRPMソースも入手できる。 http://swissnet.ai.mit.edu/ftpdir/scm/scm-5d9-1.src.rpm or ftp://swissnet.ai.mit.edu/pub/scm/scm-5d9-1.src.rpm

以下から入手できるSLIBは、SCMが使用する可搬性の高いSchemeライブラリである。 http://swissnet.ai.mit.edu/ftpdir/scm/slib2d1.zip or ftp://swissnet.ai.mit.edu/pub/scm/slib2d1.zip

以下からはRPMも入手できる。 http://swissnet.ai.mit.edu/ftpdir/scm/slib-2d1-1.noarch.rpm or ftp://swissnet.ai.mit.edu/pub/scm/slib-2d1-1.noarch.rpm

Schemeソースのテスト

wbディレクトリからscm allを実行する。これにより、テストコードを含むWB-ツリーのSchemeバージョンがロードされる。(main)を入力すると、テストデータベースzがこのディレクトリに作成される。これを実行してエラーが発生しなければ、Cコードの作成が可能である。(quit)でscmを終了する。

Cソースの再生成。

CコンパイラがANSI関数プロトタイプを受け付けない場合は、make.scmの行(set! __STDC__ #t)をコメントアウトする。 コマンド行scm-lmake.scmを入力すれば、SCMの適切なファイルがすべて変換される。

make@VMSBUILDを実行すれば、wbと補助プログラムwbcheckがコンパイルされる。

コンパイル済みDBSCMのテスト

scm-rwb-ltest-e"(main)"を実行する。テストデータベースzの作成が前回よりはるかに高速に行われるはずである。

(quit)を入力してDBSCMを終了する。次に./wbcheck zを実行する。 これはデータベースの構造を検査して、一時ファイルを回収するプログラムである。これにより52ブロックが再利用され、no errorsが報告されるはずである。再度実行しても、今度は回集されるブロックは存在しない。


次: , 前: 概要, 上: Top

2 理論

コンカレントb-ツリーアルゴリズムの出発点として、[SAGIV]を使用した。 ただしかなりの変更と改善を行った(と思う)。実装作業、とりわけデバッギングの苦労を減らすために、特にアルゴリズムの単純化を試みた。完全な実装を作成するには多くの複雑な詳細も必要だった。本書の目的は、設計上の主な決断とそれから生まれたこまごましたものを書き留めて、説明することである。


次: , 前: 理論, 上: 理論

2.1 B-ツリーの構造とアクセス


次: , 前: B-ツリーの構造とアクセス, 上: B-ツリーの構造とアクセス

2.1.1 定義

B+ツリー

ブロック

ルートブロック

内部ブロック

リーフブロック

プレフィックス圧縮

それぞれのキーテキストの全文を保存するのではなく、前のキーに一致するこのブロックの部分の長さと、一致しないキーテキストを保存する。

サフィックス圧縮

リーフ以外のブロックでは、下位レベルの連続する2つのブロックを識別できる分割キーだけを保存する。


次: , 前: 定義, 上: B-ツリーの構造とアクセス

2.1.2 ブロック形式

ブロックヘッダ形式の最初の20バイトは、すべての型のブロックについて同一である。

0 blk:id
このブロックのID。
4 blk:top-id
このツリーのルートブロックのID。
8 blk:nxt-id
同じレベルのチェーンの次のブロックのID。
12 blk:time
このブロックが最後に変更された時点の32ビットの時刻/日付。
16 blk:end
ブロック内のデータの長さ(ヘッダを含めて2バイト)。
18 blk:level
ブロックレベル。0はリーフを示す。
19 blk:typ
ブロックの種類、以下の1つである。
20
SEQ-TYPブロックのデータ開始点。 データの終端はblk:end
20 leaf-split-key
22
その他の種類のブロックのデータ開始点。データの終端はblk:end


次: , 前: ブロック形式, 上: B-ツリーの構造とアクセス

2.1.3 ツリー形式

WB-ツリー ("Wanna B-tree")

B-リンクツリー形式が採用された([SAGIV]参照)。リーフブロックの1つ1つには一定の数の(キーと値)のペアが入る。リーフ以外のブロック(インデックス)には、(キーとダウンポインタ)のペアが入る。 それぞれのブロックには1個の追加のキーの値、分割キーが入っている。分割キーはブロック内のその他あらゆるキーよりも厳密な意味で大きい。ツリーは、ツリーの各レベルのノードを分割キーの順序(NEXTポインタ)で連結することによって成長する。

一定のキー順序不変式が保持される限り、インデックスの挿入もしくはブロックの削除によるツリーの更新をいっさい行わないことを、われわれは選択した。

A
各レベルにおいてブロックは増加する分割キーの順序で連結されるので、チェーンにはすべての有効なブロックが出現する。
B
分割キーはレベルごとに一意である。
C
レベルN+1からのすべての「下向き」ポインタは次の下位レベルNのブロックBを指し示し、レベルNの分割キーSは、ポインタに連結されたキーS1に等しいか小さい。
C1
レベルNにおけるブロックBに対する分割キーがレベルN+1からのポインタに連結されたキーより厳密に小さければ(S<S1)、以下が成立するはずである。
  1. 分割キーS1を有するブロックB'がレベルNに存在する。
  2. B'はBからのNEXTポインタを追いかければ到達できる。
  3. レベルN+1にはB'へのポインタばかりでなく、BとB'の間のいかなるブロックへのポインタも存在しない。BからB'までの(キー、ポインタ)エントリ「空間」(split(B')、B)は、サブチェーンと呼ばれる。

C2
次のレベルで分割キーとして存在しないキーを下向きポインタが含む場合は無効である。

インデックス内のキーは、キーが存在するブロックの分割キーに正確に一致しなければならない点に注意が必要である。キーKがそれが指し示すブロックBの分割キーSより小さい場合、中間キーの検索は次のブロックへ向かう方向を誤ってしまう。KがSより大きい場合は、論理的にはK'はKの後ろに来るはずであるが実際にはK'<Kなので、S<K'<Kとなるようなキーの値K'で、B以降のブロックの分割が誤ってBの親に挿入される。

インデックスエントリの空間の概念は利用価値が高い。ブロック1つ1つの分割は次のより高いレベルにおける何らかの空間の「拡張」と考えることができるのに対して、「親への挿入更新」1つ1つは対応する空間の縮退と考えることができる点にわれわれは注目した。内部に1つのブロックだけを有する空間は「完全に縮退した」と呼ばれる。すべての空間が完全に縮退したとき、すなわちすべての保留中もしくは延期された挿入更新が実行されたときは、b-ツリーは完全に縮退する。最後に空間に関して、規則C1は次のようにより簡潔に表現できる:

C,C2
「空間は」正確に生成しなければならない(空間は閉じていなければならず、キーは正確に一致しなければならない)。
C1
すべてのインデックスにおいてエントリ空間は重複してはならない。

キー/値の順序、一様なリーフ/ノード形式

挿入が単純になることから元々はインデックスノードを(値、キー)の順序にしていたのだが、それはあきらめた。この方法では挿入/削除を伝播するコードをすべて、特殊ケースとして扱わなければならなかったからである。実際「挿入」と「削除」が非対称であるために、いずれか一方の一回の操作で、2つのブロックの変更(see 挿入メソッド)が必要となる場合が生ずる。 ただしツリーのすべてのレベルで(キー、値)の順序づけを使用したことにより、コードはかなり単純化された。


次: , 前: ツリー形式, 上: B-ツリーの構造とアクセス

2.1.4 分割キー

B-ツリーを編成するにあたって、分割キーは確立されたメソッドであると思われる。目的キーを探索するために潜在的に順方向に連鎖を作成しなければならない場合があるBリンクツリーにおいては、探索をいつ停止できるかを分割キーによって決定できる。 ブロックの終端に分割キーがあれば、1探索あたり1回のブロックアクセスが節約される。(分割キーがブロックの先頭にあるとすれば、探索を停止できるかどうかを判断するためにはチェーンの次のブロックを調査する必要があるだろう)。

終端キーの値

すべてのレベルにおいて、最大キーを終端の分割キーとして定義することは有効である。最後のキーが辞書式順序にしたがわない何らかの特殊な値(例えばヌル文字列)であるとすれば、空(最後)のブロックへの挿入で発生する問題をあげるまでもなく、コードはより複雑になる。0xffで始まる文字列の集合が分割キー専用に予約された。これを実際のキーの値として使用することはできない。終端キーの値の形式は、xFF(<レベル>)である。これによりレベルN+1の最後のキーはレベルNのいかなるキーよりも厳密に大きくなり、したがってレベルNのチェーン終端のキーをレベルN+1でキーとして挿入するときに特別扱いする必要がない。

固定分割キー/レベルからの独立

インデックスレベルの分割キーは、リーフレベルの分割キーと同じように動作するものとした。すなわち、1つのブロック内の分割キーは決して変化しない。この利点は、挿入と削除によって分割キーが変化することはありえず、変化を伝播させるコードが不要になることである。変化を伝播させるコードのテストは厄介なものである。これによってすべてのレベルが真に独立したものともなり、概念上有効な簡素化が行われる。

難点は、これによってインデックスブロックの最後のキーと値のペアとそのブロックの分割キー間に、デッドスペースが導入されることである。このためコードはわずかに複雑になり、平均探索パスもlog(N)よりわずかに(BFをツリーの分岐率として定数係数1+(1/BF)だけ)長くなる。より厄介なことには、挿入を行うとブロックの分割が発生する(「挿入」参照)。


次: , 前: 分割キー, 上: B-ツリーの構造とアクセス

2.1.5 挿入メソッド

インデックスへの挿入は、キー順序不変式が保持されるようにアトミック(分割不可)に見える必要がある。キー/値で順序づけられたインデックスブロックを使用している以上、親の更新挿入には次のように特殊な追加のステップが存在する。インデックスブロックBに新規のキーとポインタが挿入されると、値フィールドが連続する次のエントリとスワップされる。挿入がブロックの終端で行われるときは、残念ながら次のエントリは次のブロックB'にあるので、2つのブロックを変更しなければならない。(値/キーによる順序づけの利点は、挿入によって変更されるブロックが1つだけということである。ただしその代わりに、削除コードを同じように考えたら失敗する)。 コードはこのような場合を検査しており、先へ進む前に両方のブロックをロックする。(検討したもう1つの解は新規のキーがB'の先頭に来るようにBの分割キーをバックアップすることであるが、そうすると別の問題が導入される)。

上記のメソッドは(同時実行時にも)正しさを保存するが、次のようにさらに実装する必要がある2次的な欠陥が残念ながら存在する。ディスククラッシュの場合に正しさを保存する順序で2つのブロックに書込みを行う方法。Bだけが書込まれた場合、データベースには分割によって挿入を発生させたブロックへの2つのポインタが含まれることになる。B'だけが書込まれたとすると、ポインタの正しさが破壊される。(この種の問題は、複数ブロックにわたる一貫した変更を保持する必要があるあらゆる操作に内在すると思われる)。解決策はこの特殊ケースが実行中であることを知らせるルートへの注釈で書込みを取り囲み、変更中のブロック(B、B')とあるべきポインタを次のように示すことであると思われる。

ブロック分割によって作成された新規のブロックがB'である場合との一貫性を保つために、最初にブロックB'を書き出すことが選択された。極端な場合には壊れたDBが作成されるが、重複して指定されたブロックを削除する危険は回避される。これは直接的に回復を行う場合の適切な情報である。 (JONATHAN?)

(これ以外の代替手段も検討した。次のレベルで分割キーをバックアップすれば後続する挿入をアトミックにできるが、バックアップ操作には親のインデックスの一貫性を保持する場合の2つのブロックの一貫性という同じ問題がつきまとう。親のキーがバックアップされていなければ、後続するブロックの後続する分割によって、次のレベルでの更新は不正確なものとなる)。


次: , 前: 挿入メソッド, 上: B-ツリーの構造とアクセス

2.1.6 削除

削除は次のように2つの部分に分割することができる。削除するブロックは、親ブロックとと先行ブロックの両方から切り離さなければならない。切り離したブロックはその後で回収できる。

ブロックの切り離し

現在われわれは、親ブロックと先行ブロックの両方が変更可能な場合に削除が実行され、それ以外の場合には削除が失敗する(すなわち延期される)ように削除操作を単純化することを選択している。これによってブロックの削除はアトミックな変更となり、部分的削除を許可することによって導入される複数の問題が回避される(「同時実行性」参照)。

代替案: [WANG]は、ブロックをスワップすることによってPREVを使用せずにブロックを削除する賢明な方法を紹介している。これを同時実行性に対して堅牢に仕上げることは極めて困難と思われたので、われわれはPREVメソッドにこだわった。PREVメソッドでは結局、1/BF時間のブロックアクセスが増えるだけである。

削除中のクラッシュ

1回の削除における親ブロックと先行ブロックの書き出し順序については万一システムがクラッシュした場合にもチェーンが手つかずで残るように、まず親ブロックを書き出すことを選択した。削除しようとしていたブロックはチェーン内に留まるけれどもこれは「デッドブロック」であり、使用することはできない 「デッド」ブロックを取り扱う方法はインデックスの遅延更新と同時実行性で検討する。

ブロックの回収

[SAGIV]からの大きな変更は、SAGIVではブロックの複数のコピーが存在できると想定していた点である。この想定では削除したブロックの回収が複雑になる(SAGIVはタイムアウトベースのプロトコルを示唆している)。 われわれの方法ではブロックの複数のコピーは想定せずにロック、すなわち「名前」ロック(本質的には「削除」ロック)を追加することによって、各ブロックへのポインタがいくつ存在するかを追跡することを選択した。 ルーチンはポインタを取得するブロックに関する読み取り/書き込みをの実行を開始する以前に、ポインタに関する名前ロックを獲得しなければならない。 (書き込み期間中の読み取り要求という問題が発生しやすい場合のみを処理するSAGIVの方法とは対照的に、われわれの方法ではすべての操作にオーバーヘッドが導入されるという意味で、SAGIVの方法の方がほぼ確実に効率的である。このようなトレードオフに関する複数の実証的研究がこの結論を支持している)。一方名前ロックは、親ブロックや先行ブロック...を探索している間は前データの探索を開始するブロックを削除できないことを保障するなどの、その他の場合に有効である。

挿入と削除の非対称性

遅延された挿入は(キー、ポインタ)ペアの削除と等価ではないという意味で、「挿入」と「削除」が対称的でないことは覚えておくに値する。(キー、ポインタ)ペアの削除ではポインタが欠落したブロックがインデックス経由でアクセスできないまま残されるのに対して、遅延された挿入では依然としてNEXTポインタチェーン経由でブロックにアクセスできる。

この非対称性により、同時実行性に関する各種の問題を解決する試みはわたしが思い出せる限り終息した!

例:

  1. レベルnの分割キーをkとするブロックpから開始する。
  2. ブロックp'を追加して、pをk'で分割する。
  3. これでpもしくはp'を削除しても、次のように元々のインデックス内容は生成されない。

したがって、続く削除は挿入を「取り消す」ことができない。削除は関連する挿入の完了を待機するか、正しさを保持するための特殊な作業を行うかのいずれかを行わなければならない。


次: , 前: 削除, 上: B-ツリーの構造とアクセス

2.1.7 チェーン内の最後のブロックの非削除

われわれは現在、あらゆるレベルの最後のブロック、すなわちブロックの終端キーが存在するブロックの削除を許可していない。この削除はブロックの終端キーを確保しておくための特別な対応を必要とするからである。これを実現する方法の1つはnext-to-lastブロックの内容を前方コピーして、最後のブロックを削除する代わりにnext-to-lastブロックを削除することである。[例えばこの操作期間中に正しさを保存するなどの具体化しなければならない詳細が存在する]。


次: , 前: チェーン内の最後のブロックの非削除, 上: B-ツリーの構造とアクセス

2.1.8 Prev

[どう動作しているかの説明]

「分かってはいるけれどもまだ実装されていない難しいケースの解決策」: あるレベルの最初のブロック直後のブロックに下向きポインタが欠落している場合、PREVはそのブロックを探索できない。この問題はレベルNでブロックBのPREV-BLOCKが発生したときに発生し、レベルN+1でPREVが実行される。下向きポインタが欠落している場合、Bの分割キーに連結されたブロックB'はB自体ではなく、Bに先行する何らかのブロックである場合がある。この場合にレベルN+1でPREVを実行すると資源の浪費が発生する。ただし動作自体は正しい。この場合B'からのチェーンを作成するためには、同じエントリのPREVからよりもブロックアクセスが少い必要がある。ただしB'エントリがレベルN+1の1番目であった場合、PREVは誤ってそれがチェーンの最初にあると結論する。PREVは、(a)レベルN+1のBのエントリを常に調査して現在のブロックのポインタが本当に最新であることを確認するか、(b)単に自分がいつSTART-OF-CHAINに遭遇したかを確認するかのいずれかを行う必要がある。


次: , 前: Prev, 上: B-ツリーの構造とアクセス

2.1.9 ルートブロックプロトコル

ルートの一意性

われわれはルートのブロック番号が決して変化しないことを保証しており、したがってWB-ツリーが与えられた場合にはルートのブロック番号を一意の識別子として使用できることを保証する。その他のシステムではルートの参照に間接指定のレベルを導入することによって、一意のツリーIDを用意している。ルートの参照は頻繁に行われるのでこれは非効率的である。ルートが分割されるときはルートブロックに残っていたデータを保持するために新規のブロックが割り当てられ、その後以前のルートブロックが新規のルートとして使用される。これはブロックが分割された場合にもブロックIDが変化しないので、ブロックIDが信頼できないことを意味する。

ルートの削除とツリー内のレベル数の減少

実装されていない。


前: ルートブロックプロトコル, 上: B-ツリーの構造とアクセス

2.1.10 その他のツリー編成

ツリーレイアウトについては別の可能性が複数存在する。その中には、挿入の難しいケースなどの現在のレイアウトでは複雑な操作を単純化できるものもある。その他の可能な選択には以下が含まれる。

わたし(RJZ)が好むもう1つの仮定は、[SAGIV]のように複数バージョンのブロックの存在を許可することである。これは次を意味する。

恐らくいつか時期が来れば、以上の相互関係を方法論的に探求できるであろう...


次: , 前: B-ツリーの構造とアクセス, 上: 理論

2.2 同時実行性


次: , 前: 同時実行性, 上: 同時実行性

2.2.1 名前アクセス(および削除したブロックの再利用)

ブロックを安全に削除できる時期を明示的に知ることができるためには、ポインタを取得したブロックに関する「読み取り/書き込み」の実行に移る以前に、ポインタに関する名前ロックをユーザがぜひとも取得しなければならない。名前ロックは次のようにその他の場合にも有効である


次: , 前: 名前アクセス(および削除したブロックの再利用), 上: 同時実行性

2.2.2 失敗時の脱出プロトコル/アクセス競合時の戦略

ブロックされた操作は現在RETRYERRのエラーコードを返して単に失敗しようとする。後で安全に再試行できるようにするためである。 現在の発想は「読み取り書き込み」の競合が発生したときは、常にこれを利用することである。 (SAGIVの方法を使用する場合はこれは不要である) 。ただしブロック読み取りの待機、名前ロックに関する待機、インターロック操作に関する待機などのその他各種のロックアウト条件と待機条件が発生する可能性がある以上、そのような機能は必ず必要になるのであり、したがって「読み取り書き込み」のブロッキングの処理にそれを使用しようとすることもまた合理的であろう。

すべての場合に適切な情報を上位に渡すコードを再編成する複雑さのために、これは「本当にはまだ実装されていない」。 (Topレベルルーチンはこのようなコードを返すが内部ルーチンは実際にはまだこれを使用しておらず、したがって再試行機能は現実には存在していない。)


前: 失敗時の脱出プロトコル/アクセス競合時の戦略, 上: 同時実行性

2.2.3 インデックスの遅延更新と同時実行性

基本戦略はブロックが分割され、空になって完了するキーの挿入/削除ができることであるが、このときキーはバックグラウンドで成功するまで遅延更新を再試行する何らかのプロセスで親の更新/ブロックの削除の待ち行列に入る。

問題は親の更新と先行ブロックの更新という、待機可能な2つの独立した操作が削除に含まれることである 。この2つの更新は、挿入が発生できないようにブロックがまず「デッド」とマークされていれば、独立して行うことができる。残念ながら、同じキーにたまたま関係する削除と挿入の正しい順序づけを巻き込む、ごくまれで複雑な難しい事例の類がある。例えばブロックは、キーを削除して削除することも可能であり、その後、後続する分割でそのブロックを再導入して、削除をやり直すことができる。インデックスレベルの操作が遅延された場合、遅延された操作の順序づけによって、結果のツリーが正しいかどうかが定まる。

ブロック削除を(上で定義するように)アトミックにすれば、このプロセスは大きく単純化される。このとき挿入中もしくは削除中のブロックは、ブロックそれ自体のセマフォとして使用できる。

われわれは、遅延更新戦略を採用することを選択した。すなわち、更新を直ちに実行できない場合は保留中の親の更新キューを保持するのではなく、更新は放棄することとした。これは、レベルN+1の更新はレベルNのチェーンから再構築できるために、可能になることである。

これで、更新するパスに実際に遭遇した次のような場合には、遅延更新は性能のみに影響することになる: 2つのブロックにわたってチェーンを作成しなければならない事が判明した場合、すなわち親の更新がまだ発生していない場合。空ブロックに遭遇した場合、すなわち削除更新が発生していない場合。考え方は、このような「非効率性」の解決は要求があり次第、すなわち非効率的な例に遭遇した場合にだけ、それを解決する労を取るということである。さしあたっては、すべてのブロック削除とすべての挿入更新が遅延されると想定する。

この基本アルゴリズムは以下の通りである。

  1. キーを検索して順方向の連鎖を作成しなければならない場合は、次のレベルでは欠落するポインタが存在するはずである(遅延挿入)。したがって、この場合は挿入を試みる。キーのNEXTとPREVに到達するために順方向連鎖を作成するのは普通であり、したがって更新を試みさせてはならない。
  2. 空のブロックに到達したときは、そのブロックへの挿入を行っている場合を除いて常にそのブロックの削除を試みる。削除の試みは関連する親の更新が完了しない限り失敗する。すなわち成功するのは当該ブロックが完全に縮退した空間内部にある場合だけである。

ブロックの削除中に入出力障害が発生した場合に「デッド」ブロック、すなわち親のレベルから到達できないブロックが残る可能性が大きな懸念であった。このブロックはまだチェーン内にあるにもかかわらずブロックへの下向きポインタが存在せず、探索がそのノードで停止できない状態が発生する。ブロックがデッド状態になった場合はブロック内部への挿入やブロックの復元を防止する必要があるということが問題なのである。それを行うとエントリの一貫性が損われる場合があるからである(ブロックがデッドである間に分割キーよりも小さいキーの何らかの挿入がが発生したと仮定する。挿入はインデックスによって次のブロックへ仕向けられ、そこに配置される。このときにブロックを復元すると、キーの順序づけは正しくないものになる)。ただし次のようにB-ツリー操作が遭遇する可能性がある遅延更新状況の種類を観察すれば、これを防止できることがわかる。

ツリーを、インデックスエントリがまたがるブロックのエントリの集合が形成するインデックスエントリ空間1つ1つからなる入れ子になった空間ととらえるならば、GET、PUT、REMなどの探索のみを使用する操作中は、探索の場所はルート内の何らかのエントリ空間の範囲内に厳密にとどまることがわかる。ブロックは親のポインタが完全に更新されるまで、すなわち親のポインタ空間が正確に1つのブロックになるまでは削除されないようにしている。今度は親のポインタを持たない空のブロックを残して、ブロック削除が途中で失敗した場合を考えてみる。このブロックはFIND-NODEによっては、したがってINSERTによっては到達できない!これは、INSERTが空のブロックに遭遇した場合は、そのブロックへの挿入が有効でなければならないことを意味する。

この帰結は、次のように興味深いものである。

  1. これはおそらく、空間に「またがって」連鎖を作成する可能性のある次の操作の場合にのみ、デッドブロックに注意する必要があることを意味する: NEXT操作とPREV操作である。 (PREVへの影響は正確には何があるか?)
  2. これは、(特別にデッドブロックをを探さない限りは)「デッド」ブロックを削除できないことを意味する。ただしデッドブロックは、(a)ごくまれな種類のイベントの場合にだけ作成され、(b)NEXTとPREVが空のブロックを無視するように(すなわちデッドブロックの分割キーの値を無視するように)取り決めておけば別に害にはならない。
  3. 先に定義した遅延削除の再構成の通り、ブロックが完全に縮退した空間内部になければ、削除は単に成功できないだけである。 これは、空間を経由して連鎖を作成するときは空白ブロックの削除を試みる場所が存在しないことを意味する。すなわち(1)FIND-ENTでDOWNポインタを追跡しているとき、もしくは(2)NEXT操作(もしくはPREV操作?)によって追跡する場合には、遭遇した空のブロックの削除だけを試みる必要がある。

[これに気がつけば、ブロック削除は実際には(またまた)2つの操作に分けることができる。追加される複雑さはこのとき、デッドブロックを検出する方法を実装する必要があるということだけになる。すなわち、削除を試みてはならないデッドブロックと空のブロックを大きな空間の中央で識別する必要がある。当該ブロックが何らかの空間に連続するかどうかだけを検査すればよい。これを効率的に行う方法はまた別の話である。]

具体的には、遅延操作を検出する方法は次のように行われる。

  1. 親の遅延更新(欠落したDOWNポインタ)の再構築。

    ブロックBのNEXTポインタを(FIND-NODEで)追跡しなければならないときはいつも、(キー、値)ペア(split(B)、next(B))を使用してPARENT-INSERT-UPDATEを試みる必要がある。「デッドスペース」に遭遇したときは、FIND-NODEは下向きではなく右向きに連鎖を作成するように定める必要がある。かつ、この場合はPARENT-INSERT-UPDATEを試みてはならない。

    PARENT-INSERT-UPDATEは、次の場合に失敗することがある。

    1. なんらかの別のプロセスが既に更新を行っている(最初に親をロックしたものが制御を獲得し、それ以外は失敗して排除される)。
    2. キーsplit(B)が既に存在する(削除が保留中であることを意味する、ただしこれは実際には発生しないはずである)。
    3. 更新はブロックの分割を必要とするが、分割できるブロックが存在しない。
  2. 遅延したブロック削除の再構築:

    FIND-NODEもしくはNEXT/PREV操作で空のブロックに到達したときは、PARENT-DELETE-UPDATEを必ず試みる。

    PARENT-DELETE-UPDATEは次のときに失敗する必要がある。

    1. キーは発見されたけれども別のブロックを指し示している(包蔵する空間が完全には縮退していないことを意味する)。
    2. ブロックが名前ロックされている(これは、名前ロックは残っても安全であることを意味する。起こり得る最悪のケースはブロック削除がいくぶん遅延される可能性があることだからである)。
    3. 別の誰かがこのブロック上にPARENT-DELETE-UPDATEを行っている(これは削除プロセスに削除中のブロックを最初に名前ロックさせることによって、保証することができる)。
    4. 変更を必要とするブロックにロックされているものがある(親もしくはprev)。
  3. NEXT-KEY操作が潜在的デッドブロックで停止しないように、NEXT-KEY操作を行うコードを修正する必要がある。 CHAIN-FINDは空白ブロックを無視する必要はない。

    実際には、平常時にも更新ルーチンを起動したくなる。すなわちブロック分割後には挿入更新を、ブロックが空になった後には削除更新を試みたくなる。

    銘記しておかねばならない新規の統計が若干存在する。これには以下が含まれる。

    (前方連鎖の数もオーバヘッドの測定である。)

    [注:このメカニズムは、待ち行列を作成する次のような単純な方法にも対応している。更新が延期されたブロック番号のリストを保持しておいて、利用率が低いときにそのブロックに対してFINDを実行すれば、その副作用としてブロックが更新される...。]

—————–

[その他の戦略も検討したが、次のようにかなり複雑になるか、オーバヘッドが大きくなるか、もしくは不要な遅延が導入されるものであった。

インデックスの遅延挿入操作と遅延削除操作の待ち行列を力づくでシリアル化する切り口が、1つ考えられる: 操作を正確に到着した順序で行うのである。次の別法の方がおそらくより簡単であろう: キーでソートしてタイムスタンプを打てばいい!

待ち行列が増えすぎた場合には遅延操作の実行に資源を振り向けたいので、インタープリタはプロセスを単純に1つ1つの遅延操作に専念させるべきであるとも思われた。

[WANG]は削除された操作の待ち行列をあて先ブロック上に保持する。 この難点は、ブロックが分割もしくはマージされるされるときは、遅延操作待ち行列も必ず分割もしくはマージする必要があるということである。うーみゅ!]


次: , 前: 同時実行性, 上: 理論

2.3 バッファI/Oとフリーリストの管理


次: , 前: バッファI/Oとフリーリストの管理, 上: バッファI/Oとフリーリストの管理

2.3.1 バッファの回収

時間対レベル対汚損

これは昔からある厄介な問題である – 実際には評価されていないか調節されていない複雑なシステムが配置されており、Jonathanは単純に最初に発見した自由なバッファ(もしくは解放可能なバッファ)を使用することを提案した。


次: , 前: バッファの回収, 上: バッファI/Oとフリーリストの管理

2.3.2 更新アクセス

単に#fを発行してそれから更新を行うだけでは充分ではない場合がなにがしか存在するとわたしには思われたが、今即座には思いつくことができない...


次: , 前: 更新アクセス, 上: バッファI/Oとフリーリストの管理

2.3.3 データブロックの遅延書き込み

注: これは、前述の「遅延インデックス更新」からの異なる種類の照会である。前述の遅延操作では正しさが保存されていたが; 今回はそうではない。考え方としては、安全に失ってもよい更新の数が「わずか」であれば、入出力トラフィックを軽減できるということである。

説明と目的

この趣旨は、データベースの構造に障害が起きなければ更新が失われてもよいという意味で、リーフブロックの書き込みを延期することによって入出力トラフィックを軽減できるということである。これは、問題のデータ更新がデータベースやアプリケーションに危険でない場合にのみ機能する。 現在のところ、ツリーの種類が「ディレクトリ」以外であれば、データツリーに対するリーフの更新は、PUTとREMの両方とも必ず遅延される。(「ディレクトリ」リーフブロックは更新のたびにディスクに書込まれる)。データブロックが書込まれる頻度はユーザアプリケーションが制御すべきであるというのが基本の考え方である。

さらに、PUTとDELETEの照会は個別に制御できなければならない。 この機能は例えば次のように、フリーリストを保守する場合にデータベース自体が必要とするものである。削除済みブロックの「挿入」は遅延して差し支えない。起こり得る最悪の事態はフリーブロックの消失だからである。ただしフリーリストからの「削除」は直ちに更新しなければならない。さもないとブロックが二重に割り当てられる場合があるからである。

実装

ハンドルは以下の論理値が含まれるように拡張されている。

  1. SAP: PUT後のブロックの保存
  2. SAR: REMOVE後のブロックの保存
  3. SAC: キャッシュされたブロックに変更があった場合のブロックの強制保存
  4. FAC: キャッシュされたブロックに変更があった場合の全バッファのフラッシュ(現在は実装されていない–将来に予定される機能)

これらのビットは例えば次のように使用される。

ディレクトリ
SAP=SAR=1;
フリーリスト
SAR=1; SAP=SAC=0;
ユーザデータ
SAP=SAR=SAC=0;

これらのビットの状態は、(HAN-SET-WCB han new-bits)を使用していつでも変更できる。WRITE-CACHE-BLKを呼び出せば現在のブロックが書き出されたことが、WRITE-MODIFIED-BLKSを呼び出せばすべての変更済みブロックが書き出されたことがユーザに保証される。 ディレクトリツリーがオープンもしくは作成されたときは、現在は安全のためにHAN-SAPとHAN-SARが強制的に実行される。さらにフリーリスト書き込み制御ビットは、フリーリストのブロックの種類にかかわらずOPEN-SEGによって上記の通りになるように強制される。


次: , 前: データブロックの遅延書き込み, 上: バッファI/Oとフリーリストの管理

2.3.4 最後に使用された(リーフ)ブロックのキャッシュ

非常に良好に動作している。

以下はまだ実装されていない: 同じTRY-GET-ENTプロトコルを使用すれば、実際にはより賢くすべてのノードの親、さらにはPREVすらキャッシュできるであろう!


次: , 前: 最後に使用された(リーフ)ブロックのキャッシュ, 上: バッファI/Oとフリーリストの管理

2.3.5 複数の読み取りアクセス

複数の読み取りアクセスにはまだ対応していない。「読み取り」と「読み取り」の競合が発生する可能性がある。 この制限があるために、現在は同定できなくなっているある種の別の問題に遭遇せずにすんでいることを注意しておく必要があると思われる。


次: , 前: 複数の読み取りアクセス, 上: バッファI/Oとフリーリストの管理

2.3.6 フリーブロックの管理

概要:

現在の問題:

これまでのすべての努力にもかかわらず最後の週に(1/8)われわれは、以下のような問題のために、並行操作でのフリーブロック管理には障害が発生する場合がまだ存在すると結論した。

肯定的な側面としては、フリーリストの挿入によってツリー全体が分割されるために、充分なフリーブロックを割り当てる必要はないことがわかった - リーフの分割以外のあらゆる分割は、そのとき利用できるフリーブロックが存在しなければ単に遅延することができるからである!(しかも、フリーリストの操作によって引き起こされるあらゆる挿入更新も同様である)

考えてみれば、フリーリストの挿入期間中にブロックが不足した場合は挿入を失敗させてもよい。単にディスクブロック1つを失うだけだからである おそらくこれが答えとなるだろう。


次: , 前: フリーブロックの管理, 上: バッファI/Oとフリーリストの管理

2.3.7 バッファ管理ルーチン

バッファをパージする次の2つのルーチンが作成された。

FLUSH-BUFFER(ENT)は、ENTが汚損されかつロック解除されていればENTを書き出す。 FLUSH-BUFFER(ENT)はENTがロックされていればTERMINATEDを、書き出しを試みて失敗した場合はRETRYERRを、それ以外の場合はSUCCESSを返す。

PURGE-BUFFER(ENT)はENTが汚損されていればENTを書き出し、その後バッファをすべて解放する。このルーチンはバッファのアクセスステータスを無視するので、ユーザがこれを呼び出してはならない。PURGE-BUFFER(ENT)は常にSUCCESSを返す。

(DO-SEG-BUFFERS SEG#FUNC)を使用して関数を与えられたセグメントのすべてのバッファに適用する。例えば(DO-SEG-BUFFERS SEG#FLUSH-BUFFER)を使用して、セグメントSEG#のディスクファイルが最新であることを保証することができる。 FUNCがSUCCESS以外を返した場合はDO-SEG-BUFFERSは停止する。FUNCの結果が返される。すべてのバッファの処理に成功した場合はSUCCESSが返される。すべてのセグメントを処理する場合は、SEG#=-1を使用する。

(CHECK-BUFFER ENT) バッファが書き出されてロック解除されたことを確認し、そうなっていないバッファを修復する。


前: バッファ管理ルーチン, 上: バッファI/Oとフリーリストの管理

2.3.8 文書化を必要とするその他の問題


次: , 前: バッファI/Oとフリーリストの管理, 上: 理論

2.4 エラー処理

問題: 呼び出しは以下を識別する適切な情報を返す必要がある。

  1. 例えば再起動可能な操作
  2. 再起動不能障害(例えばディスク入出力エラー)
  3. 無効な結果(例えばキーが見つからない)
  4. 「実際の値」、例えば返された文字列の長さ、もしくはヌルポインタに対するENTポインタ。

解: 「成功」コードとして利用できる非負の戻り値を残し、境界が定められた範囲の負の数を「障害」コードとして使用する。正準化(キャノニカル)成功コードは0であるが、値(文字列長さ、ENTポインタ)を返す必要があるルーチンは0を返すことができるので、値0を「成功」コードとして解釈することができる。

障害には「程度」があり、負のコードは増大する重大度に応じて、以下のように分割される。

value C名称 意味


0 success 実行に成功
-1 notpres 実行に成功、データが存在しないか変更が行われなかった
-2 terminated 障害、損傷なし、呼び出し元は操作を再試行できる
-10 retryerr 障害、損傷なし、呼び出し元は操作を再試行できる
-15 argerr 障害、損傷なし、呼び出しがエラーで終了した
-20 noroom 障害、損傷なし、ファイルに余地がない
-30 typerr 障害、ファイルもしくはオブジェクトの型が正しくなかった
-40 ioerr 入出力エラー、データベースが損傷を受けた可能性がある
-45 strangerr 内部エラー、データベースが損傷を受けた可能性がある
-90 unkerr プレースホルダコード
-100 maxerr

最初のクラスはエラーなしで完了した操作を示す。二番目のクラスは完了できなかった操作を示すが、データベースは正しい状態のままであることが保証されており、再試行が可能(もしくは簡単に修正可能)である。3番目のクラスは完了できなかった操作を示し、データベースも損傷していないが、修復や再起動が簡単にはできない。最後のクラスはエラー条件によってデータベースが壊れたか、もしくはエラー期間中に壊れたデータベースが検出されたことを示す。

戻りコードが範囲NOTPRES-MAXERR内部にあれば、述語手続き(ERR?code)は#tを返す。述語手続き(REALERR?code)は"not there"もしくは"stop processing"メッセージとは対照的に、CODEが現実のエラーの場合に#tを返す。


次: , 前: エラー処理, 上: 理論

2.5 長い値フィールド

値文字列用の256.Bの長さの制限は、WBに可能な多くのアプリケーションに対する障壁であった。db.cdb:getdb:put!手続きは、64770.Bまでの長さの値文字列で機能する(see レコード操作)。

長さLの値文字列は次のように処理される。

0.B <= L <= 255.B
値文字列は与えられたキーとともに与えられた通りに格納される。
256.B <= L <= 64770.B
値文字列の最初の255バイトは与えられたキーとともに与えられた通りに格納される。 値文字列の次の255バイトのデータブロックは、L/255-1の連続するキーと値のペアとして格納される。それぞれのデータブロック用のキーは、ブロックに追加されるインデックスバイト 1<= k <=254で与えられるキーである。

bt:scanの使用法は、長い値文字列のために複雑になっている点に注意が必要である。

拡張の提案

以下は長さに制限がない値文字列への拡張の提案である。

256.B <= L <= bsiz - 20
b-ツリーの値フィールドは、型がdatalongの値が入るブロックを指し示す。1

make_seg()bsiz引数もしくはmake-segblock-size引数は、そのセグメントにおけるすべてのWBブロック(ページ)のサイズである。

bsiz < L
値はdatalongブロックのチェーンもしくはツリーの先頭を指し示す。 取り出した値の集合状態によって、実用上のサイズが制限される。ディスクの充填率はL >> bsizの場合に良好である。

興味深い変種は、datalong用に1つとその他すべて用に1つの、2本のツリーを用意するものである。2本のツリーを(独立したファイルに格納された)独立したセグメントに置けば、非datalong操作の速度に影響を与えずにdatalongのセグメントブロックサイズを最適化することができる。

bsiz < L
値は外部ファイルに含まれるデータを示す。ディスクの充填率はL >> bsizの場合に良好である。取り出した値の再構築不要。mmap()を使用。


次: , 前: 長い値フィールド, 上: 理論

2.6 長さ制限のないキーと値

文責Jonathan Finger

以後mainslaveとして参照する2つのbツリーを使用する。 記法D[123,4567]は、文字列D\3 1 2 3 \4 4 5 6 7に変換される。ただし\3はアスキー文字の3など(続く数字文字列の長さ)である。これによりキーは数値順にソーティングされる。

  1. データ (容易な部分)

    データの最初のバイトはフラグである。

    IF データ長さ < 255

    THEN

    1 - (データ長さ + 1)バイトに格納する

    ELSE

    スレーブbツリーでキーDの値を増分する(Dはデータ)

    例として、新規の値が2357,データが1万バイトとすると

              次のようにデータを格納する。
              D[2357,0] = 最初の250バイト
              D[2357,1] = 2番目の250バイト
                .
                .
                .
              D[2357,249] = 最後の250バイト
         

    新規の値をセットするときにその長さが > 254バイトであれば、必要に応じて追加や削除を行って名前D[2357]を再利用すればよい。その際既存のノードは(ほとんどが)同一サイズで、終端で追加や削除が行われるので、既存のノードを上書きする方がはるかに効率的であることは注目に値する。 新規の値が<255バイトであれば、D[2357]を削除してマスターbツリーに値を格納する。

  2. キー(困難な部分)

    IFキー < 250バイト

    THEN

    通常通りマスターファイルに格納する

    ELSE (キー >= 250バイト)

    キーをデータブロックC0…CNに分割する。最初のブロックの長さは250バイト、残りのブロックの長さは220バイトである。

    エントリを作成する(キーVの現在の値を243とする)。

              マスターbツリー
              C0 = (フラグ)244
              スレーブbツリー
              V[244,C1] = 245
              V[245,C2] = 246
                  .
                  .
                  .
              V[244+N、CN] = データ
         

    1回のgetは今度はキーの分割とチェーンの追跡で構成される。 検討すべき問題が多数になることから、put、delete、next、prevのコードはすこし繁雑になる。

この方式であれば、キーとデータの長さを無制限にできるとわたしは信じている。 性能はすばらしいとはいえないかもしれないが、許容範囲内であろう。 これにより良好なキー圧縮が得られるはずである。


次: , 前: 長さ制限のないキーと値, 上: 理論

2.7 予定

RJZリスト項目の大部分は完了したと思われる。

RJZ修正1993年4月8日

B-ツリーの保守

I/O

同時実行性

エラー処理

その他

設計/マニュアル


前: 予定, 上: 理論

2.8 その他

「最大キー」(チェーンの終端マーカー文字列)。
最初のバイトがFFのキーを分割キー用に予約してあるので、ユーザはこれらのキーを利用できない。
NULLキー
WBはキーとしてのヌル文字列の使用に対応している(Sliced Breadはこのキーを特別に処理している)。
最小キーと最大キーにもとづく検索
ヌル文字列をキーとして使用できるとすれば、最初のキーがNULLであった場合にもNEXT(least)が最初のキーを生成するような、“least"キーを指定する方法が必要になる。長さが-2と-1の、それぞれ最小と最大のキーの値を表す特殊なキー文字列が用意されている。これらのキーはNEXTとPREVでのみ有効である。これらのキーをデータに連結することはできない。
TSCAN、TSTATSを文書化する必要性。

2.8.1 参考文献

B-ツリーに関する包括的な参考文献は以下で検索できる。 http://www.informatik.uni-trier.de/~ley/db/access/btree.html

[BM72]
R. Bayer and E. McCreight. Organization and maintenance of large ordered indexes. Acta Informatica, 1:173-189, 1972.
[SAGIV]
Yehoshua Sagiv. Concurrent Operations on B*-trees with Overtaking. JCSS 33(2): 275-296 (1986)
[WANG]
W.E. Weihl and P. Wang. Multi-version memory: Software cache management for concurrent B-trees. In Proc. 2nd IEEE Symp. Parallel and Distributed Processing, 650-655, 1990.


次: , 前: 理論, 上: Top

3 Cインタフェース


次: , 前: Cインタフェース, 上: Cインタフェース

3.1 コンセプト

segmentは自己完結的なBツリーの集合で、一つ一つのツリーは通常固有の(ディスク)ファイルに連結される。WB関数は0からnum_segs - 1までの整数でセグメントを参照する。

— Cプリプロセッサ定数: num_segs

num_segsdefs.scmとそれから導かれたdefs.hで定義されている。num_segsのデフォルト値は10で、その最小値は1である。

ファイルベースであるか否かに関わらず、セグメント一つ一つにはディスクブロックのfreelistが保持されている。 新しく作成されたセグメントでは、ほぼすべてのブロック番号がフリーリストに入っている。

— Cプリプロセッサ定数: flc_len

flc_lenは、フリーリストに分割が発生した場合に必要な最大ブロック数の2倍以上大きくなければならない。flc_lenの最小値は10である。

— Cプリプロセッサマクロ: err_P (x)

エラーコードが有効であれば(-1 ... MAXERR) xを返し、有効でなければ0を返す。

— Cプリプロセッサマクロ: success_P (x)

err_Pの否定。


前: コンセプト, 上: コンセプト

3.1.1 診断チャネル

機械変換されたソースでは、プラットフォームから独立した診断、警告、エラーメッセージの記録方法としてdprintfを使用する。 tdprintf

— Cプリプロセッサマクロ: dprintf ((diagout、const char *template, ... ))

dprintfへの単一の引数は小括弧に入れた引数のリスト(例えば二重括弧)でなければならない。このリスト内部の最初の引数は文字通りdiagoutとする必要がある。 templateprintfスタイルの書式文字列で、printfのように後ろに書式用の引数が続く。


次: , 前: コンセプト, 上: Cインタフェース

3.2 SEG

make_segの呼出しで渡すセグメントのbsizは、性能にとって重要なパラメータである。ブロックを横断するCPU時間とファイルシステムの待ち時間とのバランスを左右するからである。bsizは、ファイルシステムブロックサイズの整数倍でなければならない。

1990年代には、われわれの公称 bsizは2.kiBであった。 これは現在では、おそらく4.kiB、8.kiB、16.kiBのいずれかにする必要がある

— 機能: C関数 int open_seg (int seg, unsigned char * filename, int mode)

segは非負の数でなければならない。。filename内のデータベースsegをオープンし、オープンに成功した場合はsegを、さもなければステータスコードを返す。mode引数に0を渡した場合、データベースsegは読み取り専用になる。mode引数に2を渡した場合、データベースは読み取り書き込み用になる。

— 機能: C関数 int close_seg (int seg, int hammer)

データベースセグメントsegとデータベースセグメントが入っているファイルを閉じる。hammerがNULLでかつバッファの解放になんらかの問題があった場合、クローズは異常終了する。ステータスコードが返される

— 機能: C関数 int make_seg (int seg, unsigned char * filename, int bsiz)

整数segには未使用のセグメントを指定しなければならない。 整数 bsizにはB-ツリーブロックサイズを指定する。 bsizは、ファイルシステムブロックサイズの整数倍でなければならない。 公称値は4096である。

make_segは、名前がfilenameの新しい空のデータベースを作成する。ステータスコードが返される。新しいデータベースを使用するには、open_segを呼び出す。

次の関数に渡す書き込み制御ビット引数(wcb)は、各種操作の後のファイル更新の遅延時間を制御する。このビットは以下のように定義される

C名称 意味
1 wcb_sap PUT後のブロックの保存
2 wcb_sar REMOVE後のブロックの保存
4 wcb_sac キャッシュされたブロックに変更があった場合のブロックの強制保存
8 wcb_fac キャッシュされたブロックの変更後に全バッファをフラッシュする(現在は実装されていない)。

— 機能: C関数 int bt_open (int seg, long blk_num, HAND * han, int wcb)

セグメント番号seg、ブロック番号blknumへのbt-handleをオープンし、ブロックの型を返す。 ブロックが存在しないかルートブロックでない場合は、(負の)ステータスコードが返される

— 機能: C関数 int bt_create (int seg, int typ, HAND * han, int wcb)

型がtypのセグメントsegに新しいルートブロックを作成し、そのルートブロックへのbt-handle hanをオープンしてステータスコードを返す。segに充分な容量がない場合は新しいツリーを作成してステータスコードnoroomを返す。bt_createは一時b-ツリーの作成に使用できる。一時ツリーは、システムがクラッシュした後に検査プログラムで回収される。ツリーを永続的なものにする場合は、ツリーをディレクトリ(ツリー)に追加する。

— 機能: C関数 int bt_close (HAND * han)

bt-handle han を閉じて SUCCESSを返す。

現在のところ、 bt_close には hanをクリアする以外の効果はない。


次: , 前: SEG, 上: Cインタフェース

3.3 HANDとツリー操作

注: この項のデータ操作コマンドは、以下の意味を持つnotpresを返すことができる。

bt-get そのようなキーは存在しない。
bt-next NEXTキーが存在しない(つまり与えられたキーはLASTキーだった)。
bt-prev PREVキーが存在しない(つまり与えられたキーはFIRSTキーだった)。
bt-rem キーを発見できなかった。
bt-put 未使用(WRITEに対称的でも良い).
bt-write キーが発見されなかった。したがって書込みが行なわれなかった。

— 機能: C関数 int bt_get (HAND * han, unsigned char * key_str, int k_len, unsigned char * ans_str)

key_strは長さk_lenの文字列。bt_getはツリーhan内のkey_strに連結された値を文字列ans_strに格納する。bt_getans_strに格納された値を返す。さもなければエラーコードを返す。

— 機能: C関数 int bt_next (HAND * han, unsigned char * key_str, int k_len, unsigned char * ans_str)

key_strは長さk_lenの文字列。bt_nextは、ツリーhan内のkey_strの後の次のキーを文字列ans_strに格納する。bt_nextans_strに格納された値を返す。さもなければエラーコードを返す。

— 機能: C関数 int bt_prev (HAND * han, unsigned char * key_str, int k_len, unsigned char * ans_str)

key_strは長さk_lenの文字列。bt_prevは、ツリーhan内のkey_strの前の最後のキーを文字列ans_strに格納する。bt_prevans_strに格納された値を返す。さもなければエラーコードを返す。

— 機能: C関数 int bt_rem (HAND * han, unsigned char * key_str, int k_len, unsigned char * ans_str)

key_strは長さk_lenの文字列。bt_remはツリーhan内のkey_strに連結された値を文字列ans_strに格納した上で、その連結をツリーhanから削除する。bt_remans_strに格納された値を返す。さもなければエラーコードを返す。

ans_strが0の場合、bt_remはツリーhanから連結 key_strを削除し、成功すればSUCCESSを、失敗すればエラーコードを返す。

— 機能: C関数 int bt_rem_range (HAND * han, unsigned char * key_str, int k_len, unsigned char * key2_str, int k2_len)

key_strは長さがk_lenバイトのキーが入る最大長(256バイト)の文字列でなければならない。 bt_rem_rangeは[key_str ... key2_str)と関連する値を削除する。key2_str <= key_strの場合は、key_strが発見された場合でも削除は行なわれない。bt_rem_rangeは操作が完了した場合にSUCCESSを返し、完了しなかった場合はエラーステータスを返す。

— 機能: C関数 int bt_put (HAND * han, unsigned char * key_str, int k_len, unsigned char * val_str, int v_len)

key_strは長さk_lenの文字列、val_strは長さがv_lenの文字列である。 bt_putkey_strに連結された値をツリー han内のval_strとする。 bt_putは操作のステータスコードを返す。

— 機能: C関数 int bt_write (HAND * han, unsigned char * key_str, int k_len, unsigned char * val_str, int v_len)

key_strは長さk_lenの文字列、val_strは長さがv_lenの文字列、val_strは長さがv_lenの文字列である。現在hankey_strとの連結が入っている場合、bt_writeはツリーを変更せずにnotpresステータスコードを返す。

それ以外の場合、bt_writekey_strに連結された値をツリーtree han内のval_strとする。 bt_writeは操作のステータスコードを返す。


前: HANDとツリー操作, 上: Cインタフェース

3.4 Scan

— 機能: C関数 int bt_scan (HAND * han, int operation, unsigned char * kstr1, int len1, unsigned char * kstr2, int len2, int_function func, long * long_tab, int * respkt, int blk_limit)

bt_scanは複数の機能を実行しながら、[kstr1..kstr2)の範囲のすべてのキーを走査する。

operation func RESULT
COUNT-SCAN NIL 範囲内のすべてのキーをカウントする。
COUNT-SCAN given funcを満足する範囲内のすべてのキーをカウントする。
REM-SCAN NIL 範囲内のすべてのキーを削除する。
REM-SCAN given funcを満足する範囲内のすべてのキーを削除する。
MODIFY-SCAN NIL ARGERR
MODIFY-SCAN given funcを満足する範囲内のキーの値を更新する。

bt_scan走査が完了した場合はSUCCESSを返す。それ以外の結果コードが返された場合は走査を再開できる。可能な結果は次の通りである。

NOTPRES
blk_limitを越えたことを意味する。
RETRYERR
funcもしくは削除からRETRYERRRが返されたことを意味する。
TERMINATED
funcが走査の終了を要求したことを意味する。
<その他のエラー>
funcもしくはDELETEがこのエラーに遭遇したことを意味する。

データブロック一つ一つは、単一の操作で走査、削除、変更のいずれかが行なわれる。すなわちブロックが検索されて一度だけロックされ、すべての変更が行なわれた後に初めて書き込まれる。唯一の例外は、ブロックの分割を発生させる場合がある、値サイズを増加させるMODIFY-SCANである。この場合は検出が行なわれ、PUTとそれに続くNEXTへの変換が行なわれる。これにより、次の2つの帰結が発生する。データはPUTが発生するたびに書き出されるので、PUTの最中にRETRYERRが発生すると、分割を発生させたキー値について、funcが2回以上呼び出される場合もあることが考えられる。ただしSCANはこの場合にも実際には1回しか変更を行なわないことを保証している(したがって例えばINCREMENT-RANGEを書くことが可能である)。

funcにはキーと値(のコピー)へのポインタとユーザ引数が1つ渡される。

          func (keystr klen vstr vlen extra_arg);
     

funcには、DELETE/COUNTの場合はSUCCESS、SKIPの(すなわちDELETE/COUNTを行なわない)場合はNOTPRES/NOTDONE、現在のポイントから再開可能な方法で走査を終了させるそれ以外のコードのいずれかを返すことが期待される。 MODIFY-SCANで値の変更がある場合は新しい値の長さが返される。 上記の場合以外には、指定範囲内のキーの値に対して該当する値についてのみfuncが呼び出されることを呼出し元は信頼してよい。

kstr2 <= kstr1の場合、(kstr1が発見されたとしても)走査は実行されない。 時間制限のある操作を行なうためにbt_scanは一度に高々blk_limitのブロックしかアクセスしないようにしているが、時間制限を気にしない場合ばbt_scanblk_limitに-1を渡せばよい。

削除、カウント、変更されるキーの数はrespktskey-countフィールドに返される。再開するキーはkstr1に返され(したがってその長さは256バイトである必要がある)、返される新しいキーの長さはrespktskey-countフィールドに入る。SUCCESSが返された場合のskey-lenはゼロである。skey-countは累積数なので、新しいbt_scanを開始するときは、呼出し元はそれをゼロに初期化する必要がある。

警告: bt_scanがSUCCESS以外の値を返した時は、次の呼出し用に文字列引数が正しく設定されるように、関数は文字列kstr1を変更する(返される値はkstr1の新しい長さである)。したがって kstr1は最大長の文字列でなければならない!


次: , 前: Cインタフェース, 上: Top

4 Schemeインタフェース

DBSCMは、Schemeの実装SCMに統合した、ディスクベースのソート済み連想配列パッケージ(WB)である。連想配列は、長さが256バイト未満の文字列であるキーと値で構成される連想配列はMUMPSスタイルデータベースの生成に使用でき、補助ファイルなしで標準的なレコード構造の実装に使用できる(example.scmの例参照)。

WBの(コンパイル済)実装を追加すると、およそ66kバイトがSCMのサイズに追加される。


次: , 前: Schemeインタフェース, 上: Schemeインタフェース

4.1 ステータスコード

— 機能: Scheme手続き err? x

エラーコードが有効であれば(-1...MAXERR)、xを返す。 さもなければ#fを返す。

— 機能: Scheme手続き success? x

not err?

— constant: success

実行に成功(0)。

エラーの場合は負の整数が使用され、以下のように重大度が増すにしたがって絶対値が増大する。

— constant: notpres

実行に成功、データが存在しない、変更がなかった

— constant: terminated

失敗、損傷がない、呼び出し元は操作を再試行できる

— constant: retryerr

失敗、損傷がない、呼び出し元は操作を再試行できる

— constant: argerr

失敗、損傷がない、呼び出しが間違っていた

— constant: noroom

失敗、損傷がない、ファイルに余地がない。

— constant: typerr

失敗、ファイルまたはオブジェクトの型が正しくない。

— constant: ioerr

入出力エラー、データベースが損傷された可能性がある。

— constant: strangerr

内部エラー、データベースが損傷された可能性がある。

— constant: unkerr

プレースホルダコード。

— constant: maxerr

すべてのエラーコードは0からmaxerrの間にある。


次: , 前: ステータスコード, 上: Schemeインタフェース

4.2 セグメント

make-segへの呼び出しで渡すセグメントのblock-sizeは、性能にとって重要なパラメータである。ブロックを横断するCPU時間とファイルシステムの待ち時間とのバランスを左右するからである。block-sizeは、ファイルシステムブロックサイズの整数倍でなければならない。

1990年代には、われわれの公称block-sizeは2.kiBであった。 これは現在では、おそらく4.kiB、8.kiB、16.kiBのいずれかにする必要がある。

— Scheme手続き: init-wb max-num-ents max-num-buks max-blk-size

WBシステムの初期化を実行する。Max-blk-sizeはディスクキャッシュバッファのサイズを決定する。max-num-entsは割り当てられるディスクキャッシュバッファの数である。(* max-num-ents Max-blk-size) はコンピュータのRAMサイズより小さくなければならない。すべてのmax-num-entsを(mallocで)割り当てることができなかった場合でも、WBは正しく実行できる。max-num-buksはディスクキャッシュ用のハッシュバケツ数である。ハッシュバケツ数はmax-num-entsとほぼ同一のサイズか、それよりも大きい必要がある。実際に割り当てられたバッファの数が返される。

init-wbの呼び出しを行わずにopen-segcreate-segが呼び出された場合は、ちょうどパラメータ75,150,2048を使用してinit-wbを呼び出した場合のようにWBが初期化される。

— Scheme手続き: final-wb

WBシステムが使用したメモリがすべて解放される。 すべてのセグメントがクローズされる。

— Scheme手続き: open-seg seg filename mode

Segは非負の数でなければならない。filename内のデータベースsegをオープンし、オープンに成功した場合はsegを、さもなければステータスコードを返す。mode引数に0を渡した場合、データベースsegは読み取り専用になる。mode引数に2を渡した場合、データベースは読み取り書き込み用になる。

— Scheme手続き: close-seg seg hammer

データベースセグメントsegとデータベースセグメントが入っているファイルを閉じる。hammerが#fでかつバッファの解放になんらかの問題があった場合、クローズは異常終了する。ステータスコードが返される。

— Scheme手続き: make-seg seg filename block-size

整数segには未使用のセグメントを指定しなければならない。 整数block-sizeにはB-ツリーブロックサイズを指定する。 block-sizeは、ファイルシステムブロックサイズの整数倍でなければならない。 公称値は4096である。

make-segは、名前がfilenameの新しい空のデータベースsegを作成する。ステータスコードが返される。新しいデータベースを使用するには、open-segを呼び出す。


次: , 前: セグメント, 上: Schemeインタフェース

4.3 連想配列

この関数グループでは、typは次のいずれかでなければならない。

ルートブロック(1)内のスペシャルエントリで指し示されるtyp#\Dを有するB-ツリー内のすべてのスペシャルエントリは、検査プログラムによるガーベージコレクションから保護される。#\Tは通常の(データ)配列に使用される。

— Scheme手続き: create-db seg typ name

ルートディレクトリで名前が入力されたB-ツリーを返す。

— Scheme手続き: open-db seg name

ルートディレクトリで名前が入力されたB-ツリーを返す。存在しない場合は#fが返される。


次: , 前: 連想配列, 上: Schemeインタフェース

4.4 低レベル操作

次の関数に渡す書き込み制御ビット引数(WCB)は、各種操作の後のファイル更新の遅延時間を制御する。このビットは以下のように定義される。

名称 意味


1 WCB-SAP PUT後のブロックの保存
2 WCB-SAR REMOVE後のブロックの保存
4 WCB-SAC キャッシュされたブロックに変更があった場合のブロックの強制保存
8 WCB-FAC キャッシュされたブロックの変更後に全バッファをフラッシュする(現在は実装されていない)。

— Scheme手続き: create-bt seg typ wcb

セグメントsegに型がtypの新しいルートブロックを作成し、そのルートブロックへのオープンしたbt-handleを返す。これは通常、システムがクラッシュした場合に検査プログラムで回収される一時b-ツリーの作成に使用される。

— Scheme手続き: open-bt seg blknum wcb

セグメント番号seg、ブロック番号blknumへのオープンしたbt-handleを返す。 ブロックが存在しないかルートブロックでない場合は、ステータスコードが返される。

— Scheme手続き: str2long string index

ブロック番号その他の整数量は、4バイトのポインタとしてデータベースに格納される。Str2longは、このindexから始まるstringの4バイトを符号なし整数に変換する。

— Scheme手続き: long2str! string index integer

integerindexから始まる4バイトのstringに格納する。


次: , 前: 低レベル操作, 上: Schemeインタフェース

4.5 レコード操作

— Scheme手続き: bt:get han key

hanはオープンしたbtへのハンドルである。keyは長さが255.B未満の文字列である。

bt:getは、オープンされたhanでbtにkeyで連結された値の文字列を返す。bt内にkeyへの連結が存在しない場合、bt:getは#fを返す。

— Scheme手続き: bt:next han key

hanはオープンしたbtへのハンドルである。keyは長さが255.B未満の文字列である。

bt:nextはbthan内の次のkeyを返す。次のキーが存在しない場合は#fを返す。

— Scheme手続き: bt:prev han key

hanはオープンしたbtへのハンドルである。keyは長さが255.B未満の文字列である。

bt:prevはbthan内の先行するkeyを返す。先行するキーが存在しない場合は#fを返す。

— Scheme手続き: bt:put! han key val

hanはオープンした書き変え可能なbtへのハンドルである。keyvalは、長さが255.B未満の文字列である。

bt:put!は、bthan内のkeyvalを連結する。ステータスコードが返される。

— Scheme手続き: bt:rem!han key

hanはオープンした書き変え可能なbtへのハンドルである。keyは長さが255.B未満の文字列である。

bt:rem!keyとそれに連結された値をbthanから削除する。

bt:getbt:put!が動作する値文字列は、長さが255.Bまでに限定される。 db:getdb:put!は64770.Bまでの長さの値文字列で動作する。

— Scheme手続き: db:get han key

hanはオープンしたbtへのハンドルである。keyは長さが255.B未満の文字列である。

db:getは、hanでオープンしたbtのkeyに連結された(長さが64770.Bまでの)値文字列を返す。 keyがbtに存在しない場合は#fを返す。

— Scheme手続き: db:put! han key val

hanはオープンした書き変え可能なbtへのハンドルである。keyは長さが255.B未満の文字列である。 valは長さが64770.B未満の文字列である。

db:put!は、bthankeyvalに連結する。ステータスコードが返される。


次: , 前: レコード操作, 上: Schemeインタフェース

4.6 排他制御

次の2つの呼び出しはプロセスのロックと同期に使用できる。

— Scheme手続き: bt:put han key val

keyが以前に空であった場合にだけ、bthankeyvalに連結する。 成功すれば#tを、失敗すれば#fを返す。

— Scheme手続き: bt:rem han key

keyが存在する場合にだけ、keyとそれに連結された値をbthanから削除する。成功の場合はkeyの値を、失敗の(キーが存在しない)場合は#fを返す。


次: , 前: 排他制御, 上: Schemeインタフェース

4.7 多重操作

— Scheme手続き: bt:rem* han key1 key2

key1を含むkey1からkey2を除くkey2までのkeyとそれに連結された値を、bthanから削除する。ステータスコードが返される。

— Scheme手続き: bt:scan han op key1 key2 func blklimit

手続きfuncを一定範囲のキー(と値)に適用して、連想配列のカウント、変更、削除のそれぞれを行う。 ステータスコード、処理されたレコードのカウント数、key1に対する新しい値のリストを返す。

opが-1の場合、指定したキーが削除される。opが0の場合、指定したキーがカウントされる。opが1の場合、範囲内のそれぞれのキーの値は、funcが返す文字列に変更される。

Funcはキーと値の2つの文字列引数を使用して呼び出される。opが1でfuncが#fを返した場合、変更は行われない。opが1でfuncが文字列を返した場合、キーに対応する値がその文字列で置き換えられる。その他の(count、delete)モードの場合、funcは#fか#tを返さなければならない。funcが#tを返す場合、連想配列がカウントされる(同時におそらく削除される)。

key1を含むkey1からkey2を除くkey2までのキーが走査される。blklimitが-1であれば、すべての範囲が走査される。さもなければblklimitで指定される(内部データベース構造の)ブロックだけが走査される。走査は返された情報を使用して再開できる。例えば次の式では"3"と"4"の間のキーの数が一度に1ブロックづつカウントされ、キー数とブロック数のリストが返される。

          (do ((res (bt:scan current-bt 0 "3" "4" (lambda (k v) #t) 1)
                    (bt:scan current-bt 0 (caddr res) "4" (lambda (k v) #t) 1))
               (blks 0 (+ 1 blks))
               (cnt 0 (+ cnt (cadr res))))
              ((not (= -1 (car res))) (list (+ cnt (cadr res)) (+ 1 blks))))
     

巨大な走査を行うときは、正のblklimitを指定するのが賢明である。走査の詳細についてはscan.scm参照。


前: 多重操作, 上: Schemeインタフェース

4.8 診断ルーチン

以下のルーチンが返す値は不定である。

— Scheme手続き: check-access

バッファとロックが一貫した状態にあることを検査し、WBルーチンが中断を受けていた場合はそれを修復する。

— Scheme手続き: clear-stats

収集した統計をすべて0にリセットする。

— Scheme手続き: stats

最後のclear-statsもしくはcstats以後の操作に関する統計の概要を印字する。

— Scheme手続き: cstats

最後のclear-statsもしくはcstats以後の操作に関する統計の概要を印字し、ついでclear-statsを呼び出す。

— Scheme手続き: show-buffers

すべてのディスクキャッシュバッファのステータステーブルを印字する。


次: , 前: Schemeインタフェース, 上: Top

5 リレーショナルデータベース


次: , 前: リレーショナルデータベース, 上: リレーショナルデータベース

5.1 wb-table

(require 'wb-table) wb-tableは、SCMからWBを使用する場合のために、SLIB base-table(see Base Table (SLIB))を直接的に埋め込んだものである。 長さが255文字未満の、テキストで表現したキーと値に対するscheme式に対応している。対応しているプリミティブ型は以下の通りである。

boolean #tもしくは#f
文字列(string) 0 - 255 byte string.
symbol 0 - 255バイトの文字列。
atom シンボルに対する伝統的な内部的別名(もしくは#f)。
整数(integer)
数(number)
序数(ordinal) 数(<256.B)の文字列表現。非負の整数は正しくソートされる。
式(expression) Schemeの式(表現は<256.Bでなければならない)。


前: wb-table, 上: リレーショナルデータベース

5.2 rwb-isam

(require 'rwb-isam) rwb-isamはWBとSCM上に構築された、キーとキー以外のフィールドに対して2進数形式を使用した高性能なベーステーブルの実装である。正しい数照合順序を使用し、IEEEの浮動小数点数と固定精度整数キーに対応している。

wb-tableで説明した型に加えて、rwb-isamは以下の型のキーと値に対応している。

r64 IEEE 64.bit数で表される実数。
r32 IEEE 32.bit数で表される実数。
s64 64.bit符号付き整数。
s32 32.bit符号付き整数。
s16 16.bit符号付き整数。
s8 8.bit符号付き整数。
u64 64.bitの非負の整数。
u32 32.bitの非負の整数。
u16 16.bitの非負の整数。
u8 8.bitの非負の整数。

キー以外のフィールドについては複素数に対応している。

c64 2つのIEEE 64.bit数で表される複素数。
c32 2つのIEEE 32.bit数で表される複素数。


前: リレーショナルデータベース, 上: Top

手続きとマクロインデックス

WBのすべての手続きとマクロのアルファベット順リスト。

変数インデックス

WBのすべての大域変数のアルファベット順リスト。

型インデックス

WBのデータ型と機能名のアルファベット順リスト。

このマニュアルで紹介したコンセプトのアルファベット順リスト。

コンセプトインデックス

目次


脚注

[1] このオプションは、通常20バイトのヘッダと2バイトの長さフィールドを持つWBブロックの新規の型を必要とする。それぞれのブロックにはbsiz-20バイトまでのデータが保持される。