图数据库调研报告

2021-11-28

我主要参考了《Demystifying Graph Databases: Analysis and Taxonomy of Data Organization, System Designs, and Graph Queries》这篇文章。它是2019年10月的一篇针对图数据库的综述，这篇综述本身引用了202篇参考文献，被引29次。文章中也提到，在这篇文章之前几乎没有专门针对图形数据库的系统方面的调查，只有几篇涵盖该领域小部分的简短论文(对几个系统、概念或技术的简要描述，对图处理质量的调查，以及几个系统的性能评估)。因此我主要解读这篇综述中对图数据库的介绍和总结，对其中的一些表述进行理解后的复述以及解释，并为了更好地说明图数据库基本特点对文章内容进行重新组合。

我选择的调研题目是图数据库的储存索引和查询优化。重点是各种图数据库类型分类以及它们的储存方式。储存方式的不同自然带来了不同的索引方式。索引方式各有千秋引出了查询的优化方案。

目录

点击相应目录可以直接跳转查看。

[TOC]

1.储存

论文中在对比了51个数据库后得到如下结论。

1.1实现难点

• 图的结构不规则，尺寸可能很大
• 处理过的图失去了局部性或者一些联系
• 图自身结构动态地变化且连接过于复杂
• 图的搜索遍历较为复杂，难以应对低延迟高吞吐量的需求
• 事务支持
• 与传统图数据结构算法不同，图数据结构算法通常是静态的和简单的数据，但是图数据库可能有丰富的附加数据如标签或键值对

1.2实现方法

• 不使用表而使用边和顶点。尽管可以使用顶点和边组成的表，但是遍历查询等操作都依赖临界列表数组的存储方式。每个顶点的邻居可以通过连接到每个顶点的指针通过简单的内存查找来访问
• 数据结构分两种，原生图数据库或者使用其他数据库实现图的存储(宽列存储、文档存储和通用键值存储)
• 实现方式分两种，顶点和边可能属于不同的类型，并且可能与任意属性相关联；或者边或顶点可能具有权重或者有诸如时间戳之类的附加属性

1.3多种类别的图模型

图模型没有一个标准的概念，目前最流行的两个模型是RDF和LPG。RDF是一个定义明确的标准，但是它只支持简单的三元组(主体、谓词、客体)来表示从主语标识符通过谓词到客体的边。LPG允许顶点和边具有标签和属性，从而支持更自然的数据建模。尽管如此，它仍然不是标准化的，并且有许多变体。一些系统将标签的数量限制为只有一个。例如MarkLogicAllow允许顶点的属性，但不允许边的属性，因此可以将其视为LPG(顶点)和RDF(边)的组合。LPG模型中存储的数据可以转换为RDF。为了综合不同的LPG特性同时保持RDF的简单性等优点，一些研究人员提出并实现了对RDF的修改。例如三元组属性或将三元组附加到其他三元组。

