グラフDBの内部：隣接リストとインデックスフリー隣接

グラフを「物理的に」どう置くか

グラフは頂点（ノード）と辺（エッジ）の集まりです。論理モデルは単純でも、これをディスクやメモリにどう並べるかでトラバーサル（隣を次々辿る探索）の速さが桁で変わります。グラフDB の心臓部は「あるノードの隣接エッジを、どれだけ速く列挙できるか」に尽きます。BFS・最短経路・パターンマッチングはすべて「隣を辿る」操作の繰り返しだからです。

物理レイアウトには大きく3系統あります。ノードのレコードに隣接エッジへのポインタを直接埋める隣接リスト型（ネイティブグラフDB が採る）、V×V の真偽値表で辺の有無を持つ隣接行列、疎な隣接リストを連続配列に圧縮する CSR（Compressed Sparse Row）です。それぞれ得意な形と操作が違います。

index-free adjacency――隣を引かずに辿る

ネイティブグラフDB の中核思想が index-free adjacency（インデックスフリー隣接）です。各ノードのレコードには、そのノードに接続するエッジレコードへの物理ポインタ（ファイル内のオフセット、固定長レコードなら ID×レコードサイズで算出可能）が格納されます。エッジレコードはさらに「次の隣接エッジ」「相手側ノード」への物理ポインタを持ち、隣接エッジが連結リストとして物理的に繋がります。

Node(A) ──first_edge──▶ Edge(A→B) ──next_edge──▶ Edge(A→C) ──next_edge──▶ ∅
                            │ to_node                  │ to_node
                            ▼                          ▼
                         Node(B)                    Node(C)
各ポインタはファイルオフセット。値を介さず、加算で次レコードに飛ぶ。

要点は、隣を辿る操作がグローバルインデックスの検索を一切伴わないことです。ポインタは「どこを読めばよいか」を直接指すので、ノード A の隣接を列挙する手間は A の次数（隣の数）に比例するだけで、グラフ全体のサイズ N には依存しません。1ホップが実質定数時間（隣1個あたり）で済み、これはヒープ上の行を TID という物理アドレスで直接指すのと同じ「値で引かずアドレスで飛ぶ」発想の、グラフ版です。

RDB でグラフを表すと何が起きるか

同じグラフをリレーショナルDBで表すと、ノード表とエッジ表（from_id, to_id の2列）になります。「A の隣を辿る」は SELECT to_id FROM edges WHERE from_id = A で、from_id の B+Tree インデックスを引きます。これは1ホップあたり O(log N) です（N はエッジ総数）。

問題は深い探索で顕在化します。K ホップ辿るには JOIN を K 回重ね、各段で log N の重みが乗ります。ネイティブ方式が「次数の合計回ぶんポインタを辿るだけ」なのに対し、RDB 方式は「訪れるノードごとにインデックスを引き直す」ため、探索が深く広いほど log の係数が効いてきます。

隣接行列と CSR――解析・行列演算の視点

トラバーサルではなくグラフ全体の解析（PageRank、連結成分、行列演算）では、別のレイアウトが効きます。

隣接行列は V×V のビット（または重み）表で、M[i][j] が辺 i→j の有無を表します。辺の存在判定が定数時間、行列積でホップ数の合成（2ホップ到達は M²）ができるのが利点ですが、メモリが頂点数の2乗に比例し、辺が疎なグラフ（実世界の大半）では大半が 0 で埋まり致命的に無駄です。密グラフや小規模グラフ、線形代数で解く GNN の隣接表現に向きます。

CSR（Compressed Sparse Row）は疎な隣接リストを3本の連続配列に圧縮します。row_ptr[i] がノード i の隣接の開始位置、col_idx が隣接先 ID を詰めた配列です。

ノード0: {1,2}  ノード1: {2}  ノード2: {0}
col_idx  = [1, 2, 2, 0]      # 隣接先をノード順に連結
row_ptr  = [0, 2, 3, 4]      # ノード i の隣接は col_idx[row_ptr[i]..row_ptr[i+1]]
ノード0の隣接 = col_idx[0..2] = {1, 2}

CSR は隣接が完全に連続配置されるためキャッシュ局所性が極めて高く、頂点数+辺数のメモリしか食いません。これは列指向ストレージが同型値を連続配置してスキャンを速める発想と同じで、グラフ解析エンジン（GraphBLAS、各種 GNN ライブラリ）が CSR/CSC を標準採用する理由です。

トラバーサル性能の原理的差

3方式の性質を、操作ごとに整理します。深い経路探索なら index-free adjacency、辺の存在判定や行列演算なら隣接行列、静的疎グラフの全体スキャンなら CSR、と適材が分かれます。

まとめ

グラフのトラバーサル性能は、結局「隣接をどう物理的に持つか」で決まります。index-free adjacency はノードに隣接エッジへの物理ポインタを直結し、隣を辿るのにグローバルインデックスを引かないので1ホップが N 非依存の定数時間で済み、深い探索ほど RDB のエッジ表方式（毎ホップ O(log N)）に差をつけます。

一方、グラフ全体を解析するなら隣接行列（密・行列演算向き、V の2乗メモリ）や CSR（疎・静的・キャッシュ最良だが更新に弱い）が効きます。物理ポインタで関連データを直結する発想はヒープと TIDやクラスタ化インデックスの物理整列とも地続きで、「値で引くか、アドレスで飛ぶか」というストレージ設計の普遍的な選択が、グラフでは探索の計算量そのものを左右します。