IEEE Transactions on Software Engineering · 1987 · 39 citations · 6 references
ComputingComputer EngineeringComputer ScienceComputer ArchitectureData StructuresStorage SystemsData CompressionData Storage SystemsDynamic Data StructuresFile StorageFile SystemsB-tree IndexingB-treesBinary TreesCompact Binary SystemsDigital Data StorageSequential Access PerformanceTree Search
It is shown how a highly compact representation of binary trees can be used as the basis of two access methods for dynamic files, called BDS-trees and S-trees, respectively. Both these methods preserve key-order and offer easy and efficient sequential access. They are different in the way the compact binary trees are used for searching. With a BDS-tree the search is a digital search using binary digits. Although the S-tree search is performed on a bit-by-bit basis as well, it will appear to be slightly different. Actually, with S-trees the compact binary trees are used to represent separators at low storage costs. As a result, the fan-out, and thus performance, of a B-tree can be improved by using within each index page an S-tree for representing separators efficiently.
6
An effective way to represent quadtrees
Irene Gargantini · Communications of the ACM · 1982 · 639 citations · Full text
Rudolf Bayer, Karl Unterauer · ACM Transactions on Database Systems · 1977 · 276 citations
Andrew Chi-Chih Yao · Acta Informatica · 1978 · 207 citations
Linear hashing with partial expansions
Per-Åke Larson · Very Large Data Bases · 1980 · 115 citations