btreeのヘルプ・マニュアル
日本語 英語
btree --help
man btree
BTREE(3) Linux Programmer’s Manual BTREE(3)
名前
btree - btree データベースへのアクセスメソッド
書式
#include
#include
説明
ルーチン dbopen(3) はデータベースファイルに対するライブラリインターフェ
ースである。サポートされているファイルフォーマットのひとつに btree ファ
イ ル が あ る 。データベースへのアクセスメソッドに関する一般的な記述は
dbopen(3) に書かれている。このマニュアルページでは btree 特有の情報につ
いてのみ記述する。
btree データ構造では、ソートされたバランスツリー構造に互いに関連づけら
れたキー/データ対を格納している。
dbopen(3) に渡される btree アクセスメソッドに特有のデータ構 造 体 は 、
インクルードファイルで次のように定義されている。
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 操作の回数
をかなり減らすことができる。あきらかにキャッシュを使うと、ツリー
が変更されている途中でシステムがクラッシュした場合のデータ破壊や
データロストの可能性は増える (まあでもそれだけのこと) 。 cache-
size が 0 (サイズが指定されていない) の場合、デフォルトのキャッ
シュが使われる。
maxkeypage
単一ページに納められる最大キー数である。現在実装されていない。
minkeypage
単一ページに納められる最小キー数である。この値は、どのキーをオー
バーフローページに納めるか決めるのに使われる。すなわちキーまたは
データが minkeypage の値で分割されたページサイズより大きい時、そ
のページに納める代わりにオーバーフローページに納めるということで
ある。 minkeypage が 0 (キーの最小値が指定されていない) の場合、
値として 2 が使われる。
psize ツリーの中のノードに使われるページサイズ (バイト単位)。最小値は
512 バイトで、最大値は 64K である。 psize が 0 (ページサイズが指
定 されていない) の場合、ファイルシステムの I/O ブロックサイズに
基づいて決められる。
compare
compare はキーの比較関数である。最初のキー引数に対し、二番目のキ
ー引数が大きい場合には正の整数を、同じ場合にはゼロを、小さい場合
には負の整数を返す。ツリーを開く際には、常に同じ比較関数が使われ
な ければならない。 compare が NULL (比較関数が指定されていない)
の場合、辞書的に比較される。短いキーは長いキーより小さいことにな
る。
prefix prefix は前置比較関数である。このルーチンは (指定された場合には)
、二番目のキー引数のバイト数を返さなくてはならない。これは二番目
のキー引数が一番目のキー引数より大きいかどうか決めるのに必要であ
る。キーが同じ場合、キーの長さが返る。このルーチンが有用かどうか
は、データに強く依存する。しかしデータセットによっては、明らかに
ツリーのサイズと検索時間を減らしてくれる。 prefix が NULL (pre-
fix 関数が指定されていない) で、 かつ比較関数が指定されていない
と、デフォルトの辞書比較ルーチンが使われる。 prefix が NULL で比
較関数が指定されている場合は、前置比較は行われない。
lorder データベースに格納されているメタデータの整数値のバイトオーダー。
この数字は、順序を整数で表したものである。例えばビッグエンディア
ンなら、この数値は 4,321 となる。 lorder が 0 (指定されていない)
の場合、現在のホストで使われているバイトオーダーが使われる。
ファイルが既に存在している (または O_TRUCT フラグが指定されていない) と
、引き数 flag, lorder, psize に指定された値は無視され、ツリーが作られた
時に使った値が用いられる。
ツリーの前方順検索は、最小キーから最大キーに向かって行われる。
ツリーからキー/データ対が削除されることによってできたスペースは、通常再
利用できる形になっているが再利用されることは無い。つまり brtee 記憶構造
は肥大する一方である。対策は過度の削除を避けるか、存在するツリーを調 べ
て定期的に新しいツリーを作るか、だけである。
エラー
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.
4.4 Berkeley Distribution 1994-08-18 BTREE(3)