[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では前置キーと後置キーの圧縮が使用される。
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.
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:
(非公式な翻訳) 前記の著作権情報がすべての複製に表示され、著作権情報と本許諾情報の両方が解説文書に表示される限りにおいて、いかなる目的についても本ソフトウェアとマニュアルの使用料を支払わない使用、複製、変更、頒布、販売の許諾をここに認可する。
プログラムが無償でライセンス供与される以上、準拠法が許可する範囲においてプログラムの保証は全く存在しない。文書による別段の指定がない限り、著作権保有者とその他の当事者のいずれかもしくは両方は「現状のままで」本「プログラム」を提供するものであり、明示的と暗黙とにかかわらずいかなる種類の保証も行わない。保証には市場性や適合性に関するあるゆる目的の暗黙の保証が含まれるが、暗黙の保証に限定されるものではない。プログラムの品質と性能に関する全てのリスクはユーザに帰するものである。万一プログラムに欠陥があると判明した場合にも、修復や訂正のすべての必要な修理コストはユーザの負担とする。
準拠法によって要求されるか、もしくは文書による同意がない限り、著作権保有者も、上記に許可されてプログラムの修正と再配付のいずれかもしくは両方を行うその他のいかなる当事者も、ユーザに対して損害の責任を負わないものとする。これにはプログラムの使用もしくは適用不能によって発生するあらゆる一般的な、特別な、付帯的な、結果的な損害賠償責任が含まれる(これにはデータの喪失、不正確なデータの生成、ユーザもしくは第三者が被る損害、その他あらゆるプログラムと当該プログラムとの協調動作の不能が含まれるがそれに限定されるわけではない)。前述の著作権保有者もしくはその他の当事者が前述の損害の可能性に関して通知を受けていた場合も例外ではない。
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にて頻繁に使用された。
WBレイヤを使用するにあたっての最初のCインクルードファイルはwbsys.hである。このファイルにより、同じディレクトリのその他の複数のファイルが取り込まれる。wbsys.hではWBの内部データ型も定義されている。 WBには、ディスク上に保存されたデータベースファイルについてのユーティリティプログラムが含まれる。
WBソースは、schlep.scmによってSCMから(K&R)CとTeXinfoに変換される。make.scmは変換を統合するプログラムである。ソースはCに変換された後でプラットフォームのネイティブコンパイラでコンパイルされる。
WBは名前がwbのディレクトリに展開される。WBをSCMで使用したい場合は、ディレクトリscmとwbを同じディレクトリ配下に置く必要がある。
VMSシステムでは、wbcheckとdb(SCM)はVMSBUILD.COMスクリプトで作成される。
unixの場合:
make allmake install$(prefix)ツリーにlibwb、wbscm.so、wbcheckがインストールされる。
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
wbディレクトリからscm allを実行する。これにより、テストコードを含むWB-ツリーのSchemeバージョンがロードされる。(main)を入力すると、テストデータベースzがこのディレクトリに作成される。これを実行してエラーが発生しなければ、Cコードの作成が可能である。(quit)でscmを終了する。
CコンパイラがANSI関数プロトタイプを受け付けない場合は、make.scmの行(set! __STDC__ #t)をコメントアウトする。 コマンド行scm-lmake.scmを入力すれば、SCMの適切なファイルがすべて変換される。
makeか@VMSBUILDを実行すれば、wbと補助プログラムwbcheckがコンパイルされる。
scm-rwb-ltest-e"(main)"を実行する。テストデータベースzの作成が前回よりはるかに高速に行われるはずである。
(quit)を入力してDBSCMを終了する。次に./wbcheck zを実行する。 これはデータベースの構造を検査して、一時ファイルを回収するプログラムである。これにより52ブロックが再利用され、no errorsが報告されるはずである。再度実行しても、今度は回集されるブロックは存在しない。
コンカレントb-ツリーアルゴリズムの出発点として、[SAGIV]を使用した。 ただしかなりの変更と改善を行った(と思う)。実装作業、とりわけデバッギングの苦労を減らすために、特にアルゴリズムの単純化を試みた。完全な実装を作成するには多くの複雑な詳細も必要だった。本書の目的は、設計上の主な決断とそれから生まれたこまごましたものを書き留めて、説明することである。
それぞれのキーテキストの全文を保存するのではなく、前のキーに一致するこのブロックの部分の長さと、一致しないキーテキストを保存する。
リーフ以外のブロックでは、下位レベルの連続する2つのブロックを識別できる分割キーだけを保存する。
ブロックヘッダ形式の最初の20バイトは、すべての型のブロックについて同一である。
B-リンクツリー形式が採用された([SAGIV]参照)。リーフブロックの1つ1つには一定の数の(キーと値)のペアが入る。リーフ以外のブロック(インデックス)には、(キーとダウンポインタ)のペアが入る。 それぞれのブロックには1個の追加のキーの値、分割キーが入っている。分割キーはブロック内のその他あらゆるキーよりも厳密な意味で大きい。ツリーは、ツリーの各レベルのノードを分割キーの順序(NEXTポインタ)で連結することによって成長する。
一定のキー順序不変式が保持される限り、インデックスの挿入もしくはブロックの削除によるツリーの更新をいっさい行わないことを、われわれは選択した。
インデックス内のキーは、キーが存在するブロックの分割キーに正確に一致しなければならない点に注意が必要である。キーKがそれが指し示すブロックBの分割キーSより小さい場合、中間キーの検索は次のブロックへ向かう方向を誤ってしまう。KがSより大きい場合は、論理的にはK'はKの後ろに来るはずであるが実際にはK'<Kなので、S<K'<Kとなるようなキーの値K'で、B以降のブロックの分割が誤ってBの親に挿入される。
インデックスエントリの空間の概念は利用価値が高い。ブロック1つ1つの分割は次のより高いレベルにおける何らかの空間の「拡張」と考えることができるのに対して、「親への挿入更新」1つ1つは対応する空間の縮退と考えることができる点にわれわれは注目した。内部に1つのブロックだけを有する空間は「完全に縮退した」と呼ばれる。すべての空間が完全に縮退したとき、すなわちすべての保留中もしくは延期された挿入更新が実行されたときは、b-ツリーは完全に縮退する。最後に空間に関して、規則C1は次のようにより簡潔に表現できる:
挿入が単純になることから元々はインデックスノードを(値、キー)の順序にしていたのだが、それはあきらめた。この方法では挿入/削除を伝播するコードをすべて、特殊ケースとして扱わなければならなかったからである。実際「挿入」と「削除」が非対称であるために、いずれか一方の一回の操作で、2つのブロックの変更(see 挿入メソッド)が必要となる場合が生ずる。 ただしツリーのすべてのレベルで(キー、値)の順序づけを使用したことにより、コードはかなり単純化された。
B-ツリーを編成するにあたって、分割キーは確立されたメソッドであると思われる。目的キーを探索するために潜在的に順方向に連鎖を作成しなければならない場合があるBリンクツリーにおいては、探索をいつ停止できるかを分割キーによって決定できる。 ブロックの終端に分割キーがあれば、1探索あたり1回のブロックアクセスが節約される。(分割キーがブロックの先頭にあるとすれば、探索を停止できるかどうかを判断するためにはチェーンの次のブロックを調査する必要があるだろう)。
すべてのレベルにおいて、最大キーを終端の分割キーとして定義することは有効である。最後のキーが辞書式順序にしたがわない何らかの特殊な値(例えばヌル文字列)であるとすれば、空(最後)のブロックへの挿入で発生する問題をあげるまでもなく、コードはより複雑になる。0xffで始まる文字列の集合が分割キー専用に予約された。これを実際のキーの値として使用することはできない。終端キーの値の形式は、xFF(<レベル>)である。これによりレベルN+1の最後のキーはレベルNのいかなるキーよりも厳密に大きくなり、したがってレベルNのチェーン終端のキーをレベルN+1でキーとして挿入するときに特別扱いする必要がない。
インデックスレベルの分割キーは、リーフレベルの分割キーと同じように動作するものとした。すなわち、1つのブロック内の分割キーは決して変化しない。この利点は、挿入と削除によって分割キーが変化することはありえず、変化を伝播させるコードが不要になることである。変化を伝播させるコードのテストは厄介なものである。これによってすべてのレベルが真に独立したものともなり、概念上有効な簡素化が行われる。
難点は、これによってインデックスブロックの最後のキーと値のペアとそのブロックの分割キー間に、デッドスペースが導入されることである。このためコードはわずかに複雑になり、平均探索パスもlog(N)よりわずかに(BFをツリーの分岐率として定数係数1+(1/BF)だけ)長くなる。より厄介なことには、挿入を行うとブロックの分割が発生する(「挿入」参照)。
インデックスへの挿入は、キー順序不変式が保持されるようにアトミック(分割不可)に見える必要がある。キー/値で順序づけられたインデックスブロックを使用している以上、親の更新挿入には次のように特殊な追加のステップが存在する。インデックスブロックBに新規のキーとポインタが挿入されると、値フィールドが連続する次のエントリとスワップされる。挿入がブロックの終端で行われるときは、残念ながら次のエントリは次のブロックB'にあるので、2つのブロックを変更しなければならない。(値/キーによる順序づけの利点は、挿入によって変更されるブロックが1つだけということである。ただしその代わりに、削除コードを同じように考えたら失敗する)。 コードはこのような場合を検査しており、先へ進む前に両方のブロックをロックする。(検討したもう1つの解は新規のキーがB'の先頭に来るようにBの分割キーをバックアップすることであるが、そうすると別の問題が導入される)。
上記のメソッドは(同時実行時にも)正しさを保存するが、次のようにさらに実装する必要がある2次的な欠陥が残念ながら存在する。ディスククラッシュの場合に正しさを保存する順序で2つのブロックに書込みを行う方法。Bだけが書込まれた場合、データベースには分割によって挿入を発生させたブロックへの2つのポインタが含まれることになる。B'だけが書込まれたとすると、ポインタの正しさが破壊される。(この種の問題は、複数ブロックにわたる一貫した変更を保持する必要があるあらゆる操作に内在すると思われる)。解決策はこの特殊ケースが実行中であることを知らせるルートへの注釈で書込みを取り囲み、変更中のブロック(B、B')とあるべきポインタを次のように示すことであると思われる。
ブロック分割によって作成された新規のブロックがB'である場合との一貫性を保つために、最初にブロックB'を書き出すことが選択された。極端な場合には壊れたDBが作成されるが、重複して指定されたブロックを削除する危険は回避される。これは直接的に回復を行う場合の適切な情報である。 (JONATHAN?)
(これ以外の代替手段も検討した。次のレベルで分割キーをバックアップすれば後続する挿入をアトミックにできるが、バックアップ操作には親のインデックスの一貫性を保持する場合の2つのブロックの一貫性という同じ問題がつきまとう。親のキーがバックアップされていなければ、後続するブロックの後続する分割によって、次のレベルでの更新は不正確なものとなる)。
削除は次のように2つの部分に分割することができる。削除するブロックは、親ブロックとと先行ブロックの両方から切り離さなければならない。切り離したブロックはその後で回収できる。
現在われわれは、親ブロックと先行ブロックの両方が変更可能な場合に削除が実行され、それ以外の場合には削除が失敗する(すなわち延期される)ように削除操作を単純化することを選択している。これによってブロックの削除はアトミックな変更となり、部分的削除を許可することによって導入される複数の問題が回避される(「同時実行性」参照)。
代替案: [WANG]は、ブロックをスワップすることによってPREVを使用せずにブロックを削除する賢明な方法を紹介している。これを同時実行性に対して堅牢に仕上げることは極めて困難と思われたので、われわれはPREVメソッドにこだわった。PREVメソッドでは結局、1/BF時間のブロックアクセスが増えるだけである。
1回の削除における親ブロックと先行ブロックの書き出し順序については万一システムがクラッシュした場合にもチェーンが手つかずで残るように、まず親ブロックを書き出すことを選択した。削除しようとしていたブロックはチェーン内に留まるけれどもこれは「デッドブロック」であり、使用することはできない 「デッド」ブロックを取り扱う方法はインデックスの遅延更新と同時実行性で検討する。
[SAGIV]からの大きな変更は、SAGIVではブロックの複数のコピーが存在できると想定していた点である。この想定では削除したブロックの回収が複雑になる(SAGIVはタイムアウトベースのプロトコルを示唆している)。 われわれの方法ではブロックの複数のコピーは想定せずにロック、すなわち「名前」ロック(本質的には「削除」ロック)を追加することによって、各ブロックへのポインタがいくつ存在するかを追跡することを選択した。 ルーチンはポインタを取得するブロックに関する読み取り/書き込みをの実行を開始する以前に、ポインタに関する名前ロックを獲得しなければならない。 (書き込み期間中の読み取り要求という問題が発生しやすい場合のみを処理するSAGIVの方法とは対照的に、われわれの方法ではすべての操作にオーバーヘッドが導入されるという意味で、SAGIVの方法の方がほぼ確実に効率的である。このようなトレードオフに関する複数の実証的研究がこの結論を支持している)。一方名前ロックは、親ブロックや先行ブロック...を探索している間は前データの探索を開始するブロックを削除できないことを保障するなどの、その他の場合に有効である。
遅延された挿入は(キー、ポインタ)ペアの削除と等価ではないという意味で、「挿入」と「削除」が対称的でないことは覚えておくに値する。(キー、ポインタ)ペアの削除ではポインタが欠落したブロックがインデックス経由でアクセスできないまま残されるのに対して、遅延された挿入では依然としてNEXTポインタチェーン経由でブロックにアクセスできる。
この非対称性により、同時実行性に関する各種の問題を解決する試みはわたしが思い出せる限り終息した!
例:
したがって、続く削除は挿入を「取り消す」ことができない。削除は関連する挿入の完了を待機するか、正しさを保持するための特殊な作業を行うかのいずれかを行わなければならない。
われわれは現在、あらゆるレベルの最後のブロック、すなわちブロックの終端キーが存在するブロックの削除を許可していない。この削除はブロックの終端キーを確保しておくための特別な対応を必要とするからである。これを実現する方法の1つはnext-to-lastブロックの内容を前方コピーして、最後のブロックを削除する代わりにnext-to-lastブロックを削除することである。[例えばこの操作期間中に正しさを保存するなどの具体化しなければならない詳細が存在する]。
[どう動作しているかの説明]
「分かってはいるけれどもまだ実装されていない難しいケースの解決策」: あるレベルの最初のブロック直後のブロックに下向きポインタが欠落している場合、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に遭遇したかを確認するかのいずれかを行う必要がある。
われわれはルートのブロック番号が決して変化しないことを保証しており、したがってWB-ツリーが与えられた場合にはルートのブロック番号を一意の識別子として使用できることを保証する。その他のシステムではルートの参照に間接指定のレベルを導入することによって、一意のツリーIDを用意している。ルートの参照は頻繁に行われるのでこれは非効率的である。ルートが分割されるときはルートブロックに残っていたデータを保持するために新規のブロックが割り当てられ、その後以前のルートブロックが新規のルートとして使用される。これはブロックが分割された場合にもブロックIDが変化しないので、ブロックIDが信頼できないことを意味する。
実装されていない。
ツリーレイアウトについては別の可能性が複数存在する。その中には、挿入の難しいケースなどの現在のレイアウトでは複雑な操作を単純化できるものもある。その他の可能な選択には以下が含まれる。
わたし(RJZ)が好むもう1つの仮定は、[SAGIV]のように複数バージョンのブロックの存在を許可することである。これは次を意味する。
恐らくいつか時期が来れば、以上の相互関係を方法論的に探求できるであろう...。
ブロックを安全に削除できる時期を明示的に知ることができるためには、ポインタを取得したブロックに関する「読み取り/書き込み」の実行に移る以前に、ポインタに関する名前ロックをユーザがぜひとも取得しなければならない。名前ロックは次のようにその他の場合にも有効である
ブロックされた操作は現在RETRYERRのエラーコードを返して単に失敗しようとする。後で安全に再試行できるようにするためである。 現在の発想は「読み取り書き込み」の競合が発生したときは、常にこれを利用することである。 (SAGIVの方法を使用する場合はこれは不要である) 。ただしブロック読み取りの待機、名前ロックに関する待機、インターロック操作に関する待機などのその他各種のロックアウト条件と待機条件が発生する可能性がある以上、そのような機能は必ず必要になるのであり、したがって「読み取り書き込み」のブロッキングの処理にそれを使用しようとすることもまた合理的であろう。
すべての場合に適切な情報を上位に渡すコードを再編成する複雑さのために、これは「本当にはまだ実装されていない」。 (Topレベルルーチンはこのようなコードを返すが内部ルーチンは実際にはまだこれを使用しておらず、したがって再試行機能は現実には存在していない。)
基本戦略はブロックが分割され、空になって完了するキーの挿入/削除ができることであるが、このときキーはバックグラウンドで成功するまで遅延更新を再試行する何らかのプロセスで親の更新/ブロックの削除の待ち行列に入る。
問題は親の更新と先行ブロックの更新という、待機可能な2つの独立した操作が削除に含まれることである 。この2つの更新は、挿入が発生できないようにブロックがまず「デッド」とマークされていれば、独立して行うことができる。残念ながら、同じキーにたまたま関係する削除と挿入の正しい順序づけを巻き込む、ごくまれで複雑な難しい事例の類がある。例えばブロックは、キーを削除して削除することも可能であり、その後、後続する分割でそのブロックを再導入して、削除をやり直すことができる。インデックスレベルの操作が遅延された場合、遅延された操作の順序づけによって、結果のツリーが正しいかどうかが定まる。
ブロック削除を(上で定義するように)アトミックにすれば、このプロセスは大きく単純化される。このとき挿入中もしくは削除中のブロックは、ブロックそれ自体のセマフォとして使用できる。
われわれは、遅延更新戦略を採用することを選択した。すなわち、更新を直ちに実行できない場合は保留中の親の更新キューを保持するのではなく、更新は放棄することとした。これは、レベルN+1の更新はレベルNのチェーンから再構築できるために、可能になることである。
これで、更新するパスに実際に遭遇した次のような場合には、遅延更新は性能のみに影響することになる: 2つのブロックにわたってチェーンを作成しなければならない事が判明した場合、すなわち親の更新がまだ発生していない場合。空ブロックに遭遇した場合、すなわち削除更新が発生していない場合。考え方は、このような「非効率性」の解決は要求があり次第、すなわち非効率的な例に遭遇した場合にだけ、それを解決する労を取るということである。さしあたっては、すべてのブロック削除とすべての挿入更新が遅延されると想定する。
この基本アルゴリズムは以下の通りである。
ブロックの削除中に入出力障害が発生した場合に「デッド」ブロック、すなわち親のレベルから到達できないブロックが残る可能性が大きな懸念であった。このブロックはまだチェーン内にあるにもかかわらずブロックへの下向きポインタが存在せず、探索がそのノードで停止できない状態が発生する。ブロックがデッド状態になった場合はブロック内部への挿入やブロックの復元を防止する必要があるということが問題なのである。それを行うとエントリの一貫性が損われる場合があるからである(ブロックがデッドである間に分割キーよりも小さいキーの何らかの挿入がが発生したと仮定する。挿入はインデックスによって次のブロックへ仕向けられ、そこに配置される。このときにブロックを復元すると、キーの順序づけは正しくないものになる)。ただし次のようにB-ツリー操作が遭遇する可能性がある遅延更新状況の種類を観察すれば、これを防止できることがわかる。
ツリーを、インデックスエントリがまたがるブロックのエントリの集合が形成するインデックスエントリ空間1つ1つからなる入れ子になった空間ととらえるならば、GET、PUT、REMなどの探索のみを使用する操作中は、探索の場所はルート内の何らかのエントリ空間の範囲内に厳密にとどまることがわかる。ブロックは親のポインタが完全に更新されるまで、すなわち親のポインタ空間が正確に1つのブロックになるまでは削除されないようにしている。今度は親のポインタを持たない空のブロックを残して、ブロック削除が途中で失敗した場合を考えてみる。このブロックはFIND-NODEによっては、したがってINSERTによっては到達できない!これは、INSERTが空のブロックに遭遇した場合は、そのブロックへの挿入が有効でなければならないことを意味する。
この帰結は、次のように興味深いものである。
[これに気がつけば、ブロック削除は実際には(またまた)2つの操作に分けることができる。追加される複雑さはこのとき、デッドブロックを検出する方法を実装する必要があるということだけになる。すなわち、削除を試みてはならないデッドブロックと空のブロックを大きな空間の中央で識別する必要がある。当該ブロックが何らかの空間に連続するかどうかだけを検査すればよい。これを効率的に行う方法はまた別の話である。]
具体的には、遅延操作を検出する方法は次のように行われる。
ブロックBのNEXTポインタを(FIND-NODEで)追跡しなければならないときはいつも、(キー、値)ペア(split(B)、next(B))を使用してPARENT-INSERT-UPDATEを試みる必要がある。「デッドスペース」に遭遇したときは、FIND-NODEは下向きではなく右向きに連鎖を作成するように定める必要がある。かつ、この場合はPARENT-INSERT-UPDATEを試みてはならない。
PARENT-INSERT-UPDATEは、次の場合に失敗することがある。
FIND-NODEもしくはNEXT/PREV操作で空のブロックに到達したときは、PARENT-DELETE-UPDATEを必ず試みる。
PARENT-DELETE-UPDATEは次のときに失敗する必要がある。
実際には、平常時にも更新ルーチンを起動したくなる。すなわちブロック分割後には挿入更新を、ブロックが空になった後には削除更新を試みたくなる。
銘記しておかねばならない新規の統計が若干存在する。これには以下が含まれる。
(前方連鎖の数もオーバヘッドの測定である。)
[注:このメカニズムは、待ち行列を作成する次のような単純な方法にも対応している。更新が延期されたブロック番号のリストを保持しておいて、利用率が低いときにそのブロックに対してFINDを実行すれば、その副作用としてブロックが更新される...。]
—————–
[その他の戦略も検討したが、次のようにかなり複雑になるか、オーバヘッドが大きくなるか、もしくは不要な遅延が導入されるものであった。
インデックスの遅延挿入操作と遅延削除操作の待ち行列を力づくでシリアル化する切り口が、1つ考えられる: 操作を正確に到着した順序で行うのである。次の別法の方がおそらくより簡単であろう: キーでソートしてタイムスタンプを打てばいい!
待ち行列が増えすぎた場合には遅延操作の実行に資源を振り向けたいので、インタープリタはプロセスを単純に1つ1つの遅延操作に専念させるべきであるとも思われた。
[WANG]は削除された操作の待ち行列をあて先ブロック上に保持する。 この難点は、ブロックが分割もしくはマージされるされるときは、遅延操作待ち行列も必ず分割もしくはマージする必要があるということである。うーみゅ!]
これは昔からある厄介な問題である – 実際には評価されていないか調節されていない複雑なシステムが配置されており、Jonathanは単純に最初に発見した自由なバッファ(もしくは解放可能なバッファ)を使用することを提案した。
単に#fを発行してそれから更新を行うだけでは充分ではない場合がなにがしか存在するとわたしには思われたが、今即座には思いつくことができない...。
注: これは、前述の「遅延インデックス更新」からの異なる種類の照会である。前述の遅延操作では正しさが保存されていたが; 今回はそうではない。考え方としては、安全に失ってもよい更新の数が「わずか」であれば、入出力トラフィックを軽減できるということである。
この趣旨は、データベースの構造に障害が起きなければ更新が失われてもよいという意味で、リーフブロックの書き込みを延期することによって入出力トラフィックを軽減できるということである。これは、問題のデータ更新がデータベースやアプリケーションに危険でない場合にのみ機能する。 現在のところ、ツリーの種類が「ディレクトリ」以外であれば、データツリーに対するリーフの更新は、PUTとREMの両方とも必ず遅延される。(「ディレクトリ」リーフブロックは更新のたびにディスクに書込まれる)。データブロックが書込まれる頻度はユーザアプリケーションが制御すべきであるというのが基本の考え方である。
さらに、PUTとDELETEの照会は個別に制御できなければならない。 この機能は例えば次のように、フリーリストを保守する場合にデータベース自体が必要とするものである。削除済みブロックの「挿入」は遅延して差し支えない。起こり得る最悪の事態はフリーブロックの消失だからである。ただしフリーリストからの「削除」は直ちに更新しなければならない。さもないとブロックが二重に割り当てられる場合があるからである。
ハンドルは以下の論理値が含まれるように拡張されている。
これらのビットは例えば次のように使用される。
これらのビットの状態は、(HAN-SET-WCB han new-bits)を使用していつでも変更できる。WRITE-CACHE-BLKを呼び出せば現在のブロックが書き出されたことが、WRITE-MODIFIED-BLKSを呼び出せばすべての変更済みブロックが書き出されたことがユーザに保証される。 ディレクトリツリーがオープンもしくは作成されたときは、現在は安全のためにHAN-SAPとHAN-SARが強制的に実行される。さらにフリーリスト書き込み制御ビットは、フリーリストのブロックの種類にかかわらずOPEN-SEGによって上記の通りになるように強制される。
非常に良好に動作している。
以下はまだ実装されていない: 同じTRY-GET-ENTプロトコルを使用すれば、実際にはより賢くすべてのノードの親、さらにはPREVすらキャッシュできるであろう!
複数の読み取りアクセスにはまだ対応していない。「読み取り」と「読み取り」の競合が発生する可能性がある。 この制限があるために、現在は同定できなくなっているある種の別の問題に遭遇せずにすんでいることを注意しておく必要があると思われる。
概要:
現在の問題:
これまでのすべての努力にもかかわらず最後の週に(1/8)われわれは、以下のような問題のために、並行操作でのフリーブロック管理には障害が発生する場合がまだ存在すると結論した。
肯定的な側面としては、フリーリストの挿入によってツリー全体が分割されるために、充分なフリーブロックを割り当てる必要はないことがわかった - リーフの分割以外のあらゆる分割は、そのとき利用できるフリーブロックが存在しなければ単に遅延することができるからである!(しかも、フリーリストの操作によって引き起こされるあらゆる挿入更新も同様である)
考えてみれば、フリーリストの挿入期間中にブロックが不足した場合は挿入を失敗させてもよい。単にディスクブロック1つを失うだけだからである おそらくこれが答えとなるだろう。
バッファをパージする次の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) バッファが書き出されてロック解除されたことを確認し、そうなっていないバッファを修復する。
問題: 呼び出しは以下を識別する適切な情報を返す必要がある。
解: 「成功」コードとして利用できる非負の戻り値を残し、境界が定められた範囲の負の数を「障害」コードとして使用する。正準化(キャノニカル)成功コードは0であるが、値(文字列長さ、ENTポインタ)を返す必要があるルーチンは0を返すことができるので、値0を「成功」コードとして解釈することができる。
障害には「程度」があり、負のコードは増大する重大度に応じて、以下のように分割される。
最初のクラスはエラーなしで完了した操作を示す。二番目のクラスは完了できなかった操作を示すが、データベースは正しい状態のままであることが保証されており、再試行が可能(もしくは簡単に修正可能)である。3番目のクラスは完了できなかった操作を示し、データベースも損傷していないが、修復や再起動が簡単にはできない。最後のクラスはエラー条件によってデータベースが壊れたか、もしくはエラー期間中に壊れたデータベースが検出されたことを示す。
戻りコードが範囲NOTPRES-MAXERR内部にあれば、述語手続き(ERR?code)は#tを返す。述語手続き(REALERR?code)は"not there"もしくは"stop processing"メッセージとは対照的に、CODEが現実のエラーの場合に#tを返す。
値文字列用の256.Bの長さの制限は、WBに可能な多くのアプリケーションに対する障壁であった。db.cのdb:getとdb:put!手続きは、64770.Bまでの長さの値文字列で機能する(see レコード操作)。
長さLの値文字列は次のように処理される。
bt:scanの使用法は、長い値文字列のために複雑になっている点に注意が必要である。
以下は長さに制限がない値文字列への拡張の提案である。
make_seg()のbsiz引数もしくはmake-segのblock-size引数は、そのセグメントにおけるすべてのWBブロック(ページ)のサイズである。
興味深い変種は、datalong用に1つとその他すべて用に1つの、2本のツリーを用意するものである。2本のツリーを(独立したファイルに格納された)独立したセグメントに置けば、非datalong操作の速度に影響を与えずにdatalongのセグメントブロックサイズを最適化することができる。
文責Jonathan Finger
以後mainとslaveとして参照する2つのbツリーを使用する。 記法D[123,4567]は、文字列D\3 1 2 3 \4 4 5 6 7に変換される。ただし\3はアスキー文字の3など(続く数字文字列の長さ)である。これによりキーは数値順にソーティングされる。
データの最初のバイトはフラグである。
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ツリーに値を格納する。
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のコードはすこし繁雑になる。
この方式であれば、キーとデータの長さを無制限にできるとわたしは信じている。 性能はすばらしいとはいえないかもしれないが、許容範囲内であろう。 これにより良好なキー圧縮が得られるはずである。
RJZリスト項目の大部分は完了したと思われる。
RJZ修正1993年4月8日
B-ツリーに関する包括的な参考文献は以下で検索できる。 http://www.informatik.uni-trier.de/~ley/db/access/btree.html
segmentは自己完結的なBツリーの集合で、一つ一つのツリーは通常固有の(ディスク)ファイルに連結される。WB関数は0からnum_segs - 1までの整数でセグメントを参照する。
ファイルベースであるか否かに関わらず、セグメント一つ一つにはディスクブロックのfreelistが保持されている。 新しく作成されたセグメントでは、ほぼすべてのブロック番号がフリーリストに入っている。
機械変換されたソースでは、プラットフォームから独立した診断、警告、エラーメッセージの記録方法としてdprintfを使用する。
tdprintf
dprintfへの単一の引数は小括弧に入れた引数のリスト(例えば二重括弧)でなければならない。このリスト内部の最初の引数は文字通りdiagoutとする必要がある。 templateはprintfスタイルの書式文字列で、printfのように後ろに書式用の引数が続く。
make_segの呼出しで渡すセグメントのbsizは、性能にとって重要なパラメータである。ブロックを横断するCPU時間とファイルシステムの待ち時間とのバランスを左右するからである。bsizは、ファイルシステムブロックサイズの整数倍でなければならない。
1990年代には、われわれの公称 bsizは2.kiBであった。 これは現在では、おそらく4.kiB、8.kiB、16.kiBのいずれかにする必要がある
segは非負の数でなければならない。。filename内のデータベースsegをオープンし、オープンに成功した場合はsegを、さもなければステータスコードを返す。mode引数に0を渡した場合、データベースsegは読み取り専用になる。mode引数に2を渡した場合、データベースは読み取り書き込み用になる。
データベースセグメントsegとデータベースセグメントが入っているファイルを閉じる。hammerがNULLでかつバッファの解放になんらかの問題があった場合、クローズは異常終了する。ステータスコードが返される
整数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 | キャッシュされたブロックの変更後に全バッファをフラッシュする(現在は実装されていない)。
|
セグメント番号seg、ブロック番号blknumへのbt-handleをオープンし、ブロックの型を返す。 ブロックが存在しないかルートブロックでない場合は、(負の)ステータスコードが返される
型がtypのセグメントsegに新しいルートブロックを作成し、そのルートブロックへのbt-handle hanをオープンしてステータスコードを返す。segに充分な容量がない場合は新しいツリーを作成してステータスコードnoroomを返す。
bt_createは一時b-ツリーの作成に使用できる。一時ツリーは、システムがクラッシュした後に検査プログラムで回収される。ツリーを永続的なものにする場合は、ツリーをディレクトリ(ツリー)に追加する。
bt-handle han を閉じて SUCCESSを返す。
現在のところ、
bt_closeには hanをクリアする以外の効果はない。
注: この項のデータ操作コマンドは、以下の意味を持つnotpresを返すことができる。
bt-get
| そのようなキーは存在しない。
|
bt-next
| NEXTキーが存在しない(つまり与えられたキーはLASTキーだった)。
|
bt-prev
| PREVキーが存在しない(つまり与えられたキーはFIRSTキーだった)。
|
bt-rem
| キーを発見できなかった。
|
bt-put
| 未使用(WRITEに対称的でも良い).
|
bt-write
| キーが発見されなかった。したがって書込みが行なわれなかった。
|
key_strは長さk_lenの文字列。
bt_getはツリーhan内のkey_strに連結された値を文字列ans_strに格納する。bt_getはans_strに格納された値を返す。さもなければエラーコードを返す。
key_strは長さk_lenの文字列。
bt_nextは、ツリーhan内のkey_strの後の次のキーを文字列ans_strに格納する。bt_nextはans_strに格納された値を返す。さもなければエラーコードを返す。
key_strは長さk_lenの文字列。
bt_prevは、ツリーhan内のkey_strの前の最後のキーを文字列ans_strに格納する。bt_prevはans_strに格納された値を返す。さもなければエラーコードを返す。
key_strは長さk_lenの文字列。
bt_remはツリーhan内のkey_strに連結された値を文字列ans_strに格納した上で、その連結をツリーhanから削除する。bt_remはans_strに格納された値を返す。さもなければエラーコードを返す。ans_strが0の場合、
bt_remはツリーhanから連結 key_strを削除し、成功すればSUCCESSを、失敗すればエラーコードを返す。
key_strは長さがk_lenバイトのキーが入る最大長(256バイト)の文字列でなければならない。
bt_rem_rangeは[key_str ... key2_str)と関連する値を削除する。key2_str <= key_strの場合は、key_strが発見された場合でも削除は行なわれない。bt_rem_rangeは操作が完了した場合にSUCCESSを返し、完了しなかった場合はエラーステータスを返す。
key_strは長さk_lenの文字列、val_strは長さがv_lenの文字列である。
bt_putはkey_strに連結された値をツリー han内のval_strとする。bt_putは操作のステータスコードを返す。
key_strは長さk_lenの文字列、val_strは長さがv_lenの文字列、val_strは長さがv_lenの文字列である。現在hanにkey_strとの連結が入っている場合、
bt_writeはツリーを変更せずにnotpresステータスコードを返す。それ以外の場合、
bt_writeはkey_strに連結された値をツリーtree han内のval_strとする。bt_writeは操作のステータスコードを返す。
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_scanのblk_limitに-1を渡せばよい。削除、カウント、変更されるキーの数はrespktの
skey-countフィールドに返される。再開するキーはkstr1に返され(したがってその長さは256バイトである必要がある)、返される新しいキーの長さはrespktのskey-countフィールドに入る。SUCCESSが返された場合のskey-lenはゼロである。skey-countは累積数なので、新しいbt_scanを開始するときは、呼出し元はそれをゼロに初期化する必要がある。警告:
bt_scanがSUCCESS以外の値を返した時は、次の呼出し用に文字列引数が正しく設定されるように、関数は文字列kstr1を変更する(返される値はkstr1の新しい長さである)。したがって kstr1は最大長の文字列でなければならない!
DBSCMは、Schemeの実装SCMに統合した、ディスクベースのソート済み連想配列パッケージ(WB)である。連想配列は、長さが256バイト未満の文字列であるキーと値で構成される連想配列はMUMPSスタイルデータベースの生成に使用でき、補助ファイルなしで標準的なレコード構造の実装に使用できる(example.scmの例参照)。
WBの(コンパイル済)実装を追加すると、およそ66kバイトがSCMのサイズに追加される。
エラーの場合は負の整数が使用され、以下のように重大度が増すにしたがって絶対値が増大する。
make-segへの呼び出しで渡すセグメントのblock-sizeは、性能にとって重要なパラメータである。ブロックを横断するCPU時間とファイルシステムの待ち時間とのバランスを左右するからである。block-sizeは、ファイルシステムブロックサイズの整数倍でなければならない。
1990年代には、われわれの公称block-sizeは2.kiBであった。 これは現在では、おそらく4.kiB、8.kiB、16.kiBのいずれかにする必要がある。
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-segかcreate-segが呼び出された場合は、ちょうどパラメータ75,150,2048を使用してinit-wbを呼び出した場合のようにWBが初期化される。
Segは非負の数でなければならない。filename内のデータベースsegをオープンし、オープンに成功した場合はsegを、さもなければステータスコードを返す。mode引数に0を渡した場合、データベースsegは読み取り専用になる。mode引数に2を渡した場合、データベースは読み取り書き込み用になる。
データベースセグメントsegとデータベースセグメントが入っているファイルを閉じる。hammerが#fでかつバッファの解放になんらかの問題があった場合、クローズは異常終了する。ステータスコードが返される。
整数segには未使用のセグメントを指定しなければならない。 整数block-sizeにはB-ツリーブロックサイズを指定する。 block-sizeは、ファイルシステムブロックサイズの整数倍でなければならない。 公称値は4096である。
make-segは、名前がfilenameの新しい空のデータベースsegを作成する。ステータスコードが返される。新しいデータベースを使用するには、open-segを呼び出す。
この関数グループでは、typは次のいずれかでなければならない。
#\D (ディレクトリ)
#\T (通常のツリー).
ルートブロック(1)内のスペシャルエントリで指し示されるtyp#\Dを有するB-ツリー内のすべてのスペシャルエントリは、検査プログラムによるガーベージコレクションから保護される。#\Tは通常の(データ)配列に使用される。
次の関数に渡す書き込み制御ビット引数(WCB)は、各種操作の後のファイル更新の遅延時間を制御する。このビットは以下のように定義される。
| 値 | 名称 | 意味
|
| 1 | WCB-SAP | PUT後のブロックの保存
|
| 2 | WCB-SAR | REMOVE後のブロックの保存
|
| 4 | WCB-SAC | キャッシュされたブロックに変更があった場合のブロックの強制保存
|
| 8 | WCB-FAC | キャッシュされたブロックの変更後に全バッファをフラッシュする(現在は実装されていない)。
|
セグメントsegに型がtypの新しいルートブロックを作成し、そのルートブロックへのオープンしたbt-handleを返す。これは通常、システムがクラッシュした場合に検査プログラムで回収される一時b-ツリーの作成に使用される。
セグメント番号seg、ブロック番号blknumへのオープンしたbt-handleを返す。 ブロックが存在しないかルートブロックでない場合は、ステータスコードが返される。
ブロック番号その他の整数量は、4バイトのポインタとしてデータベースに格納される。
Str2longは、このindexから始まるstringの4バイトを符号なし整数に変換する。
hanはオープンしたbtへのハンドルである。keyは長さが255.B未満の文字列である。
bt:getは、オープンされたhanでbtにkeyで連結された値の文字列を返す。bt内にkeyへの連結が存在しない場合、bt:getは#fを返す。
hanはオープンしたbtへのハンドルである。keyは長さが255.B未満の文字列である。
bt:nextはbthan内の次のkeyを返す。次のキーが存在しない場合は#fを返す。
hanはオープンしたbtへのハンドルである。keyは長さが255.B未満の文字列である。
bt:prevはbthan内の先行するkeyを返す。先行するキーが存在しない場合は#fを返す。
hanはオープンした書き変え可能なbtへのハンドルである。keyとvalは、長さが255.B未満の文字列である。
bt:put!は、bthan内のkeyとvalを連結する。ステータスコードが返される。
hanはオープンした書き変え可能なbtへのハンドルである。keyは長さが255.B未満の文字列である。
bt:rem!はkeyとそれに連結された値をbthanから削除する。
bt:getとbt:put!が動作する値文字列は、長さが255.Bまでに限定される。 db:getとdb:put!は64770.Bまでの長さの値文字列で動作する。
hanはオープンしたbtへのハンドルである。keyは長さが255.B未満の文字列である。
db:getは、hanでオープンしたbtのkeyに連結された(長さが64770.Bまでの)値文字列を返す。 keyがbtに存在しない場合は#fを返す。
hanはオープンした書き変え可能なbtへのハンドルである。keyは長さが255.B未満の文字列である。 valは長さが64770.B未満の文字列である。
db:put!は、bthanのkeyをvalに連結する。ステータスコードが返される。
次の2つの呼び出しはプロセスのロックと同期に使用できる。
keyが存在する場合にだけ、keyとそれに連結された値をbthanから削除する。成功の場合はkeyの値を、失敗の(キーが存在しない)場合は#fを返す。
key1を含むkey1からkey2を除くkey2までのkeyとそれに連結された値を、bthanから削除する。ステータスコードが返される。
手続き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参照。
以下のルーチンが返す値は不定である。
(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でなければならない)。
|
(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数で表される複素数。
|
WBのすべての手続きとマクロのアルファベット順リスト。
bt:get: レコード操作bt:next: レコード操作bt:prev: レコード操作bt:put: 排他制御bt:put!: レコード操作bt:rem: 排他制御bt:rem!han: レコード操作bt:rem*: 多重操作bt:scan: 多重操作check-access: 診断ルーチンclear-stats: 診断ルーチンclose-seg: セグメントcreate-bt: 低レベル操作create-db: 連想配列cstats: 診断ルーチンdb:get: レコード操作db:put!: レコード操作dprintf: 診断チャネルerr_P: コンセプトfinal-wb: セグメントinit-wb: セグメントint: HANDとツリー操作int: SEGint: Scanlong2str!: 低レベル操作make-seg: セグメントopen-bt: 低レベル操作open-db: 連想配列open-seg: セグメントpath: 構成Scheme手続き: ステータスコードshow-buffers: 診断ルーチンstats: 診断ルーチンstr2long: 低レベル操作success_P: コンセプトWBのすべての大域変数のアルファベット順リスト。
argerr: ステータスコードflc_len: コンセプトioerr: ステータスコードmaxerr: ステータスコードnoroom: ステータスコードnotpres: ステータスコードnum_segs: コンセプトretryerr: ステータスコードstrangerr: ステータスコードsuccess: ステータスコードterminated: ステータスコードtyperr: ステータスコードunkerr: ステータスコードWBのデータ型と機能名のアルファベット順リスト。
このマニュアルで紹介したコンセプトのアルファベット順リスト。