2.2.1　图存储的基础概念

在介绍图存储的原理之前，我们先了解下通用的数据库存储引擎，如图2-18所示。数据库存储引擎最主流的有两大类：基于B-Tree的存储引擎和基于LSM-Tree的存储引擎。

这两类之外，当然还有很多其他类型的存储方式。

·基于文件的：有序或无序的。

·基于堆的（也是一种文件）。

·基于哈希桶（hash buckets）的。

·基于索引顺序存储（ISAM）文件系统的。

如果按照数据存储的排列方式，其还可以分为行存储、列存储、KV存储、关联存储等类型。

B-Tree是一种自平衡的树状、有序数据结构，它源自20世纪70年代初的波音实验室（Boeing Research Labs）的研究院发明的数据结构，但是B到底代表什么从来没有定论。B-Tree在数据库存储引擎端通常会实现如下功能：

·保证键排序以支持顺序遍历；

·使用层级化索引来最小化磁盘读操作次数；

·通过块操作来对插入和删除进行加速；

·通过递归算法来保持索引平衡性。

B-Tree可以让数据查找、顺序访问、插入及删除等操作的时间复杂度控制在对数时间内。换句话说，如果数据记录量为100万，以二叉搜索树（binary search tree）的方式，从根节点出发到叶子节点的时间复杂度为O(20)，因为2 ²⁰ ≈1000000。在数据库查询中，数据通常以记录的方式存储在外存中（如磁盘），磁盘上的寻址时间远超CPU计算的时耗（后者的时耗相对而言可以被忽略）。以7200转的磁盘为例，如果磁盘读写的机械臂的换道和平均寻址时间为10ms，并且假设20次操作都需要换道和寻址，那么20次磁盘读操作的最大时耗就是200ms（0.2s）。实际情况中，可能一部分数据记录在B-Tree中是可以做到连续存储的，会节省一部分磁盘寻址、换道操作的时间。

实际上，工业界的B-Tree索引通常都采用辅助索引（auxiliary index）的方式来进行加速。上面描述的二叉搜索树通过辅助索引的递归加速，可以把上面的100万条记录的定位复杂度从O(20)降低到O(3)=log ₁₀₀ 1000000。B-Tree的这种索引加速的特性让其成为几乎所有关系型数据库的默认索引实现方式，当然大多NoSQL类数据库也可以使用，对图数据库的存储引擎而言也一样适用。我们熟知的很多关系型或非关系型数据库如Oracle、SQL Server、IBM DB2、MySQL InnoDB、PostgreSQL、SQLite、MongoDB（早期）、Couchbase等都能看到B-Tree的身影。

图2-19示意的是在一棵扁平的树状结构中，B-Tree如何存储排好序的数据，注意叶子节点的列表索引寻址加速作用。B-Tree对于顺序读写而言是非常高效的，但是维护一个动态平衡的有序数据结构涉及大量的随机写操作，而一个简单的行更新操作可能会让其所在的整个磁盘块都要进行读-改-写操作，成本太高了。因此我们需要介绍第二种树状索引架构：LSM-Tree。

LSM-Tree（Log-Structured Merge-Tree，日志结构化合并树，以下简称LSMT）诞生的背景是大数据情况下，数据量日益增大，写操作较之前的关系型数据库更为频繁，非关系型数据库迅速崛起，这些新兴的数据库和大数据框架更多地用于分析和决策支撑。它设计之初的目标就是提供对磁盘文件的高写入性能索引。LSMT最早是由帕特里克·奥尼尔（Patrick O'Neil）等在20世纪90年代初加州的DEC公司进行数据库研发时发明的，并最终于1996年发布。今天几乎所有的NoSQL数据库实现中都可以看到它的身影：Bigtable、HBase、LevelDB、SQLite、RocksDB、Cassandra、InfluxDB、ScyllaDB等。

LSMT的发展历程如图2-20所示。

LSMT的设计理念用最简单的语言描述为构造了两套大小不同的树状（tree-like）数据结构，一套是较小的内存数据结构C ₀ ，另一套数据结构C ₁ 、C ₂ 、C ₃ ……持久化在硬盘上。新的记录先插入C ₀ ，当其大小超过一定阈值后，C ₀ 中一部分连续的数据会被清除并归并入C ₁ ，同理当C ₁ 足够大之后会裁剪并入C ₂ ，以此类推，逻辑示意图如图2-21所示。

LSMT展现给我们最核心的理念是分层存储加速。充分利用内存加速，当内存空间不够的时候再利用硬盘加速，特别是随着新型存储硬件如SSD、NVMe-SSD、持久化内存PMEM的不断推陈出新，LSMT的理念至今仍然深具影响力。

LSMT并非没有缺点，实际上，它相比B-Tree有两个问题：

·读性能瓶颈（CPU资源消耗更高）；

·（更高的）读以及空间放大效果（占用更多内存、硬盘空间）。

在实际应用中，LSMT与B-Tree通常是同时被使用的。LSMT的读性能问题通过布隆过滤器（Bloom Filter）得到了大幅提升。

布隆过滤器（图2-22）最核心的数据结构是bit-array（位数组，m位），这决定了它的空间占用很小，同时也意味着潜在的速度优势（如果能充分利用数组下标访问的话）。它的主要操作流程涉及多个（k个）哈希函数。在图2-22中，m=18，k=3。

