[apple/libc.git] / db / man / FreeBSD / btree.3

.\" Copyright (c) 1990, 1993
.\"	The Regents of the University of California.  All rights reserved.
.\"
.\" Redistribution and use in source and binary forms, with or without
.\" modification, are permitted provided that the following conditions
.\" are met:
.\" 1. Redistributions of source code must retain the above copyright
.\"    notice, this list of conditions and the following disclaimer.
.\" 2. Redistributions in binary form must reproduce the above copyright
.\"    notice, this list of conditions and the following disclaimer in the
.\"    documentation and/or other materials provided with the distribution.
.\" 4. Neither the name of the University nor the names of its contributors
.\"    may be used to endorse or promote products derived from this software
.\"    without specific prior written permission.
.\"
.\" THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
.\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
.\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
.\" ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
.\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
.\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
.\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
.\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
.\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
.\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
.\" SUCH DAMAGE.
.\"
.\"	@(#)btree.3	8.4 (Berkeley) 8/18/94
.\" $FreeBSD: src/lib/libc/db/man/btree.3,v 1.9 2007/01/09 00:27:51 imp Exp $
.\"
.Dd August 18, 1994
.Dt BTREE 3
.Os
.Sh NAME
.Nm btree
.Nd "btree database access method"
.Sh SYNOPSIS
.In sys/types.h
.In db.h
.Sh DESCRIPTION
The routine
.Fn dbopen
is the library interface to database files.
One of the supported file formats is
.Nm
files.
The general description of the database access methods is in
.Xr dbopen 3 ,
this manual page describes only the
.Nm
specific information.
.Pp
The
.Nm
data structure is a sorted, balanced tree structure storing
associated key/data pairs.
.Pp
The
.Nm
access method specific data structure provided to
.Fn dbopen
is defined in the
.In db.h
include file as follows:
.Bd -literal
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;
.Ed
.Pp
The elements of this structure are as follows:
.Bl -tag -width indent
.It Va flags
The flag value is specified by
.Em or Ns 'ing
any of the following values:
.Bl -tag -width indent
.It Dv 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
.Xr dbopen 3 ,
is to overwrite a matching key when inserting a new key or to fail if
the
.Dv R_NOOVERWRITE
flag is specified.
The
.Dv R_DUP
flag is overridden by the
.Dv R_NOOVERWRITE
flag, and if the
.Dv R_NOOVERWRITE
flag is specified, attempts to insert duplicate keys into
the tree will fail.
.Pp
If the database contains duplicate keys, the order of retrieval of
key/data pairs is undefined if the
.Va get
routine is used, however,
.Va seq
routine calls with the
.Dv R_CURSOR
flag set will always return the logical
.Dq first
of any group of duplicate keys.
.El
.It Va cachesize
A suggested maximum size (in bytes) of the memory cache.
This value is
.Em 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
.Va cachesize
is 0 (no size is specified) a default cache is used.
.It Va 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
.\" .Nm
.\" data structure works,
.\" .Va maxkeypage
.\" must always be greater than or equal to 2.
.\" If
.\" .Va 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).
.It Va 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, 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
.Va minkeypage
is 0 (no minimum number of keys is specified) a value of 2 is used.
.It Va 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
.Va psize
is 0 (no page size is specified) a page size is chosen based on the
underlying file system I/O block size.
.It Va 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
.Va compare
is
.Dv NULL
(no comparison function is specified), the keys are compared
lexically, with shorter keys considered less than longer keys.
.It Va prefix
The
.Va prefix
element
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
.Va prefix
is
.Dv NULL
(no prefix function is specified),
.Em and
no comparison function is specified, a default lexical comparison routine
is used.
If
.Va prefix
is
.Dv NULL
and a comparison routine is specified, no prefix comparison is
done.
.It Va 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
.Va lorder
is 0 (no order is specified) the current host order is used.
.El
.Pp
If the file already exists (and the
.Dv O_TRUNC
flag is not specified), the
values specified for the
.Va flags , lorder
and
.Va psize
arguments
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
.Nm
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
.Nm
will all complete in
O lg base N where base is the average fill factor.
Often, inserting ordered data into
.Nm Ns s
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
.Nm
access method routines may fail and set
.Va errno
for any of the errors specified for the library routine
.Xr dbopen 3 .
.Sh SEE ALSO
.Xr dbopen 3 ,
.Xr hash 3 ,
.Xr mpool 3 ,
.Xr recno 3
.Rs
.%T "The Ubiquitous B-tree"
.%A Douglas Comer
.%J "ACM Comput. Surv. 11"
.%N 2
.%D June 1979
.%P 121-138
.Re
.Rs
.%A Bayer
.%A Unterauer
.%T "Prefix B-trees"
.%J "ACM Transactions on Database Systems"
.%N 1
.%V Vol. 2
.%D March 1977
.%P 11-26
.Re
.Rs
.%B "The Art of Computer Programming Vol. 3: Sorting and Searching"
.%A D. E. Knuth
.%D 1968
.%P 471-480
.Re
.Sh BUGS
Only big and little endian byte order is supported.
Commit	Line	Data
5b2abdfb A	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.
5b2abdfb A	12	.\" 4. Neither the name of the University nor the names of its contributors
	13	.\" may be used to endorse or promote products derived from this software
	14	.\" without specific prior written permission.
	15	.\"
	16	.\" THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
	17	.\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
	18	.\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
	19	.\" ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
	20	.\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
	21	.\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
	22	.\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
	23	.\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
	24	.\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
	25	.\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
	26	.\" SUCH DAMAGE.
	27	.\"
	28	.\" @(#)btree.3 8.4 (Berkeley) 8/18/94