在原生图形数据库中，虽然没有关注LPG的系统同时支持RDF，但一些RDF系统(例如Amazon Eptune)也支持LPG。许多其他类(KV值、文档储存、RDBMS、宽列储存、OODBMS)仅提供LPG(除了一些例外，例如oracle spatial and graph。后者建议使用相应的非图形数据模型(如文档集合)来表达LPG模型(比RDF模型)更容易。很少有系统既不使用RDF也不使用LPG。HyperGraphDB使用超图模型，而Gbase使用没有任何标签或属性的简单有向图模型。

在表示图结构时，许多图形数据库使用AL的变体，因为它使遍历邻域变得高效和简单。这包括基于LPG的原生图形数据库、KV存储、文档存储、宽列存储、元组存储和OODBMS类中的几个(但不是所有)系统。但是所考虑的RDF、RDBMS和数据中心系统都没有显式使用AL。这是因为底层数据模型的默认设计，例如RDBMS中的表或文档存储中的文档，并不经常使用AL。此外，绝大多数系统都没有使用未压缩的AM，因为它在$O(𝑛^2)$空间中的效率很低，特别是对于稀疏图。使用AM的系统侧重于压缩邻接矩阵来减少存储和查询开销(例如，GBASE)。在AL中效率低下的一个潜在原因是扫描所有的边来寻找给定顶点的邻居，为了缓解这一问题，可以采用索引结构。对于具有𝑛个顶点的图，这样的索引是指向各个邻域的指针数组，仅占用𝑂(𝑛)空间。

下面来详细介绍一下不同类型的图模型以及它们的特点。

1.3.1简单图模型

最简单的表示图的数据结构有邻接矩阵(AM)、邻接列表(AL)、边列表(EL)三种，它们都可以表示有向图或无向图。AM使用$O(n^2)$空间，可以在O(1)时间内检查两个顶点的连通性；AL占用O(𝑛+𝑚)空间，可以在$O(|𝐴𝑢|)⊆O(Degree_{max})$时间内检查连通性。

1.3.2超图模型

任意边可以连接任意个点。超图的每一个定点至少属于一条边，也可以属于一条封闭的曲线。形式上，超图表示为元组(𝑉，𝐸)，𝑉是这个超图模型中所有顶点，𝐸是超边的集合，每个超边使用一组点表示，它是V的一个非空子集。例如：$V=\{a,b,c,d,e,f,g\}，E=\{abc,cde,def,efg\}$。

超图在图形数据库和图处理系统中很少使用。HyperGraphDB的基本构建块是点和超边的每个值，都有自己唯一的ID以及区分顶点和边的标签。顶点和超边也有类型ID(即标签ID)，还有一个递归结构，这个递归结构可以可以是另一个递归结构或二进制数据的值ID。

1.3.3标记属性图(LPG)

经典的图模型tuple 𝐺=(𝑉，𝐸)对各种现实世界的问题进行建模还不够丰富，因此图形数据库经常使用标记属性图LPG(Label Property Graph Model，LPG)。每个顶点和边可以具有任意数量的属性。属性是一对(𝑘𝑒𝑦，𝑣𝑎𝑙𝑢𝑒)，其中Key标识属性，Value是该属性的相应值。

形式上，LPG被定义为元组$(𝑉ertex，𝐸dge，𝐿abel，𝑙_V，𝑙_E，𝐾ey，𝑊_{value}，𝑝_V，𝑝_E)$，其中𝐿是标签集，$L_V$和$L_E$分别代表V和E到L所有子集中某一个的一个映射因此，每个顶点和边都被映射到一个标号子集。顶点和边可以与任意数量的属性相关联，将属性建模为键-值对(𝑝=(𝑘𝑒𝑦，𝑣𝑎𝑙𝑢𝑒)，其中𝑘𝑒𝑦∈𝐾，𝑣𝑎𝑙𝑢𝑒∈𝑊。𝐾和𝑊是所有可能键和值的集合。$p_V$和$p_E$分别为获取某点和某边的属性键值对的集合的映射函数。

除了下文中要说的RDF系统或明确指出是其他系统外，下文要说到的所有系统实际上都使用LPG的某些变体。

上图为一个社交网络的子图，其中一个人可以认识其他人、发布消息和评论其他人的消息。

1.3.4 LPG变体

Neo4j支持任意数量的顶点标签，但是它只允许每条边有一个标签(称为边缘类型)；ArangoDB只允许每个顶点一个标签和每个边一个标签，这便于将顶点和边分离到不同的文档集合中。

形式上，它使用𝐺=(𝑉，𝐸，𝐿)表示，其中𝑉是顶点集，𝐸是边集。此定义下允许两个点通过具有不同标签的多条边连接。

1.3.5资源描述框架RDF

资源描述框架(RDF)是用于表示信息的规范集合。它是由万维网联盟(W3C)于1999年推出的，RDF规范的最新版本(1.1)于2014年发布。它的目标是实现一种简单的格式，允许在不同格式的数据之间轻松交换数据。它在描述不规则连接的数据时特别有用。

RDF模型的核心部分是一个三元组的集合。每个三元组由主体、谓词、客体组成，因此RDF数据库通常也称为三重存储。主语可以是标识符(称为统一资源标识符(URI))，也可以是空白节点(即虚拟标识符)。客体可以是URI、空白节点或值较为简单的文字。使用三元组可以将标识符与标识符连接或将标识符与文字连接。谓词使用另一个URI命名。

Cray图引擎

Cray Graph Engine(CGE)是一个三元组存储，可以扩展到无数个RDF三元组。CGE不存储三元组而是存储四元组(4元组)，其中第四个元素是ID。因此，可以在一个CGE数据库中存储多个图。CGE中的四元组按照它们的谓词和它们所属的图的标识符进行分组。因此，对于一组这样的四元组，只需要存储具有子对象和对象的对。这些主体-客体对存储在哈希表中(每组一个哈希表)。由于每个主体和客体被表示为唯一的48位整数标识符(HURI)，因此可以将主体-客体对打包成12个字节并存储在32位无符号整数数组中，从而最终减少了所需的存储量。

AllegroGraph和BlazeGraph

一些RDF存储允许显式地将属性附加到三元组。AllegroGraph允许在创建三元组时定义每个三元组的任意属性集，但是这些属性不可变。BlazeGraph是RDF的一种扩展，允许将三元组附加到三元组谓词。和普通的RDF类似，顶点可以使用三元组来存储标签和属性。但是与普通的RDF相比，使用RDF可以更自然地表示LPG边缘：边可以存储为三元组，边属性可以通过其他三元组链接到边三元组。

1.3.6 LPG与RDF之间的转换

要想在RDF模型中表示带标签的属性图需要把LPG顶点映射到URI，然后使用RDF三元组通过分别用RDF谓词和RDF对象表示属性键和属性值来将这些点与它们的LPG属性链接起来。

例如，对于具有ID vertex-id的顶点以及具有key property-key和value property-value的对应属性，可以创建一个RDF三元组(vertex-id、property-key、property-value)。类似地，可以通过为每个边赋予URI状态来表示RDF模型中的LPG图模型中的边并将边属性与类似于顶点的特定边链接起来：(边-id，属性-键，属性-值)。然后，必须使用两个三元组将每条边连接到其任意相邻顶点。最后，通过为顶点和边创建RDF三元组，LPG标签也可以以类似于属性的方式转换为RDF三元组使得谓词变成有标签的URI并包含该标签的字符串名。下图展示了将LPG图转换为RDF三元组的过程示例。

如果所有顶点和边只有一个标签，则可以省略标签的三元组，并将标签与顶点或边名称一起存储在标识符中。如下图例子：

将RDF数据转换为LPG模型更为复杂，因为RDF谓词(通常会转换为边)是URI。因此，从RDF图转换为LPG图时必须将边映射到顶点并链接这些顶点，否则得到的LPG图可能会断开。有几种方案用于这样的RDF到LPG转换，例如以增加图大小为代价导出二部LPG图。

1.4非图底层的系统存储方案

很多不是专门为图数据设计的数据库也可以储存图数据模型，包括使用键值对、文档和元组、关系和表以及对象的数据库。

1.4.1键-值对(key-value)

键值存储是最简单的NoSQL存储方式。将数据存储为键-值对的集合，重点放在基于键的高性能和高度可伸缩的查找上。键和值的确切形式取决于特定的系统或应用程序。键可以是简单的(例如，URI或散列)，也可以是结构化的。值通常编码为字节数组，也就是说值的结构通常是无模式的。但是，键值存储还可以强加一些额外的数据布局从而构建无模式的值。根据键值存储的一般性质，可以有许多方式将图表示为KV值的集合。例如可以使用顶点标签作为键，将顶点的邻域编码为值。

微软图引擎(Trinity)

微软的图引擎是基于名为Trinity的分布式键值对。Trinity实现了全局可寻址的分布式RAM存储。在Trinity中，键称为cell ID，值称为cell(单元格)。一个cell可以保存不同数据类型的数据项，包括其他cell的ID。MS Graph Engine在Trinity KV存储层之上引入了一个图存储层，点存储在专用字段包含cell ID或ID的哈希值的cell中。与给定点𝑣相邻的边直接在v的cell中存储为𝑣邻域的ID列表。但是，如果边包含丰富的数据，则这样的边也可以和关联数据一起存储在单独的专用cell中。

1.4.2文档(document)

文档是一类文档存储的NoSQL数据库中的基本存储单元。这些文档存储在集合中多个文档集合构成一个数据库，使用所选的标准半结构化格式(例如JSON或XML)对文档进行编码。文档存储扩展了键值存储，因为文档可以被视为具有某种灵活模式的值。该模式由属性组成，其中每个属性都有一个名称以及一个或多个值。这样一个基于具有属性的文档允许各种值类型、键-值对存储和递归数据存储(属性值可以是列表或键值字典)

文档存储每个顶点都存储在一个顶点文档中。文档存储键值对的能力用于在相应的顶点文档中存储顶点标签和属性。然而，边存储的细节取决于系统：边可以存储在与每个边的源顶点对应的文档中，也可以存储在目的顶点的文档中。文档不会限制可以存储的键值，因此点和边可能具有不同的属性集。

OrientDB

在OrientDB中，每个文档𝑑都有一个记录ID(RID)，由存储𝑑的文档集合的ID和偏移量(其在该集合中的位置)组成。文档之间的指针使用这些唯一的RID表示。orientDB引入了规则边和轻量级边。规则边存储在边的文档中，可以具有它们自己的相关键/值对(例如，对边缘属性或标签进行编码)。轻量级边则直接存储在相邻(源或目标)顶点的文档中。这样的边没有任何关联的键/值对。它们构造指向其他顶点的简单指针，并且它们被实现为文档RID。因此，顶点文档不仅存储顶点的标签和属性，还存储轻量级边的列表(作为与相邻顶点相关联的文档的RID的列表)，以及指向相邻规则边的指针列表(作为与这些规则边相关联的文档的RID的列表)。每条规则边都有指向存储源和目标顶点的文档的指针(RID)。每个点存储指向其传入和传出边的链接(RID)列表。

ArangoDB

ArangoDB将其文档保存为称为VelcyPack的二进制格式，这是JSON文档的压缩实现。文档可以存储在不同的集合中，并且具有key属性，该属性是给定集合中的唯一ID。与OrientDB不同，这些ID不是直接内存指针。为了保持图的特性，ArangoDB使用了点集合和边集合。前者是带有顶点文档的规则文档集合，顶点文档不存储关于相邻边的信息，这具有在添加或移除边时不必修改顶点文档的优点。边缘集合存储边缘文档。边缘文档有两个特定的属性：源和目的地，它们是与给定边连接的两个顶点相关联的文档的ID。ArangoDB的设计中有一个优化，可以防止读取顶点文档，并允许基于另一个边文档中的顶点ID直接访问一个边文档。这可以提高高速缓存效率，从而减少查询执行时间。

可以使用不同的文档集合来存储不同的边缘类型(例如，“Friend_of”或“Like”)。当检索以某种边类型为条件的边(例如，“Friend_of”)时，不必遍历整个邻接列表(所有“Friend_of”和“Like”边)，而是可以使用特定边缘类型(“Friend_Of”)的边缘来确定集合的目标。

1.4.3元组(tuple)

元组是元组存储的NoSQL存储方式的基础。元组存储是RDF存储的一种扩展：RDF存储被限制为三元组，而元组存储可以包含任意大小的元组。元组中的元素数量不是固定的，甚至在单个数据库中也是可以变化的。每个元组都有一个ID，该ID可以是直接指向内存的指针。元组的集合可以以不同的方式对图形建模。例如，一个大小为𝑛的元组可以存储指向包含顶点邻域的其他元组的指针。这种元组和图形数据之间的具体映射方式取决于不同的数据库。

WhiteDB

WhiteDB是一个元组存储，它允许分配任意元组长度以外的新记录(元组)。一些小的值和指向其他元组的指针直接存储在固定位置中，大型字符串保存在单独的存储区中。每个大值只存储一次，引用计数器随时跟踪引用它的元组的数量。WhiteDB只允许访问单个元组记录，例如，没有更高级的查询引擎或图形API允许执行获取另一个顶点的所有邻居的查询。但是可以使用元组作为顶点和边存储，通过内存指针将它们彼此链接起来。这有助于快速解析关于WhiteDB中任意不规则图形结构的各种查询。例如，可以将具有其属性的顶点𝑣存储为与𝑣相关联的元组中的连续字段，并在𝑣的元组中维护指向𝑣的选定邻域的指针。

1.4.4表(table)

表是关系数据库管理系统(RDBMS)的基础。表由行和列组成，每行表示单个数据元素，单个列通常定义特定的数据属性。某些列可以定义数据元素的唯一ID，称为主键，可用于实现数据元素之间的关系。一对一或一对多关系可以用包含相关数据元素的主键副本(外键)的单个附加列来实现。可以使用包含相关数据元素的外键的专用表来实现多对多关系。

要将图建模为表的集合，可以将顶点和边实现为两个独立表中的行。每个顶点都有一个构成其ID的唯一主键。边可以通过以其外键形式引用它们的主键从而与它们的源顶点或目标顶点相关。LPG标签和属性以及RDF谓词可以用附加的列建模。

DBMS有两种类型：列RDBMS(不要与宽列存储混淆)和行RDBMS(也称为面向列或列和行)。它们在物理数据持久性方面有所不同。行RDBMS将表行存储在连续的内存块中。ColumnRDBMS连续存储表列。行RDBMS在只需要检索几行但需要检索它的所有列时效率更高，而列RDBMS在需要检索许多行但只需要几列时效率更高。使用RDBMS作为后端的图形数据库解决方案同时使用行RDBMS(例如，Oracle Spatialand Graph，基于MariaDB构建的OQGRAPH)和列RDBMS(例如，SAP HANA)。

Oracle Spatial and Graph

Oracle Spatial and Graph建立在Oracle数据库之上，它为图数据的管理和分析提供了一套丰富的工具。Oracle Spatial and Graph附带了一系列内置的并行图算法(例如，用于寻径、遍历、链接预测、PageRank等)。LPG和RDF模型均受支持。行的RDBMS表构成顶点，这些行之间的关系形成边。关联的属性和属性以键-值对的形式存储在单独的结构中。

1.4.5对象(object)

还可以使用面向对象的数据库管理系统(OODBMS)中的对象集合来建模图形。数据元素及其关系通过某种形式的指针链接的对象来实现。将图建模为对象的细节在很大程度上取决于特定的设计。

VelocityGraph

VelocityGraph是依赖于VelocityDB分布式对象数据库的图形数据库。它的边、顶点以及边或顶点属性存储在包含对其他对象的引用的C#对象中。为了处理这种结构，VelocityGraphy引入了VertexType、EdgeType和PropertyType等抽象概念。每个对象都有一个指向它物理存储位置的唯一id。每个顶点和边都有一个类型(标签)，属性存储在字典中，点将相邻边储存在集合中。

1.4.6宽列储存

宽列存储结合了键值存储和关系表的不同功能。宽列存储将键映射到行(将键映射到值的KV存储)。每行可以有任意数量的cell，并且每个cell构成一个键-值对。因此，一行包含cell键到cell值的映射，有效地使宽列存储成为二维KV值(行键和cell键都标识特定值)。此外，宽列存储是一个表，其中cell键构成列名。但是与关系型数据库不同，同一表中的行之间的列名称和格式可能不同。

Titan and JanusGrap

Titan及其后续的JanusGraph建立在宽列储存之上。它们可以使用不同的宽列存储作为底层，例如Apache Cassandra。在这两个系统中，当存储图时，每行代表一个顶点。每个顶点属性和相邻边都存储在单独的单元中，因此一个边和该边的所有属性被编码在单个单元中。由于每行中的cell是按cell键排序的，因此此排序顺序可用于高效地查找cell。对于图，属性和边的cell键的选择是这样的：在对cell进行排序后，存储属性的cell首先出现，然后是包含边的cell。由于行是按键排序的，因此两个系统都会直接将表划分为所谓的平面，这些平面可以分布在多个数据服务器上。

1.5原生图数据库系统

1.5.1 直接指针

Neo4j

Neo4j是最流行的图数据库系统。Neo4j使用基于固定大小记录的存储设计实现LPG模型。顶点𝑣由顶点记录表示，该记录存储：(1)𝑣的标签、(2)指向𝑣属性的链表的指针、(3)指向与𝑣相邻的第一边的指针、(4)一些标志。边𝑒由边记录来表示，该边记录存储：(1)𝑒的sedge类型(标签)、(2)指向𝑒属性的链表的指针、(3)指向表示与𝑒相邻的顶点的两个顶点记录的指针、(4)指向两个相邻顶点的AL的指针、(5)一些标志。每个属性记录最多可以存储四个属性，具体取决于属性值的大小：大的值(例如，长字符串)存储在单独的动态存储中，在顶点和边记录之外允许记录一些较小的属性。此外，如果查询中没有访问任何属性，则根本不会加载它们。

顶点的AL的实现为双向链表。一条边只存储一次，但它是两个这样的链表的一部分(每个相邻顶点一个列表)。因此，一条边有两个指向前一条边的指针和两个指向下一条边的指针。两个顶点由一条“知道”边链接。两个顶点都维护属性的链接列表。边是两个双向链表的一部分，每个相邻顶点一个链表。

Neo4j中的一个核心概念是使用直接指针：顶点存储指向其邻居的物理分配的指针。因此，对于邻域查询或遍历，不需要索引，而是可以跟随直接指针(遍历中的根顶点除外)，因此查询复杂度不依赖于图的大小。相反，它只取决于被访问的子图有多大（也就是说，如果内存放不下整个图，那么执行速度基本取决于缓存和预取，运行时间可能显著增加）。

1.5.2 B+树和位图

Sparksee/DEX

Sparksee是一个图数据库系统，以前称为DEX。Sparksee的顶点和边(都称为对象)都有唯一的ID。对于每个属性名称，都有一个关联的B+树，它将顶点和边ID映射到各自的属性值。从属性值到顶点和边ID的反向映射由位图维护，其中位设置为1表示对应的ID具有某个属性值。此外，每个顶点存储了表示输入边和输出边的两个位图，两个B+树维护有关边连接到哪些顶点的信息(每个边方向一个树)。

Sparksee是少数几个不基于记录的系统之一，它使用简化为B+树和位图。位图的使用允许以比特为单位执行某些操作。例如，如果要查找具有特定属性值的所有顶点，如“age”和“First Name”，只需找到与“age”和“First Name”属性相关联的两个位图，然后得到第三个位图，该位图是对这两个输入位图应用按位“与”运算的结果。

未压缩的位图可能会大的离谱。由于大多数图都是稀疏的，按顶点或边索引的位图大多包含零。可以把它们切割成32位簇来缩小这种稀疏位图的尺寸。如果簇包含非零位，则显式存储该位。这个位图然后由(簇-ID，位-数据)对的集合表示。这些对存储在排序树结构中，以实现高效的查找、插入和删除。

1.5.3稀疏邻接矩阵

GBASE

GBASE是一个只能表示有向图结构的系统，它既不存储属性，也不存储标签。GBASE的目标是保持图的邻接矩阵的压缩，这样就可以有效地检索选定顶点的所有输入和输出边，而不会产生令人望而却步的$𝑂(𝑛^2)$矩阵存储开销。同时，利用邻接矩阵可以在𝑂(1)时间内验证任意两个顶点是否连通。为了压缩邻接矩阵，GBASE将其切割成$𝐾^2$个块(每行和每列都有𝐾块)。因此，获取每个顶点的传入和传出邻居的查询只需要查询𝐾个块。可以针对特定数据库优化参数𝐾。当𝐾变小时，就必须检索更多的小文件。如果𝐾变大，文件会变少，但它们会变得更大，从而产生开销。当块只包含0或只包含1时，可以进行进一步的优化，这样可以实现更高的压缩率。

2.索引

大多数图形数据库系统都建立在现有的存储设计之上，包括键值存储、宽列存储、关系型数据库管理系统等，使用现有存储设计的优点是这些系统通常是成熟的和经过良好测试的。缺点是它们可能没有针对图形数据和图形查询进行完美优化。这就是原生图数据库试图解决的问题。

大多数图数据库系统都使用索引。然而，它们的确切目的在不同的系统之间差别很大。一般来说索引可以分为四类：存储顶点邻域的位置(称为“邻域索引”)，存储丰富图数据的位置(称为“数据索引”)，存储实际的图数据，以及维护与图形无关的数据(称为“结构索引”)。

2.1索引的数据结构

与键值存储的情况一样，所研究的图形数据库使用的记录可以是非结构化的(即，不具有诸如JSON的预先指定的格式)。它们也可以是结构化的：文档数据库通常使用JSON格式，宽列存储在每行中有一个键-值映射，面向行的RDBMS将每行分成列，OODBMS强加一些类定义，元组存储以及一些RDF存储使用元组。数据布局的细节(即顶点和边是如何在记录中精确表示和编码的)在不同的系统类中可能会有所不同。一些结构化系统仍然能够在其记录中实现高度灵活的结构。例如，使用JSON或宽列存储(如Titanand JanusGraph)的文档数据库允许为每个顶点和边提供不同的键值映射。其他基于记录的系统在其结构上更加固定。例如，在OODBMS中，必须为顶点和边属性的每个配置定义一个类。在RDBMS中，必须为每个顶点或边类型定义表。总体而言，这些系统中的大多数使用记录来存储顶点，最常见的情况是每条记录对应一个顶点。一些系统将边存储在单独的记录中，另一些系统将它们与相邻的顶点一起存储。如果要查找特定顶点的属性，则必须找到包含该顶点的记录，搜索属性或者直接存储在记录中，或者可以通过指针访问其位置。

一些系统(例如，Sparksee、一些三元组存储或面向列的RDBMS)不在专用记录中连续存储有关顶点和边的信息。相反，它们为每个属性或标签维护单独的数据结构。因此，关于给定顶点的信息分布在不同的结构上。如果想要找到某个特定顶点的属性，就必须在相关的数据结构(索引)中查询该属性，并找到给定顶点的值。这种使用的索引结构的示例是B+树(在Sparksee中)或哈希表(在某些RDF系统中)。

图数据结构的另一个方面是设计记录之间的邻接关系。可以为每条记录分配一个ID，然后通过ID将记录相互链接，或者可以使用直接内存指针。使用ID需要索引结构来查找物理存储与特定ID关联的记录的地址。直接内存指针不需要索引即可从一条记录遍历到其相邻记录。但是此时仍可使用索引，例如检索具有特定属性值的点，此情况下直接指针仅有助于解决折点之间的邻接查询。

有时，图形数据直接存储在索引中。三元组存储将索引用于主体、谓词和客体的各种排列，以高效地回答查询。Jena TBD将大量数据存储在这些索引中，但本身没有三元表，因为索引已经存储了所有必要的数据。HyperGraphDB使用键值索引(即Berkeley DB)来访问其物理存储。此外，该方法允许与引用计数共享基元数据值，从而使得多个相同的值仅存储一次。

也有一些其他数据布局优化。例如，CGE优化了存储来自其三元组/四元组的字符串的方式。考虑到许多三元组/四元组可能共享字符串，每个三元组/四元组存储多个长字符串的效率很低。因此，类似于许多其他RDF系统，CGE维护一个将字符串映射到唯一的48位整数标识符(HURI)的字典。为此，使用了两个分布式哈希表(一个用于将字符串映射到HURI，另一个用于将HURI映射到字符串)。加载时，对字符串进行排序，然后将其分配给HURI。这允许整数比较(等于、大于、小于等)以代替更昂贵的字符串比较。该方法被例如诸如WhiteDB的元组存储使用。

2.2邻域索引类型

主要用于加速邻接表的访问，以加速遍历查询。这种索引称为为以顶点为中心的索引。虽然允许每个顶点有多个以顶点为中心的索引，每个索引都针对不同的条件进行了优化，然后由查询优化器选择不同的条件，但也存在更简单的解决方案。LiveGraphs使用两级层次结构，在指向实际物理存储之前，第一级通过它们的标签来区分边。Graphflow将顶点的邻居索引到前向和后向邻接列表中，其中每个列表首先按边标签划分，然后按邻居顶点的标签划分。另一个例子是Sparksee，它使用各种不同的索引结构来查找相邻顶点和顶点的属性。

2.3数据索引类型

这种索引主要是为了处理邻域信息以外的数据。例如，可以索引具有特定属性(值)的所有顶点。它们通常用于加速业务智能工作负载。许多三元组存储，例如AllegroGraph，都提供主体(S)、谓词(P)和客体(O)的全部六种排列，以及附加的聚合索引。然而，为了降低相关成本，也存在其他方法：TripleBit仅使用具有两个聚合索引(SP，SO)和两个辅助索引结构的两个排列(PSO，POS)。GStore在两种索引结构的帮助下实现了模式匹配查询：VS*树，这是一种专门的B+树，以及基于TRIE的T索引。一些数据库系统，如AmazonNeptun或AnzoGraph只提供隐式索引，但仍然可以高效地应对所有类型的查询。大多数图数据库系统都允许用户显式定义索引。其中一些系统，如Azure Cosmos DB，对于更具体的用例支持复合索引(不同标签/属性的组合)，除了内部索引之外，一些系统还使用外部索引工具。例如，Titan和JanusGraph使用内部索引进行基于标签和值的查找，但依赖外部索引后端进行涉及多个属性、范围或全文搜索的重要查找。

根据数据索引的实现方式进一步对其进行分类。用于实现这些索引的三种基本数据结构：树、跳跃表和哈希表。根据表中的标准对系统进行分类。可以发现索引类型和图形数据库的后端之间没有明确的联系，但是大多数系统使用基于树的索引。

数据通常存储在数据结构中。当这些数据结构变得更加复杂时，一些图形数据库选择使用结构化索引来增强其设计。其他系统中的LiveGraph使用顶点索引将其顶点ID映射到物理存储位置。同样，ArangoDB多次使用混合索引、哈希表来查找顶点的关联边和相邻顶点的文档。

3.优化

基于记录的系统通常为需要检索关于顶点或边的全部或大部分信息的查询提供更高的性能，因为所需的数据存储在连续的内存块中，所以效率更高。在将数据存储在索引中的系统中，查询每个属性的数据结构会导致更多的随机访问模式。如果只想检索有关顶点或边的单个属性，这样的系统可能只需要检索单个值。而许多基于记录的系统不能仅检索部分记录，会获取更多不必要的数据。

此外，决定是否使用ID或直接内存指针来链接记录取决于给定系统的工作负载的读/写比率。在前一种情况下，必须使用索引结构来查找记录的地址。与紧随其后的直接指针相比，这会降低读取查询的速度。但是，使用ID而不是指针可以提高写查询的效率。例如，当必须将记录移动到新地址时，所有指向这条记录的指针都需要更新来映射到新地址，ID可以保持不变，只有索引结构需要修改给定记录的地址。

对于更新图的事务性工作负载，基于非图数据模型(例如文档存储或宽列存储)的系统通常获得更高的性能。相反，只读工作负载(包括简单分析和全局分析)通常在原生图数据库上实现更高的性能。全局分析尤其受益于确保单个查询并行化的原生图数据库。

3.1将数据划分为记录

图形数据库通常将数据组织成称为记录的小单元，一条记录包含关于特定单个实体(例如：一个人)的信息，该信息被组织成指定的逻辑字段(例如：名字、姓氏等)。一定数量的记录通常一起保存在内存或磁盘中的一个连续盘块中，以增强数据访问局部性。基于记录的数据组织的细节在很大程度上取决于特定的系统。例如，关系型数据库可以将表行视为记录，键值存储通常在单个记录中维护单个值，而在文档存储中，单个文档可以是记录。一些系统允许可变大小的记录(例如：ArangoDB)，而其他系统仅允许固定大小的记录(例如：Neo4j)。可以观察到，虽然一些系统(例如：一些三元组存储如CrayGraph engine)没有显式提到记录，但是数据仍然可以隐式地以基于记录的方式组织起来。

图形数据库通常每个顶点使用一条或多条记录(这些记录有时被称为顶点记录)。Neo4j对顶点使用多个固定大小的记录，而文档数据库对每个顶点使用一个文档(例如：ArangoDB)。边有时与相关联的(源或目标)顶点(例如：Titan或JanusGraph)一起存储在同一记录中。否则，边存储在单独的边记录中(例如：ArangoDB)。

3.2在索引结构中存储数据

图数据库通常使用索引来加快查询速度。基于非图形后端的系统(例如RDBMS或文档存储)通常依赖于此类系统中原本的索引方法。原生图形数据库对每个顶点的邻域采用索引结构，通常采用直接指针的形式。

除了使用索引结构来维护数据的位置之外，一些数据库还将图形数据存储在索引本身中。在这种情况下，索引不指向特定的数据记录，但索引本身包含所需的数据。具有此类功能的示例系统有Sparksee/DEX和Cray Graph Engine。为了维护索引，前者使用位图和B+树，而后者使用哈希表。

3.3使用轻量级边的数据结构

某些系统(例如：OrientDB)允许将没有标签或属性的边存储为轻量级边。这样的边存储在对应的源顶点和(或)目的顶点的记录中。这些轻量级边由其目标顶点的ID或指向此顶点的指针表示。这可以节省存储空间并加速解决不同的图查询，例如验证两个顶点的连通性。

3.4将记录与直接指针链接

在基于记录的系统中，顶点和边存储在记录中。为了能够有效地解决连通性查询(即，验证两个顶点是否连接)，这些记录必须指向其他记录。可以存储指向相应连接记录的直接指针(即存储器地址)。例如，边记录可以存储指向具有相邻顶点的顶点记录的直接指针。还可以为每个记录分配一个唯一的ID，并使用这些ID而不是直接指针来引用其他记录。这虽然需要额外的索引结构来根据记录ID查找记录的物理位置，但是如果物理位置改变，更新索引结构通常比更改所有关联的直接指针更容易。

可以给一个系统使用直接指针来避免维护额外的专用索引结构来遍历图形。注意索引仍可用于查找顶点；使用直接指针意味着只有邻接数据的结构没有附加索引。使用直接指针避免了额外的索引遍历从而可以加速图的遍历。但是当需要更新邻接数据时，通常也需要更新大量指针，从而产生额外的开销。

3.5支持并发性和并行性

几乎所有的图数据库系统都支持并发查询，但在几乎所有的系统类中，支持并行查询执行的系统却较少(除了基于OODBMS的图形数据库)。这表明更多的数据库将更多的压力放在单位时间内执行的查询的高吞吐量上，而不是降低单个查询的延迟上。一个值得注意的例外是Cray图引擎，它不支持并发查询，但它确实提供了单个查询的并行化。

查询并发的方法之一是不同类型的锁。例如，WhiteDB使用读写锁提供数据库范围的锁定，从而支持并发读取器，但一次只能有一个写入操作。还可以自动更新元组字段(设置、比较和设置、添加)作为锁定整个数据库的替代方法。WhiteDB本身不强制一致性，它取决于用户正确使用锁和原子性。另一种方法是基于事务的，例如由OrientDB使用，它为分布式事务提供ACID。

一些支持并行查询执行的系统在执行这种并行化查询时明确地优化了通信的数据量。例如，CGE中的计算分布在参与的进程中。为了最大限度地减少所有对所有的通信量，查询结果在本地聚合，并且只要有可能，每个进程只与少数几个对等点通信以避免网络拥塞。微软图引擎和Trinity数据库的底层实现使用的另一种简化通信的方法是减小进程交换的数据块的大小。为此，Trinity维护特殊的访问器，允许访问单元格中的单个属性而无需加载整个单元格，这降低了许多不需要整个单元的操作的I/O成本。几个系统共享的单边通信，使得进程能够直接访问彼此的数据。例如，Trinity可以部署在InfiniBand上利用远程直接内存访问。类似地，Cray的底层实现使多个计算节点的内存资源可以作为单个全局地址空间使用，也支持CGE中的单边通信。这便于在分布式环境中进行并行编程。