【图数据库内核】邻接的代价模型：边表 JOIN、CSR 与原生指针为何不是同一件事
内容提要
本文比较图数据库四种邻接布局（边表、CSR、指针链、Block内联）的代价模型，分析一次hop与k跳扩张的差异。核心观点：大O相同但常数、局部性、更新代价不同；幂律图超节点主导事故形态；选型需关注k、f、d_max和更新频率四个旋钮，而非品牌之争。
延伸解读
大O相同，事故不同
四种布局读取邻居的渐近复杂度都是Θ(d)，但实际代价差异巨大。边表依赖索引探测，CSR顺序扫描，指针链可能随机I/O，block内联则在小度数时接近CSR。幂律图上，超节点会放大这些差异：指针链在超节点上变成随机读，而CSR虽顺序但输出基数爆炸。选型时不能只看大O，要关注常数、局部性和更新代价。
四个旋钮决定选型
文章提出用四个参数来评估图数据库布局：k（路径长度）、f（平均有效扇出）、d_max（最大度）和边更新频率。深度多跳、点查驱动、度数中低时，原生内联/指针布局有优势；全图扫描分析则CSR更直接；少跳强过滤时边表可能够用。争论应落在这些旋钮上，而非品牌之争。
超节点是事故源头
幂律图中，平均度掩盖了超节点的存在。超节点在边表中导致长叶页扫描，在指针链中变成随机读，在CSR中顺序扫但内存爆炸，在block dense中按类型进树但输出基数仍大。排障时先问是否某个点或类型的扇出过大，再问计划是否选错，否则平均度会掩盖问题。
更新代价分叉OLTP与分析
边表插入有索引写放大，CSR常需重建，指针链改指针加插入记录，block内联写主块或动态块。选型时把读hop和写边拆开：偶发多跳查询加频繁点属性更新，边表或混合架构更合理；边高频写入且多跳模式匹配，才更接近原生图引擎的舒适区。
Q&A
图数据库中四种邻接布局（边表、CSR、指针链、Block内联）在代价模型上有什么本质区别？
四种布局在读取邻居时都需要访问Θ(d)条边信息，大O复杂度相同，但常数、局部性、更新代价不同。边表依赖索引探测和可能的回表；CSR顺序扫描邻接数组，适合只读分析；指针链可能产生随机I/O，尤其在度数高时；Block内联在小度数时接近CSR的常数，在超节点时走dense树避免无效读。
为什么说在幂律图上平均度会掩盖超节点的问题？
幂律图中平均度很小但最大度极大，少数超节点主导了代价叙事。平均路径的代价会被超节点放大，导致不同布局在超节点上的表现不同：指针链会变成随机长链读，边表是顺序叶扫但输出基数大，CSR顺序扫但可能爆内存，Block dense按类型走树但无法解决输出爆炸。
在k跳扩张时，四种布局的代价如何随k恶化？
k跳扩张时，访问的边数级为|S| * f^k（f为平均有效扇出）。边表每层增加一次索引探测和可能回表；CSR每层顺序扫描f个邻居；指针链每层可能随机读链上所有记录（包括非匹配类型）；Block内联小度数时每层少数块，超节点层走dense树。
对于深度多跳查询，哪种布局更合适？为什么？
对于深度多跳、点查驱动、度数中低的工作负载，原生内联/指针布局（如Block内联）更合适，因为其局部性好，能减少指针追逐和随机I/O。而CSR适合全图扫描式分析，边表适合少跳强过滤的场景。
四种布局在更新代价（插入、删除边）上有什么不同？
边表插入边需要索引页分裂和写放大；CSR插入常需重建或缓冲合并；指针链插入只需改节点首指针和插入关系记录；Block内联写入主块，满则动态或dense。删除边时，边表维护索引，CSR留洞或压缩，指针链脱链并复用id，Block内联块内压缩或回收。
选型时应该关注哪些关键参数（旋钮）？
选型时应关注四个旋钮：k（路径长度）、f（平均有效扇出）、d_max（最大度）、边更新频率。先填这四个参数，再讨论原生图或SQL引擎，而不是品牌之争。
