Adding upstream version 6.05.01.upstream/6.05.01

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

1 files changed, 229 insertions, 0 deletions

diff --git a/man3/btree.3 b/man3/btree.3
new file mode 100644
index 0000000..dfa8f4e
--- /dev/null
+++ b/man3/btree.3
@@ -0,0 +1,229 @@
+.\" Copyright (c) 1990, 1993
+.\"	The Regents of the University of California.  All rights reserved.
+.\"
+.\" SPDX-License-Identifier: BSD-4-Clause-UC
+.\"
+.\"	@(#)btree.3	8.4 (Berkeley) 8/18/94
+.\"
+.TH btree 3 2022-12-04 "Linux man-pages 6.05.01"
+.\".UC 7
+.SH NAME
+btree \- btree database access method
+.SH LIBRARY
+Standard C library
+.RI ( libc ", " \-lc )
+.SH SYNOPSIS
+.nf
+.ft B
+#include <sys/types.h>
+#include <db.h>
+.ft R
+.fi
+.SH DESCRIPTION
+.IR "Note well" :
+This page documents interfaces provided up until glibc 2.1.
+Since glibc 2.2, glibc no longer provides these interfaces.
+Probably, you are looking for the APIs provided by the
+.I libdb
+library instead.
+.PP
+The routine
+.BR dbopen (3)
+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
+.BR dbopen (3),
+this manual page describes only the btree-specific information.
+.PP
+The btree data structure is a sorted, balanced tree structure storing
+associated key/data pairs.
+.PP
+The btree access-method-specific data structure provided to
+.BR dbopen (3)
+is defined in the
+.I <db.h>
+include file as follows:
+.PP
+.in +4n
+.EX
+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;
+.EE
+.in
+.PP
+The elements of this structure are as follows:
+.TP
+.I flags
+The flag value is specified by ORing any of the following values:
+.RS
+.TP
+.B R_DUP
+Permit duplicate keys in the tree, that is,
+permit insertion if the key to be
+inserted already exists in the tree.
+The default behavior, as described in
+.BR dbopen (3),
+is to overwrite a matching key when inserting a new key or to fail if
+the
+.B R_NOOVERWRITE
+flag is specified.
+The
+.B R_DUP
+flag is overridden by the
+.B R_NOOVERWRITE
+flag, and if the
+.B R_NOOVERWRITE
+flag is specified, attempts to insert duplicate keys into
+the tree will fail.
+.IP
+If the database contains duplicate keys, the order of retrieval of
+key/data pairs is undefined if the
+.I get
+routine is used, however,
+.I seq
+routine calls with the
+.B R_CURSOR
+flag set will always return the logical
+"first" of any group of duplicate keys.
+.RE
+.TP
+.I cachesize
+A suggested maximum size (in bytes) of the memory cache.
+This value is
+.I 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 substantially 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
+corruption or lost data if the system crashes while a tree is being modified.
+If
+.I cachesize
+is 0 (no size is specified), a default cache is used.
+.TP
+.I maxkeypage
+The maximum number of keys which will be stored on any single page.
+Not currently implemented.
+.\" The maximum number of keys which will be stored on any single page.
+.\" Because of the way the btree data structure works,
+.\" .I maxkeypage
+.\" must always be greater than or equal to 2.
+.\" If
+.\" .I maxkeypage
+.\" is 0 (no maximum number of keys is specified), the page fill factor is
+.\" made as large as possible (which is almost invariably what is wanted).
+.TP
+.I minkeypage
+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, that is, 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
+.I minkeypage
+is 0 (no minimum number of keys is specified), a value of 2 is used.
+.TP
+.I 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 64\ KiB.
+If
+.I psize
+is 0 (no page size is specified), a page size is chosen based on the
+underlying filesystem I/O block size.
+.TP
+.I compare
+Compare is the key comparison function.
+It must return an integer 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
+.I compare
+is NULL (no comparison function is specified), the keys are compared
+lexically, with shorter keys considered less than longer keys.
+.TP
+.I prefix
+Prefix is the prefix comparison function.
+If specified, this routine must return the number of bytes of the second key
+argument 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 significantly reduced tree sizes and search times.
+If
+.I prefix
+is NULL (no prefix function is specified),
+.I and
+no comparison function is specified, a default lexical comparison routine
+is used.
+If
+.I prefix
+is NULL and a comparison routine is specified, no prefix comparison is
+done.
+.TP
+.I lorder
+The byte order for integers in the stored database metadata.
+The number should represent the order as an integer; for example,
+big endian order would be the number 4,321.
+If
+.I lorder
+is 0 (no order is specified), the current host order is used.
+.PP
+If the file already exists (and the
+.B O_TRUNC
+flag is not specified), the
+values specified for the arguments
+.IR flags ,
+.IR lorder ,
+and
+.I psize
+are ignored
+in favor of the values used when the tree was created.
+.PP
+Forward sequential scans of a tree are from the least key to the greatest.
+.PP
+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 solutions are to avoid excessive deletions, or to create a fresh
+tree periodically from a scan of an existing one.
+.PP
+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.
+.SH ERRORS
+The
+.I btree
+access method routines may fail and set
+.I errno
+for any of the errors specified for the library routine
+.BR dbopen (3).
+.SH BUGS
+Only big and little endian byte order is supported.
+.SH SEE ALSO
+.BR dbopen (3),
+.BR hash (3),
+.BR mpool (3),
+.BR recno (3)
+.PP
+.IR "The Ubiquitous B-tree" ,
+Douglas Comer, ACM Comput. Surv. 11, 2 (June 1979), 121-138.
+.PP
+.IR "Prefix B-trees" ,
+Bayer and Unterauer, ACM Transactions on Database Systems, Vol. 2, 1
+(March 1977), 11-26.
+.PP
+.IR "The Art of Computer Programming Vol. 3: Sorting and Searching" ,
+D.E. Knuth, 1968, pp 471-480.