Provided by: manpages-ja-dev_0.5.0.0.20221215+dfsg-1_all 
名前
btree - btree データベースへのアクセスメソッド
書式
#include <sys/types.h>
#include <db.h>
説明
大事な注意: このページは、バージョン 2.1 までの glibc が提供するインターフェースに ついて説明してい
る。バージョン 2.2 以降の glibc では、もはやこれらの インターフェースは提供されていない。おそらく、この
ページではなく、 libdb ライブラリが提供する API をお探しなのだろう。
ルーチン dbopen(3) はデータベースファイルに対するライブラリインターフェースである。 サポートされている
ファイルフォーマットのひとつに btree ファイルがある。 データベースへのアクセスメソッドに関する一般的な記
述は dbopen(3) に書かれている。 このマニュアルページでは btree 特有の情報についてのみ記述する。
btree データ構造では、ソートされたバランスツリー構造に 互いに関連づけられたキー/データ対を格納している。
dbopen(3) に渡される btree アクセスメソッドに特有のデータ構造体は、 <db.h> インクルードファイルで次のよ
うに定義されている。
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;
この構造体の要素を以下に示す。
flags flags の値は以下の値の論理和で指定される。
R_DUP ツリーの中にキーの重複を許す。すなわちツリーの中に挿入されようとしている キーが既に存在して
いても、その挿入を許可する。デフォルトの動作は dbopen(3) に記述されているように、新しい
キーが挿入されると一致したキーを上書きする。 あるいは R_NOOVERWRITE フラグが指定されている
と挿入に失敗する。 R_DUP フラグは R_NOOVERWRITE フラグによって上書きされる。つまり
R_NOOVERWRITE フラグが指定された場合、ツリーに複製キーを挿入しようとすると失敗する。
データベースにキーの重複があると、 get ルーチンを使った場合のキー/データ対の取得順は未定義
である。それに対し、 R_CURSOR フラグをセットして seq ルーチンを使うと、複製キーのグループの
中の 論理的に「最初」のキーを必ず返してくる。
cachesize
想定されるメモリーキャッシュの最大サイズ (バイト単位)。 この値は あくまで 参考であり、アクセスメ
ソッドはこの値を越えたメモリーの 割り当てに成功することもある。 加えて、物理的な書き込みは可能な限
り遅延されるので、 キャッシュの大きさを適度にしておけば I/O 操作の回数をかなり減らすこと ができ
る。 あきらかにキャッシュを使うと、ツリーが変更されている途中で システムがクラッシュした場合のデー
タ破壊やデータロストの可能性は 増える (まあでもそれだけのこと)。 cachesize が 0 (サイズが指定され
ていない) の場合、デフォルトのキャッシュが使われる。
maxkeypage
単一ページに納められる最大キー数である。現在実装されていない。
minkeypage
単一ページに納められる最小キー数である。この値は、どのキーを オーバーフローページ に納めるか決める
のに使われる。すなわちキーまたはデータが minkeypage の値で分割されたページサイズより大きい時、その
ページに納め る代わりにオーバーフローページに納めるということである。 minkeypage が 0 (キーの最小
値が指定されていない) の場合、値として 2 が使われる。
psize ツリーの中のノードに使われるページサイズ (バイト単位)。 最小値は 512 バイトで、最大値は 64 KiB で
ある。 psize が 0 (ページサイズが指定されていない) の場合、 ファイルシステムの I/O ブロックサイズ
に基づいて決められる。
compare
compare はキーの比較関数である。 最初のキー引数に対し、二番目のキー引数が大きい場合には正の整数
を、 同じ場合にはゼロを、小さい場合には負の整数を返す。 ツリーを開く際には、常に同じ比較関数が使わ
れなければならない。 compare が NULL (比較関数が指定されていない) の場合、 辞書的に比較される。短
いキーは長いキーより小さいことになる。
prefix prefix は前置比較関数である。 このルーチンは (指定された場合には)、二番目のキー引数の バイト数を返
さなくてはならない。これは二番目のキー引数が 一番目のキー引数より大きいかどうか決めるのに必要であ
る。 キーが同じ場合、キーの長さが返る。このルーチンが有用かどうかは、 データに強く依存する。しかし
データセットによっては、明らかにツリー のサイズと検索時間を減らしてくれる。 prefix が NULL (prefix
関数が指定されていない) で、 かつ 比較関数が指定されていないと、デフォルトの辞書比較ルーチンが使わ
れる。 prefix が NULL で比較関数が指定されている場合は、前置比較は行われない。
lorder データベースに格納されているメタデータの整数値のバイトオーダー。 この数字は、順序を整数で表したも
のである。 例えばビッグエンディアンなら、この数値は 4,321 となる。 lorder が 0 (指定されていない)
の場合、現在のホスト で使われているバイトオーダーが使われる。
ファイルが既に存在している (または O_TRUCT フラグが指定されていない) と、 引数 flag, lorder, psize に指定
された値は無視され、 ツリーが作られた時に使った値が用いられる。
ツリーの前方順検索は、最小キーから最大キーに向かって行われる。
ツリーからキー/データ対が削除されることによってできたスペースは、 通常再利用できる形になっているが再利用
されることは無い。 つまり brtee 記憶構造は肥大する一方である。 対策は過度の削除を避けるか、 存在するツ
リーを調べて定期的に新しいツリーを作るか、だけである。
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.
エラー
btree アクセスメソッドルーチンは失敗すると、ライブラリルーチン dbopen(3) で定義されているエラーのいずれ かを errno として返す。
バグ
バイトオーダーとしてはビッグエンディアンとリトルエンディアンのみが サポートされている。
関連項目
dbopen(3), hash(3), mpool(3), recno(3) The Ubiquitous B-tree, Douglas Comer, ACM Comput. Surv. 11, 2 (June 1979), 121-138. Prefix B-trees, Bayer and Unterauer, ACM Transactions on Database Systems, Vol. 2, 1 (March 1977), 11-26. The Art of Computer Programming Vol. 3: Sorting and Searching, D.E. Knuth, 1968, pp 471-480.
この文書について
この man ページは Linux man-pages プロジェクトのリリース 5.10 の一部である。プロジェクトの説明とバグ報告
に関する情報は https://www.kernel.org/doc/man-pages/ に書かれている。
2020-12-21 BTREE(3)