Provided by: manpages-ja-dev_0.5.0.0.20210215+dfsg-1_all bug

名前

       btree - 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 バイトで、最大
              値は 64K である。 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 アクセスメソッドルーチンは失敗すると、ライブラリルーチン dbopen(3)  で定義されている
       エラーのいずれかを errno として返す。

バグ

       バイトオーダーとしてはビッグエンディアンとリトルエンディアンのみが サポートされている。

関連項目

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

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

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

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

この文書について

       この  man ページは Linux man-pages プロジェクトのリリース 3.79 の一部 である。プロジェクト
       の説明とバグ報告に関する情報は http://www.kernel.org/doc/man-pages/ に書かれている。

                                            2012-04-23                                   BTREE(3)