Improve Google’s B-Tree Implementation with Golang Generics

Many reasons to be excited about generics in Golang. In this article, the author is going to show how, using Go generics, ScyllaDB achieved a 40% performance gain in an already well-optimized package, the Google B-Tree implementation.

B-Tree is a kind of self-balancing tree. For the purpose of this article, it’s sufficient to say that it is a collection. You can add, remove, get or iterate over its elements. The Google B-Tree is well optimized; measures are taken to make sure memory consumption is correct. There is a benchmark for every exported method, and the benchmark results show that there are zero allocations in the B-Tree code for all operations except cloning. This suggests it would be hard to further optimize using traditional techniques.

The author Michael is a software team leader working on ScyllaDB Manager, Drivers, and ScyllaDB Cloud. He’s the author of GocqlX, an object-relational mapping framework for ScyllaDB, and a contributor to many open-source projects. He holds a master’s degree in computer science and a bachelor’s in math from the University of Warsaw.

The work covered in this article was part of ScyllaDB’s long-standing partnership with the Computer Science Department at the University of Warsaw. We’ve worked on a number of projects together: integrating Parquet, an async userspace filesystem, a Kafka client for Seastar, a system for linear algebra in ScyllaDB, and a design for a new Rust driver.

Making Faster B-Trees with Golang Generics