btree man page on 4.4BSD

Man page or keyword search:  
man Server   1065 pages
apropos Keyword Search (all sections)
Output format
4.4BSD logo
[printable version]

BTREE(3)							      BTREE(3)

       btree - btree database access method

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

       The  routine dbopen is the library interface to database files.	One of
       the supported file formats is btree files.  The general description  of
       the database access methods is in dbopen(3), this manual page describes
       only the btree specific information.

       The btree data structure is a sorted, balanced tree  structure  storing
       associated key/data pairs.

       The  btree  access method specific data structure provided to dbopen is
       defined in the <db.h> include file as follows:

       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;

       The elements of this structure are as follows:

       flags  The flag value is specified by or'ing any of the following  val‐

	      R_DUP  Permit  duplicate keys in the tree, i.e. permit insertion
		     if the key to be inserted already	exists	in  the	 tree.
		     The  default  behavior,  as described in dbopen(3), is to
		     overwrite a matching key when inserting a new key	or  to
		     fail  if  the R_NOOVERWRITE flag is specified.  The R_DUP
		     flag is overridden by the R_NOOVERWRITE flag, and if  the
		     R_NOOVERWRITE  flag  is  specified,  attempts  to	insert
		     duplicate keys into the tree will fail.

		     If the database contains duplicate	 keys,	the  order  of
		     retrieval	of key/data pairs is undefined if the get rou‐
		     tine is used, however, seq routine calls with the	R_CUR‐
		     SOR  flag set will always return the logical ``first'' of
		     any group of duplicate keys.

	      A suggested maximum size (in bytes) of the memory	 cache.	  This
	      value is only advisory, and the access method will allocate more
	      memory rather than fail.	Since every search examines  the  root
	      page  of the tree, caching the most recently used pages substan‐
	      tially improves access time.  In addition, physical  writes  are
	      delayed  as long as possible, so a moderate cache can reduce the
	      number of I/O  operations	 significantly.	  Obviously,  using  a
	      cache  increases	(but only increases) the likelihood of corrup‐
	      tion or lost data if the system crashes while a  tree  is	 being
	      modified.	  If  cachesize	 is 0 (no size is specified) a default
	      cache is used.

	      The maximum number of keys which will be stored  on  any	single
	      page.  Not currently implemented.

	      The  minimum  number  of keys which will be stored on any single
	      page.  This value is used to determine which keys will be stored
	      on overflow pages, i.e. if a key or data item is longer than the
	      pagesize divided by the minkeypage value, it will be  stored  on
	      overflow	pages instead of in the page itself.  If minkeypage is
	      0 (no minimum number of keys is specified) a value of 2 is used.

       psize  Page size is the size (in bytes) of the pages used for nodes  in
	      the  tree.   The	minimum page size is 512 bytes and the maximum
	      page size is 64K.	 If psize is 0 (no page size is	 specified)  a
	      page  size  is  chosen  based  on the underlying file system I/O
	      block size.

	      Compare is the key comparison function.  It must return an inte‐
	      ger  less	 than, equal to, or greater than zero if the first key
	      argument is considered to be respectively less than,  equal  to,
	      or  greater  than	 the second key argument.  The same comparison
	      function must be used on a given tree every time it  is  opened.
	      If  compare  is  NULL (no comparison function is specified), the
	      keys are compared lexically, with shorter keys  considered  less
	      than longer keys.

       prefix Prefix  is  the  prefix comparison function.  If specified, this
	      routine must return the number of bytes of the second key	 argu‐
	      ment  which  are	necessary to determine that it is greater than
	      the first key argument.  If the keys are equal, the  key	length
	      should  be  returned.   Note,  the usefulness of this routine is
	      very data dependent, but, in some data sets can produce signifi‐
	      cantly  reduced  tree sizes and search times.  If prefix is NULL
	      (no prefix function is specified), and no comparison function is
	      specified,  a  default  lexical  comparison routine is used.  If
	      prefix is NULL and a comparison routine is specified, no	prefix
	      comparison is done.

       lorder The  byte	 order	for  integers in the stored database metadata.
	      The number should represent the order as an integer;  for	 exam‐
	      ple, big endian order would be the number 4,321.	If lorder is 0
	      (no order is specified) the current host order is used.

       If the file already exists (and the O_TRUNC flag is not specified), the
       values specified for the parameters flags, lorder and psize are ignored
       in favor of the values used when the tree was created.

       Forward sequential scans of a tree are from the least key to the great‐

       Space  freed  up	 by  deleting  key/data	 pairs	from the tree is never
       reclaimed, although it is normally  made	 available  for	 reuse.	  This
       means  that  the	 btree storage structure is grow-only.	The only solu‐
       tions are to avoid excessive deletions, or to create a fresh tree peri‐
       odically from a scan of an existing one.

       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 implemen‐
       tation has been modified to  make  ordered  insertion  the  best	 case,
       resulting in a much better than normal page fill factor.

       The  btree access method routines may fail and set errno for any of the
       errors specified for the library routine dbopen(3).

       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 Sys‐
       tems, Vol. 2, 1 (March 1977), 11-26.

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

       Only big and little endian byte order is supported.

				August 18, 1994			      BTREE(3)

List of man pages available for 4.4BSD

Copyright (c) for man pages and the logo by the respective OS vendor.

For those who want to learn more, the polarhome community provides shell access and support.

[legal] [privacy] [GNU] [policy] [cookies] [netiquette] [sponsors] [FAQ]
Polarhome, production since 1999.
Member of Polarhome portal.
Based on Fawad Halim's script.
Vote for polarhome
Free Shell Accounts :: the biggest list on the net