.\" 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:
.\" 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>
.\"
-.\"WORD: access method アクセスメソッド
-.\"WORD: prefix (comparison) 前置比較
-.TH BTREE 3 1994-08-18 "" "Linux Programmer's Manual"
-.UC 7
+.TH BTREE 3 2012\-04\-23 "" "Linux Programmer's Manual"
+.\".UC 7
.SH 名前
-.\"O btree \- btree database access method
btree \- btree データベースへのアクセスメソッド
.SH 書式
.nf
-.ft B
-#include <sys/types.h>
-#include <db.h>
-.ft R
+\fB#include <sys/types.h>
+#include <db.h>\fP
.fi
.SH 説明
-.\"O The routine
-.\"O .BR dbopen (3)
-.\"O is the library interface to database files.
-ルーチン
-.BR dbopen (3)
-はデータベースファイルに対するライブラリインターフェースである。
-.\"O One of the supported file formats is btree files.
-.\"O The general description of the database access methods is in
-.\"O .BR dbopen (3),
-.\"O this manual page describes only the btree specific information.
-サポートされているファイルフォーマットのひとつに btree ファイルがある。
-データベースへのアクセスメソッドに関する一般的な記述は
-.BR dbopen (3)
-に書かれている。
+\fI大事な注意\fP:
+このページは、バージョン 2.1 までの glibc が提供するインターフェースに
+ついて説明している。バージョン 2.2 以降の glibc では、もはやこれらの
+インターフェースは提供されていない。おそらく、このページではなく、
+\fIlibdb\fP ライブラリが提供する API をお探しなのだろう。
+
+ルーチン \fBdbopen\fP(3) はデータベースファイルに対するライブラリインターフェースである。 サポートされているファイルフォーマットのひとつに
+btree ファイルがある。 データベースへのアクセスメソッドに関する一般的な記述は \fBdbopen\fP(3) に書かれている。
このマニュアルページでは btree 特有の情報についてのみ記述する。
.PP
-.\"O The btree data structure is a sorted, balanced tree structure storing
-.\"O associated key/data pairs.
-btree データ構造では、ソートされたバランスツリー構造に
-互いに関連づけられたキー/データ対を格納している。
+btree データ構造では、ソートされたバランスツリー構造に 互いに関連づけられたキー/データ対を格納している。
.PP
-.\"O The btree access method specific data structure provided to
-.\"O .BR dbopen (3)
-.\"O is defined in the
-.\"O .I <db.h>
-.\"O include file as follows:
-.BR dbopen (3)
-に渡される btree アクセスメソッドに特有のデータ構造体は、
-.I <db.h>
+\fBdbopen\fP(3) に渡される btree アクセスメソッドに特有のデータ構造体は、 \fI<db.h>\fP
インクルードファイルで次のように定義されている。
-.sp
.in +4n
.nf
} BTREEINFO;
.fi
.in
-.sp
-.\"O The elements of this structure are as follows:
+.PP
この構造体の要素を以下に示す。
-.TP
-.I flags
-.\"O The flag value is specified by ORing any of the following values:
-.I flags
-の値は以下の値のいずれかか、これらの論理和で指定される。
+.TP
+\fIflags\fP
+\fIflags\fP の値は以下の値の論理和で指定される。
.RS
-.TP
-.B R_DUP
-.\"O Permit duplicate keys in the tree, that is,
-.\"O permit insertion if the key to be
-.\"O inserted already exists in the tree.
-.\"O The default behavior, as described in
-.\"O .BR dbopen (3),
-.\"O is to overwrite a matching key when inserting a new key or to fail if
-.\"O the
-.\"O .B R_NOOVERWRITE
-.\"O flag is specified.
-ツリーの中にキーの重複を許す。すなわちツリーの中に挿入されようとしている
-キーが既に存在していても、その挿入を許可する。デフォルトの動作は
-.BR dbopen (3)
-に記述されているように、新しいキーが挿入されると一致したキーを上書きする。
-あるいは
-.B R_NOOVERWRITE
-フラグが指定されていると挿入に失敗する。
-.\"O The
-.\"O .B R_DUP
-.\"O flag is overridden by the
-.\"O .B R_NOOVERWRITE
-.\"O flag, and if the
-.\"O .B R_NOOVERWRITE
-.\"O flag is specified, attempts to insert duplicate keys into
-.\"O the tree will fail.
-.B R_DUP
-フラグは
-.B R_NOOVERWRITE
-フラグによって上書きされる。つまり
-.B R_NOOVERWRITE
-フラグが指定された場合、ツリーに複製キーを挿入しようとすると失敗する。
+.TP
+\fBR_DUP\fP
+ツリーの中にキーの重複を許す。すなわちツリーの中に挿入されようとしている キーが既に存在していても、その挿入を許可する。デフォルトの動作は
+\fBdbopen\fP(3) に記述されているように、新しいキーが挿入されると一致したキーを上書きする。 あるいは \fBR_NOOVERWRITE\fP
+フラグが指定されていると挿入に失敗する。 \fBR_DUP\fP フラグは \fBR_NOOVERWRITE\fP フラグによって上書きされる。つまり
+\fBR_NOOVERWRITE\fP フラグが指定された場合、ツリーに複製キーを挿入しようとすると失敗する。
.IP
-.\"O If the database contains duplicate keys, the order of retrieval of
-.\"O key/data pairs is undefined if the
-.\"O .I get
-.\"O routine is used, however,
-.\"O .I seq
-.\"O routine calls with the
-.\"O .B R_CURSOR
-.\"O flag set will always return the logical
-.\"O "first" of any group of duplicate keys.
-データベースにキーの重複があると、
-.I get
-ルーチンを使った場合のキー/データ対の取得順は未定義である。それに対し、
-.B R_CURSOR
-フラグをセットして
-.I seq
-ルーチンを使うと、複製キーのグループの中の
-論理的に「最初」のキーを必ず返してくる。
+データベースにキーの重複があると、 \fIget\fP ルーチンを使った場合のキー/データ対の取得順は未定義である。それに対し、 \fBR_CURSOR\fP
+フラグをセットして \fIseq\fP ルーチンを使うと、複製キーのグループの中の 論理的に「最初」のキーを必ず返してくる。
.RE
-.TP
-.I cachesize
-.\"O A suggested maximum size (in bytes) of the memory cache.
-想定されるメモリキャッシュの最大サイズ (バイト単位)。
-.\"O This value is
-.\"O .I only
-.\"O advisory, and the access method will allocate more memory rather than fail.
-.\"O Since every search examines the root page of the tree, caching the most
-.\"O recently used pages substantially improves access time.
-この値は
-.I あくまで
-参考であり、アクセスメソッドはこの値を越えたメモリの
-割り当てに成功することもある。
-.\"O In addition, physical writes are delayed as long as possible, so a moderate
-.\"O cache can reduce the number of I/O operations significantly.
-加えて、物理的な書き込みは可能な限り遅延されるので、
-キャッシュの大きさを適度にしておけば I/O 操作の回数をかなり減らすこと
-ができる。
-.\"O Obviously, using a cache increases (but only increases) the likelihood of
-.\"O corruption or lost data if the system crashes while a tree is being modified.
-あきらかにキャッシュを使うと、ツリーが変更されている途中で
-システムがクラッシュした場合のデータ破壊やデータロストの可能性は
-増える (まあでもそれだけのこと)。
-.\"O If
-.I cachesize
-.\"O is 0 (no size is specified) a default cache is used.
-が 0 (サイズが指定されていない) の場合、デフォルトのキャッシュが使われる。
-.TP
-.I maxkeypage
-.\"O The maximum number of keys which will be stored on any single page.
-.\"O Not currently implemented.
-単一ページに納められる最大キー数である。現在実装されていない。
+.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
+.\" 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
-.\"O The minimum number of keys which will be stored on any single page.
-.\"O This value is used to determine which keys will be stored on overflow
-.\"O pages, that is, if a key or data item is longer than the pagesize divided
-.\"O by the minkeypage value, it will be stored on overflow pages instead
-.\"O of in the page itself.
-単一ページに納められる最小キー数である。この値は、どのキーを
-オーバーフローページ
-に納めるか決めるのに使われる。すなわちキーまたはデータが
-minkeypage の値で分割されたページサイズより大きい時、そのページに納め
-る代わりにオーバーフローページに納めるということである。
-.\"O If
-.I minkeypage
-.\"O is 0 (no minimum number of keys is specified) a value of 2 is used.
-が 0 (キーの最小値が指定されていない) の場合、値として 2 が使われる。
-.TP
-.I psize
-.\"O Page size is the size (in bytes) of the pages used for nodes in the tree.
-.\"O The minimum page size is 512 bytes and the maximum page size is 64K.
-ツリーの中のノードに使われるページサイズ (バイト単位)。
-最小値は 512 バイトで、最大値は 64K である。
-.\"O If
-.I psize
-.\"O is 0 (no page size is specified) a page size is chosen based on the
-.\"O underlying file system I/O block size.
-が 0 (ページサイズが指定されていない) の場合、
-ファイルシステムの I/O ブロックサイズに基づいて決められる。
-.TP
-.I compare
-.\"O Compare is the key comparison function.
-.I compare
-はキーの比較関数である。
-.\"O It must return an integer less than, equal to, or greater than zero if the
-.\"O first key argument is considered to be respectively less than, equal to,
-.\"O or greater than the second key argument.
-最初のキー引数に対し、二番目のキー引数が大きい場合には正の整数を、
-同じ場合にはゼロを、小さい場合には負の整数を返す。
-.\"O The same comparison function must be used on a given tree every time it
-.\"O is opened.
-ツリーを開く際には、常に同じ比較関数が使われなければならない。
-.\"O If
-.I compare
-.\"O is NULL (no comparison function is specified), the keys are compared
-.\"O lexically, with shorter keys considered less than longer keys.
-が NULL (比較関数が指定されていない) の場合、
-辞書的に比較される。短いキーは長いキーより小さいことになる。
-.TP
-.I prefix
-.\"O Prefix is the prefix comparison function.
-.I prefix
-は前置比較関数である。
-.\"O If specified, this routine must return the number of bytes of the second key
-.\"O argument which are necessary to determine that it is greater than the first
-.\"O key argument.
-このルーチンは (指定された場合には)、二番目のキー引数の
-バイト数を返さなくてはならない。これは二番目のキー引数が
-一番目のキー引数より大きいかどうか決めるのに必要である。
-.\"NAKANO ちょっと意味わからん...
-.\"O If the keys are equal, the key length should be returned.
-.\"O Note, the usefulness of this routine is very data-dependent, but, in some
-.\"O data sets can produce significantly reduced tree sizes and search times.
-キーが同じ場合、キーの長さが返る。このルーチンが有用かどうかは、
-データに強く依存する。しかしデータセットによっては、明らかにツリー
-のサイズと検索時間を減らしてくれる。
-.\"O If
-.\"O .I prefix
-.\"O is NULL (no prefix function is specified),
-.\"O .I and
-.\"O no comparison function is specified, a default lexical comparison routine
-.\"O is used.
-.I prefix
-が NULL (prefix 関数が指定されていない) で、
-.I かつ
-比較関数が指定されていないと、デフォルトの辞書比較ルーチンが使われる。
-.\"O If
-.\"O .I prefix
-.\"O is NULL and a comparison routine is specified, no prefix comparison is
-.\"O done.
-.I prefix
-が NULL で比較関数が指定されている場合は、前置比較は行われない。
-.TP
-.I lorder
-.\"O The byte order for integers in the stored database metadata.
-.\"O The number should represent the order as an integer; for example,
-.\"O big endian order would be the number 4,321.
-.\"O If
-.\"O .I lorder
-.\"O is 0 (no order is specified) the current host order is used.
-データベースに格納されているメタデータの整数値のバイトオーダー。
-この数字は、順序を整数で表したものである。
-例えばビッグエンディアンなら、この数値は 4,321 となる。
-.I lorder
-が 0 (指定されていない) の場合、現在のホスト
-で使われているバイトオーダーが使われる。
+単一ページに納められる最大キー数である。現在実装されていない。
+.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
-.\"O If the file already exists (and the
-.\"O .B O_TRUNC
-.\"O flag is not specified), the
-.\"O values specified for the arguments
-.\"O .IR flags ,
-.\"O .I lorder
-.\"O and
-.\"O .I psize
-.\"O are ignored
-.\"O in favor of the values used when the tree was created.
-ファイルが既に存在している (または
-.B O_TRUCT
-フラグが指定されていない) と、
-引き数
-.IR flag ,
-.IR lorder ,
-.I psize
-に指定された値は無視され、
-ツリーが作られた時に使った値が用いられる。
+ファイルが既に存在している (または \fBO_TRUCT\fP フラグが指定されていない) と、 引き数 \fIflag\fP, \fIlorder\fP,
+\fIpsize\fP に指定された値は無視され、 ツリーが作られた時に使った値が用いられる。
.PP
-.\"O Forward sequential scans of a tree are from the least key to the greatest.
ツリーの前方順検索は、最小キーから最大キーに向かって行われる。
.PP
-.\"O Space freed up by deleting key/data pairs from the tree is never reclaimed,
-.\"O although it is normally made available for reuse.
-.\"O This means that the btree storage structure is grow-only.
-.\"O The only solutions are to avoid excessive deletions, or to create a fresh
-.\"O tree periodically from a scan of an existing one.
-ツリーからキー/データ対が削除されることによってできたスペースは、
-通常再利用できる形になっているが再利用されることは無い。
-つまり brtee 記憶構造は肥大する一方である。
-対策は過度の削除を避けるか、
-存在するツリーを調べて定期的に新しいツリーを作るか、だけである。
+ツリーからキー/データ対が削除されることによってできたスペースは、 通常再利用できる形になっているが再利用されることは無い。 つまり brtee
+記憶構造は肥大する一方である。 対策は過度の削除を避けるか、 存在するツリーを調べて定期的に新しいツリーを作るか、だけである。
.PP
-.\"O Searches, insertions, and deletions in a btree will all complete in
-.\"O O lg base N where base is the average fill factor.
-.\"O Often, inserting ordered data into btrees results in a low fill factor.
-.\"O This implementation has been modified to make ordered insertion the best
-.\"O case, resulting in a much better than normal page fill factor.
+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 エラー
-.\"O The
-.\"O .I btree
-.\"O access method routines may fail and set
-.\"O .I errno
-.\"O for any of the errors specified for the library routine
-.\"O .BR dbopen (3).
-.I btree
-アクセスメソッドルーチンは失敗すると、ライブラリルーチン
-.BR dbopen (3)
-で定義されているエラーのいずれかを
-.I errno
-として返す。
-.\"O .SH BUGS
+\fIbtree\fP アクセスメソッドルーチンは失敗すると、ライブラリルーチン \fBdbopen\fP(3) で定義されているエラーのいずれかを
+\fIerrno\fP として返す。
.SH バグ
-.\"O Only big and little endian byte order is supported.
-バイトオーダーとしてはビッグエンディアンとリトルエンディアンのみが
-サポートされている。
+バイトオーダーとしてはビッグエンディアンとリトルエンディアンのみが サポートされている。
.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.
+\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.78 の一部
+である。プロジェクトの説明とバグ報告に関する情報は
+http://www.kernel.org/doc/man\-pages/ に書かれている。
OSDN Git Service
