manページ  — BTREE

btree データ構造は、関連するキー / データのペアを格納する、 ソート済みのバランスのとれたツリー構造です。

dbopen() に提供される btree アクセス方式に固有のデータ構造は、 次のように < db.h> インクルードファイルに定義されています。

typedef struct {
        u_long flags;
        u_int cachesize;
        int maxkeypage;
        int minkeypage;
        u_int psize;
        int (*compare)(const DBT *key1, const DBT *key2);
        size_t (*prefix)(const DBT *key1, const DBT *key2);
        int lorder;
} BTREEINFO;

この構造体のエレメントは次のとおりです。

flags
	flag の値は以降の値の or (論理和) を取ることによって定義されます。
R_DUP	ツリー内部に重複したキーを許容します。 すなわち、挿入するキーが ツリー内に既に存在する場合にも挿入を許容します。 dbopen(3) に記述されたデフォルトの動作としては、 新しいキーを挿入するときに一致するキーを上書きするか、 または R_NOOVERWRITE フラグが指定されている場合は処理失敗します。 R_DUP フラグは R_NOOVERWRITE フラグによって上書きされ、 R_NOOVERWRITE フラグが指定されている場合は、 重複するキーをツリーに挿入しようとする処理が失敗します。 データベースに重複したキーが含まれている場合、 get ルーチンを使用すると、 キー / データのペアの取り出しの順序は未定義になります。 しかし、R_CURSOR フラグを設定して seq ルーチンを呼び出すと、 重複したキーの論理的な "最初" が必ず返されます。

cachesize
	メモリキャッシュの示唆する最大サイズ (バイト単位)。 この値は 単に アドバイスにすぎず、 アクセス方式は処理失敗せずに多くのメモリを割り振ります。 各検索がツリーのルートページを調査するので、 最も最近に使用されたページをキャッシュすると、 アクセス時間が短くなります。 さらに、物理的な書き込みは可能な限り遅延されるので、 適度なキャッシュは入出力操作の回数を大幅に減少できます。 明らかに、キャッシュを使用すると、 ツリーを修正している間にシステムがクラッシュした場合、 データが破損または喪失される見込みは増大します (増大するだけです)。 cachesize が 0 (サイズが指定されていない) の場合、 デフォルトのキャッシュが使用されます。
maxkeypage
	1 ページに格納されるキーの最大数。現時点では実現されていません。
minkeypage
	1 ページに格納されるキーの最少数。 この値を使用して、 オーバフローページにどのキーが格納されるかを判定します。 すなわち、キーまたはデータ構造が、minkeypage 値で除算された pagesize より長い場合は、ページ自体にではなく、 オーバフローページに格納されます。 minkeypage が 0 (キーの最少数が指定されていない) の場合、 値 2 が使用されます。
psize
	ページサイズは、ツリー内のノードに使用されるページのサイズ (バイト単位) です。最少ページサイズは 512 バイトであり、 最大ページサイズは 64K です。 psize が 0 (ページサイズが指定されていない) の場合、 ページサイズは、基層となっている ファイルシステム入出力ブロックサイズを基礎にして選択されます。
compare
	compare はキー比較関数です。 最初のキー引数が 2 番めのキー引数より小さいと考えられるときは、 0 より小さい整数を返す必要があります。 2 番めのキー引数と同じと考えられるときは、 0 を返す必要があります。 2 番めのキー引数より大きいと考えられるときは、 0 より大きい整数を返す必要があります。 指定のツリーについては、ツリーが開かれるたびに、 同じ比較関数を使用する必要があります。 compare が NULL の場合 (比較関数が指定されない場合)、 キーは辞書的に比較され、 短いキーは長いキーより小さいと見なされます。
prefix
	prefix は接頭語比較関数です。 指定すると、このルーチンは、2 番めのキーとなる引数のバイト数を返します。 これは、2 番めの引数が1 番めの引数より大きいことを判定するために必要です。 キーが等しい場合は、キーの長さが返されるはずです。 このルーチンの便利さはきわめてデータに依存します。 しかし、データセットによっては、 ツリーのサイズと検索時間が大幅に削減できることもあることに注意してください。 prefix が NULL (接頭語関数が指定されていない) であって、 しかも 比較関数が指定されない場合は、 デフォルトの辞書的な比較ルーチンが使用されます。 prefix が NULL であり、しかも比較ルーチンが指定されている場合、 比較は行われません。
lorder
	格納されたデータベースメタデータ内の整数のバイト順序。 数字は整数としての順序を表すはずです。 たとえば、ビッグエンディアン順では数字 4,321 になります。 lorder が 0 の (順序が指定されていない) 場合、 現在のホスト順序が使用されます。

ファイルが既に存在している場合 (しかも O_TRUNC フラグが指定されていない場合)、 パラメータ flags, lorder, psize について指定された値は、 ツリーが作成されたときに使用された値のために無視されます。

ツリーの前方シーケンシャル走査は、 最も小さいキーから最も大きいキーに向かいます。

ツリーからキー / データのペアを削除することによって解放された空間は、 再び要求されることはありませんが、 再使用のために利用できるようにされるのが普通です。 すなわち、 btree 記憶域は成長のみです。 唯一の解決策は、過度な削除を避けること、 または既存のツリーの走査から定期的に新しいツリーを作成することです。

btree 内の検索、挿入、および削除はすべて、 基底が平均のフィル要因である基底 N の O の対数で完了します。 順序付けられたデータを btree に挿入すると、 フィル要因が低くなることがよくあります。 この実装では、順序付けられた挿入が最良のケースとなり、 通常のページフィル要因よりはるかに良い結果になるように修正してあります。

Douglas Comer, 2, ACM Comput. Surv. 11, 121-138, The Ubiquitous B-tree, June 1979.

Bayer, Unterauer, 1, ACM Transactions on Database Systems, 11-26, Prefix B-trees, Vol. 2, March 1977.

D. E. Knuth, The Art of Computer Programming Vol. 3: Sorting and Searching, 471-480, 1968.