draft/man3/btree.3

   1 .\" Copyright (c) 1990, 1993
   2 .\"     The Regents of the University of California.  All rights reserved.
   3 .\"
   4 .\" Redistribution and use in source and binary forms, with or without
   5 .\" modification, are permitted provided that the following conditions
   6 .\" are met:
   7 .\" 1. Redistributions of source code must retain the above copyright
   8 .\"    notice, this list of conditions and the following disclaimer.
   9 .\" 2. Redistributions in binary form must reproduce the above copyright
  10 .\"    notice, this list of conditions and the following disclaimer in the
  11 .\"    documentation and/or other materials provided with the distribution.
  12 .\" 3. All advertising materials mentioning features or use of this software
  13 .\"    must display the following acknowledgement:
  14 .\"     This product includes software developed by the University of
  15 .\"     California, Berkeley and its contributors.
  16 .\" 4. Neither the name of the University nor the names of its contributors
  17 .\"    may be used to endorse or promote products derived from this software
  18 .\"    without specific prior written permission.
  19 .\"
  20 .\" THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  21 .\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  22 .\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  23 .\" ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  24 .\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  25 .\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  26 .\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  27 .\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  28 .\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  29 .\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  30 .\" SUCH DAMAGE.
  31 .\"
  32 .\"     @(#)btree.3     8.4 (Berkeley) 8/18/94
  33 .\"
  34 .\" Japanese Version Copyright (c) 1999 Shouichi Saito
  35 .\"     all rights reserved.
  36 .\" Translated Mon Jul 26 21:43:11 JST 1999
  37 .\"     by Shouichi Saito <ss236rx@ymg.urban.ne.jp>
  38 .\" Proofed Mon Aug 16 1999 by NAKANO Takeo <nakano@apm.seikei.ac.jp>
  39 .\"
  40 .\"WORD:        access method           アクセスメソッド
  41 .\"WORD:        prefix (comparison)     前置比較
  42 .TH BTREE 3 1994-08-18 "" "Linux Programmer's Manual"
  43 .UC 7
  44 .SH 名前
  45 .\"O btree \- btree database access method
  46 btree \- btree データベースへのアクセスメソッド
  47 .SH 書式
  48 .nf
  49 .ft B
  50 #include <sys/types.h>
  51 #include <db.h>
  52 .ft R
  53 .fi
  54 .SH 説明
  55 .\"O The routine
  56 .\"O .BR dbopen (3)
  57 .\"O is the library interface to database files.
  58 ルーチン
  59 .BR dbopen (3)
  60 はデータベースファイルに対するライブラリインターフェースである。
  61 .\"O One of the supported file formats is btree files.
  62 .\"O The general description of the database access methods is in
  63 .\"O .BR dbopen (3),
  64 .\"O this manual page describes only the btree specific information.
  65 サポートされているファイルフォーマットのひとつに btree ファイルがある。
  66 データベースへのアクセスメソッドに関する一般的な記述は
  67 .BR dbopen (3)
  68 に書かれている。
  69 このマニュアルページでは btree 特有の情報についてのみ記述する。
  70 .PP
  71 .\"O The btree data structure is a sorted, balanced tree structure storing
  72 .\"O associated key/data pairs.
  73 btree データ構造では、ソートされたバランスツリー構造に
  74 互いに関連づけられたキー/データ対を格納している。
  75 .PP
  76 .\"O The btree access method specific data structure provided to
  77 .\"O .BR dbopen (3)
  78 .\"O is defined in the
  79 .\"O .I <db.h>
  80 .\"O include file as follows:
  81 .BR dbopen (3)
  82 に渡される btree アクセスメソッドに特有のデータ構造体は、
  83 .I <db.h>
  84 インクルードファイルで次のように定義されている。
  85 .sp
  86 .in +4n
  87 .nf
  88
  89 typedef struct {
  90     unsigned long flags;
  91     unsigned int  cachesize;
  92     int           maxkeypage;
  93     int           minkeypage;
  94     unsigned int  psize;
  95     int         (*compare)(const DBT *key1, const DBT *key2);
  96     size_t      (*prefix)(const DBT *key1, const DBT *key2);
  97     int           lorder;
  98 } BTREEINFO;
  99 .fi
 100 .in
 101 .sp
 102 .\"O The elements of this structure are as follows:
 103 この構造体の要素を以下に示す。
 104 .TP
 105 .I flags
 106 .\"O The flag value is specified by ORing any of the following values:
 107 .I flags
 108 の値は以下の値のいずれかか、これらの論理和で指定される。
 109 .RS
 110 .TP
 111 .B R_DUP
 112 .\"O Permit duplicate keys in the tree, that is,
 113 .\"O permit insertion if the key to be
 114 .\"O inserted already exists in the tree.
 115 .\"O The default behavior, as described in
 116 .\"O .BR dbopen (3),
 117 .\"O is to overwrite a matching key when inserting a new key or to fail if
 118 .\"O the
 119 .\"O .B R_NOOVERWRITE
 120 .\"O flag is specified.
 121 ツリーの中にキーの重複を許す。すなわちツリーの中に挿入されようとしている
 122 キーが既に存在していても、その挿入を許可する。デフォルトの動作は
 123 .BR dbopen (3)
 124 に記述されているように、新しいキーが挿入されると一致したキーを上書きする。
 125 あるいは
 126 .B R_NOOVERWRITE
 127 フラグが指定されていると挿入に失敗する。
 128 .\"O The
 129 .\"O .B R_DUP
 130 .\"O flag is overridden by the
 131 .\"O .B R_NOOVERWRITE
 132 .\"O flag, and if the
 133 .\"O .B R_NOOVERWRITE
 134 .\"O flag is specified, attempts to insert duplicate keys into
 135 .\"O the tree will fail.
 136 .B R_DUP
 137 フラグは
 138 .B R_NOOVERWRITE
 139 フラグによって上書きされる。つまり
 140 .B R_NOOVERWRITE
 141 フラグが指定された場合、ツリーに複製キーを挿入しようとすると失敗する。
 142 .IP
 143 .\"O If the database contains duplicate keys, the order of retrieval of
 144 .\"O key/data pairs is undefined if the
 145 .\"O .I get
 146 .\"O routine is used, however,
 147 .\"O .I seq
 148 .\"O routine calls with the
 149 .\"O .B R_CURSOR
 150 .\"O flag set will always return the logical
 151 .\"O "first" of any group of duplicate keys.
 152 データベースにキーの重複があると、
 153 .I get
 154 ルーチンを使った場合のキー/データ対の取得順は未定義である。それに対し、
 155 .B R_CURSOR
 156 フラグをセットして
 157 .I seq
 158 ルーチンを使うと、複製キーのグループの中の
 159 論理的に「最初」のキーを必ず返してくる。
 160 .RE
 161 .TP
 162 .I cachesize
 163 .\"O A suggested maximum size (in bytes) of the memory cache.
 164 想定されるメモリキャッシュの最大サイズ (バイト単位)。
 165 .\"O This value is
 166 .\"O .I only
 167 .\"O advisory, and the access method will allocate more memory rather than fail.
 168 .\"O Since every search examines the root page of the tree, caching the most
 169 .\"O recently used pages substantially improves access time.
 170 この値は
 171 .I あくまで
 172 参考であり、アクセスメソッドはこの値を越えたメモリの
 173 割り当てに成功することもある。
 174 .\"O In addition, physical writes are delayed as long as possible, so a moderate
 175 .\"O cache can reduce the number of I/O operations significantly.
 176 加えて、物理的な書き込みは可能な限り遅延されるので、
 177 キャッシュの大きさを適度にしておけば I/O 操作の回数をかなり減らすこと
 178 ができる。
 179 .\"O Obviously, using a cache increases (but only increases) the likelihood of
 180 .\"O corruption or lost data if the system crashes while a tree is being modified.
 181 あきらかにキャッシュを使うと、ツリーが変更されている途中で
 182 システムがクラッシュした場合のデータ破壊やデータロストの可能性は
 183 増える (まあでもそれだけのこと)。
 184 .\"O If
 185 .I cachesize
 186 .\"O is 0 (no size is specified) a default cache is used.
 187 が 0 (サイズが指定されていない) の場合、デフォルトのキャッシュが使われる。
 188 .TP
 189 .I maxkeypage
 190 .\"O The maximum number of keys which will be stored on any single page.
 191 .\"O Not currently implemented.
 192 単一ページに納められる最大キー数である。現在実装されていない。
 193 .\" The maximum number of keys which will be stored on any single page.
 194 .\" Because of the way the btree data structure works,
 195 .\" .I maxkeypage
 196 .\" must always be greater than or equal to 2.
 197 .\" If
 198 .\" .I maxkeypage
 199 .\" is 0 (no maximum number of keys is specified) the page fill factor is
 200 .\" made as large as possible (which is almost invariably what is wanted).
 201 .TP
 202 .I minkeypage
 203 .\"O The minimum number of keys which will be stored on any single page.
 204 .\"O This value is used to determine which keys will be stored on overflow
 205 .\"O pages, that is, if a key or data item is longer than the pagesize divided
 206 .\"O by the minkeypage value, it will be stored on overflow pages instead
 207 .\"O of in the page itself.
 208 単一ページに納められる最小キー数である。この値は、どのキーを
 209 オーバーフローページ
 210 に納めるか決めるのに使われる。すなわちキーまたはデータが
 211 minkeypage の値で分割されたページサイズより大きい時、そのページに納め
 212 る代わりにオーバーフローページに納めるということである。
 213 .\"O If
 214 .I minkeypage
 215 .\"O is 0 (no minimum number of keys is specified) a value of 2 is used.
 216 が 0 (キーの最小値が指定されていない) の場合、値として 2 が使われる。
 217 .TP
 218 .I psize
 219 .\"O Page size is the size (in bytes) of the pages used for nodes in the tree.
 220 .\"O The minimum page size is 512 bytes and the maximum page size is 64K.
 221 ツリーの中のノードに使われるページサイズ (バイト単位)。
 222 最小値は 512 バイトで、最大値は 64K である。
 223 .\"O If
 224 .I psize
 225 .\"O is 0 (no page size is specified) a page size is chosen based on the
 226 .\"O underlying file system I/O block size.
 227 が 0 (ページサイズが指定されていない) の場合、
 228 ファイルシステムの I/O ブロックサイズに基づいて決められる。
 229 .TP
 230 .I compare
 231 .\"O Compare is the key comparison function.
 232 .I compare
 233 はキーの比較関数である。
 234 .\"O It must return an integer less than, equal to, or greater than zero if the
 235 .\"O first key argument is considered to be respectively less than, equal to,
 236 .\"O or greater than the second key argument.
 237 最初のキー引数に対し、二番目のキー引数が大きい場合には正の整数を、
 238 同じ場合にはゼロを、小さい場合には負の整数を返す。
 239 .\"O The same comparison function must be used on a given tree every time it
 240 .\"O is opened.
 241 ツリーを開く際には、常に同じ比較関数が使われなければならない。
 242 .\"O If
 243 .I compare
 244 .\"O is NULL (no comparison function is specified), the keys are compared
 245 .\"O lexically, with shorter keys considered less than longer keys.
 246 が NULL (比較関数が指定されていない) の場合、
 247 辞書的に比較される。短いキーは長いキーより小さいことになる。
 248 .TP
 249 .I prefix
 250 .\"O Prefix is the prefix comparison function.
 251 .I prefix
 252 は前置比較関数である。
 253 .\"O If specified, this routine must return the number of bytes of the second key
 254 .\"O argument which are necessary to determine that it is greater than the first
 255 .\"O key argument.
 256 このルーチンは (指定された場合には)、二番目のキー引数の
 257 バイト数を返さなくてはならない。これは二番目のキー引数が
 258 一番目のキー引数より大きいかどうか決めるのに必要である。
 259 .\"NAKANO ちょっと意味わからん...
 260 .\"O If the keys are equal, the key length should be returned.
 261 .\"O Note, the usefulness of this routine is very data-dependent, but, in some
 262 .\"O data sets can produce significantly reduced tree sizes and search times.
 263 キーが同じ場合、キーの長さが返る。このルーチンが有用かどうかは、
 264 データに強く依存する。しかしデータセットによっては、明らかにツリー
 265 のサイズと検索時間を減らしてくれる。
 266 .\"O If
 267 .\"O .I prefix
 268 .\"O is NULL (no prefix function is specified),
 269 .\"O .I and
 270 .\"O no comparison function is specified, a default lexical comparison routine
 271 .\"O is used.
 272 .I prefix
 273 が NULL (prefix 関数が指定されていない) で、
 274 .I かつ
 275 比較関数が指定されていないと、デフォルトの辞書比較ルーチンが使われる。
 276 .\"O If
 277 .\"O .I prefix
 278 .\"O is NULL and a comparison routine is specified, no prefix comparison is
 279 .\"O done.
 280 .I prefix
 281 が NULL で比較関数が指定されている場合は、前置比較は行われない。
 282 .TP
 283 .I lorder
 284 .\"O The byte order for integers in the stored database metadata.
 285 .\"O The number should represent the order as an integer; for example,
 286 .\"O big endian order would be the number 4,321.
 287 .\"O If
 288 .\"O .I lorder
 289 .\"O is 0 (no order is specified) the current host order is used.
 290 データベースに格納されているメタデータの整数値のバイトオーダー。
 291 この数字は、順序を整数で表したものである。
 292 例えばビッグエンディアンなら、この数値は 4,321 となる。
 293 .I lorder
 294 が 0 (指定されていない) の場合、現在のホスト
 295 で使われているバイトオーダーが使われる。
 296 .PP
 297 .\"O If the file already exists (and the
 298 .\"O .B O_TRUNC
 299 .\"O flag is not specified), the
 300 .\"O values specified for the arguments
 301 .\"O .IR flags ,
 302 .\"O .I lorder
 303 .\"O and
 304 .\"O .I psize
 305 .\"O are ignored
 306 .\"O in favor of the values used when the tree was created.
 307 ファイルが既に存在している (または
 308 .B O_TRUCT
 309 フラグが指定されていない) と、
 310 引き数
 311 .IR flag ,
 312 .IR lorder ,
 313 .I psize
 314 に指定された値は無視され、
 315 ツリーが作られた時に使った値が用いられる。
 316 .PP
 317 .\"O Forward sequential scans of a tree are from the least key to the greatest.
 318 ツリーの前方順検索は、最小キーから最大キーに向かって行われる。
 319 .PP
 320 .\"O Space freed up by deleting key/data pairs from the tree is never reclaimed,
 321 .\"O although it is normally made available for reuse.
 322 .\"O This means that the btree storage structure is grow-only.
 323 .\"O The only solutions are to avoid excessive deletions, or to create a fresh
 324 .\"O tree periodically from a scan of an existing one.
 325 ツリーからキー/データ対が削除されることによってできたスペースは、
 326 通常再利用できる形になっているが再利用されることは無い。
 327 つまり brtee 記憶構造は肥大する一方である。
 328 対策は過度の削除を避けるか、
 329 存在するツリーを調べて定期的に新しいツリーを作るか、だけである。
 330 .PP
 331 .\"O Searches, insertions, and deletions in a btree will all complete in
 332 .\"O O lg base N where base is the average fill factor.
 333 .\"O Often, inserting ordered data into btrees results in a low fill factor.
 334 .\"O This implementation has been modified to make ordered insertion the best
 335 .\"O case, resulting in a much better than normal page fill factor.
 336 .SH エラー
 337 .\"O The
 338 .\"O .I btree
 339 .\"O access method routines may fail and set
 340 .\"O .I errno
 341 .\"O for any of the errors specified for the library routine
 342 .\"O .BR dbopen (3).
 343 .I btree
 344 アクセスメソッドルーチンは失敗すると、ライブラリルーチン
 345 .BR dbopen (3)
 346 で定義されているエラーのいずれかを
 347 .I errno
 348 として返す。
 349 .\"O .SH BUGS
 350 .SH バグ
 351 .\"O Only big and little endian byte order is supported.
 352 バイトオーダーとしてはビッグエンディアンとリトルエンディアンのみが
 353 サポートされている。
 354 .SH 関連項目
 355 .BR dbopen (3),
 356 .BR hash (3),
 357 .BR mpool (3),
 358 .BR recno (3)
 359 .sp
 360 .IR "The Ubiquitous B-tree" ,
 361 Douglas Comer, ACM Comput. Surv. 11, 2 (June 1979), 121-138.
 362 .sp
 363 .IR "Prefix B-trees" ,
 364 Bayer and Unterauer, ACM Transactions on Database Systems, Vol. 2, 1
 365 (March 1977), 11-26.
 366 .sp
 367 .IR "The Art of Computer Programming Vol. 3: Sorting and Searching" ,
 368 D.E. Knuth, 1968, pp 471-480.