企业官网建设流程全解析

用AVL树构建数据库索引：NeDB的indexes.js源码深度解析

【免费下载链接】nedbThe JavaScript Database, for Node.js, nw.js, electron and the browser项目地址: https://gitcode.com/gh_mirrors/ne/nedb

NeDB 是一款纯 JavaScript 编写的嵌入式数据库，可同时运行在 Node.js、Electron、nw.js 和浏览器中。它的索引系统全部集中在 lib/indexes.js 一个文件里，底层基于 AVL 平衡二叉搜索树实现，正是它让 NeDB 在万级数据量下仍能保持 O(log n) 的查询速度。本文将带你读懂这份不到 300 行的核心源码。

一、为什么 NeDB 选择 AVL 树？

数据库索引的本质是“按键值快速定位文档”。普通二叉搜索树在数据有序插入时会退化成链表（O(n)），而 AVL 树通过自动旋转保持平衡，插入、删除、查找稳定在 O(log n)。

NeDB 在第 1 行就点明了选型：

var BinarySearchTree = require('binary-search-tree').AVLTree

该依赖 binary-search-tree@0.2.5 提供了现成的 AVL 树实现，NeDB 无需自己写旋转逻辑。更妙的是，lib/datastore.js 中有一段注释：_id字段始终建立唯一索引，且_id是随机生成的 16 位字符串，因此这棵 AVL 树天然就是平衡的。

二、Index 类解剖：一个索引如何诞生

Index构造函数（lib/indexes.js）接受三个关键配置：

构造时会把配置传入treeOptions，其中compareKeys: model.compareThings决定了键的比较方式——这是 NeDB 索引支持任意类型的灵魂所在。reset()方法则会重建整棵树，加载数据库或重置索引时都会用到。

三、四大核心操作：insert / remove / update / 查询

1. 插入 insert：O(log n) 带回滚

insert（lib/indexes.js）的流程：

• 用model.getDotValue按点语法取出字段值；
• sparse 索引遇到undefined直接跳过，不占用树节点；
• 若字段是数组，会为每个数组元素各插入一条记录（用_id去重）。若中途触发唯一约束，会回滚之前所有插入再抛错——保证索引的原子性。

2. 删除 remove：与插入对称

remove（lib/indexes.js）逻辑与插入镜像对应：取出键值、处理 sparse、数组元素逐个从树中删除。

3. 更新 update：先删后插的朴素策略

update（lib/indexes.js）注释里写着 "Naive implementation"，思路却非常清晰：

1. 先把旧文档从索引中删除；
2. 再插入新文档；
3. 若插入违反唯一约束，回滚旧文档并抛错。

批量更新updateMultipleDocs同样遵循“先全部删除、再全部插入、失败逆序回滚”的事务式思路。

4. 查询：getMatching / getBetweenBounds / getAll

• getMatching（lib/indexes.js）：按键值精确查找，传数组时逐个查找并按_id去重，对应$in查询；
• getBetweenBounds（lib/indexes.js）：区间查询，返回按键排序的结果，对应$lt/$gt/$lte/$gte；
• getAll：遍历所有节点，供建索引时全量导入数据使用。

四、类型感知比较：compareThings 如何给“万物”排序

JavaScript 里数字、字符串、布尔、日期混在一起，怎么比较大小？lib/model.js 的compareThings定义了一套固定的类型层级：

undefined < null < number < string < boolean < date < array < object

同类型内部再按各自规则比较（字符串可注入自定义compareStrings以支持带重音字符的语言）。而 lib/indexes.js 的projectForUnique则给不同类型的键加上前缀（$string、$number、$boolean、$null、$date），避免42（数字）和"42"（字符串）在唯一索引中互相“撞车”。这两处设计是 NeDB 索引能覆盖任意字段类型的关键。

五、索引如何加速查询？从 ensureIndex 到 getCandidates

🎯 在 lib/datastore.js 中调用db.ensureIndex(options)即可建索引，它会对现有全量数据同步建树（官方基准：10,000 条文档约 35ms，见 benchmarks/ensureIndex.js），因此建议在应用启动时调用。

查询时，getCandidates（lib/datastore.js）按“命中率从高到低”的顺序挑选索引：

1. 基本等值匹配→getMatching
2. $in 成员查询→getMatching(数组)
3. 范围比较→getBetweenBounds
4. 都不可用时，退回全表扫描getAllData()

此外还有 TTL（存活时间）索引：建索引时传expireAfterSeconds，查询候选集时会自动清理过期文档。索引定义还会持久化到数据文件，下次加载数据库时自动重建，无需重复调用ensureIndex。

六、给新手的 3 条实践建议

1. 常查字段必建索引：官方基准显示 10,000 条文档下带索引查询可达 43,290 ops/s，差距显著；
2. 唯一约束 + sparse 组合：对“选填字段”建unique: true, sparse: true索引，既防重复又不惩罚缺少该字段的文档；
3. 别在运行中途频繁建索引：ensureIndex是同步操作，放启动阶段执行最稳妥。

// 最简单的索引使用方式 db.ensureIndex({ fieldName: 'email', unique: true, sparse: true }); db.find({ email: 'neo@example.com' }, function (err, docs) { // 通过索引快速定位，O(log n) });

七、相关源码导航 📂

读透indexes.js你会发现：一个精巧的索引系统并不需要千行代码。AVL 树负责平衡，compareThings负责万物可比，回滚逻辑负责一致性——三者合力，就让 NeDB 这块“JavaScript 数据库”拥有了真正的索引能力。

【免费下载链接】nedbThe JavaScript Database, for Node.js, nw.js, electron and the browser项目地址: https://gitcode.com/gh_mirrors/ne/nedb