The paper entitled "The ubiquitous B-tree" by Comer was published in ACM Computing Surveys in 1979. Actually, the keyword "B-tree" was standing as a generic term for a whole family of variations, namely the B*-tree, the B+-tree and several other variants. The title of the paper might have seemed provocative at that time. However, it represented a big truth, which is still valid now, because all textbooks on databases or data structures devote a considerable number of pages to explain definitions, characteristics, and basic procedures for searches, inserts, and deletes on B-trees. Moreover, B+-trees are not just a theoretical notion. On the contrary, for years they have been the de facto standard access method in all prototype and commercial relational systems for typical transaction processing applications, although one could observe that some quite more elegant and efficient structures have appeared in the literature. (Download Chapter1)
The survey by Gaede and Guenther annotates a vast list of citations related to multi-dimensional access methods and, in particular, refers to R-trees to a significant extent. In this chapter, we are further focusing on the family of R-trees by enlightening the similarities and differences, advantages and disadvantages of the variations in a more exhaustive manner. As the number of variants that have appeared in the literature is large, we group them according to the special characteristics of the assumed environment or application, and we examine the members of each group. In this chapter, we present dynamic versions of the R-tree, where the objects are inserted on a one-by-one basis, as opposed to the case where a special packing technique can be applied to insert an a priori known static set of objects into the structure by optimizing the storage overhead and the retrieval performance. The latter case will be examined in the next chapter. In simple words, here we focus on the way dynamic insertions and splits are performed in assorted R-tree variants. (Download Chapter2)