IDB-RBush is a high-performance JavaScript library for 2D spatial indexing of points and rectangles in an IndexedDB object store. It's based on an optimized R-tree data structure with bulk insertion support.
Spatial index is a special data structure for points and rectangles that allows you to perform queries like "all items within this bounding box" very efficiently (e.g. hundreds of times faster than looping over all items). It's most commonly used in maps and data visualizations.
The demos contain visualization of trees generated from 50k bulk-loaded random points.
Install with NPM (npm install idb-rbush).
It's important, that the IDBObjectStore has the keyPath set to 'id'.
const request = self.indexedDB.open(dbName)
request.onupgradeneeded = () => {
const db = request.result
db.createObjectStore(objectStoreName, { keyPath: 'id' })
}For creating a tree you need a successfully opened IDBDatabase connection object together with an unique name of an IDBObjectStore, in which IDB-RBush will persist your R-tree data structure. If the function finds an existing root node, the persisted structure will be reused. Otherwise a new root node will be created.
(async () => {
try {
const tree = await rbush(db, objectStoreName)
} catch (error) {
// handle error
}
})()An optional argument to rbush defines the maximum number of entries in a tree node.
9 (used by default) is a reasonable choice for most applications.
Higher value means faster insertion and slower search, and vice versa.
(async () => {
try {
const tree = await rbush(db, objectStoreName, 16)
} catch (error) {
// handle error
}
})()Insert an item:
(async () => {
const item = {
bbox: [20, 40, 30, 50], // mandatory
foo: 'bar' // any additional data
}
try {
await tree.insert(item)
} catch (error) {
// handle error
}
})()Remove a previously inserted item:
(async () => {
try {
await tree.remove(item)
} catch (error) {
// handle error
}
})()By default, IDB-RBush removes objects by reference.
However, you can pass a custom equals function to compare by value for removal,
which is useful when you only have a copy of the object you need removed (e.g. loaded from server):
(async () => {
try {
await tree.remove(itemCopy, (a, b) => {
return a.id === b.id
})
} catch (error) {
// handle error
}
})()Remove all items:
(async () => {
try {
await tree.clear()
} catch (error) {
// handle error
}
})()If you're indexing a static list of points (you don't need to add/remove points after indexing), you should use kdbush which performs point indexing 5-8x faster than IDB-RBush.
Bulk-insert the given data into the tree:
(async () => {
try {
await tree.load([item1, item2, ...])
} catch (error) {
// handle error
}
})()Bulk insertion is usually ~2-3 times faster than inserting items one by one. After bulk loading (bulk insertion into an empty tree), subsequent query performance is also ~20-30% better.
Note that when you do bulk insertion into an existing tree, it bulk-loads the given data into a separate tree and inserts the smaller tree into the larger tree. This means that bulk insertion works very well for clustered data (where items in one update are close to each other), but makes query performance worse if the data is scattered.
(async () => {
try {
const result = await tree.search([40, 20, 80, 70])
} catch (error) {
// handle error
}
})()Returns an array of data items (points or rectangles) that the given bounding box intersects.
Note that the search method accepts a bounding box in [minX, minY, maxX, maxY] format
regardless of the format specified in the constructor (which only affects inserted objects).
(async () => {
try {
const allItems = await tree.all()
} catch (error) {
// handle error
}
})()Returns all items of the tree.
// export the internal data object tree
var treeData = tree.toJSON()
// import previously exported data
var tree = rbush(9).fromJSON(treeData)Importing and exporting as JSON allows you to use RBush on both the server (using Node.js) and the browser combined, e.g. first indexing the data on the server and and then importing the resulting tree data on the client for searching.
Note that the nodeSize option passed to the constructor must be the same in both trees for export/import to work properly.
For "k nearest neighbors around a point" type of queries for IDB-RBush, check out rbush-knn.
- single insertion: non-recursive R-tree insertion with overlap minimizing split routine from R*-tree (split is very effective in JS, while other R*-tree modifications like reinsertion on overflow and overlap minimizing subtree search are too slow and not worth it)
- single deletion: non-recursive R-tree deletion using depth-first tree traversal with free-at-empty strategy (entries in underflowed nodes are not reinserted, instead underflowed nodes are kept in the tree and deleted only when empty, which is a good compromise of query vs removal performance)
- bulk loading: OMT algorithm (Overlap Minimizing Top-down Bulk Loading) combined with Floyd–Rivest selection algorithm
- bulk insertion: STLT algorithm (Small-Tree-Large-Tree)
- search: standard non-recursive R-tree search
- R-trees: a Dynamic Index Structure For Spatial Searching
- The R*-tree: An Efficient and Robust Access Method for Points and Rectangles+
- OMT: Overlap Minimizing Top-down Bulk Loading Algorithm for R-tree
- Bulk Insertions into R-Trees Using the Small-Tree-Large-Tree Approach
- R-Trees: Theory and Applications (book)
npm install # install dependencies
npm test # check the code with JSHint and run tests
npm run cov # report test coverage (with more detailed report in coverage/lcov-report/index.html)IDB-RBush should run on all major browsers with IndexedDB support. It uses various native ES2015 features: promise, arrow function, spread operator, proxy, reflect. And the ES2017 async/await.
- Breaking: Initial fork from rbush to implement a variant with IndexedDB support.
- Breaking: Changed the bbox format again from
{minX: 20, minY: 40, maxX: 30, maxY: 50}tobbox: [20, 40, 30, 50]. Matching the GeoJSON RFC 7946 spec and reduce the property access over the proxy objects. - Breaking: New promise-based API calls for all exported functions because of the IndexedDB asynchronous API.
- Breaking: Now every node in the R-tree data structure has an unique UUID based on this GitHubGist. The
idof the root node is always00000000-0000-0000-0000-000000000000. - Breaking: Removed
collidesmethod from version 1.4.0 -> no use case. - Breaking: Removed the ability to customize the internal data format.
- Breaking: Removed the method chaining ability because of simplification.
- Added
fake-indexeddbfor tests running in Node.js. - Added Typings Definition file (index.d.ts).
- Reworked README documentation.
- Added default export for better ES6 modules / transpiler support.
- Fixed browser builds in NPM.
- Breaking: changed the default format of inserted items from
[20, 40, 30, 50]to{minX: 20, minY: 40, maxX: 30, maxY: 50}. - Breaking: changed the
searchmethod argument format from[20, 40, 30, 50]to{minX: 20, minY: 40, maxX: 30, maxY: 50}. - Improved performance by up to 30%.
- Added
equalsFnoptional argument toremoveto be able to remove by value rather than by reference. - Changed the source code to use CommonJS module format. Browser builds are automatically built and published to NPM.
- Quickselect algorithm (used internally) is now a separate module.
- Fixed an error when inserting many empty bounding boxes.
- 50% faster insertion.
- Fixed insertion in IE8.
- Added
collidesmethod for fast collision detection.
- Improved bulk insertion performance for a large number of items (e.g. up to 100% for inserting a million items).
- Fixed performance regression for high node sizes.
- Improved bulk insertion performance by ~60-70%.
- Improved insertion performance by ~40%.
- Improved search performance by ~30%.
- Improved removal performance by ~50%. #18
- Significantly improved search performance (especially on large-bbox queries — up to 3x faster). #11
- Added
allmethod for getting all of the tree items. #11 - Made
toBBox,compareMinX,compareMinYmethods public, made it possible to avoid Content Security Policy issues by overriding them for custom format. #14 #12
- Fixed a bug where insertion failed on a tree that had all items removed previously. #10
- Added Web Workers support. #9
- Added AMD support. #8
- Eliminated recursion when recalculating node bboxes (on insert, remove, load).
First fully functional RBush release.