node-rtree - 高性能Node.js空间索引库

一个基于TypeScript实现的高性能RTree空间索引库，专为Node.js环境优化，核心聚焦极致的插入/查询速度与低内存占用，同时支持ESM（ES模块）和CommonJS两种模块系统，可无缝适配各类Node.js项目架构，适用于实时空间数据处理场景（如传感器坐标管理、游戏碰撞检测、GIS地理信息系统、地图POI索引等）。

特性

- 双模块系统支持：同时提供ESM和CommonJS两种格式，既能融入现代前端/Node.js项目，也可兼容传统CommonJS架构
- 极致性能表现：批量插入速率达80万+条/秒，点查询耗时<0.2毫秒，可满足高频实时数据处理需求
- Node.js原生优化：针对Node.js内存管理机制与异步操作特性优化，剔除浏览器环境冗余代码
- 高效内存利用：采用紧凑节点结构（基于Float32Array存储）+ 临时数组池设计，内存占用较传统RTree降低40%
- 完整类型安全：内置TypeScript类型定义，支持IDE自动提示与类型校验，避免运行时类型错误
- 轻量无依赖：无任何第三方依赖，压缩后体积仅15KB，降低项目部署与维护成本
- 核心功能完备：支持单条数据插入（insert）、批量数据插入（inserts）、范围查询（query）、点查询（queryPoint）

安装

``bash

npm（推荐）

npm install node-rtree --save

yarn

yarn add node-rtree
`

快速开始

$3

`typescript
import { RTree, createBBox } from 'node-rtree';

// 定义空间数据类型（TypeScript可选）
interface SpatialData {
id: string;
name: string;
}

// 创建RTree实例
const rtree = new RTree();

// 单条插入数据
rtree.insert(createBBox(0, 0, 100, 100), { id: '1', name: '示例数据' });

// 批量插入数据（比多次调用insert快3-4倍）
rtree.inserts([
{ bbox: createBBox(50, 50, 80, 80), data: { id: '2', name: '批量数据1' } },
{ bbox: createBBox(150, 150, 60, 60), data: { id: '3', name: '批量数据2' } }
]);

// 执行范围查询（获取与[0,0,200,200]重叠的数据）
const rangeResults = rtree.query(createBBox(0, 0, 200, 200));
console.log('范围查询结果:', rangeResults);
`

$3


`javascript
const { RTree, createBBox } = require('node-rtree');

// 创建RTree实例
const rtree = new RTree();

// 单条插入数据
rtree.insert(createBBox(0, 0, 100, 100), { id: '1', name: '示例数据' });

// 执行点查询（获取包含(75,75)点的数据）
const pointResults = rtree.queryPoint(75, 75);
console.log('点查询结果:', pointResults);
`




浏览器环境支持


node-rtree核心代码完全兼容浏览器环境，其内部仅依赖标准JavaScript特性（如Float32Array）与TypeScript类型系统，不依赖任何Node.js特有API（如fs、os等），可直接用于前端项目。

$3

#### 1. 通过构建工具引入（推荐，如Webpack/Vite/Rollup）
前端项目可直接按ESM方式导入，构建工具会自动处理模块格式转换：
`javascript
import { RTree, createBBox } from 'node-rtree';

// 初始化RTree并使用
const rtree = new RTree();
rtree.insert(createBBox(10, 20, 30, 40), { name: '前端空间数据' });
`

#### 2. 直接通过HTML引入（需先转换为UMD格式）
默认输出的ESM/CommonJS格式无法直接通过

`

$3


1. 内存限制：浏览器对单页面内存限制通常严于Node.js，处理超大规模数据（如100万+条）时，建议分批次插入并及时清理无用数据，避免内存溢出。
2. 主线程阻塞：浏览器中JavaScript运行在主线程，大规模数据处理可能导致页面卡顿，建议配合Web Worker实现异步处理：
`javascript
// 主线程代码
const worker = new Worker('rtree-worker.js');
// 向Worker发送插入指令
worker.postMessage({
type: 'insert',
bbox: [0, 0, 100, 100],
data: { id: '1' }
});

// rtree-worker.js（Web Worker脚本）
import { RTree, createBBox } from 'node-rtree';
const rtree = new RTree();

self.onmessage = (e) => {
if (e.data.type === 'insert') {
rtree.insert(createBBox(...e.data.bbox), e.data.data);
}
};
`
3. 兼容性范围：支持所有现代浏览器（Chrome 60+、Firefox 55+、Safari 11+），不支持IE浏览器（因依赖Float32Array与ES6类语法）。




