![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to memo CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [Research Unix] / researchv10no / cmd / btree|
Return to memo CVS log | Up to [Research Unix] / researchv10no / cmd / btree |
1.1 root 1: .fp 1 PA
2: .fp 2 PI
3: .fp 3 PB
4: .fp 4 PX
5: .EQ
6: delim $$
7: .EN
8: .ND January 2, 1981
9: .TM 81-11272-1 11173 11173-11
10: .TL
11: .UX
12: B-trees
13: .AU "MH 2C522" 7214
14: P.J. Weinberger
15: .AI
16: .MH
17: .AB
18: B-trees are a good data structure for storing, retrieving,
19: and updating records in files containing many records.
20: Ordinary
21: .UX
22: tools such as
23: $awk$ and $grep$ become too slow when used on files with more than
24: a few hundred lines,
25: and $ed$ can no longer be used for updating after a thousand or so lines.
26: This memo contains descriptions of subroutines and commands
27: for creating and maintaining B-trees,
28: and a complete example of their use in a data base with two files.
29: .AE
30: .CS 5 2 7 0 0 1
31: .NH
32: Introduction
33: .PP
34: This memo contains a description of subroutines and commands
35: which implement B-trees.
36: (See [Comer] for a bibliography on B-trees.)
37: The subroutines make the B-trees look to the user like a list
38: of
39: .I "key\(emvalue"
40: pairs,
41: sorted by
42: .I key .
43: The subroutines provide for positioning within the list,
44: reading the next pair, deleting pairs, and writing pairs.
45: The way the subroutines implement the list is by using
46: a prefix-compressed B-tree,
47: in which prefixes common to consecutive
48: .I keys
49: are factored out.
50: The details of the data structures are in sections 2 and 5.
51: .PP
52: There are several advantages to using these B-trees as the file
53: organization for data bases.
54: A given key can be searched for with a small number of file system
55: accesses, typically two or three.
56: Since the file looks to the user as if it is sorted on the keys,
57: it is easy to retrieve the lexically next key, and
58: so to scan the file in lexical order.
59: Because the keys are sorted,
60: adjacent keys tend to have a common prefix,
61: which can be compressed out.
62: In the case of
63: the dictionary
64: .I /usr/dict/words ,
65: where the
66: .I values
67: are all null,
68: the original file consists of 24473 words and 201032 bytes,
69: while the B-tree contains only 134144 bytes.
70: The B-tree is significantly shorter even though it contains
71: headers and other overhead.
72: .PP
73: Sections 3 and 4 contain descriptions of subroutines and commands.
74: .PP
75: There are 9 subroutines.
76: 4 of these correspond to
77: .UX
78: system calls $read$, $write$, $open$, $close$,
79: with the difference that the data stored in the B-trees is not just
80: a vector of bytes, but is a sequence of $key\(emvalue$ pairs.
81: There is one routine for deleting,
82: which has no corresponding system call.
83: The remaining 4 correspond to various aspects of $lseek$:
84: one positions, one reports on the position, one positions to the
85: beginning, and the last gives the length of the $value$ at the
86: current position.
87: .PP
88: The commands are utilities for building B-trees,
89: dealing with them at the command level,
90: and gathering statistics about them.
91: .PP
92: Section 6 contains a complete example constructing and using
93: a small but interesting data base.
94: .NH
95: B-trees
96: .PP
97: The B-trees used by the subroutines are slightly different from
98: standard B-trees.
99: The resemblance would be closer if the routines did not support the
100: .I value
101: half of the pair.
102: Then the
103: .UX
104: B-trees would be B-trees in which all the keys are in leaves,
105: and in which the keys can be of variable length, and are stored
106: with some compression.
107: Adding the
108: .I value
109: half of a pair allows very large records to be stored.
110: Further each record can be stored contiguously,
111: rather than broken across tree nodes.
112: .PP
113: The standard definition of B-tree requires some bounds on the number
114: of keys in a node,
115: as in 2-3 trees, where each node has 2 or 3 keys.
116: While this restriction is convenient for proving theorems
117: it is silly in practice.
118: Intuitively, trees which branch a lot at each node
119: have more leaves for a given height,
120: so that searching from the root to a leaf requires fewer file
121: system accesses the bushier the tree.
122: Therefore one wants as many keys as possible in each node,
123: all other things being equal.
124: The node size has been chosen to be the disk block size.
125: Given that,
126: various algorithms for data compression might be used to squeeze
127: as many keys as possible into a node.
128: .PP
129: The method I chose maintains the keys in lexical order in the node.
130: If a key begins with the same $n$ bytes as its immediate predecessor,
131: it is stored with the $n$ bytes replaced by the count $n$.
132: A trivial analysis shows how much space might be saved:
133: Suppose that the keys are chosen at random from strings of length $m$
134: in which each of $a$ characters appears with equal probability.
135: Since there are no more than $a sup k$ prefixes of length $k$,
136: one expects that the length of the common prefix of two of $N$
137: keys is about $log ( N) / log (a)$.
138: Since one byte is required to store the length of the common prefix,
139: the space saving should be around
140: $N( log N / log a - 1) $ bytes.
141: .PP
142: Using this compression technique does not make handling the keys
143: much more complicated.
144: The reader will have no trouble seeing that searching to find a
145: key is easy, that the size of a list of keys decreases when a key
146: is deleted, and that the size of a list of keys increases by no more
147: than the uncompressed size of the new key when a key is inserted.
148: .PP
149: The neighborhood of an interior node in a B-tree looks like
150: .KS
151: .nf
152: .so picture.out
153: .fi
154: .KE
155: Each node which is not a leaf contains one more pointer than key:
156: .EQ
157: p sub 0 , ~ k sub 0 , ~ p sub 1 , ~ k sub 1 , ~ ... ,
158: ~ k sub n , ~ p sub n+1 .
159: .EN
160: Of the keys in the subtree whose root is the given node,
161: $p sub j$ points to the subtree containing keys strictly greater than
162: $k sub j-1$ and no greater than $k sub j$.
163: $p sub 0$ points to the subtree containing keys no greater than $k sub 0$,
164: and $p sub n+1$ points to the subtree containing keys strictly greater
165: than $k sub n$.
166: If $n$ is 0, then there is only one subtree, and $p sub 0$ points to it.
167: This last case can occur when the tree is being built by the $build$
168: command, which may leave a single node nearly empty at each level of
169: the tree due to its zeal in making the rest of the nodes at that
170: level as full as possible.
171: More detail on file structure is in section 5.
172: .NH
173: Subroutines
174: .PP
175: There are 9 subroutines that C programs can use to access B-trees.
176: The normal order of events would be for a program to open one or more
177: B-trees using $bopen$.
178: To retrieve information the program would use $bseek$ to position
179: itself in the B-tree.
180: It could use $breclen$ to see how much it was about to read,
181: and then $bread$ to actually retrieve the data.
182: If it wanted to delete information it would use $bdelete$,
183: and to write new or changed information it would use $bwrite$.
184: .SH
185: /usr/include/cbt.h
186: .LP
187: contains definitions of some manifest constants and types used
188: by the subroutines.
189: Manifest constants are represented as CONSTANT.
190: A pointer of type
191: .I *bfile
192: is returned by the open routine and passed to each of the other
193: routines.
194: Data is passed in
195: an
196: .I mbuf :
197: .DS
198: .ft 8
199: typedef struct {
200: char *mdata;
201: unsigned short mlen;
202: } mbuf;
203: .ft P
204: .DE
205: .I mdata
206: points to
207: .I mlen
208: bytes of data.
209: .PP
210: An open B-tree is either positioned at its end or at some pair.
211: When the file is opened, it is positioned at the first pair.
212: Reading the B-tree gets the pair at the current position.
213: Each subroutine has a deterministic effect on the current position.
214: .PP
215: B-trees can have any one of the 4 types INDEX, READONLY, both,
216: or neither.
217: The type is determined when the B-tree is created.
218: INDEX says that the
219: .I value
220: part of a pair will always be null;
221: i.e.,
222: .I mlen
223: will be zero.
224: A B-tree should be READONLY if updates are infrequent and are never done
225: while someone else is reading in the B-tree.
226: .SH
227: bfile *bopen(b-tree-name, flag)
228: char *b-tree-name;
229: .LP
230: returns a pointer to an internal structure if the open is
231: successful, and NULL otherwise.
232: The file is positioned to its first pair.
233: .I flag
234: should be 0 if the file is only to be read, and 2 otherwise.
235: It is passed directly to the system
236: .I open
237: routine.
238: .SH
239: bclose(bf) bfile *bf;
240: .LP
241: closes the B-tree, flushing buffers and cleaning up in general.
242: If a process updates a B-tree which is not READONLY,
243: then it must call this routine before any other user can perceive
244: its updates.
245: .SH
246: bfirst(bf) bfile *bf;
247: .LP
248: resets the current position in the file to the beginning.
249: It returns EOF if the B-tree is empty.
250: .SH
251: bseek(bf, key) bfile *bf; mbuf key;
252: .LP
253: sets the current position in the file to the first key in the file
254: which is lexically greater than or equal to
255: .I key .
256: The routine returns FOUND if
257: .I key
258: was in the file,
259: EOF if
260: .I key
261: is greater than any key in the file,
262: and NOTFOUND otherwise.
263: Lexical ordering is that induced by the C type
264: .I char .
265: .SH
266: breclen(bf) bfile *bf;
267: .LP
268: returns the length of the
269: .I value
270: at the current position in the file,
271: or EOF if you are at the end of the file.
272: (On a machine where
273: $short$ and
274: .I int
275: are 16 bits long,
276: EOF will be a legal value for $mlen$,
277: name 65535.
278: If the user is on such a machine and writes objects of this length,
279: he must not rely on this subroutine to detect the end of the file.)
280: .SH
281: mbuf bkey(bf) bfile *bf;
282: .LP
283: returns the
284: .I key
285: at the current position of the file.
286: A key cannot have
287: .I mlen
288: of zero, so if the returned value does,
289: you are at the end of the file.
290: Do not change the data pointed to by
291: .I mdata
292: in the returned value,
293: as it is used by the subroutines.
294: .SH
295: bread(bf, key, rec) bfile *bf; mbuf *key, *rec;
296: .LP
297: returns 0 if successful and EOF otherwise.
298: If
299: .I key
300: is not NULL,
301: $ key->mlen $
302: is set to the length of the key at the current position of the file,
303: and the buffer pointed to by
304: $ key->mdata $
305: is filled with the key.
306: Likewise, if
307: .I rec
308: is not NULL,
309: $ rec->mlen $ is set to the length of the value at the current position
310: of the file,
311: and the buffer pointed to by
312: $rec->mdata $
313: is filled with the value.
314: Then the current position in the file is moved to the next pair.
315: It is the user's responsibility to make the buffers large enough
316: to hold what is put in them.
317: $breclen$ gives the necessary size for values,
318: and no key can be as large as the defined constant NDSZ from
319: .I /usr/include/cbt.h .
320: .SH
321: bdelete(bf, key) bfile *bf; mbuf key;
322: .LP
323: deletes the pair with the given
324: .I key
325: from the file if it is present.
326: The routine returns EOF on error,
327: FOUND if a pair was deleted,
328: and NOTFOUND otherwise.
329: Afterwards, the current position in the file is as if
330: .I "bseek(bf, key)"
331: had been called.
332: .SH
333: bwrite(bf, key, value) bfile *bf; mbuf key, value;
334: .LP
335: writes the pair
336: .I "key value"
337: into the file.
338: It returns EOF on error, FOUND if a pair was overwritten,
339: and NOTFOUND if a new pair was written.
340: When the routine returns,
341: the position of the file is as if
342: .I "bseek(bf, key)"
343: had been called.
344: Keys should not be more than about 120 bytes long.
345: .SH
346: Error Returns
347: .PP
348: If an error causes a routine to return EOF,
349: the external integer
350: .I errno
351: is set to one of the codes defined in the header file.
352: BNOWRITE means you tried to write on a B-tree not opened for writing,
353: BIOWRT means that the system wrote fewer bytes than requested,
354: BNOMEM means that a subroutine needed more memory and couldn't get it,
355: and BTALL means that the tree has grown too tall.
356: .I errno
357: can also be set because one of the system calls failed.
358: Then it will have one of the values from
359: .I /usr/include/errno.h .
360: .NH
361: Commands
362: .PP
363: The commands are all of the form
364: .I "cbt command args" .
365: The file
366: .I cbt
367: is a shell script which invokes the actual commands.
368: The commands are utilites.
369: $cat$ just uses the subroutines of the last section,
370: but $creat$, $build$, and $report$
371: require inside knowledge of data structures not available through
372: the B-tree subroutines.
373: This is all in the spirit of data abstraction.
374: The user, through the subroutines, gets certain services,
375: which are best provided through private data structures
376: not available to the user.
377: $build$ has another and more compelling justification;
378: it creates trees that require less space than if they were constructed
379: by a sequence of $bwrite$s.
380: .SH
381: cbt creat [flags] file
382: .LP
383: creates an empty B-tree.
384: In
385: .I flags ,
386: .I -i
387: makes the file have type INDEX,
388: and
389: .I -r
390: makes the file have type READONLY.
391: The
392: .UX
393: file created is
394: .I file.T .
395: If the B-tree is not of type INDEX,
396: .I file.F
397: is created to hold the values.
398: .SH
399: cbt build [-R] file
400: .LP
401: builds the B-tree
402: .I file
403: from the standard input.
404: The input data must be sorted by key.
405: The new file has each node as full as possible,
406: given that the program decides what to do with each key
407: before looking at the next.
408: .PP
409: If the optional argument is not present
410: each line of input contains a key and value separated by a tab.
411: All the bytes to the first tab on a line make up the key
412: (which must not be empty),
413: the tab is removed,
414: and the remaining bytes, not including the trailing newline,
415: make up the value.
416: Thus there is no way, without the optional argument to the command, to
417: get a tab or newline in a key, or a newline in a value.
418: .PP
419: If the optional argument is present,
420: the command expects a sequence of data of the form
421: .DS
422: .ft 8
423: struct {
424: struct
425: unsigned short klen;
426: char kdata[klen];
427: } key;
428: struct {
429: unsigned short vlen;
430: char vdata[vlen];
431: } value;
432: };
433: .ft P
434: .DE
435: The dictionary mentioned in the introduction was constructed by
436: .DS
437: .ft 8
438: cbt creat -i foo; sort /usr/dict/words | cbt build foo
439: .ft P
440: .DE
441: .SH
442: cbt cat [flags] files
443: .LP
444: writes the contents of the files on its standard output.
445: If the
446: .I R
447: flag is present the output is suitable for
448: .I R
449: input to
450: .I build,
451: otherwise the output is a sequence of `lines' of the form
452: key, tab, value, newline.
453: Thus the command
454: .DS
455: .ft 8
456: cbt cat -R file | cbt build -R newfile
457: .ft P
458: .DE
459: will compress the old file into the new file.
460: .SH
461: cbt report file
462: .LP
463: scans the file and reports on the number of pairs,
464: the total size, the amount of the tree in use, and
465: the amount of free space.
466: .NH
467: File Structure
468: .PP
469: The
470: .I .F
471: file contains the values concatenated together in the order they
472: were written.
473: Each time a pair is written, the new value is put on the end of
474: the
475: .I .F
476: file.
477: Deleting a pair has no effect on the
478: .I .F
479: file.
480: Therefore as a B-tree is updated,
481: the
482: .I .F
483: file grows.
484: .PP
485: The
486: .I .T
487: file contains the B-tree proper,
488: and pointers to the
489: .I .F
490: file if the B-tree is not an INDEX.
491: The
492: .I .T
493: contains only tree nodes,
494: each one NDSZ bytes long.
495: (NDSZ is defined in the header file.)
496: Each node has the form
497: .DS
498: header, keys, space, addresses, trailer.
499: .DE
500: The trailer is a $short$ containing the number of unused bytes in the
501: node,
502: which is the size of $space$.
503: .PP
504: The form of an $address$ depends on the type of the file
505: and the height of the node in the tree.
506: Leaves have height 0.
507: Each other node has height one greater than its children.
508: B-trees have the property that each node has a well-defined
509: height.
510: If the node is not a leaf, each $address$ is a $short$
511: which is the location of a child of the node.
512: The node pointed to by $address$ is the node starting at $address * NDSZ$
513: in the file.
514: Leaves in files of type INDEX don't have addresses.
515: Otherwise an $address$ is a structure containing the length of the
516: value and its starting position in the
517: .I .F
518: file.
519: .PP
520: Each $key$ structure contains its total length in a
521: one-byte field, then the number of bytes of prefix
522: in common with the preceding key in the node, and then the rest of the key.
523: .PP
524: The $header$ contains an identifier so that a program
525: can tell if it rewrote the node,
526: the number of keys in the node,
527: the type of the node,
528: and the height of the node.
529: The first node in a file is always the root.
530: The identifier is made from the process id and the time.
531: If a file is not READONLY the routines will not overwrite a node unless the
532: node was originally written by the process,
533: or unless the file is being closed and the node is the root.
534: In this way a file which is not READONLY supports one writer concurrently with
535: programs reading.
536: .NH
537: An example
538: .PP
539: The example is a data base with two files.
540: With it the user can translate from old department numbers
541: to new department numbers,
542: and get the title of a department from either department number.
543: The example illustrates how to construct the data base
544: and suggests one way of contstructing an index.
545: There is also a complete program for retrieving from the data base
546: whcih illustrates using all the subroutines which don't change
547: B-trees.
548: .PP
549: A file named $deptnos$ contains old department numbers,
550: new department numbers,
551: and department titles.
552: It is 1124 lines long and contains 56816 bytes.
553: Here are the first 4 and last 4 lines:
554: .DS
555: 0001 00001 Chairman of the Board
556: 0002 20000 Executive Vice President - Corporate Studies
557: 0003 30000 President/Project Planning
558: 0004 40000 Executive Vice President - Customer Systems
559: 9543 59543 Demand Economics Department
560: 9544 59544 Computer Systems Department
561: 9545 59545 Advanced Software Department
562: 9800 59800 Transfer of Non-Incremental Cost Between BIS and AT&T
563: .DE
564: For the example the file will go into 2 B-trees.
565: One named $dept$ will have the new department numbers as keys
566: and the department titles as values.
567: The other,
568: $olddept$,
569: will be an index which will give new department numbers as a
570: function of old.
571: By combining the two, a user will be able to determine
572: the department title from the old department number.
573: In both,
574: leading zeros will be stripped off department numbers.
575: The commands
576: .I "cbt creat dept"
577: and
578: .I "cbt creat -i olddept"
579: create empty B-trees.
580: The bold (but correct) command
581: .EQ
582: delim off
583: .EN
584: .DS
585: .ft 8
586: awk < deptnos '{$1 = ""; print}' |
587: sed 's/^ //
588: s/^0*//
589: s/ /\et/' | sort | cbt build dept
590: .ft P
591: .DE
592: .EQ
593: delim $$
594: .EN
595: builds $dept$.
596: The $awk$ command deletes the old department number and
597: replaces multiple blanks by a single blank.
598: The $sed$ command removes the leading blank
599: (which is the separator $awk$ put after the null first field)
600: and replaces the single blank separating the new
601: department number from the department title with a tab for
602: .I "cbt build" .
603: $sort$ sees 48089 bytes.
604: $dept.T$ contains 13284 bytes,
605: and $dept.F$ contains 39955 bytes.
606: Thus the additional space required for the B-tree is(39955+13284)/48089,
607: which is 1.118, about 12%.
608: The command
609: .EQ
610: delim off
611: .EN
612: .DS
613: .ft 8
614: awk < deptnos '{print $1, $2}' |
615: sed 's/^0*//
616: s/ 0*/ /' | sort | cbt build olddept
617: .ft P
618: .DE
619: .EQ
620: delim $$
621: .EN
622: builds $olddept$.
623: The $awk $ command prints the old and new department numbers,
624: separated by a space.
625: Each of the strings is the key of a pair in olddept.
626: The output of $sort$ is 12875 bytes long,
627: and $olddept.T$ is 11776 bytes long.
628: .PP
629: The program in the appendix provides a simple facility for using
630: $dept$ and $olddept$.
631: If the user types a number, all the new department numbers
632: which have that number
633: as a prefix are printed,
634: together with their department names.
635: If the user types a number preceded with the letter O,
636: then the program computes the set of old department numbers which
637: begin with the typed number,
638: and prints a set of lines consisting of the old and new
639: department numbers and the department title.
640: .NH
641: Conclusion
642: .PP
643: The subroutines and commands described in this memo can be used
644: to build and maintain data bases of moderate size.
645: The subroutines give a clean interface to C programs,
646: and the files themselves are efficient to use and
647: reasonably economical of space.
648: .SG
649: .SH
650: Bibliography
651: .LP
652: D. Comer,
653: .I
654: The Ubiquitous B-Tree,
655: .R
656: Computing Surveys
657: .B (11)
658: June 1979,
659: pp 121-137.
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.