1f2f436a	29	.\" $FreeBSD: src/lib/libc/db/man/btree.3,v 1.9 2007/01/09 00:27:51 imp Exp $
5b2abdfb A	30	.\"
	31	.Dd August 18, 1994
	32	.Dt BTREE 3
	33	.Os
	34	.Sh NAME
	35	.Nm btree
	36	.Nd "btree database access method"
	37	.Sh SYNOPSIS
	38	.In sys/types.h
	39	.In db.h
	40	.Sh DESCRIPTION
	41	The routine
	42	.Fn dbopen
	43	is the library interface to database files.
	44	One of the supported file formats is
	45	.Nm
	46	files.
	47	The general description of the database access methods is in
	48	.Xr dbopen 3 ,
	49	this manual page describes only the
	50	.Nm
	51	specific information.
	52	.Pp
	53	The
	54	.Nm
	55	data structure is a sorted, balanced tree structure storing
	56	associated key/data pairs.
	57	.Pp
	58	The
	59	.Nm
	60	access method specific data structure provided to
	61	.Fn dbopen
	62	is defined in the
3d9156a7	63	.In db.h
5b2abdfb A	64	include file as follows:
	65	.Bd -literal
	66	typedef struct {
	67	u_long flags;
	68	u_int cachesize;
	69	int maxkeypage;
	70	int minkeypage;
	71	u_int psize;
	72	int (compare)(const DBT key1, const DBT *key2);
	73	size_t (prefix)(const DBT key1, const DBT *key2);
	74	int lorder;
	75	} BTREEINFO;
	76	.Ed
	77	.Pp
	78	The elements of this structure are as follows:
	79	.Bl -tag -width indent
	80	.It Va flags
	81	The flag value is specified by
	82	.Em or Ns 'ing
	83	any of the following values:
	84	.Bl -tag -width indent
	85	.It Dv R_DUP
3d9156a7	86	Permit duplicate keys in the tree, i.e., permit insertion if the key to be
5b2abdfb A	87	inserted already exists in the tree.
	88	The default behavior, as described in
	89	.Xr dbopen 3 ,
	90	is to overwrite a matching key when inserting a new key or to fail if
	91	the
	92	.Dv R_NOOVERWRITE
	93	flag is specified.
	94	The
	95	.Dv R_DUP
	96	flag is overridden by the
	97	.Dv R_NOOVERWRITE
	98	flag, and if the
	99	.Dv R_NOOVERWRITE
	100	flag is specified, attempts to insert duplicate keys into
	101	the tree will fail.
	102	.Pp
	103	If the database contains duplicate keys, the order of retrieval of
	104	key/data pairs is undefined if the
	105	.Va get
	106	routine is used, however,
	107	.Va seq
	108	routine calls with the
	109	.Dv R_CURSOR
	110	flag set will always return the logical
	111	.Dq first
	112	of any group of duplicate keys.
	113	.El
	114	.It Va cachesize
	115	A suggested maximum size (in bytes) of the memory cache.
	116	This value is
	117	.Em only
	118	advisory, and the access method will allocate more memory rather than fail.
	119	Since every search examines the root page of the tree, caching the most
	120	recently used pages substantially improves access time.
	121	In addition, physical writes are delayed as long as possible, so a moderate
	122	cache can reduce the number of I/O operations significantly.
	123	Obviously, using a cache increases (but only increases) the likelihood of
	124	corruption or lost data if the system crashes while a tree is being modified.
	125	If
	126	.Va cachesize
	127	is 0 (no size is specified) a default cache is used.
	128	.It Va maxkeypage
	129	The maximum number of keys which will be stored on any single page.
	130	Not currently implemented.
	131	.\" The maximum number of keys which will be stored on any single page.
	132	.\" Because of the way the
	133	.\" .Nm
	134	.\" data structure works,
	135	.\" .Va maxkeypage
	136	.\" must always be greater than or equal to 2.
	137	.\" If
	138	.\" .Va maxkeypage
	139	.\" is 0 (no maximum number of keys is specified) the page fill factor is
	140	.\" made as large as possible (which is almost invariably what is wanted).
	141	.It Va minkeypage
	142	The minimum number of keys which will be stored on any single page.
	143	This value is used to determine which keys will be stored on overflow
