BTREE(3) | Linux Programmer's Manual | BTREE(3) |
名前¶
btree - btree データベースへのアクセスメソッド
書式¶
#include <sys/types.h> #include <db.h>
説明¶
ルーチン 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 バイトで、最大値は 64K である。 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 記憶構造は肥大する一方である。 対策は過度の削除を避けるか、 存在するツリーを調べて定期的に新しいツリーを作るか、だけである。
エラー¶
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.
1994-08-18 | 4.4 Berkeley Distribution |