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

名前

書式

説明

エラー

バグ

関連項目

この文書について

Recommended readings

Questions & Answers