3d9156a7	144	pages, i.e., if a key or data item is longer than the pagesize divided
5b2abdfb A	145	by the minkeypage value, it will be stored on overflow pages instead
	146	of in the page itself.
	147	If
	148	.Va minkeypage
	149	is 0 (no minimum number of keys is specified) a value of 2 is used.
	150	.It Va psize
	151	Page size is the size (in bytes) of the pages used for nodes in the tree.
	152	The minimum page size is 512 bytes and the maximum page size is 64K.
	153	If
	154	.Va psize
	155	is 0 (no page size is specified) a page size is chosen based on the
	156	underlying file system I/O block size.
	157	.It Va compare
	158	Compare is the key comparison function.
	159	It must return an integer less than, equal to, or greater than zero if the
	160	first key argument is considered to be respectively less than, equal to,
	161	or greater than the second key argument.
	162	The same comparison function must be used on a given tree every time it
	163	is opened.
	164	If
	165	.Va compare
	166	is
	167	.Dv NULL
	168	(no comparison function is specified), the keys are compared
	169	lexically, with shorter keys considered less than longer keys.
	170	.It Va prefix
59e0d9fe A	171	The
	172	.Va prefix
	173	element
5b2abdfb A	174	is the prefix comparison function.
	175	If specified, this routine must return the number of bytes of the second key
	176	argument which are necessary to determine that it is greater than the first
	177	key argument.
	178	If the keys are equal, the key length should be returned.
	179	Note, the usefulness of this routine is very data dependent, but, in some
	180	data sets can produce significantly reduced tree sizes and search times.
	181	If
	182	.Va prefix
	183	is
	184	.Dv NULL
	185	(no prefix function is specified),
	186	.Em and
	187	no comparison function is specified, a default lexical comparison routine
	188	is used.
	189	If
	190	.Va prefix
	191	is
	192	.Dv NULL
	193	and a comparison routine is specified, no prefix comparison is
	194	done.
	195	.It Va lorder
	196	The byte order for integers in the stored database metadata.
	197	The number should represent the order as an integer; for example,
	198	big endian order would be the number 4,321.
	199	If
	200	.Va lorder
	201	is 0 (no order is specified) the current host order is used.
	202	.El
	203	.Pp
	204	If the file already exists (and the
	205	.Dv O_TRUNC
	206	flag is not specified), the
59e0d9fe	207	values specified for the
5b2abdfb A	208	.Va flags , lorder
	209	and
	210	.Va psize
59e0d9fe	211	arguments
5b2abdfb A	212	are ignored
	213	in favor of the values used when the tree was created.
	214	.Pp
	215	Forward sequential scans of a tree are from the least key to the greatest.
	216	.Pp
	217	Space freed up by deleting key/data pairs from the tree is never reclaimed,
	218	although it is normally made available for reuse.
	219	This means that the
	220	.Nm
	221	storage structure is grow-only.
	222	The only solutions are to avoid excessive deletions, or to create a fresh
	223	tree periodically from a scan of an existing one.
	224	.Pp
	225	Searches, insertions, and deletions in a
	226	.Nm
	227	will all complete in
	228	O lg base N where base is the average fill factor.
	229	Often, inserting ordered data into
	230	.Nm Ns s
	231	results in a low fill factor.
	232	This implementation has been modified to make ordered insertion the best
	233	case, resulting in a much better than normal page fill factor.
	234	.Sh ERRORS
	235	The
	236	.Nm
	237	access method routines may fail and set
	238	.Va errno
	239	for any of the errors specified for the library routine
	240	.Xr dbopen 3 .
	241	.Sh SEE ALSO
	242	.Xr dbopen 3 ,
	243	.Xr hash 3 ,
	244	.Xr mpool 3 ,
	245	.Xr recno 3
	246	.Rs
	247	.%T "The Ubiquitous B-tree"
	248	.%A Douglas Comer
	249	.%J "ACM Comput. Surv. 11"
	250	.%N 2
	251	.%D June 1979
	252	.%P 121-138
	253	.Re
	254	.Rs
	255	.%A Bayer
	256	.%A Unterauer
	257	.%T "Prefix B-trees"
	258	.%J "ACM Transactions on Database Systems"
	259	.%N 1
	260	.%V Vol. 2
	261	.%D March 1977
	262	.%P 11-26
	263	.Re
	264	.Rs
	265	.%B "The Art of Computer Programming Vol. 3: Sorting and Searching"
	266	.%A D. E. Knuth
	267	.%D 1968
	268	.%P 471-480
	269	.Re
	270	.Sh BUGS
	271	Only big and little endian byte order is supported.