path: root/src/util/db2/docs/btree.3.ps

%!PS-Adobe-3.0
%%Creator: groff version 1.08
%%DocumentNeededResources: font Times-Roman
%%+ font Times-Bold
%%+ font Times-Italic
%%DocumentSuppliedResources: procset grops 1.08 0
%%Pages: 2
%%PageOrder: Ascend
%%Orientation: Portrait
%%EndComments
%%BeginProlog
%%BeginResource: procset grops 1.08 0
/setpacking where{
pop
currentpacking
true setpacking
}if
/grops 120 dict dup begin
/SC 32 def
/A/show load def
/B{0 SC 3 -1 roll widthshow}bind def
/C{0 exch ashow}bind def
/D{0 exch 0 SC 5 2 roll awidthshow}bind def
/E{0 rmoveto show}bind def
/F{0 rmoveto 0 SC 3 -1 roll widthshow}bind def
/G{0 rmoveto 0 exch ashow}bind def
/H{0 rmoveto 0 exch 0 SC 5 2 roll awidthshow}bind def
/I{0 exch rmoveto show}bind def
/J{0 exch rmoveto 0 SC 3 -1 roll widthshow}bind def
/K{0 exch rmoveto 0 exch ashow}bind def
/L{0 exch rmoveto 0 exch 0 SC 5 2 roll awidthshow}bind def
/M{rmoveto show}bind def
/N{rmoveto 0 SC 3 -1 roll widthshow}bind def
/O{rmoveto 0 exch ashow}bind def
/P{rmoveto 0 exch 0 SC 5 2 roll awidthshow}bind def
/Q{moveto show}bind def
/R{moveto 0 SC 3 -1 roll widthshow}bind def
/S{moveto 0 exch ashow}bind def
/T{moveto 0 exch 0 SC 5 2 roll awidthshow}bind def
/SF{
findfont exch
[exch dup 0 exch 0 exch neg 0 0]makefont
dup setfont
[exch/setfont cvx]cvx bind def
}bind def
/MF{
findfont
[5 2 roll
0 3 1 roll 
neg 0 0]makefont
dup setfont
[exch/setfont cvx]cvx bind def
}bind def
/level0 0 def
/RES 0 def
/PL 0 def
/LS 0 def
/PLG{
gsave newpath clippath pathbbox grestore
exch pop add exch pop
}bind def
/BP{
/level0 save def
1 setlinecap
1 setlinejoin
72 RES div dup scale
LS{
90 rotate
}{
0 PL translate
}ifelse
1 -1 scale
}bind def
/EP{
level0 restore
showpage
}bind def
/DA{
newpath arcn stroke
}bind def
/SN{
transform
.25 sub exch .25 sub exch
round .25 add exch round .25 add exch
itransform
}bind def
/DL{
SN
moveto
SN
lineto stroke
}bind def
/DC{
newpath 0 360 arc closepath
}bind def
/TM matrix def
/DE{
TM currentmatrix pop
translate scale newpath 0 0 .5 0 360 arc closepath
TM setmatrix
}bind def
/RC/rcurveto load def
/RL/rlineto load def
/ST/stroke load def
/MT/moveto load def
/CL/closepath load def
/FL{
currentgray exch setgray fill setgray
}bind def
/BL/fill load def
/LW/setlinewidth load def
/RE{
findfont
dup maxlength 1 index/FontName known not{1 add}if dict begin
{
1 index/FID ne{def}{pop pop}ifelse
}forall
/Encoding exch def
dup/FontName exch def
currentdict end definefont pop
}bind def
/DEFS 0 def
/EBEGIN{
moveto
DEFS begin
}bind def
/EEND/end load def
/CNT 0 def
/level1 0 def
/PBEGIN{
/level1 save def
translate
div 3 1 roll div exch scale
neg exch neg exch translate
0 setgray
0 setlinecap
1 setlinewidth
0 setlinejoin
10 setmiterlimit
[]0 setdash
/setstrokeadjust where{
pop
false setstrokeadjust
}if
/setoverprint where{
pop
false setoverprint
}if
newpath
/CNT countdictstack def
userdict begin
/showpage{}def
}bind def
/PEND{
clear
countdictstack CNT sub{end}repeat
level1 restore
}bind def
end def
/setpacking where{
pop
setpacking
}if
%%EndResource
%%IncludeResource: font Times-Roman
%%IncludeResource: font Times-Bold
%%IncludeResource: font Times-Italic
grops begin/DEFS 1 dict def DEFS begin/u{.001 mul}bind def end/RES 72 def/PL
792 def/LS false def/ENC0[/asciicircum/asciitilde/Scaron/Zcaron/scaron/zcaron
/Ydieresis/trademark/quotesingle/.notdef/.notdef/.notdef/.notdef/.notdef
/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef
/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/space
/exclam/quotedbl/numbersign/dollar/percent/ampersand/quoteright/parenleft
/parenright/asterisk/plus/comma/hyphen/period/slash/zero/one/two/three/four
/five/six/seven/eight/nine/colon/semicolon/less/equal/greater/question/at/A/B/C
/D/E/F/G/H/I/J/K/L/M/N/O/P/Q/R/S/T/U/V/W/X/Y/Z/bracketleft/backslash
/bracketright/circumflex/underscore/quoteleft/a/b/c/d/e/f/g/h/i/j/k/l/m/n/o/p/q
/r/s/t/u/v/w/x/y/z/braceleft/bar/braceright/tilde/.notdef/quotesinglbase
/guillemotleft/guillemotright/bullet/florin/fraction/perthousand/dagger
/daggerdbl/endash/emdash/ff/fi/fl/ffi/ffl/dotlessi/dotlessj/grave/hungarumlaut
/dotaccent/breve/caron/ring/ogonek/quotedblleft/quotedblright/oe/lslash
/quotedblbase/OE/Lslash/.notdef/exclamdown/cent/sterling/currency/yen/brokenbar
/section/dieresis/copyright/ordfeminine/guilsinglleft/logicalnot/minus
/registered/macron/degree/plusminus/twosuperior/threesuperior/acute/mu
/paragraph/periodcentered/cedilla/onesuperior/ordmasculine/guilsinglright
/onequarter/onehalf/threequarters/questiondown/Agrave/Aacute/Acircumflex/Atilde
/Adieresis/Aring/AE/Ccedilla/Egrave/Eacute/Ecircumflex/Edieresis/Igrave/Iacute
/Icircumflex/Idieresis/Eth/Ntilde/Ograve/Oacute/Ocircumflex/Otilde/Odieresis
/multiply/Oslash/Ugrave/Uacute/Ucircumflex/Udieresis/Yacute/Thorn/germandbls
/agrave/aacute/acircumflex/atilde/adieresis/aring/ae/ccedilla/egrave/eacute
/ecircumflex/edieresis/igrave/iacute/icircumflex/idieresis/eth/ntilde/ograve
/oacute/ocircumflex/otilde/odieresis/divide/oslash/ugrave/uacute/ucircumflex
/udieresis/yacute/thorn/ydieresis]def/Times-Italic@0 ENC0/Times-Italic RE
/Times-Bold@0 ENC0/Times-Bold RE/Times-Roman@0 ENC0/Times-Roman RE
%%EndProlog
%%Page: 1 1
%%BeginPageSetup
BP
%%EndPageSetup
/F0 10/Times-Roman@0 SF 132.34(BTREE\(3\) BSD)72 48 R(Programmer')2.5 E 2.5(sM)
-.55 G 132.34(anual BTREE\(3\))340.17 48 R/F1 9/Times-Bold@0 SF -.18(NA)72 84 S
(ME).18 E F0(btree \255 btree database access method)108 96 Q F1(SYNOPSIS)72
112.8 Q/F2 10/Times-Bold@0 SF(#include <sys/types.h>)108 124.8 Q(#include <db)
108 136.8 Q(.h>)-.4 E F1(DESCRIPTION)72 153.6 Q F0 .198(The routine)108 165.6 R
/F3 10/Times-Italic@0 SF(dbopen)2.698 E F0 .198(is the library interf)2.698 F
.198(ace to database \214les.)-.1 F .198
(One of the supported \214le formats is btree \214les.)5.198 F .974
(The general description of the database access methods is in)108 177.6 R F3
(dbopen)3.475 E F0 .975(\(3\), this manual page describes only).24 F
(the btree speci\214c information.)108 189.6 Q(The btree data structure is a s\
orted, balanced tree structure storing associated k)108 206.4 Q -.15(ey)-.1 G
(/data pairs.).15 E .504(The btree access method speci\214c data structure pro)
108 223.2 R .504(vided to)-.15 F F3(dbopen)3.004 E F0 .503
(is de\214ned in the <db)3.003 F .503(.h> include \214le as)-.4 F(follo)108
235.2 Q(ws:)-.25 E(typedef struct {)108 252 Q(u_long \215ags;)144 264 Q
(u_int cachesize;)144 276 Q(inde)144 288 Q(x_t psize;)-.15 E(int lorder;)144
300 Q(int mink)144 312 Q -.15(ey)-.1 G(page;).15 E
(int \(*compare\)\(const DBT *k)144 324 Q -.15(ey)-.1 G(1, const DBT *k).15 E
-.15(ey)-.1 G(2\);).15 E(int \(*pre\214x\)\(const DBT *k)144 336 Q -.15(ey)-.1
G(1, const DBT *k).15 E -.15(ey)-.1 G(2\);).15 E 2.5(}B)108 348 S(TREEINFO;)
121.97 348 Q(The elements of this structure are as follo)108 364.8 Q(ws:)-.25 E
14.61(\215ags The)108 381.6 R(\215ag v)2.5 E(alue is speci\214ed by)-.25 E F3
(or)2.5 E F0('ing an).73 E 2.5(yo)-.15 G 2.5(ft)313.2 381.6 S(he follo)321.81
381.6 Q(wing v)-.25 E(alues:)-.25 E(R_DUP)144 398.4 Q 1.296(Permit duplicate k)
180 410.4 R -.15(ey)-.1 G 3.796(si).15 G 3.796(nt)275.578 410.4 S 1.296
(he tree, i.e. permit insertion if the k)287.154 410.4 R 1.596 -.15(ey t)-.1 H
3.796(ob).15 G 3.796(ei)466.878 410.4 S 1.296(nserted already)477.894 410.4 R
-.15(ex)180 422.4 S 1.935(ists in the tree.).15 F 1.935(The def)6.935 F 1.935
(ault beha)-.1 F(vior)-.2 E 4.435(,a)-.4 G 4.435(sd)358.215 422.4 S 1.935
(escribed in)371.54 422.4 R F3(dbopen)4.435 E F0 1.935(\(3\), is to o).24 F
-.15(ve)-.15 G 1.935(rwrite a).15 F .148(matching k)180 434.4 R .448 -.15(ey w)
-.1 H .148(hen inserting a ne).15 F 2.649(wk)-.25 G .449 -.15(ey o)329.709
434.4 T 2.649(rt).15 G 2.649(of)355.407 434.4 S .149(ail if the R_NOO)366.286
434.4 R(VER)-.5 E .149(WRITE \215ag is speci-)-.55 F 5.972(\214ed. The)180
446.4 R 3.472(R_DUP \215ag is o)5.972 F -.15(ve)-.15 G 3.472
(rridden by the R_NOO).15 F(VER)-.5 E 3.471(WRITE \215ag, and if the)-.55 F
(R_NOO)180 458.4 Q(VER)-.5 E .781
(WRITE \215ag is speci\214ed, attempts to insert duplicate k)-.55 F -.15(ey)-.1
G 3.282(si).15 G .782(nto the tree will)474.604 458.4 R -.1(fa)180 470.4 S(il.)
.1 E 1.13(If the database contains duplicate k)180 487.2 R -.15(ey)-.1 G 1.129
(s, the order of retrie).15 F -.25(va)-.25 G 3.629(lo).25 G 3.629(fk)439.644
487.2 S -.15(ey)451.503 487.2 S 1.129(/data pairs is unde-).15 F .837
(\214ned if the)180 499.2 R F3 -.1(ge)3.337 G(t).1 E F0 .837
(routine is used, ho)3.337 F(we)-.25 E -.15(ve)-.25 G -.4(r,).15 G F3(seq)3.737
E F0 .838(routine calls with the R_CURSOR \215ag set)3.337 F(will al)180 511.2
Q -.1(wa)-.1 G(ys return the logical `).1 E(`\214rst')-.74 E 2.5('o)-.74 G 2.5
(fa)333.85 511.2 S .3 -.15(ny g)344.12 511.2 T(roup of duplicate k).15 E -.15
(ey)-.1 G(s.).15 E(cachesize)108 528 Q 3.056(As)144 540 S .556
(uggested maximum size \(in bytes\) of the memory cache.)158.166 540 R .555
(This v)5.556 F .555(alue is)-.25 F F2(only)3.055 E F0(advisory)3.055 E 3.055
(,a)-.65 G .555(nd the)514.725 540 R .759
(access method will allocate more memory rather than f)144 552 R 3.259
(ail. Since)-.1 F -2.15 -.25(ev e)3.259 H .76(ry search e).25 F .76
(xamines the root)-.15 F .055
(page of the tree, caching the most recently used pages substantially impro)144
564 R -.15(ve)-.15 G 2.554(sa).15 G .054(ccess time.)459.578 564 R .054
(In addi-)5.054 F .661(tion, ph)144 576 R .662(ysical writes are delayed as lo\
ng as possible, so a moderate cache can reduce the number)-.05 F .601
(of I/O operations signi\214cantly)144 588 R 5.601(.O)-.65 G -.15(bv)280.744
588 S(iously).15 E 3.101(,u)-.65 G .601(sing a cache increases \(b)324.995 588
R .6(ut only increases\) the lik)-.2 F(eli-)-.1 E .19(hood of corruption or lo\
st data if the system crashes while a tree is being modi\214ed.)144 600 R(If)
5.191 E F3(cac)2.691 E(hesize)-.15 E F0(is)2.691 E 2.5(0\()144 612 S
(no size is speci\214ed\) a def)154.83 612 Q(ault cache is used.)-.1 E 12.95
(psize P)108 628.8 R .45
(age size is the size \(in bytes\) of the pages used for nodes in the tree.)
-.15 F .449(The minimum page size is)5.449 F .442
(512 bytes and the maximum page size is 64K.)144 640.8 R(If)5.442 E F3(psize)
2.942 E F0 .442(is 0 \(no page size is speci\214ed\) a page size)2.942 F
(is chosen based on the underlying \214le system I/O block size.)144 652.8 Q
9.62(lorder The)108 669.6 R 1.597(byte order for inte)4.097 F 1.596
(gers in the stored database metadata.)-.15 F 1.596
(The number should represent the)6.596 F .688(order as an inte)144 681.6 R .689
(ger; for e)-.15 F .689(xample, big endian order w)-.15 F .689
(ould be the number 4,321.)-.1 F(If)5.689 E F3(lor)3.189 E(der)-.37 E F0 .689
(is 0 \(no)3.189 F(order is speci\214ed\) the current host order is used.)144
693.6 Q 174.135(4.4BSD June)72 732 R(4, 1993)2.5 E(1)535 732 Q EP
%%Page: 2 2
%%BeginPageSetup
BP
%%EndPageSetup
/F0 10/Times-Roman@0 SF 132.34(BTREE\(3\) BSD)72 48 R(Programmer')2.5 E 2.5(sM)
-.55 G 132.34(anual BTREE\(3\))340.17 48 R(mink)108 84 Q -.15(ey)-.1 G(page).15
E 1.423(The minimum number of k)144 96 R -.15(ey)-.1 G 3.923(sw).15 G 1.422
(hich will be stored on an)282.245 96 R 3.922(ys)-.15 G 1.422(ingle page.)
400.618 96 R 1.422(This v)6.422 F 1.422(alue is used to)-.25 F .257
(determine which k)144 108 R -.15(ey)-.1 G 2.757(sw).15 G .257
(ill be stored on o)242.001 108 R -.15(ve)-.15 G(r\215o).15 E 2.757(wp)-.25 G
.257(ages, i.e. if a k)348.006 108 R .558 -.15(ey o)-.1 H 2.758(rd).15 G .258
(ata item is longer than the)435.11 108 R 1.102(pagesize di)144 120 R 1.102
(vided by the mink)-.25 F -.15(ey)-.1 G 1.102(page v).15 F 1.102
(alue, it will be stored on o)-.25 F -.15(ve)-.15 G(r\215o).15 E 3.602(wp)-.25
G 1.102(ages instead of in the)451.164 120 R(page itself.)144 132 Q(If)5 E/F1
10/Times-Italic@0 SF(mink)2.5 E -.3(ey)-.1 G(pa).3 E -.1(ge)-.1 G F0
(is 0 \(no minimum number of k)2.6 E -.15(ey)-.1 G 2.5(si).15 G 2.5(ss)392.84
132 S(peci\214ed\) a v)403.12 132 Q(alue of 2 is used.)-.25 E(compare)108 148.8
Q .751(Compare is the k)144 160.8 R 1.051 -.15(ey c)-.1 H .751
(omparison function.).15 F .751(It must return an inte)5.751 F .752
(ger less than, equal to, or greater)-.15 F .913(than zero if the \214rst k)144
172.8 R 1.213 -.15(ey a)-.1 H -.18(rg).15 G .913
(ument is considered to be respecti).18 F -.15(ve)-.25 G .913
(ly less than, equal to, or greater).15 F .352(than the second k)144 184.8 R
.652 -.15(ey a)-.1 H -.18(rg).15 G 2.852(ument. The).18 F .353
(same comparison function must be used on a gi)2.852 F -.15(ve)-.25 G 2.853(nt)
.15 G .353(ree e)503.127 184.8 R -.15(ve)-.25 G(ry).15 E .817
(time it is opened.)144 196.8 R(If)5.817 E F1(compar)3.317 E(e)-.37 E F0 .817
(is NULL \(no comparison function is speci\214ed\), the k)3.317 F -.15(ey)-.1 G
3.316(sa).15 G .816(re com-)508.364 196.8 R(pared le)144 208.8 Q(xically)-.15 E
2.5(,w)-.65 G(ith shorter k)214.57 208.8 Q -.15(ey)-.1 G 2.5(sc).15 G
(onsidered less than longer k)282.92 208.8 Q -.15(ey)-.1 G(s.).15 E 10.17
(pre\214x Pre\214x)108 225.6 R .291(is the pre\214x comparison function.)2.791
F .292(If speci\214ed, this routine must return the number of bytes)5.291 F
.937(of the second k)144 237.6 R 1.237 -.15(ey a)-.1 H -.18(rg).15 G .937
(ument which are necessary to determine that it is greater than the \214rst k)
.18 F -.15(ey)-.1 G(ar)144 249.6 Q 3.477(gument. If)-.18 F .977(the k)3.477 F
-.15(ey)-.1 G 3.477(sa).15 G .977(re equal, the k)241.898 249.6 R 1.277 -.15
(ey l)-.1 H .978(ength should be returned.).15 F .978
(Note, the usefulness of this)5.978 F .558(routine is v)144 261.6 R .558
(ery data dependent, b)-.15 F .558
(ut, in some data sets can produce signi\214cantly reduced tree sizes)-.2 F
.354(and search times.)144 273.6 R(If)5.354 E F1(pr)2.854 E(e\214x)-.37 E F0
.354(is NULL \(no pre\214x function is speci\214ed\),)2.854 F/F2 10
/Times-Bold@0 SF(and)2.854 E F0 .354(no comparison function)2.854 F .193
(is speci\214ed, a def)144 285.6 R .193(ault le)-.1 F .193
(xical comparison routine is used.)-.15 F(If)5.192 E F1(pr)2.692 E(e\214x)-.37
E F0 .192(is NULL and a comparison rou-)2.692 F
(tine is speci\214ed, no pre\214x comparison is done.)144 297.6 Q .79
(If the \214le already e)108 314.4 R .79(xists \(and the O_TR)-.15 F .79
(UNC \215ag is not speci\214ed\), the v)-.4 F .79
(alues speci\214ed for the parameters)-.25 F
(\215ags, lorder and psize are ignored in f)108 326.4 Q -.2(avo)-.1 G 2.5(ro).2
G 2.5(ft)284.4 326.4 S(he v)293.01 326.4 Q(alues used when the tree w)-.25 E
(as created.)-.1 E -.15(Fo)108 343.2 S(rw).15 E
(ard sequential scans of a tree are from the least k)-.1 E .3 -.15(ey t)-.1 H
2.5(ot).15 G(he greatest.)348.55 343.2 Q 1.043(Space freed up by deleting k)108
360 R -.15(ey)-.1 G 1.043(/data pairs from the tree is ne).15 F -.15(ve)-.25 G
3.543(rr).15 G 1.043(eclaimed, although it is normally made)378.686 360 R -.2
(av)108 372 S 1.394(ailable for reuse.)-.05 F 1.394
(This means that the btree storage structure is gro)6.394 F(w-only)-.25 E 6.395
(.T)-.65 G 1.395(he only solutions are to)441.09 372 R -.2(avo)108 384 S(id e)
.2 E(xcessi)-.15 E .3 -.15(ve d)-.25 H
(eletions, or to create a fresh tree periodically from a scan of an e).15 E
(xisting one.)-.15 E .344(Searches, insertions, and deletions in a btree will \
all complete in O lg base N where base is the a)108 400.8 R -.15(ve)-.2 G .343
(rage \214ll).15 F -.1(fa)108 412.8 S(ctor).1 E 5.798(.O)-.55 G .799
(ften, inserting ordered data into btrees results in a lo)146.188 412.8 R 3.299
<778c>-.25 G .799(ll f)377.505 412.8 R(actor)-.1 E 5.799(.T)-.55 G .799
(his implementation has been)423.443 412.8 R(modi\214ed to mak)108 424.8 Q 2.5
(eo)-.1 G(rdered insertion the best case, resulting in a much better than norm\
al page \214ll f)185.4 424.8 Q(actor)-.1 E(.)-.55 E/F3 9/Times-Bold@0 SF
(SEE ALSO)72 441.6 Q F1(dbopen)108 453.6 Q F0(\(3\),).24 E F1(hash)2.5 E F0
(\(3\),).28 E F1(mpool)2.5 E F0(\(3\),).51 E F1 -.37(re)2.5 G(cno).37 E F0
(\(3\)).18 E F1(The Ubiquitous B-tr)108 477.6 Q(ee)-.37 E F0 2.5(,D).18 G
(ouglas Comer)209.47 477.6 Q 2.5(,A)-.4 G(CM Comput. Surv)276.72 477.6 Q 2.5
(.1)-.65 G(1, 2 \(June 1979\), 121-138.)360.25 477.6 Q F1(Pr)108 501.6 Q 1.588
(e\214x B-tr)-.37 F(ees)-.37 E F0 4.088(,B).27 G 1.587(ayer and Unterauer)
177.636 501.6 R 4.087(,A)-.4 G 1.587(CM T)270.447 501.6 R 1.587
(ransactions on Database Systems, V)-.35 F 1.587(ol. 2, 1 \(March 1977\),)-1.29
F(11-26.)108 513.6 Q F1(The Art of Computer Pr)108 537.6 Q -.1(og)-.45 G -.15
(ra).1 G(mming V).15 E(ol. 3: Sorting and Sear)-1.11 E -.15(ch)-.37 G(ing).15 E
F0 2.5(,D).22 G(.E. Knuth, 1968, pp 471-480.)382 537.6 Q F3 -.09(BU)72 554.4 S
(GS).09 E F0(Only big and little endian byte order is supported.)108 566.4 Q
174.135(4.4BSD June)72 732 R(4, 1993)2.5 E(2)535 732 Q EP
%%Trailer
end
%%EOF