2.2.2　图存储数据结构与构图

在实际应用场景中，SQL类数据库很少用来做2层或以上的查询，这是由它的存储结构和计算模式决定的。例如，在一个工商图谱中，从某个企业顶点出发，以递归的方式查询它的投资人（上游），找到所有持股比例大于0.1%的股东，穿透5层，并返回全部的持股路径（及完整的子图）。

显然，这个问题如果用SQL来解决会非常复杂，代码量大，而且因“递归穿透”问题而导致代码可读性低。当然，最大的问题是计算复杂度高，时效性变得很差（性能会指数级地差于基于原生图的图计算系统）。

另外一个方面，SQL非常不善于处理异构的数据，例如持股路径，一条路径上有点、边，而且是不同类型的点（公司和人），从数据组装角度来看，还需要在SQL之外封装如XML、JSON之类的数据结构，才可能支持如此复杂的查询逻辑（业务逻辑）。

在一个有1万条持股关系的表中进行5层查询的耗时为38s,SQL代码如图2-26所示。对比而言，用图数据库在5亿～6亿量级点、边（2.2亿实体、3.3亿条关系）的数据集上完成相应的操作，耗时7ms，两者间相差高达5000倍以上。在实际的场景中，SQL在亿万量级的数据集上操作，是不可能以秒级（例如1000s以内）穿透3层以上再返回的。5层以上的穿透深度，对于SQL类型的数据库而言，只能“望洋兴叹”了。

上面的持股路径查询场景可以概括为一种典型的“工商关系图谱”，它的应用场景较为广泛，如查老板、查关系、KYC（Know Your Customer，银行开户用户尽职调查）、行业研究、投资研究等。

另外，图数据库区别于SQL类数据库的一个很大的特点是对于异构数据的处理，从存储、计算、查询、计算、分析到可视化呈现，不一而足。因为数据流经或持久化在图数据库中最重要的一步就是存储，所以我们就以原生图的模式存储为例来解释一下异构数据的图存储逻辑和场景。

原生图存储最先关注的数据是元数据，其次是次生数据（auxiliary-data），再次是衍生数据或组合数据（combo-data），它们的详细描述如下：

1）元数据。

·实体数据（顶点）。

·关联关系数据（边）。

2）次生数据（辅助数据）。

·实体属性数据。

·关系属性数据。

3）高维、组合数据（衍生数据）。

·多点组合。

·多边组合。

·路径：单路径、多路径、环路等。

·子图、森林。

·跨子图组合数据等。

很显然，从存储的复杂度和计算（穿透或聚合）能力的需求维度上看，以上列表中的数据从上至下由浅及深、由易变难。换言之，存储更多关注的是元数据及离散类型的数据，而高维的组合数据是需要图计算引擎来生产的。如图2-27和图2-28所示的数据，如果一次性、实时生成并呈现，图算力引擎（或图数据库）的支撑必不可少。

元数据与辅助数据的存储的最核心诉求是让顶点、边及其属性可以尽快落盘（持久化），并且在进行读取（查询）的时候有足够高的效率。这个流程用我们最熟悉也最容易的行存储的方式来理解，可以综合为两个部分：“顶点存储+顶点属性存储”和“边存储+边属性存储”。

它们的数据结构见表2-7和表2-8。

当然，顶点及其属性也可以分离存储，这样处理的优点和缺点同样明显。一方面，分离意味着以顶点ID为骨架的数据结构非常精简，可以获得极高的索引加速、读写加速的效果；另一方面，属性可能有很多个（列），分离后更方便在分布式架构中以分布式的方式存放，如以多文件、多实例多文件等方式存放，以此获得更高的并发写入速度。缺点在于增加了额外的寻址、跳转等操作的时耗，以及数据结构与架构的整体设计复杂度。

边及其属性也可以用类似的逻辑，无论是整体存储还是分离存储。边的存储比顶点存储更复杂的地方在于，边的属性设计更为复杂，我们可能需要考虑如下几点：

·边是否需要方向？

·边的方向如何表达？

·边的起点和终点如何表达？

·边能否关联多个起点或多个终点？

·边为什么需要其他属性？

以上问题没有唯一的标准答案。在前面的章节中已经涉及其中一部分问题的答案，例如边的方向问题，我们可以通过在一条以行存储模式（row-store）连续存储的边记录中向后放置起点ID与终点ID来表达边的方向。当然，这个问题很快就会引发另一个问题：如何表达反向边（逆边）？这是图计算、图数据库的存储与计算中一个非常重要的概念。假设在记录中存放了如下的一条边：

当通过索引加速数据结构找到边的ID或起点的ID时，可以顺序读取其后的终点ID，然后在图中继续进行遍历查询。但是，如果先找到终点的ID，如何反向（逆向）读取到起点的ID来同样地进行遍历查询呢？

