# node-rtree

**Repository Path**: nodets/node-rtree

## Basic Information

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

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2025-10-08
- **Last Updated**: 2025-10-08

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# 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
```


## 快速开始

### ESM导入（现代Node.js项目，package.json需配置"type": "module"）
```typescript
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项目）
```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`等），可直接用于前端项目。

### 浏览器中使用方法
#### 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格式无法直接通过`<script>`标签引入，需先使用工具（如Rollup）转换为UMD格式：
```bash
# 示例：用Rollup将ESM转换为UMD（需提前安装rollup）
npx rollup dist/index.mjs --format umd --name "NodeRTree" --file dist/rtree.umd.js
```
转换后可直接在HTML中引入：
```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`实现异步处理：
   ```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 文档

### 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](https://github.com/your-username/node-rtree/blob/main/LICENSE) 文件，允许商用、修改与分发，无需额外授权。