Our great sponsors
-
-
WorkOS
The modern identity platform for B2B SaaS. The APIs are flexible and easy-to-use, supporting authentication, user identity, and complex enterprise features like SSO and SCIM provisioning.
-
github.com/ajwerner/btree provides go1.18 generic implementations of CoW btree data structures including regular a regular map/set, order-statistic trees, and interval trees all backed by a shared, generic augmented btree implementation. Given go 1.18 hasn't been released yet and it hasn't been heavily tested, don't use it yet. Benchmarks and a deeper discussion on the patterns and experience to follow.
Recently a colleague, Nathan, reflecting on CockroachDB, remarked (paraphrased from memory) that the key data structure is the interval btree. The story of Nathan’s addition of the first interval btree to cockroach and the power of copy-on-write data structures is worthy of its own blog post for another day. It’s Nathan’s hand-specialization of that data structure that provided the basis (and tests) for the generalization I’ll be presenting here. The reason for this specialization was as much for the performance wins of avoiding excessive allocations, pointer chasing, and cost of type assertions when using interface boxing.
As we all know, generics are coming in go1.18. So what better time for an experience report building some real things with it? This post will explore github.com/ajwerner/btree, a library leveraging go1.18's parametric polymorphism to build an abstract augmented btree which offers rich core functionality and easy extensibility.