BTREE(3) | FreeBSD Library Functions Manual | BTREE(3) |
名称
btree — btree データベースアクセス方式解説
ルーチン 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;
この構造体のエレメントは、次の通りです:
- 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 に挿入すると、フィル要因が低くなることがよくあります。この実装では、順序付けられた挿入が最良のケースとなり、通常のページフィル要因よりはるかに良い結果になるように修正してあります。
エラー
btree アクセス方式ルーチンは、ライブラリルーチン dbopen(3) について指定したエラーの場合、処理失敗し、 errno を設定する可能性があります。関連項目
dbopen(3), hash(3), mpool(3), recno(3) Douglas Comer, The Ubiquitous B-tree, ACM Comput. Surv. 11, 2, 121-138, June 1979. Bayer and Unterauer, Prefix B-trees, ACM Transactions on Database Systems, 1, Vol. 2, 11-26, March 1977. D. E. Knuth, The Art of Computer Programming Vol. 3: Sorting and Searching, 471-480, 1968.バグ
ビッグエンディアンおよびリトルエンディアンのバイト順序だけがサポートされています。August 18, 1994 | FreeBSD |