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

用AVL树构建数据库索引NeDB的indexes.js源码深度解析【免费下载链接】nedbThe JavaScript Database, for Node.js, nw.js, electron and the browser项目地址: https://gitcode.com/gh_mirrors/ne/nedbNeDB 是一款纯 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-tree0.2.5 提供了现成的 AVL 树实现NeDB 无需自己写旋转逻辑。更妙的是lib/datastore.js 中有一段注释_id字段始终建立唯一索引且_id是随机生成的 16 位字符串因此这棵 AVL 树天然就是平衡的。二、Index 类解剖一个索引如何诞生Index构造函数lib/indexes.js接受三个关键配置配置项作用fieldName索引字段支持点语法如humans.gendersunique是否强制唯一约束sparse允许文档中不存在该字段稀疏索引构造时会把配置传入treeOptions其中compareKeys: model.compareThings决定了键的比较方式——这是 NeDB 索引支持任意类型的灵魂所在。reset()方法则会重建整棵树加载数据库或重置索引时都会用到。三、四大核心操作insert / remove / update / 查询1. 插入 insertO(log n) 带回滚insertlib/indexes.js的流程用model.getDotValue按点语法取出字段值sparse 索引遇到undefined直接跳过不占用树节点若字段是数组会为每个数组元素各插入一条记录用_id去重。若中途触发唯一约束会回滚之前所有插入再抛错——保证索引的原子性。2. 删除 remove与插入对称removelib/indexes.js逻辑与插入镜像对应取出键值、处理 sparse、数组元素逐个从树中删除。3. 更新 update先删后插的朴素策略updatelib/indexes.js注释里写着 Naive implementation思路却非常清晰先把旧文档从索引中删除再插入新文档若插入违反唯一约束回滚旧文档并抛错。批量更新updateMultipleDocs同样遵循“先全部删除、再全部插入、失败逆序回滚”的事务式思路。4. 查询getMatching / getBetweenBounds / getAllgetMatchinglib/indexes.js按键值精确查找传数组时逐个查找并按_id去重对应$in查询getBetweenBoundslib/indexes.js区间查询返回按键排序的结果对应$lt/$gt/$lte/$gtegetAll遍历所有节点供建索引时全量导入数据使用。四、类型感知比较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因此建议在应用启动时调用。查询时getCandidateslib/datastore.js按“命中率从高到低”的顺序挑选索引基本等值匹配→getMatching$in 成员查询→getMatching(数组)范围比较→getBetweenBounds都不可用时退回全表扫描getAllData()此外还有 TTL存活时间索引建索引时传expireAfterSeconds查询候选集时会自动清理过期文档。索引定义还会持久化到数据文件下次加载数据库时自动重建无需重复调用ensureIndex。六、给新手的 3 条实践建议常查字段必建索引官方基准显示 10,000 条文档下带索引查询可达 43,290 ops/s差距显著唯一约束 sparse 组合对“选填字段”建unique: true, sparse: true索引既防重复又不惩罚缺少该字段的文档别在运行中途频繁建索引ensureIndex是同步操作放启动阶段执行最稳妥。// 最简单的索引使用方式 db.ensureIndex({ fieldName: email, unique: true, sparse: true }); db.find({ email: neoexample.com }, function (err, docs) { // 通过索引快速定位O(log n) });七、相关源码导航 文件说明lib/indexes.jsIndex 类构造、insert、remove、updatelib/indexes.jsgetMatching / getBetweenBounds / getAll 查询接口lib/model.jscompareThings 类型层级比较函数lib/datastore.js_id默认唯一索引的初始化lib/datastore.jsgetCandidates索引选择策略test/indexes.test.js索引插入、唯一约束、数组字段的完整测试benchmarks/ensureIndex.jsensureIndex 性能基准脚本benchmarks/find.js带索引查询的性能基准脚本读透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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考