ZBush

A very fast spatial index for 2D points based on a Z-Order space filling curve and BIGMIN search space pruning.

Installation

We publish this project as the package zbush on NPM

npm install zbush

Usage

const index = new ZBush();

for (const {x, y} of items) {
  index.add(x, y);
}

index.finish();

const foundIds = index.range(minX, minY, maxX, maxY);

Note: at the moment the x and y coordinates of points added must be of non-negative integral type and fit into 32-bit, i.e. in [0, 2^32-1]. We might relax this constraint in the future.

How It Works

We sort 2d points along a Z-order space-filling curve and use an optimization ("BIGMIN") to skip over irrelevant data when walking the curve.

| Z-curve with query bounding box | Z-curve with BIGMIN skipping | |-|-| | | |

If you are interested in a high-level overview check out my blog post. The ideas implemented here originated as experiments in tinygraph.org but really go back to the 80s.

For experiments, context, implementation details, and ideas for further improvements

• https://github.com/tinygraph/tinygraph/issues/22
• https://github.com/tinygraph/tinygraph/pull/68
• https://github.com/tinygraph/tinygraph/issues/71
• https://github.com/tinygraph/tinygraph/issues/70
• https://github.com/tinygraph/tinygraph/blob/main/tinygraph/tinygraph-zorder.c
• https://github.com/tinygraph/tinygraph/blob/main/tinygraph/tinygraph-index.c

Note: The core ideas implemented here are very flexible and allow e.g. to index more dimensions than two, indexing more shapes and not just points, have a fast WebAssembly version, and more. If you come across limitations or have use-cases not covered here, please do open an issue and let us know.

Similar

Similar projects for point indices using R-Tree or KD-Tree data structures

• https://github.com/mourner/rbush
• https://github.com/mourner/kdbush
• https://github.com/mourner/flatbush

Release

Checklist

• [ ] Bump version in package.json
• [ ] Tag the release git tag vx.y.z -a
• [ ] Push the tag git push origin vx.y.z

There is a GitHub Action publishing to the zbush package on NPM with provenance attestation.

License

Copyright © 2025 Daniel J. H.

Distributed under the MIT License (MIT).