グラフデータベース 第2版

第6章 グラフデータベース内部

この作品はAIを使って翻訳されている。ご意見、ご感想をお待ちしている：[e-mail]

この章では、グラフデータベースの実装について説明し、複雑で多様な構造を持ち、高密度に接続されたデータをストアしたりクエリしたりする他の手段との違いを示す。グラフデータベースであっても、単一の普遍的なアーキテクチャパターンは存在しないが、この章では、グラフデータベース内部で発見できる最も一般的なアーキテクチャパターンとコンポーネントについて説明する。

本章では、いくつかの理由から、Neo4jグラフ・データベースを用いて説明を行う。Neo4jは、ネイティブのグラフ処理機能とネイティブのグラフ・ストレージを持つグラフ・データベースである（ネイティブのグラフ処理とストレージについては第1章を参照）。執筆時点で最も一般的に使われているグラフ・データベースであることに加え、オープン・ソースであるという透明性の利点がある。最後に、著者たちがよく知っているデータベースでもある。

ネイティブ・グラフ処理

プロパティ・グラフ・モデルについては、本書を通じて何度か説明してきた。名前付けされた有向リレーションシップによって接続されたノードの概念、ノードとリレーションシップの両方がプロパティのコンテナとして機能することについては、もうお分かりだろう。このモデル自体はグラフ・データベースの実装でほぼ一貫しているが、データベース・エンジンのメイン・メモリにグラフをエンコーディングして表現する方法は数多くある。さまざまなエンジンアーキテクチャがある中で、インデックスフリー隣接と呼ばれる特性（ ）を示す場合、そのグラフデータベースはネイティブな処理能力を持つと言う。

インデックスフリーの隣接関係を利用するデータベースエンジンは、各ノードが隣接ノードへの直接参照を保持するものである。したがって、各ノードは近接する他のノードのマイクロインデックスとして機能し、グローバルインデックスを使用するよりもはるかに低コストである。これは、クエリ時間がグラフの合計サイズに依存せず、単に検索されるグラフの量に比例することを意味する。

対照的に、非ネイティブのグラフ・データベース・エンジンは、図6-1に示すように、（グローバル）インデックスを使用してノード間をリンクする。このようなインデックスを使用すると、各トラバーサルに間接的なレイヤーが追加されるため、計算コストが増大する。ネイティブ・グラフ処理の支持者は、高速で効率的なグラフ探索には、インデックスを使わない隣接関係が重要であると主張している。

注

なぜネイティブ・グラフ処理が、重いインデックスに基づくグラフよりもはるかに効率的なのかを理解するために、次のことを考えてみよう。実装にもよるが、インデックスの検索はO(log n)であるのに対し、直接的な関係を検索する場合はO(1)である。mステップのネットワークをトラバースする場合、インデックス付きアプローチのコストはO(m log n)であり、インデックスなしの隣接関係を使用する実装のO(m)を凌駕する。

図6-1. 非ネイティブ・グラフ処理エンジンは、ノード間のトラバースにインデックスを使用する。

図6-1は、グラフ処理への非ネイティブ・アプローチがどのように機能するかを示している。アリスの友達を発見するためには、まず ...