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）

安装

# npm（推荐）
npm install node-rtree --save

# yarn
yarn add node-rtree

快速开始

ESM导入（现代Node.js项目，package.json需配置"type": "module"）

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

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

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

// 单条插入数据
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);

CommonJS导入（传统Node.js项目）

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等），可直接用于前端项目。

浏览器中使用方法

1. 通过构建工具引入（推荐，如Webpack/Vite/Rollup）

前端项目可直接按ESM方式导入，构建工具会自动处理模块格式转换：

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

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

2. 直接通过HTML引入（需先转换为UMD格式）

默认输出的ESM/CommonJS格式无法直接通过<script>标签引入，需先使用工具（如Rollup）转换为UMD格式：

# 示例：用Rollup将ESM转换为UMD（需提前安装rollup）
npx rollup dist/index.mjs --format umd --name "NodeRTree" --file dist/rtree.umd.js

转换后可直接在HTML中引入：

<script src="path/to/rtree.umd.js"></script>
<script>
  // 通过全局变量NodeRTree使用
  const rtree = new NodeRTree.RTree();
  const bbox = NodeRTree.createBBox(0, 0, 100, 100);
  rtree.insert(bbox, { id: '1', name: '直接引入数据' });
</script>

浏览器环境注意事项

1. 内存限制：浏览器对单页面内存限制通常严于Node.js，处理超大规模数据（如100万+条）时，建议分批次插入并及时清理无用数据，避免内存溢出。
2. 主线程阻塞：浏览器中JavaScript运行在主线程，大规模数据处理可能导致页面卡顿，建议配合Web Worker实现异步处理：

   // 主线程代码
   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 文档

1. 核心类型与工具函数

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字节。

2. RTree<T> 类核心方法

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 文件，允许商用、修改与分发，无需额外授权。