+++ /dev/null
-.\" 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 <ss236rx@ymg.urban.ne.jp>
-.\" Proofed Mon Aug 16 1999 by NAKANO Takeo <nakano@apm.seikei.ac.jp>
-.\" Updated 2012-05-01, Akihiro MOTOKI <amotoki@gmail.com>
-.\"
-.TH BTREE 3 2012\-04\-23 "" "Linux Programmer's Manual"
-.\".UC 7
-.SH 名前
-btree \- btree データベースへのアクセスメソッド
-.SH 書式
-.nf
-\fB#include <sys/types.h>
-#include <db.h>\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<db.h>\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/ に書かれている。
OSDN Git Service
