.\" Copyright (c) 1990, 1993 .\" The Regents of the University of California. All rights reserved. .\" .\" %%%LICENSE_START(BSD_4_CLAUSE_UCB) .\" 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. .\" %%%LICENSE_END .\" .\" @(#)btree.3 8.4 (Berkeley) 8/18/94 .\" .\"******************************************************************* .\" .\" This file was generated with po4a. Translate the source file. .\" .\"******************************************************************* .\" .\" 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 .\" Updated 2012-05-01, Akihiro MOTOKI .\" .TH BTREE 3 2012\-04\-23 "" "Linux Programmer's Manual" .\".UC 7 .SH 名前 btree \- btree データベースへのアクセスメソッド .SH 書式 .nf \fB#include #include \fP .fi .SH 説明 \fI大事な注意\fP: このページは、バージョン 2.1 までの glibc が提供するインターフェースに ついて説明している。バージョン 2.2 以降の glibc では、もはやこれらの インターフェースは提供されていない。おそらく、このページではなく、 \fIlibdb\fP ライブラリが提供する API をお探しなのだろう。 ルーチン \fBdbopen\fP(3) はデータベースファイルに対するライブラリインターフェースである。 サポートされているファイルフォーマットのひとつに btree ファイルがある。 データベースへのアクセスメソッドに関する一般的な記述は \fBdbopen\fP(3) に書かれている。 このマニュアルページでは btree 特有の情報についてのみ記述する。 .PP btree データ構造では、ソートされたバランスツリー構造に 互いに関連づけられたキー/データ対を格納している。 .PP \fBdbopen\fP(3) に渡される btree アクセスメソッドに特有のデータ構造体は、 \fI\fP インクルードファイルで次のように定義されている。 .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 .PP この構造体の要素を以下に示す。 .TP \fIflags\fP \fIflags\fP の値は以下の値の論理和で指定される。 .RS .TP \fBR_DUP\fP ツリーの中にキーの重複を許す。すなわちツリーの中に挿入されようとしている キーが既に存在していても、その挿入を許可する。デフォルトの動作は \fBdbopen\fP(3) に記述されているように、新しいキーが挿入されると一致したキーを上書きする。 あるいは \fBR_NOOVERWRITE\fP フラグが指定されていると挿入に失敗する。 \fBR_DUP\fP フラグは \fBR_NOOVERWRITE\fP フラグによって上書きされる。つまり \fBR_NOOVERWRITE\fP フラグが指定された場合、ツリーに複製キーを挿入しようとすると失敗する。 .IP データベースにキーの重複があると、 \fIget\fP ルーチンを使った場合のキー/データ対の取得順は未定義である。それに対し、 \fBR_CURSOR\fP フラグをセットして \fIseq\fP ルーチンを使うと、複製キーのグループの中の 論理的に「最初」のキーを必ず返してくる。 .RE .TP \fIcachesize\fP 想定されるメモリーキャッシュの最大サイズ (バイト単位)。 この値は \fIあくまで\fP 参考であり、アクセスメソッドはこの値を越えたメモリーの 割り当てに成功することもある。 加えて、物理的な書き込みは可能な限り遅延されるので、 キャッシュの大きさを適度にしておけば I/O 操作の回数をかなり減らすこと ができる。 あきらかにキャッシュを使うと、ツリーが変更されている途中で システムがクラッシュした場合のデータ破壊やデータロストの可能性は 増える (まあでもそれだけのこと)。 \fIcachesize\fP が 0 (サイズが指定されていない) の場合、デフォルトのキャッシュが使われる。 .TP \fImaxkeypage\fP .\" 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 \fIminkeypage\fP 単一ページに納められる最小キー数である。この値は、どのキーを オーバーフローページ に納めるか決めるのに使われる。すなわちキーまたはデータが minkeypage の値で分割されたページサイズより大きい時、そのページに納め る代わりにオーバーフローページに納めるということである。 \fIminkeypage\fP が 0 (キーの最小値が指定されていない) の場合、値として 2 が使われる。 .TP \fIpsize\fP ツリーの中のノードに使われるページサイズ (バイト単位)。 最小値は 512 バイトで、最大値は 64K である。 \fIpsize\fP が 0 (ページサイズが指定されていない) の場合、 ファイルシステムの I/O ブロックサイズに基づいて決められる。 .TP \fIcompare\fP \fIcompare\fP はキーの比較関数である。 最初のキー引数に対し、二番目のキー引数が大きい場合には正の整数を、 同じ場合にはゼロを、小さい場合には負の整数を返す。 ツリーを開く際には、常に同じ比較関数が使われなければならない。 \fIcompare\fP が NULL (比較関数が指定されていない) の場合、 辞書的に比較される。短いキーは長いキーより小さいことになる。 .TP \fIprefix\fP \fIprefix\fP は前置比較関数である。 このルーチンは (指定された場合には)、二番目のキー引数の バイト数を返さなくてはならない。これは二番目のキー引数が 一番目のキー引数より大きいかどうか決めるのに必要である。 キーが同じ場合、キーの長さが返る。このルーチンが有用かどうかは、 データに強く依存する。しかしデータセットによっては、明らかにツリー のサイズと検索時間を減らしてくれる。 \fIprefix\fP が NULL (prefix 関数が指定されていない) で、 \fIかつ\fP 比較関数が指定されていないと、デフォルトの辞書比較ルーチンが使われる。 \fIprefix\fP が NULL で比較関数が指定されている場合は、前置比較は行われない。 .TP \fIlorder\fP データベースに格納されているメタデータの整数値のバイトオーダー。 この数字は、順序を整数で表したものである。 例えばビッグエンディアンなら、この数値は 4,321 となる。 \fIlorder\fP が 0 (指定されていない) の場合、現在のホスト で使われているバイトオーダーが使われる。 .PP ファイルが既に存在している (または \fBO_TRUCT\fP フラグが指定されていない) と、 引き数 \fIflag\fP, \fIlorder\fP, \fIpsize\fP に指定された値は無視され、 ツリーが作られた時に使った値が用いられる。 .PP ツリーの前方順検索は、最小キーから最大キーに向かって行われる。 .PP ツリーからキー/データ対が削除されることによってできたスペースは、 通常再利用できる形になっているが再利用されることは無い。 つまり brtee 記憶構造は肥大する一方である。 対策は過度の削除を避けるか、 存在するツリーを調べて定期的に新しいツリーを作るか、だけである。 .PP Searches, insertions, and deletions in a btree will all complete in O lg base N where base is the average fill factor. Often, inserting ordered data into btrees results in a low fill factor. This implementation has been modified to make ordered insertion the best case, resulting in a much better than normal page fill factor. .SH エラー \fIbtree\fP アクセスメソッドルーチンは失敗すると、ライブラリルーチン \fBdbopen\fP(3) で定義されているエラーのいずれかを \fIerrno\fP として返す。 .SH バグ バイトオーダーとしてはビッグエンディアンとリトルエンディアンのみが サポートされている。 .SH 関連項目 \fBdbopen\fP(3), \fBhash\fP(3), \fBmpool\fP(3), \fBrecno\fP(3) \fIThe Ubiquitous B\-tree\fP, Douglas Comer, ACM Comput. Surv. 11, 2 (June 1979), 121\-138. \fIPrefix B\-trees\fP, Bayer and Unterauer, ACM Transactions on Database Systems, Vol. 2, 1 (March 1977), 11\-26. \fIThe Art of Computer Programming Vol. 3: Sorting and Searching\fP, D.E. Knuth, 1968, pp 471\-480. .SH この文書について この man ページは Linux \fIman\-pages\fP プロジェクトのリリース 3.79 の一部 である。プロジェクトの説明とバグ報告に関する情報は http://www.kernel.org/doc/man\-pages/ に書かれている。