# Workiva/go-datastructures: a Go library of interval trees, bitarrays and lock-free queues

> Workiva/go-datastructures is a collection of threadsafe Go data structures rather than a single library. Its interval tree, bitarray, queue and trie packages are the parts worth evaluating first.

**Workiva/go-datastructures** — A collection of useful, performant, and threadsafe Go datastructures.

- Repository: https://github.com/Workiva/go-datastructures
- Stars: 7,965 · Forks: 844
- Language: Go
- License: Apache-2.0
- Published: 2026-09-22 · Updated: 2026-09-22 · Language: en
- Canonical page: https://hysenlabs.com/projects/workiva-go-datastructures

## What Workiva/go-datastructures actually is

This is not one data structure with one API. It is a module that bundles roughly two dozen packages, each with its own subfolder at the repository root: augmentedtree, bitarray, btree, cache, fibheap, futures, graph, hashmap, list, numerics, queue, rangetree, rtree, set, slice, sort, threadsafe, tree and trie. The README describes the whole thing as "a collection of useful, performant, and threadsafe Go datastructures."

The audience is the Go engineer who has hit a wall with the standard library. If you need to know which stored intervals overlap a query range, or you need to track membership of millions of uint64 identifiers without paying hashmap costs, or you need a broadcast primitive that reaches every listener rather than whichever goroutine wins the channel race, this module has a package for it. If you need a map, a slice or a heap, it does not, and you should not be here.

One framing detail matters for evaluation. Several packages are described as work in progress or as experiments. The numerics package is called "early work" on nonlinear optimization. The fast integer hashmap is documented as faster than the native Go implementation only up to a few million integers. Treat the module as a set of independent tools, not as a coherent product with a single quality bar.

## The interval tree in augmentedtree, and why bit arrays decide intersection

The augmentedtree package implements an interval tree for collision detection across n-dimensional ranges. The README states it is built as a red-black augmented tree, and that extra dimensions are handled by simultaneous inserts and queries rather than by nesting trees. That design saves space, and the README is candid that it "may result in suboptimal time complexity."

Intersection itself is determined using bit arrays. In a single dimension, the README says inserts, deletes and queries should run in O(log n) time. The n-dimensional path is where the trade-off lives: you get one tree instead of d trees, and you pay for it in query cost as d grows.

This is the package most likely to justify pulling in the module. A red-black tree with interval augmentation is fiddly to write correctly, and collision queries over ranges are a common need in scheduling, resource allocation and time-series overlap checks. The limitation is that the README does not document the exact complexity for the multi-dimensional case, only that it is suboptimal. If your ranges are genuinely multi-dimensional and hot, that gap is something you have to measure yourself in the package's own tests.

## Bitarrays, sparse bitmaps and the uint64 identifier requirement

The bitarray package exists to answer existence questions without hashing. The constraint is stated plainly: entities must have a uint64 unique identifier. Two implementations ship, a regular one and a sparse one. The sparse version "saves a great deal of space but insertions are O(log n)."

The package also provides bitmaps of length 32 and 64 that store bits in unsigned integers rather than arrays. The README claims increased speed and O(1) for all operations on those. That is the part of the package with the cleanest complexity story.

The interface is not just Set and Get. The README mentions functions on the BitArray interface for detecting intersection between two bitarrays. That is the real use case: you have two sets of identifiers, you want to know whether they overlap, and you want to answer without building two maps. If your identifiers are strings or UUIDs, this package is the wrong tool and you should look at hashmap instead.

## Installing it and running a first queue

The module path is declared in go.mod as github.com/Workiva/go-datastructures, and the module requires Go 1.15. The repository also ships a Dockerfile that builds from the golang:1.16-alpine3.13 image, runs go mod vendor inside /go/src/github.com/Workiva/go-datastructures/, and then produces a scratch stage. That Dockerfile is a build fixture rather than an installation path for consumers, so the practical way in is the module path itself.

```dockerfile
FROM golang:1.16-alpine3.13 AS build-go

ARG GIT_SSH_KEY
ARG KNOWN_HOSTS_CONTENT
WORKDIR /go/src/github.com/Workiva/go-datastructures/
ADD . /go/src/github.com/Workiva/go-datastructures/

ARG GOPATH=/go/
ENV PATH $GOPATH/bin:$PATH
RUN echo "Starting the script section" && \
    go mod vendor && \
    echo "script section completed"

ARG BUILD_ARTIFACTS_DEPENDENCIES=/go/src/github.com/Workiva/go-datastructures/go.mod

FROM scratch
```

The queue package contains a normal queue and a priority queue. The README states both never block on send, both grow as much as necessary, and both only return errors when you push to a disposed queue rather than panicking the way a send on a closed channel would. That last property is the reason to choose it over a channel in code where a producer might outlive a consumer.

The package also includes a MPMC threadsafe ring buffer, described as a block full/empty queue that returns a blocked thread if the queue is disposed while that thread is waiting. The README says threadsafety there is achieved using only CAS operations, and that benchmarks live in that package. If you want to see the intended usage before writing your own, the package subfolder is where the examples and tests are, not the root README.

## Where the collection is weak, and the cases to avoid

The README is unusually direct about weak spots, which is useful but also a warning. The priority queue is described as "somewhat slow currently and targeted for an update to a Fibonacci heap." A structure with a known pending rewrite is not one to build a latency-sensitive path on.