布隆过滤器的优点和缺点共存，它的时间和空间优势是占用空间小、速度快，缺点是存在可能的一类错误（伪阳性）。

显然，布隆过滤器的实际运行效果如何，与m和k的设置直接相关，一方面要让空间占用不要过高，另一方面不要设置过多、过于复杂的哈希函数，以此来保证索引查询效率以及降低伪阳性发生的概率。

相比B-Tree而言，LSMT结合了布隆过滤器可以更广泛地应用在分布式系统架构中，因为其聚合函数（aggregate functions）更适合在完全去中心化的条件下发挥效用。

前面用了不小的篇幅介绍传统数据库的存储引擎，现在来剖析一下图数据库的存储引擎原理。图2-23所示的是图存储引擎、计算引擎、数据管理、操作管理等组件有机地结合成为一个相对完整的产品时的样子。

在前面的章节中，我们介绍过图数据库的计算引擎数据结构，这些数据在逻辑上都是源自持久化存储的数据，或者需要与存储引擎保持某种一致性，以实现数据库的事务正确性（即ACID，原子性、一致性、隔离性与持久性对应的四个英文单词的首字母）。

图的存储无非是最主要的两种基础数据结构——顶点和边，其他所有数据结构都是在这两者的基础上衍生而来的，例如各类索引、中间、临时的数据结构，用来实现查询与计算加速等，以及那些需要异构返回的数据结构，如路径、子图等。

我们来分析一下顶点和边的数据结构及其适合的存储方式。

·顶点：每个顶点可以看作内部元素有着某种规则排列的数组，多个顶点的组合就是一个二维数组。如果考虑到顶点的动态变化（增删改查等涉及读、更新、插入等操作）的需求，向量数组是一种可能的方式。

·边：边的数据结构较顶点更为复杂，因为边不仅有一个unique ID，还需要起点、终点的ID，边的方向以及其他可能的属性，例如权重、时间戳等。显然用二维数组也可以满足边的存储，剩下需要关注的问题是效率，如存储空间占用率、访问效率、索引数据结构的效率等。

支持点、边结合的数据类型如果是完全静态的，也就是说点或边的数量不会变化，不会增加、减少或更新，也不会发生它们各自属性的变化，那么映射到文件系统上的数据结构就可以作为图存储的核心数据结构。如果真是这样的话，我们可以复用传统数据库的存储引擎，例如MySQL的InnoDB或MyISAM（ISAM的变种）引擎，更有甚者，只使用磁盘文件就可以支持静态的图数据库。

然而，效率在大多数情况下是不可或缺的。上面“静态”数据的假设在商业场景中是极少成立的，因为无论是交易系统还是业务管理系统，数据都是动态的、流动的。任何贴近真实业务场景的系统都需要支持对数据（存储引擎）的更新操作。

因此，图存储引擎的架构设计中有一对重要的概念：非原生图与原生图。所谓非原生图是指它的存储与计算是以传统的表结构（行或列数据库）的方式进行的；而原生图则采用更能直接反映关联关系的方式构造而成，也因此会有更高效的存储和计算效率。

如果用关系型数据库MySQL、宽列数据库（wide-column）HBase或二维的KV数据库Cassandra来作为底层存储引擎，也可以把点、边数据以表（或列表）的方式存储起来，它们在进行图查询与计算时的逻辑大体如图2-24所示。举个例子，查询某位员工隶属于什么部门，返回该员工姓名、员工编号、部门名称、部门编号等信息。用关系型数据库来表达，这个简单的查询要涉及3张表之间的关联关系：员工表、部门表和员工部门对照表。

整个查询过程分为如下几步：

①在员工表中，定位007号员工；

②在对照表中，定位007号员工所对应的全部部门ID；

③在部门表中，定位步骤②中的全部ID所对应的部门名称；

④组装以上①～③步骤中的全部信息，返回。

本节前面介绍过数据库存储加速的概念，上面每个步骤的时间复杂度如表2-4所示。

上面的查询（时间）复杂度并没有考虑任何硬盘操作的物理延迟或文件系统上的定位寻址时间，实际的时间复杂度在这样简单的一个查询操作中，如果数据量在千万以上，可能会以分钟计。如果是更复杂的查询，涉及多表之间复杂的关联，则可能会出现多次扫表操作，试想在硬盘上这个操作的复杂度和时延会是何等量级。

如果用原生图的“近邻无索引”模式来完成以上查询，整个流程如图2-25所示。

在原生图上的查询步骤细分如下：

①在图存储数据结构中定位员工；

②从该员工顶点出发，通过员工-部门关系，找到它所隶属的部门；

③返回员工、员工编号、部门、部门编号。

以上第一步的时间复杂度与非原生图（SQL）基本相当，但是第二步会有明显的缩短。因为近邻无索引的数据结构，员工顶点通过3条边直接链接到3个部门。如果SQL查询的方式最优解是O(35)，原生图则可以做到O(8)，分解如表2-5所示。

以上的例子显示，原生图与非原生图在事件复杂度上存在较大的性能差异。以较简单的1度（1-Hop）查询为例，有330%的性能提升。如果是更为复杂、深度更大的查询，则会产生乘积的效果，也就是说随着深度增加而性能差异指数级飙升，如表2-6所示。