.\" Copyright (c) 1990, 1993 .\" The Regents of the University of California. All rights reserved. .\" .\" Redistribution and use in source and binary forms, with or without .\" modification, are permitted provided that the following conditions .\" are met: .\" 1. Redistributions of source code must retain the above copyright .\" notice, this list of conditions and the following disclaimer. .\" 2. Redistributions in binary form must reproduce the above copyright .\" notice, this list of conditions and the following disclaimer in the .\" documentation and/or other materials provided with the distribution. .\" 3. All advertising materials mentioning features or use of this software .\" must display the following acknowledgement: .\" This product includes software developed by the University of .\" California, Berkeley and its contributors. .\" 4. Neither the name of the University nor the names of its contributors .\" may be used to endorse or promote products derived from this software .\" without specific prior written permission. .\" .\" THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND .\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE .\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE .\" ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE .\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL .\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS .\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) .\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT .\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY .\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF .\" SUCH DAMAGE. .\" .\" @(#)btree.3 8.4 (Berkeley) 8/18/94 .\" .\" Japanese Version Copyright (c) 1999 Shouichi Saito .\" all rights reserved. .\" Translated Mon Jul 26 21:43:11 JST 1999 .\" by Shouichi Saito .\" Proofed Mon Aug 16 1999 by NAKANO Takeo .\" .\"WORD: access method アクセスメソッド .\"WORD: prefix (comparison) 前置比較 .TH BTREE 3 1994-08-18 "" "Linux Programmer's Manual" .UC 7 .SH 名前 btree \- btree データベースへのアクセスメソッド .SH 書式 .nf .ft B #include #include .ft R .fi .SH 説明 ルーチン .BR dbopen (3) はデータベースファイルに対するライブラリインターフェースである。 サポートされているファイルフォーマットのひとつに btree ファイルがある。 データベースへのアクセスメソッドに関する一般的な記述は .BR dbopen (3) に書かれている。 このマニュアルページでは btree 特有の情報についてのみ記述する。 .PP btree データ構造では、ソートされたバランスツリー構造に 互いに関連づけられたキー/データ対を格納している。 .PP .BR dbopen (3) に渡される btree アクセスメソッドに特有のデータ構造体は、 .I インクルードファイルで次のように定義されている。 .sp .in +4n .nf typedef struct { unsigned long flags; unsigned int cachesize; int maxkeypage; int minkeypage; unsigned int psize; int (*compare)(const DBT *key1, const DBT *key2); size_t (*prefix)(const DBT *key1, const DBT *key2); int lorder; } BTREEINFO; .fi .in .sp この構造体の要素を以下に示す。 .TP .I flags .I flags の値は以下の値のいずれかか、これらの論理和で指定される。 .RS .TP .B R_DUP ツリーの中にキーの重複を許す。すなわちツリーの中に挿入されようとしている キーが既に存在していても、その挿入を許可する。デフォルトの動作は .BR dbopen (3) に記述されているように、新しいキーが挿入されると一致したキーを上書きする。 あるいは .B R_NOOVERWRITE フラグが指定されていると挿入に失敗する。 .B R_DUP フラグは .B R_NOOVERWRITE フラグによって上書きされる。つまり .B R_NOOVERWRITE フラグが指定された場合、ツリーに複製キーを挿入しようとすると失敗する。 .IP データベースにキーの重複があると、 .I get ルーチンを使った場合のキー/データ対の取得順は未定義である。それに対し、 .B R_CURSOR フラグをセットして .I seq ルーチンを使うと、複製キーのグループの中の 論理的に「最初」のキーを必ず返してくる。 .RE .TP .I cachesize 想定されるメモリキャッシュの最大サイズ (バイト単位)。 この値は .I あくまで 参考であり、アクセスメソッドはこの値を越えたメモリの 割り当てに成功することもある。 加えて、物理的な書き込みは可能な限り遅延されるので、 キャッシュの大きさを適度にしておけば I/O 操作の回数をかなり減らすこと ができる。 あきらかにキャッシュを使うと、ツリーが変更されている途中で システムがクラッシュした場合のデータ破壊やデータロストの可能性は 増える (まあでもそれだけのこと)。 .I cachesize が 0 (サイズが指定されていない) の場合、デフォルトのキャッシュが使われる。 .TP .I maxkeypage 単一ページに納められる最大キー数である。現在実装されていない。 .\" The maximum number of keys which will be stored on any single page. .\" Because of the way the btree data structure works, .\" .I maxkeypage .\" must always be greater than or equal to 2. .\" If .\" .I maxkeypage .\" is 0 (no maximum number of keys is specified) the page fill factor is .\" made as large as possible (which is almost invariably what is wanted). .TP .I minkeypage 単一ページに納められる最小キー数である。この値は、どのキーを オーバーフローページ に納めるか決めるのに使われる。すなわちキーまたはデータが minkeypage の値で分割されたページサイズより大きい時、そのページに納め る代わりにオーバーフローページに納めるということである。 .I minkeypage が 0 (キーの最小値が指定されていない) の場合、値として 2 が使われる。 .TP .I psize ツリーの中のノードに使われるページサイズ (バイト単位)。 最小値は 512 バイトで、最大値は 64K である。 .I psize が 0 (ページサイズが指定されていない) の場合、 ファイルシステムの I/O ブロックサイズに基づいて決められる。 .TP .I compare .I compare はキーの比較関数である。 最初のキー引数に対し、二番目のキー引数が大きい場合には正の整数を、 同じ場合にはゼロを、小さい場合には負の整数を返す。 ツリーを開く際には、常に同じ比較関数が使われなければならない。 .I compare が NULL (比較関数が指定されていない) の場合、 辞書的に比較される。短いキーは長いキーより小さいことになる。 .TP .I prefix .I prefix は前置比較関数である。 このルーチンは (指定された場合には)、二番目のキー引数の バイト数を返さなくてはならない。これは二番目のキー引数が 一番目のキー引数より大きいかどうか決めるのに必要である。 .\"NAKANO ちょっと意味わからん... キーが同じ場合、キーの長さが返る。このルーチンが有用かどうかは、 データに強く依存する。しかしデータセットによっては、明らかにツリー のサイズと検索時間を減らしてくれる。 .I prefix が NULL (prefix 関数が指定されていない) で、 .I かつ 比較関数が指定されていないと、デフォルトの辞書比較ルーチンが使われる。 .I prefix が NULL で比較関数が指定されている場合は、前置比較は行われない。 .TP .I lorder データベースに格納されているメタデータの整数値のバイトオーダー。 この数字は、順序を整数で表したものである。 例えばビッグエンディアンなら、この数値は 4,321 となる。 .I lorder が 0 (指定されていない) の場合、現在のホスト で使われているバイトオーダーが使われる。 .PP ファイルが既に存在している (または .B O_TRUCT フラグが指定されていない) と、 引き数 .IR flag , .IR lorder , .I psize に指定された値は無視され、 ツリーが作られた時に使った値が用いられる。 .PP ツリーの前方順検索は、最小キーから最大キーに向かって行われる。 .PP ツリーからキー/データ対が削除されることによってできたスペースは、 通常再利用できる形になっているが再利用されることは無い。 つまり brtee 記憶構造は肥大する一方である。 対策は過度の削除を避けるか、 存在するツリーを調べて定期的に新しいツリーを作るか、だけである。 .PP .SH エラー .I btree アクセスメソッドルーチンは失敗すると、ライブラリルーチン .BR dbopen (3) で定義されているエラーのいずれかを .I errno として返す。 .SH バグ バイトオーダーとしてはビッグエンディアンとリトルエンディアンのみが サポートされている。 .SH 関連項目 .BR dbopen (3), .BR hash (3), .BR mpool (3), .BR recno (3) .sp .IR "The Ubiquitous B-tree" , Douglas Comer, ACM Comput. Surv. 11, 2 (June 1979), 121-138. .sp .IR "Prefix B-trees" , Bayer and Unterauer, ACM Transactions on Database Systems, Vol. 2, 1 (March 1977), 11-26. .sp .IR "The Art of Computer Programming Vol. 3: Sorting and Searching" , D.E. Knuth, 1968, pp 471-480.