这个问题的答案不止一个，我们可以设计不同类型的数据结构来解决，例如，在边记录中设置一个方向标识属性，然后每一条边记录会正反方向各存储一遍：

当然，还有其他很多种解决方案，例如：以顶点为中心的方式存储，包含点自身的属性，以及与它关联的顶点及属性的序列，这种方式同样也可以被看作近邻无索引存储，并且不再需要设置单独的边数据结构。这种方式的优缺点不在此展开论述，有兴趣的读者可以进行独立的延展分析。

反之，我们也可以以边为中心设计存储数据结构。实际上这种结构在学术界和社交网络图分析中非常常见，例如Twitter的用户关注关系网络仅使用一个边文件即可以表达，文件中的每一行记录仅两列，其中第一列为起点，第二列为终点，每一行记录表达的是第二列用户关注第一列用户，见表2-9。

在表2-9的基础上，每一行记录的存储逻辑可以得到大幅扩展，例如加入边的唯一化ID来进行全局索引定位，加入更多的边的属性，加入边的方向，或以自动扩展的方式对每一条原始的表达关注关系的边，自动增加一条反向的表达被关注关系的边。

在表2-7的顶点实体列表中，细心的读者一定会提出一个问题，如何存放异构类型的实体（顶点）数据？因为在传统的数据中，不同类型的实体会以不同的表的形式聚合，如我们之前讨论的员工表、部门表、公司实体表，以及不同实体间的关联关系映射表等。在图数据库的存储逻辑中，异构的数据（以实体为例）是可以融合在一张大表中的，这也是为什么图被称作高维的数据库。

下面以金融行业中的卡交易数据为例来说明异构的数据如何存储和查询，在表2-10中示例的是用关系型数据库表达的卡交易的3张核心表的记录结构。

如果上面的关系表中的实体与关联关系用图数据库来表达，可视化呈现后效果如图2-29所示。

在图2-29的银行卡交易的异构网络中，有4类实体与2类关系，它们的定义分解如下：

·实体：包括账户、卡［包含一个子类或属性（电话）］、设备和交易。

·关系：包括交易关联关系和拥有关系（或账户层级关系）。

显然，图2-29中的这种实体分类（建模）方式并不是唯一的，我们还可以以更精简的方式来实现建模，例如只有2类实体和1种关系。

·实体：直接发生交易的卡（卡的属性包含账号、电话）、商户（商户属性信息）。

·关系：交易（属性包括交易时间、设备、环境信息等）。

细心的读者一定会发现，后面这种建模思路与前面的区别在图论中被概括为：多边图和单边图。也就是说，在多边图的任意一对顶点（银行卡）中，可以直接有多条交易关联关系（边），而在单边图的任意一对顶点中，最多只能表达一条边（一条关系）。另外，在单边图中，边上所承载的属性很少，通常只有一个标签（label），而多边图上，边因为表达的是交易，它可能有很多属性信息。

事实上，在工业界的图数据库实现中，不同的厂家确实采用了不同的实现方式。笔者倾向于认为多边图可以向下兼容单边图，并且多边图的实现显然更贴近真实的场景和人类的思维方式。另外，虽然多边图的存储设计会更为复杂，但是它可能会节省更多的存储空间。

以两个账户之间有1万笔交易为例：如果用单边图，它需要10002个实体，以及20000条边来表达；如果用多边图，只需要2个实体和10000条边。两者的存储有3倍的差异，多边图比单边图存储空间占用节省了2/3（67%）。

不过，在某些场景下，单边图的查询模式有其存在的道理。例如在反欺诈场景中，常见的是查找是否有两个信用卡申请或贷款申请使用了同样的电话号码与地址，单边图的构图如图2-30所示。

这样构图的优势在进行“模式”查询的时候才会体现出来，因为判断（任意）一个申请是否存在欺诈，是先在图中查找该申请与任意其他可触达的申请之间是否形成了某种环路的拓扑结构，两个申请间通过电话与地址关联，形成了一个深度为4（4步或4层）的环路，即从申请A出发，沿电话可达申请B，再通过地址可返回申请A，算作一条环路。如果从该申请出发，可以找到很多类似的环路（设定一个阈值，例如>5），那么该申请为欺诈的可能性高，进而可以拒绝该卡（贷款）申请。

如果是多边图，电话、地址等信息是附属于卡申请之下的属性，反欺诈的查询逻辑就完全不同于上面的环路查询了。

本节为大家提供了一些真实场景中的例子，以及可能的多种构图方式，在进行任何图数据库的设计过程中，没有所谓的唯一方案。图数据库非常贴近业务，它的建模直接反映了业务逻辑。存储位于图数据库的最底层，存储的效率与灵活性决定了在其之上的计算和查询的效率与灵活性。后面的章节将进行更深入的探讨和剖析。 w1vUoSK23xJ1JMdLNIju20GZFF8TadlxwAR9vvZ/yfrLUkh1XKgmhFXWmDCyOl2N