The
BAYE76
BAYE77
BAYE77a
BERL78
BROW78
BROW78a
CLAM64
FOST65
GHOS69
GUIB77
GUIB78
HELD78
HORO76
IBM1
IBM2
KARL76
KEEH74
BAYER, R., AND METZGER, J. "On enci-
pherment
of search trees and random ac-
cess files," A CM Trans. Database Syst. 1, KNUT68
1 (March 1976), 37-52.
BAYER, R, AND UNTERAUER,
K. "PrefLx
B-trees," ACM Trans. Database Syst. 2,
1 (March 1977), 11-26. KNUT73
BAYER, R., AND SCHKOLNICK,
M. "Con-
currency of operations on B-trees," Acta
Inf. 9, 1 (1977), 1-21.
BERLINER, H. The B*-tree search al- MARU77
gortthm: a best-first proof procedure,
Tech. Rep. CMU-CA-78-112, Computer
Scmnce Dept, Carnegie-Mellon Univ.,
Pittsburgh, 1978. MAUE75
BROWN, M "A storage scheme for
height-balanced trees," Inf. Process. Lett.
7, 5 (Aug. 1978), 231-232. MCCR77
BROWN, M. "A partial analysis of
height-balanced trees," SIAM J. Comput.,
to appear. MILL77
CLAMPETT, H.
"Randomized binary
searching with tree structures," Commun.
ACM 7, 3 (March 1964), 163-165.
FOSTER, C. "Informatmn storage and re-
trieval using AVL trees," m Proc. ACM NIEV74
20th Nattonal Conf., ACM, New York,
1965, 192-205.
GHOSH, S, AND SENKO, M. "File orga- ORGA72
nization: on the selection of random ac-
cess index points for sequential files," J
ACM 16, 4 (Oct. 1969), 569-579. ROSE78
GUIBUS, L., MCCREIGHT, E., PLASS, M.,
AND ROBERTS, J. "A new representation
for linear lists," m Proc. 9th ACM Syrup. RUBI76
Theory of Computing, ACM, New York,
1977, 49-60.
GUIBAS, L., AND SEDGEWICK, R. "A dI- SAMA76
chromatic framework for balanced trees,"
m Proc 19th Syrup. Foundatmns of Com-
puter Science, 1978, 8-21. SEVE74
HELD,
G., AND STONEBRAKER, M. "B-
trees reexamined," Commun. ACM 21, 2
(Feb. 1978), 139-143.
HOROWITZ, E., AND SAHNI, S. Fundamen- WAGN73
tals of data structures, Computer Science
Press, Inc., Woodland Hdls, Calif., 1976. WEDE74
OS/VS Virtual Storage Access Method
(VSAM) planning gutde, Order No.
GC26-3799, IBM, Armonk, N.Y.
OS/VS Vwtual Storage Access Method
(VSAM) logw, Order No. SY26-3841,
IBM, Armonk, N.Y.
KARLTON, P., FULLER, S., SCROGGS, R., WIRT76
AND KACHLER, E. "Performance of
height balanced trees," Commun. ACM
19, 1 (Jan. 1976), 23-28. YAO78
KEEHN, D., AND LACY, J. "VSAM data
RECEIVED AUGUST
1978;
FINAL REVISION ACCEPTED DECEMBER
1978
Ubiquitous
B-Tree •
137
set design parameters," IBM Syst. J. 3,
(1974), 186-212.
KNUTH, D. The art of computer pro-
grarnmmg, Vol. 1. fundamental algo.
r~thrns, Addison-Wesley Publ. Co., Read-
mg, Mass, 1968.
KNUTH, D. The art of computer pro-
grammmg, Vol. 3: sorting and searching,
Addison-Wesley Publ. Co, Reading,
Mass., 1973.
MARUYAMA, K, AND SMITH, S. "Anal-
ysis of design alternatives for virtual
memory indexes," Commun. ACM 20, 4
(April 1977), 245-254.
MAUER, W., AND LEWIS, T. "Hash table
methods," Comput. Surv. 7, 1 (March
1975), 5-19.
McCREIGHT, E. "Pagination of B*-trees
with variable-length records," Commun.
ACM 20, 9 (Sept. 1977), 670-674
MILLER, R., PIPPENGER, N., ROSENBERG,
A., AND SNYDER, L. Opttmal 2-3 trees,
IBM Research Rep. RC 6505, IBM Re-
search Lab, Yorktown Heights, N.Y.,
1977.
NIEVERGELT, J. "Binary search trees
and file organization," Comput. Surv. 6, 3
(Sept. 1973), 195-207.
ORGANICK,
E. The Multics system: an
exammatmn of ~ts structure, MIT Press,
Cambridge, Mass., 1972.
ROSENBERG, A, AND SNYDER, L.
"Minimal comparison 2-3 trees," SIAM J.
Comput 7, 4 (Nov. 1978), 465-480.
RUBIN, F "Experiments in text file
compression," Commun. ACM 19, 11
(Nov 1976), 617-623.
SAMADI,
B. "B-trees m a system w~th
multiple views," Inf. Process. Lett. 5, 4
(Oct. 1976), 107-112
SEVERENCE, D.
"Identifier search
mechnisms, a survey and generalized
model," Comput. Surv 6, 3 (Sept. 1974),
175-194.
WAGNER,
R. "Indexing design consider-
ations," IBM Syst. J. 4, (1973), 351-367.
WEDEKIND,
H. "On the selection of ac-
cess paths in a database system," in Data
base management (Proc. IFIP Working
Conf. Data Base Management) J Klim-
bie and K. Koffeman (Eds.), Elsevier/
North-Holland Publishing Co., New York,
1974, 385-397.
WIRTH,
N. Algorithms + data struc-
tures ffi programs, Prentice-Hall Inc., En-
glewood Cliffs, N J., 1976.
YAO, A. "On random 2-3 trees," Acta
Inf. 9, 2 (1978), 159-170.
Computing Surveys, VoL ll, No 2, June '"~"