Abstract

An earlier survey of modern b-tree techniques is now over a decade old. Obviously, it lacks descriptions of techniques invented and published during this time. Just as importantly, it lacks descriptions of insertion-optimized b-trees in the forms of log-structured merge-trees and stepped-merge forests, which seem to have become almost as ubiquitous as b-trees themselves. This monograph complements the earlier survey in order to bring the combined contents up-to-date.

More Modern B-Tree Techniques

B-tree indexes have been ubiquitous in databases for decades. Their contribution to efficient database query processing can hardly be overstated. B-tree indexes have been used in a wide variety of computing systems from handheld devices to mainframes and server farms. Over the years, many techniques have been added to the basic design in order to improve efficiency or to add functionality. Examples include separation of updates to structure or contents, utility operations such as non-logged yet transactional index creation, and robust query processing such as graceful degradation during index-to-index navigation.

An earlier survey of modern b-tree techniques, published in 2011, has been widely used for education and reference. Unfortunately, it omits some of the techniques known then and of course those invented since. This monograph is intended to complement the earlier survey and to bring the combined contents more up-to-date. This monograph adds new techniques for tree structures and a few new techniques in query processing, and log-structured merge-forests and stepped-merge forests are now covered. Lastly, concurrency control and in-memory b-trees, from thread-private via shared-but-transient to persistent are also dealt with in this updated work.