btree(3)

btree − btree データベースアクセス方式

#include <sys/types.h>
#include <db.h>

ルーチン dbopen() は、データベースファイルへのライブラリインタフェースで す。サポートされているファイル形式の 1 つは btree ファイルです。データ ベースアクセス方式の一般的な説明は dbopen(3) にあります。このマニュアル ページは、 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;

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

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 に挿入すると、 フィル要因が低くなることがよくあります。この実装では、順序付けられた挿入 が最良のケースとなり、通常のページフィル要因よりはるかに良い結果になるよ うに修正してあります。

エラー

btree アクセス方式ルーチンは、ライブラリルーチン dbopen(3) について指定し たエラーの場合、処理失敗し、 errno を設定する可能性があります。

dbopen(3), hash(3), mpool(3), recno(3)

ビッグエンディアンおよびリトルエンディアンのバイト順序だけがサポートされ ています。

FreeBSD 10.0 August 18, 1994 FreeBSD 10.0