Sequential retrieval of B-trees and a file structure with a dense B-tree index

Abstract

A simple fast method is given for sequentially retrieving all the records in a B-tree. A file structure for database is proposed. The records in its primary data file are sorted according to the key order. A B-tree is used as its dense index. It is easy to insert, delete or search a record, and it is also convenient to retrieve records in the sequential order of the keys. The merits and efficiencies of these methods or structures are discussed in detail.

Keywords

B-tree / B⁺-tree / data structure / file organization / retrieval method

References

[1] Ullman J D. Principles of database systems. Computer Science Press, 1980

[2] YaoS B. Fundamentals of database systems. Computer Eng and Appl, 1981, 8–10: 1-94(in Chinese)

[3] BayerR, McCreightE. Organizations and maintenance of large ordered indexes. Acta Informatica, 1972, 1(3): 173-189

[4] ComerD. The ubiquitous B-tree. ACM Computing Surveys, 1979, 11(2): 121-137

[5] Black J P, Taylor D J, Morgan D E. A robust B-tree implementation. Proc Info Conf Software Eng, 1981. 63–70

[6] HeldG, StonebrakerM. B-tree reexamined. Commun ACM, 1978, 21(2): 139-143

[7] YaoA C. On random 2–3 tree. Acta Informatica, 1978, 9(2): 159-170

[8] Baeza-YatesR A, LarsonP A. Performance of B⁺-trees with partial expansions. IEEE Trans Knowledge and Date Eng, 1989, 1(2): 248-257

[9] FujimuraK, JaloteP. On robustness of B-trees. IEEE Trans Knowledge and Date Eng, 1993, 5(3): 530-533

[10] TaylorD J, BlackJ P. A locally correctable B-tree implementation. The Comput J, 1986, 29(3): 269-276

[11] Pollari-MalmiK, Soisalon-SoininenE, YlonenT. Concurrency control in B-trees with batch updates. IEEE Trans Knowledge and Date Eng, 1996, 8(6): 975-984

[12] SnyderL. On B-trees reexamined. Commun ACM, 1978, 21(7): 594-603

[13] Lanin V, Shahsa D. A symmetric concurrent B-tree algorithm. Proc Fall Joint Computer Conf, 1986. 380–389

[14] Baeza-YatesR A. The expected behavior of B⁺-tree. Acta Informatica, 1989, 26: 439-471