bdb_usenix.ps

介绍：MySQL是比较出名的数据库软件

(full in the steady state.)323.2 573 Q 1.649
(The Hash access method supports insertion and dele-)323.2 589.2 R .259
(tion of records and lookup by e)323.2 601.2 R .259(xact match only)-.15
F 5.258(.A)-.65 G(ppli-)-5.258 E .038(cations may iterate o)323.2 613.2
R -.15(ve)-.15 G 2.538(ra).15 G .038(ll records stored in a table, b)
-2.538 F(ut)-.2 E(the order in which the)323.2 625.2 Q 2.5(ya)-.15 G
(re returned is unde\214ned.)-2.5 E F1 3(2.2. B+tr)323.2 655.2 R(ee)
-.216 E F0(Berk)323.2 671.4 Q(ele)-.1 E 7.184(yD)-.15 G 7.184(Bi)-7.184
G 4.683(ncludes a B+tree [Come79] access)-7.184 F 2.502(method. B+trees)
323.2 683.4 R .002(store records of k)2.502 F -.15(ey)-.1 G(/v).15 E
.003(alue pairs in leaf)-.25 F .52(pages, and pairs of \(k)323.2 695.4 R
-.15(ey)-.1 G 3.02(,c)-.5 G .52(hild page address\) at internal)-3.02 F
5.384(nodes. K)323.2 707.4 R -.15(ey)-.25 G 5.384(si).15 G 5.384(nt)
-5.384 G 2.885(he tree are stored in sorted order)-5.384 F(,)-.4 E EP
%%Page: 3 3
%%BeginPageSetup
BP
%%EndPageSetup
/F0 10/Times-Roman@0 SF .576
(where the order is determined by the comparison func-)79.2 84 R .815
(tion supplied when the database w)79.2 96 R .815(as created.)-.1 F -.15
(Pa)5.815 G .815(ges at).15 F .389(the leaf le)79.2 108 R -.15(ve)-.25 G
2.889(lo).15 G 2.889(ft)-2.889 G .389
(he tree include pointers to their neigh-)-2.889 F 1.444
(bors to simplify tra)79.2 120 R -.15(ve)-.2 G 3.944(rsal. B+trees).15 F
1.445(support lookup by)3.944 F -.15(ex)79.2 132 S .068
(act match \(equality\) or range \(greater than or equal to).15 F 2.891
(ak)79.2 144 S -.15(ey)-2.991 G 2.891(\). Lik).15 F 2.891(eH)-.1 G .391
(ash tables, B+trees support record inser)-2.891 F(-)-.2 E
(tion, deletion, and iteration o)79.2 156 Q -.15(ve)-.15 G 2.5(ra).15 G
(ll records in the tree.)-2.5 E .646
(As records are inserted and pages in the B+tree \214ll up,)79.2 172.2 R
(the)79.2 184.2 Q 2.722(ya)-.15 G .223(re split, with about half the k)
-2.722 F -.15(ey)-.1 G 2.723(sg).15 G .223(oing into a ne)-2.723 F(w)
-.25 E 1.603(peer page at the same le)79.2 196.2 R -.15(ve)-.25 G 4.103
(li).15 G 4.103(nt)-4.103 G 1.603(he tree.)-4.103 F 1.603(Most B+tree)
6.603 F .387(implementations lea)79.2 208.2 R .687 -.15(ve b)-.2 H .387
(oth nodes half-full after a split.).15 F 2.763
(This leads to poor performance in a common case,)79.2 220.2 R 1.522
(where the caller inserts k)79.2 232.2 R -.15(ey)-.1 G 4.022(si).15 G
4.022(no)-4.022 G(rder)-4.022 E 6.522(.T)-.55 G 4.023(oh)-7.322 G 1.523
(andle this)-4.023 F 1.643(case, Berk)79.2 244.2 R(ele)-.1 E 4.143(yD)
-.15 G 4.143(Bk)-4.143 G 1.642(eeps track of the insertion order)-4.243
F(,)-.4 E 2.023(and splits pages une)79.2 256.2 R -.15(ve)-.25 G 2.024
(nly to k).15 F 2.024(eep pages fuller)-.1 F 7.024(.T)-.55 G(his)-7.024
E 2.3(reduces tree size, yielding better search performance)79.2 268.2 R
(and smaller databases.)79.2 280.2 Q 3.177
(On deletion, empty pages are coalesced by re)79.2 296.4 R -.15(ve)-.25
G(rse).15 E 2.03(splits into single pages.)79.2 308.4 R 2.03
(The access method does no)7.03 F .347
(other page balancing on insertion or deletion.)79.2 320.4 R -2.15 -.25
(Ke y)5.348 H 2.848(sa).25 G(re)-2.848 E 1.927(not mo)79.2 332.4 R -.15
(ve)-.15 G 4.427(da).15 G 1.927(mong pages at e)-4.427 F -.15(ve)-.25 G
1.926(ry update to k).15 F 1.926(eep the)-.1 F 2.206
(tree well-balanced.)79.2 344.4 R 2.207(While this could impro)7.206 F
2.507 -.15(ve s)-.15 H(earch).15 E 2.341
(times in some cases, the additional code comple)79.2 356.4 R(xity)-.15
E(leads to slo)79.2 368.4 Q(wer updates and is prone to deadlocks.)-.25
E -.15(Fo)79.2 384.6 S 2.948(rs).15 G(implicity)-2.948 E 2.948(,B)-.65 G
(erk)-2.948 E(ele)-.1 E 2.949(yD)-.15 G 2.949(BB)-2.949 G .449
(+trees do no pre\214x com-)-2.949 F(pression of k)79.2 396.6 Q -.15(ey)
-.1 G 2.5(sa).15 G 2.5(ti)-2.5 G(nternal or leaf nodes.)-2.5 E/F1 12
/Times-Bold@0 SF 3(2.3. Recno)79.2 426.6 R F0(Berk)79.2 442.8 Q(ele)-.1
E 2.736(yD)-.15 G 2.736(Bi)-2.736 G .236(ncludes a \214x)-2.736 F .236
(ed- or v)-.15 F .235(ariable-length record)-.25 F 5.075
(access method, called)79.2 454.8 R/F2 10/Times-Italic@0 SF(Recno)7.575
E F0 10.075(.T)C 5.075(he Recno access)-10.075 F .896
(method assigns logical record numbers to each record,)79.2 466.8 R .978
(and can search for and update records by record num-)79.2 478.8 R(ber)
79.2 490.8 Q 5.037(.R)-.55 G .037(ecno is able, for e)-5.037 F .037
(xample, to load a te)-.15 F .036(xt \214le into a)-.15 F 1.514
(database, treating each line as a record.)79.2 502.8 R 1.514
(This permits)6.514 F -.1(fa)79.2 514.8 S 1.313
(st searches by line number for applications lik).1 F 3.812(et)-.1 G
-.15(ex)-3.812 G(t).15 E(editors [Ston82].)79.2 526.8 Q 2.59
(Recno is actually b)79.2 543 R 2.59(uilt on top of the B+tree access)
-.2 F 3.192(method and pro)79.2 555 R 3.191(vides a simple interf)-.15 F
3.191(ace for storing)-.1 F 3.14(sequentially-ordered data v)79.2 567 R
5.64(alues. The)-.25 F 3.14(Recno access)5.64 F 2.266
(method generates k)79.2 579 R -.15(ey)-.1 G 4.766(si).15 G(nternally)
-4.766 E 7.266(.T)-.65 G 2.266(he programmer')-7.266 F(s)-.55 E(vie)79.2
591 Q 4.102(wo)-.25 G 4.102(ft)-4.102 G 1.602(he v)-4.102 F 1.602
(alues is that the)-.25 F 4.102(ya)-.15 G 1.603(re numbered sequen-)
-4.102 F .254(tially from one.)79.2 603 R(De)5.254 E -.15(ve)-.25 G .254
(lopers can choose to ha).15 F .553 -.15(ve r)-.2 H(ecords).15 E 9
(automatically renumbered when lo)79.2 615 R(wer)-.25 E(-numbered)-.2 E
.041(records are added or deleted.)79.2 627 R .041(In this case, ne)
5.041 F 2.541(wk)-.25 G -.15(ey)-2.641 G 2.541(sc).15 G(an)-2.541 E
(be inserted between e)79.2 639 Q(xisting k)-.15 E -.15(ey)-.1 G(s.).15
E F1 3(3. F)79.2 669 R(eatur)-.3 E(es)-.216 E F0 1.827
(This section describes important features of Berk)79.2 685.2 R(ele)-.1
E(y)-.15 E 3.456(DB. In)79.2 697.2 R .956(general, de)3.456 F -.15(ve)
-.25 G .956(lopers can choose which features).15 F .488
(are useful to them, and use only those that are required)79.2 709.2 R
(by their application.)323.2 84 Q -.15(Fo)323.2 100.2 S 3.529(re).15 G
1.029(xample, when an application opens a database, it)-3.679 F .101
(can declare the de)323.2 112.2 R .101(gree of concurrenc)-.15 F 2.601
(ya)-.15 G .102(nd reco)-2.601 F -.15(ve)-.15 G .102(ry that).15 F .049
(it requires.)323.2 124.2 R .048
(Simple stand-alone applications, and in par)5.049 F(-)-.2 E .491
(ticular ports of applications that used)323.2 136.2 R/F3 10/Courier@0
SF(dbm)2.991 E F0 .491(or one of its)2.991 F -.25(va)323.2 148.2 S 1.093
(riants, generally do not require concurrent access or).25 F .975
(crash reco)323.2 160.2 R -.15(ve)-.15 G(ry).15 E 5.975(.O)-.65 G .975
(ther applications, such as enterprise-)-5.975 F 3.08
(class database management systems that store sales)323.2 172.2 R 2.643
(transactions or other critical data, need full transac-)323.2 184.2 R
3.93(tional service.)323.2 196.2 R 3.93(Single-user operation is f)8.93
F 3.93(aster than)-.1 F 1.175(multi-user operation, since no o)323.2
208.2 R -.15(ve)-.15 G 1.176(rhead is incurred by).15 F 3.156
(locking. Running)323.2 220.2 R .656(with the reco)3.156 F -.15(ve)-.15
G .655(ry system disabled is).15 F -.1(fa)323.2 232.2 S 1.732
(ster than running with it enabled, since log records).1 F 2.703
(need not be written when changes are made to the)323.2 244.2 R
(database.)323.2 256.2 Q .851
(In addition, some core subsystems, including the lock-)323.2 272.4 R
.345(ing system and the logging f)323.2 284.4 R(acility)-.1 E 2.844(,c)
-.65 G .344(an be used outside)-2.844 F 1.772(the conte)323.2 296.4 R
1.772(xt of the access methods as well.)-.15 F(Although)6.773 E(fe)323.2
308.4 Q 4.284(wu)-.25 G 1.784(sers ha)-4.284 F 2.084 -.15(ve c)-.2 H
1.784(hosen to do so, it is possible to use).15 F .939
(only the lock manager in Berk)323.2 320.4 R(ele)-.1 E 3.439(yD)-.15 G
3.439(Bt)-3.439 G 3.439(oc)-3.439 G .939(ontrol con-)-3.439 F(currenc)
323.2 332.4 Q 4.743(yi)-.15 G 4.743(na)-4.743 G 4.743(na)-4.743 G 2.242
(pplication, without using an)-4.743 F 4.742(yo)-.15 G 4.742(ft)-4.742 G
(he)-4.742 E .158(standard database services.)323.2 344.4 R(Alternati)
5.158 E -.15(ve)-.25 G(ly).15 E 2.658(,t)-.65 G .159(he caller can)
-2.658 F(inte)323.2 356.4 Q .07
(grate locking of non-database resources with Berk)-.15 F(e-)-.1 E(le)
323.2 368.4 Q 5.201(yD)-.15 G(B')-5.201 E 5.201(st)-.55 G 2.702
(ransactional tw)-5.201 F 2.702(o-phase locking system, to)-.1 F 2.892
(impose transaction semantics on objects outside the)323.2 380.4 R
(database.)323.2 392.4 Q F1 3(3.1. Pr)323.2 422.4 R
(ogrammatic interfaces)-.216 E F0(Berk)323.2 438.6 Q(ele)-.1 E 4.008(yD)
-.15 G 4.008(Bd)-4.008 G 1.509(e\214nes a simple API for database man-)
-4.008 F 3.452(agement. The)323.2 450.6 R .952
(package does not include industry-stan-)3.452 F 1.898
(dard programmatic interf)323.2 462.6 R 1.898
(aces such as Open Database)-.1 F(Connecti)323.2 474.6 Q .852
(vity \(ODBC\), Object Linking and Embedding)-.25 F .817
(for Databases \(OleDB\), or Structured Query Language)323.2 486.6 R
4.027(\(SQL\). These)323.2 498.6 R(interf)4.027 E 1.527
(aces, while useful, were designed)-.1 F 2.477
(to promote interoperability of database systems, and)323.2 510.6 R
(not simplicity or performance.)323.2 522.6 Q 3.192
(In response to customer demand, Berk)323.2 538.8 R(ele)-.1 E 5.691(yD)
-.15 G 5.691(B2)-5.691 G(.5)-5.691 E .538
(introduced support for the XA standard [Open94].)323.2 550.8 R(XA)5.539
E .52(permits Berk)323.2 562.8 R(ele)-.1 E 3.02(yD)-.15 G 3.02(Bt)-3.02
G 3.02(op)-3.02 G .52(articipate in distrib)-3.02 F .52(uted trans-)-.2
F 3.373(actions under a transaction processing monitor lik)323.2 574.8 R
(e)-.1 E -.45(Tu)323.2 586.8 S -.15(xe).45 G 1.31(do from BEA Systems.)
.15 F(Lik)6.31 E 3.81(eX)-.1 G 1.31(A, other standard)-3.81 F(interf)
323.2 598.8 Q .99(aces can be b)-.1 F .99
(uilt on top of the core system.)-.2 F(The)5.99 E .846
(standards do not belong inside Berk)323.2 610.8 R(ele)-.1 E 3.346(yD)
-.15 G .846(B, since not)-3.346 F(all applications need them.)323.2
622.8 Q F1 3(3.2. W)323.2 652.8 R(orking with r)-.9 E(ecords)-.216 E F0
3.134(Ad)323.2 669 S .634
(atabase user may need to search for particular k)-3.134 F -.15(ey)-.1 G
(s).15 E .908(in a database, or may simply w)323.2 681 R .908
(ant to bro)-.1 F .907(wse a)-.25 F -.25(va)-.2 G(ilable).25 E 4.101
(records. Berk)323.2 693 R(ele)-.1 E 4.101(yD)-.15 G 4.101(Bs)-4.101 G
1.601(upports both k)-4.101 F -.15(ey)-.1 G 1.602(ed access, to).15 F
.173(\214nd one or more records with a gi)323.2 705 R -.15(ve)-.25 G
2.673(nk).15 G -.15(ey)-2.773 G 2.673(,o)-.5 G 2.673(rs)-2.673 G
(equential)-2.673 E .53(access, to retrie)323.2 717 R .83 -.15(ve a)-.25
H .53(ll the records in the database one at).15 F EP
%%Page: 4 4
%%BeginPageSetup
BP
%%EndPageSetup
/F0 10/Times-Roman@0 SF 6.34(at)79.2 84 S 6.34(ime. The)-6.34 F 3.84
(order of the records returned during)6.34 F .208
(sequential scans depends on the access method.)79.2 96 R(B+tree)5.209 E
1.495(and Recno databases return records in sort order)79.2 108 R 3.995
(,a)-.4 G(nd)-3.995 E .023
(Hash databases return them in apparently random order)79.2 120 R(.)-.55
E(Similarly)79.2 136.2 Q 4.959(,B)-.65 G(erk)-4.959 E(ele)-.1 E 4.959
(yD)-.15 G 4.958(Bd)-4.959 G 2.458(e\214nes simple interf)-4.958 F 2.458
(aces for)-.1 F
(inserting, updating, and deleting records in a database.)79.2 148.2 Q
/F1 12/Times-Bold@0 SF 3(3.3. Long)79.2 178.2 R -.12(ke)3 G(ys and v).12
E(alues)-.12 E F0(Berk)79.2 194.4 Q(ele)-.1 E 3.553(yD)-.15 G 3.553(Bm)
-3.553 G 1.053(anages k)-3.553 F -.15(ey)-.1 G 3.553(sa).15 G 1.053
(nd v)-3.553 F 1.053(alues as lar)-.25 F 1.054(ge as 2)-.18 F/F2 8
/Times-Roman@0 SF(32)-5 I F0 3.192(bytes. Since)79.2 206.4 R .692
(the time required to cop)3.192 F 3.192(yar)-.1 G .692(ecord is pro-)
-3.192 F 1.895(portional to its size, Berk)79.2 218.4 R(ele)-.1 E 4.396
(yD)-.15 G 4.396(Bi)-4.396 G 1.896(ncludes interf)-4.396 F(aces)-.1 E
4.507(that operate on partial records.)79.2 230.4 R 4.507
(If an application)9.507 F 1.273(requires only part of a lar)79.2 242.4
R 1.274(ge record, it requests partial)-.18 F .026(record retrie)79.2
254.4 R -.25(va)-.25 G .026(l, and recei).25 F -.15(ve)-.25 G 2.526(sj)
.15 G .025(ust the bytes that it needs.)-2.526 F(The smaller cop)79.2
266.4 Q 2.5(ys)-.1 G -2.25 -.2(av e)-2.5 H 2.5(sb).2 G
(oth time and memory)-2.5 E(.)-.65 E(Berk)79.2 282.6 Q(ele)-.1 E 3.206
(yD)-.15 G 3.206(Ba)-3.206 G(llo)-3.206 E .706
(ws the programmer to de\214ne the data)-.25 F 2.72(types of k)79.2
294.6 R -.15(ey)-.1 G 5.22(sa).15 G 2.72(nd v)-5.22 F 5.22(alues. De)
-.25 F -.15(ve)-.25 G 2.72(lopers use an).15 F 5.22(yt)-.15 G(ype)-5.22
E -.15(ex)79.2 306.6 S(pressible in the programming language.).15 E F1 3
(3.4. Lar)79.2 336.6 R(ge databases)-.12 E F0 3.255(As)79.2 352.8 S .755
(ingle database managed by Berk)-3.255 F(ele)-.1 E 3.256(yD)-.15 G 3.256
(Bc)-3.256 G .756(an be up)-3.256 F 1.716(to 2)79.2 364.8 R F2(48)-5 I
F0 1.716(bytes, or 256 petabytes, in size.)4.216 5 N(Berk)6.715 E(ele)
-.1 E 4.215(yD)-.15 G(B)-4.215 E 2.144
(uses the host \214lesystem as the backing store for the)79.2 376.8 R
2.668(database, so lar)79.2 388.8 R 2.667
(ge databases require big \214le support)-.18 F 3.113
(from the operating system.)79.2 400.8 R(Sleep)8.113 E 3.114(ycat Softw)
-.1 F 3.114(are has)-.1 F 5.712(customers using Berk)79.2 412.8 R(ele)
-.1 E 8.212(yD)-.15 G 8.212(Bt)-8.212 G 8.211(om)-8.212 G 5.711
(anage single)-8.211 F(databases in e)79.2 424.8 Q(xcess of 100 gig)-.15
E(abytes.)-.05 E F1 3(3.5. Main)79.2 454.8 R(memory databases)3 E F0
1.171(Applications that do not require persistent storage can)79.2 471 R
.119(create databases that e)79.2 483 R .119(xist only in main memory)
-.15 F 5.118(.T)-.65 G(hese)-5.118 E .542(databases bypass the o)79.2
495 R -.15(ve)-.15 G .543(rhead imposed by the I/O sys-).15 F
(tem altogether)79.2 507 Q(.)-.55 E 2.144
(Some applications do need to use disk as a backing)79.2 523.2 R 2.248
(store, b)79.2 535.2 R 2.249(ut run on machines with v)-.2 F 2.249
(ery lar)-.15 F 2.249(ge memory)-.18 F(.)-.65 E(Berk)79.2 547.2 Q(ele)
-.1 E 2.799(yD)-.15 G 2.799(Bi)-2.799 G 2.799(sa)-2.799 G .299
(ble to manage v)-2.799 F .299(ery lar)-.15 F .299(ge shared mem-)-.18 F
.128(ory re)79.2 559.2 R .129
(gions for cached data pages, log records, and lock)-.15 F 3.938
(management. F)79.2 571.2 R 1.437(or e)-.15 F 1.437
(xample, the cache re)-.15 F 1.437(gion used for)-.15 F .033
(data pages may be gig)79.2 583.2 R .034
(abytes in size, reducing the lik)-.05 F(eli-)-.1 E .639(hood that an)