kdbush

KDBush is a high-performance, static spatial index for 2D points based on a flat KD-tree.

Key Characteristics:

• Points Only: Unlike RBush, it does not support rectangles.
• Static: Once you call index.finish(), you cannot add or remove items. This allows for a highly optimized, compact memory footprint.
• Memory Efficient: The index is stored as a single ArrayBuffer, making it extremely fast to transfer between threads (using postMessage) or to save to a file.
• Performance: It offers faster indexing and search with lower memory usage compared to RBush or Flatbush (when indexing points).

You can install KDBush via NPM for Node.js environments or use it directly in the browser via CDN.

NPM Installation:

npm install kdbush

Browser (ESM):

<script type="module">
    import KDBush from 'https://cdn.jsdelivr.net/npm/kdbush/+esm';
</script>

Browser (Global Variable):

<script src="https://cdn.jsdelivr.net/npm/kdbush"></script>

To use KDBush, you must initialize it with the total number of items you intend to index, add the points one by one, and then call finish() to finalize the index.

// 1. Initialize with the expected number of items
const index = new KDBush(1000);

// 2. Add points (returns an incremental ID)
for (const {x, y} of items) {
    index.add(x, y);
}

// 3. Finalize the index (required before querying)
index.finish();

Because KDBush stores its data in a single ArrayBuffer (accessible via index.data), it is highly efficient for multi-threaded environments or persistence.

To transfer to a Worker:

postMessage(index.data, [index.data]);

To reconstruct from raw data: Use KDBush.from(data) where data is an ArrayBuffer or SharedArrayBuffer.

// Reconstruct from received data
const index = KDBush.from(e.data);

Once an index is finalized, you can perform two types of spatial queries:

1. Bounding Box Query (range): Finds all items within a rectangle defined by minX, minY, maxX, maxY.
2. Radius Query (within): Finds all items within a specific radius from a point (x, y).

Both methods return an array of indices that correspond to the order in which items were added via index.add().

// Bounding box query
const foundIds = index.range(minX, minY, maxX, maxY);

// Radius query
const neighborIds = index.within(x, y, 5);

If you want to avoid the overhead of creating a new array during every query, use withinInto. This method writes matching indices into a pre-allocated container.

• Typed Arrays: If you provide a typed array sized to your expected upper bound, the operation is allocation-free.
• Plain Arrays: If you provide a standard Array, it will grow as needed.

Returns the number of matches found.

// Using a pre-allocated typed array for performance
const out = new Uint32Array(100);
const count = index.withinInto(x, y, 5, out);

The new KDBush(numItems[, nodeSize, ArrayType, ArrayBufferType]) constructor allows fine-tuning of the index structure.

The following properties are available on a KDBush instance:

• data: The ArrayBuffer (or SharedArrayBuffer) holding the index data.
• numItems: The number of stored items.
• nodeSize: The number of items in a KD-tree node.
• ArrayType: The array type used for internal coordinate storage.
• IndexArrayType: The array type used for internal item indices storage.

The static from(data) method allows you to reconstruct a KDBush instance from a serialized ArrayBuffer or SharedArrayBuffer. This is useful for loading pre-built indexes from disk or network.

Parameters:

• data (ArrayBufferLike): The raw buffer containing the KDBush serialized data.

Throws:

• Error if data is not an ArrayBuffer or SharedArrayBuffer.
• Error if the magic number does not match the KDBush format (0xdb).
• Error if the data version does not match the current library version.

// Assuming 'buffer' is an ArrayBuffer loaded from a file
const index = KDBush.from(buffer);

The finish() method performs the KD-tree sorting required for efficient spatial searching. This method must be called once all points have been added via add() and before calling range() or within().

Throws:

• Error if the number of items added does not match the numItems specified during construction.

index.finish();

The range(minX, minY, maxX, maxY) method searches the index for all points located within the specified rectangular bounding box. It returns an array of indices corresponding to the found items.

Requirements:

• finish() must have been called on the index instance before searching.

// Returns indices of points where minX <= x <= maxX and minY <= y <= maxY
const results = index.range(0, 0, 100, 100);