The skiplist section is blunter still. It says that in testing the performance of the skip list is "often far worse than the guaranteed log n time of a BBST," and explains why: tall nodes cast shadows, particularly when large bit sizes are required. If you were considering the skiplist as a simpler alternative to a balanced tree, the README itself argues against that.

The Fibonacci heap comes with its own caveat. Constant-time find-minimum, insert and merge, amortized constant decrease-key, and O(log n) delete or dequeue-minimum are the theoretical properties. The README then says that in practice the constant factors are large and that Fibonacci heaps could be slower than pairing heaps depending on usage. It also states the heap has not been designed for thread-safety, so the module's headline promise does not extend to every package.

The Set package is a fourth boundary. The README calls it "very simple," accepting interface{} items with only a few methods, and points readers who need something richer to xtgo/set and goware/set. That is an admission that this package is a convenience, not a competitive implementation.

## How it compares with the Go standard library and container packages

The honest comparison is not against another third-party library. It is against what Go ships. For a map keyed by integers, the native implementation is the baseline, and the README concedes the point: the fast integer hashmap in this module is faster than native Go only up to a few million integers, and beyond that "the native implementation is faster." The stated plan is a B-tree implementation for scale, which has not happened.

For sorting, the sort package here implements a multithreaded bucket sort that the README claims can be up to 3x faster than the native Go sort, with buckets merged by symmetrical decomposition. That is a genuine difference in approach: parallelism across buckets rather than a single-threaded comparison sort. It is also the kind of claim that depends entirely on your data distribution and core count, and the README does not qualify it.

For ordered data, Go's container/heap gives you a heap interface you implement yourself. This module gives you a concrete Fibonacci heap with a documented decrease-key cost. The difference is the decrease-key operation, which is what makes Dijkstra and Prim's algorithms hit their theoretical bounds. If your algorithm never decreases a key, the standard heap is simpler and has smaller constants, and the README's own note about large constant factors supports that reading.

## Maintenance, licence and what upgrading costs you

The repository is not archived, and the last push was on 2026-07-31. Releases are infrequent rather than continuous: v1.1.7 on 2025-10-31, v1.1.6 on 2025-09-02, and v1.1.5 on 2024-05-16. The gap between v1.1.5 and v1.1.6 is over a year, which tells you the release cadence is driven by occasional fixes rather than a steady stream of feature work.

The go.mod file declares go 1.15 and requires github.com/stretchr/testify v1.7.0 and github.com/tinylib/msgp v1.1.5. A go 1.15 directive does not prevent use with a newer toolchain, but it does mean the module was not written against newer language features, and your build will enforce whichever Go version your own module declares.

The licence is Apache-2.0, which permits commercial use and modification and includes an explicit patent grant. That matters for a library you vendor into a product. It also means you carry the obligation to retain the licence and notices, and to state significant changes if you fork. The repository does not ship a NOTICE file at the root, so there is nothing extra to propagate beyond the LICENSE file itself. This is a description of the licence terms, not legal advice; have counsel review anything you redistribute.

Upgrade cost is low in one sense and uncertain in another. There is no migration tooling and no versioned API policy documented in the README, so a minor bump could change a package you depend on. Pin the version and read the diff between tags before moving.

## Conclusion

Adopt Workiva/go-datastructures when you need a specific structure the standard library lacks, such as an interval tree, a sparse bitarray, or a queue that never blocks on send, and when you can read the package documentation before depending on it. Do not adopt it as a general-purpose replacement for Go's built-in map, slice or container/heap, and do not treat the collection as uniformly mature: the README states the priority queue is targeted for a rewrite and that the skip list often performs far worse than a balanced tree. Before you commit, verify the module path resolves at the version you pin, check that each package you import is documented in its own subfolder, and confirm the Go version your toolchain enforces against the go 1.15 directive in go.mod.

## FAQ

### How do I install Workiva/go-datastructures?

The module path declared in go.mod is github.com/Workiva/go-datastructures, and the module requires Go 1.15. The repository also ships a Dockerfile that vendors the module inside a golang:1.16-alpine3.13 build stage.

### What data structures does Workiva/go-datastructures provide?

The repository root contains packages for an augmented interval tree, bitarrays and bitmaps, futures, queues and a ring buffer, a Fibonacci heap, a range tree, a set, threadsafe helpers, an immutable AVL tree, X-Fast and Y-Fast tries, a fast integer hashmap, a skiplist, a multithreaded sort, and numerics work.

### Is the Fibonacci heap in Workiva/go-datastructures threadsafe?

No. The README states the heap has not been designed for thread-safety, even though the module as a whole is described as a collection of threadsafe data structures. You would need to serialize access yourself.

### Is the priority queue in Workiva/go-datastructures fast?

The README describes the priority queue as somewhat slow currently and targeted for an update to a Fibonacci heap. It also states that the priority queue allows items to be placed in priority order inside the queue.

## Sources

- [Issues](https://github.com/Workiva/go-datastructures/issues)
- [License: Apache-2.0](https://github.com/Workiva/go-datastructures/blob/master/LICENSE)
- [README](https://github.com/Workiva/go-datastructures/blob/master/README.md)
- [Releases](https://github.com/Workiva/go-datastructures/releases)
- [Workiva/go-datastructures on GitHub](https://github.com/Workiva/go-datastructures)

---

Hysen Labs editorial analysis, written from the project's own repository and release notes. Cite the canonical page: https://hysenlabs.com/projects/workiva-go-datastructures