A very fast spatial index for 2D points based on a Z-Order space filling curve and BIGMIN search space pruning.
We publish this project as the package zbush on NPM
npm install zbush
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.
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 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
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.
Copyright © 2025 Daniel J. H.
Distributed under the MIT License (MIT).