《大规模分布式计算深入解析》2.3 免索引邻接:Neo4j 为什么遍历快

关系记录用双端指针串成邻接链,遍历 O(度数) 而全表扫描 O(节点数);探针实测 alpha 出度 2、两跳可达。

免索引邻接:Neo4j 为什么遍历快

关系数据库用索引把点查从全表扫描变小;Neo4j 更进一步:关系本身是指针,遍历沿物理邻接链走,不查全局索引。这种「免索引邻接」是遍历快的根源。

双端指针与邻接链

store 用例 58-59 给出记录账本:节点记录 25 字节(头 9 + 属性指针 8 + 首关系 8),关系记录 34 字节(类型 2 + 两端 next 各 8 + 两端节点 8×2)。关系记录两端各带一条 next 指针,把同一节点的全部关系串成双向链。

store 用例 61:免索引邻接 = 关系记录双端 next 链。从节点出发沿链取邻居,无需维护或查询全局索引。

遍历成本账本

store 用例 62:遍历成本 = 邻接关系数 7。用例 63:邻接遍历 O(度数),远小于全表扫描 O(节点数)。度数低的节点跳转成本恒定,与全图规模无关——这是记录布局决定的结构性优势,不是缓存运气。

对齐卷八:索引 vs 扫描

卷八的 B+ 树把点查从 O(n) 降到 O(log n);免索引邻接更进一步到 O(度数),且不用维护索引。代价是关系必须作为实体记录存在、链指针要随删除维护——用存储换遍历。

验证

从卷十一实验包 解包:运行 neo4j-probe.sh,在 3 节点(Doc alpha/beta/gamma)+ 3 条 LINK(alpha→beta→gamma、alpha→gamma)上执行 MATCH (a:Doc{name:'alpha'})-[:LINK*1..2]->(n),可达 beta、gamma、gamma(一跳 + 两跳两条路径);出度沿关系指针计数 alpha=2、beta=1、gamma=0——印证 store 用例 61-62。Java 账本 store 用例 63 验证邻接遍历 O(度数) 小于全表扫描 O(节点数)。

一手资料

卷十一目录 · 系列导读与实验

继续阅读

探索更多技术文章

浏览归档,发现更多关于系统设计、工具链和工程实践的内容。

全部文章 返回首页

「books」更多文章

  1. 《大规模分布式计算深入解析》15.3 落地:从 Neo4j 到自研图引擎
  2. 《大规模分布式计算深入解析·图计算与图数据库内核》 · 目录与学习路径(45 篇)
  3. 《大规模分布式计算深入解析》15.2 十一卷主线:从切分到图