免索引邻接: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(节点数)。
一手资料
继续阅读
探索更多技术文章
浏览归档,发现更多关于系统设计、工具链和工程实践的内容。