| Compact B-trees |
| Full text |
 Pdf
(928 KB)
|
| Source
|
International Conference on Management of Data
archive
Proceedings of the 1979 ACM SIGMOD international conference on Management of data
table of contents
Boston, Massachusetts
SESSION: B-trees
table of contents
Pages: 43 - 51
Year of Publication: 1979
ISBN:0-89791-001-X
|
|
Authors
|
|
| Sponsor |
|
| Publisher |
|
| Bibliometrics |
Downloads (6 Weeks): 2, Downloads (12 Months): 17, Citation Count: 2
|
|
|
 ABSTRACT
A B-tree is compact if it is minimal in number of nodes, hence has optimal space utilization, among equally capacious B-trees of the same order. The space utilization of compact B-trees is analyzed and is compared with that of noncompact B-trees and of (node)-visit-optimal B-trees, which minimize the expected number of nodes visited per key access. Compact B-trees can be as much as a factor of 2.5 more space-efficient than visit-optimal B-trees; and the node-visit cost of a compact tree is never more than 1 + the node-visit cost of an optimal tree. Finally, an in-place compactification algorithm is presented which operates in linear time in the size of the file.
REFERENCES
Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.
| |
1
|
R. Bayer and E. McCreight. Organization and maintenance of large ordered indexes. Acta Informatica 1 (3), 1972.
|
| |
2
|
R. Bayer and K. Unterauer. Prefix B-trees. IBM Technical Report RJ1796, 1976.
|
| |
3
|
|
| |
4
|
R. E. Miller, N. Pippenger, A. L. Rosenberg, and L. Snyder. Optimal 2,3-trees. SIAM Journal of Computing 8(1), February 1979, pp. 42--59.
|
| |
5
|
A. L. Rosenberg and L. Snyder. Minimal comparison 2,3-trees. SIAM Journal of Computing 7(4), November 1978, pp. 465--480.
|
| |
6
|
L. Snyder. On uniquely represented data structures. Proceedings of the 18th Annual Conference on the Foundations of Computer Science, 1977.
|
| |
7
|
A. C. Yao. On random 2,3-trees. Acta Informatica 9:159--170, 1978.
|
CITED BY 2
|
|
David M. Arnow , Aaron M. Tenenbaum , Connie Wu, P-trees: storage efficient multiway trees, Proceedings of the 8th annual international ACM SIGIR conference on Research and development in information retrieval, p.111-121, June 05-07, 1985, Montreal, Quebec, Canada
|
|
|
|
|
Adobe Acrobat
QuickTime
Windows Media Player
Real Player