模块兼容性说明


node-rtree采用双格式打包，确保在不同类型项目中均能正常使用：

| 项目类型 | 模块格式 | 导入方式 | 包内对应文件 |
|------------------------|------------|-----------------------------------|----------------------------|
| 现代Node.js（v14+） | ESM | import { RTree } from 'node-rtree' | dist/index.mjs |
| 传统Node.js项目 | CommonJS | const { RTree } = require('node-rtree') | dist/index.js |
| TypeScript项目 | 自动适配 | 同上（根据tsconfig配置自动识别） | dist/index.d.ts（类型声明）|

注意：TypeScript项目需确保tsconfig.json中moduleResolution配置为Node16、NodeNext或Classic，否则可能出现类型解析错误。




API 文档

$3


#### RTreeOptions（构造函数配置项）
| 参数名 | 类型 | 默认值 | 说明 |
|-----------------|-----------|--------|----------------------------------------------------------------------|
| maxEntries | number | 8 | 每个节点允许的最大条目数（需≥2，推荐8-16：值越大插入越快，值越小查询剪枝效果越好） |
| strictMode | boolean | false | 是否启用严格模式（启用后会校验边界矩形合法性，如width≥0，牺牲性能换取安全性） |
| tempPoolSize | number | 20 | 临时数组池大小（减少Float32Array动态创建开销，推荐20-50，平衡内存与效率） |

#### createBBox(x: number, y: number, width: number, height: number): Float32Array
创建RTree所需的标准边界矩形：
- 参数：
- x：边界矩形左上角X坐标
- y：边界矩形左上角Y坐标
- width：边界矩形宽度（需≥0）
- height：边界矩形高度（需≥0）
- 返回值：Float32Array类型，格式为[x, y, width, height]，内存占用仅16字节。




$3


#### constructor(options?: RTreeOptions)
创建RTree实例，支持通过泛型T定义关联数据的类型（TypeScript特性）。

#### insert(bbox: Float32Array, data: T): void
单条插入空间数据，适用于零散数据插入场景。

#### inserts(entries: Array<{ bbox: Float32Array; data: T }>): void
批量插入空间数据，内部优化了节点分裂与内存分配逻辑，比多次调用insert快3-4倍，适用于大规模数据初始化（如导入10万条地图POI）。

#### query(bbox: Float32Array): T[]
范围查询：返回与指定边界矩形相交的所有关联数据，结果为数组（顺序与插入顺序无关）。

#### queryPoint(x: number, y: number): T[]
点查询：返回包含指定点的所有关联数据，适用于坐标定位场景（如鼠标点击检测）。

#### size(): number
获取当前RTree中存储的数据总数，O(1)时间复杂度，无性能开销。

#### clear(): void`
清空RTree中所有数据，保留预分配的临时数组池与节点结构，避免重建实例的开销。

性能测试

基于 Node.js 18.17.0 + Intel i7-12700H（14核）+ 32GB DDR5 环境，测试数据为随机分布的50x50像素边界矩形：

| 操作 | 数据规模 | 平均耗时 | 性能指标 | 内存占用（RSS） |
|-----------------|----------|----------|------------------------|-----------------|
| 批量插入（inserts） | 10万条 | 118ms | 847,458 条/秒 | 89.2MB |
| 批量插入（inserts） | 100万条 | 1.25s | 800,000 条/秒 | 485MB |
| 点查询 | 10万条 | 0.12ms | 8,333 次/秒 | - |

许可证

MIT License - 详见 LICENSE 文件，允许商用、修改与分发，无需额外授权。