日本語 man コマンド類 (ja-man-1.1j_5) と日本語 man ドキュメント (ja-man-doc-5.4 (5.4-RELEASE 用) など) をインストールすると、以下のような man コマンド閲覧、キーワード検索が コンソールからできるようになります。
4.11-RELEASE-K, 5.4-RELEASE-K, 5.5-RELEASE-K, 6.0-RELEASE-K から 6.4-RELEASE-K, 7.0-RELEASE-K から 7.4-RELEASE-K, 8.0-RELEASE-K から 8.4-RELEASE-K, 9.0-RELEASE-K から 9.3-RELEASE-K, 10.0-RELEASE-K から 10.3-RELEASE-K, 11.0-RELEASE-K から 11.4-RELEASE-K, 12.0-RELEASE-K, 12.1-RELEASE-K は、 プライベート版 (小金丸が編集してまとめたもの) ですが、 より多くの翻訳したファイルが含まれています。 (5.4-RELEASE-K から 6.4-RELEASE-K, 7.0-RELEASE-K から 7.4-RELEASE-K, 8.0-RELEASE-K から 8.4-RELEASE-K, 9.0-RELEASE-K から 9.3-RELEASE-K, 10.0-RELEASE-K から 10.3-RELEASE-K, 11.0-RELEASE-K から 11.4-RELEASE-K, 12.0-RELEASE-K から 12.3-RELEASE-K, 13.0-RELEASE-K から 13.2-RELEASE-K は、全翻訳済み)
13.3-STABLE-K, 15.0-CURRENT-K は現在、作成中で日々更新されています。
Table of Contents
BTREE(3) FreeBSD ライブラリ関数マニュアル 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;
この構造体の要素は、次の通りです:
flags フラグ値は、次の値のいずれかを論理和 (or) することによって指定さ
れます:
R_DUP ツリーに重複しているキーを許可します、すなわち、挿入され
るキーが既にツリーに存在しても、挿入を許可します。
dbopen(3) に説明されるようなデフォルトの振る舞いは、新し
いキーを挿入するとき、一致しているキーを上書きするか、ま
たは R_NOOVERWRITE フラグが指定されるなら、失敗します。
R_DUP フラグは、R_NOOVERWRITE フラグによって上書きされ、
R_NOOVERWRITE フラグが指定されるなら、重複しているキーを
ツリーに挿入する試みは、失敗します。
データベースが重複しているキーを含んでいるなら、キー/デー
タのペアの検索の順序は、get ルーチンが使用されるなら、未
定義ですが、しかしながら、R_CURSOR フラグを付けで呼び出さ
れる seq ルーチンは、重複しているキーのあらゆるグループの
論理的な ``first'' (最初) を常に返します。
cachesize
メモリキャッシュの推奨されている (バイト単位の) 最大のサイズ。こ
の値は、助言のみで、アクセス方式は、失敗するのではなくより多くの
メモリを割り付けます。すべての検索は、ツリーのルートページを調査
するので、最も最近使用されたページをキャッシュすることは、アクセ
ス時間を大幅に改良します。さらに、物理的な書き込みは、できるだけ
遅延されるので、適度なキャッシュは、I/O 操作の数をかなり減少する
ことができます。明らかに、キャッシュを使用することは、ツリーが修
正されているる間にシステムがクラッシュするなら、データを破損する
か、または失う可能性を増大させます (が、増大するだけです)。
cachesize が 0 (サイズは指定されない) であるなら、デフォルトの
キャッシュが使用されます。
maxkeypage
あらゆる単一のページに格納されるキーの最大数。現在、実装されてい
ません。
minkeypage
あらゆる単一のページに格納されるキーの最小数。この値は、キーが
オーバフローページに格納されるかを決定するために使用されます、す
なわち、キーまたはデータ項目が minkeypage 値によって分割された
ページサイズより長いなら、ページ自体の代わりにオーバフローページ
に格納されます。minkeypage が、0 (キーの最小数が指定されない) で
あるなら、2 の値が使用されます。
psize ページサイズは、ツリーのノードのために使用されるページの (バイト
単位の) サイズです。最小のページサイズは、512 バイトであり、最大
のページサイズは、64K です。psize が 0 (ページサイズが指定されな
い) であるなら、ページサイズは、基本的なファイルシステム I/O ブ
ロックサイズに基づいて選択されます。
compare
compare は、キー比較関数です。最初のキー引数が 2 番目のキー引数よ
りそれぞれ、小さい、等しい、大きいと見なされるなら、0 より小さ
い、等しい、大きい整数を返さなければなりません。同じ比較関数は、
それがオープンされるたびに、与えられたツリーで使用されなければな
りません。compare が NULL (比較関数が指定されない) であるなら、
キーは、より短いキーは、より長いキーより小さいと見なされて、字句
解析的に比較されます。
prefix prefix 要素は、接頭辞の比較関数です。指定されるなら、このルーチン
は、最初のキー引数より大きいと判断するために必要な 2 番目のキー引
数のバイトの数を返さなければなりません。キーが等しいなら、キーの
長さが、返されるべきです。このルーチンの有用性は、まさにデータに
依存しますが、いくつかのデータセットにおいて、著しく減少されたツ
リーのサイズと検索時間をもたらすことができることに注意してくださ
い。prefix が、NULL (接頭辞関数が指定されない) であり、そして比較
関数がが指定されないなら、デフォルトの字句解析比較ルーチンが、使
用されます。prefix が NULL であり、比較ルーチンが指定されるなら、
接頭辞の比較は、行われません。
lorder 格納されたデータベースのメタデータの整数のためのバイト順序。数値
は、整数として順序を表すべきです。例えば、ビッグエンディアンの順
序は、数値 4,321 となります。lorder が、0 (順序が指定されない) で
あるなら、現在のホスト順序が使用されます。
ファイルが既に存在し (そして、O_TRUNC フラグが指定されない) なら、flags,
lorder と psize 引数のために指定された値は、ツリーが作成されたとき、使用
された値を支持して、無視されます。
ツリーの前方シーケンシャルなスキャンは、最小のキーから最大のキーです。
ツリーからキー/データのペアを削除することによって解放された空間は、決して
再要求されませんが、通常、再利用のために利用可能にされます。これは、btree
の記憶域構造は、成長のみであることを意味しています。唯一の解決策は、過度
な削除を避けること、または既存のもののスキャンから定期的に新しいツリーを
作成することです。
btree の検索、挿入と削除は、すべて O lg base N で完了します、ここで base
は、平均の fill ファクタです。しばしば、順序付けられたデータを btree に挿
入することは、最低の fill ファクタの結果となります。この実装は、最良の場
合に、順序付けられた挿入を行うために修正され、通常のページ fill ファクタ
より良い結果となります。
エラー
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.
バグ
ビッグエンディアンとリトルエンディアンのバイト順序のみサポートされていま
す。
FreeBSD 11.2 August 18, 1994 FreeBSD 11.2